home mail me! RSS (2.0) feed

Embedded Lisp – via Lua

A few months ago I had one of those nights where you just do not feel like sleeping. That time, I created an interpreting environment for a mini Lisp in Lua. I call that LuaLisp.
DISCLAIMER to all die-hard Scheme fanatics out there: I use the term Lisp losely here, to the extent of including Scheme. LuaLisp is actually more of a Scheme interpreter.

The upside of this nocturnal feat, beside showing the coolness of these two specific languages, is that the small footprint of Lua translates to an embeddable and small Lisp environment. Since I decided to complete the project in one night, the Lisp environment was forced to be small.Yes, I do get a bit slow after 4 AM :-(

There are two approaches to this post: (1) follow me through my attempts at exposing implementation techniques and decisions for a Lisp interpreter or (2) just download the files from the bottom of this post or from the Google project page and start using it.

To enjoy this post, it is helpful, but certainly not necessary, to understand the basics of Lua. You can find such information at its home page. There is only one book available about Lua – besides tiny script snippets in game development literature – as far as I know, which can also be downloaded as a PDF from the Lua site for free:
Programming in Lua, Second Edition

For an introduction to Lisp or Scheme (the relation between the two is analogous to the words “Unix” and “Linux”, by the way), I would recommend two books:
The Little Schemer - 4th Edition Structure and Interpretation of Computer Programs - 2nd Edition (MIT Electrical Engineering and Computer Science).
For a more detailed treatise about Scheme, and that acted as a source of motivation for LuaLisp, buy:
The Scheme Programming Language: Third Edition.

Now that we have the knowledge groundwork covered, let us continue with LuaLisp

How To Implement Lisp In Lua

Let us first look at the three most striking features of Lisp:

  1. The simple and regular syntax – yes, those parentheses :-)
  2. Functions and closures being first class citizens – ok, this might not sound that exotic for you lucky bastards that are raised in the modern IT world, where all popular languages (except for Java) support this to some extent, but for me, when encountering Lisp back in 1984, it was an eye opener
  3. Same syntax for data and code

Some people would add beauty as the fourth striking feature ;-)

Feature #1 makes parsing extremely simple, and it took me about 160 minutes to create one in Lua, whereof 90 minutes were spent on Lua idiosyncracies – I was a newbie of Lua that evening. This does not say much about me, but speaks a lot about the (eye-pleasing or not…) simplicity of the Lisp syntax. In fact, it probably takes longer to write this post about that system than building that system :-)

Feature #2 happens to be embeddable into Lua’s closure system, which comes very handy at around 2 AM. I.e., I translated Lisp closures directly into Lua closures, and even provided callback integration, which allowed Lisp closures to be called from Lua code.

Feature #3 is focused around symbolic expressions, or S-Expr for short. This is the heart and soul of Lisp. It is best defined and explained in the must-have book Anatomy of Lisp by John Allen. This book is a bit hard to get, and when I lent my good friend Luke Flemmer my copy, he just got to smell it before I needed it back. It is that good! For Luke and other curious (double semantics…) minds, you can find it at Anatomy of Lisp (McGraw-Hill computer science series). If you think $50 for a used copy is a bit steep, wait till you buy it and read it. The joy that book brings exceeds those 4 pitchers of beer you would get around the corner. Just like this other classic, you must preempt your mind from buzz before reading it.

So, how did I implement these features and the rest of Lisp?

I started, as mentioned above, with the S-Expr parser, which would by feature #3 handle both data structures and code. Neat.

I did not use a proper compiler-compiler tool, such as discussed in previous posts, but used good old ad hoc hand-coded magic. I would not use this approach for a language with more complex syntax. But due to feature #1, it worked here.

The parser consists of two files: Token.lua and Parser.lua. Both these files are found in their entirety in the bottom of this post. These two files corresponds to what computer scientists would call lexical analyzer and parser, respectively.

Token.lua is extremly simple, and contains only five tokens. That is right: 5! Here is the complete content:
[hilite,lua]
– Token.lua

– Tokens, which are unevaluated atoms, list delimiters or special
– operators

Token = {}

function Token.newString(str)
return { .token=”STR”, .lexeme=str }
end

function Token.newLeftParen()
return { .token=”LEFTPAREN”, .lexeme=”(” }
end

function Token.newRightParen()
return { .token=”RIGHTPAREN”, .lexeme=”)” }
end

function Token.newComma()
return { .token=”COMMA”, .lexeme=”)” }
end

function Token.newQuote()
return { .token=”QUOTE”, .lexeme”‘” }
end
[/hilite]

Side Note: I just realized that my WordPress code hiliter handles Lua syntax :-)
Note: Lua has only tables, so to create a Token object, one just needs to return a new table with the keys that a Token should have. This open structure is of course familiar to both Erlang and JavaScript developers.

The stream of tokens is created by an invocation of Parser.parseTokens, in Parser.lua. The parser then acts on this stream. Both this lexical and more semantic analysis are triggered by the Parser.parseExpr function.

The aforementioned function returns Sexpr objects, which are defined in Sexpr.lua.

Let us try this parser before continuing! Download the LuaLisp files, a Lua implementation and open a command window or shell and direct yourself to the download directory. Create a new test app in Lua, TestParser.lua as follows:
[hilite,lua]
require “Parser”
sexpr = Parser.parseSexpr(arg[1])[1]
print (sexpr)
[/hilite]

Note: the parser actually returns a list of Sexpr, and we here expect only one expression, thereof the [1] at the end. Note: Lua uses index 1 as the first index, by convention.

Pass it a simple S-Expr, such as 7:

% lua TestParser.lua 7
atom[type=NUM, lex="7"]

See, we got an Sexpr object representing 7. Ok, I must show that I am not bluffing, so let us expose that object in a more user-friendly manner. This is done via pretty-printing (in fact, the pretty printing function in Sexpr.lua is probably the second largest function in the whole system…):
[hilite,lua]
require “Parser”
sexpr = Parser.parseSexpr(arg[1])[1]
print(Sexpr.prettyPrint(sexpr))
[/hilite]

Try with the expression 7 again:

% lua TestParser.lua 7
7

One last adventorous run before we continue beyond parsing:

% lua TestParser.lua "((lambda (x) (+ x 2)) 5)"
((lambda (x) (+ x 2)) 5)

Note: the apostrophes around the argument is stripped before arriving to Lua.
Hey, should it not be 7? After all, adding two to five should yield seven, right?

Well, remember that we are only parsing the expressions, not evaluating them.

The Sexpr.lua module is the glue between “compile-time” (i.e., parsing) and runtime.

So we have three files handling the syntax: Token.lua, Parser.lua and Sexpr.lua, where the former two modules manifest the “compile-time” syntax while the latter module represents a live syntax, which will follow the execution. In fact, the former two can be brought into execution via introspection (the Lisp function eval and cousins.)

In runtime, there are three new modules assisting: Environment.lua, LispInterpreter.lua and Prelude.lsp. What the heck is a .lsp file doing among the Lua files?! Well, the idea behind LuaLisp is to implement a minimal core language, to bootstrap the environment, upon which the actual Lisp primitives are built. This separation enables bringing in distinct Lisp dialects via separate “prelude” files.

Let us look at Prelude.lsp to get a better sense.
[hilite,lisp]
(defmacro defun (name params body)
(setq name (lambda params body)))

(defmacro or (a b)
(if a a b))

(defmacro and (a b)
(if a b nil))

(defun <= (x y)
(or (< x y) (eq x y)))

(defun > (x y)
(< y x))

(defun >= (x y)
(<= y x))

(defun - (x y)
(+ x (neg y))))

(defun nullp (x)
(eq x nil))
[/hilite]

As the experienced Lisp and/or Scheme practioner can readily see, I am mixing Scheme syntax ((lambda (x) …)) and Common Lisp syntax ((defun ...)). May McCarthy forgive me! But wait, that blesphamy is only an inch deep (or, two lines, to be exact), since I define that defun inside the prelude itself. This is done via a macro facility I had to create as part of the core language. Basically, a macro is a call-by-name function. In Lisp lingo, it is called a special form.

This bootstrapping makes it possible to introduce a more Schemish define construct instead, as:
[hilite,lisp]
(defmacro define ((name . params) body)
(setq name (lambda params body)))
[/hilite]
after which we can define a function as in Scheme:
[hilite,lisp]
(define (fac n) (if (eq n 0) 1 (* n (fac (- n 1)))))
[/hilite]

My special form defmacro is a hybrid between similarly named constructs found in Common Lisp and the special translating forms of Scheme. Just view it as a “really cool thing that does not evaluate stuff till it is really needed” :-)

To get into a bit more detail, the interpreter actually consists of three layers:

  1. The engine
  2. The core primitives, being part of the core language, and not corresponding to any concrete syntax. They are mapped to operations inside the engine
  3. The dialect primitives, mapped onto basic (and sometimes core…) primitives via a prelude Lisp file.

We have seen layer #3, so let us look at the other two layers.

The core primitives are defined in LispInterpreter.lua. They should be put in a separate “core language” Lua file, but I must have been too tired :-(

Anyway, the core primitives are

  1. prim_car – get the first part of a pair
  2. prim_cdr – get the second part of a pair
  3. prim_cons – create a new pair
  4. prim_plus – add two numbers
  5. prim_mult – multiply two numbers
  6. prim_lambda – create a parameterized closure
  7. prim_if – select one of two expressions to evaluate
  8. prim_eq – test two S-Expr for equivalence
  9. prim_lt – is one number smaller than another?
  10. prim_consp – is the given S-Expr a pair?
  11. prim_neg – take the negation of one number
  12. prim_setq – bind a variable in the current environment
  13. prim_eval – evaluate an S-Expr inside the current environment; this provides reflection
  14. prim_load – load and execute code from a file
  15. prim_echo – just pretty print the given S-Expr
  16. prim_defmacro – create a new call-by-name construct

As the attentive reader (and thinker) can guess, all Lisp code is executed in terms of core primitives in the end.

How are the core primitives brought into environment of the Lisp code? I said that the core primitives themselves did not have a concrete syntax, and without concrete syntax, it is hard to create code ;-)
Ok, first one has to understand what an environment is. An environment is a mapping from variables to their values, simplistically. So, before the Lisp code is executed – in fact even before the prelude is executed – an initial environment is setup by the following function in LispInterpreter.lua:
[hilite,lua]
function Lisp.getPrimitiveScope()
return {
car = Sexpr.newFun(“car”, Lisp.prim_car),
cdr = Sexpr.newFun(“cdr”, Lisp.prim_cdr),
cons = Sexpr.newFun(“cons”, Lisp.prim_cons),
lambda = Sexpr.newFun(“lambda”, Lisp.prim_lambda, “lazy”),
setq = Sexpr.newFun(“setq”, Lisp.prim_setq, “lazy”),
[“<"] = Sexpr.newFun("<", Lisp.prim_lt),
["+"] = Sexpr.newFun("+", Lisp.prim_plus),
neg = Sexpr.newFun("neg", Lisp.prim_neg),
eq = Sexpr.newFun("eq", Lisp.prim_eq),
consp = Sexpr.newFun("consp", Lisp.prim_consp),
eval = Sexpr.newFun("eval", Lisp.prim_eval),
load = Sexpr.newFun("load", Lisp.prim_load),
echo = Sexpr.newFun("echo", Lisp.prim_echo),
defmacro = Sexpr.newFun("defmacro", Lisp.prim_defmacro, "lazy"),
["if"] = Sexpr.newFun("if", Lisp.prim_if, "lazy")
}
end
[/hilite]

The string lazy indicates that the parameters supplied to this function will not be evaluated before invoking the function, i.e., call-by-name semantics.

After this, the prelude is executed inside that environment, enrichening the environment further.

The environment is our store, for values and functions, and will follow the Lisp session wherever it goes. Lua tables can also be used to associate values with keys. So, that is basically what I use for the Lisp environments, the Lua table. I say basically cause there is one caveat: Lisp allows for nested environments, which constitute a chain of environments, from the most local one to the global environment. Since we do not want to change the global variable fib just because we define a local variable with the same name, we have to seperate these environments into distinct Lua tables. The lookup then has to traverse this chain from local to global scope:
[hilite,lua]
function Env:lookup(symbol)
for i = self.scopeCount, 1, -1 do
local tab = self.scopes[i]
local val = tab[symbol]
if val then
return val
end
end
return nil
end
[/hilite]

One nice syntactic extension capability of Lua is the meta keys for any table, which allows us to overload the primitive Lua operations. We can thereby route index accesses to our chain-traversing lookup, by the following code:
[hilite,lua]
Env.mt = {
__index = Env.lookup,
__newindex = Env.add,
__tostring = Env.tostring
}
[/hilite]

After that, using this simple Lua syntax will do what we want:
[hilite,lua]
value = env["foo"]
env["foo"] = 42
env["bar"] = 33 — this will create a new binding in the most local scope
[/hilite]

The evaluation of parsed Sexpr is relatively simple once environments are there.

We have an expression evaluator in LispInterpreter.lua:
[hilite,lua]
function Lisp.evalSexpr(env, sexpr)
local value
if not sexpr.type then
error(“Invalid S-expr: ” .. sexpr, 2)
end
if sexpr.type == “CONS” then
— 1. Cons cell
local car = sexpr.car
if car.type==”OP” and car.lexeme==”‘” then
value = sexpr.cdr
elseif car.type==”OP” and car.lexeme==”`” then
local cdr = Lisp.evalQuote(env, sexpr.cdr)
value = cdr
else
local fun = Lisp.evalSexpr(env, car)
if not fun or fun.type ~= “FUN” then
error(“The S-expr did not evaluate to a function: ” ..
tostring(car))
end
— The function can be eithe “lazy”, in that it deals with
— evaluation of its arguments itself, a “macro”, which requires
— a second evaluation after the macro expansion, or
— a regular eager one

local args
if fun.special == “lazy” or fun.special == “macro” then
args = sexpr.cdr
else
args = Lisp.evalList(env, sexpr.cdr)
end
value = fun.fun(env, args)
end
elseif sexpr.type == “SYM” then
— a. symbol
value = env[sexpr.lexeme]
if not value then
error(“The symbol ‘” .. sexpr.lexeme .. “‘ is not defined”)
end
else
— b. constant
value = sexpr
end
return value
end
[/hilite]

We see that we have three top-level cases in the evaluation function:

  1. a pair – or CONS cell, in which case we check whether the first component is a “special” operator (there are a few “escaping” operators in Lisp, such as the quote or backquote operators). If not, we evaluate the first component, which should result in a Lisp function, and if that is not a lazy function, we also evaluate the parameters, after which we apply the function
  2. a symbol, which is looked up in the passed environment and the associated value becomes the result
  3. a constant, such as a numerical literal or a quoted symbol, which is returned as is

Besides these entry points to the system, there also is an interactive shell, to test or execute Lisp code. That interactive shell is defined in a seventh file, Interaction.lua. A guide and sample runs is found below.

Interactive Lisp Shell

An interactive session is started by
lua Interpreter.lua

Here is a sample session:

> 42
42
> 'foo
foo
> foo
#error: LispInterpreter.lua:92: The symbol 'foo' is undefined
> (lambda (x) (+ x 1))
#'(lambda (x) (+ x 1))
> +
#'+
> (defun !(n) (if (eq n 0) 1 (* n (! (- n 1)))))
#'(lambda (n) (if (eq n 0) 1 (* n (! (- n 1)))))
> (! 5)
120

Note 1: I use a Common Lisp syntax for showing a lambda closure, preceded by #' (which is shorthand for function.)
Note 2: you can use quite special names for variables (and functions), such as !.

Please start the interactive shell and try yourself.

I actually created a newer version of LuaLisp a few days later, but cannot find it right now :-( That version included reflection mechanisms and transparent integration between Lisp and Lua closures, enabling Lisp functions to be called from native Lua, with automatic S-Expr wrapping of native values. Will inform you when I find it…

The Code

Here are the source files, which all adher to the M.I.T. License – read the license.txt file. The project is hosted at Google’s code site, wherefrom you can download the code as well.

First, we need a few tokens:

[syntax,Token.lua,lua]

Then we can parse those tokens:

[syntax,Parser.lua,lua]

The parsed objects are S-Expr, represented by:

[syntax,Sexpr.lua,lua]

Values, being S-Expr are stored and retrieved from environments:

[syntax,Environment.lua,lua]

The operations, implemented by the engine and exposed as core Lisp primitives:

[syntax,LispInterpreter.lua,lua]

Then we add a sugar coat on top of it, matching specific Lisp dialects:

[syntax,Prelude.lsp,lisp]

Ok, we could use an interactive shell:

[syntax,Interaction.lua,lua]

Sverker said,

September 8, 2006 @ 7:26 pm

Neat, and it ran straight out of the box. LuaLisp lacks a few primitives needed by my little Prolog in Lisp (dug up from a sibling directory to where resides groeb.pl), but adding them wouldn’t be a lot of work…

mhyst said,

March 28, 2008 @ 1:37 pm

Hello,
I was creating a new language (lisp based) for my w3s personal web crawler, to serve as interpreter for user searching algorithms. The entire project is written in java. Then I discovered this post and I got shocked. Lol. Your code is really short!

I got some good ideas from your post.

Thank you!

davber said,

March 28, 2008 @ 7:18 pm

I would love to share ideas with you, since neat and short implementation of (interpreted or not) languages is one of my hobbies.

There are mainly two reasons for the shortness of my implementation:

1. I decided to do it as a one-night stunt :-)

2. The (static) closures and chains of environments in Lua are isomorphic to what is found in (most) LISP implementations; I used that isomorphism heavily.

Hope to see some code from you somewhere; please post an URL for anything you can expose to the big wide world :-)

Thanks,

David

mhyst said,

March 30, 2008 @ 7:04 pm

I haven’t any problem to comment it with you. After all it’s open source. w3s project is already released to the publi (http://sourceforge.net/projects/w3s/). Also I wrote a paper some months ago (http://searchlores.org/mhyst_w3s.htm).

As for the w3s language, now I’m writing an interface to access Java Objects from it. I’ll write some article about it as soon as I have something working.

Data types management sucks. I wanted for my language a loose types management. But as long as I need to instantiate java objects and pass arguments to it, I need a hard typed model.

If you’re really interested, I can send you the source code.

Thanks

RSS feed for comments on this post · TrackBack URI

Leave a Comment

You must be logged in to post a comment.