RLisp - Lisp naturally embedded in Ruby

I wrote a small Lisp interpretter for Ruby. It supports macros,
and is fully integrated with Ruby - lambdas are native procedures, lists are native Array objects
and so on. That required a few unusual things for a Lisp, like cdr/cons actually
copying the list, special function (send obj method args) for message passing.

There is hello-world code for webrick-based HTTP server in RLisp in examples/ directory,
so it's basically good enough for playing. And I guess it can be used to build
macro systems for Ruby - many people seem interested but don't know where to start.
Now you can start by playing with RLisp :-)

The code is here.
The documentation is only on my blog so far - 1, 2, 3. I'll try to get some real docs later.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Lists and arrays

Implementing lists in terms of arrays this way is a bad idea. Most algorithms using cons and cdr apply them recursively; they would have awful performance. Lisp-style lists and Ruby-style arrays require different programming styles.

Lists and arrays

I strongly disagree. The performance is going to be worse only in a very rare case when at the same time:

  • the list is huge (like hundreds or more elements), and
  • is being created or traversed by explicit structural recursion.

If the list is small, or is big but is traversed by high-order operations like map/fold/foreach, or we do things like random access, whole-list operations (length), then we get better performance - compiled array iteration is >5x faster on modern hardware than list traversal for cache reasons. And a "sufficiently smart compiler" ;-) can detect the worst cases anyway, so why worry ;-) (or one can rewrite those rare cases to use more efficient algorithms if they are actually performance-critical)

As a nice side effect this also disallows two uses that I consider extremely ugly:

  • Using cons for things other than list building. (a . b) should be (list a b) for god's sake, it's high level language not assembly.
  • Modifying cons cells and expecting those modifications to be shared across cons/cdr.

In any case, I wouldn't care much about performance. Expressiveness is much more important than that, and very tight integration with Ruby brings huge boost to expressiveness.

Best of both worlds:

You can actually get the best of both worlds: VList

Cool :-)

VList looks cool :-)

Still, in RLisp implementing lists as Ruby Arrays was for interoperability, not performance :-)


VList's asymptotic performance goes down when there's a lot of sharing. Timewise, it's within a constant factor of cons-based lists, but they take a lot more space. Maybe if the size of the next array was double the size of the portion of the previous array that is actually shared, instead of its total size, it'd work out much better. Actually, this might be what their implementation does, that point wasn't clear in the paper, IIRC.

I just noticed that there

I just noticed that there exists another RLisp , so you might perhaps want to change name.