Loop - Recur and Tail Call Optimization in LispyScript.

Javascript does not have tail call optimisation. Which means recursively calling a function in javascript will eventually blow the stack. Lets look at a simple javascript function that recursively calls itself n number of times.

var count = function(i) {
    if (i === 18000) {
        console.log(i)
    } else {
        count(++i)
    }
};

count(1);

On my machine the above code blows the stack before logging i to the console (round about 17000). The figure will vary depending on your setup.

In LispyScript tail call optimisation is implemented in its loop-recur construct. Here is the same example above in LispyScript recurring a million times without blowing the stack.


(console.log
  (loop (i) (1)
    (if (= i 1000000)
      i
      (recur ++i))))

The loop expression takes a set of arguments and binds them to a set of initial values, and evaluates the rest of the expressions. A recursion point is set by calling the recur expression with a new set of values, and control is returned to the top of the loop. You can break out of the loop anytime by returning a value that is not a javascript 'undefined'. 

Here is another LispyScript example to calculate a Fibonacci number.


(var fib
  (function (n)
    (loop (a b count) (1 0 n)
     (if (= count 0)
        b
        (recur (+ a b) a (- count 1))))))

(console.log (fib 10))

Tail call optimisation is implemented in LispScript using the method explained here.

And we are Live!

Lispyscript.com is now live with, overview, documentation, try it, usage example. Also released version 0.2.0 today.