Identification of recursive functions

[Abhiroop]

The frontend currently fails to identify certain recursive functions. A minimal example:

foo : Int
foo =
  let v = 5 in
  foo

main = foo

The desugared code for this:

let v0 = let v1 = 5 in v0 in v0

whereas it should generate

letrec v0 = let v1 = 5 in v0 in v0

[Abhiroop]

Perhaps fixed by (needs testing) https://github.com/svenssonjoel/Sense-VM/commit/a39c7f4f8ac661bdace9ba93140162d97abd0510

[Abhiroop]

Seems to work!

[Abhiroop]

This issue is reoccurring:

foo : Int -> Int
foo = \x -> case x of
                 1 -> 1
                 _ -> let m = (3,2) in
                        foo (x - 1)
main = foo 3

The generated frontend IR for this:

let v4 = \ v5 -> case v5 of {
  v3 -> case v3 of {
    1 -> 1;
    _ -> let v2 = (3, 2) in v0 (v3 - 1)
  }
  }
in let v0 = v4 in v0 3

whereas it should be:

letrec v4 = \ v5 -> case v5 of {
  v3 -> case v3 of {
    1 -> 1;
    _ -> let v2 = (3, 2) in v4 (v3 - 1)
  }
  }
in let v0 = v4 in v0 3

[Rewbert]

This is really weird... I'll try to figure out exactly where it is misunderstanding crap

[Rewbert]

I think I see what the issue is, at least. The initial part that causes the issue is this part:

foo : Int -> Int
foo = \x -> case x of
                 1 -> 1
                 _ -> let m = (3,2) in
                        foo (x - 1)

We have a function foo which has the body of a lambda expression. We might be checking if a function is recursive in quite a greedy way - we only check if the name of the function appears in the AST of the body. If it does, we say that it is recursive.

After renaming we get this

v0 : Int -> Int;
v0 = \ v1 -> case v1 of {
  1 -> 1;
  _ -> let v2 = (3, 2) in v0 (v1 - 1)
}

Which also looks fine. We have a function v0 and within the body of v0 we still have the reference to v0, so it is still considered recursive.

Now we get to the lambda lifter. The lambda lifter will lift any anonymous function to the top level, give it a name, and replace the original lambda function with a reference to the lifted function. This gets turned to this code:

v4 : Int -> Int;
v4 v3 = case v3 of {
  1 -> 1;
  _ -> let v2 = (3, 2) in v0 (v3 - 1)
}
:  Int -> Int

v0 : Int -> Int;
v0 = v4 :  Int -> Int

The anonymous function gets lifted to the top level and given the name v4, and v0 then becomes v0 = v4. All good. However, the lifted function does not replace the occurrence of v0 in the body with v4, as that's not what the lifter is supposed to do.

The compiler works as intended when the definition is fun x = ... because then there is no lambda that will be lifted in this case. A quick fix is to perhaps when parsing the language, if you see foo = \x -> ..., turn that into foo x = ...? It's a quick, greasy fix!

Perhaps a slightly better way of doing things is to when we are simplifying things towards the end, 'follow' variables, and if they simply reference another variable we replace the occurrence of the first variable with the latter. In this case that would solve the issue. Eventually, the body of v4 would replace the v0 with v4. This would perhaps be some simple form of normalization? Or perhaps an optimization? It would eliminate a call in the resulting code.

I can probably implement and push the first fix (the parser one) very quickly @Abhiroop , if you think this solution is fine for now.

[Abhiroop]

@Rewbert Well identified!

Instead of the quick fix, let's fix the lambda lifter later such that it replaces all the calls in the lifted lambda's body with the appropriate variable names.