This is the basis of operational semantics, a way of capturing the meaning of a programming language by defining rules for how its programs execute on some kind of device.
This device is often an abstract machine: an imaginary, idealized computer that is designed for the specific purpose of explaining how the language’s programs will execute.
Different kinds of a programming language will usually require different designs of an abstract machine in order to neatly capture their runtime behavior.
”⁷ In order to construct Lisp, we first construct an imaginary machine on which it will operate.
Fig.
3 ST µA741 op-amp, or: imaginary Lisp machine3.
1.
Elementary functionsWe start by defining seven (The Magnificent Seven, in fact) elementary functions on s-expressions.
We call them elementary because we assume they exist on the abstract machine (just like we assume axioms to be true in some mathematical system).
A function on s-expression receives an s-expression and returns a new one.
By convention, we will refer to such functions as operators.
To keep our notation simple, we represent operators using atoms and lists — if an s-expression is a list, the first element is an operator, and remaining ones are arguments.
This means that functions on s-expressions are encoded using s-expressions themselves.
For example, the car operator expects one argument, and so its invocation will take the form:(car x)Atom “car" on its own refers to the function itself.
If car expected an argument which is a function (it doesn’t), we could write (car car).
atomatom is a very simple operator; it just returns t if the argument passed is an atom, and otherwise.
> (atom f)t> (atom foo)t> (atom atom)tquotequote is even simpler, it returns whatever was passed into it.
> (quote x)x> (quote (atom x))(atom x)> (quote (1 2 3 4 5))(1 2 3 4 5)It is crucial to understand how quote behaves and why is useful.
The second example — (quote (atom x)) —will reduce to the list containing atom and x.
(atom x) is not “evaluated” further (at this point we do not know what evaluation even is, but let us ignore that for a second).
In essence, quote is used to stop the evaluation — normally in(1 2 3), 1 would be assumed to be an operator but we want to treat the list as a regular list.
This is why we would use quote.
It is usually abbreviated with ', which gives us:> '(1 2 3)(1 2 3)Now that we have quote , we can go back to atom for one more example:> (atom '(foo bar baz))fIf the code would eventually be evaluated by some kind of program capable of doing that, quote would prevent evaluation of any s-expression given as its argument, which is very important when passing data around.
eqeq returns t if the values of its arguments are the same atom and f otherwise.
Some languages, such as Scheme, use eq?.
Clojure uses =.
carcar expects a list as an argument and returns its first element.
It's name, similar to cdr, is a historical legacy.
> (car '(1 2 3 4))1Certain languages, such as Clojure, rename car with something more intuitive, e.
g.
first.
The “car” and “cdr” names are derived from the machine architecture that Lisp was designed for and nowadays languages use more familiar names.
cdrcdr expects a list as an argument and returns its back without the first element.
For example:> (cdr '(1 2 3 4))(2 3 4)In Clojure, cdr behavior is provided viarest.
conscons (construct) takes two arguments, second of which must be a list, and prepends the list with the first argument:> (cons 1 '(2 3))(1 2 3)Why would we prepend to lists instead of appending them is a topic on its own.
In short, lists constructed as the head and rest are simpler to manipulate recursively, which is a huge benefit for a language such as Lisp.
For example, in Clojure, to check if a list contains an uneven number we could do:(check-if-uneven [list] (let [head & rest list] (if (not (even? head)) false check-if-uneven rest)))In let we are deconstructing the list to head and the rest — head & rest list, checking if head is uneven and recursively checking rest.
condWe will now translate conditional expressions into s-expressions using cond.
cond has the following form:(cond (p₁ e₁) .
(pₙ eₙ))The value is evaluated as follows.
We evaluate p expressions from left to right.
If any predicate evaluates to t, the value of the cond expression is taken to be the value of the corresponding expression e.
For example:> (cond (t 1) (f 2))1Moreover, because we evaluate from left to right:> (cond (t 1) (t 2))13.
2.
Denoting non-elementary functionsWith basic functionality in place, we define a general scheme for defining new functions on the abstract machine.
A function is expressed as(lambda (p₁ … pₙ) e)where p₁ -pₙ are called parameters and e is an expression.
If you ever tinkered with lambda calculus (or with lambdas/anonymous functions in pretty much any modern programming language), you will recognize this notation.
An expression whose first element is a lambda, i.
e.
, is of the form:— is called a function call and its value is computed as follows.
Each expression aᵢ is evaluated.
Then e is evaluated.
During the evaluation of e, the value of any occurrence of one of the pᵢ is the value of the corresponding aᵢ in the most recent function call.
Do you remember label notation?.We can now translate it to s-expression form and use it on our abstract machine to obtain a general method for defining functions.
The label s-expression will have the following form:(label name lambda)— where name is an atom representing the name of the function and lambda is the function body, also called to form.
Using label and the Magnificent Seven our expressive power is limitless.
For example, we can define the Boolean operator AND:(label and (lambda (x y) (cond (x (cond (y t) (t f))) (t f))))> (and t f)f> (and t t)t— or the operator NOT:(label not (lambda (x) (cond (x f) (t t))))> (not t)f> (not f)tWe can write functions to manipulate lists, Boolean expressions, pair elements, rewrite expressions, and so on.
For example:(not x) returns t if its argument returns f and t otherwise.
(pair x y) takes two lists of the same length and returns a third one containing two-element lists of corresponding elements in argument lits.
Nowadays we would more likely call this function zip.
(append x y) takes two lists and concatenates them.
(assoc x y) takes an atom x and a y of the form return by pair and returns a second-element from a pair in y whose first element is x.
This function emulates a lookup into a dictionary (alternatively called a hash table or associative array).
It is important to note that in Lisp, functions are first class objects — they’re data, just like numbers and strings.
Therefore, functions can be stored in variables, passed around as arguments, and so on.
The idea of a first-class function was pioneered by Lisp.
3.
3.
EvaluationMore importantly, however, we can write a function that takes arbitrary Lisp expression and returns its value:That is a bit of mouthful.
If you want a step by step description, which is beyond the scope of this article, I recommend reading Recursive Functions… by McCarthy³ and Paul Graham’s The Roots of Lisp², which take a thorough look at eval‘s inner-workings.
The important thing is this: eval is a Lisp interpreter, and thus, implements the language.
Any valid Lisp code can be passed to it for evaluation and we don’t need any other infrastructure.
With only seven functions and a bit of notation, we were able to implement the whole language and allow it to define new functions.
That’s neat and very elegant, but so what?.Now that we understand how Lisp operates, let’s step back and consider what it means.
If you’re curious how Lisp can be implemented in a few hundred lines of code, check out my toy Lisp implementation: Kite.
4.
Chemical X: HomoiconicityIn Lisp, as we saw, both code and data are represented in the same form: as s-expressions (forming trees) which are available for unrestricted mutation and execution.
This means that the Lisp code is first-class.
It can be explicitly constructed from scratch, passed around, modified and executed.
In other words, in Lisp everything is data.
A language in which the internal «representation matches the external representation is called homoiconic (from the Greek words homo meaning “the same” and icon meaning “representation”).
Other examples of a language with this property include Prolog (logic programming) and Julia (numerical analysis and computational science).
One of the immediate consequences of homoiconicity is that by using just a few functions: quote, atom, eq, car, cdr, cons, and cond, we can define eval, that fully implements the language, and with label and eval we can define any additional function we need.
In fact, it is a famous fact that the core of the Lisp can be written in about 20–30 lines of Lisp.
In (an unfair) comparison, the average person who writes a C compiler or interpreter requires about 20,000 lines of C to do so and must be moderately expert about compilers or interpreters (of course, we rely on meta-circularity in doing so, but that’s a topic for another post).
At this point, you may be asking yourself — what’s the big deal?The big deal, as it turns out, that when the representation of the program (code) is the same as the representation for that data, you can manipulate code like you would manipulate data.
This allows, for example, for syntactic extensibility, which is the ability to extend (or completely) change the syntax of the language.
For example, in a normal language, if you wished that you had the for-each construct, you would have to wait until creators of the language add it in the next version.
In Lisp, you can write a macro in a matter of minutes.
In many Lisp languages, program transformation is an explicit part of the evaluation strategy of the language.
Moreover, in Lisp, programs composed of expressions.
Lisp programs are trees of expressions, each of which returns a value.
At the time, this was a revolutionary idea, in contrast to languages such as Fortran which distinguish between expressions and statements.
This was largely dictated by the limitations of the hardware available in the late 1950s.
Finally, what McCarthy discovered is not just a programming language but a very elegant model of computation, just a notch above lambda calculus.
We can say that Lisp was discovered, and not invented, because McCarthy built it from axioms so fundamental that it would be very hard to make an argument for the otherwise.
Core Lisp corresponds to an untyped, call-by-value lambda calculus extended with constants.
The big difference is that lambda calculus doesn’t contain any non-functional data.
In lambda calculus, everything is a function, even a number (if you’re curious how this is achieved see Church encodings or Mogensen-Scott encodings).
Lisp, on the other hand, operates on atoms and numbers (hence, constants).
This is most likely what makes Lisp readable to mortal humans — a property that lambda calculus lacks.
The adherence to mathematically sound principles of computation allows Lisp to reap the benefits in the form of simple semantics, clarity, consistency, and other nice things such as referential transparency (original Lisp formulation is completely value-based).
In contrast, almost all imperative languages are “just” tools (sometimes very good tools nonetheless) with undefined formal semantics, which makes reasoning about them rigorously very hard or almost impossible.
Thank you for reading.
Please check out the references and maybe my other stuff.
If you have any questions, please feel free to send me an e-mail at hi@iwoherka.
eu or leave a comment.
ReferencesBYTE Magazine, August 1979The Roots of LispRecursive functions of symbolic expressions and their computation by machine, Part IHow Lisp Became God’s Own Programming LanguageHomoiconic LanguagesOn LispUnderstanding ComputationWhat Made Lisp Different.