Ages ago, when I first decided to delve into the manuscripts of yore that let us bind demons in silica, I wrote a lisp interpreter (in C), and, in a state of insomnia-induced derilium, wrote a page about it. Turns out, the drivel

lists and atoms concells function-argument idea special forms (quote)

Ok so I have a six-hour train ride ahead of me, a copy of the wizard book of programming, and a working gcc setup. Let’s write a lisp interpreter.

What is Lisp

Lisp, short for LISt Processing, is an old (‘59, second after FORTRAN) programming language that had its own ideas on how to do things. It pioneered a lot of programming concepts, perhaps most famously practical recursion (which, while possible in ASM, isn’t nearly as straight-forward or useful), functional programming (which is quite natural in a meta-language), garbage collecton (sparing us from having to manually manage memory like savages), repl loops (both foundational for modern languages like python) and object-oriented programming (which Smalltalk went on to perfect, and Java proceeded to fuck up). More importantly, it is a meta-programming language - iow most of the “programming” consists of modifying/expanding the language itself (well, technically it’s mostly function definitions, but I digress). That makes all tasks roughly equal in difficulty, which is why it had been used extensively in AI programming and is nowadays popular for quantum computing, with minimal changes - essentially none to the language itself.

Instead of going with the imperative paradigm natural for hardware, Lisp was made for ease of evaluating and manipulating mathematical expressions. It wasn’t really meant to work as a language, but with some clever ideas regarding command structure, it ended up being quite functional (pun intended). Let’s take a look at those expressions. f(x,y)=x^3+y^2 is a polynomial in the usual infix notation which is rather easy to read on paper but a nightmare for computers to parse (figuring out which operands are applied on which variables takes context). We could represent it in postfix notation as xxx**yy*+ (using simplified befunge syntax - another fun language I recommend reading up on). That is trivially interpreted with a basic (imperative) stack automaton, as the function applications are themselves imperative, but it’s impossible to work with from a mathematical perspective, as it is similarly hard to predict how the values we apply the operands on are constructed. Bracketed prefix notation on the other hand groups functions with their arguments as follows: (+ (* x x x) (* y y)). Now, each operand comes with its own context! It is trivial to tell which operands we apply in what order, and what their arguments are. Writing a function that takes derivatives, for example, can now be accomplished by first deriving all arguments (makes it easier to simplify expressions if we do that first), checking the current operand, and reshuffling the arguments accordingly (for an actual example, see “Structure and Interpretation of Computer Programs” Chapter 2.3.2). We can also take a hint from A. Church and wrap it in a lambda closure - (lambda (x y) (+ (* x x x) (* y y))) - giving us a context for the whole function (what variables it takes), and producing a valid lisp expression. This makes it quite easy to manipulate not only mathematical expressions, but also whole code structures. Indeed, a very useful aspect of Lisp is that it only needs a minimal set of instructions to be implemented, as the rest can be derived from those (some purists would argue that technically, you only need an implementation of eval, but that still includes other functions, just within a convenient wrapper). The set of instructions I’ll be implementing is defun lambda cond eq car cdr cons atom quote + - * / % - a repl loop takes care of inputs and outputs, and we’ll just bravely shove everything else aside.

Lisp datatypes

Lisp essentially only has two datatypes. One of them is the atom, the individual strings that name all functions, variables, or simply signify themselves. Numbers are stored as a string of digits, which, while making it less efficient to work with them (as we cannot use the computer’s existing hardware arithmetic functions for them, but have to do digit arithmetic), it means we also have arbitrary precision. Atoms we shall simply treat as strings. The other - as the name suggests - is lists, though those are handled in a somewhat unusual manner. As lists have arbitrary length and contents, they would be quite tricky to implement, yet Lisp has a trick up its sleeve and circumvents the issue by not implementing lists at all and instead implementing a binary structure known as concells. Each concell consists of two other objects, each of which can be an atom or another concell. Thus, if we denote a concell as (a.b) (commonly, a is referred to as the car and b as the cdr), the list (a b c d e) becomes (a.(b.(c.(e.())))). The empty list () is a special case called nil and functions both as the false boolean and as a list terminator the same way a null byte terminates strings, and is equivalent to a nullpointer in C/C++ - try printf("%p\n",0);

Those we shall implement as two fixed-size arrays, for efficiency and ‘simplicity’ reasons. A C++ std::vector of a custom concell struct that denotes the types of its pointers with an enum would be the ‘correct’ way of implementing this, but I opted for a more basic, fixed-memory solution. Fun fact, Lisp Machines were mainframe-type computers optimized to run Lisp - if doing it in hardware was a good idea, then why overcomplicate our lives with ‘best-practice’ code?

## define MAX 4096
## define STRLEN 16
int mem[MAX*2]={0};
char strings[MAX*STRLEN]={0};
int lastmem=1,laststring=0;

## define iscons(x) (x<MAX)
## define isstr(x) (MAX<=x && x<2*MAX)
## define bool(x) (x?newstring_s("t"):0)

int car(int index){return mem[2*index];}
int cdr(int index){return mem[2*index+1];}
char*getstr(int index){return strings+(index-MAX)*STRLEN;}

int newcell(int car,int cdr){
    if(lastmem>=MAX)return 0; // hcf
    mem[2*lastmem]=car;
    mem[2*lastmem+1]=cdr;
    return lastmem++;
}

int newstring_s(char*string){
    for(int i=0;i<laststring;i++)
    if(strings[STRLEN*i])
        if(!strcmp(string,strings+STRLEN*i)) // lazy hack
            return i+MAX;

    if(laststring>=MAX)return 0; // hcf

    for(int i=0;i<STRLEN && string[i];i++)
        strings[laststring*STRLEN+i]=string[i];
    laststring++;
    return laststring-1+MAX;
}

And with that, we have all we need to represent Lisp programs and expressions. Lastly, let’s define some functions for displaying all of that.

void pprint_(int i){
    if(i==0)printf("<0>");
    else if(i<MAX){
        putchar('(');
        pprint_(getcar(i));

        for(int t=getcdr(i);t;t=getcdr(t))
            if(t<MAX)putchar(' '),pprint_(getcar(t));
            else putchar('.'),pprint_(t),t=0;

        putchar(')');
    }else printf("%s",getstr(i));
}

void pprint(int i){pprint_(i);putchar(10);}

void printmem(){ // for debugging, prints the memory itself
    printf("%i cons defined, %i atoms\n",lastmem,laststring);
    for(int i=0;i<lastmem;i++)printf("%i:(%i.%i) | ",i,getcar(i),getcdr(i));putchar(10);
    for(int i=0;i<laststring;i++)printf("%i:<%s> | ",i+MAX,strings+i*STRLEN);putchar(10);
}

Parser

We can now represent Lisp expressions, and we’ll soon figure out how to interpret them, but first, we’ll have to be able to parse them, iow to take a program, consisting of text, and transform it into a tree of concells and atoms.

FILE*fd;char lookahead=0;

int iswhite(char a){return a==' '||a=='\n'||a=='\t';}
int isparen(char a){return a=='('||a==')'||a==EOF;}
char getnext(){return lookahead=getc(fd);}
char white(){
    while(iswhite(lookahead))getnext();
    return lookahead;
}

int newstring(){
    char buf[STRLEN]={0};
    for(int i=0;i<STRLEN && !iswhite(lookahead) && !isparen(lookahead);i++){
        buf[i]=lookahead;
        getnext();
    }

    return newstring_s(buf);
}

int parselist(){
    white();
    if(lookahead==')' || lookahead==EOF){getnext();return 0;}

    int car;
    if(lookahead=='('){getnext();car=parselist();}
    else car=newstring();

    return newcell(car,parselist());
}

Lisp functions

Before we get started on the interpreter (iow the part that takes all the code and structures and actually does stuff), let’s actually go through what each of the primitive functions we’ll be implementing does. For those of you who already have dipped their feet in Lisp - there isn’t really a formal language specification as with eg python (ok that’s a lie, [Common Lisp] very much exists, but it is by no means an authority), so this is also a definition of which functions I decided to include, and what syntax they use (defun specifically has a lot of variations across dialects).

• (quote a) - this returns its argument unchanged. It might seem somewhat pointless to have a function that by definition doesn’t do anything, however this ends up being quite relevant - functions in Lisp evaluate their arguments before applying, giving rise to eg the “first derive all arguments” described in the beginning. Without this, it would be impossible to specify pure data as arguments. The concept is further elaborated in the wizard book.

• (atom a) - returns whether a is/refers to an atom (aka string) - an interface to isstr, so to speak. We can use cond to invert the output of this and thus test for concells. I elected to implement this because it’s the one more frequently used to end recursion.

• (cons a b) - makes a concell with a as the car and b as the cdr. This differs from (quote (a b)) in that lists are nil-terminated, while cons allows us to set each element ourselves. This is also the foundation of custom datatypes.

• (car a) and (cdr a) - return the car and cdr elements of a.

• (eq a b) returns whether two elements are the same. More precisely, it evaluates both arguments, and recursively compares them - while we can simply compare atoms via their pointers, concells are recursive structures.

• (cond (<bool1> <expr1>) (<bool2> <expr2>) ...) - conditionals! Also the main way of controlling program flow. cond iterates through its arguments and evaluates the car of each. If it evaluates to anything but false, the whole expression evaluates to the cdr of that subexpression. Better make sure it has a default at the end of the argument list! You can imagine this as a list of else ifs.

• (lambda (<vars>) <expr>) - lambda defines an anonymous function, as exemplified in the beginning. It takes a list of variables to bind, and provides an expression to evaluate, with the variables substituted. In practice, this works by creating a sub-environment, called a ‘closure’, wherein the variables are bound to their values. Some dialects (famously, Scheme) are implemented to the closure persists with the lambda, ie you can return a lambda from a function, use a lambda as an argument to another function, or [curry] a function, and the variables in the closure will persist (see [funarg problem]). I elected not to implement that, as it is a mess to implement and can relatively easily be implemented within Lisp if you really need it.

• (defun a b) - going with the closure idea, this binds global variables. For the rest of the program, the atom a evaluates to the expression b. This allows us to define variables and functions (you could say it deanonymizes lambda functions).

• +-*/% - arithmetics, work pretty much as you’d expect. The one exception to that is that they work on arbitrarily many arguments, which is a bit less straight-forward for the division and modulus.

As elaborated in the quote explanation, each function first evaluates its arguments, and then does its business with them. This bears repeating, as it has some implications for both implementation and command composition.

Interpreter

Fortunately for the purists, the actual interpretng is (mostly) a single eval function. Unfortunately, it is quite a long one, consisting of case checks for each form the expressions could take. We’ll also ignore the bignum idea described above and convert numbers back and forth between digit and native representation for calculations (math is hard ok).

int atoi(int index){
    int res=0;
    for(int i=0;i<STRLEN;i++){
        char a=*(strings+(index-MAX)*STRLEN+i);
        if(a)res=res*10+a-'0';
    }
    return res;
}

int itoa(int i){
    char buf[STRLEN]={0};
    sprintf(buf,"%i",i);
    return newstring_s(buf);
}

int eval(int exp,int env);

int primfn(int exp,int env){
    int fn=getcar(exp),args=getcdr(exp);

    if(fn==newstring_s("funcname")){
        // XXX INSERT CODE HERE
    }

    printf("not primfn:");pprint(fn);
    return 0;
}

Now, to fill in the blanks.

if(fn==newstring_s("quote"))return args;
if(fn==newstring_s("lambda"))return exp;

if(fn==newstring_s("atom"))return isstr(car(eval(car(args),env)))?newstring_s("t"):0;
if(fn==newstring_s("eq"))return car(eval(car(args),env)) == car(eval(car(cdr(args)),env))?newstring_s("t"):0;

if(fn==newstring_s("car"))return car(car(eval(car(args),env)));
if(fn==newstring_s("cdr"))return cdr(car(eval(car(args),env)));
if(fn==newstring_s("cons"))return cons(car(eval(car(args),env)),car(eval(car(cdr(args)),env)));

if(fn==newstring_s("cond")){
    for(int cond=args;cond;cond=cdr(cond))
        if(car(eval(car(car(cond)),env)))
            return car(eval(car(cdr(car(cond))),env));
    return 0;
}

if(fn==newstring_s("+")){
    int res=0;
    for(;args;args=cdr(args))
        res+=atoi(car(eval(car(args),env)));
    return itoa(res);
}

if(fn==newstring_s("*")){
    int res=1;
    for(;args;args=cdr(args))
        res*=atoi(car(eval(car(args),env)));
    return itoa(res);
}

if(fn==newstring_s("-")){
    int res=atoi(car(eval(car(args),env)));
    for(args=cdr(args);args;args=cdr(args))
        res-=atoi(car(eval(car(args),env)));
    return itoa(res);
}

if(fn==newstring_s("/")){
    int res=atoi(car(eval(car(args),env)));
    for(args=cdr(args);args;args=cdr(args))
        res/=atoi(car(eval(car(args),env)));
    return itoa(res);
}

if(fn==newstring_s("%")){
    int res=atoi(car(eval(car(args),env)));
    for(args=cdr(args);args;args=cdr(args))
        res%=atoi(car(eval(car(args),env)));
    return itoa(res);
}

int eval(int exp,int env){
    if(!exp)return cons(0,env);

    if(isstr(exp)){
        for(int val=env;val;val=cdr(val))
            if(car(car(val))==exp)
                return cons(cdr(car(val)),env);
        return cons(exp,env);
    }

    if(isstr(car(exp))){
        int op=car(eval(car(exp),env));

        if(iscons(op))
            return eval(cons(op,cdr(exp)),env);

        if(op==newstring_s("defun")){
            int a = car(cdr(exp));
            int b = car(cdr(cdr(exp)));

            b = car(eval(b,env));

            int c = cons(a,b);
            env=cons(c,env);

            return cons(a,env);
        }
        return cons(primfn(cons(op,cdr(exp)),env),env);
    }

    if(car(car(exp)) == newstring_s("lambda")){
        int cloj=env,names=car(cdr(car(exp))),vals=cdr(exp);
        for(;names;names=cdr(names),vals=cdr(vals))
            cloj=cons(cons(car(names),car(eval(car(vals),env))),cloj);
        int res = eval(car(cdr(cdr(car(exp)))),cloj);
        return cons(car(res),env);
    }

If all else fails, we are most likely dealing with a compound expression, ie a list of expressions to be evaluated. In that case, we want to iterate through all of them, updating the environment as we go, and return the value of the last one (or rather, we return the current one if there is no next one - same statement, but easier to implement).

    int t = eval(car(exp),env);
    if(cdr(exp))return eval(cdr(exp),cdr(t));
    else return t;
}

int main(){
    init();
    int env=0;
    fd=stdin;
    while(1){
        if(feof(fd))return 0;
        getnext();
        white();
        getnext();
        white();
        int data=parselist();
        //pprint(data);
        int res=eval(data,env);
        env=cdr(res);
        pprint(car(res));
    }
    return 0;
}

Lisp programming

Now that we have a functioning Lisp interpreter, let’s write some code in Lisp. As Lisp is (in)famous for being a functional language and we have so far been working with the imperative C, let’s implement some functional code. Most of the following operate on lists, by first doing something with the first element, and then recursively calling themselves on the rest of the list, if present. Thus, the general structure is the same.

(defun map (lambda (f x) (
    cond
    ((eq x ()) ())
    (t (cons (f (car x)) (map f (cdr x))))
)))

Let’s see it in (simplified) action:

(defun f (lambda (x) (* x x)))
(map f (quote 1 2 3 4 5))
> ((map f (1 2 3 4 5)))
> (1 (map f (2 3 4 5)))
> (1 4 (map f (3 4 5)))
> (1 4 9 (map f (4 5)))
> (1 4 9 16 (map f (5)))
> (1 4 9 16 25 (map f ()))
> (1 4 9 16 25)

(defun filter (lambda (f x)(
    cond
    ((eq x ()) ())
    (t (cond
        ((f (car x)) (cons (car x) (filter f (cdr x))))
        (t (filter f (cdr x)))
    ))
)))

(defun f (lambda (x)(eq (% x 2) 0)))
(filter f (quote 1 2 3 4 5))
> ((filter f (1 2 3 4 5)))
> ((filter f (2 3 4 5)))
> (2 (filter f (3 4 5)))
> (2 (filter f (4 5)))
> (2 4 (filter f (5)))
> (2 4 (filter f ()))
> (2 4)

(defun range (lambda (from to)(
    (defun range_acc (lambda (from to acc)
        (cond
            ((eq from to) acc)
            (t (cons from (range_acc (+ from 1) to acc)))
        )
    ))
    (range_acc from to ())
)))

(range 0 6)
> ((range 0 6))
> (0 (range 1 6))
> (0 1 (range 2 6))
> (0 1 2 (range 3 6))
> (0 1 2 3 (range 4 6))
> (0 1 2 3 4 (range 5 6))
> (0 1 2 3 4 5 (range 6 6))
> (0 1 2 3 4 5)

(defun foldr (lambda (f x s) (
    cond
    ((eq x ()) s)
    (t (f (car x) (foldr f (cdr x) s)))
)))

(defun foldl (lambda (f x s) (
    cond
    ((eq x ()) s)
    (t (foldl f (cdr x) (f (car x) s)))
)))

(foldr + (quote 1 2 3 4 5) 0)
> (foldr + (1 2 3 4 5) 0)
> (+ 1 (foldr + (2 3 4 5) 0))
> (+ 1 (+ 2 (foldr + (3 4 5) 0)))
> (+ 1 (+ 2 (+ 3 (foldr + (4 5) 0))))
> (+ 1 (+ 2 (+ 3 (+ 4 (foldr + (5) 0)))))
> (+ 1 (+ 2 (+ 3 (+ 4 (+ 5 (foldr + () 0))))))
> (+ 1 (+ 2 (+ 3 (+ 4 (+ 5 0)))))
> (+ 1 (+ 2 (+ 3 (+ 4 5))))
> (+ 1 (+ 2 (+ 3 9)))
> (+ 1 (+ 2 12))
> (+ 1 14)
> 15

(foldl + (quote 1 2 3 4 5) 0)
> (foldl + (1 2 3 4 5) 0)
> (foldl + (2 3 4 5) 1)
> (foldl + (3 4 5) 3)
> (foldl + (4 5) 6)
> (foldl + (5) 10)
> (foldl + () 15)
> 15

(defun fac (lambda (x)(
    cond
    ((eq x 0) 1)
    (t (* n (fac (- n 1))))
)))
(fac 5)
> (fac 5)
> (* 5 (fac 4))
> (* 5 (* 4 (fac 3)))
> (* 5 (* 4 (* 3 (fac 2))))
> (* 5 (* 4 (* 3 (* 2 (fac 1)))))
> (* 5 (* 4 (* 3 (* 2 (* 1 (fac 0))))))
> (* 5 (* 4 (* 3 (* 2 (* 1 1)))))
> (* 5 (* 4 (* 3 (* 2 1))))
> (* 5 (* 4 (* 3 2)))
> (* 5 (* 4 6))
> (* 5 24)
> 120

(defun fact (lambda (x)
    (define fact_tail (x a)(
        cond
        ((eq x 0) a)
        (t (fact_tail (- x 1) (* x a)))
    ))
    (fact_tail x 1)
))
(fact 5)
> (fact_tail 5 1)
> (fact_tail 4 5)
> (fact_tail 3 20)
> (fact_tail 2 60)
> (fact_tail 1 120)
> (fact_tail 0 120)
> 120

To roll back a bit, why is functional programming such a big deal? Instead of giving the programmer a minimal set of complicated functions and requiring them to figure out how to get shit done, it gives them a ton of tiny functions and lets them daisy-chain the results together. In a way, it is a metaphor for what we have been doing - took a bunch of primitive functions, and assembled them in larger, more complex ones. [XXX got off the train. rewrite that last part - it sounds deranged. point out that low-func iterative is better suited for computers as it is how they do code at the most fundamental level]

[functional programming does not allow assignment, so evaluating the same expression twice with the same arguments will always produce the same result, modelling mathematics (sicp 3.1.3)]

[functions are single valued (not necessarily total) maps between sets] [anonymous functions]

[“functional” meaning “modeled after / modeling mathematical functions” - derive rest from that]

Something something sum of all odd cubes of the numbers from 1 to 20:

res=0;
for(int i=0;i<20;i++){
    int t=i*i;
    if(t%2==0)
        res+=t;
}

(
    (defun g (lambda (x res)(
        (defun f (lambda (x res)(
            cond
            ((eq (% (* x x) 2) 0) (+ res (* x x)))
            (t res)
        )))
        (cond
        ((eq x 21) res)
        (t (g (+ x 1) (f x res)))
        )
    )))
(g 0 0)
)

(defun a (range 0 21))

(defun b (map (lambda (x) (* x x)) a))

(defun c (filter (lambda (x) (eq (% x 2) 0)) b))

(foldl + c 0)

(foldl +
    (filter
        (lambda (x) (eq (% x 2) 0))
        (map
            (lambda (x) (* x x))
            (range 0 21)
        )
    )
    0
)

[implement currying] [compiler?] [mention we dont use tags] [elaborate on memory overflow & garbage collection] [maybe elaborate on why exactly were doing this? as in how we get from math to lisp?] [bignums] [XXX iterative example is wrong] steele ‘77 proved functional programming can be as fast/efficient as imperative?

(witten 19122023)