lazy+andThen+map3 overflowing the stack

[Janiczek]

Use of these three (or maybe two, I'm not sure about map3) results in "too much recursion."

Ellie with a SSCCE :arrow_right: https://ellie-app.com/4Kv76dc7Hkpa1

type Expr
    = Int_ Int
    | Plus2 Expr Expr
    | Plus3 Expr Expr Expr

exprGenerator : Generator Expr
exprGenerator =
    Random.uniform
        (Random.map Int_ (Random.int Random.minInt Random.maxInt))
        --[ Random.map2 Plus2 lazyExprGenerator lazyExprGenerator
        [ Random.map3 Plus3 lazyExprGenerator lazyExprGenerator lazyExprGenerator
        ]
        |> Random.andThen identity

lazyExprGenerator : Generator Expr
lazyExprGenerator =
    Random.lazy (\() -> exprGenerator)

Switching the recursive generators (Plus3 for Plus2) or changing the seed to 1 shows non-failing case.

[evancz]

Right now you have a 50% of terminating and a 50% of continuing. Continuing means three chances to continue again. So I think the expected value for the depth is just really high.

I am having trouble calculating the expected value of the depth, but I think that's the next step before saying this is an issue with the package.

In the meantime, my first instinct is to switch from uniform to weighted and make termination more likely. Non-termination is still possible though, so for a 100% reliable fix, you'd want to put in a hard depth limit. So you pass maxDepth in the generator, and on each recursion you give maxDepth - 1. If maxDepth <= 0 then you always terminate.

---

P.S. I am struggling because the probabilities get real complicated in the map3 case:

• 1/8 chance of terminating
• 3/8 chance of starting one extra level
• 3/8 chance of starting two extra levels
• 1/8 chance of starting three extra levels

Putting together two uniform distributions does not result in a uniform distribution, but I do not recall enough probability theory to figure it out. Would love to see someone figure it out though!

[Janiczek]

@evancz I can try and dust off my math to compute the probabilities :slightly_smiling_face: But I wonder, do you consider this a bug, or just a thing that would happen every now and then? Is this eg. solvable with some kind of trampolining?

[Janiczek]

(FWIW, I think the comment about hard depth limit is something worthy of being in the package documentation. It solved my problem.)

[mgold]

It's pretty easy to use andThen to request a limitless amount of random numbers:

endless : Generator (List Int)
endless =
    Random.int 0 20 
      |> Random.andThen (\x -> Random.map (\xs -> x :: xs) endless)

What we're dealing with here though is a computation that might terminate quickly, or might balloon so much that termination becomes increasingly improbable, though never impossible.

Either way, I think we're up against the halting problem, so that's not something code can solve. We should advise people to use a hard depth limit, or perhaps a 1/depth chance of recursing. We can improve the documentation when the error happens, perhaps pointing to a markdown page that explains the issue in depth (we already have some of these).

[evancz]

In terms of documenting this, where in the documentation should such a note be? Why would someone with this problem be reading the docs for map3 or uniform when they run into this? Or is there some generator that they are guaranteed to have read in full before having this problem?

The root issue is that recursion may not terminate, which is not in the API of this library directly. It's just a thing about recursion. So it's not clear to me that this kind of thing can/should be documented in this library.

[Janiczek]

I was thinking about putting the note next to andThen. Just a reminder about the possibility of infinite recursion. Other functions in the module probably don't have that ability to recurse infinitely on their own?

[mgold]

I agree, it belongs next to andThen. I can confirm that none of the maps can explode on their own.

Perhaps something like:

A word of caution: It's surprisingly easy to use this function to make a generator that requests an infinite amount of randomness. This will crash your program! Be sure there is some kind of branching that will guarantee you stop eventually. A common way to do this is with a depth limit, which is a number that only gets smaller as you ask for more randomness, and you stop once it gets small enough.