Nerdworks Blogorama - Nerdspeak

Writing a sensor driver for the Wiimote on Windows 7

2010-02-05T16:57:28Z

Ever since I saw Johnny Chung Lee's demos of the innovative ways in which the Nintendo Wiimote can be used as an input device for the PC, I've been hooked! The Wiimote is a surprisingly self-contained piece of hardware that is able to operate independently apart from the Wii console. Among other things, the Wiimote features a 3-axis accelerometer which is the primary enabler for letting you do things like wave a virtual tennis racquet or roll a bowling ball down the alley.

When Microsoft released Windows 7, one of the new things that they added to the system was a brand new platform for managing a certain class of hardware devices known as "sensors". Sensors are basically devices that, well, sense things! A GPS device for example is a sensor that can provide geographical location information. Another example is an ambient light sensor that lets the system know how bright the ambient light is. Now, these kinds of devices could be written and used even before Windows 7, just that now we have standard ways of exposing and consuming sensor data so that device vendors and application developers are able to communicate with each other in non-proprietary ways.

So, putting the two together, I figured it'd be kind of neat to come up with a sensor driver that exposed the accelerometer data from the Wiimote to the sensor platform. After some bit of head-scratching I managed to put something together. I've written up an article about it and posted it over at CodeProject.com. If you're interested, you can head over there and read all about it! Here's the link:

Writing a sensor driver for the Wiimote on Windows 7

Enabling JSONP calls on ASP.NET MVC

2010-03-09T08:50:36Z

JSONP is the technique of making cross-domain HTTP requests via JavaScript circumventing browser security restictions on requests that return data in the JSON format. By cross-domain, we refer to the practice of making HTTP requests on URLs that refer to resources residing on a domain other than the one from where the page being viewed/executed was loaded from. You'll find a good description of what JSONP is all about here. Briefly, the technique exploits a browser back-door where the SRC attribute on a SCRIPT tag is allowed to be a "foreign" URL and the browser will download the code and evaluate it. But then again, this is perhaps not so much a back-door as a feature that allows you to build mash-ups by composing code that draws on functionality hosted on different servers. If this were not allowed then something like the Content Delivery Networks (CDN) would just not work. In fact this blog that you're reading right now loads the jQuery JavaScript library via the Google CDN.

Here's an example of this in practice - I've loaded up the 5 most "interesting" photos uploaded on Flickr in the last day or so below:

And here's the code that accomplishes this with a little jQuery magic:

//
// Flickr REST url
//
var url = "http://api.flickr.com/services/rest/?";

//
// My Flickr API key
//
var api_key = "<<your flickr api key here>>";

//
// build a flicker url from a photo object
//
function buildPhotoUrl(photo) {
    return "http://farm" + photo.farm +
           ".static.flickr.com/" + photo.server + "/" +
           photo.id + "_" + photo.secret + "_t.jpg";
}

//
// get interesting photos
//
function getInterestingPhotos() {
    //
    // build the URL
    //
    var call = url + "method=flickr.interestingness.getList&api_key=" +
               api_key + "&per_page=5&page=1&format=json&jsoncallback=?";

    //
    // make the ajax call
    //
    $.getJSON(call, function(rsp) {
        if (rsp.stat != "ok") {
            //
            // something went wrong!
            //
            $("#interesting_photos").append(
                "<label style=\"color:red\">Whoops!  It didn't work!" +
                "  This is embarrassing!  Here's what Flickr had to " +
                " say about this - " + rsp.message + "</label>");
        }
        else {
            //
            // build the html
            //
            var html = "";
            $.each(rsp.photos.photo, function() {
                var photo = this;
                html += "<span><img src=\"" + buildPhotoUrl(photo) +
                        "\" title=\"" + photo.title + "\" alt=\"" + photo.title +
                        "\" /></span> ";
            });

            //
            // append this to the div
            //
            $("#interesting_photos").append(html);
        }
    });
}

//
// get the photos
//
$(getInterestingPhotos);

The basic idea is to dynamically add a SCRIPT tag to the DOM where the SRC attribute is pointing to the external URL where the data that we want resides. Upon encountering a new SCRIPT node, the browser immediately starts loading the code and evaluating it (and also freezes pretty much everything else in the browser while it is doing this!). If we can have the external resource render a call to a function that we define (or to a well-known function name) in the script that it produces then we can effectively have a callback routine invoked when the data is received from the foreign domain. The function to be called when the script dynamically loads is usually passed in as a query string parameter in the GET request or can be a function name that is mandated by the 3rd party site. Flickr for example defaults to rendering a call to a function called jsonFlickrApi but allows you to override this by passing a different name via the jsoncallback query string parameter.

jQuery has direct support for JSONP in that if you include a callback=? parameter in the AJAX URL for the getJSON call then it will replace the ? with a dynamically generated global JavaScript function name that it also defines. The word callback can be replaced with anything else as we did above by using jsoncallback. All the grunt work of dynamically adding SCRIPT tags to the DOM is done by jQuery.

Now, imagine that you designed your own little REST based service using ASP.NET MVC and have opted to provide JSON as one of the data output formats and wish to support JSONP requests. This basically means that you simply need to wrap your JSON output in a call to a user-supplied or a standard JavaScript function. So instead of rendering something like this out to the client:

{
    photos : [
        photo : {
            id : 232992,
            secret : "bAC980980c09c08a0ef"
        }
    ],
    page : 1,
    total : 500,
    photosPerPage : 10
}

You want to render something like this:

callback({
    photos : [
        photo : {
            id : 232992,
            secret : "bAC980980c09c08a0ef"
        }
    ],
    page : 1,
    total : 500,
    photosPerPage : 10
});

Where callback is the name of the JavaScript function defined by the client that needs to be invoked when the script is evaluated by the browser. If you wanted your ASP.NET MVC controllers to support this, how would you do it? The first approach I took was to simply define a custom ActionResult class that would produce the correct script. Here's what this looks like:

/// <summary>
/// Renders result as JSON and also wraps the JSON in a call
/// to the callback function specified in "JsonpResult.Callback".
/// </summary>
public class JsonpResult : JsonResult
{
    /// <summary>
    /// Gets or sets the javascript callback function that is
    /// to be invoked in the resulting script output.
    /// </summary>
    /// <value>The callback function name.</value>
    public string Callback { get; set; }

    /// <summary>
    /// Enables processing of the result of an action method by a
    /// custom type that inherits from <see cref="T:System.Web.Mvc.ActionResult"/>.
    /// </summary>
    /// <param name="context">The context within which the
    /// result is executed.</param>
    public override void ExecuteResult(ControllerContext context)
    {
        if (context == null)
            throw new ArgumentNullException("context");

        HttpResponseBase response = context.HttpContext.Response;
        if (!String.IsNullOrEmpty(ContentType))
            response.ContentType = ContentType;
        else
            response.ContentType = "application/json";

        if (ContentEncoding != null)
            response.ContentEncoding = ContentEncoding;

        if (Callback == null || Callback.Length == 0)
            Callback = context.HttpContext.Request.QueryString["callback"];

        if (Data != null)
        {
            // The JavaScriptSerializer type was marked as obsolete
            // prior to .NET Framework 3.5 SP1 
#pragma warning disable 0618
            JavaScriptSerializer serializer = new JavaScriptSerializer();
            string ser = serializer.Serialize(Data);
            response.Write(Callback + "(" + ser + ");");
#pragma warning restore 0618
        }
    }
}

Now you can simply return a JsonpResult (note the p before the "R" in "Result") from your action methods instead of JsonResult and everything should just work. Client's would indicate that this is a JSONP request by appending a query string parameter called callback to the request with the name of a JavaScript function that is to be called. I wasn't however, entirely happy with this situation as this would mean that I'd have to go and change the return type of all my action methods to return a JsonpResult instead of a JsonResult. And also update the code that instantiated JsonResult. I wanted a less disruptive solution if you will.

It is precisely for scenarios such as this that the ASP.NET MVC framework includes extension points in the form of action filters. Action filters are basically hooks that you can define to intercept and enhance request processing in various ways. ASP.NET MVC allows you to define filters that get called before and/or after the action method is invoked and also before and/or after the ExecuteResult method on the ActionResult is invoked. Action filters are defined as .NET custom attribute classes that inherit from ActionFilterAttribute. ActionFilterAttribute defines 4 virtual methods that you can override to hook into the request processing pipeline at the right juncture. The OnActionExecuted method for instance is invoked immediately after the action method has been invoked and gives you a chance to further process the returned result. This would perfectly suit our purpose here where we wish to conditionally supplant the JsonResult object being returned from the action method with a JsonpResult instead. Here's what I came up with:

public class JsonpFilterAttribute : ActionFilterAttribute
{
    public override void OnActionExecuted(ActionExecutedContext filterContext)
    {
        if(filterContext == null)
            throw new ArgumentNullException("filterContext");

        //
        // see if this request included a "callback" querystring parameter
        //
        string callback = filterContext.HttpContext.Request.QueryString["callback"];
        if (callback != null && callback.Length > 0)
        {
            //
            // ensure that the result is a "JsonResult"
            //
            JsonResult result = filterContext.Result as JsonResult;
            if (result == null)
            {
                throw new InvalidOperationException("JsonpFilterAttribute must be applied only " +
                    "on controllers and actions that return a JsonResult object.");
            }

            filterContext.Result = new JsonpResult
            {
                ContentEncoding = result.ContentEncoding,
                ContentType = result.ContentType,
                Data = result.Data,
                Callback = callback
            };
        }
    }
}

As is perhaps self-evident, we simply check if the query string included a parameter called callback and if it did, then we supplant the Result object in filterContext with a new JsonpResult instance. This approach allows us to enable JSONP processing on a controller or an action method by simply tagging on the JsonpFilter attribute. If I wanted all of my methods in the controller to support JSONP then, I can do this:

[JsonpFilter]
public class DoofusController : Controller
{
    //
    // all your action methods here
    //
}

Or if I wanted it to work with only a specific action method then I'd do this:

public class DoofusController : Controller
{
    [JsonpFilter]
    public JsonResult DoTheThing(string data, string moreData)
    {
        return new JsonResult
        {
            Data = FetchSomeData(data, moreData)
        };
    }
}

ASP.NET MVC is kind of cool eh?! :-P

The Conman

2010-06-15T09:10:01Z

The conman was seated at his usual vantage point, a place that afforded a clear view of the populace exiting the railway station. As he stubbed out his morning cigarette, he was sure he'd spotted his first quarry.

"Aren't you from Sivan Master's household?" the conman accosted him as he was crossing the subway under M--- Road across the Central railway station.

"Sivan who?"

"Err... Are you from Kerala?"

"Yes, Palakkad."

"Where in Palakkad?"

"It's a village, about 12 kms from the town."

"Ah! I am not mistaken then! Do you know postmaster Balan?"

"No"

"Well, I am his son. I knew I had seen you somewhere before! You're on your way back from home I gather?"

"Yes". The conman appeared to ponder this awhile.

"What is your ancestral name?"

"I am from the Mele Paadam house."

That seemed to clear the matter at once. With the widest grin he'd ever seen, the conman remarked, "Indeed! I know your family very well. You should ask your parents about Balan postmaster's son Vasu. You perhaps don't remember, but I have been to your house many times."

He just smiled pleasantly and continued making his way through the morning rush of work and school bound humanity.

"You won't believe the trip I had yesterday night!" Vasu persisted, "The train we were in was stopped by dacoits!" This halted the quarry in his tracks.

"Dacoits?!"

"Oh yes! Rumor has it that it was Veerappan! Haven't you read the papers?" he paused, "It perhaps hasn't made it to the press yet. But I am sure you'll read all about it in the evening edition! Suffice it to say that I am extremely lucky to be alive!"

He looked at Vasu with concern and remarked, "That's quite awful!"

"Yes! Yes! My wife wasn't quite so lucky though. She has been admitted to the general hospital which is where I am headed right now. Oh! I don't know what I'll do!" Vasu was visibly distraught. They were out of the subway by now.

"They took everything you see." Vasu continued, "We escaped only with the clothes on our back!"

"Tragic! Quite tragic!"

"Yes! Yes! Quite! And I am so new to this city. I am so glad I saw you - you're a God send!"

He faced Vasu and said abruptly, "Well, Vasu it was nice meeting you. Hope your wife recovers soon. Goodbye!"

"Yes, thank you! Goodbye then!" Vasu replied and turned away walking towards the hospital.

The quarry had waved an auto rickshaw and got into it before he heard the familiar voice call out to him again.

"I feel so embarrassed saying this to somebody I've just met, but it is a desperate situation you see. Like I said, they took everything; even the money in my wallet! May they be struck by lightning!" Vasu cursed, "I am completely broke right now. Would you be able to spare some money? I will personally return it to the Mele Paadam house once I get back. It will be a big help."

Seeing him hesitate, Vasu was quick to remark, "No, that's quite alright. I completely understand. Please forget that I ever asked. I apologize. Please give my regards to your parents." And made as if he would leave.

He stopped Vasu and said with feeling, "No Vasu, that's not it. It's just that... I don't have change you see. All I have is a Rs. 1000/- note. If you can spare Rs.100/- for this auto I'd happily hand it over to you. I am sure you need it more right now than I do."

There was an expression of genuine surprise on Vasu's face. He quickly recovered and said, "Thank you so much Sir! I was right, you truly are a God send! I do in fact happen to have this one Rs.100/- note. They forgot my secret pant pocket you see!"

They quickly exchanged the money and Vasu said as he handed his hundred rupee note, "I promise to return this money as soon as I get back home. I shall never forget this favor! Again, thank you Sir, may God shower His blessings upon you."

"Oh! That's quite alright. Please go attend to your wife now. Goodbye!"

As the rickshaw sped away from the station, he thought, "Now, if only the rest of the fake notes were as easily spent!"

PS: My colleague cum boss cum general pain in the wrong part of the anatomy (otherwise known as Aravind) is writing a series of really short stories over at his blog Moving Horizons and doing a pretty good job of it - so much so that the writing bug seems to have bit me too now! This little short here is my first shot at the genre (or any genre in writing any kind of ficitonal prose actually). Feel free to critique, slobber mindlessly at its sheer blinding genius etc.

Memoization - Optimize your function calls

2009-07-31T12:04:34Z

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:

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.
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.
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)))))))

Random Lisp thoughts

2009-07-26T10:03:12Z

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.

Learning Common Lisp

2009-07-26T10:15:37Z

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).

JavaScript closures act like implicit function state?

2009-07-12T15:36:27Z

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?!

Calling a JavaScript function with variable arguments

2009-07-04T15:21:37Z

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?!