stack overflow iterating on a list

[tittoassini]

Description

A simple recursive iteration on a long list causes a stack overflow error.

I have seen this problem already reported, but I would like to add another case, especially given that it heavily affects the package that I am trying to port to eta.

Steps to Reproduce

git clone https://github.com/Quid2/flat cd flat git checkout d66cc7fc6880b50d81730fb9c075f7681889064f etlas run listTest

Exception in thread "main" java.lang.StackOverflowError at flat.data.flat.encoder.Prim.$L$wa15$1(Prim.hs:316) at flat.data.flat.encoder.Prim.$La17$1(Prim.hs) at flat.data.flat.encoder.Prim.eBoolF(Prim.hs:316) at flat.data.flat.encoder.Prim$eBoolF.apply2V(Prim.hs:316) at eta.runtime.apply.PAPSlow.apply(PAPSlow.java:71) at eta.runtime.apply.PAPSlow.apply1V(PAPSlow.java:197) at eta.runtime.thunk.Thunk.apply1V(Thunk.java:156) at flat.data.flat.Instances$sat$215.apply1V(Instances.hs) at eta.runtime.thunk.Thunk.apply1V(Thunk.java:156) at flat.data.flat.Instances$sat$215.apply1V(Instances.hs) at eta.runtime.thunk.Thunk.apply1V(Thunk.java:156) at flat.data.flat.Instances$sat$215.apply1V(Instances.hs) ....

The code is simply:

import Data.Flat

longBools = replicate 1000000 True

main = print $ flat longBools

And what the code does is to iterate on the list encoding one boolean at the time.

Current Eta & Etlas version: eta-0.8.6b2.

etlas version 1.5.0.0 compiled using version 2.1.0.0 of the etlas-cabal library

[rahulmutt]

@tittoassini By chance do you use some form of continuation passing style in implementing flat? If so, you'll need to add on a trampoline.

For now, can you let me know whether this works?

import Data.Flat
import Data.Function (trampoline)

longBools = replicate 1000000 True

main = print $ trampoline $ flat longBools

If that doesn't work, I'll see if I can assist you in finding the right location inside the definition of flat or its dependencies that you'll need to add it in.

[tittoassini]

I tried that, but no joy.

I also added a top level trampolineIO but it made no difference:

longBools = replicate 1000000 False

main = trampolineIO $ do print $ (trampoline $ flat longBools)

The instance of Flat for [a] was generated by generics but I have rewritten it explicitly so that I could add a 'trampoline' on encode:

instance {-# OVERLAPPABLE #-} Flat a => Flat [a] where encode = trampoline . encodeListWith encode ...

{-# INLINE encodeListWith #-} -- |Encode as a List encodeListWith :: (t -> Encoding) -> [t] -> Encoding encodeListWith enc = go where go [] = eFalse go (x : xs) = eTrue <> enc x <> go xs

But I still get a stack overflow:

Exception in thread "main" java.lang.StackOverflowError at flat.data.flat.encoder.Prim.$La17$1(Prim.hs) at flat.data.flat.encoder.Prim.eBoolF(Prim.hs:317) at flat.data.flat.encoder.Prim$eBoolF.apply2V(Prim.hs:317) at eta.runtime.apply.PAPSlow.apply(PAPSlow.java:71) at eta.runtime.apply.PAPSlow.apply1V(PAPSlow.java:197) at eta.runtime.thunk.Thunk.apply1V(Thunk.java:156) at flat.data.flat.Instances$sat$152.apply1V(Instances.hs) at eta.runtime.thunk.Thunk.apply1V(Thunk.java:156) ...

By the way, reading your blog, I got the impression that 'trampoline' would solve the stack overflow problem on all computations in its context so if the trampolineIO in main does not fix it then there is no way of fixing it by applying trampoline on any of the subcomputations, is this correct?

On Tue, 13 Nov 2018 at 21:59, Rahul Muttineni [email protected] wrote:

@tittoassini https://github.com/tittoassini By chance do you use some form of continuation passing style in implementing flat? If so, you'll need to add on a trampoline.

For now, can you let me know whether this works?

import Data.Flatimport Data.Function (trampoline)

longBools = replicate 1000000 True

main = print $ trampoline $ flat longBools

If that doesn't work, I'll see if I can assist you in finding the right location inside the definition of flat or its dependencies that you'll need to add it in.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/typelead/eta/issues/901#issuecomment-438434328, or mute the thread https://github.com/notifications/unsubscribe-auth/AABYwRRDJgmz-by-By33Dt876XK2J2mDks5uuzKpgaJpZM4YWe2E .

-- Dr. Pasqualino "Titto" Assini

http://networkpolitics.svbtle.com http://quid2.org/

[rahulmutt]

@tittoassini trampoline solves the SOE on the "thread" of computation that is tail-called, not on every possible computation in the problem. Doing so would kill lots of performance since that amounts to setting up a fresh trampoline on every case expression in your program. The reason why your encodeListWith solution didn't work is that the encode definition in the instance you defined will get called recursively and each recursive invocation is setting up a fresh trampoline.

The solution I came up with looks like this:

The current behavior of nested trampolines is that the nested trampoline will start fresh, which I think should not be the case. Instead, the nested trampoline should be a no-op.