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.