LESS is More

When a programer looks at a new language which is slightly different than general programming languages, first question that comes to his mind is if the language is turing complete. Similar thing happened to me when I looked at LESS. LESS is a CSS preprocessor and from a cursory look it looks like a macro sort of language which copy pastes definitions from one place to another. Actually, it is little more than that as it also tries to be a CSS like declarative language. That is, instead of defining variable you define properties and order defining those properties does not matter. Nevertheless, I have still not well understood the model of computation followed by this language, but it seems that even implementing a counter in this language is not very straightforward. I do not have anything to say to creators of LESS as it is not intended to be a general purpose language. Language does allow mathematical expression, variable definition, conditions (guards), methods. With these tools at hand I thought it would be easy to implement loops using recursion and calculate factorial and fibonacci sequence. My first attempt at creating a program that will find the factorial of a given number failed as it seems language does not allow updating a variable in a given scope once it is defined. At this point I knew that probably language does not well support writing such routines. I googled a lot to see if someone else has done something like this, but did not find anything. I was now looking for a language feature which could be exploited to carry out calculations and also preserve state. After trying many things I found that if you keep all the state in the form of parameters of a function (mixin), it is possible to get the effect of modifying a variable (state updation).  Below are some programs I wrote for calculating factorial and fibonacci numbers.

  
.fact_impl(@n,@res) when (@n > 1){
   .fact_impl(@n - 1, @res * (@n - 1));
}

.fact_impl(1,@res){
  @fact_res:@res;
}
.fact(@k){
  .fact_impl(@k,@k);
}

.fib_impl(@n,@first,@second) when (@n > 0){
  .fib_impl(@n - 1,@second,@first+@second);
}
.fib_impl(0,@first,@second){
  @fib_res:@first;
}
.fib(@k){
  .fib_impl(@k,0,1);
}

result{
  .fact(6);
  .fib(8);
  factorial_of_6:@fact_res;
  fibonacci_8:@fib_res;
}

LISP in Javascript

The main concept in LISP is that data is program and program is data. A wonderful way in which authors of SICP present the later is by creating data structure just by using functions. Lists in LISP and methods to operate on them can be created using just functions. We can do the same in Javascript as well, i.e. create List data-structure by just using functions and without objects or arrays. In fact we can create any data structure in this way. But an interesting question is where is data stored? (Its not too difficult to answer this question). Following is the JavaScript code which implements basic cons, car and cdr routines in Javascript.

  
function cons(x,y){
    var p=function(n){
        if(n==0)return x;
        if(n==1)return y;
        throw new Error("Index out of bound"+n);
    }
    p.toString=function(){
        return "("+x+","+y+")";
    }
    return p;
}
function car(z){
    return z(0);
}
function cdr(z){
    return z(1);
}

Now let us create some functions based on this list

  
/**
 * Syntactic sugar for constructing a list
 */
function list(){
   var args = [].slice.call(arguments);
   if(args.length == 0)
       return null;
   var first = args.shift();
   return cons(first,list.apply(this,args));
}
/**
 *  calculates length of the list
 */
function len(l){
    if(!l) return 0;
    return 1 + len(cdr(l))
}
/**
 * Calculate the factorials upto n
 * returns a list of factorials upto n
 */ 
function fact1(n,acc,a){
   if(n>1) return cons(acc,fact(n-1,acc*a,a+1));
   return acc;
}
function fact(n){
  return fact1(n,1,1);
}

These lists are created purely out of functions, we did not use any array or object type. This list can be extended to more complex data structures such as tree or graph.
Now let us create a little more complicated data structure, a binary search tree.

/**
 * Method to create a node in tree
 */
function create_node(val,left,right){
  return cons(val,cons(left,right));
}
/**
 * method to get left subtree
 */
function left(tree){
  return car(cdr(tree));
}
/**
 * method to get right subtree
 */
function right(tree){
  return cdr(cdr(tree));
}
/**
 * method to add a new number in binary search tree
 */
function add(num,tree){
    if(!tree){
      return create_node(num,null,null);
    }
    var val=car(tree);
    var l = left(tree);
    var r = right(tree);
    if(num > val) return create_node(val,l,add(num,r));
    if(num < val) return create_node(val,add(num,l),r);
    return tree;
}
/*
 * method to check if a number 
 * exists in the tree
 */
function num_exists(num,tree){
  if(tree){
     var l = left(tree);
     var r = right(tree);
     var val = car(tree);
     if(num == val){
       return true;
     }
     return num_exists(num,l) || num_exists(num,r);
  }
  return false;
}

/**
 * method to do in order traversal of tree
 * and output list of sorted nodes
 * @param tree current node to traverse in the tree
 * @parent list of root val and in order traversed 
 * list of right sibling subtree
 */
function traverse(tree,parent){
  if(!parent){
    parent = null;
  }
  if(tree){
     var l = left(tree);
     var r = right(tree);
     var val = car(tree);
     var traversedRight = traverse(r,parent);
     var trr = cons(val,traversedRight);
     return traverse(l,trr);
  }
  return parent;
}

/* sample run */
var tree = add(3);
tree=add(4,tree);
tree=add(9,tree);
tree=add(5,tree);
tree=add(1,tree);
tree=add(2,tree);
console.log(num_exists(5,tree)); // outputs: true
console.log(""+traverse(tree)); // outputs: (1,(2,(4,(5,(9,null)))))

As we can how complex data structures can be created without using any object or array