I’ve been working fervently the past 15 days¹ on my first language and interpreter, a dialect of lisp I’ve come to refer to as MsLisp. I had a few goals starting, some of which are still in progress.

What I wanted

• I wanted an embeddable lisp that could run on tiny specialized hardware.
• A minimal interpreter with most implementation written in lisp itself (for portability).
• Written in portable C++.

What I have

• A working dialect of lisp with a minimal interpreter.
• A small standard library with basic functionality.
• Written in C#.

I plan on reading up some more on some lisp functionality and fixing up some design changes before porting the code to C++ or start working on any other versions of it. Most of MsLisp is inspired by Scheme with some of parts stolen from the CLisp implementation of Common Lisp. I’ve started working through The Little Schemer for some less dry insights into Scheme.

Features²

First Class Macros.

Lisp macros are unlike macros in other languages. I can best describe macros as functions that return code as data (which I understand still isn’t clear).

In order to really understand macros (and the implications of macros, without which you don’t really actually understand macros), you need to understand how lisp code is interpreted. The process can be broken down into three parts.

1. Parsing. Which can be broken down into two sub-steps,
   1. Lexing (tokenizing).
   2. Parsing the tokens into lisp values (numbers, strings, expressions, symbols…).
2. Expanding. This is the step where macros are evaluated and expand into the code they return.
3. Evaluating. This is your normal evaluation step where function and variable execution and manipulation happen.

Let me give some code examples.

(define pair
  (lambda (x y)
    (cons x (cons y '()))))

That’s a completely valid function in lisp that takes two arguments and adds them into an empty list, which is then returned.

Protip: Whatever statement is last evaluated is what is returned. Every function at least returns NIL.

Now lets define a macro.

(define let
  (macro
    (lambda (var-value body)
      `((lambda (,(car var-value))
         ,body) ,(cadr var-value)))))

Wait a second. That looks a lot like a function. Yep, macros are alot like functions, except for when they are evaluated.

Protip: Noticed in the first example how the lambda function was just set to the variable pair? That makes it a First class function, which can be passed to other functions just like any other variable. In MsLisp, macros just wrap a lambda function (see the macro keyword before the lambda keyword?) to let the interpreter know that this particular function is special. Therefore, macros are First class macros and can be passed to other functions just like their function counterparts. Most lisp macro implementations are not implemented this way, although I find understanding and mostly implementing macros in the interpreter easier this way compared to the standard implemenations.

Now we can implement a macro to make it less verbose to write normal lambda functions

(define defun
  (macro
    (lambda (name params body)
      `(define ,name
         (lambda ,params
            ,body)))))

(defun pair (x y)
  (cons x (cons y '())))

See what we did there? We wrote the macro defun which we use to rewrite our pair function with. When the interpreter see’s this, it’ll replace (defun pair …) with all the code returned from the defun macro. After expansion, both pair functions, old and new, result in the same code. Pretty cool huh?!

The implication of macros really clicked for me when write the + macro. MsLisp has a builtin function called add, which adds exactly two arguments. Not one, not three, but exactly two like so (add 1 2). But what if we wanted to do this (add 1 2 3 4)? Well we can! But we’ll have to write a macro.

Note: I’ve gone ahead and replaced define **name** (macro (lambda (args))) with (defmacro **name** (args)).

(defmacro + (&rest x)
  ((Y
    (lambda (f)
      (lambda (x)
        (if (= (length x) 1)
           (car x)
           (f (cons `(add ,@(first-pair x)) (cddr x)))))))
   x))

There are a few functions we haven’t defined yet in that function such as Y, the recursive y-combinator, first-pair, which returns the first two elements of a list, and cddr, which skips the first two elements of a list and returns the remainder.

Our new + macro expands (+ 1 2 3 4) into (add (add (add 1 2) 3) 4).

C# Reflection in lisp.

This isn’t so much of a feature that I wanted, but just something that I though was neat and gives MsLisp a lot more functionality. Since C# can reflect on itself and know what methods it has, when can dynamically invoke these methods and create new instances of objects by calling methods like the following.

(new "Mslisp.Lexical.Parser" *args-if-we-need-any*)

(invoke-static (get-type "System" "Console") "Write" "string arg to print to console")