Cyclic value with lambda

It is hard to detect “good recursion” statically. I forget if it’s undecidable, so I’ll just go with “hard” in this conversation!

I wrote about some of these problems here in 2017.

In the current design, you can have recursive functions anywhere you want, but you can only have recursive values at the top level. So recursive functions can be in let expressions, but recursive values cannot be in let expressions. (This hopefully will be helpful to people working on GC for Elm since they will not need to do cycle detection for values.)

As for why v _ = ... is different than v = \_ -> ..., the compiler does not currently turn \x -> \y -> ... into \x y -> ... or do any coalescing of functions. The ideal thing to do would be to detect call sites and generate versions of the function like “called with all arguments” and “called with three arguments then one argument” so that the overhead of partial application is as low as possible. Since the compiler cannot do that, the functions are left as you wrote them since someone probably wouldn’t write code like f x y = \z -> ... by accident.

The rules for detecting cyclic values in let are pretty straight forward. Detect the cycle, and then see if any of the definitions are values by simple syntactic classification.

6 Likes