Metacircular evaluator

Every culture have their own rites of passage. Recently I passed one of those, as I wrote my own lisp interpreter. I chose to write on with Hy, as that is a language I currently enjoy most. I also found certain satisfaction in writing an interpreter with a language that closely resembles the language the interpreter is supposed to be working with. There are many lisps in the world and this one isn’t particularly special. But the goal wasn’t about creating something spectacular. The goal was to write a complete interpreter, learn while doing so and appreciate the elegance of the eval-apply – loop. I mostly following the excellent SICP lecture from 1986 by Gerald J. Sussman. There’s a little bit code here and there (most notably the reader part) that I crafted, instead of following what he was explaining.

Normally, people under 40 and who don’t have several children are advised to be careful. If they’re really worried, they should leave. Because there’s a certain amount of mysticism that will appear here which may be disturbing and cause trouble in your minds.

Even when I was working with Hy, I wanted to write fairly substantial amount of code by myself. This meant that I would’t be using HySymbol, HyExpression and such, but rolling out my own (not that they’re particularly hard). I also wanted to write my own reading and parsing routines and not use existing ones (funnily these were the hardest part about the program).

Now, there are countless of articles, blog posts and tutorials about writing a lisp interpreter and this one isn’t going to be particularly special (maybe the only redeeming feature it has is usage of Hy). And the excellent lecture by Sussman I mentioned earlier explains things in crisp clarity that I’m not able to achieve. However, if you are after a travel blog of some sort about the journey I had while writing the interpreter, read on.

Like the lecture, I started by writing core of eval function (although I called it to eval- in order not to shadow eval that Hy already had). This is just a simple case analysis that detects what kind of thing it’s evaluating and returns correct value based on that. In case of the evaluated expression is a function call, eval calls apply to handle it. In turn, apply might need to call eval in order to evaluate some more expressions and thus they form a loop that keeps going until all expressions have been reduced to a value.

Originally I made a mistake here as I tried using symbol?, number? and so forth from Hy. This of course would have required me to use HySymbol, HyExpressions and such, which I wanted to avoid. So I rolled out my own versions for Symbol, Expression, Boolean and utility functions to check for their type. Since I was using classes and objects, checking if something is an expression was simple as checking for the type of the object (which I don’t often do).

At this point I was writing super-simple tests that checked if evaluating 5 would give me 5 and so on. This of course also meant that I was construting objects for internal representation for my tests. For most parts this was just fine, but nested calls that I used testing apply- function were a bit of pain to get correct:

(defn test-evaluate-nested-form []
  "evaluating (+ 2 (+ 5 4 3) (- 2 4) (+ (+ 1 2) 3)) results 18"
  (assert (= (eval-
              (Expression [(PrimitiveOperation "+")
                           2
                           (Expression [(PrimitiveOperation "+")
                                        5 4 3])
                           (Expression [(PrimitiveOperation "-")
                                        2 4])
                           (Expression [(PrimitiveOperation "+")
                                        (Expression [(PrimitiveOperation "+")
                                                     1 2])
                                        3])])
              {})
             18)))

I didn’t want to use archimedes or hamcrest for testing, since goal was to keep dependencies to minimum. This meant that I was stuck with simple assert and no fancy error reporting (I could have rolled out something simple, but useful, but that wasn’t the focus of the excercise). When code failed, I had to resort to staring it sternly, until it yielded and revealed why it wasn’t working.

Alongside with the eval I was working with apply. The first version of apply was super simple (again, I seem to love that expression), since it only needed to handle primitive operations (those defined in the terms of the host language) and there was no environment to worry about. I just simply called the respective Hy function and passed required arguments. evalapply – loop didn’t take that long to write and get working to a sufficient degree. Where I really had to scratch my head was reading and parsing a string.

Hy uses rply for tackling this problem. I wanted to do it by hand, so had to roll out my own implementation. Apocrita doesn’t have reader macros or any shorthand operators, which made things easier. All the code was either a symbol or expression consisting of symbols and more expressions.

First part of the task was to detect where symbols and expressions were and split one long string into array of strings. This is exactly what group-elements function does by tracking parentheses and code in between them. After the string has been grouped into easier to handle form, tokenize function will take over and start building expressions and symbols by tracking opening and closing parentheses. This is also the part of the code that is responsible for detecting numbers, boolean literals and primitive operations. In the unknown future I’m planning on treating primitive operations in the same way as any other symbol, thus simplifying the code a bit.

At this point I had fully functional lisp, albeit without a way to actually use it. So next logical step was to implement a simple repl that reads user input, evaluates it and prints out the answer. Here I had to count parentheses and concatenate subsequent inputs from user until amount of open and closed ones matches. This allowed simple multi-line input.

Rest of the journey was just filling in details: how to define variables, how scoping would work and how to define and interpret functions. Most of this was explained really well by Sussman, so I didn’t have much trouble implementing it (and fast feedback loop helped quite a bit too).

2016-04-06_00001

There are some improvements that I would like to incorporate to code still at later point. For example, error reporting is quite inadequate and most error cases just give “error:” text, which isn’t quite helpful. Since the code is interpreted and I have access to source, it wouldn’t be too difficult to actually print out the expression that was being executed when the error occurred.

A bit fancier improvements would be currying, memoization and tail call optimization. All are rather well researched features and internet should have plenty of material about them.

Probably the most coolest moment was when I got factorial working. It’s a short program, just couple of lines, but it does demonstrate things like defining and calling function and scope management.

=> (define factorial
...   (lambda (n)
...     (cond ((= n 0) 1)
...           (#t (* n (factorial (- n 1)))))))
<closure>
=> (factorial 4)
24

At this point I knew I had a real programming language at my hands, that could be used to perform computations. However, it could do things like higher order functions and passing them as parameters to other functions. The machinery behind all this was small, almost tiny and yet it could do all these complicated computations.

Code of the interpreter is a github. Funny little detail, name Hy comes from Hymenoptera and Apocrita is a suborder of it.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s