The Little Pythoner, Part I

I saw this article from alistapart, which is about Javascript’s prototypal object orientation. So the article mentioned Douglas Crawford, and I was immediately reminded about my struggle in understanding the language itself. Back then I used to also refer to his site for a lot of notes in Javascript. So I went back to have a quick read, and found this article that discusses the similarity between Javascript and Lisp.

So within the article, there’s a mention of this book titled “The Little LISPer”. Being a fanboy of LISP that quickly grabbed my attention. So one thing led to another I started to look for the book (I read “The Little Schemer” instead), and start trying out the example. I was too lazy to set up Lisp (or any other dialect of it), so I decided to use Python. Although there are some syntax differences and limitations, I still somehow managed to get most of the examples implemented.

While I pretty much learned recursion the hardway through work, the book managed to restructured my understanding on the topic. After implementing some of the examples in the book, a proper recursion function does follow some patterns. These patterns are summarized as ten commandments in the book, which are basically the DOs and DON’Ts when writing a recursive function. Most of the examples here shoud run fine in a standard Python3 environment.

So the first chapter is titled “Toys”, which is pretty much a quick introduction to LISP. First thing first is the definition of an atom. Practically an atom has to satisfy the following criteria:

• a string of characters (e.g. word, 1337, $ymb*ls)
• does not have parentheses in them

With that in mind, we first write a unit-test to satisfy the criteria.

from operator import *

def test_isatom():
    test_cases = (('atom', True),
                  ('turkey', True),
                  ('1492', True),
                  ('u', True),
                  ('*abc$', True),
                  ('Harry', True),
                  (('Harry', 'had', 'a', 'heap', 'of', 'apples'), False))

    for atom, expected in test_cases:
        result = isatom(atom)
        assert result == expected

As shown in the unit test, strings in Python has to be enclosed with a quote characters ' (or "). Hence we cannot really test the second point. Next we would need to implement the primitive, as we are not using Lisp, also because this is not defined in Python.

def primitive(func):
    def _decorator(*args, **kwargs):
        try:
            return func(*args, **kwargs)
        except AssertionError:
            return None

    return _decorator

@primitive
def isatom(atom):
    return and_(not_(isinstance(atom, tuple)),
                isinstance(atom, str))

There are times where the primitives not returning an answer (may be due to mismatch in input type, or other reasons). In order to simulate the behaviour, each primitive function is decorated so that if the input argument fails assertion, a None is returned instead (which will be shown in the later implementations).

Now that we have isatom defined, run the test to verify (I am not writing a book, so most of the time the test should pass unless otherwise specified).

test_isatom()

A list on the other hand is a sequence of items. The sequence of items must be enclosed within a pair of parentheses. Another list can also defined as an element in the sequence, which is commonly referred to as a nested list. For example ((hello world) yo). Due to the differences in Python, I am using tuples to represent lists (both immutable, which should be a good fit). Also note that a tuple with one element requires a comma after the element.

Then we are given the definition of S-expression, which can be

• an atom
• a list

And in fact, a list is actually a sequence of s-expressions (or none of it) enclosed by a pair of parentheses. So, being a language that is built by lists, Lisp by default defines a couple of functions to manipulate them. First of all is the car primitive function to fetch the first element from a given list. The definition can be seen in the unit test below. Note that when an atom or empty list is passed to `car` we should receive no answer.

def test_car():
    test_cases = ((('a', 'b', 'c'), 'a'),
                  ((('a', 'b', 'c'), 'x', 'y', 'z'), ('a', 'b', 'c')), 
                  (((('hotdogs', ),), ('and', ), ('pickle', ), 'relish'), (('hotdogs', ),)),
                  (((('hotdogs', ), ), ('and', )), (('hotdogs', ), )),
                  ('hotdog', None),
                  ((), None))

    for l, expected in test_cases:
        result = car(l)
        assert result == expected

Considering we are doing this in Python instead of Lisp/Scheme, so we would have to implement the primitive car function.

@primitive
def car(l):
    assert l
    assert isinstance(l, tuple)

    return l[0]

Next is the cdr primitive (resembles tail in Prolog), which fetches the remaining list excluding the first element. Also cdr would return no answer if input argument is an atom, or an empty list.

def test_cdr():
    test_cases = ((('a', 'b', 'c'), ('b', 'c')),
                  ((('a', 'b', 'c'), 'x', 'y', 'z'), ('x', 'y', 'z')),
                  (('hamburgers', ), ()),
                  ('hotdogs', None),
                  ((), None))

    for l, expected in test_cases:
        result = cdr(l)
        assert result == expected
    
    
@primitive
def cdr(l):
    assert l
    assert isinstance(l, tuple)
    
    return l[1:]

For the people who are familiar with languages like Prolog, lisp does share a somewhat similar structure for lists. Each list is constructed by a head (car) element, and the rest forms the tail (cdr). If the list has only one element, then the respective cdr returns an empty list.

Constructing a list is just passing the two different elements into a primitive function named cons (which should be the short of “construction”). The two required parameters are any s-expression, and a list.

def test_cons():
    test_cases = (('peanut',
                   ('butter', 'and', 'jelly'),
                   ('peanut', 'butter', 'and', 'jelly')),
                  (('banana', 'and'),
                   ('peanut', 'butter', 'and', 'jelly'),
                   (('banana', 'and'), 'peanut', 'butter', 'and', 'jelly')),
                  ((('help', ), 'this'),
                   ('is', 'very', 'hard', 'to', 'learn'),
                   ((('help', ), 'this'), 'is', 'very', 'hard', 'to', 'learn')),
                  (('a', 'b', 'c'),
                   'b',
                   None),
                  ('a', 'b', None))

    for s, l, expected in test_cases:
        result = cons(s, l)
        assert result == expected

        
@primitive
def cons(s, l):
    assert isinstance(l, tuple)

    return (s, ) + l

An empty list (or null list) is special in the world of Lisp. It sort of both exists and not exists in every list in Lisp. Usually it only shows up when a cdr call is made to a list with one and only one element (besides creating one manually, that is).

There is also a primitive method to test whether a given list is empty (no, it doesn’t work with atoms), as shown below.

def test_isnull():
    test_cases = (((), True),
                  (('a', 'b', 'c'), False),
                  ('spaghetti', None))

    for l, expected in test_cases:
        result = isnull(l)
        assert result == expected
        

@primitive
def isnull(l):
    assert isinstance(l, tuple)

    return l == ()

Also, we can also check the equality of two given non-numeric atoms

def test_iseq():
    test_cases = (('Harry', 'Harry', True),
                  ('margarine', 'butter', False),
                  ((), ('strawberry', ), None))

    for alpha, beta, expected in test_cases:
        result = iseq(alpha, beta)
        assert result == expected


@primitive
def iseq(alpha, beta):
    assert isatom(alpha) and isatom(beta)

    return alpha == beta

So this is a rather long-winded summary of the first chapter.