Javascript tips

I am reading Secrete of Javascript Ninja these days. This book introduced many js tips/patterns, and I wish to summarize what I find useful in this post.

Force the “new” operator

JS is not that object oriented. In JS, all functions is a constructor when it is called with a “new” operator, and “this” variable in the function is bounded to the newly constructed object automatically. This was considered a harmful pattern, because if I forgot to add “new”, then the function will not be considered a constructor, and “this” variable refers to global variable. However, this situation can be avoided by adding the “new” operator automatically if we forgot. Following code does this:

[sourcecode language=”javascript”]
function User(first, last){
if ( !(this instanceof arguments.callee) )
return new User(first, last);
….
}
[/sourcecode]

In this case, “User” cannot be used as a normal function.

Get function it self inside function execution

JS allows you to write code in functional programming style. In other functional programming languages like Scheme, it is not easy to do recursion using a lambda function, because you don’t know how to call the function it self: it got no name. In JS, you can always call current function through arguments.callee.

[sourcecode language=”javascript”]
var factorial=function(n){return n==0?1:n*arguments.callee(n-1);}
[/sourcecode]

Use setTimtout to help break time consuming script

If a script is running when page is loaded, then the page will only be displayed after the script finishes running. However, we can use setTimeout to break long script into small pieces. When the script is constructing page, page view update is not done immediately. Instead, it is pushed into a queue, and everything in the queue will be handled after script block finish running. setTimeout function will break the current script block, and let those tasks in the queue have a chance to be handled.
[sourcecode language=”javascript”]
bd=document.getElementsByTagName("body")[0];
tb=document.createElement("table");
bd.appendChild(tb);
for(var i=0;i<10000;i++){
var tr=document.createElement("tr");
var td=document.createElement("td")
td.appendChild(document.createTextNode(i));
tr.appendChild(td);
td=document.createElement("td")
td.appendChild(document.createTextNode(i*i));
tr.appendChild(td);
tb.appendChild(tr);
}
[/sourcecode]
[sourcecode language=”javascript”]
bd=document.getElementsByTagName("body")[0];
tb=document.createElement("table");
bd.appendChild(tb);
var j=10;
(function(){
for(var i=0;i<1000;i++){
var tr=document.createElement("tr");
var td=document.createElement("td")
td.appendChild(document.createTextNode(i));
tr.appendChild(td);
td=document.createElement("td")
td.appendChild(document.createTextNode(i*i));
tr.appendChild(td);
tb.appendChild(tr);
}
if(j–)setTimeout(arguments.callee,0);
})();
[/sourcecode]

Refer to group in regular expression

Like regular expressions in many other languages, JS use “\1” to refer to first matching group, “\2” for the second…However, this only works inside regular expression itself. One application is primality testing in my earlier post.

JS string also has “replace” method, which support regular expression replacement. To refer to matching group in the second argument of replace method, we need to use “$1”, “$2” instead of “\1”, “\2”.

[sourcecode language=”javascript”]
"hello world".replace(/(\w+)\s+(\w+)/,"$2 $1");
[/sourcecode]

Remove empty text node from HTML

When using DOM to get html node, text nodes containing white space only is very annoying. Following code removes white space text nodes using DFS.

[sourcecode language=”javascript”]
function cleanWhitespace( element ) {
// If no element is provided, do the whole HTML document
element = element || document;
// Use the first child as a starting point
var cur = element.firstChild;
// Go until there are no more child nodes
while ( cur != null ) {
// If the node is a text node, and it contains nothing but whitespace
if ( cur.nodeType == 3 && ! /\S/.test(cur.nodeValue) ) {
// Remove the text node
element.removeChild( cur );
// Otherwise, if it’s an element
} else if ( cur.nodeType == 1 ) {
// Recurse down through the document
cleanWhitespace( cur );
}
cur = cur.nextSibling; // Move through the child nodes
}
}
[/sourcecode]

Get element by class name

[sourcecode language=”javascript”]
function hasClass(name,type) {
var r = [];
var e = document.getElementsByTagName(type || "*");
for ( var j = 0; j < e.length; j++ )
if ( e[j].classList.contains(name) )
r.push( e[j] );
return r;
}
[/sourcecode]

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]

Recursion to Loop

Sometimes, we need to convert recursive functions into loop for efficiency consideration, or stack size constrain. Converting tail recursion into iteration is trivial. The method we discuss in this post is a general method to convert any recursive functions into iterative ones.

The idea is to simulate stack behavior: we store frame record as a structure into a simulated stack when calling a function, and restore the top record in stack when function returns.

The record should contain 2 part of data:

  • local variable, including parameter
  • next instruction to execute(used when restoring the record)

We also need a global variable to store return value (the same as eax register).

“Next instruction to execute” can be stored using label, and we can “goto” corresponding instruction after restoring record. However, “goto” statement is not supported in some languages, and also not recommended. Thus, we use integer number to represent label id, and use switch statement to jump to different part of code.

Following example shows recursive and iterative version of factorization function. Iterative version is significantly longer in code length, and slightly slower in practice. However, iterative version can work on large input where recursive version may get stack overflow.

We select javascript to demonstrate because:

  • Dynamic type saves declaration code
  • Closure can simulate behavior of frame record perfectly (stack elements are actually functions)
  • Powerful literal value representation

 

var fact=function(n){
  return n==0?1:n*fact(n-1);
};
var Fact=function(n){
  var _ret;
  var stk=[];
  var construct=function(n){
    var l=0;
    return function(){
      switch(l){
        case 0:
          l=1;
          if(n==0){
            _ret=1;
            stk.pop();
            return;
          }
          stk.push(construct(n-1));
          return;
        case 1:
          _ret*=n;
          stk.pop();
          return;
      }
    };
  };
  stk.push(construct(n));
  while(stk){
    if(stk.length==0)return _ret;
    stk[stk.length-1]();
  }
};

 

Now let’s look at more complicated examples:

fibonacci number
var Fib=function(n){
  var _ret;
  var stk=[];
  var construct=function(n){
    var l=0,a,b;
    return function(){
      switch(l){
        case 0:
          l=1;
          if(n<=1){
            _ret=n;
            stk.pop();
            return;
          }
          stk.push(construct(n-1));
          return;
        case 1:
          l=2;
          a=_ret;
          stk.push(construct(n-2));
          return;
        case 2:
          b=_ret;
          _ret=a+b;
          stk.pop();
          return;
      }
    };
  };
  stk.push(construct(n));
  while(true){
    if(stk.length==0)return _ret;
    stk[stk.length-1]();
  }
}

 

hanoi tower
var Hanoi=function(a,b,c,n){
  var stk=[];
  var construct=function(a,b,c,n){
    var l=0;
    return function(){
      switch(l){
        case 0:
          l=1;
          if(n>0){
            stk.push(construct(a,c,b,n-1));
            return;
          }
          stk.pop();
          return;
        case 1:
          l=2;
          document.write(a+"->"+c+"<br>");
          stk.push(construct(b,a,c,n-1));
          return;
        case 2:
          stk.pop();
          return;
      }
    };
  };
  stk.push(construct(a,b,c,n));
  while(stk){
    if(stk.length==0)return;
    stk[stk.length-1]();
  }
};
merge sort
var MergeSort=function(a,i,j){
  if(!i)i=0;
  if(!j)j=a.length;
  var stk=[];
  var construct=function(a,i,j){
    var l=0;
    var mid,t=[],x,y;
    return function(){
      switch(l){
        case 0:
          l++;
          if(j-i<=1){
            stk.pop();
            return;
          }
          mid=floor((i+j)/2);
          stk.push(construct(a,i,mid));
          return;
        case 1:
          l++;
          stk.push(construct(a,mid,j));
          return;
        case 2:
          x=i, y=mid;
          while(x<mid && y<j){
            if(a[x]<a[y]){
              t.push(a[x]);
              x++;
            }else{
              t.push(a[y]);
              y++;
            }
          }
          while(x<mid)t.push(a[x++]);
          while(y<j)t.push(a[y++]);
          for(var k=i;k<j;k++)
            a[k]=t[k-i];
          stk.pop();
          return;
      }
    };
  };
  stk.push(construct(a,i,j));
  while(stk){
    if(stk.length==0)return;
    stk[stk.length-1]();
  }
};