Assignment loops when overwriting a binding

[Feliix42]

When compiling the following ohuac file:

ns some_ns;

use sf house (move_house, move_in_one, evict_one, house_information);

fn main(house: House, target_address: String, humans: Vec<Human>) -> House {
    let house = move_house(house, target_address);
    let (house, humans) = move_in_one(house, humans);
    let (house, humans) = move_in_one(house, humans);
    let (house, humans) = move_in_one(house, humans);

    house_information(house);

    evict_one(house)
}

the compiler produces this DFG representation. Normally, a user would assume that the function move_house is provided with two of the main arguments upon call, but the output produced is the following:

{
    "target": {
        "operator": 1,
        "index": 0
    },
    "source": {
        "type": "local",
        "val": {
            "operator": 1,
            "index": -1
        }
    }
},

This is a loop where the input of the operator pulls from its output without ever being provided an initial value. The same happens for the three following lines, where both function arguments are affected. I know the example above does not make any real "sense", but I wouldn't rule out the possibility that someone will have to write something similar in a non-nonsense algorithm.

[sertel]

It seems like we have problems with variables that have the same name. Either that or we have problems with env vars that have the same name as a variable.

[Feliix42]

Yeah, I discussed this with @JustusAdam on Wednesday and as the problem also occurs with the move_in_house calls I would guess it's the first.

[JustusAdam]

The fundamental question, as I have explained to @Feliix42, is that we must ask ourselves if there's any chance or desire for us to introduce recursion via "tying the knot", that is self referential variable assignment.

A simple example would be this for instance:

let xs = 5 : xs
in xs
-- [5,5,5,5,5....]

Now, I am not sure if we can, or want, that kind of value level recursion, but we might want to have self referencing algorithms:

foo x =
    if x < 3
        then x
        else foo (x - 1)

This is the reason why, right now, you get nonsense when using self reference, because it assumes you want to do recursion, the support for which is not quite complete yet.

I was thinking whether we should instead use a form of explicit recursion, where recursive have to be explicitly annotated thusly. In that case we could allow those kinds of rebinding.

[sertel]

Maybe I don't fully understand the problem but I feel that there is not such a fundamental issue here.

The following two cases exist:

Case 1: Variable Scoping

let x = 6 in
  let x = 5 + x in 
    x

Here the bound variable x appears on the right-hand side in an argument position, i.e., x is just passed to a function.

Case 2: Recursion

let f =  (\a -> 
         if a < 3 
           then a 
           else f (x-1))

Here f is used on the right-hand side in function position and therefore this is a recursive definition.

It feels to me like the example from @Feliix42 falls entirely into the first category.

[JustusAdam]

I think it is not a good idea to make the same syntax behave differently based on how a value is used, or what it's type is. You can actually come up with esoteric examples of where that distinction cannot be safely made without a proper type checker.

But even if it was possible I don't think we should do that. This will be messy to implement and make for confusing logic in the compiler.

Besides I believe this is generally inconsistent behaviour in a language (alang) that makes no fundamental distinction between functions and values.

I would not be opposed to making the "value" assumption the default and instead adding a rec keyword for explicitly marking functions or values that are used recursively.

Actually I would be even more in favour if we disallowed rebinding and shadowing of names. I think it leads too easily to errors where you accidentally pass the wrong value as a result of refactoring. (Especially in an untyped language)

Aka

let x = ... in
  let x = ... in

Would be an error.

[sertel]

I was going to introduce an internal letrec on ALang anyways. All that this detection would have done would have been a transformation to a letrec term in case of a recursion. Anyways, there is a lot more to be thought of for recursion, so let's set this aside for now.

I like the idea of not being allowed to rebind variables. I'm not sure though whether we end up in situations where a variable is bound in a library call which is then inlined by us.

I feel like our SSA pass should just handle this situation properly.

[JustusAdam]

Yes exactly. I think disallowing shadowing and rebinding should be just a "nice feature", not an invariant the compiler depends on. So if you agree I'll add a pass at the beginning to error on rebound variables and for those that are rebound after inlining, SSA should fix that, or more precisely the renaming during inlining.

[sertel]

That sounds good, please go ahead.