Skeem

Description

Skeem is a toy Lisp interpreter implemented in C, which can be seen as the next educational step from a lisp interpreter I wrote in Python.

This is by no means a production quality implementation, and there's a strong chance it never will be. The goal of the project was to learn some C, which I didn't know much of when I started (I often feel like I still don't...), and to make a simple interpreter that someone with a modest amount of background knowledge could understand in a weekend. Most of the inspiration was drawn from

• Dragon Book The reference for all things language implementation.
• K&R: The reference for learning the basics of C and how to think about the language.
• Writing Compilers and Interpreters (1st edition): This may not be the right book if you know nothing about language implementation, Dragon Book is the go to reference there. But, if you already know some theory, but not much C, then this will show you how to effectively use C in the context of langauge implementation. The tokenizer of Skeem was heavily inspired by the treatment in this book.
• TinyScheme: A relatively easy to understand Scheme implementation in C. I also recommend looking at MiniScheme, available on TinyScheme's download page, which is a bit simpler. The op codes for Skeem are mostly copied directly from MiniScheme.

Building

A Makefile has been included for easy building. Simply run make in the project directory and then execute skeem to run the interpreter.

Syntax

The syntax is some combination of Scheme and Common Lisp, leaning more toward Scheme. For example, basic function definition look like:

(define (square x)
  (* x x))

More complicated functions, however, borrow some syntax from Common Lisp:

(define (foo x &optional y)
  (if (null? y)
    x
    y))

and

(define (foo x &rest rest)
  (if (null? rest)
    x
    rest))

For optional arguments, the default is nil, someday I'd like to add user-supplies defaults.

Todo

• Fix known segfaults on some bad syntactic forms, e.g. (define (+ 1 2 3)).
• Implement cond - You could argue that it's not really necessary, but I'd probably disagree with you.
• Code cleanup - While trying to figure out good ways to do a few things (e.g. binding values to function parameters) the code got a bit wet. It's not super concerning, but I'd like to clean some of that up.
• Remove simplifying limitations - There are caps on things like string and identifier length. This was done to help speed up building the project, but should be removed eventually.
• Bignums - The interpreter eliminates tail calls, but uses C's builtin int type so we get overflow errors.
• Macros - Generally considered the Holy Grail of Lisp programming. I'll probably go for Common Lisp style macros.
• Tests - Write a suite of simple tests.
• Documentation - Most of the comments are just for my own benefit and I should thoroughly document any tricky spots.
• Bug squashing - Obviously, bugs need to be squashed as they appear.