Lisp in 32 lines of Ruby | Hacker News Reader

Lisp in 32 lines of Ruby

blog.fogus.me

194 pointsjohndcook54 comments

I've just started working on full-featured Lisp in javascript over the past few weeks: https://github.com/jlongster/outlet

It will compile to js and lua, and I'm focusing on writing games with it. I can attest that writing a Lisp compiler is really fun and shockingly simple in some places.

Current features I'm working on: http://jlongster.com/2012/01/16/outlet-gets-a-personality.ht...

It may be worthwhile looking at Shen (a similar lisp-like langauge) which targets translation to JS. I haven't checked in on their progress in a while, but it seems the largest implementation hurdle is tail recursion.

shen is http://www.shenlanguage.org/

And of you course you can't talk about compile-to-JS lisps these days without mentioning ClojureScript ;)

ClojureScript is amazing, and makes sense for a lot of apps because it's so feature full.

It looks really interesting!

This "lisp in x lines of y" tradition started with the original Lisp paper back in 1960, which defined lisp in a few lines of lisp. Which, when you think about it, is an extraordinarily lispy thing to do.

Lambdas all the way down. Now beat that, modern "bootstrapped" compilers.

"Look, it's all lambdas all the way down. Until you reach turtles."

At which point, the parentheses are removed and you wind up with LOGO.

Lisp had to be bootstrapped with another compiler before it could run, of course. The compiler, in this case, was Steve Russell's brain.

http://www-formal.stanford.edu/jmc/history/lisp/node3.html

Hey guys

This seems like it would be perfect stuff for an educational lightning talk

If any of you are in the SF Bay Area, please consider doing a ~5 min presentation on your lisp-in-x implementation at the lisp meetup "revival" this saturday at the blackbox mansion in Atherton

...free beer... ;-)

http://www.meetup.com/balisp/events/48872022/ http://balisp.org/

A similar endeavor in Python: http://www.brool.com/index.php/the-tiniest-lisp-in-python

I find it quite entertaining to see how specific language features allow for differing patterns. It is much more apparent with such Lisp implementations than with your typical Hello, World app or hidden by some library or framework.

I got a lot of interesting comments from that article. Someone pointed me to this brilliantly evil implementation which can be seen at https://gist.github.com/1679908 (originally from http://www.pick.ucam.org/~ptc24/yvfc.html, which seems to be down). There's also Norvig's implementation, which is much cleaner, at http://norvig.com/lispy.html, and a Lisp to Python compiler at http://bernhardkausler.wordpress.com/2009/11/28/sinc-%e2%80%....

See also: Heist, a feature-rich implementation of Scheme in Ruby: https://github.com/jcoglan/heist

Shameless Self Promotion. Here are two version of the LISP interpreter in JavaScript that I wrote:

1. Direct port of Peter Norvig's version in Python:

https://bitbucket.org/sainamdar/lisp2js/

2. Separate Syntactic Analysis from Execution:

https://bitbucket.org/sainamdar/lisp2js2/

I think that's a testament to the awesomeness of Lisp, not of Ruby ;)

Exactly. I reckon you couldn't invert the process i.e. write Ruby in 32 (short) lines of lisp.

Well. Obviously. The syntax is much, much more complicated.

But if you were to adopt a ruby syntax subset, enough of the semantics are similar enough to not pose a significant problem.

How easy is lisp to implement in a language without first class functions?

Whilst not supporting first class functions, C is pretty easy on you in that respect. I reckon there are suitably small lisp implementations in C (less than 100 lines). It all really depends if your lisp implementation uses the language's VM or a VM layer over the top.

Which class are functions in C? It was my impression that the only thing missing were anonymous functions, but there are pointers to functions if I'm not mistaken.

You can use function pointers. Functions in C are not first class (they are not a type) but you can emulate higher order functions crudely using function pointers.

It gets ugly pretty quick though.

> Which class are functions in C?

Economy class. :-)

In general, how do you write functions that return functions without some form of anonymous function? For instance, how do you write a function that takes an int a and returns a function that takes an int parameter and returns non-zero if and only if that parameter is greater than a?

Ruby has a lot of special cases (the Proc versus block dichotomy, implicit conversions, etc). Scheme has shockingly clean semantics in comparison.

Implementing Lisp in a language without first class functions is quite easy. Closure conversion is a simple process:

1) Find every variable in the parent lambda that is both accessed in a child lambda and assigned-to outside the child lambda; demote those variables to heap-allocated cells and rewrite references to those variables to indirect through the cell.

2) Note every free variable in the child lambda, and rewrite all references to those variables to indirect through an environment vector passed in through a hidden argument.

3) Generate each lambda as a top-level function, and generate each lambda expression as the allocation of a callable object referencing the top-level function and a heap-allocated environment vector; at each allocation site, generate code to copy the free variables into the environment vector.

This is literally the entire algorithm. It can be implemented in a couple of hundred lines of C.

Why not? [:eq, 42, :a] isn't native syntax in any Lisp I've ever seen. This is Lisp-like data structures and evaluation of native Ruby types, not a whole Lisp compiler or even the reader. It doesn't seem like it'd be any harder to get Ruby-like data structures and evaluation of native Lisp types. What's the core of Ruby? class, def, and :send, perhaps? SICP 3.1.1 does pretty much just that.

I'm not sure it even makes sense to talk about a core of Ruby in the same sense. The semantic core of Ruby is very light, but while a small Lisp is recognizable Lisp, a "small Ruby" without the weight of the Ruby syntax and a whole slew of runtime libraries, is not really likely to be recognizable as Ruby.

What makes Ruby is all the sugar.

E.g. MRI 1.8.x has a parser alone that is about 6000 lines of Yacc with C actions and workarounds for Yacc limitations.

Your best bet for a semantic core of Ruby would probably seem closer to Smalltalk than to Ruby...

I spent a term in college writing a Pascal interpreter in Scheme. It was far more than 32 lines. I wish I still had that code, but, alas, no github in the first half of the nineties.

By that argument BrainFuck is even awesomer than Lisp.

No because after making an interpreter you have a nice language to work with. That makes it very different than BF.

That is begging the question. The argument was supposed to prove that Lisp is "awesome;" if you have to assume that Lisp is a "nice language" for the argument to work, the argument hasn't proven anything.

I think Ruby is a nicer language than Lisp.

Nice is relative. Most anything is nice compared with BF.

Lisp (including full lexical closures) in 50 lines of Python:

http://www.flownet.com/ron/lisp/l.py

Cute, but from like 28 [1] it looks like there is no macro support, so this isn't a lisp but is rather a way to write a ruby expression in a ruby array.

[1] https://github.com/fogus/ulithp/blob/master/lithp.rb#L28

If macros are needed for the definition of a lisp, then you'll eliminate some important Lisps.[1] If you want macros in the one at the link (ulithp), then you only need to write that feature into an evaluator (dare I say, meta-circular) written in ulithp much like what is done in my other Lisp Lithp.[2]

[1]: http://www-formal.stanford.edu/jmc/recursive/recursive.html

[2]: https://github.com/fogus/lithp/blob/master/src/core.lisp#L10...

Link [2] looks very nice and IMO would be a much more interesting topic than the trivial ruby implementation.

I apologize for the dismissive rudeness of my first comment... I am tired of the many "I saved a function and its arguments into a list, and then wrote a method to evaluate that list" implementations which seem to be so exciting. Although I guess this isn't a new trend (see lisp in awk [1]).

[1] http://chasen.org/~daiti-m/etc/awk/walk.pdf

32 lines of Ruby and a hundred thousand lines of C, let's not forget. Anyone can write any short program in a DSL, that is not represenative of the true complexity of it.

And another order of magnitude in assembly.

Wow...for me learning LISP just earned itself priority-High status!

It seems funny to me, that it needs most probably more lines to write a good lisp tutorial for beginners, than a lisp implementation. Lisps beauty lies in its simplicity.

Next up, lisp in 1 line of common lisp

#'eval

I was a bit hasty, here is the complete version:

  (loop (print (eval (read))))

I translated it to js -> https://gist.github.com/1679611 Earned 1 line, and packed it with a cheap implementation of zip :3

I personally, have been waiting centuries for our robotic overlords to improve the runtime performance of lisp. Now I can wait some more!

Racket and SBCL are very fast.

Check out the Stalin Scheme[1] compiler which can produce code faster than hand-written C (it's a whole-program optimizing compiler targetting C).

[1]: http://en.wikipedia.org/wiki/Stalin_(Scheme_implementation)

Nice, but wasn't chicken scheme the flagship of scheme-to-c compilers? http://www.call-cc.org/

A real lisp: http://sbcl.org

He seems to have forgotten lambda, without which you can't really write anything more interesting than the examples that are given.

I thought this was his example of lambda:

  l.eval [:label, :second, [:quote, [:lambda, [:x], [:car, [:cdr, :x]]]]]

No?

Can someone explain how this works?

I understand that (label second '(...)) makes second evaluate to that in the future, statefully, but, the lambda symbol doesn't even appear to have a definition; furthermore, if you try to use it in a way that would work with a real lambda, it doesn't work.

For instance [[:lambda, [:x], :x], 2]

Take a look at the second line in the `apply` definition[1]:

    self.eval @env[fn][2], Hash[*(@env[fn][1].zip args).flatten(1)]

It's triggered when the `fn` is not callable, i.e. when we pass in lambda:

    [:lambda, [:x], [:car, [:cdr, :x]]]

The code ignores the `:lambda` symbol (that would be `@env[fn][0]`).

It evals the third element of the list (the lambda body) in a new context that combines `@env` and the binding of lambda's args to the symbols in the lambda's definition -- that's what the `Hash` mumbo jumbo creates.

[1]: https://github.com/fogus/ulithp/blob/b02d5806ce3b2d3766311c2...

Even the example using lambda?

    :if    => lambda { |(cond, thn, els), ctx| eval(cond, ctx) ? eval(thn, ctx) : eval(els, ctx) },

Seriously, any production code like that (very long line, cryptic variable names to make it fit better on said line) would get nasty review comments here.

Why not put the whole thing a single line and have an even prettier page title?

Reply on news.ycombinator.com