Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

lazy+andThen+map3 overflowing the stack #9

Open
Janiczek opened this issue Feb 15, 2019 · 7 comments
Open

lazy+andThen+map3 overflowing the stack #9

Janiczek opened this issue Feb 15, 2019 · 7 comments

Comments

@Janiczek
Copy link

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

Ellie with a SSCCE ➡️ 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)

recursion

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

@evancz
Copy link
Member

evancz commented Feb 15, 2019

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
Copy link
Author

@evancz I can try and dust off my math to compute the probabilities 🙂 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
Copy link
Author

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

@mgold
Copy link

mgold commented Feb 16, 2019

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
Copy link
Member

evancz commented Mar 18, 2019

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
Copy link
Author

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
Copy link

mgold commented Mar 19, 2019

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants