A Ruby Mockingbird

As noted in “Going static with Middleman,” I have a fair bit of work ahead to rebuild my personal website.

This is part of that work.

Ruby is not usually regarded as—or employed as—a functional programming language. Yet Ruby does support a fair bit of functional programming, and has a small community of programmers actively investigating functional techniques in Ruby. We’ll examine a simple technique in the following discussion of the Mockingbird, a recursive combinator.

First we need to lay foundation, just a few simple “bricks” of combinatory logic. Define the mockingbird combinator

\[Mx = xx.\]

This might be easier to understand as \(M(x) = x(x)\), that is, the function \(M\) taking \(x\) acts the same as \(x\) applied to itself.

This seems overblown.

But it’s not, and here’s why: since \(x\) is arbitrary, we can concretely define \(M\) to accept an arbitrary function (e.g., \(x\)) and invoke \(x\) on itself. This allows creating anonymous recursive functions, promoting a natural separation of concerns between the function \(x\) that does the work and the mockingbird \(M\) which controls the recursion.

Code!

Here’s a little technique I like to use to reduce code clutter and tighten focus on specific examples: embed the testing with the implementation.

It’s really convenient. The code by itself may be invoked as-is, or the spec may be run by $ rspec mockingbird.rb. A third way is to add an RSpec runner at the end of the file which makes it “self-executing” with respect to the tests. In any case, the implementation and the tests or specs are all together for easy reference.

#!/usr/bin/env ruby

require 'rspec'

def mockingbird x
  x.(x)
end
# But really, this is the M combinator Mx = xx
alias M mockingbird

describe "self" do
  it "blows up the stack with SystemStackError when without a halting condition" do
    y = ->(y) { mockingbird y }
    expect { mockingbird(y) }.to raise_error SystemStackError
  end

  it "raises NoMethodError when not called with a function" do
    y = 1
    expect { mockingbird(y) }.to raise_error NoMethodError
  end

  it "sings like a mockingbird" do
    x = ->(x) { "sing like a mockingbird" }
    expect(mockingbird(x)).to eq "sing like a mockingbird"
  end

  it "satisfies the M combinator definition Mx = xx" do
    x = ->(x) { "I am the Mighty M Combinator" }
    expect(M(x)).to eq x[x]
  end
end

You now have the choice of three ways to spend your time:

  1. (Recommended) Type the code, by hand, into your favorite programming environment and prove to your own satisfaction that it works; or
  2. Cut-n-paste (Lazy! Learn it the hard way!); or
  3. Continue reading along with the best of intentions to “do it later.” (But, you know, “later is a bad habit”).

Regardless of your choice, I have no choice: the narrative must continue.

If you’re a fan of Raganwald or even just a customer who’s purchased his Kestrels, Quirky Birds & Hopeless Egocentrecity, you may notice a slight difference in the definition of the mockingbird \(M\). We’re requiring an argument, Raganwald passes in a block:

def mockingbird &x
  x.call(x)
end

The difference is largely syntactic rather than semantic. The mockingbird accepts a function and invokes that function to duplicate itself. In the version given here, notions of functions and arguments is taken literally in the sense of \(y = f(x)\). But all we really care about is that the mockingbird “functions” (there’s that word again) correctly. In Ruby, we can pass a block to a method to acheive the same result.

However, the syntax does have some ramifications. Passing in a callback as an argument allows testing as shown above. Passing a block does not. On the other hand, in working code, defining a mockingbird to take no arguments and accept a block is probably easier.

If comments are not yet hooked up, and you feel compelled to correct any misconceptions you see in the exposition above, feel free to shoot me an email (david dot doolin at gmail dot com), or a twitter (@doolin) or whatever. I’m happy to make factual corrections, and usually inclined to present alternative arguments.

Finally, yes, there are practical applications. Raganwald demontrates processing nested arrays of integers, which can be generalized to nested lists of any sort of thing which can be processed by some function \(x\). In Ruby syntax, \(x\) being some method, it looks like (&:method).