μLithp

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 name
• quote : avoids evaluation of an expression
• car : retrieves the first element in a list
• cdr : retrieves all but the first element in a list
• cons : constructs a new list from some element appended to the front of some list
• eq : checks the equality of two values
• if : checks the truthiness of an expression and evaluates one of two branches depending on the result
• atom : 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.

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!

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.

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