Swift's Abstract Syntax Tree

Not everything which uses a notation similar to s-expressions has anything to do Lisp.

There are cons cells. A cons cell is basically an untyped tuple. The syntax for a cons cell containing a number look like this: (1 nil) (where nil is the zero byte (I think, please correct me if I'm wrong)).

You can nest them, like this: (1 (2 (3 nil))).

Because nobody can be bothered to type those parens, the part of the compiler/interpreter called the Reader compiles syntax like this

(1 2 3)

to this

(1 (2 (3 nil))).

After being parsed by "the reader" (you could also call it "parser"), those nested tuples/cons cells are sent to eval function. The eval function takes the first element of the list (aka `car` in lisp-speak. My mnemonic is that a is to the left of the keyboard, therefore means first element). That first element is being regarded as the function, and the second element in the cons cell is the argument to the function.

The function to get the second item in the cons cell is `cdr`. I remember that by having `d` being to the right on my keyboard. (car 1 2) => 1. (cdr 1 2) => 2. (cdr 1 (2 (3 nil))) => (2 (3 nil)). That is how things are nested.

I digress. The eval function evaluates every symbol (aka atom) in these nested cons cells, and looks up the corresponding meaning of them in a big table of defined symbols. So the + symbol might match an addition function, the string-join symbol might match to a function for joining strings.

What is returned from eval you could say is the true AST, which still looks pretty darn similar to the lisp syntax. The function is then sent to the apply function, which applies the argument to the function. Remember that the argument can be a nested set of cons cell, so it can nest infinitely.

That's it! I'm no lisp expert, so if someone is, please correct me. But that's the gist of it. Syntax is read by the read function, the symbols are interpreted (lookup in a big key-value object) by the eval function, these function gets apply-ed with their argument. Very few primitives are needed by build a system from that. Here is a list of the primitives needed - these can be implemented in binary, C, assembly, Java, Javascript or whatever: http://stackoverflow.com/a/3482883.

BONUS SYNTAX:

If you want a eval to skip over a cons cell (and of course it's children), you can prepend it with a `'` symbol. So (cdr 1 '(this is never going to be evaled, but is just a list)) => (this is never going to be evaled, but is just a list)

This is called a 'quote'. Any Javascript array is basically working like a quoted list. If the first item in a javascript array was a function, and you applied the cdr of that array as argument to that funciton, it would be like using lisp with an not-quoted list.

BONUS VIDEO:

This is just lovely. I'm not American, and do not have a CS degree, so I feel like attending a place like this is a far dream. But happy to be able to enjoy it over the interwebs. Incredibly thankful to the giants of computing on whose shoulders we can stand https://www.youtube.com/watch?v=2Op3QLzMgSY&list=PLF4E3E1B72...

The standard notation for a cons cell with car "x" and cdr "y" is (x . y), not (x y). The latter is a list, equivalent of (x . (y . nil)).

So (1 2 3) is equivalent to (1 . (2 . (3 . nil)), not (1 (2 (3 nil))). The latter is a nested list, which is equivalent to (1 . ((2 . ((3 . (nil . nil)) . nil)) . nil))

To anyone who wants to play around with lisp, I recommend downloading the emacs text editor. Just open it, navigate around with the arrow keys. Type an s-expression, and place the point after the ")". Then type Ctrl-x Ctrl-e, and the expression will be sent thru read -> eval -> apply. Fun to just play around with.

(+ 1 2)_ ;; _ means the cursor, ";" means a comment