eigenclass logo
MAIN  Index  Search  Changes  PageRank  Login

Ruby interpreting Prolog' interpreting Lisp interpreting Lisp solving FizzBuzz

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:

Here's the top-level of the eval function and the part that interprets the primitive operators (the remainder handles lambda and label):

   _eval_[:E, :A, :R] <<= [ _atom[:E, LTRUE], _assoc[:E, :A, :R], :CUT ]
   # atom but not var
   _eval_[:E, :A, :E] <<= [ _atom[:E, LTRUE], :CUT ]

   _eval_[:E, :A, :R] <<= [ _atom[:E, LTRUE], _assoc[:E, :A, :R], :CUT ]
   _eval_[:E, :A, :R] <<= [ _car[:E, :X], _atom[:X, LTRUE], _eval_1[:E,:A,:R], :CUT ]

   # eval_1 -> car(exp) is atom
   _eval_1[:E, :A, :R] <<= [ _car[:E, "quote"], _cadr[:E,:R], :CUT ]
   _eval_1[:E, :A, :R] <<= [ _car[:E, "atom"], _cadr[:E, :X], _eval_[:X, :A, :Y], _atom[:Y, :R], :CUT ]
   _eval_1[:E, :A, :R] <<= [ _car[:E, "eq"], _cadr[:E, :X1], _eval_[:X1, :A, :Y1],
     _caddr[:E, :X2], _eval_[:X2, :A, :Y2], _eq[:Y1, :Y2, :R], :CUT ]
   _eval_1[:E, :A, :R] <<= [ _car[:E, "car"], _cadr[:E, :X], _eval_[:X, :A, :Y], _car[:Y, :R], :CUT ]
   _eval_1[:E, :A, :R] <<= [ _car[:E, "cdr"], _cadr[:E, :X], _eval_[:X, :A, :Y], _cdr[:Y, :R], :CUT ]
   _eval_1[:E, :A, :R] <<= [ _car[:E, "cons"], _cadr[:E, :X1], _eval_[:X1, :A, :Y1],
     _caddr[:E, :X2], _eval_[:X2, :A, :Y2], _cons[:Y1, :Y2, :R], :CUT ]
   _eval_1[:E, :A, :R] <<= [ _car[:E, "cond"], _cdr[:E, :X], _evcon[:X, :A, :R], :CUT ]

The code

You'll have to enlarge your stack if you want to run fizzbuzz(1,101) (a few hundred MBs at least).



Sick and Wrong - Devin Ben-Hur (2007-03-03 (Sat) 15:33:48)

You're hired.

[Why L(...), not S(...)? They're S-expressions, after all]

mfp 2007-03-03 (Sat) 16:49:57

Sick, yes, but wrong? The solution is more correct than most I've seen :P

The plan now is to implement the polymorphic (second-order) lambda calculus on top of the Lisp dialect.

[L stands for "list", but S seems good]


Obfuscation - goodbyejim (2007-03-03 (Sat) 17:24:10)

Perl used to have obfuscation contents to see who could write the most incomprehensible Perl one-liners. This sort of article, while amusing, is a step down that path.

Obfuscation contests encouraged unhealthy attitudes among Perl programmers, and this FizzBuzz business threatens to do the same.

mfp 2007-03-03 (Sat) 17:50:26

The difference is that writing obfuscated Perl can only get you a few Perl tricks, and (I'd like to think, at least) this might inspire somebody to read up on Lisp-in-Lisp and hence learn about a particularly elegant model of computation. If there's any merit to the above, it must be the fact that it's not about FizzBuzz.

But I don't really believe in the "unhealthy attitudes" part. There's surely more value in knowing how to write obfuscated code and deciding not to than in being unable.

tyler 2007-03-03 (Sat) 18:42:16

/agrees with mfp.

My initial thought wasn't "oh god thats ugly" but rather "oh god thats beautiful". It's complicated, especially if you don't know exactly what you're looking at, but I fully agree - in terms of models, and the fact that it's Lisp-in-ruby, makes me giggle. I mean, it's almost perverse, but it makes me smile.


No Title - Anonymous (2007-03-04 (Sun) 16:25:18)

It occurs that:

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

might be a more efficient way of describing eq.

I'm definitely in the 'beautiful' camp. But then, I think the Sendmail Turing Machine is beautiful.

Piers Cawley 2007-03-04 (Sun) 16:32:14

Drat. Forgot to take responsibility for my words.

Piers Cawley 2007-03-04 (Sun) 16:49:40

I'm just having a play in IRB, and it looks like it might be possible to tweak things to get rid all those ugly commas in your Sexps by using a module with methods for a few special forms and a method_missing that, when you do

 module.module_eval { [a b [c d]] }

it builds you an sexp.

I think I need to play some more :)

Piers Cawley 2007-03-05 (Mon) 04:54:06

Gah! 'eq' is not 'and'

mfp 2007-03-05 (Mon) 15:52:58

Yes, something like

sexp = Lisp.some_magic_method { [lambda [a b], [cons a b]] }

seems possible. We cannot get rid of all commas, but most textual symbols could be chained using some additional method_missing magic. It's not as bad as it sounds since it'd be scoped to the block. (method_missing is defined globally by the mini-prolog engine, but the Lisp interpreter could be written independently very easily)


Expanding code blocks - clavicle (2007-03-05 (Mon) 13:30:04)

How is this done? It looks pretty neat.

mfp 2007-03-05 (Mon) 16:03:24

You mean the Sexps? Basically, #lisp does someobject.instance_eval(&block), where all methods have been undefined at someobject's singleton class' level. There's a method_missing in that class that returns the atoms (just a .to_s with optional renaming to avoid clashes), and L(*args) turns the array into a list (chain of cons).

The only half-nice thing about all this is that the special method_missing is circumscribed to the block. This is something some Ruby DSLs could also use.



Last modified:2007/03/03 10:03:09
Keyword(s):[blog] [ruby] [frontpage] [logical] [prolog] [lisp] [fizzbuzz] [interpreter]
References:

*1 itself interpreted, in the dominant implementation

*2 plus a few convenience functions like caar and friends