Iterate produces StackOverflow errors

Question

So I just started out with Frege and Haskell as well. I have experience with functional languages, since I was using Clojure for a couple of years now. The first thing I wanted to try out is my usual approach at the Fibonacci numbers.

next_fib (a, b) = (b, a + b)
fibs = map fst $ iterate next_fib (0, 1)
fib x = head $ drop x fibs

This is how it turned out in Frege. It works, but for very high numbers for fib, e.g. (fib 4000), it throws StackOverflow errors. This surprised me, because same functions in Clojure would work just fine. Is this a Frege bug or am I getting the whole lazy evaluation thing wrong?

Answer 1

You probably don't "get the whole lazy evaluation thing wrong", but you're bitten twice by too lazy evaluation in this case.

And although GHC essentially works exactly the same as Frege in this regard, the outcome is different and seemingly unfavorable for Frege.

But the reason that Haskell can get awya with really big thunks[see below], while Frege early aborts with stack overflow is the way the runtime systems manage heap and stack. The Haskell RTS is flexible and can devote huge portions of the available memory to the stack, if the need arises. While Frege's runtime system is the JVM, which usually starts out with a tiny stack, just enough to accomodate a call depth of a few hundred. As you have observed, giving the JVM enough stack space makes the think work, exactly like it would in GHC.

Because of the ever scarce stack space in the JVM, we have developed some techniques in Frege to avoid unwanted and unneeded laziness. Two of them will be explained below. In the end, in Frege you are forced to control bad effects of laziness early, while the GHC developer can happily code away without having to take notice.

To understand the following, we need to introduce the concept "thunk". A thunk is first and foremost some yet to be evaluated expression. For example, since tuples are lazy, an expression like

(b, b+a)

is compiled to an application of the tuple constructor (,) to b and {a+b} where the notation { e } for the sake of this discussion means some implementation dependent representation of a thunk that promises to compute the expression e when evaluated. In addition, a thunk memoizes its result upon evaluation, so whenver the same thunk is evaluated again, it just returns the precomputed result. (This is only possible in a pure functional language, of course.)

For example, in Frege, to represent thunks there is a class Delayed<X> that implements Callable<X> and arranges for memoization of the result.

We shall now investigate what the result of

next_fib (next_fib (0, 1)) 

is. The inner application results in:

(1, {0+1})

and then the outer one computes from that:

({0+1}, {1+{0+1}})

We see here that thunks can get nested in other thunks, and this is the problem here, since every application of next_fib will result in a tuple that will have as its elements thunks that have thunks of the previous iteration nested inside them.

Now consider what is happening when the thunk for the 4000th fib-number gets evaluated, which happens, for instance, when you print it. It will have to perform an addition, but the numbers to add are actually both thunks, which must be evaluated before the addition can take place. In this way, each nested thunk means an invocation of that thunks evaluation method, unless the thunk is already evaluated. Hence, to print the 4000th number, we need a stack depth of at least 4000 in the case when no other thunk of this series was evaluated before.

So the first measure was to replace the lazy tuple constructor with the strict one:

(b; a+b)

It doesn't build thunks but computes the arguments right away. This is not available in Haskell, to do the same there you need to say something like:

let c = a+b in b `seq` c `seq` (b,c)

But this was not the end of the story. It turned out that the computation fib 4000 still overflowed the stack.

The reason is the implementation of iterate that goes like this:

iterate f x = x : iterate f (f x)

This builds an infinite list

[ x, f x, f (f x), f (f (f x)), ...]

Needless to say, all the terms except the first one are thunks!

This is normally not a problem when the list elements are evaluated in sequential order, because when, for example, the 3rd term

{f {f x}}

gets evaluated, the inner thunk is already evaluated and returns the result right away. In general, we need only enough stack depth to reach the first previously evaluated term. Here is a demo straight from the frege online REPL at try.frege-lang.org

frege> next (a,b) = (b; a+b) :: (Integer, Integer)
function next :: (Integer,Integer) -> (Integer,Integer)
frege> fibs = map fst $ iterate next (0,1)
function fibs :: [Integer]
frege> fib = (fibs!!)
function fib :: Int -> Integer
frege> map (length . show . fib) [0,500 ..]
[1,105,209,314,418,523,627,732,836,941,1045,1150,...]
frege> fib 4000
39909473435004422792081248094960912600792...

Here, with the map, we force evaluation of every 500th number (as far as the REPL demands output, it will only print initial portions of infinite lists), and compute the length of the decimal representation of each number (just so as not to display the large resulting numbers). This, in turn forces evaluation of the 500 preceding numbers, but this is ok, as there is enough stack space for that. Once that is done, we can even compute fib 4000! Because now, all the thunks up to 6000 are already evaluated.

But we can do even better with a slightly better version of iterate, which uses the head strict constructor (!:):

a !: as = a `seq` (a:as)

This evaluates the head of the list right away, which is appropriate in our case.

With the two changes, we get a program whose stack demand does not depend on the argument of fib anymore. Here is the proof:

frege> iterate' f x = x !: iterate' f (f x)
function iterate' :: (a->a) -> a -> [a]
frege> fibs2 = map fst $ iterate' next (0,1)
function fibs2 :: [Integer]
frege> (length . show . (fibs2 !!)) 4000
836
frege> (length . show . (fibs2 !!)) 8000
1672
frege> (length . show . (fibs2 !!)) 16000
3344
frege> (length . show . (fibs2 !!)) 32000
6688
frege> (length . show . (fibs2 !!)) 64000
13375
frege> (length . show . (fibs2 !!)) 128000
java.lang.OutOfMemoryError: Java heap space

Well, we'd need more heap space now to keep more than 100.000 huge numbers. But notice that there was no stack problem anymore to compute 32.000 new numbers in the last step.

We could get rid of the heap space problem with a simple tail recursive definition that doesn't need to mark all those numbers:

fib :: Int -> Integer
fib n = go n 0 1 where
    go :: Int -> Integer -> Integer -> Integer
    go 0 !a !b = a
    go n !a !b = go (n-1) b (a+b)

I guess this would be even faster than traversing the list.

Unlike(?) in Clojure, direct list access is O(n), and long lists consume lots of space. Therefore, if you need to cache something and have an upper limit, you better use arrays. Here are 2 ways to construct an array of 10000 fibs:

frege> zzz = arrayFromList $ take 10000 $ map fst $ iterate (\(a,b) -> (b; a+b)) (0n,1)
function zzz :: JArray Integer
frege> elemAt zzz 4000
39909473435004422792081248094960912600792570982820257 ...

This works, because the intermediate list should never exist as a whole. And once created, access is O(1)

And there is also a special function for creating caches like that:

yyy = arrayCache f 10000 where 
       f 0 a = 0n
       f 1 a = 1n
       f n a = elemAt a (n-1) + elemAt a (n-2)
fib = elemAt yyy

This avoids even the intermediate list, all the tuples, and so on.

This way, you can keep your good habit of prefering combinators over explicit recursion. Please give it a try.