World, say hello to Kimi!

In week 7 of my batch here at the Recurse Center, I started (and finished) a new project: creating and interpreting a programming language. My goal for this language was less to build a language you can actually code in, and more to simply learn about programming languages and interpreters, as this is something I find really interesting but have almost no experience with.

What is Kimi?

Kimi is a little toy language with only the most basic features a small, elegant language needs, and nothing more. The name “Kimi” stands for Keep It MInimal, which is exactly what I tried to do with this project.

Why did I build Kimi?

A few weeks into my batch at the Recurse Center, resident Prabhakar Ragde gave a talk called “Small, Elegant, Practical: The benefits of a minimal approach”, in which he laid out a minimal set of features (see below) for a small, elegant programming language. It was interesting to know that a programming language doesn’t in principle need to have a huge set of features, like most of the major languages do.

I didn’t know much about programming languages before coming to RC, and although I had a vague sense of what interpreters/compilers do, I didn’t really know what was going on under the hood. So, with some inspiration from Prabhakar’s talk, and some encouragement from RC facilitator John Workman, I decided to write a little interpreter for such a minimal language myself.

How did I build Kimi?

In crafting the language, I tried to stick as closely as possible to minimal set of features laid out by Prabhakar:

• Lambda expressions
• Some useful built-in functions (e.g. arithmetic)
• Function application
• Variable definition
• Conditional evaluation
• Lists

To write the interpreter, I loosely followed two tutorials:

• the Programming language project outlined by this week’s RC resident, Marijn Haverbeke, in his excellent and fun book Eloquent Javascript. Marijn himself also provided invaluable assistance by pair-programming with me on some components of the interpreter.
• Peter Norvig’s tutorial (How to Write a (Lisp) Interpreter (in Python)).

What does Kimi code look like?

Here’s a sample Kimi program, factorial.kimi, which defines a recursive function to compute the factorial of a given number, and then applies that function to the number 3:

(do
    (define fact
        (lambda n
            (if (= n 0) 1
                (* n (fact (- n 1))))))
    (fact 3)
)

Running this program in the Kimi interpreter produces the result 6.

Several other examples are available in the samples/ directory of the Kimi repo.

What did I learn from this project?

Before starting work on Kimi, I had a very shallow understanding of what an interpreter actually does. Through this project, I learned how an interpreter:

• Tokenizes the raw source code into distinct pieces
• Parses those tokens into an abstract syntax tree representing the structure of the program
• Evaluates the expressions in that tree recursively
• Creates and keeps track of a hierarchy of environments, i.e. contexts in which expressions are evaluated
• Makes use of special syntactic forms (e.g. if statements, lambda expressions, and imperative do blocks) to decide how to evaluate certain expressions

This project was also a great opportunity to practice Test-Driven Development; before implementing a given feature (e.g. a built-in function like +), I wrote tests using Python’s unittest to capture the desired behavior, watched them fail, and then wrote the code that made them pass. I loved the structure and gratification I got from TDD on this project - seeing those tests pass is so rewarding! - so I’ll definitely keep using this development strategy in the future.

What’s next for Kimi?

For the time being, I’m satisfied with Kimi’s feature set and will be switching focus to other projects. But in the unlikely case of a future time and energy surplus, I’ll also try to implement some nice-to-have features, such as:

• Built-in string functions (e.g. concat or find)
• Simple I/O (e.g. print)
• Macros
• Maps
• Arbitrary structures using S-expressions (a la XML or JavaScript objects)