• The Joy of concatenative programming
• Ruby objects on the stack
• Performance issues

A while ago, I sat down examining a few alternative 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 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).

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, or maybe just the overview: 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:

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:

def square(x)
  x*x
end

What's unusual here? — 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:

[1,2,3,4].map { |e| e*e }

Do you notice anything different? — 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.

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:

2.send(:+, 2)

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:

receiver.send(method, *params)

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:

[2, 2, :+]

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:

["Ciao, Fabio", /Ciao/, "Hello", :sub|2]

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.

Introducing the Concatenative Ruby DSL

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:

require 'concatenative'

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

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:

10 [0 =] [1 +] [dup 1 -] [*] linrec

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.

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, you can get the gem from RubyForge and you can submit ticket through GitHub as well.