This post originated from an RSS feed registered with Ruby Buzz by Eigen Class. Original Post: Ruby interpreting Prolog' interpreting Lisp interpreting Lisp solving FizzBuzz Feed Title: Eigenclass Feed URL: http://feeds.feedburner.com/eigenclass Feed Description: Ruby stuff --- trying to stay away from triviality. Latest Ruby Buzz Posts Latest Ruby Buzz Posts by Eigen Class Latest Posts From Eigenclass

I've written a Lisp 1 interpreter in a Lisp dialect interpreted by the Prolog-ish language interpreted in Ruby*1 I have recently blogged about.

FizzBuzz is poised to become the programming task of choice for discriminating hackers, right? It surely deserves being the first program to be executed by that interpreter.

This Ruby code would not get you to be designated an extremely cool hacker, but it exercises 4 interpretation levels and it actually solves FizzBuzz:

require 'lisp'

fizzbuzz = lisp do
  L(lambda, L(x, y),
    L(cond,
      L(L(">=", x, y), 1),
      L(LTRUE, L(fizzbuzz_, L("+", L(output, x), 1), y))))
end
fizzbuzz2 = lisp{ L(L(label, fizzbuzz_, fizzbuzz), 1, 101) }

show = lisp{ L(lambda, L(text, ret), L(car, L(_cons, ret, L(puts, text)))) }

output = lisp do
  L(lambda, L(i),
    L(cond,
      L(L("==", L("%", i, 15), 0),    L(show, "FizzBuzz", i)),
      L(L("==", L("%", i, 3), 0),     L(show, "Fizz", i)),
      L(L("==", L("%", i, 5), 0),     L(show, "Buzz", i)),
      L(LTRUE,                        L(puts, i))))
end

# using label, a bit slower
#query _eval_[fizzbuzz2, L(L("output", output), L("show", show)), :X]

# explicitly adding fizzbuzz_ to the environment to allow recursion
le_fizzbuzz = _eval_[L("fizzbuzz_", 1, 101), 
                     L(L("output", output), 
                       L("fizzbuzz_", fizzbuzz),
                       L("show", show)),
                     :X]
resolve(le_fizzbuzz){ }

The interpreter stack

Lisp can be written in itself, and the S-expressions in the above program are processed by a Lisp 1 interpreter written in a (somewhat different) Lisp dialect interpreted by a logical language defined atop Ruby. Here follows a rough overview of some of these layers.

Primitive operators

The Lisp 1 interpreter is implemented in terms of seven primitive operators (quote, atom, car, cdr, eq, cons, cond)*2, which themselves are written using the above-mentioned logical language.

The only primitive operator that requires some (a couple lines of) Ruby code is atom, but the other six can be expressed very succinctly.

A function is but a special case of a relation, so

eq(x, x) := true, otherwise
eq(x, y) := false

can be expressed as "EQ[X, X, TRUE], otherwise EQ[X, Y, FALSE]". In the following definitions, I leverage the fact that predicates will be tested in order, allowing me to use the cut to express disjunction:

_quote[:X, :X] <<= :CUT

_eq[:X, :X, LTRUE]    <<= :CUT
_eq[:X, :Y, LFALSE]   <<= :CUT

_car[cons(:X, _), :X] <<= :CUT
_car[:X, LFALSE]      <<= :CUT

_cdr[cons(_, :X), :X] <<= :CUT

_cons[:X, :Y, cons(:X, :Y)].fact 

_cond[cons(list(LTRUE, :E), _), :E] <<= :CUT
_cond[cons(_, :R), :Ret]            <<= _cond[:R, :Ret]

The Lisp 1 interpreter

A Lisp interpreter written in itself takes only 60 lines of code. I did a straightforward translation using the above operators, and although it didn't grow that much in terms of lines of code (around 75), it's considerably more dense: