Link Me a Closure

An Exploration of Aggregate Closure-Structures in JavaScript

In recent years, closures have elicited substantial interest, due largely to the rise of languages such as JavaScript. They hold great potential for the sophisticated developer, and this potential extends to the creation of aggregate closure collections, such as linked lists. It is possible to implement these efficiently and elegantly in a similar fashion to their 'classical object' counterparts, and this article explores these intriguing possibilities, and their use in JavaScript applications.

Thumbnail image of the front cover of the May 2009 edition of Visual Systems Journal This article appeared in the May 2009 edition of Visual Systems Journal,

Closures in Brief

A closure - perhaps described better as a 'stack persistence' - arises from the way in which the processors of languages such as JavaScript perform their book-keeping when one function invokes another. On a call to a function, the run-time system creates an 'activation' object that holds the arguments passed into that function, along with the objects that it creates locally, including any inner functions. A call from there to another function links that activation to a new one; and when that function returns, the garbage collector reclaims that second activation.

However, the garbage collector will reclaim storage only where no (non-circular) references to it remain. Given this, and should a function return a reference to an inner function, retention of that reference prevents reclamation of the outer function's activation. It follows that the local objects created by the outer function originally will still be available to the inner function should the application invoke it subsequently (by application of the parentheses operator to the reference).

This is the basis of closures - they allow invocation of the same function in the context of different, unique sets of private objects, including references to other closures, and Example 1 demonstrates this essential principle.


 // Example 1

 function createClosure (Value)
    {
    return function ()
       {
       alert (Value);
       };

    }

 var Closure_0 = createClosure ("Fred");
 var Closure_1 = createClosure ("Barney");

 Closure_0 ();  // Parentheses are a 'call this' operator
 Closure_1 ();

 ----------------------------------

 Output:

 Fred
 Barney
             

Closure Interfaces

We can develop this concept further by returning not a single function-reference, but an object containing a number of them. Once again, the garbage collector holds its fire, thus allowing the object to serve as an interface to the underlying closure, with the function references acting as methods.

This principle permits the generation of closures that have complex functionality, and Example 2 illustrates the essential logic.


 // Example 2

 function createClosureInterface (Value)
    {
    return {

       getValue : function ()         { return Value; },
       setValue : function (NewValue) { Value = NewValue; }

       };

    }

 var Interface = createClosureInterface ("Fred");

 alert (Interface.getValue ());

 Interface.setValue ("Barney");

 alert (Interface.getValue ());

 ----------------------------------

 Output:

 Fred
 Barney
            

Closure Linkage

Given these points, and given that one closure can contain a reference to another, constructing chains of such objects - linked lists - follows naturally.

In Example 3, the createElement function accepts an argument representing the application-object that it should add to the collection, and takes a second argument denoting that object's prospective sibling. When called, the function instantiates a new Element object, and instructs the sibling-to-be to point itself at that. It then returns the new Element, on which the caller can invoke createElement again in order to append a third element.


 // Example 3

 function createElement (Value, Prev)
    {
    var Next    = Prev.getNext ();
    var Element =
       {
       setNext  : function (NewNext) { Next = NewNext; },
       getNext  : function ()        { return Next; },

       getValue : function ()        { return Value; }

       };

    Prev.setNext (Element);

    return Element;

    }
            

A Professional Implementation

We can elaborate and refine this; double rather than single element-linkage is within reach if we pass a 'Next' as well as a 'Prev' argument, and add some logic. Similarly, we can add a 'remove' method that operates by re-assigning the relevant references. These embellishments aside, however, Example 3 presents a chicken and egg problem, in that an initial call requires the prior existence of an element, otherwise the Prev.getNext and Prev.setNext statements will fail.

We can address this by creating two sentinel elements - a 'head' and 'tail' - that cap the ends of a given list, and which are linked to each other initially. We can then pass these to createElement as its Prev and Next arguments respectively when adding the first 'proper' element to a list. These sentinels are an instance of the Null Object design pattern, and while they bootstrap the creation of a list, they also simplify the addition and removal logic greatly, thus improving comprehension, provability and performance.

Nevertheless, createElement is still deficient because an element's setNext and setPrev methods are available publicly. This would allow inept, lazy or malicious third-parties to corrupt a list structure by manipulating its links explicitly - an approach that a cross-site scripting attack might adopt.

Happily, the use of closures can resolve this too, as Example 4 demonstrates generically. In this listing, createList subsumes two literal definitions of the sentinels described above, along with a definition for createElement, thus hiding these from clients. Critically, createElement defines an Element object, as before, but returns only a reference to the Interface object subsumed within that.


 // Example 4

 function createList ()                                            // Define a list-creator function
    {
    var Head  =                                                    // Define the Head sentinel-object...
       {
       Next      : null,
       Interface : null,
       setNext   : function (NewNext) { Head.Next = NewNext; }
       };

    var Tail  =                                                    // ...And the Tail
       {
       Prev      : Head,                                           // Link the Tail to the Head...
       Interface : null,
       setPrev   : function (NewPrev) { Tail.Prev = NewPrev; }
       };

    Head.Next = Tail;                                              // ...And the Head to the Tail

    // ---------------------------------------------------------------

    function createElement (Val, Prev, Next)                       // Define an element-closure creator...
       {
       var Elem =                                                  // ...that defines an Element object when called
          {
          setPrev   : function (NewPrev) { Prev = NewPrev; },
          setNext   : function (NewNext) { Next = NewNext; },

          Interface :                                              // Subsume the interface within its element
             {
             insertBefore : function (Val)    { return createElement (Val, Prev, Elem); },
             insertAfter  : function (Val)    { return createElement (Val, Elem, Next); },

             setVal       : function (NewVal) { Val = NewVal; },
             getVal       : function ()       { return Val; },

             getPrev      : function ()       { return Prev.Interface; },
             getNext      : function ()       { return Next.Interface; },

             remove       : function ()
                {
                Prev.setNext (Next);
                Next.setPrev (Prev);
                }

             }

          };

       Prev.setNext (Elem);                                        // Link the prev to Elem...
       Next.setPrev (Elem);                                        // ...and link the next to the same object

       return Elem.Interface;                                      // Return the interface, not the element itself

       }

    // ---------------------------------------------------------------

    return {                                                       // Return an interface for the List closure-object

       getHead : function ()    { return Head.Next.Interface; },
       getTail : function ()    { return Tail.Prev.Interface; },

       prepend : function (Val) { return createElement (Val, Head,      Head.Next); },
       append  : function (Val) { return createElement (Val, Tail.Prev, Tail); }

       };

    }
            

The (quasi UML) diagram shows the steps required to use this code. When called at time T0, createList returns a list interface, thus creating a closure that constitutes a List object. That interface allows addition of elements at the structure's head and tail, and permits retrieval of the first and last elements (should they exist).

Given this, and as shown at T1, the application should add an initial element by calling prepend or append, both of which return the Interface member of the element they insert.

That interface has access to the element and all other local objects that existed during its creation, and this allows the application to walk the list by calling a given interface's getNext or getPrev methods. Similarly, and as shown at T2, the insertBefore and insertAfter methods allow addition of a new element at a specific place because they call createElement reflexively, passing a reference to their Element object.

Example 4 therefore yields a highly efficient and extensible approach to the creation of linked lists of closures, yet clients can never act improperly because the actual Prev/Next references and the setPrev/setNext methods remain private throughout.

Just a Curiosity?

These points aside, however, JavaScript allows the construction of arrays of references to objects and functions, and, as shown, closures are manipulated either through a reference to a function, or through objects that contain such references.

Given this, it is possible to implement closure collections using arrays, as Example 5 illustrates, and this would suggest in turn that linked-lists of closures are no more than a curiosity.


 // Example 5

 function generateClosure (Str)
    {
    return function () { alert (Str); }
    }

 var ClosureArray = [generateClosure ("Fred"),
                     generateClosure ("Barney"),
                     generateClosure ("Wilma")];

 ClosureArray[1] ();  // Should give 'Barney', and does

 ----------------------------------

 Output:

 Barney
            

However, while function and object references have unique identities, it is impossible to use those identities as array subscript-values. Example 6 shows that Closure_A is clearly distinct from Closure_B, as one would expect, yet it also shows that these references do not serve as array indices.

This is significant in at least one JavaScript product, namely the AspectJS Method-Call Interception library[1]. AspectJS - technically, the 'AJS' object - exploits JavaScript's scope for the interception of calls to a given method, such that one or more other functions (affixes) execute before and/or after that method. The technique is trivial to implement in the very simplest case but, beyond that, control over affix lifetime etc requires the use of closures. Moreover, a given method may acquire multiple affixes (by accident or design), and this requires closure collections that permit arbitrary manipulation using references to their individual members - arrays of closures fail us here.

Given this, and when applying an initial affix to a given method, the AJS object constructs a pair of doubly-linked lists of closures for that method - one for the prefixes, one for the suffixes - and uses a variant on the interface technique explored above, to preclude corruption of the underlying structures by errant code.

Moreover, coercion into using closure-lists turns out to be gratifyingly positive - the absence of arrays obviates the management logic they require, and this precludes the defects that may arise in such machinery. This yields a small, elegant and robust component that passes a unit-test regimen of over 52,000 checks completely.


 // Example 6

 function generateClosure (Value)
    {
    return function () { return Value; }
    }

 var Closure_A = generateClosure (0); // Note: the values supplied here
 var Closure_B = generateClosure (1); // are immaterial, and serve only
 var Closure_C = generateClosure (2); // to generate unique closures.

 var StrArray  = [];

 StrArray[Closure_A] = "Fred";
 StrArray[Closure_B] = "Barney";
 StrArray[Closure_C] = "Wilma";

 alert (Closure_A === Closure_B);     // Should give false, and does
 alert (StrArray[Closure_B]);         // Should give 'Barney', but doesn't

 ----------------------------------

 Output:

 false
 Wilma
            

Closure Lego

The ability to link closures opens the door to a wealth of aggregate closure-structures, such as (double-ended) queues and stacks, and Example 7 gives a generic implementation for the latter.

We can extend matters further to create closure trees (lists of lists), and from there, binary-search trees of closures, and so on. The latter would give fast selection of a given closure-object according to a given criterion, and while the roles that might play in a web application are uncertain, the ability to treat closures like Lego is sure to play a significant role in the ambitious JavaScript applications of the future.


 // Example 7

 // createList defined as in Example 4

 function createStack ()
    {
    var List = createList ();

    return {

       push : function (Val) { List.prepend (Val); },
       pop  : function ()
          {
          var Element = List.getHead ();

          if (!Element) {return null; }

          Element.remove ();

          return Element.getVal ();

          }

       };

    }
            

References

[1] AspectJS - http://www.aspectjs.com/

Further Reading

End Note

Unfortunately, Visual Systems Journal re-drafted the diagram that appears in this piece, yet failed to send a proof for review prior to publication. Given this, the print version of the diagram contained a number of errata that are absent from the (correct) version presented here.

Copyright © Richard Vaughan 2009