Notes on Lisp

This is the first in a series of posts covering Lisp. What have I done so far?

• Implemented a basic Lisp interpreter in JS, supporting function calls and recursion.
• Read the first chapter of Structure and Interpretation of Computer Programs (SICP), the “killer textbook” of Lisp.

Why learn Lisp?

There’s this old adage that goes -

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp. – Greenspun’s tenth rule

Lisp transcends the utilitarian criteria used to judge other languages, because the median programmer has never used Lisp to build anything practical and probably never will, yet the reverence for Lisp runs so deep that Lisp is often ascribed mystical properties.

Lisp learnings

Operators and operands. Implementing the meta-circular evaluator. Eval/apply.

The list data type, car and cdr as indexing. Building a range function a la Python out of simple car, cons and recursion. How is this related to Church calculus and Church encoding.

Code is data. I understood this conceptually, but it was difficult to reason about. Take (write ((lambda (x) (car x)) '((1 2) 3))) as an example. The simple quote ' makes this expression work.

Implementing a malleable language syntax using macros. https://stackoverflow.com/questions/267862/what-makes-lisp-macros-so-special

Implementing symbolic computation. eg. differentiate equations using Lisp.

Explicit vs. implicit recursion.

http://www.paulgraham.com/diff.html

Recursion

https://mvanier.livejournal.com/2897.html Implementing recursion without variable rebinding using the Y Combinator:

• Recursion using label involves adding new objects to the environment.
• Lisp has strong roots in lambda calculus. Abstraction/application via the A-conversion, eta and B-reduction laws.
• The Y-Combinator is a combinator, meaning in lambda calculus, it is a function with no free variables. The Y-Combinator expands a function to apply itself recursively.
• The Y-Combinator doesn’t eliminate call stack growth, unless it’s used with TCO. It is a helpful way of expressing recursion using functions alone. It’s easy to imagine the combinator as a factory function. You define your function, extracting the recursive out into a variable. By giving it the Y combinator, you reify it into recursive form, without changing the inner body of the function. This post has some great explanation using JavaScript.

The λ-calculus, the language in which the Y combinator is typically expressed, is a programming language which contains only anonymous functions, function applications and variable references.

https://stackoverflow.com/questions/93526/what-is-a-y-combinator#:~:text=The Y combinator is a,so it can call itself.

Observations on the Lisp type system

Let’s implement a basic proof-of-work algorithm in Lisp.

The Lisp package manager is a script I run:

(load "~/.quicklisp/setup.lisp")
(map nil 'ql:quickload '(:ironclad))

The package is lazy-loaded if it’s not already downloaded.

(let
    ((nonce (make-array 2 ; len=2
        :element-type '(unsigned-byte 8)
        :initial-element 0)))
(ironclad:digest-sequence :sha256 nonce)

A couple observations:

1. We call make-array to create an array of unsigned bytes.
2. make-array is given the element-type of (unsigned-byte 8).

Looking at the LispWorks doc for unsigned-byte, you begin to see how a type system is implemented in Lisp. It’s expressions all the way down -

The atomic type specifier unsigned-byte denotes the same type as is denoted by the type specifier (integer 0 *)

Let’s examine the integer type specifier. (* is simply a wildcard expression for types).

An integer is a mathematical integer. There is no limit on the magnitude of an integer. integer [lower-limit [upper-limit]]

Now, integers are self-evaluating expressions in Lisp, which is most akin to a primitive type in other OO languages. When the eval algorithm encounters an integer, it simply returns itself. This is the same as for strings, and the booleans t and nil.

One thing I love is that you don’t need bignumber wrapper libraries in Lisp. (expt 2 256) will evaluate to the integer $2^256$. Lisp has native support for arbitrary-precision arithmetic, which includes ratios and big numbers.

The earliest widespread software implementation of arbitrary-precision arithmetic was probably that in Maclisp.

The type specifier is also an expression. Which leads to some beautifully axiomatic descriptions of common types:

• Unsigned bytes are represented with a lower-limit of 0.
• The type (integer 0 1) is a bit, (integer 0 7) is a byte.
• Thus an unsigned byte can be defined as (deftype unsigned-byte (integer 0 7)).

So, how are byte arrays implemented? In a pure interpretation of Lisp’s design, a byte array can be implemented as a linked list of unsigned-byte objects. Each item is a cons cell consisting of two pointers, the car to the unsigned-byte object and the cdr to the next cons cell in the linked list (or nil). However this is clearly space-inefficient for fixed-size arrays, where we would usually allocate contiguous blocks of memory. Furthermore, we’d be unable to make use of architecture-specific features like SIMD. This aspect of computer science is called the duality of computational artifacts, and is very interesting for those with a insatiable mind [^2].

In mathematics, once the abstraction is established, the physical device is left behind.

[…] computational abstraction must leave behind an implementation trace. Information is hidden but not destroyed.

The type of an array that is not displaced to another array, has no fill pointer, and is not expressly adjustable is a subtype of type simple-array. The concept of a simple array exists to allow the implementation to use a specialized representation and to allow the user to declare that certain values will always be simple arrays.

One thing I’ve noticed with Lisp is the clarity of specification and implementation. Reading the documentation to understand make-array, simple-array and so on, I came across the specification of displaced and adjustable arrays:

• A displaced array is an array which “has no storage of its own, but which is instead indirected to the storage of another array, called its target, at a specified offset”.
• An adjustable array can have its dimensions and elements changed. Notably, if the array is displaced, you can change the specified offset into the target array (like a cursor).

Using space-saving measures like pointers or virtualized tables is commonplace, but it requires additional abstractions on top of the base type. In Lisp, you can build an array out of other arrays with negligible abstraction cost ¹, using the same functions you use to build a simple array. In fact, that’s the definition of the simple-array type - one which is akin to your normal uint32_t x[32].

So these are a couple of learnings from reading about Lisp’s type system so far.

Building a simple hashcash proof-of-work in Lisp.

Reader algorithm and malleable language

Make a Lisp visualises all aspects of building a Lisp. The reader algorithm.

http://www.paulgraham.com/diff.html

The whole language always available. There is no real distinction between read-time, compile-time, and runtime. You can compile or run code while reading, read or run code while compiling, and read or compile code at runtime.

Running code at read-time lets users reprogram Lisp’s syntax; running code at compile-time is the basis of macros; compiling at runtime is the basis of Lisp’s use as an extension language in programs like Emacs; and reading at runtime enables programs to communicate using s-expressions, an idea recently reinvented as XML.

Continuations and Tail Call Optimisation

Convert recursive procedures (as opposed to recursive processes) into tail call form, such that they can be run as continuations.

What’s a continuation? How is it similar to a callback?

http://blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html

https://stackoverflow.com/questions/14019341/whats-the-difference-between-a-continuation-and-a-callback

https://journal.stuffwithstuff.com/2015/02/01/what-color-is-your-function/

Reforming recursive procedures as iterative functions with accumulators. Recursive processes.

^[1]: I had a brief read into how this works. Objects in SBCL Lisp are tagged with lowtag (4 bits) and a widetag. There’s some interesting reading in the SBCL Internals - 6.1 Type tags as well as this article.

^[2]: Simply put, there is a difference between specification and implementation of computational objects. The byte array here is specified as a collection of unsigned-byte items, whereas the implementation could be a cons linked list, a C-style array, etc.