----- 
permalink: concatenative-programming-in-ruby
filters_pre: 
- erb
- redcloth
title: Concatenative programming in Ruby
date: 2009-03-28 07:24:00 +01:00
tags: 
- ruby
- concatenative
- programming
type: article
toc: true
-----
A while ago, I sat down examining a few "alternative programming languages":http://www.h3rald.com/articles/10-programming-languages I might decide to learn someday. Each of those languages has its own peculiarities, and I didn't choose them randomly, I chose them based on their popularity, power, paradigm and how actively they are developed.

I included "Factor":http://factorcode.org/ as the only representative for _concatenative programming_, an interesting way to write programs, but seldom used in "recent" languages (except for Factor and a few others).

h3. The Joy of concatenative programming

If you have absolutely no clue on what I'm talking about, you should consider looking at the home page for the "Joy Programming Language":http://www.latrobe.edu.au/philosophy/phimvt/joy.html, or maybe just the "overview":http://www.latrobe.edu.au/philosophy/phimvt/joy/j00ovr.html: it should be enough to tikle your curiosity.

Joy is often considered the _canonical_ concatenative programming language: a basic —but working— implementation of a simple programming language to illustrate the fundamentals of concatenative programming. Joy looks like this:

@2  3  +  dup  *@

This simple programs computes the sum of 2 and 3, pushes it on the stack, duplicates it (using the @dup@ combinator) and then multiplies the two values, obtaining 25 as a result.

Let's slow down a second. Here's what happens, exactly:

|_. Element entered |_. Stack contents|
| 2 | [2] |
| 3 | [2 3] |
| + | [5] |
| dup | [5 5] |
| * | [25] |

Got it? Let's take it one step further. When you enter @dup@ and then @*@, you are effectively computing the square of a number, so we can define the function @square@ simply as:

@square == dup *@

In Ruby, this would be:

<% highlight :ruby do %>
def square(x)
  x*x
end
<% end %>

What's unusual here? &mdash; Simple, there are no _variables_ involved. Joy doesn't need any explicit variable or _formal parameters_ of any sort.

There's more. Take the following code:

@[1 2 3 4]  [dup *]  map@

The @map@ combinator expects a list and a _quoted program_ (the same one used to compute the square) and produces a new list containing the result of that program applied to each element of the original list. Basically the equivalent of:

<% highlight :ruby do %>
[1,2,3,4].map { |e| e*e }
<% end %>

Do you notice anything different? &mdash; Yes, Joy doesn't need blocks or lambdas either, it uses _quoted programs_ instead, which are nothing but slightly fancier lists (or arrays, as you like).

Let's recap then, Joy doesn't need of:

* lambda functions or blocks (quotation does the trick)
* explicit parameters (everything you need is on the stack)
* variable assignments (same as above)
* explicit recursion (provided you can use combinators like linrec, primrec, binrec, etc.)

I would consider this one of the best examples of _programming minimalism_: an incredibly simple syntax, a very small set of rules, but a good deal of power.

h3. Ruby objects on the stack

After reading about Joy, I realized that implementing something similar in Ruby would be an interesting mini-project (let's say a week of lunch breaks) to understand more about concatenative programming. It would also be pointless, too: a stack-based programming language implemented on top of one of the most high-level programming languages you can find isn't going to be fast, is it? Nevertheless, it would still be interesting.

Ruby offers everything you need to build a Joy-like DSL:

* You can use arrays as ...arrays, but also as quoted programs, and to model the stack itself.
* You can use integers, strings, etc. as themselves
* You can use Symbols as functions (we'll get to this in a minute)

If you think about the following expression in postfix notation:

@2 2 +@

We _could_ translate it into infix notation (@2 + 2@), because Ruby supports it, but it's not general enough. What you could do is this though:

<% highlight :ruby do %>2.send(:+, 2)<% end %>

Message sending. I can see all the SmallTalk sympathizers drooling already. Well yes, In Ruby, _everything_ is an object, so _everything_ has a receiver and maybe some parameters. In other words, every method call can be reduced to the following syntax:

<% highlight :ruby do %>receiver.send(method, *params)<% end %>

In this way, it is safe to assume that everything has a receiver, which could be understood as a function parameter, and may have 0 or more parameters. Take the following then:

<% highlight :ruby do %>[2, 2, :+]<% end %>

It's not too different from Joy, and it's still Ruby code. All you have to do is use something to do the following:

* Take an array, and examine each item:
** If it's an object (non-Symbol), then push it on top of the stack.
** If it's a Symbol, then do something different, i.e.:
*** Find its receiver and its parameters and call a method.
*** Manipulate something on the stack.

In this case, we have to find :+'s receiver and its parameter and we're sorted. 

Unfortunately Ruby's @arity@ method isn't that reliable. For example: @"test".instance_method(:sub).arity@ returns -1, while it should return "2" to be useful. So we have no choice but find a way to pass the method's arity explicitly, in some cases.

For example like this:

<% highlight :ruby do %>
["Ciao, Fabio", /Ciao/, "Hello", :sub|2]
<% end %>

If we define a | operator for the Symbol class, it's not too bad after all. It's heavy, but in this way we can use _any_ Ruby method in postfix notation.

h3. Introducing the Concatenative Ruby DSL

"Concatenative":/concatenative is a simple Ruby DSL for concatenative programming. You can write concatenative programs inside ordinary Ruby arrays and execute them by calling either @Array#execute@ or @Kernel#concatenate@, like this:

<% highlight :ruby do %>
require 'concatenative'

concatenate(
  10,
  [0, :==],
  [1, :+],
  [:dup, 1, :-],
  [:*],
  :linrec
 )
<% end %>

This simple program calculates the factorial of 10. As you can see, no matter how unusual it may look, it is perfectly valid Ruby code and it is equivalent to the following Joy code:

<code>
10 [0 =] [1 +] [dup 1 -] [*] linrec
</code>

Granted, Joy looks better, but that's the tradeoff for not writing a parser for Joy syntax, after all. 
Looking at the code above, there are a few things to keep in mind when programming with Concatenative:

* You are using Ruby arrays, so you have to use commas, at least
* functions, operators and combinators (let's just call them _words_) are available as Ruby symbols
* The arity of all Ruby infix operators has been already set to "1" by concatenative using the @set_arity@ method (which simply stores the arity of a particular symbol in a constant hash)
* You can specify explicit arities using the | operator (@:gsub|2@, or @:join|1@)
* Unless the arity has been specified, an arity of 0 is assumed.
* You can define your own concatenative functions using the @Symbol#<=@ method, which expects a quoted concatenative program.

h3. Performance issues

In its current form, Concatenative can be very slow, as show the "benchmarks" provided in the /examples folder, especially if you use recursive combinators. This is understandable because everything is implemented in pure Ruby, which is totally unsuitable for low level stuff.

If you are interested, you are more than welcome to submit patches and suggestions to improve Concatenative's performance, or, if you feel brave enough, you could help me create a C extension instead: things would become much faster then.

At any rate, feel free to play with it. You can get the source from "GitHub":http://github.com/h3rald/concatenative/tree/master, you can get the gem from "RubyForge":http://rubyforge.org/projects/concatenative/ and you can submit ticket through "GitHub":http://github.com/h3rald/concatenative/issues as well.