Memoization is an optimization technique where the idea is to create functions that cache computed values for various input sets so that subsequent invocations can return the value from the cache instead of re-computing the results. It is a simple space for time trade-off where processing time is reduced at the expense of increased memory use. I figured I'd implement an automatic memoization mechanism in JavaScript that will work well under certain well defined constraints. Here's what I came up with:

function memoize( fn ) {
    //
    // check if this function has already been memoized
    //
    if( typeof( fn.__fn ) == "undefined" ) {
        //
        // the cache where the results are to be stored
        //
        fn.__cache = {};
        
        //
        // memoized version of the function
        //
        fn.__fn = function() {
            //
            // build the key that represents the given input set;
            // note that this thing works only so long as the operation
            // "toString" returns a meaningful result on all of the
            // parameters
            //
            var key = "";
            for( var i = 0 ; i < arguments.length ; ++i )
                key += arguments[i].toString() + "-";
            
            //
            // if the result for the current parameter set already exists
            // in the cache then return that; otherwise call the original
            // routine and store the result
            //
            if( typeof( fn.__cache[key] ) == "undefined" )
                fn.__cache[key] = fn.apply( null, arguments );
            return fn.__cache[key];
        }
    }
    
    return fn.__fn;
}

Imagine that you are tasked with the job of writing a Javascript function that returns the factorial given a number. If you wished to write a memoized version of the function here's what you'd do:

var fac = memoize( function( n ) {
    if( n <= 0 )
        return 1;
    return ( n * fac( n - 1 ) );
} );

If you invoked fac passing 5 for instance, and traced the control flow, here's the sequence of calls you'd see:

. __fn(5)
.. fac(5)
... __fn(4)
.... fac(4)
..... __fn(3)
...... fac(3)
....... __fn(2)
........ fac(2)
......... __fn(1)
.......... fac(1)
........... __fn(0)
............ fac(0)

The number of dots to the left of the function names indicates the stack depth and here it tends to increase because fac is a recursive function and keeps calling itself till the termination criteria is met. This seems like a drawback since where you'd have had a sequence of calls to just fac now we see it interspersed with calls to __fn also, effectively doubling the number of function calls that needs to be made. The benefit however, is realized when we observe what happens when fac is invoked again, a second time, passing 5.

. __fn(5)

As you can see, this time around, there was only a single function call. No further computation was needed as the required result was already available in the cache and only a simple look-up operation was performed. Observe what happens when we pass 3 next.

. __fn(3)

This was resolved via cache look-up also because the first call with 5 had recursively invoked fac with 3 as well. On a similar note, passing 7 produces the following call sequence:

. __fn(7)
.. fac(7)
... __fn(6)
.... fac(6)
..... __fn(5)

Automatic memoization ensures that the original routine is called only the bare minimum number of times - in this case, for the values 7 and 6. The implementation of memoize given above is useful only so long as the following are held true:

1. Each parameter passed to the actual function has a toString method that returns a meaningful value; if you passed a custom object for instance, you're going to have to define a toString method on it.
2. The CPU overhead of constructing a unique key for a given parameter set and doing hashtable lookups should be lower (preferably significantly) than simply performing the actual work.
3. For obvious reasons, the function should have at least 1 parameter!

If you've been following this blog, you know that I am trying to learn the Common Lisp programming language. I figured, I'll try and implement memoize in Common Lisp as well, to see if I'd learned enough of it to be able to do this. After looking up the Common Lisp Hyperspec a few times, I was in fact able to come up with an implementation that does essentially the same thing as what the JavaScript version above does. Here goes:

(defun make-key (lst)
  (format nil "~{~A-~}" lst))

(defun memoize (fn)
  (let ((cache (make-hash-table :test 'equal)))
    #'(lambda (&rest p)
	(let ((key (make-key p)))
	  (if (not (gethash key cache))
	    (setf (gethash key cache) (apply fn p)))
	  (gethash key cache)))))

(setf fac (memoize #'(lambda (n)
                        (if (<= n 0) 1
                            (* n (funcall fac (- n 1)))))))

I have covered about 4 chapters from the book Practical Common Lisp and what I have learnt so far is quite fascinating to say the least. Here're some random observations that I happened to make about Commmon Lisp. Please note that whenever I use the term Lisp below I refer to the Common Lisp dialect of the language.

• Contrary to what one might conclude upon encountering a typical Lisp program, the basic Lisp syntax is actually quite minimalistic. It is so minimalistic in fact that I can probably explain all of Lisp syntax in about one line (OK, not all of it, but maybe a significant chunk of it - the point is, the basic structure of Lisp code is fairly straightforward)! Here goes:

  Any Lisp code is a line of space delimited list of "things" and nested lists enclosed in parentheses.

  By "things", I mean pretty much everything that can go into Lisp code. Here's some lisp code:

  (believe it or not but this is some lisp code!)

  And here's another example with nested lists:

  (lisp code (with nested lists))

  If you tried entering this stuff at an interactive Lisp shell prompt however, you are bound to have been slapped with some errors and that's because even though this conforms to Lisp code structure it really doesn't mean anything. Its like trying to feed some random bit of XML to an XSL parser, or trying to pass an XSL file to the ANT program. In each of these cases, though we are passing well-formed XML they don't exactly have the tags that the respective programs are looking for.

  What we have accomplished with our definition above therefore is to specify what Lisp expressions are to look like. Imagine specifying the entire XML specification in one line (which of course is quite impossible because the actual spec runs to about 50 pages)! For a fully featured multi-paradigm programming language I think this is quite an incredible feat!

  The technical Lisp term for what we have defined above is an s-expression. Any piece of valid Lisp code is always a valid s-expression but as you might have discovered if you tried getting a Lisp interpreter to parse the examples given above, not all valid s-expressions are valid Lisp code. And that is where the typical Lisp noob (such as yours truly) spends time learning the language. But as is perhaps self evident, the terseness of the basic syntax for Lisp code goes a long way in accelerating the learning process and all the apparently confounding parentheses actually end up being a rather natural way of doing things.

• The basic Lisp form is so simple that I was able to whip up a little Lisp parser in JavaScript in about half an hour! Here's the complete parser:

  //
  // Each node in the parse tree can be a list or a symbol.
  //
  var NodeType = {
      List: 0,
      Symbol: 1
  };
  
  //
  // Each node is defined by its type and content which in
  // turn can be another node (list) or a symbol name.
  //
  function Node(type, content) {
      this.type = type;
      this.content = content;
  }
  
  //
  // Helper function that generates a "Node" object given
  // a symbol name.
  //
  function symbol(sym) {
      return new Node(NodeType.Symbol, sym);
  }
  
  //
  // Helper function that generates a "Node" object given
  // a list object.
  //
  function list(lst) {
      return new Node(NodeType.List, lst);
  }
  
  //
  // Helper function that trims a string for leading/trailing white space.
  //
  String.prototype.trim = function() {
      return this.replace(/^\s+|\s+$/g, "");
  }
  
  //
  // The Lisp lexer that can tokenize a string of Lisp code.
  //
  function Lexer(code) {
      this.code = code;
      var current = 0;
      var delims = "( )";
  
      this.nextToken = function() {
          var token = null;
          //
          // skip all white-space only tokens
          //
          while (((token = internalNextToken.apply(this)) != null) && (token.trim().length == 0));
          return token;
      }
  
      function internalNextToken() {
          //
          // if we have reached end of code then return null
          //
          if (current >= this.code.length)
              return null;
  
          //
          // accumulate characters into token till one of
          // the delimiters are encountered
          //
          var token = "";
          for (; current < this.code.length; ++(current)) {
              var ch = this.code.charAt(current);
              if (isDelim(ch)) {
                  if (token.length == 0) {
                      token += ch;
                      ++current;
                  }
  
                  break;
              }
  
              token += ch;
          }
  
          return token;
      }
  
      function isDelim(ch) {
          return (delims.indexOf(ch) != -1);
      }
  }
  
  //
  // The Lisp parser class that generates a parse tree composed of
  // "Node" object given a lexer object.
  //
  function Parser(lexer) {
      this.lexer = lexer;
  
      this.parseList = function() {
          var token;
          var lst = [];
          while (((token = this.lexer.nextToken()) != null) && (token != ")")) {
              switch (token) {
                  case "(":
                      lst.push(this.parseList());
                      break;
                  default:
                      lst.push(symbol(token));
                      break;
              }
          }
  
          return list(lst);
      };
  
      this.parse = function() {
          //
          // the first token MUST be a "("
          //
          if (this.lexer.nextToken() != "(")
              return null;
          return this.parseList();
      };
  }
  
  //
  // Parse some lisp code.
  //
  var code = "(sum (gen-multiples (gen-series 1000) 3 5))";
  var parser = new Parser(new Lexer(code));
  var root = parser.parse();

  This code simply generates an in-memory tree representation of the Lisp expression without performing any validation to check for correctness. This is akin to writing a non-validating DOM parser for XML - it simply hands you an object graph that you can programmatically traverse and do stuff with. I wrote a little HTML page to generate parse-tree visualizations given Lisp expressions of arbitrary complexity using the Google Visualization API and the Organizational Chart visualization in particular. Given the following Lisp expression for instance:

  (sum (gen-multiples (gen-series 1000) 3 5))

  Here's the tree representation:

  

  And for the following slightly more complex Lisp expression:

  (sqrt (1+ (* (- (/ 28 2) 10) 2)))

  Here's the tree representation:

  

  You can try building Lisp expression trees of your own at the following location:

  Build your own Lisp expression trees

• Lisp s-expressions (i.e. valid Lisp form s-expressions) are of 3 types:

  1. Function calls
  2. Macro invocations
  3. Special forms

  Function calls, are, well, function calls! In keeping with the minimalistic syntax philosophy, almost everything in Lisp is a function call (except of course, macros and special forms). Take for instance, arithmetic operators. In most languages, the compiler is able to natively recognize operators such as [+ - / *] and assign special meanings depending on the context where they are used and for that reason must, among other things, differentiate between unary, binary and ternary operators. In Lisp however, these are all function calls!

  The general form of a function call is like so:

  (function-name [arg1 arg2 ... argN])

  As is perhaps obvious, a function call is expressed simply as a list where the first element is considered to be the function name and everything else its arguments. As always, the arguments can be Lisp s-expressions themselves. If you wanted to add 2 numbers for instance, here's what you'd do:

  (+ 1 2)

  Here, + is the name of the function being invoked and 1 and 2 are its arguments. The function + can accept a variable number of arguments (like the C printf function), which means that in order to add 4 numbers for instance, you can simply do this:

  (+ 1 2 3 4)

  You can build compound lists by nesting s-expressions like so:

  (+ 1 2 (+ 3 4))

  Lisp will always evaluate the function arguments first from left to right (evaluating nested s-expressions if any) and only then invoke the function with the result of evaluating the argument forms. In the example above therefore, it will evaluate 1 and 2 first - which evaluate to themselves, i.e. 1 and 2 - followed by (+ 3 4) - which evaluates to 7. The resulting 3 numbers (1, 2 and 7) are then passed to + which evaluates the composite expression to the value 10.

There's a lot more that one can say about functions. I'll cover some of it in a subsequent post and also talk a bit about macros (which while a rather unique feature of Lisp is also at the same time quite powerful) and special forms.

As is frequently the case with such things (at least with me) I have decided, for no compelling reason whatsoever, that I will learn to program in the Common Lisp programming language. It might perhaps have something to do with the fact that I stumbled upon the following impassioned pleas for that language and the functional style of programming, all of which are in my opinion well worth your while should you choose to spend the next hour or so of your life reading them, even if you have no plans of learning Lisp:

Functional Programming For The Rest of Us

- an introduction to functional programming designed to appeal to us imperative grunt programmers.

The Nature of Lisp

- an admirable attempt at showing to the Lisp noob what its all really about.

Beating The Averages

- if you thought Lisp was only for "intellectual" academicians, then you've got to hear from this guy who made, like 50 million bucks by selling a piece of software to Yahoo - and guess what he wrote it in?

If Lisp is So Great

- tries to answer this question: if Lisp is so great, why don't more people use it?

This being my blog and everything, I plan to use it to post what I hope will be a series of entries chronicling my experiments with Common Lisp. There is frequent reference in popular Lisp literature to this so called moment of enlightenment that you apparently experience at some point as you work your way through the language. If this occurs with me, well, you'll know about it!

Here's what I am using to learn the thing:

• Practical Common Lisp by Peter Seibel - a great free book that teaches you ANSI Common Lisp
• CLISP - a free open source implementation of the ANSI Common Lisp language (running on Cygwin on Windows boxes - just remember to select the "clisp" package when you install Cygwin)

Here's what this dude called Eric Raymond had to say about Lisp:

Lisp is worth learning for the profound enlightenment experience you will have when you finally get it; that experience will make you a better programmer for the rest of your days...

I intend to personally find out if there's any truth to this or if Eric was just high when he wrote it (OK, so I do have a reason for learning Common Lisp - I never said I'll never contradict myself you know).

Consider this JavaScript code:

function acc( n ) {
    return function( i ) {
        return n += i;
    };
}

var fn = acc( 5 );
var n1 = fn( 1 );
var n2 = fn( 2 );

The question, of course, is what the values of n1 and n2 will be. It is perhaps evident that n1 must now equal to 6. But what about n2? Will it now contain 7 (i.e. 2 + 5) or will successive calls to fn result in the parameters being accumulated by addition with the value that was passed to acc (5)? We find by experimentation that the latter turns out to be true. n2 now equals 8, i.e., 5 + 1 + 2!

The conclusion to draw here therefore is that JavaScript function closures are essentially implicit function state. In the code snippet given above, if you treat fn as a regular object (which in fact it is), then the variable n which is part of the closure captured by the function object when it was returned from acc now acts like member state of fn. This is why multiple calls to fn causes the mutation to n to persist across those calls.

This is further corroborated by the fact that a subsequent call to acc to create another function object results in that instance getting a separate copy of the closure containing n. Here's an example:

function acc( n ) {
    return function( i ) {
        return n += i;
    };
}

var fn = acc( 5 );
var n1 = fn( 1 );
var n2 = fn( 2 );

var fn2 = acc( 10 );
var n3 = fn2( 1 );
var n4 = fn2( 2 );

Here, n3 and n4 hold 11 and 13 respectively. The function fn has no effect whatsoever on fn2 (or vice versa). This in fact, is the basis for creating the C++ equivalent of private member data in JavaScript. Imagine that you wish to create the equivalent of the .NET StringBuilder class and want to make the buffer where the string is actually stored a private member of the class. If you did this:

function StringBuilder() {
    this.buffer = [];
}

Then buffer is a public member and can be accessed via an instance. To make it private, simply declare buffer as a local variable inside StringBuilder. Like this:

function StringBuilder() {
    var buffer = [];
    
    this.getBuffer = function() {
        //
        // TODO:
        // return a copy so the original buffer is
        // left intact
        //
        return buffer;
    }
}

Now buffer is not visible to routines defined outside StringBuilder via an instance. But all methods defined inside StringBuilder can access buffer like any other member. You'd have to add accessor methods if you wished to provide access to private data. The same principle applies to member methods as well. Any local functions that you defined inside StringBuilder remain accessible only from other functions defined inside that class.

Cool eh?!

I am working on this little Windows Scripting Host script using JavaScript where I basically need to load up a Word document and do a bunch of text transformation tasks on each line and dump the output to the console (which I plan to redirect to a file). I decided to employ the builder pattern a bit and set something up like this first:

//
// transform events collection
//
var transformTable = {
    parseFileBegin : [],
    parseLineBegin : [],
    parseLineEnd : [],
    parseFileEnd : []
};

The idea is to populate the arrays parseFileBegin and parseFileEnd with a set of function object references that would get called in sequence at the appropriate time. To make calling these callbacks easier I decided to come up with a fireEvent routine which I could then use to fire a particular set of callback functions. I wanted also, to be able to call fireEvent passing as many arguments as are needed for that particular callback. When invoking parseFileBegin for instance, I wanted to pass the name of the file as a parameter to the callback routines and when calling parseLineBegin I wanted to pass in a tokenized form of each line along with the line string itself. Here're a couple of examples of how I wanted to call fireEvent.

fireEvent(transformTable.parseFileBegin, fileName);
fireEvent(transformTable.parseLineBegin, line, tokens);

And here's what I came up with for fireEvent:

function forEach( arr, cb ) {
    for( var i = 0 ; i < arr.length ; ++i )
        if( cb( arr[i] ) == false )
            return false;

    return true;
}

function fireEvent(eventHandlers) {
    //
    // everything after the first argument must be
    // considered as parameters to be passed to the
    // event handler routines
    //
    var args = [];
    var i = 0;
    forEach(arguments, function( arg ) {
        if( i++ == 0 )
            return;
        args.push( arg );
    });

    //
    // iterate through the handlers collection and call one by one
    //
    forEach(eventHandlers, function(handler) {
        // TODO: call the handler
    });
}

I needed to somehow call the function referenced by handler and pass all the values in the args array as parameters to it. One way might have been to dynamically build a string of JavaScript code that calls handler and then have it executed by calling eval on the string. But I perferred a more direct method if one were available. As it turned out, one was in fact available in the form of the apply method on Function objects. Consider this code:

var foo = function(s1, s2) {
    alert( s1 + " - " + s2 );
}

There are a couple of ways you can invoke foo. You can call it as you normally would with functions or, alternatively, you can call the member method apply that all function objects posses. Here's an example:

var foo = function(s1, s2) {
    alert( s1 + " - " + s2 );
}

foo("ding", 20);                 // call like normal function
foo.apply( null, ["ding", 20] ); // call via "apply" method

The apply method requires you to supply 2 parameters, the first one indicates the object in whose scope the function must be invoked - which means that the function will be invoked as though it were a member function of that object. The effect of this is that the variable "this" within that function will refer to the object you pass as the first argument. If you pass null then it will execute like a global function. Here's an example:

var person = {
    name : "binga",
    age : 20
};

var print = function() {
    alert( this.name + " - " + this.age );
}

print.apply( person );

From within the function print here, the reference to "this" turns out to refer the first parameter that you pass to apply. So what happens if you called print like this?

print.apply( null );

As things tend to be in such cases, "this" becomes "undefined" from inside print.

The second parameter to apply is of course, the array of parameters that are to be passed to the function. So with this new information, fireEvent looks like this:

function fireEvent(eventHandlers) {
    //
    // everything after the first argument must be
    // considered as parameters to be passed to the
    // event handler routines
    //
    var args = [];
    var i = 0;
    forEach(arguments, function( arg ) {
        if( i++ == 0 )
            return;
        args.push( arg );
    });

    //
    // iterate through the handlers collection and call one by one
    //
    forEach(eventHandlers, function(handler) {
        handler.apply(null, args);
    });
}

Simple enough, when you know how to do it eh?!