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:

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:
.
For a more detailed treatise about Scheme, and that acted as a source of motivation for LuaLisp, buy:
.

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:

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:

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...):

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.

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:

after which we can define a function as in Scheme:

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:

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:

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:

After that, using this simple Lua syntax will do what we want:

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

We have an expression evaluator in LispInterpreter.lua:

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:

-- This software is licensed under the M.I.T. license.
-- The license text is found in "license.txt"
--
-- 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

Download this code: Token.lua

Then we can parse those tokens:

-- This software is licensed under the M.I.T. license.
-- The license text is found in "license.txt"
--
-- Parser.lua
-- Author: David Bergman
-- 
-- A Scheme parser
--
 
require "Sexpr"
 
Parser = {
   operators = { ["("] = true, [")"] = true, [","] = true,
      ["'"] = true, ["`"] = true, ["."] = true }
}
 
-- Parse the code snippet, yielding a list of (unevaluated) S-expr
function Parser.parseSexpr(expr)
   local tokenList = Parser.parseTokens(expr)
   local expr
   local next = 1
   local sexprList = {}
   repeat
      next, sexpr = Parser.createSexpr(tokenList, next)
      if sexpr then
	 table.insert(sexprList, sexpr)
      end
   until not sexpr
   return sexprList
end
 
function Parser.createSexpr(tokens, start)
   -- If the first token is a '(', we should expect a "list"
   local firstToken = tokens[start]
   if not firstToken then
      return start, nil
   end
   if firstToken.type == "LEFTPAREN" then
      return Parser.createCons(tokens, start+1)
   elseif firstToken.type == "OP" then
      local next, cdr = Parser.createSexpr(tokens, start+1)
      return next, Sexpr.cons(firstToken, cdr)
   else
      return start+1, firstToken
   end
end
 
function Parser.createCons(tokens, start)
   -- If the first token is a '.', we just return the second token,
   -- as is,
   -- while skipping a subsequent ')',
   -- else if it is a ')' we return NIL, else
   -- we get the first Sexpr and CONS it with the rest
 
   local firstTok = tokens[start]
   if not firstTok then
      error("Token index " .. start ..
	    " is out of range when creating CONS S-Expr", 2)
   end
   if firstTok.type == "OP" and firstTok.lexeme == "." then
      -- We skip the last ')'
      local next, cdr = Parser.createSexpr(tokens, start+1)
      if not tokens[next] or tokens[next].type~="RIGHTPAREN" then
	 error("The CDR part ending with " .. tokens[next-1].lexeme ..
	       " was not followed by a ')'")
      end
      return next+1, cdr
   elseif firstTok.type == "RIGHTPAREN" then
      return start+1, Sexpr.newAtom("nil")
   else
      local next, car = Parser.createSexpr(tokens, start)
      local rest, cdr = Parser.createCons(tokens, next)
      return rest, Sexpr.cons(car, cdr)
   end
end
 
-- Parse a sub expression, returning both an expression and
-- the index following this sub expression 
function Parser.parseTokens(expr)
   tokens = {}
 
   -- We do it character by character, using queues to
   -- handle strings as well as regular lexemes
 
   local currentToken = {}
   local inString = false
   local isEscaping = false
   for i = 1, string.len(expr) do
      local c = string.sub(expr, i, i)
      -- We have seven (7) main cases:
      if isEscaping then
	 -- 1. Escaping this character, whether in a string
	 -- or not
	 --
	 table.insert(currentToken, c)
	 isEscaping = false
      elseif c == "\\" then
	 -- 2. An escape character
	 --
	 isEscaping = true
      elseif c == "\""  then
	 -- 3. A quotation mark
	 --
	 -- Two sub cases:
	 if not inString then
	    -- a. starting a new string
	    -- If we already had a token, let us finish that
	    -- up first
	    if table.getn(currentToken) > 0 then
	       table.insert(tokens,
			Sexpr.newAtom(table.concat(currentToken)))
	    end
	    currentToken = {}
	    inString = true
	 else
	    -- b. ending a string
	    table.insert(tokens,
		Sexpr.newString(table.concat(currentToken)))
	    currentToken = {}
	    inString = false
	 end
      elseif inString then
	 -- 4. inside a string, so just add the character
	 --
	 table.insert(currentToken, c)
      elseif Parser.operators[c] then
	 -- 5. special operator (and not inside string)
	 --
	 -- We add any saved token
	 if table.getn(currentToken) > 0 then
	    table.insert(tokens,
		Sexpr.newAtom(table.concat(currentToken)))
	    currentToken = {}
	 end
	 table.insert(tokens, Sexpr.newOperator(c))
      elseif string.find(c, "%s") then
	 -- 6. A blank character, which should add the current
	 -- token, if any
	 -- 
	 if table.getn(currentToken) > 0 then
	    table.insert(tokens,
		Sexpr.newAtom(table.concat(currentToken)))
	    currentToken = {}
	 end
      else
	 -- 7. A non-blank character being part of the a symbol
	 --
	 table.insert(currentToken, c)
      end
   end
   -- Add any trailing token...
   if table.getn(currentToken) > 0 then
      local atom
      if inString then
	 atom = Sexpr.newString(table.concat(currentToken))
      else
	 atom = Sexpr.newAtom(table.concat(currentToken))
      end
      table.insert(tokens, atom)
   end
   return tokens
end
 
 

Download this code: Parser.lua

The parsed objects are S-Expr, represented by:

-- This software is licensed under the M.I.T. license.
-- The license text is found in "license.txt"
--
-- Sexpr.lua
-- Author: David Bergman
--
-- Deals with (unevaluated or not) S-expressions, which are simply
-- atoms or CONS cells
--
-- The atoms are either
-- 1. Literals (t or nil)
-- 2. Numericals
-- 3. Operators [',`] 
-- 4. Symbols
-- 5. Function references
 
Sexpr = {}
 
Sexpr.constants = { ["t"] = true, ["nil"] = true }
Sexpr.mt = {}
function Sexpr.mt.__tostring(expr)
   local str
   if expr.type == "CONS" then
      str = "(" .. tostring(expr.car) .. " . " .. tostring(expr.cdr) .. ")"
   else
      str = "atom[type=" .. expr.type .. ", lex=\"" .. expr.lexeme .. "\"]"
   end
   return str
end
 
-- Atoms
 
function Sexpr.newBool(cond)
   local atom
   if cond then
      atom = Sexpr.newAtom("t")
   else
      atom = Sexpr.newAtom("nil")
   end
   return atom
end
 
function Sexpr.newString(content)
   local atom = { type="STR", lexeme=content }
   setmetatable(atom, Sexpr.mt)
   return atom
end
 
function Sexpr.newOperator(op)
   local type
   if op == "(" then
      type = "LEFTPAREN"
   elseif op == ")" then
      type = "RIGHTPAREN"
   else
      type = "OP"
   end
   local atom = { type=type, lexeme=op }
   setmetatable(atom, Sexpr.mt)
   return atom
end
 
function Sexpr.newAtom(atom)
   -- Make sure to use the string from here on
   atom = tostring(atom)
   local sexpr
   -- three cases
   if Sexpr.constants[atom] then
      -- 1. Constant
      sexpr = { type="LITERAL", lexeme=atom }
   elseif string.find(atom, "^%d+$") then
      -- 2. Numerical
      sexpr = { type="NUM", lexeme=atom }
   else
      -- 3. Symbol
      sexpr = { type="SYM", lexeme=atom }
   end
   setmetatable(sexpr, Sexpr.mt)
   return sexpr
end
 
-- Create a new function reference, where the
-- special parameter can be nil (for a normal function)
-- or 'lazy' for functions handling their own internal
-- evaluation, or 'macro' for functions mereley replacing
-- their body, for further evaluation
function Sexpr.newFun(name, fun, special)
   return { type="FUN", lexeme=name, fun=fun, special=special }
end
 
function Sexpr:car()
   return self.car
end
 
function Sexpr:cdr()
   return self.cdr
end
 
function Sexpr.cons(a, b)
   local sexpr = { type="CONS", car = a, cdr = b }
   setmetatable(sexpr, Sexpr.mt)
   return sexpr
end
 
 
-- Pretty printer
 
function Sexpr.prettyPrint(sexpr, inList)
   local pretty
   if sexpr.type == "CONS" then
      local str = {}
      -- If we are inside a list, we skip the initial
      -- '('
      if inList then
	 table.insert(str, " ")
      else
	 table.insert(str, "(")
      end
      table.insert(str, Sexpr.prettyPrint(sexpr.car))      

      -- Pretty print the CDR part in list mode
      table.insert(str, Sexpr.prettyPrint(sexpr.cdr, true))

      -- Close with a ')' if we were not in a list mode already
      if not inList then
	 table.insert(str, ")")
      end
      pretty = table.concat(str)
   else
      local str = {}
      if inList and
	 (sexpr.type ~= "LITERAL" or sexpr.lexeme ~= "nil") then
	 table.insert(str, " . ")
      end
      if sexpr.type == "FUN" then
	 if sexpr.special == "macro" then
	    table.insert(str, "#macro'")
	 else
	    table.insert(str, "#'")
	 end
      end
      -- We just add the lexeme, unless we are a nil in the
      -- end of a list...
      if not inList or sexpr.type ~= "LITERAL" or
	 sexpr.lexeme ~= "nil" then
	 if sexpr.type == "STR" then
	    table.insert(str, "\"")
	 end
	 table.insert(str, sexpr.lexeme)
	 if sexpr.type == "STR" then
	    table.insert(str, "\"")
	 end
      end
      pretty = table.concat(str)
   end
   return pretty
end
 

Download this code: Sexpr.lua

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

-- This software is licensed under the M.I.T. license.
-- The license text is found in "license.txt"
--
-- Environment class
-- Author: David Bergman
-- Env.new : Creating a new environment
-- env[symbol] : lookup symbol (i.e., symbol:lookup(symbol) )
-- Env:lookup : lookup symbol
-- Env:addScope : add local scope
 
Env = { }
 
-- Lookup a symbol, going from the most local to the most
-- global scope
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
 
-- Add a new key or change an existing one in the most
-- local scope
function Env:add(key, value)
   self.scopes[self.scopeCount][key] = value
   return self.scopes[self.scopeCount][key]
end
 
-- Create a string representation of the environment
function Env:tostring()
   local str = {}
   table.insert(str, "Environment[scopeCount=" ..
		self.scopeCount .. "\n")
   for _, scope in ipairs(self.scopes) do
      table.insert(str, "Scope[")
      for key, value in pairs(scope) do
	 table.insert(str, tostring(key))
	 table.insert(str, "=")
	 table.insert(str, tostring(value))
	 table.insert(str, " ")
      end
      table.insert(str, "]\n")
   end
   table.insert(str, "]")
   return table.concat(str)
end
 
function Env:addBindings(formalList, actualList)
   local localScope = {}
   Env.bind(localScope, formalList, actualList)
   return self:addLocalScope(localScope)
end
 
function Env.bind(scope, formalList, actualList)
   if formalList.type=="CONS" then
      scope[formalList.car.lexeme] = actualList.car
      Env.bind(scope, formalList.cdr, actualList.cdr)
   end
end
 
-- Create local scope and return new extended environment
function Env:addLocalScope(localScope)
   -- Add a new empty local scope
   local newScopes = {}
   for _, scope in ipairs(self.scopes) do
      table.insert(newScopes, scope)
   end
   table.insert(newScopes, localScope)
   local newEnv = { scopeCount = self.scopeCount + 1,
      scopes = newScopes,
      add = Env.add, addBindings = Env.addBindins,
      addLocalScope=Env.addLocalScope }
    setmetatable(newEnv, Env.mt)
    return newEnv
end
 
Env.mt = {
   __index = Env.lookup,
   __newindex = Env.add,
   __tostring = Env.tostring
}
 
function Env.new(initialScope)
   -- The scopes are stored from most global to most local
   local env =  { scopeCount = 1, scopes = {initialScope},
      add = Env.add,
      addBindings = Env.addBindings,
      addLocalScope = Env.addLocalScope,
      lookup=Env.lookup }
   setmetatable(env, Env.mt)
   return env
end

 

Download this code: Environment.lua

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

-- This software is licensed under the M.I.T. license.
-- The license text is found in "license.txt"
--
-- LispInterpreter.lua
-- Author: David Bergman
--
-- This is a Scheme/Lisp interpreter, written in Lua
--
 
require "Environment"
require "Parser"
 
Lisp = { }
 
function Lisp.evalExpr(env, expr)
   return Lisp.evalSexprList(env, Parser.parseSexpr(expr))
end
 
function Lisp.evalQuote(env, sexpr)
   local value
   if not sexpr.type then
      error("Invalid S-expr: ", 2)
   end
   if sexpr.type == "CONS" then
      local car = sexpr.car
      if car.type=="OP" and car.lexeme=="," then
	 value = Lisp.evalSexpr(env, sexpr.cdr)
      else
	 local evalCar = Lisp.evalQuote(env, car)
	 local cdr = Lisp.evalQuote(env, sexpr.cdr)
	 value = Sexpr.cons(evalCar, cdr)
      end
   else
      value = sexpr
   end
   return value
end
 
function Lisp.evalSexprList(env, sexprList, index)
   if not index then
      index = 1
   end