Edit 'trampoline' page

\{picoLisp} does not support tail call optimisation.  However, there is
a way around it, using a
\{http://en.wikipedia.org/wiki/Trampoline_(computers) trampoline}:

<pre>
   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.
</pre>

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

<lisp>
(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)) ) ) )
</lisp>

There was a
\{http://www.mail-archive.com/picolisp@software-lab.de/msg00136.html
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 \{http://bc.tech.coop/blog/040613.html here}):

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

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

(f1 90000) # => crash
</lisp>

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:

<lisp>
(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!
</lisp>

We could add some syntactic sugar:

<lisp>
(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))
</lisp>

Now lets try usual factorial example:

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

(fact 5) # => 120
</lisp>

We can rewrite 'fact' using tail call recursion:

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

(fact/ 5)
</lisp>

and now we are ready for a trampoline:

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

(trampoline fact/t '(5))
</lisp>

Actually, we do not need throw/catch:

<lisp>
(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)) ) ) )
</lisp>

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

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

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 \{http://en.wikipedia.org/wiki/Trampoline_(computers) 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

Summary of changes:

Captcha (enter the word 'pico' here):

Your name:

Check this box to fill in your name automatically next time (uses a cookie)

View page

This page is linked from: picoLisp

Revisions: 1 2 3 4 5 View source XHTML^V | RSS^V

picoWiki pages can be edited by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively