This is the type that I call the view length / foldr. This happens when a recursive function is used to compute the strict argument of the function application that makes up the result. For comparison:
-- naive computation of list length -- this is not like it defined in Frege, of course length [] = 0 length (_:xs) = 1 + length xs
This also happens with foldr f when f is strict in the second argument.
There are other possible causes (SO):
- tail recursion. This is handled efficiently in Frege because the tail recursive function is compiled into a while loop. Will never actually invoke SO, unlike other JVM languages.
- explicit indirect tail recursion: (for example,
a tail calls b , the tail calls c , ... which the tail calls a ). It also should never lead to SO in Frege. - the construction of spikelets that are so deeply embedded that SO occurs during evaluation. This is what happens in
foldl in Haskell. In Frege, the fold standard is strict in the battery and therefore is immune in many cases. However, the following long overflows: fold (<>) mempty (map (Just . Sum) [1..10000]) - Recursion length / foldr, as in our example.
- Recursion in non-tail calls:
Here is an example for the latter case:
even 0 = true even n = case even (pred n) of true -> false false -> true
The second equation is semantically equivalent to even n = not (even (pred n)) and, therefore, is an even more malicious variant 4.
To answer your question, in your example, you could use a drive to create a recursive version:
count n = go 0 n where go acc 0 = acc go acc n = go (succ acc) (pred n)
It may be worth noting that your example also does not work in Haskell:
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Prelude> let count 0 = 0; count n = succ (count (pred n)) Prelude> count 10000 10000 Prelude> count 100000 100000 Prelude> count 1000000 1000000 Prelude> count 10000000 10000000 Prelude> count 100000000 *** Exception: stack overflow
The reason it overflows with only a much larger number is because Haskell RTS manages RAM in a way that is better suited for functional programming, while the JVM allocates a tiny default stack at startup, which takes into account the call depth of only 1000.
You can compute much larger numbers with your program, even in Frege, when you force the JVM to allocate larger stacks:
java -Xss512m ....
Experience has shown that a 512-meter stack allows for a deeper call of approximately 10 million for single argument functions.
This, however, is not a general solution, because then the JVM creates all threads with this stack size. Thus, precious RAM is lost. And even if you have a lot of RAM, you probably cannot create a stack larger than 2g.
In the next major version of Frege, I hope some pathological cases 3 and 4 will be considered (see above). To date, however, such designs will only work for small problem sizes that fit the JVM stack.