Guarded Tail Call Optimisation

[Kesanov]

Summary

Guarded call is just a constructor in tail call position: Constructor a b c ... n
The interesting observation is that the the data type can be allocated before calling a b c ... like this:

result   = Constructor null null null ..
a' (k -> result.1 = k)
b' (k -> result.2 = k)
...
n' (k -> result.n = k)

where
n' args k = k (n args) = { result.n = n args } -- after inlining k

This allows us to choose the most expensive term (a | b | c ..) and make it a tail call.

As a consequence, guarded tree recursion allocates one stack frame less on each recursive call.
And more importantly linear recursion like map, take, filter, concat, Trie.insert becomes tail recursive:

map node fun Nil = 
    node.next = Nil
map node fun (Cons x xs) =
    node.next = Cons (fun x) null
    map node.next fun xs

Value

• faster and stackoverflow-safe recursion (when linear & guarded)
• users don't have to write mutable code, immutable code is easier to optimize

Specification

• Implement static recursion detection.
• Make sure constructors get inlined into higher order functions.
• Implement the above described transformation.

Acceptance Criteria & Test Cases

Every linear guarded recursion becomes tail call recursive. Even when implemented with higher order function. For example:

map f = foldr (a -> Cons (f a)) Nil