μLithp
μLithp - a Lisp in 27 lines of Ruby source
Primordial ooze | A reader | REPL | A compiler | Ruby interop
In the beginning was a fancy
This is a line-by-line deconstruction of how μLithp works, including commentary on extending the base language.
The primordial functions and forms
class Lisp
Ruby is one of those kinds of languages, so everything starts with a class declaration. Kidding aside, I thought it would be cool to encapsulate Lispiness in a class a provide extension via inheritance, but never got around to trying it.
def initialize(ext={})
The constructor seems like as good a place as any to declare the basic functionality. Every minimal Lisp requires a basic set of features, including, but not limited to the following functions and special forms:
label
: a way to bind a value to a namequote
: avoids evaluation of an expressioncar
: retrieves the first element in a listcdr
: retrieves all but the first element in a listcons
: constructs a new list from some element appended to the front of some listeq
: checks the equality of two valuesif
: checks the truthiness of an expression and evaluates one of two branches depending on the resultatom
: checks if a value is a base value (i.e. not a composition type like a list)λ
: creates a function
I'll give more detail about each below.
@env = { :label => proc { |(name,val), _| @env[name] = eval(val, @env) },
Every Lisp evaluation takes place in the context of some environment. In μLithp the environment is a simple Hash instance and represents a global evaluation context. The :label
symbol is bound to a lambda
that takes two things, an Array with a symbol representing a name and a value and also a context (that is ignored). The name is then inserted into the global environment with the given value. As you can see, all bindings are created explicitly in @env
. You'll notice that I created the :if
logic with the proc
form. Doing so signals to the evaluator that the thing defined should receive its arguments unevaluated.
You'll notice that all of the callable's take an array as the first argument and a context as the second. This is key for future expansion. Additionally, I like to use Ruby's destructuring format to unwrap the actual arguments hidden in the passed array.
:car => lambda { |(list), _| list[0] },
The :car
form returns the first element of its single argument. In μLithp, lists are just Ruby arrays at the bottom.
:cdr => lambda { |(list), _| list.drop 1 },
The :cdr
form takes a Ruby array and drops the first element.
:cons => lambda { |(e,cell), _| [e] + cell },
The :cons
form takes some value and plops it onto the front of the array provided as the second argument.
:eq => lambda { |(l,r), ctx| eval(l,ctx) == eval(r,ctx) },
The :eq
form takes two arguments and compares them for equality.
:if => proc { |(cond, thn, els), ctx| eval(cond, ctx) ? eval(thn, ctx) : eval(els, ctx) },
The :if
form takes a value as its first argument, tests its truthiness and either evaluates its second argument if true
or evaluates its third if false
.
:atom => lambda { |(sexpr), _| (sexpr.is_a? Symbol) or (sexpr.is_a? Numeric) },
The :atom
form tests for atomness (cannot be split). Currently, the only two things that are atoms are Symbols and Numbers. Numbers are a bit gratuitous because μLithp has no math operators.
:quote => proc { |sexpr, _| sexpr[0] } }.merge(ext)
The :quote
form just returns its first argument outright; without evaluation. Also, if an extension Hash was given, it's merged into the global environment.
end
And that's it for the primordial μLithp functions! You might notice that I've not handled the λ
form. This little nasty is handled via voodoo later on.
apply
def apply fn, args, ctx=@env
Now starts one of the two mutually recursive functions required to implement any Lisp worth its salt, apply
. The apply
function takes three arguments: 1) a symbol naming a function, 2) a array of arguments to the function and 3) a context (that defaults to @env
).
return ctx[fn].call(args, ctx) if ctx[fn].respond_to? :call
The first thing that I try is to look up the named function in the provided context and use Ruby's #call
method outright if the thing found responds to it. Most like this will mean that I've found a lambda
, Proc
or block, but it could be anything I suppose. I don't care much for proper error handling; I'm a Clojure programmer at heart.
self.eval ctx[fn][2], ctx.merge(Hash[*(ctx[fn][1].zip args).flatten(1)])
If what was provided was not a Ruby callable, then I need to perform some magic. What happens is that I look up the form stored at the symbol provided and get its third argument. For a μLithp function of the conceptual form (lambda (x y) ...body...)
this corresponds to the body of the function. After retrieving the body I then evaluate it in the context provided adorned with the bindings provided as arguments to the function zipped up with the original function's named parameters. This is the aforementioned voodoo regarding the lambda
form. What I'm doing is working under the assumption that a function was previously bound using :label
in a certain format: [:anything, [:arg1, :arg2], [:frob, :arg1, :arg2]]
. Magic!
end
And that's all there is to apply
. Freaking sweet!
eval
def eval sexpr, ctx=@env
The second mutually recursive function needed for a Lisp is eval
. This is a bit more complex than apply
, but not too bad.
if ctx[:atom].call [sexpr], ctx
The first thing to check in the course of evaluation is if the form provided is an atom. An atom can mean it's either a Symbol or a Numeric. So what I do I just look up the :atom
lambda in the context provided and use it to determine atomness.
return ctx[sexpr] || sexpr
If the form given was and atom then it might be a symbol bound to a value, so try to look it up in the context. If it didn't resolve in the environment, then it is an atom on its own terms, so I just return it outright.
end
And that's all that needs done for atoms.
fn, *args = sexpr
So if it wasn't an atom then it must be an executable thing right? Working under this assumption I destructure the form into the function symbol and its arguments. If you recall from CS 101 in college, a Lisp list of the logical form (fn arg1 arg2)
means to call function fn
with arguments arg1
and arg2
. What I'm extracting is a symbol used for looking up the function implementation and an array of arguments. If you'll recall, this is what apply
expected.
args = args.map { |a| self.eval(a, ctx) } if ctx[fn].is_a?(Array) || (ctx[fn].respond_to?(:lambda?) && ctx[fn].lambda?)
μLithp is an eager variant of Lisp. That is, arguments to functions are evaluated before the function is called. However, I do not evaluate if the form under evaluation is a Proc
created with proc
(i.e. :label
, :quote
or :if
). Ruby hackery, FTW!
apply(fn, args, ctx)
Now that I have the symbol naming a function and its evaluated arguments, I just call out to apply
to handle the call.
end
And that's all there is to eval
.
end
And that's all there is to μLithp. Enjoy.
Using
Below is a sample IRB session using μLithp:
require 'lithp.rb' l = Lisp.new l.eval [:label, :a, 42] l.eval :a #=> 42 l.eval [:eq, 42, :a] #=> true l.eval [:quote, [1, 2]] #=> [1, 2] l.eval [:car, [:quote, [1, 2]]] #=> 1 l.eval [:cdr, [:quote, [1, 2]]] #=> [2] l.eval [:cons, 1, [:quote, [2,3]]] #=> [1, 2, 3] l.eval [:if, [:eq, 1, 2], 42, 43] #=> 43 l.eval [:atom, [:quote, [1,2]]] #=> false l.eval [:label, :second, [:quote, [:lambda, [:x], [:car, [:cdr, :x]]]]] l.eval [:second, [:quote, [1, 2, 3]]] #=> 2