Expressive Javascript

When I was learning Scheme, I was told that Scheme is a expressive language, because it can implement higher order function, closure, and even OOP.

Now I am learning javascript, and I find that JS is can be even more expressive than scheme. First, you can write C-style code in JS, which is difficult, or impossible in scheme. Moreover, JS has scheme’s functional programming behavior, and it can also implement higher order function, closure, and even OOP.

Let’s implement a Scheme’s classic example: print all permutation of a set of numbers

[sourcecode language=”javascript”]
cons=function(a,b){return {fst:a,rst:b};};
car=function(p){return p.fst;};
cdr=function(p){return p.rst;};
range=function(n){
var res=null;
for(i=n;i>0;i–){
res=cons(i,res);
}
return res;
};
list=function(){
var arg=[].slice.call(arguments);
if(arg.length==0)return null;
return cons(arg[0],list.apply(undefined,arg.slice(1)));
};
print=function(l){
var cur=l;
document.write("(");
while(cur){
var v=car(cur);
cur=cdr(cur);
if(typeof v == "number")
document.write(v+(cur?", ":""));
else
print(v);
}
document.write(")<br>");
};
map=function(f,l){
return l==null?null:cons(f(car(l)),map(f,cdr(l)));
}
filter=function(f,l){
if(l==null)return null;
if(f(car(l)))return cons(car(l),filter(f,cdr(l)));
return filter(f,cdr(l));
}
append=function(l1,l2){
if(l1==null)return l2;
return cons(car(l1),append(cdr(l1),l2));
}
flat=function(l){
if(l==null)return null;
if(typeof car(l) == ‘number’)return cons(car(l),flat(cdr(l)));
return append(car(l),flat(cdr(l)));
}
length=function(l){
return l==null?0:1+length(cdr(l));
};
perm=function(l){
if(length(l)==1)return list(l);
return flat(map(function(x){ return map(function(rst){return cons(x,rst);},perm(filter( function(t){ return t!=x; },l))) },l));
};
print(perm(list(1,2,3,4)));
[/sourcecode]

We start from simulating Pair and List in scheme, then implement operations on list, and finally implement “perm” operation. All implementations are following the way they implemented in scheme style (use recursions instead of loops).

An impressive example of scheme is it’s higher order function, which takes functions as arguments, or return functions. Higher order function is a more general function, and an good example is memoization.

Memoization is one implementation of Dynamic Programming: it keeps DP formula’s recursive style in code, which is easy to understand, while avoid repeated calculations by memorize all result for each states.

All memoizations have similar format:

if state in memo: 
   return memo[state]
if state is base case: 
   get result for state
else:
   calculate result using recursive formula
add result into memo
return result

Although all memoization code looks similar, we need to rewrite all code from scratch every time in languages like C. However, if we can use higher order function, memoization can be generalized into a template, where we only need to pass recursive formula and base case into it, and the higher order function handle the rest automatically.

[sourcecode language=”javascript”]
var memo=function(base,dp){
var f=[];
return function(){
var arg=[].slice.apply(arguments),res;
if(f[arg]!=undefined)return f[arg];
res=base.apply(undefined,arg);
if(res!=undefined)return f[arg]=res;
return f[arg]=dp.apply(0,arg);
};
};
[/sourcecode]

The higher order memoization can be implemented in lines of code in js. base argument is a function that returns answer inly on base case parameters, while return undefined otherwise. dp is function that implement dp formula using recursive calls.

Some interesting examples:
[sourcecode language=”javascript”]
var fact=memo(function(n){if(n==0)return 1;},function(n){return fact(n-1)*n;});
var fib =memo(function(n){if(n<=1)return n;},function(n){return fib(n-1)+fib(n-2);});
var comb=memo(
function(n,m){
if(n<0 || m<0 || m>n)
return 0;
if(n==m || m==0)
return 1;
},
function(n,m){
return comb(n-1,m-1)+comb(n-1,m);
});
[/sourcecode]

DP functions can also call each other:

[sourcecode language=”javascript”]
var even=memo(function(n){if(n==0)return true;},function(n){return odd(n-1);})
var odd=memo(function(n){if(n==0)return false;},function(n){return even(n-1);})
[/sourcecode]

Javascript is also able to do “currying”. Currying is how Haskell handle functions: “+” is a function takes 2 arguments, return the sum; “1+” is a function takes 1 arguments x, return x+1. That is to say, if you pass function with partial arguments in Haskell, you will get a function taking the rest arguments, and return the result with complete arguments.

[sourcecode language=”javascript”]
Function.prototype.curry=function(){
var args=[].slice.apply(arguments),f=this;
return function(){
return f.apply(this,args.concat([].slice.apply(arguments)));
};
};
add=function(a,b){return a+b;}
addOne=add.curry(1)
[/sourcecode]

Leave a Reply

Your email address will not be published. Required fields are marked *