Functional Programming in JavaScript – playing with lists, cons, car and cdr

Gist: JavaScript allows to describe lists as functions in a very natural way. By putting in place a few short albeit sophisticated functions called cons, car (aka head) and cdr (aka tail) a complete system for handling lists (create, sort, filter, etc.) as binary trees is shown here. Recursion of calls lies at the basis of all; any sizeable list in this system requires a huge call stack and, unfortunately, this seems to go against the way the various JavaScript engines are implemented. Therefore, this has to remain an exercise.

In the last couple of years, my studies about functional programming have shifted focus, moved away from Java and gotten into JavaScript. This was caused firstly by me going to work for a web agency and having to become proficient in that pesky language (well, only in its good parts :-))

Using JavaScript and its first-order functions, it is perfectly legitimate to stay away from classes, types and stuff. Being just you and the functions makes it just right to program …functionally.

My most relevant products so far are all on GitHub (user Muzietto):

  • geieslists: a complete (experimental !) library for managing lists built purely from primitive functions, starting from cons, car/head, cdr/tail, and ending up with high-level list operations like splice or mergesort
  • littleFunkyJavaScripter: a thorough rewrite of the Little Schemer in JavaScript, using geieslists as engine to build and manage the unavoidable lists. I still have to “do” chapter 10, but the rest of the book is all there, especially the supercool Y-combinator.
  • seasonedFunkyJavaScripter: still work in progress. Same as above with regards to the Seasoned Schemer. I just got till chapter 13 and got stuck over call-with-current-continuation. I hope I’ll be able to proceed further in the future: continuations are insanely interesting.
  • geiesmonads: maybe and state monad in JavaScript – examples of usage. In the case of the state monad you can find there the embryo for a whole system of modular, chainable operations.
  • geiesfolds: Fold right and then left in JavaScript. Lots of examples of usages.

(geieslists reads j-s-lists in Italian, how funny…)

Example list computation in JavaScript

I am presenting a simple example using geieslists. Let’s evaluate the head of a two-elements list.

Inside geieslists any list (in the best LISP tradition) is the concatenation of an element car and another list cdr. This concatenation takes place through the application of a function named cons (they tell me that’s an abbreviation of constructor), which binds those two values. The resulting cons is obviously a list, just like cdr was. A list of two elements 'a' and 'b' is created recursively starting from a value EMPTY_LIST (we’ll see later what an EMPTY_LIST is) as:

list = cons('a',cons('b',EMPTY_LIST))

Off with her head!

When we want to extract the head (aka car) of that list (aka cons), we apply over that cons a function named head (or car); head passes to cons a third function (in this case anonymous) which, given two arguments, simply returns the first one. Those two arguments happen to be the original two values given to cons in the previous paragraph. In detail, the expression of head is:

head = function(cons){
  return cons(function(first,second){
    return first;
  });
};

In other words the head of a list comes from the application of function head to list; that’s the result of running:

head(list) = (function(cons){
  return cons(function(first,second){
    return first;
  });
)(list)

If we search instead the tail, we apply over the same cons a function named tail (or cdr); tail passes to cons a new anonymous binary function that receives the two original values of the cons and returns the second one. In short, the tail of a list is the result of running:

tail(list) = (function(cons){
  return cons(function(first,second){
    return second;
  });
)(list)

Happy the cons: he lives a simple life

The missing piece is cons. cons is basically a binary function with a single simple goal in life: to allow other binary functions to access its two original arguments and use them as their own arguments. In a way, cons does nothing with its arguments; it just wraps them and keeps them warm and ready for other functions to use. In plain JavaScript:

cons = function(first, second) {
  return function(anotherBinaryFunction){
    return anotherBinaryFunction(first, second);
  };
};

Technically cons is a function that receives two arguments, runs and returns as a result a function which in turn is ready to receive another function as its parameter. A bit dizzying, first time I saw it.

This means that if we pass to the function cons(first, second) another function as parameter, the value cons(first, second)(anotherBinaryFunction) will be whatever returns from running anotherBinaryFunctions using cons‘ arguments as parameters. In detail:

cons(first, second)(anotherBinaryFunction) =
  anotherBinaryFunction(first, second);

In the case of the two-elements list we’d have:

cons('a', cons('b', EMPTY_LIST))(anotherBinaryFunction) =
  anotherBinaryFunction('a', cons('b', EMPTY_LIST));

If we want to extract the head of this two-elements list and we recall the definition of head, the substitution goes:

cons('a', cons('b', EMPTY_LIST))(head) =
  headInnerBinaryFunction('a', cons('b', EMPTY_LIST)) =
  (function(x, y) { return x; })('a', cons('b', EMPTY_LIST)) = 'a';

This makes a lot of sense when told this way, but things ain’t that easy. In the code of our program we don’t write:

cons('a', cons('b', EMPTY_LIST))(head)

but we write instead:

head(cons('a', cons('b', EMPTY_LIST)))

What makes the magic happen, so that:

head(cons('a', cons(‘b’, EMPTY_LIST))) = 'a'

like if there was no cons in between ?

Head’s Version

Here is how the matter is seen from the point of view of head. I guess it is better to use here a simpler lambda notation (Scala, Java8) that allows to see clearly input parameters and returned values.

In this notation cons, head and tail become respectively (please compare with the JavaScript implementations given previously):

cons = (x, y) -> w -> w(x, y)
head = c -> c((x, y) -> x)
tail = c -> c((x, y) -> y)

Here c is a shortcut/reminder that the operand of head and tail is a cons. We saw that:

head(list) = (c -> c((x, y) -> x))(cons('a', cons('b', EMPTY_LIST)))

NB: I am putting in bold the two brackets that delimit head.

For the sake of clarity, let’s substitute:

cons('b', EMPTY_LIST) = TAIL

Substituting inside list the first usage of cons with its definition we obtain:

head(list) = (c -> c((x, y) -> x))(cons('a', TAIL)) =
(c -> c((x, y) -> x))(w -> w('a', TAIL))

At this point we see that technically head receives its cons, which is nothing else than a closure carrying the whole list. Because of the definition of head, parameter c (the cons) becomes c(fun), where fun is that convenient inner binary function that always returns the first of its own parameters: that’s where head got its name from. The steps are (please follow carefully the various substitutions):

head(list) = (c -> c((x, y) -> x))(w -> w('a', TAIL)) =
(w -> w('a', TAIL))((x, y) -> x)) =
((x, y) -> x))('a', TAIL) = 'a'

So, in a way, head and cons pass each other the sherry…

Basically, cons and head (or tail) plug into each other: cons takes a function and gives it its own context; head takes a function and gives it a visitor that operates in its context. In a way, head is more refined; cons is more generic. head is the specialist, and so is tail.

There is lot to understand here, a lot more to dig and discover:

  • are there other possible list specialists besides head and tail?
  • what are the characteristics that make these functions pluggable in each other?
  • what are other problems (not necessarily involving lists) that may be solved by pairs of such crafted functions?

The key must be in the signatures, but it’s the bodies that express the intent. Gotta play some more with these concepts.

UPDATE All the playing resulted in another post, which investigates whether this may be a known FP pattern.

Full of Emptiness

The last bit is the definition of EMPTY_LIST.

EMPTY_LIST is something that, whenever encountered, signals that it’s time to stop processing the list. It can be any value. But here we are used to have cdr as a function, so it’s nicer that EMPTY_LIST be a function (provided that we use always exactly the same instance!). We like the fixed-point function because it reminds us of the Y-combinator, so we say:

EMPTY_LIST = function(x) { return x; }

The problem with the stack of the function calls

At the heart of this system we have recursive calls to the cons function. This creates very soon a huge call stack for each list you need. It comes out that javaScript engines are not optimized for recurring on closures [1] (why is that?).

This impacts both the waste of memory created by each list and the running time of a mid-sized cons operation. It is interesting to measure the impact on execution speed by using the benchmark page [1]

The pages I owe credit to for building geieslists are primarily three:

[1] see http://spencertipping.com/js-instabench/ – please compare:
– allocating small structures -> 1M (int, int) pairs as array literals
– allocating small structures -> 1M (int, int) pairs as binary CPS closures
– accessing small structures -> 1M (int, int) pairs as array literals
– accessing small structures -> 1M (int, int) pairs as binary CPS closures

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s