I've been reading the SICP classic and learning a religious symbol of hacker culture – Lisp. A quote to start us off-

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.

What does this mean? What is it like using Lisp, what makes the experience so elegant and wholesome to some?

The challenge.

Let's implement a basic proof-of-work algorithm in Lisp. Proof-of-work is a probabilistic algorithm to generate a proof of burning a certain amount of CPU power. It is based on hashcash, but with an adjustable difficulty. It underpins the Bitcoin network's consensus.

Getting setup.

First of all, we'll need to compute hashes using SHA256. I found a package, ironclad, which does this. How do we install the package? There are a couple of package managers, I settle on one called QuickLisp for obvious reasons. This is how you import a package:

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

Did I install it? Is this package.json? Nope, it's just a function call inside my Lisp script. The package is lazy-loaded at run time if it's not already downloaded. Code is data? Well, package management is code.

Okay, great, let's get to it. How do I compute the SHA256 digest? Reading the ironclad docs and some StackOverflow posts, it looks like I can call (ironclad:digest-sequence :sha256 *buffer*) with a buffer object. Keep in mind, I know nothing of the Lisp type system beyond the basic types right now - numbers, symbols, lists and functions (fun fact: Lisp was the first language to have functions as first-class data types).

What type is the buffer?

If buffer is provided, it must be a (simple-array (unsigned-byte 8) (*))

Ah, a new type! I look quizically at the simple adjective...haven't arrays always been simple (conceptually speaking)? Secondly, how do we create a simple-array?

First thing you need to know about Lisp, is that the first item in a list is always a function application. So I try to call simple-array -

* (simple-array 2)

; in: SIMPLE-ARRAY 2
;     (SIMPLE-ARRAY 2)
;
; caught WARNING:
;   The function SIMPLE-ARRAY is undefined, and its name is reserved by ANSI CL so
;   that even if it were defined later, the code doing so would not be portable.
;
; compilation unit finished
;   Undefined function:
;     SIMPLE-ARRAY
;   caught 1 WARNING condition

Learning about type specs.

Hmm, undefined? Is simple-array not a function? Nope, it's a type. Here's what I've learnt so far:

  • there are primitive types in Lisp: integers, symbols, functions, lists, arrays.
  • you can test the type using a type predicate, (typep obj typespec).
  • users can define their own types using deftype. These are called composite types.

So for example, I went off to define my own type: millenial. Millenials are roughly the age group born after 1997. Nowdays, we also have zoomers, but let's ignore them. This is our millenial type:

(defun age-test (yyyy) 
  (> yyyy 1997))

(deftype millenial () 
  `(and 
        integer 
        (satisfies age-test)))

And this is testing the type predicate:

(typep  1990  'millenial) ; nil
(typep  2000  'millenial) ; T
(typep "2000" 'millenial) ; error, it's a string!

Woohoo! It runs our custom function age-test and fails for anything that isn't a number. But why does millenial not require any arguments, and why do we need to use satisfies to call age-test? The answer is, that we are defining type specifications, not the type predicates themselves. The specification is then transformed into predicate functions, according to the Lisp implementation. I found a great post on Typed Lisp which explains this in greater detail. One other interesting thing to note - Lisp types are not designed to support recursion, which is at odds with its ubiquity elsewhere.

Discovering Lisp's type hierarchy.

We understand some aspects of how types are defined, now let's touch upon some more interesting aspects of the type hierarchy.

The type specifiers are great in Lisp. Let's examine the integer specifier for example:

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

Very close to a formal definition, very far from an OO API. How would we define an unsigned byte? Remember, bytes are just numbers. A single byte digit represents $ 2^8 $ bits of information, or the numeric range, $0-255$. Representing this in code, it might look like (deftype byte '(integer 0 255)). And in fact, that's pretty close to how Lisp defines it! Another elegant tidbit - the type (integer 0 1) is called a bit.

I remember this one profound realisation I had when I was studying RSA as a teenager, trying to understand how public-key encryption worked. At a certain point, realising that the payload was in fact, just a number, that could be multiplied like any other, blew my little adolescent mind. Lisp exposes this fact as a core axiom of its type system. Now, this appears as a beautiful syntactic expression, although doesn't necessarily reflect a performant implementation, does it?

Summary.

This was part one of writing about playing with Lisp. Some things I discovered:

  • A lazy-loading package manager that is defined all in code. Cool.
  • An expressive type system using deftype and typespecs.
  • An elegant type hierarchy for numbers and data.

In the next post, I'll be implementing the proof-of-work algorithm. I'll also dig into some interesting elegance of composing Lisp arrays and how data type specialization works too.