Let binding cyclic value detection is stronger than top level

[HuwCampbell]

Quick Summary:

Top level definitions allow cyclic values to be declared when the recursive call is guarded behind a lambda.

In let bindings however, they're disallowed more strongly, based on whether the binding itself has arguments. This is a different algorithm, and forbids working programs.

SSCCE

This works (as per the bad-recursion document)

import Json.Decode as Decode exposing (Decoder)

decodeComment : Decoder Comment
decodeComment =
  Decode.map4 Comment
    (Decode.field "message" Decode.string)
    (Decode.field "upvotes" Decode.int)
    (Decode.field "downvotes" Decode.int)
    (Decode.field "responses" decodeResponses)


decodeResponses : Decoder Responses
decodeResponses =
  Decode.map Responses (Decode.list (Decode.lazy (\_ -> decodeComment)))

While this doesn't

import Json.Decode as Decode exposing (Decoder)

decodeResponses : Decoder Responses
decodeResponses =
  let
    decodeComment =
      Decode.map4 Comment
        (Decode.field "message" Decode.string)
        (Decode.field "upvotes" Decode.int)
        (Decode.field "downvotes" Decode.int)
        (Decode.field "responses" resulting)

    resulting =
      Decode.map Responses (Decode.list (Decode.lazy (\_ -> decodeComment)))
  in
  resulting

Even though these definitions are semantically identical.

• Elm: 0.19.1

Additional Details

Code in question is checkCycles in Canonicalize.Expression.

case binding of
  Define def@(Can.Def name args _) ->
    if null args then
      Result.throw (Error.RecursiveLet name (toNames otherBindings defs))
    else
      checkCycle otherBindings (def:defs)

This is overly strict and could instead use the toNodeOne and toNodeTwo approach from Canonicalize.Module.

While the above example is indeed liftable to the top level, not all let bindings are, and the alternative (to put everything in the let behind a function call, means potentially a lot of extra computation may occur.

[github-actions]

Thanks for reporting this! To set expectations:

• Issues are reviewed in batches, so it can take some time to get a response.
• Ask questions in a community forum. You will get an answer quicker that way!
• If you experience something similar, open a new issue. We like duplicates.

Finally, please be patient with the core team. They are trying their best with limited resources.

[GordonBGood]

This is overly strict and could instead use the toNodeOne and toNodeTwo approach from Canonicalize.Module.

You are correct that global and local recursive bindings are handled differently in Elm version 0.19.1, but Evan had a reason for that: He was thinking toward being able to generate WASM instead of JavaScript and WASM didn't have a garbage collector at that time so he was thinking of using reference counting. At the global level, there is never any need for reference counting as global allocations are never freed until the program ends so the more lax checks are all right there, but he was thinking that a some local values such as Custom Type's could be allocated to the heap and thus require reference counting, and a cyclic reference to something requiring reference counting would cause a memory leak.

However, nothing has been done about generating code to other back-ends, so this restriction has never been necessary so far, but perhaps it may be used sometime in the future and this would avoid a breaking change when it is.

Actually, the compiler misses a case that should have been allowed even with this limitations as per the following code, which is in roc-lang style (Roc's only way of creating functions):

type CIS a = CIS a (() -> CIS a)
makeCIS : a -> CIS a
makeClosure a
  let 
    v = a
    makeit = \ () -> CIS a (\ () -> makeit v)
    -- the following does the same "under the covers" by "unclosurefying"...
    -- makeitfixed = \ x -> CIS x (\ () -> makeitfixed x)
  in makeit a

For the above code, the compile checks if makeit has any parameters and sees it as if is a simple assignment to a value rather than recognizing that the "value expression" being assigned is actually a lambda. This would be easy to fix by just having the compiler check that the "value expression" is a lambda or not and if so allow the cyclic reference.

In fact, just because the assignment is to a function doesn't guarantee that there isn't a memory leak as Evan assumed: the function may be a closure function capturing data from outside its scope, and in this case there may also be storage allocated to the heap for the captured values as part of the data for the closure function. Evan may have considered this, and at any rate there is a fix to "unclosurefy" a function by "under the covers" passing the captured values as arguments to the outer function hidden to the programmer, which is basically what most closure function implementations do in a different way anyway.

So the extra restriction for local recursive references did have a valid reason which may or may not apply going forward...