evancz/Elm — pull request #456 by maxsnew (2014-01-18 19:47:13+00:00)
Title: Trampoline

A lot of discussion happened here: https://github.com/evancz/Elm/pull/436 , but I'll make the case for trampolines here.

Trampolines now
==============
Trampolining loops are the cheapest way to get some sort of tail call elimination in the language. This is the strategy used by Clojure: http://clojuredocs.org/clojure_core/1.2.0/clojure.core/trampoline (in addition to one special form for self-recursive functions which is much faster) though I think it's a terrible idea to have this be the only method for tail call elimination.

The important thing right now is that it's currently impossible to write long-running recursive functions in elm without stack overflow (due to bad js implementations, but we have to work around that).

Trampolines Once Tail-Call Elimination is Added to the Compiler
===================================================
Tail call elimination in the compiler will be eliminate to statically known mutually tail recursive functions. This will not help with more dynamic instances using higher order functions. For instance if we define mutually recursive functions across modules (contrived example, but minimal proof of concept):
```haskell
module A where
ev : (Int -> Bool) -> Int -> Bool
ev odd n = if n == 0 then True else odd (n - 1)
```
and
```haskell
module B where
import open A

even : Int -> Bool
even = ev odd

odd : Int -> Bool
odd = if n == 0 then False else even (n - 1)
```
then this would be impossible to tail-call eliminate without doing a lot of extra work at "linking" time.
The exmple above is contrived, but this will come up when doing things in a CPS style.

The good news about trampolining in the presence of tail call elimination is that the `trampolin` function I've implemented in this pr will be implementable in plain elm:
```haskell
data Trampoline a = Trampoline (Either a (() -> Trampoline a))
trampoline : Trampoline a -> a
trampoline (Trampoline e) = case e of
Left x -> x
Right t -> trampoline t
```
which will compile to something very similar to the native implementation in this pr. So this means that trampolining would not have to be in the standard library if the compiler implements even the most basic tail call elimination.

Roadmap
========
I think the best course of action would be this:
1. Add the version of trampolines implemented in this PR for now since it's currently impossible to implement long-running computations in elm.
2. Implement tail call elimination in the compiler and change the implementation of `trampoline` to one written in elm.
3. Remove the Trampoline library from the stdlib and into a separate package once packages can depend on each other.