Cyclic value with lambda

I’d like to understand why the compiler rejects this code:

module Main exposing (main)

type T a
    = T
        { elem : a
        , next : () -> T a
        }

f : T a -> T a
f (T inner) =
    let
        next =
            \() -> v

        v =
            T
                { elem = inner.elem
                , next = next
                }
    in
    v

The error message says there is a cyclic dependency between next and v in the let expression, and it links to a web page at https://elm-lang.org/0.19.1/bad-recursion.

That web page says that if there is “a lambda between the definition and the use”, then it is okay. This code looks to me like there is a lambda between the definition of v and the use of v in next, so I would expect this code to be okay. But the compiler still rejects it.

What am I missing?

I don’t have an answer but playing with the code I discovered that this compiles:

f : T a -> T a
f (T inner) =
    let
        v _ =
            T
                { elem = inner.elem
                , next = \() -> v ()
                }
    in
    v ()

and this doesn’t

f : T a -> T a
f (T inner) =
    let
        v =
            \_ ->
                T
                    { elem = inner.elem
                    , next = \() -> v ()
                    }
    in
    v ()

I do not understand why as in my mind the two are equivalent.

Same here. If I replace the lambda’s v in my original code sample with f (T inner) then it compiles, but I believe those two expressions should have the same value.

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

next doesn’t create a T. It references an existing T via the “free” variable v. This means that the lambda doesn’t really break the cycle. next refers to v which refers to next. For a lambda/function to break the cycle, it needs to create the cyclic value as part of its evaluation,

1 Like

That sounds pretty reasonable!

Would this situation be a useful addition to the error message catalog? I ask because the error message was specifically about let expressions, and it links to the bad-recursion web page, and from this conversation here I’m getting the impression that web page is just about top-level values, not let expressions.

1 Like

Ah, I have it set up such that when the compiler links to a hint, it goes through a redirect that will allow me to change the content later on. So it should be possible to fix this without a new release or anything.

I’ll have to have a read through the bad-recursion page to see if the best path is:

  1. Just add a note there
  2. Have a separate page for when the error is triggered in a let so people get the exactly relevant information in each scenario.

I suspect (2) is better, but that would need a 0.19.2 to get the compiler output updated, so it’d be a while before that would happen!

2 Likes

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.