Why Ruby is not an acceptable implementation of Lisp

The other day, while actually writing software (as opposed to talking about writing software), I wrote the following:

distance = lambda do |given_scale|
  (magnitudes.map { |pair| 
    (pair.evidence - (pair.flow * given_scale)) ** 2 
  }).inject { |acc, distance| acc + distance }
end

If you are curious, distance is a function that computes the distance between a curve (called a ‘flow’) and some evidence, given a float that scales the flow. It’s used for finding a curve that ‘looks like’ a set of data points.

Can you spot the bug? I’ll expunge all of the excess and give you some code you can try yourself:

require 'test/unit'

class TestRubyNames < Test::Unit::TestCase

  def test_lambda_clobbering
    foo = lambda { (1..3).map { |foo| foo ** 2 } }
    assert_nothing_raised(NoMethodError) { foo.call() }
    assert_raise(NoMethodError) { foo.call() } # WTF?
  end

  def test_local_clobbering
    foo = [1, 4, 9]
    bar = lambda { (1..3).map { |foo| foo ** 2 } }
    bar.call
    assert_equal(3, foo) # WTF?
  end

end

Is this what you expect? Ruby looks like a nice, block-structured language with lexical scope. But its standard implementation has serious issues. I believe these are well-known and understood issues, but issues nonetheless.

One more example. I swore I wouldn’t write anything else about fixed-point combinators for a very long time, but try this exercise at home. Here’s my curry combinator:

require 'test/unit'

class ExempliGratia < Test::Unit::TestCase

  CURRY = lambda { |f, a| lambda { |*b| f.call(a, *b) } }

  def test_clean_up_loose_ends
    maker = lambda { |f|
               lambda { |func_with_me| CURRY.call(func_with_me, func_with_me) }.call(
                    CURRY.call(lambda { |inner_func, me, *args|
                                inner_func.call(CURRY.call(me, me)).call(*args) }, f)) }

    factorial = maker.call(
      lambda { |f| lambda { |n| n.zero? && 1 or n * f.call(n-1) } }
    )
    assert_equal(120, factorial.call(5))
  end

end

Looks good. Now let’s prove that CURRY is referentially transparent by replacing every CURRY variable with the lambda:

maker = lambda { |f|
           lambda { |func_with_me| (lambda { |f, a| lambda { |*b| f.call(a, *b) } }).call(func_with_me, func_with_me) }.call(
                (lambda { |f, a| lambda { |*b| f.call(a, *b) } }).call(lambda { |inner_func, me, *args|
                            inner_func.call((lambda { |f, a| lambda { |*b| f.call(a, *b) } }).call(me, me)).call(*args) }, f)) }

factorial = maker.call(
  lambda { |f| lambda { |n| n.zero? && 1 or n * f.call(n-1) } }
)

begin
  factorial.call(5)
  puts 'fine'
rescue SystemStackError
  puts 'wtf?'
end

Hunh? Ruby looks like a nice language supporting anonymous functions, but sometimes they work and sometimes they don’t. I strongly suspect that this issue has something to do with the fact that with the ‘naked’ lambdas we’re creating new functions with every call, whereas the version using a CURRY variable re-uses the same function, so the system stack overflows in one case and not the other.

Update: Mike Harris proved that this second problem is the same as the first problem: once again, variables are clobbering each other all over the place. In Ruby 1.8, blocks do not create new scope, at all.

Here's Mike's submission, indented to fit:

def test_full_anonymity
  assert_equal(120, (lambda { |f0|
                       lambda { |func_with_me| 
                         (lambda { |f1, a1| 
                           lambda { |*b1| f1.call(a1, *b1) } 
                         }).call(func_with_me, func_with_me) 
                       }.call(
                            (lambda { |f2, a2| 
                              lambda { |*b2| f2.call(a2, *b2) } 
                            }).call(
                              lambda { |inner_func, me, *args|
                                inner_func.call(
                                  (lambda { |f3, a3| 
                                    lambda { |*b3| f3.call(a3, *b3) } 
                                  }).call(me, me)).call(*args) 
                              }, f0)) 
                    }).call(
    lambda { |f| lambda { |n| n.zero? && 1 or n * f.call(n-1) } }
  ).call(5))
end

Stop your sobbing

I’m not saying Ruby is an unacceptable Ruby.

I’m especially not saying “See, that’s why we should stick with language X.” If language X doesn’t even try to support this kind of programming, it’s a lame argument to say that it’s a better choice. That’s like saying that your 1972 Pinto is safer than my 2004 MX-3 because the Pinto doesn’t have air bags, and air bags can injure small children if they are sitting in the passenger seat.

If you try to bend Ruby to do Scheme-ish things, you will run into some corner cases, some places where it does the unexpected. Can you figure them out and avoid them (some people will say avoiding corner cases makes for a Leaky Abstraction)?

I think if you’re writing Ruby code in Ruby, you can easily avoid these problems. That’s why Ruby is an acceptable Ruby.

Why isn’t Ruby an acceptable implementation of Lisp?

But why isn’t Ruby an acceptable implementation of Lisp? (Besides the lack of support for hygienic macros, of course!)

The problem is that Lisp or Lisp-style programming is all about metaprogramming. Code that writes code. Code that evals code. It’s easy to look at something like the curry combinator and say “no programmer would ever write that convoluted a function in production.” But macros and code generators routinely combine snippets of code to produce monstrosities that a human wouldn’t even considering writing.

When writing a piece of code that writes code, you are heavily dependent on the underlying implementation being regular and corner-case free. The whole point of writing code-writing code is that you intend for it to generate variations and combinations on your templates or scaffolds. And it’s only a matter of time before you are combining template A with generator B and meta-programming method C.

When the underlying language is robust, none of this matters. The result works. If you look at it under the hood, you’re horrified at the result. But frankly, that isn’t an argument against meta-programming, it’s an argument for it: let the machine do the dirty jobs we don’t want to do, and let us deal with a nice abstraction like A plus B plus C that just works, never mind what the code looks like.

(Don’t even think about arguing that we should do away with code that writes code. That debate was won by the code generation folks back when COBOL and FORTRAN and ALGOL were young. From time to time you’re welcome to pull out your assembly if you like, but we use High Level Languages because we want the machine to write the messy crap for us.)

My fear is that code that writes code might one day write code that clobbers a variable. Or code that writes code might write some nested lambdas that overflow the stack.

And that’s why Ruby is not an acceptable implementation of Lisp.

---

Well, ok, I confess: the title is a bit of muckraking. Ruby is a pretty good implementation of Lisp, and anyone who has two brains to rub together can point out that the issue is not whether there’s some corner case “gotcha,” but whether using Ruby is, on the whole, more beneficial than not using Ruby.

For what it’s worth, I consider corner cases like this a strong endorsement of trying new languages like Ruby: it’s like finding out that your sailplane has a tendency to go into an inverted flat spin when you loop at an unacceptably slow speed. It’s terrifying when it first happens, but you get through it and then you realize that the only reason you got into trouble was that you were pushing yourself hard.

Labels: lispy, ruby

  ¶ 3:03 PM