Web Design Forum: Learning Scheme: car, cdr and cons - Web Design Forum

JavaScript was originally going to be a Scheme interpreter, so can learning Scheme help my JavaScript knowledge? This is the first in a series of entries about what I've learnt.


As the story goes...
When Netscape were looking to add a new language into their browser, Brendan Eich suggested a Scheme interpreter and was hired for such a brilliant idea. Just before he started, someone at Netscape found out what Scheme was and insisted that he write something more popular like Java or Visual Basic.


How I'm planning to learn
There's a book called The Little Schemer (if you know where to look, you can find a free copy) that comes highly recommended by Douglas Crockford. It's written to teach Schemers recursion. This interests me a lot, so I'll start there. Well, that and an online beginner's guide.

Yeah, that's right, I don't speak Scheme. But, I do speak JavaScript. Since the two are so closely related, it should be possible to simulate some parts of the language. First, I'm going to make an environment to keep my global variables to a minimum. I can't forget everything I've learned in JavaScript just because I'm learning a new language.

I'll start with a self-executing anonymous function with strict mode enabled. I'll write a small function to throw errors and I'll expose a global variable to contain all my Scheme.

(function (win, undef) {

    "use strict";

    function error(reason) {
        throw new SyntaxError('SCHEME.' + reason);
    }

    win.SCHEME = {
    };

}(window));

car
The car function is one that takes a non-empty list and returns the first value. It doesn't work on atoms, only lists.

(car '(one two three)) ; Returns one

... I guess I should explain what a "list" and an "atom" are... and that snippit of code above. A list, as you've probably guessed, is a collection of atoms. It's the Scheme equivalent of an array. I'm still a little sketchy on the definition of an atom, I think it's essentially a string. Watch this space for facepalms and corrections. A list is defined by round brackets. The apostrophe at the start declares that as a list, rather than a collection of procedures. The semi-colon is an inline comment.

Here's the same snippit of code in JavaScript:

SCHEME.car(['one', 'two', 'three']); // Returns 'one'

Now all we have to do is write the car function, but first - car has two caveats: the argument must be a list and the list must not be empty. These caveats appear in cdr and cons as well, so I'll write a pair of functions to check for those.

    function isList(sExpression) {
        return toString.call(sExpression) === '[object Array]';
    }

    function isEmpty(list) {
        return list === undef || list.length === 0;
    }

And now the car function. This is a very simple function that returns the first argument of a list. If the arguments is not a list or it's empty, it throws an error.

    win.SCHEME = {
        car: function (list) {
            if (!isList(list) || isEmpty(list)) {
                error('car requires a non-empty list');
            }
            return list[0];
        }
    };

cdr
(Skateside's pro-tip, totally not stolen from The Little Schemer: pronounced "could-er")

(cdr '(one two three)) ; Returns (two three)

The cdr function is another of these non-empty list functions. It returns the original list without the first entry (always returning a list). In JavaScript, we have one of those, we call it "Array.shift", so this function is only slightly more complicated than car.

    win.SCHEME = {
        car: function (list) {
            // You've already seen this.
        },
        cdr: function (list) {
            if (!isList(list) || isEmpty(list)) {
                error('cdr requires a non-empty list');
            }
            var innerList = list;
            innerList.shift();
            return innerList;
        }
    };

cons
The cons function adds an entry to the beginning of a list, a bit like an inverse Array.push. I like this function because there isn't and obvious JavaScript equivalent, but it seems so useful. It can be re-created using Array.splice.

Unlike car and cdr, cons takes two arguments and the list can be empty. I should just explain the name of the first argument "sExpression". An S-expression is a Scheme variable. It can be a list, an atom and possibly a lambda (but I haven't got that far in my Scheming yet - again, watch this space).

    win.SCHEME = {
        car: function (list) {
            // You've already seen this.
        },
        cdr: function (list) {
            // You've already seen this, too.
        },
        cons: function (sExpression, list) {
            if (!isList(list)) {
                error('cons argument 2 must be a list');
            }
            var newList = list;
            newList.splice(0, 0, sExpression);
            return newList;
        }
    };

First day of Scheme
Want to play with some of the Scheme functions and see them in JavaScript? You'll need the complete script that we've written here then:

(function (win, undef) {

    "use strict";

    function error(reason) {
        throw new SyntaxError('SCHEME.' + reason);
    }

    function isList(sExpression) {
        return toString.call(sExpression) === '[object Array]';
    }

    function isEmpty(list) {
        return list === undef || list.length === 0;
    }

    win.SCHEME = {
        car: function (list) {
            if (!isList(list) || isEmpty(list)) {
                error('car requires a list');
            }
            return list[0];
        },
        cdr: function (list) {
            if (!isList(list) || isEmpty(list)) {
                error('cdr requires a non-empty list');
            }
            var innerList = list;
            innerList.shift();
            return innerList;
        },
        cons: function (sExpression, list) {
            if (!isList(list)) {
                error('cons argument 2 must be a list');
            }
            var newList = list;
            newList.splice(0, 0, sExpression);
            return newList;
        }
    };

}(window));

As I learn more about Scheme I'll post more JavaScript equivalents.