The Very Essence of Programming, in Lisp
This amazing talk by William Byrd on YouTube entitled “The Most Beautiful Program Ever Written” explores implementing a Lisp interpreter in Lisp, step-by-step.
This simple but profound exercise explores how the line between code and data can be blurred: code is nothing more than computation described as data.
In the seminal 1960 paper by John McCarty, “Recursive Functions of Symbolic Expressions and Their Computation by Machine”, the author builds upon Lambda Calculus, which boils down to three singular concepts:
- Variables, which is a named placeholder for a value.
- Abstraction, also called lambdas, which describe how variables, abstractions and applications may be composed into some computation.
- Application, which is binding a value to input variables of an abstraction.
For example, if we call x a variable name.
We may come up with an abstraction which is increment defined as increment(x) = x + 1. (We'd need to have defined what + and 1 are beforehand.)
Then, an application would be to take a value for x, such as x = 5, then: increment(5) = 5 + 1 = 6.
Lisp takes a slightly different approach to syntax and representation from what we're used to, always putting the abstraction name as the first element of the list (instead of infix operators), as seen below:
(define (increment x) (+ x 1)) # increment is now an abstraction (increment 5) # evaluates to (+ 5 1), which is 6
It's also worth checking out the Computerphile video diving into Lambda Calculus in an approachable manner, which is available at YouTube. It draws an interesting parallel with DNA, which analogously to to how code describe how computers ought to compute, is genetic code that encodes how proteins ought to be put together.