JavaScript = C + Lisp

Since the higher layers of Mozilla are implemented using JavaScript. I’ve been eating, sleeping, and drinking it. (My copy of the Rhino book has a dozen bookmarks in it.) The more I write, the more it feels like Lisp.

Consider, for example, these lines of code:

semanticAccepter = acceptOnlyIf(
    acceptNot(emptyTextAccepter),
    scriptFilter,
    acceptAny(
        textAccepter,
        linkAccepter,
        formRelatedElementAccepter,
        linkImageAccepter));

usefulContentOfThePage = new SemTree(semanticAccepter);

Here SemTree is a object that allows you to pick out the interesting nodes of a HTML DOM tree from the uninteresting ones. (It’s basically a wrapper for the utilitous TreeWalker class.) To create a SemTree, you provide an accepter. An accepter is just a function that says whether or not a given node should be accepted:

function emptyTextAccepter(n) {
    return (n instanceof Text) && n.data.match(/^\s*$/);
}

With a few primitive accepters and filters in hand, its easy to define filter combinators—functions that combine several filters in a specific way:

function acceptAny() {
    var disjuncts = arguments;
    return function(n) {
        for (var i = 0; i < disjuncts.length; ++i) {
            var shouldAccept = disjuncts[i](n);
            if (shouldAccept) return shouldAccept;
        }
        return false;
    }
}

When called with accepters as arguments, acceptAny returns a new accepter that accepts a given node n just in case any of the disjuncts accept n. So, the occurrence of acceptAny in the semanticAccepter accepts text, links, forms, and images inside links. Conversely, acceptOnlyIf accepts a node only if it is accepted by all of the component accepters. The definition of acceptOnlyIf is similar to acceptAny:

function acceptOnlyIf() {
    var conjuncts = arguments;
    return function(n) {
        for (var i = 0; i < conjuncts.length; ++i) {
            var shouldAccept = conjuncts[i](n);
            if (shouldAccept != true) return shouldAccept;
        }
        return true;
    }
}

Both acceptOnlyIf and acceptAny are so similar I wonder if there’s a generic way to turn any boolean combiner (like negation, short-circuit conjunction, or short-circuit disjunction) into a filter combiner (like acceptNot, acceptOnlyIf, acceptAny). There is, but JavaScript isn’t up to the task. For this, we need the big guns.

The Ability to Define a Function is Insignificant next to the Power of the Monad

By providing first class functions, JavaScript takes its first step into a larger world. The deepest inroad into this world is embodied in Haskell and its varients. Since accepters tell us whether or not to accept a given node, they are functions from nodes to boolean values. In Haskell, we write:

type Accepter = Node -> Bool

To say that negation takes one boolean to another and that both conjunction and disjunction take lists of booleans to a single boolean, we write:

not ::  Bool  -> Bool
and :: [Bool] -> Bool
or  :: [Bool] -> Bool

Accepter combiners have similar types:

acceptNot    ::  Accepter  -> Accepter
acceptOnlyIf :: [Accepter] -> Accepter
acceptAny    :: [Accepter] -> Accepter

Our definition of semanticAccepter is similar to the JavaScript version:

semanticAccepter = acceptOnlyIf [
    acceptNot emptyTextAccepter,
    scriptFilter,
    acceptAny [
        textAccepter,
        linkAccepter,
        formRelatedElementAccepter,
        linkImageAccepter]];

How do we define a combiner like acceptOnlyIf? Haskell doesn’t have imperative contructs like some languages. Instead, you use recursion:

acceptOnlyIf []     n = true
acceptOnlyIf (a:as) n | a n        = true
                      | otherwise  = acceptOnlyIf as n 

For some reason, short variable names are standard in Haskell. The n is a node, a is an accepter, and as is a list of accepters. (Using an ending ’s’ is the standard way to say that something is a list.) The definition you see above is correct, but it isn’t the way I’d usually it. Instead, I’d use a nice little function called map:

map :: (a -> b) -> ([a] -> [b])
map f []     = []
map f (x:xs) = f x : map xs

When passed a function and a list, map returns the list made from applying the function to each element of the list. With map in hand, acceptOnlyIf is defined as:

acceptOnlyIf as n = and (map (\a -> a n) as)

Here the syntax (\a -> a n) means basically the same thing as the JavaScript:

function(a) {
    return a(n);
}

The whole acceptOnlyIf definition says, in essence: “Given a node n, find the value of each accepter at n, and return the conjunction of those values.” With such an elegant way of defining functions, the similarities between them are immediately apparent:

acceptOnlyIf as n = and (map (\a -> a n) as)
acceptAny    as n = or  (map (\a -> a n) as)

So much so that generalizing is trivial:

liftCombiner :: ([Bool] -> Bool) -> ([Accepter] -> Accepter)
liftCombiner c as n = c (map (\a -> a n) as)

acceptOnlyIf = liftCombiner and
acceptAny    = liftCombiner or

Can we take things a step further? Can we lift not to acceptNot as well? The main difference between and and not is that and works on a list of booleans but not uses on just one. To generalize liftCombiner further, we need to:

1. Find a structure that characterizes both simple values and lists.
2. Apply the structure to the problem of lifting combiners.

Haskell has just what we need. It’s called a Monad.

What is the Monad?

The question has been asked before. Monads are everywhere. Most structures and processes allow for a monadic interpretation: datatypes, functions, objects, state-fulness, exceptions, io, side-effects, concurrency, transactions, parsers, and programming languages. Pairs, tuples, lists, trees, graphs—all of these data structures have a monad interpretation, often more than one. Since so many things are monads, it’s hard to discribe them. I could, like most do, give you the mathematical definition up front. But like saying, “A continuation is the rest of the computation,” providing the definition of a monad is only useful if you already grok it. Providing the definition up-front, only obscures the view. (Not that anything else is clearer.) But I will delay presenting it. Instead, let’s meditate on the humble list as our means of attaining monadic enlightenment.

There are many ways of examining structures. One way is to look at how parts work together to form the whole. When lists are analyzed in this way, we discover their linked interpretation: a list is either empty or it is a cons consisting of a head and a tail. The head is an element of the list, and the tail is the rest of the list.

data LinkedList a = Nil | Cons a (List a)

To define the list [1, 2, 3], we write:

oneTwoThree = Cons 1 (Cons 2 (Cons 3 (Cons Nil)))

Lists in Haskell work just this way. Except they use [] for Nil amd infix colon : for Cons. Commas can be used to separate items, but it’s just shorthand for:

oneTwoThree = 1 : (2 : (3 : []))

The linked list has a long and prestigious history. Unfortunately, material decomposition will not reveal the monad.

Another way to analyze a list is by how it relates to and interacts with other things. Haskell provides “class” mechanism for defining objects in terms of the methods associated with them. Similar to abstract data-types and interfaces:

class List ls where
    nil  :: ls a
    cons :: a -> ls a -> ls a
    head :: ls a -> a
    tail :: ls a -> ls a
    map  :: (a -> b) -> (ls a -> ls b)

This is a perfectly good list class, but it hardly abstracts anything from the material decomposition. All of those methods, except map, are specific to the logical structure of lists, map captures a more abstract notion. It takes a function as an argument, and returns a new version of the function applicable to lists. Recall how helpful map was for defining acceptAny and acceptOnlyIf? It’s definitely a function worth looking into.

What other functions are vital to lists as a data structure independant of it’s particular implementation or shape? Well, there should be a way unit to box up a single element into a list, and we need a way join to combine a list of lists into one long list. The class definition looks like:

class List ls where
    unit :: a -> ls a
    map  :: (a -> b) -> (ls a -> ls b)
    join :: ls (ls a) -> ls a

And here’s the linked list implementation:

instance List [] where
    unit a = [a]

    map  f []     = []
    map  f (a:as) = f a : map f as

    
    join []       = []
    join [ls:lss] = ls ++ join lss

These methods are pretty straight forward: unit just puts the argument in to a list, map applies a function to each element in a list, and join concatenates a list of lists. For completeness, let’s pin down the definition of the concatenation operator (++) and see some quick examples:

(++) []     ls = ls
(++) (k:ks) ls = k : (ks ++ ls)

[1, 2, 3] ++ [4, 5, 6]        --> [1, 2, 3, 4, 5, 6]
unit 5                        --> [5]
map (\x -> x + x) [1, 2, 3]   --> [2, 4, 6]
join [[1], [2, 3], [4, 5, 6]] --> [1, 2, 3, 4, 5, 6]

Each of these functions is simple and useful. They’re standard ingredients but, like gun powder, if you combine them in just the right way, you get something explosive: a Monad. We can no longer delay the equations:

class Monad m where
    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b

That’s it. Two functions: return puts something into the monad, and (>>=), called “bind”, transforms one monad into another. We’ll see what the monad can do in just a minute. First though, for the sake of concreteness, let’s extend our list implementation for use as a monad:

instance Monad [] where
    return a   = [a]
    (>>=) ls f = join (map f ls)

The definition of return is the same as unit: put the item in a list all by itself. Bind (>>=) combines map and join into a single operation. First you map k onto the list ls, and then since f returns a list of lists, you use join to concatenate the results into a single list.

But what’s this monad thing good for? Suppose you wanted to add all of the value in one list to all of the values in another list to create a big list:

sumTwoLists [1, 2, 3] [4, 5, 6] --> [5, 6, 7, 6, 7, 8, 7, 8, 9]

The JavaScript is something like:

function sumTwoLists(ks, ls) {
    var result = [];
    for (var i = 0; i < ks.length; ++i) {
        for (var j = 0; j < ls.length; ++j) {
            result.push(ks[i] + ls[j]);
        }
    }
    return result;
}

With monads we write:

sumTwoLists ks ls = return (ks >>= \k ->
                            ls >>= \l ->
                            k + l)

That looks pretty clean, but nothing special. Fortunately, since monads are so useful, better syntax for them has existed for a long time. We could write:

sumTwoLists ks ls = do k <- ks
                       l <- ls
                       return k + l

This is called the “do notation” for obvious reasons. There’s another variation, my personal favorite is called “list comprehension syntax” or I can’t believe it’s not set theory!>

sumTwoLists ks ls = [k + l | k <- ks, l <- ls]

Either way, it’s just syntactic sugar on top of whole grain monads. The syntact sugar may look like some sort of imperative language or something involving a snake. But accept no substitutes, in Haskell any monad can use either syntax.

We’ve see how a list monad works, but that doesn’t yet help us with not since our only monad is the LinkedList. For not, we need a monad that just transforms values directly: an identity monad. It doesn’t do anything special to values, just forwards them along:

instance Monad Identity where
    return a  = a
    (>>=) a f = f a

Now we can finally define liftCombiner in completely general terms:

liftCombiner c as n = c [a n | a <- as]

Now the idea of “make these combiners work on accepters now” is as easy to write as it is to think:

acceptOnlyIf = liftCombiner and
acceptAny    = liftCombiner or
acceptNot    = liftCombiner not

Final thought

Today we’ve seen how to handle combining accepters (functions from a node to a boolean) where the combiner is any monad. It turns out that accepters are monads too. Do you think there’s a way to lift any combiner on any monad to work other monads (in addition to accepters)? If so, how? If not, what relationship do the monads need to have to make it so?

function reduce ( object, acc, fn, context ){

    if ( !object )
        return acc;

    for ( var name in object )
        acc = fn.call( context || object, acc, object[ name ], name, object );

    return acc;
}

if ( object.reduce && object.reduce !== arguments.callee )
    return object.reduce( acc, fn, context );