myLisp Interpreter 0: What is Lisp?
March 7, 2020 | 5 min
This is the first part of a series of articles that I'll be writing to document my progress on building a interpreter for a Lisp-like language.
I've been interested in learning different programming languages for a while now, I've read the first chapters of Haskell and Lisp books recently and the one that hooked me on was Land of lisp. Lisp's simplicity really struck me: from very simple building blocks you can create anything in such an elegant and simple way.
What is myLisp
myLisp is a lisp-like language, the main goal of it is to be implemented in
the most simple and educational way possible.
So, what is lisp?
A bit of history
Lisp is a programming language that was invented in the late 50's by John McCarthy, in 1960 he published a paper where he defined the language and wrote a Lisp interpreter in Lisp! It's crazy to think that you can write a interpreter for Lisp in Lisp in such an small and beautiful way using only simple operations, it really shows its elegance and power. There's a more approachable paper by Paul Graham in which he explains step by step how Lisp was defined in McCarthy's paper, here's an excerpt from it:
"I wrote this article to help myself understand exactly what McCarthy discovered. You don't need to know this stuff to program in Lisp, but it should be helpful to anyone who wants to understand the essence of Lisp - both in the sense of its origins and its semantic core. The fact that it has such a core is one of Lisp's distinguishing features (...)"
What is it?
The building blocks of Lisp are cons cells. It is a structure that holds two
values, head and tail or as Lisp calls them:
CDR. Each of them can
either point to another cons cell or to atoms. Atoms are anything that can't be
divided into smaller parts (as we can with cons cells which can be divided into
two parts) such as:
"I'm a string".
Bellow you can see some examples on how cons cells can work together:
Example 1: List
Example 2: Nested list
NIL is a special object which denotes the end of a list. As you can see from the first example we've just created a list, which is the single most important data structure in Lisp. That's where it's name comes from: LISt Processor.
Now that we know the basic concepts of the language we are going to learn how to represent them in Lisp code.
S-Expressions are how Lisp represent its code and data. Code and data being represented in the same way is a very important concept to Lisp, it is called homoiconicity. They can be in the form of atoms or other s-expressions enclosed by parenthesis and separated by a whitespace.
Lets see how the examples 1 and 2 can be represented using S-Expressions.
(42 69 613)
(c-major (c e g))
Lisp can look at these two expressions as code or as data. By default Lisp reads
them as if they were code. The first element of an expression, (it's
is interpreted as a function, so
(f a b) has the same meaning as
have in C, for example.
QUOTE: Receives an expression as its input and returns it, without evaluating it.
Let's try these two functions, let's say that I want to print the list from the
first example. If I call
(PRINT (32 69 613)) it will throw an error because
Lisp will try to call the function
613 as its arguments.
But if I call
(PRINT (QUOTE (32 69 613))) it will work as I intended,
(32 69 613) and then
a way to convert code into data.
band returns a cons cell with
aas it's first part and
bas the second.
CAR: Takes a cons cell and returns it's first part.
CDR: Takes a cons cell and returns it's second part.
CADR: Same as
CDDR: Same as
(CONS (QUOTE A) (CONS (QUOTE B) NIL))returns
- Expression to create the nested list from the second image:
(CONS (QUOTE C-MAJOR) (CONS (CONS (QUOTE C) (CONS (QUOTE E) (CONS (QUOTE G) NIL))) NIL))which returns
(C-MAJOR (C E G)).
Sidenote: You don't have to declare things this way, I just made this way for
illustration purposes, in Lisp you could also just do
(QUOTE (C-MAJOR (C E G))).
There are other important functions that we'll be discussing later, but for the next article they are enough.