trampoline

picoLisp does not support tail call optimisation. However, there is a way around it, using a trampoline:

   Used in some LISP implementations, a trampoline is a loop that
   iteratively invokes thunk-returning functions. A single trampoline
   is sufficient to express all control transfers of a program; a
   program so expressed is trampolined or in "trampolined style";
   converting a program to trampolined style is
   trampolining. Trampolined functions can be used to implement tail
   recursive function calls in stack-oriented languages.

First, lets see the final code and then discuss how to use and derive it:

(def 'continue list)

(de done (R)
   (cons NIL R) )

(de trampoline (F A)
   (use R
      (loop
         (NIL (car (setq R (apply F A))) (cdr R))
         (setq F (car R) A (cdr R)) ) ) )

There was a discussion on the topic suggesting that it is better to rewrite your recursive code using loops but there could be cases when recursion is a better abstraction.

Lets suppose we have the following, mutually recursive functions (the example was taken from here):

(de f1 (N)
   (println N)
   (if (= N 0)
      (println 'Blastoff!)
      (f2 N)))

(de f2 (N)
   (f1 (- N 1)))

(f1 90000) # => crash

If we call 'f1' with sufficiently big number, picoLisp interpreter runs out of stack eventually. This need not to be so. We can rewrite the code as follows:

(de f1 (N)
   (println N)
   (if (= N 0)
      (throw 'done 'Blastoff!)
      (list f2 N)))

(de f2 (N)
   (list f1 (- N 1)))

(de run-trampolined (F A)
   (catch 'done
      (loop
         (let R (apply F A)
            (setq F (car R) A (cdr R)) ) ) ) )

: (run-trampolined f1 '(9000))
9000
8999
...
1
0
-> Blastoff!

We could add some syntactic sugar:

(def 'continue list)

(de done (R)
   (throw 'trampoline R))

(de trampoline (F A)
   (catch 'trampoline
      (loop
         (let R (apply F A)
            (setq F (car R) A (cdr R)) ) ) ) )

(de f1 (N)
   (println N)
   (if (= N 0)
      (done 'Blastoff!)
      (continue f2 N)))

(de f2 (N)
   (continue f1 (- N 1)))

(run-trampolined f1 '(9000))

Now lets try usual factorial example:

(de fact (N)
   (if (< N 2)
      1
      (* N (fact (- N 1)))))

(fact 5) # => 120

We can rewrite 'fact' using tail call recursion:

(de fact/ (N R)
   (default R 1)
   (if (< N 2)
      R
      (fact/ (- N 1) (* N R))))

(fact/ 5)

and now we are ready for a trampoline:

(de fact/t (N R)
   (default R 1)
   (if (< N 2)
      (done R)
      (continue fact/t (- N 1) (* N R))))

(trampoline fact/t '(5))

Actually, we do not need throw/catch:

(def 'continue list)

(de done (R)
   (cons NIL R))

(de trampoline (F A)
   (use R
      (loop
         (NIL (car (setq R (apply F A))) (cdr R))
         (setq F (car R) A (cdr R)) ) ) )

What happens if we call 'fact/t' directly without 'trampoline'?

: (fact/t 5)
-> (((N R)
     (default R 1)
     (if (< N 2)
        (done R)
        (continue fact/t (- N 1) (* N R))))
    4 5)

In other words, we managed to split the original recursive call into a sequence of partial computations. The result above shows what function is to be called next (after the first iteration) and what arguments should be used.

As the Wikipedia article suggests, a single trampoline is sufficient to express all control transfers of a program. That gives us very powerful tool which could be useful in some cases, especially when used together with the power of lisp to make higher level syntactic abstractions.

TODO continuations

TODO cps

TODO light-weight processes

TODO asynchronous server