Thursday, July 15, 2010

Advanced recursion in newLISP

In my recent post about newLISP I mentioned that it does not support tail call optimization. In fact, many Lisps don't. As Bill Six pointed out even the ANSI standard of Common Lisp standard does not mandate (unlike Scheme) tail-call elimination provided by the language implementation, although it seems that all well-known ANSI Common Lisp compilers do it anyway.

I was wondering if there is a way to circumvent this problem and the first solution I found was to use memoize macro described in an excellent online documentation for newLISP, Code Patterns in newLISP:
(define-macro (memoize mem-func func)
  (set (sym mem-func mem-func)
    (letex (f func  c mem-func)
      (lambda ()
        (or (context c (string (args)))
        (context c (string (args)) (apply f (args))))))))
You can apply this macro to any function with any number of arguments. The trick here is that each time a function is called its result is cached in memory for another call. It can speed up your application tremendously, which can be observed by comparing the execution time of these example Fibonacci functions:
(define (fibo n)
  (if (< n 2) 1
    (+ (fibo (- n 1)) (fibo (- n 2)))))

(memoize fibo-m
  (lambda (n)
    (if (< n 2) 1
      (+ (fibo-m (- n 1)) (fibo-m (- n 2))))))

(time (fibo 35))
(time (fibo-m 35))
On my laptop (fibo 35) took 12,98 seconds to execute, while (fibo-m) executed in 0,016 miliseconds.

Unfortunately the memoize macro cannot help you to handle mutual recursion. A classic example of such recursion looks as follows:
(define (f1 n)
  (println n)
    (if (= n 0)
      (println "Blastoff!")
      (f2 n)))

(define (f2 n)
  (f1 (- n 1)))
You can easily make newLISP run out of stack by running (f1 1000), not to mention bigger numbers. What happens if we define a "memoized" version of f1 and f2? Let's see:
(memoize f1
  (lambda (n)
    (println n)
    (if (= n 0)
      (println "Blastoff!")
      (f2 n))))

(memoize f2
  (lambda (n)
    (f1 (- n 1))))
Again, running (f1 1000) immediately exhausts newLISP's stack.

A solution to this problem is using a technique called trampolining. Bill Clementson on his blog not only explained in an excellent way the concept of using trampolines, but also provided a Common Lisp implementation, which became my inspiration to write a newLISP version:
(define (trampoline fun arg)
  (catch
    (while true
      (let ((run (apply fun arg)))
        (setf fun (first run) arg (rest run)))) 'result)
  result)
A trampoline iteratively executes code thunks returned by a function, and this way avoids blowing out application stack. However, in order to use trampoline, the function must return continuation (a pointer to the next step) instead of value. Below is a version of beforementioned functions modified to use the trampoline:
(define (f1 n)
  (println n)
  (if (= n 0)
    (throw "Blastoff!")
    (list f2 n)))

(define (f2 n)
  (list f1 (- n 1)))
Now you can test it with:
(trampoline f1 '(1000))
(trampoline f1 '(10000))
(trampoline f1 '(100000))
...
Have fun!

4 comments:

Anonymous said...

Nice articles. Do these techniques have much place in typical practical web applications? Or are they of more academic interest, do you think?

--cormullion

Krzysztof Kliś said...

They have place in projects where developers are aware that such techniques exist, since trampolining is the best way to protect your application against stack overflows when using deep or mutual recursions. In Lisp (notably Scheme) it is rather rarely used, because tail-recursive functions are usually optimized by the compiler itself (with some exceptions). It is much more frequently used method if your application is written in a language which does not provide tail-call optimization. You can find a nice example of using trampoline in C in this article or read this discussion.
Unfortunately, many developers are still convinced that deep recursion leads to stack overflow and during my professional career I've seen lots of strange algorithms created just to avoid simple recursive solution. This is why I strongly believe in Eric Raymond's famous sentence: "Lisp is worth learning for the profound enlightenment experience you will have when you finally get it; that experience will make you a better programmer for the rest of your days, even if you never actually use Lisp itself a lot".

Anonymous said...

OK, thanks! So many coding examples are Fibonacci-examples that I sometimes find it hard to imagine how to use deep recursion when writing SQLite or CGI scripts... :)

-- cormullion

Krzysztof Kliś said...

You are right, but I think there are two main reasons for that:
1) It is easier to show the idea on a fairly easy and universal example. Showing a binary tree search used in an advanced search engine could be a real-life example, but it would require a huge article introducing all necessary context to a reader.
2) The company that built the software wouldn't be happy with presenting the idea (not to mentioning the parts of the source code) to the public and could treat it as giving away their trade secrets.