Lispy is a language that was invented to answer one question. How do I write my own programming language? My journey to the solution started with the meta-circular interpreter in SICP. I played with it and tweaked it a bit, but it seemed to me too much like cheating. I searched the internet and read everything I could find (most of it I didn’t understand at the time). Finally I found a series called Scheme from Scratch which details writing a Scheme interpreter in C. Scheme from Scratch is written in the style of An Incremental Approach to Compiler Construction, where you have a working interpreter at each stage.
To force myself to come up with my own implementations, instead of just blindly reading through the series, I decided to write a version of Scheme that has some Python influences. I wrote generic functions and list/vector/string comprehensions and I hooked up the Hans Boehm garbage collector to stop it from crashing all the time.
Writing Lispy in C was a fun, challenging and rewarding experience. However as I began to answer my questions about how basic language features could be implemented, I began to have new questions. I started wondering about sequence abstractions, parallel execution, optimization and code generation. As my questions got more in depth I began to realize that C was not the easiest language for me to solve them in.
That leads us to Chicken. Since Lispy is a language that is based on Scheme, why not write it in Scheme? The advantages are obvious, we get a full blown reader (that we now only have to modify), compilation to C and tons of other features like macros. Most of Lispy is simply syntax or functional extensions of Scheme and map directly into Scheme code.
This series will build Lispy incrementally. Each stage of this process will generate a fully working, if not featureful, language. Each stage we implement will be the simplest code possible to implement a feature. Error handling or efficiency will not be a concern (though may be taken into account if absolutely necessary). The interpreter that we will build borrows a lot from the meta-circular evaluator in The Structure and Interpretation of Computer Programs.
You will need to install Chicken to follow along (this may work on other Schemes but that is not an objective for this series), if you’re running a recent version of Ubuntu you can get a fairly recent version of Chicken with apt-get or you can download it here. This series will build an interpreter that is similar to this meta-circular evaluator that I previously wrote.
A Simple Scheme Meta-Circular Evaluator
The first thing we’re going to do is implement a REPL, also called an interpreter. REPL stands for Read, Eval, Print Loop and that’s just what it does. First the repl reads in an expression from stdin, then it evaluates the expression and prints the return value to stdout. When it is finished with these tasks it loops and does it all again. To get something up and running so we can play with it, let’s make a simple Chicken repl.
Most repls will print an indicator before the input line (>>> in Python, #;1> in Chicken). Lispy will instead print an indicator before the output. This makes sense for now because it lets us copy and paste interpreter sessions. This will make our lives easier for now and is trivial to swap later.
(define (repl) (define input (read)) (print ";===>" (eval input)) (repl))
(repl) 42 ;===> 42 "hi" ;===> hi (+ 2 2) ;===> 4
Since Lispy is very close to Scheme in syntax we can continue to use the default (read) function for now. The thing that we’re most interested in at the moment is the eval function and we need to implement that in order to start implementing everything else.
Our first version of eval will be as simple as possible. We’ll simply echo the input back to the screen. Our simple reader already understands basic Scheme data types such as integers, strings and lists.
(define (lispy-eval expr) expr) (define (repl) (define input (read)) (print ";===>" (lispy-eval input)) (repl))
(repl) 42 ;===> 42 "hi" ;===> hi (+ 2 2) ;===> (+ 2 2)
A Language of Numbers
The simplest language is a language of numbers. Numbers are self-evaluating and we’re going to use native Chicken data types wherever possible to simplify implementation, so if the expression is a number we’ll just return it for now.
(define (lispy-eval expr) (cond ((number? expr) expr) (else "Not implemented"))) (define (repl) (define input (read)) (print ";===>" (lispy-eval input)) (repl))
(repl) 42 ;===> 42 "hi" ;===> Not implemented
A Language of Self-Evaluating Values
Continuing with our language of self-evaluating values is just as simple. Booleans, strings and characters are also self-evaluating so we’ll add them now. More complex data structures like hash tables are also self evaluating, however we’ll leave them for later.
To get something up and running quickly we’ll stick with the Scheme versions of these data types. Eventually we will modify the boolean and string data types and will probably remove the character type completely.
(define (self-evaluating? expr) (or (number? expr) (string? expr) (char? expr) (boolean? expr))) (define (lispy-eval expr) (cond ((self-evaluating? expr) expr) (else "Not implemented"))) (define (repl) (define input (read)) (print ";===>" (lispy-eval input)) (repl))
(repl) 42 ;===> 42 "hi" ;===> hi #t ;===> #t
The first stage of our language is complete. We now have a functional language of self-evaluating values. Though one could argue exactly how functional it really is. The next step along our path will be to introduce symbols and implement assignment.