Does Frege perform tail call optimization?

Question

Are tail calls optimised in Frege. I know that there is TCO neither in Java nor in languages which compile to JVM bytecode like Clojure and Scala. What about Frege?

Denaturalize

The title of your question is the first thing people see, and “TCO” is just another TLA. – Somatology

It should be mentioned that Scala has TCO, and that some JVMs (like IBM's) implement it as well. – Hysell

@Hysell is this a new feature in Scala? TCO hasn't been supported in Scala for long time! – Denaturalize

IIRC, Scala has (simple cases of) TCO from the very beginning. Try def foo {println("foo!"); foo} - if you call it, it won't stop with a StackOverflowException. – Hysell

Answer 1

Frege does Tail Recursion Optimization by simply generating while loops.

General tail calls are handled "by the way" through laziness. If the compiler sees a tail call to a suspectible function that is known to be (indirectly) recursive, a lazy result (a thunk) is returned. Thus, the real burden of calling that function lies with the caller. This way, stacks whose depth depends on the data are avoided.

That being said, already the static stack depth is by nature deeper in a functional language than in Java. Hence, some programs will need to be given a bigger stack (i.e. with -Xss1m).

There are pathological cases, where big thunks are build and when they are evaluated, a stack overflow will happen. A notorious example is the foldl function (same problem as in Haskell). Hence, the standard left fold in Frege is fold, which is tail recursive and strict in the accumulator and thus works in constant stack space (like Haskells foldl').

The following program should not stack overflow but print "false" after 2 or 3s:

module Test
    -- inline (odd) 
  where

even 0 = true
even 1 = false
even n = odd (pred n)

odd n = even (pred n)

main args =  println (even 123_456_789)

This works as follows: println must have a value to print, so tries to evaluate (even n). But all it gets is a thunk to (odd (pred n)). Hence it tries to evaluate this thunk, which gets another thunk to (even (pred (pred n))). even must evaluate (pred (pred n)) to see if the argument was 0 or 1, before returning another thunk (odd (pred (n-2)) where n-2 is already evaluated. This way, all the calling (at JVM level) is done from within println. At no time does even actually invoke odd, or vice versa.

If one uncomments the inline directive, one gets a tail recursive version of even, and the result is obtained ten times faster.

Needless to say, this clumsy algorithm is only for demonstration - normally one would check for even-ness with a bit operation.

Here is another version, that is pathological and will stack overflow:

even 0 = true
even 1 = false
even n = not . odd  $ n
odd    = even . pred

The problem is here that not is the tail call and it is strict in its argument (i.e., to negate something, you must first have that something). Hence, When even n is computed, then not must fully evaluate odd n which, in turn, must fully evaluate even (pred n) and thus it will take 2*n stack frames.

Unfortunately, this is not going to change, even if the JVM should have proper tail call one day. The reason is the recursion in the argument of a strict function.

Switchboard

Amazing answer, thanks a lot! BTW are there strictness annotations in Frege? – Denaturalize