McCarthyLispNotes.md

NOTES:

Lists

There is only one type of list and it is constructed using cons cells (aka 2-tuples):

(a,  b)

There is a special value NIL which can optionally be used to terminate a chain of linked lists:

(a, (b, NIL))

There are two form of syntactic sugar for lists:

(a . b) = (a, b)
(a  b)  = (a, (b, NIL))

A linked list with a NIL terminator:

(a b c d)

A linked list without a NIL terminator:

(a b c . d)

Another way of thinking about the relationship between Dotted and Regular lists is that:

(a b c d) == (a b c d . NIL) = (a . (b . (c . (d . NIL))))

The form (a . b) is the primitive form and is the actual AST representation of all lists. For any a, b, and c:

(a . (b . c)) = (a b . c)

The primitive form (a . b) is used for constructing various data structures including, but not limited to linked lists:

tree = (1 . ((2 . (NIL . NIL)) . (3 . (NIL . NIL))))

       	    1
	   / \
	  2   3
	 /\  / \
       NILNILNILNIL

Evaluation

The interpreter will throw an error if you enter any of the following:

> (1 2)
;The object 1 is not applicable.
> (1 . 2)
;Combination must be a proper list: (1 . 2)
> (1 . (2 . 3))
;Combination must be a proper list: (1 2 . 3)

This is because 1 is not a function. The list begins with the atomic value 1 and attempts to evaluate it as a function with the value 2 as an argument and fails.

Replacing the head of the list with a function:

> (+ . (1 . 2))
;Combination must be a proper list: (+ 1 . 2)

> (+ . (1 . (2 . ())))
;Value: 3

> (+ . (1 2))     
;Value: 3

> (+ 1 2)
;Value: 3

The second example above fails because (+) expects a proper list, meaning a NIL terminated linked list. The second and third versions are equivalent with and without list sugar on the arguments. The third example shows the fully sugared application of +.

Note: The evaluator treats (+ x y)`` as (cons '+ (cons 1 nil))`.

Quote

quote is a primitive function which returns the AST generated by its argument unevaluated. In other words, Quote cancels evaluation, but NOT parsing, for a particular sub form.

> '(1 . 2) 
;Value: (1 . 2)

> '(+ 1 2)
;Value: (+ 1 2)

All lisp code is data.

lisps actually have two levels of parsing, sorta like the difference between
parsing and type checking in Haskell. Syntactic parsing, done by the parser,
and semantic parsing, done by the evaluator. `(1 2)` is syntactically valid,
but semantically nonsense. Similarly for `(1 . 2)`

Quotation bypasses the evaluator entirely, so it’s only concerned about syntactic
validity. Strictly speaking quote doesn’t even check that. Because the parser
ensures everything is syntactically valid long before quote is involved.

In lisp the ast is made out of user-level data structures.

So quotation is a special case in the evaluator that makes it not evaluate
some ast and instead return it.

Label

label binds a lambda to a variable, and introduces the binding for a lambda in the scope of the lambda itself, so that it can be recursive. label hasn’t survived to modern lisps.

Scope

Scheme is lexically scoped with a global environment, similar to Haskell. Let and lambda introduce new scopes.

I don't think McCarthy Lisp has let, however, strictly speaking it is unnecessary. It’s just sugar for a lambda you immediately apply.

Typical let syntax:

(let (( x 1)
      ( y 2))
  (+ x y))

The variables x and y are scoped to the body of the let block. This means you cannot define the bindings recursively or in terms of each other.

let* and letrec get around these limitiations and can be defined in terms of let.

Lambda

lambda works similarly to quote in that it allows you to write your ast directly without evaluating with two differences:

1. A lambda is guarenteed to eventually be evaluated where a quote requires an explicit call of eval.

2. A quote is a 'complete' expression and can be evaluated at any time. A lambda has arguments that map to variables in the unevaluated ast and which need to be reduced by the application of arguments to the lambda. The arguments are bound variables in a scope around the code in the body of the lambda.

Undefined

McCarthy references non-total functions and undefined in his paper. It is strictly possible to write non-total functions in Lisp and it is up to the implementer to decide how to handle that. There are Lisp dialects with the notion of a special undefined value that is returned by these non-total functions and there are dialects that throw an error.