raganwald
Wednesday, February 07, 2007
  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




Programming Ruby: The Second Edition is an indispensable reference, especially to the latest libraries.

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!)



On Lisp: Advanced Techniques for Common Lisp is the definitive text on metaprogramming and macros. Although written for Common Lisp, its ideas are easily applicable to Scheme and even Ruby metaprogramming.

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: ,

 

Comments on “Why Ruby is not an acceptable implementation of Lisp:
Instead of a comment, how about soliciting some advice?!

I love your blog and the topics you cover. I'm pretty into code generation (if you're interested in generating and refactoring active data model based DSLs by simply modifying the documented abstract grammar of your DSLs, I'm your guy!).

That said, I wouldn't really consider myself much of a programmer having misspent most of my youth running everything from a psychotherapy practice to an ad agency. I wrote a simple IoC/DI framework in ColdFusion in 300 lines of code using mixins, but when people start to talk about lambdas, currying and closures my brain starts to fog!

And so to the questions. I've written in various shades of assembler, learn to hack in Basic and C, learnt to program in Pascal, and have delivered projects in VB4, ColdFusion4-7, classic ASP and a little bit of .NET (c#).

I want to expand my mind, so I'm looking at Lisp (probably Common Lisp), Haskell, and maybe some SmallTalk to enrich my brain and probably Ruby to augment my toolkit.

I would love to actually learn something that would allow me to generate cooler, more functional web applications in less time fairly quickly (still have to pay the bills) and would appreciate any suggestions you might make about how a poor old harassed PHB might better himself adding the most value to his brain in the least time.

Any thoughts much appreciated!
 
why not spend some time fixing your css ;)
 
Yes, it looked very ironic when the text flowed into the sidebar and then a few lines down telling us to spot the bug!
 
The broken case with the curry is another scoping issue (maybe the same one), due to the repeated declarations of f, a and b. If you replace with distinct names, the function works.

The initial_case can be shown with a reduced example

foo = [1,4,9]
(1..3).map { |foo| nil }
puts foo #3
 
The first test case produces exactly the expected behavior.

Let's rewrite it with proc instead of lambda for a second to remove confusion. proc creates a closure over a scope with mutable variables. The code does what it says, it changes foo.

So the two questions are, why did Ruby decide to call procs lambdas? any why does Ruby not have lambdas of lambda-calculus?

The second example I skipped, that's the kind of code that if I ever had to read, I would flat out rewrite into something more maintainable.

The issue with code is not when it works, but when it fails. And when you're at the fifth level of abstraction, and something fails down underneath, then it's FORTH all the way down!

Is Ruby a better Lisp? Depends on your definition of "better". When it comes to pure form, I don't think so, I think it's a worse Lisp. But then again, it's one of those cases where worse is better.

For some people.
 
Ruby metaprogramming is a delicate art, if you want to stay out of a "flat spin." You can't just translate Lisp code verbatim to Ruby, and expect it to work perfectly.

But oftentimes, you can sneak up on the same problem from a different direction, using Ruby's native metaprogramming features.

I've had the best luck using test-driven design and refactoring when doing Ruby metaprogramming. I can't just design something in my head and write it down; it needs to grow organically.

I have a bunch of Ruby metaprogramming examples which I'll post on my blog at some point. But as you know, there's a bit of a queue...
 
The broken case with the curry is another scoping issue (maybe the same one), due to the repeated declarations of f, a and b. If you replace with distinct names, the function works.

Awesome insight, thanks!!!

I will update the text of the article as soon as I've tested the result.
 
it looked very ironic when the text flowed into the sidebar and then a few lines down telling us to spot the bug!

Q: How many programmers does it take to change a light bulb?

A: The light works in development!

Aren't you using a 30" Apple Cinema display???

That being said, code samples do not word wrap, although text does. I thought about the problem, and the best answer is probably to reformat the code to fit in a narrower column.

I'll try to get to that, thanks!
 
Ruby metaprogramming is a delicate art, if you want to stay out of a "flat spin." You can't just translate Lisp code verbatim to Ruby, and expect it to work perfectly.

But oftentimes, you can sneak up on the same problem from a different direction, using Ruby's native metaprogramming features.


I think we're in violent agreement!
 
I would love to actually learn something that would allow me to generate cooler, more functional web applications in less time fairly quickly (still have to pay the bills) and would appreciate any suggestions you might make about how a poor old harassed PHB might better himself adding the most value to his brain in the least time.

I would start my search over at programming.reddit.com.

You can post your question as an "Ask Reddit:" if you like. Others have posted similar questions. Try this search and see if any of the results are interesting.

Good luck, and email me if you have trouble getting a good answer. You know my first name is "reg" and you know my domain!
 
Thanks - I'll go get searching!
 
anyone who has two brains to rub together

I'm damn near certain you mean two brain cells. Although if you really do expect the average human to have more than one brain, that would explain your blog pretty succinctly.

Anyway, there was a "why Ruby is an acceptable Lisp" a while back, I'm glad to see this as a counter-arg. My Lisp-fu still needs developing, but looking at Lisp/Ruby translation attempts seems to result in a better understanding of Ruby's innards.
 
The broken case with the curry is another scoping issue (maybe the same one), due to the repeated declarations of f, a and b. If you replace with distinct names, the function works.

I've tried that, and so far it doesn't work, although I am now getting different errors.

If you've tried it and gotten it to work, can you email or post your code?

Perhaps I have a PBKAC?
 
To fix the problem with code overflowing into the sidebar, just add this to your CSS:

pre code {
display: block;
overflow: auto;
}

That will give you a horizontal scroll bar on just the code block when necessary.
 
Don't know if I can do anything about the formatting. Paste into your text editor of choice

class ExempliGratiaNoCurryVariableOrMethod < Test::Unit::TestCase

def test_clean_up_loose_ends
maker = 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)) }

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

end
 
This problem is fixed in 1.9 -- blocks are lexically scoped.
 
Compilers generate code that nobody is ever expected to see. Except a few gurus in debugging. I've used machine-level debuggers on compiled C code. Trust me, you don't want to do it.

It ain't the same thing as lisp generating lisp.

People used to write assembler programs that modified themselves at run time. It was never re-entrant, of course.

There are different kinds of code gen. So your argument "Don't even think of arguing against generated code" doesn't work.

I'm sure C compilers are tested more thoroughly than lisp coders test their macros.
 




<< Home
Reg Braithwaite


Recent Writing
Homoiconic Technical Writing / raganwald.posterous.com

Books
What I‘ve Learned From Failure / Kestrels, Quirky Birds, and Hopeless Egocentricity

Share
rewrite_rails / andand / unfold.rb / string_to_proc.rb / dsl_and_let.rb / comprehension.rb / lazy_lists.rb

Beauty
IS-STRICTLY-EQUIVALENT-TO-A / Spaghetti-Western Coding / Golf is a good program spoiled / Programming conventions as signals / Not all functions should be object methods

The Not So Big Software Design / Writing programs for people to read / Why Why Functional Programming Matters Matters / But Y would I want to do a thing like this?

Work
The single most important thing you must do to improve your programming career / The Naïve Approach to Hiring People / No Disrespect / Take control of your interview / Three tips for getting a job through a recruiter / My favourite interview question

Management
Exception Handling in Software Development / What if powerful languages and idioms only work for small teams? / Bricks / Which theory fits the evidence? / Still failing, still learning / What I’ve learned from failure

Notation
The unary ampersand in Ruby / (1..100).inject(&:+) / The challenge of teaching yourself a programming language / The significance of the meta-circular interpreter / Block-Structured Javascript / Haskell, Ruby and Infinity / Closures and Higher-Order Functions

Opinion
Why Apple is more expensive than Amazon / Why we are the biggest obstacles to our own growth / Is software the documentation of business process mistakes? / We have lost control of the apparatus / What I’ve Learned From Sales I, II, III

Whimsey
The Narcissism of Small Code Differences / Billy Martin’s Technique for Managing his Manager / Three stories about The Tao / Programming Language Stories / Why You Need a Degree to Work For BigCo

History
06/04 / 07/04 / 08/04 / 09/04 / 10/04 / 11/04 / 12/04 / 01/05 / 02/05 / 03/05 / 04/05 / 06/05 / 07/05 / 08/05 / 09/05 / 10/05 / 11/05 / 01/06 / 02/06 / 03/06 / 04/06 / 05/06 / 06/06 / 07/06 / 08/06 / 09/06 / 10/06 / 11/06 / 12/06 / 01/07 / 02/07 / 03/07 / 04/07 / 05/07 / 06/07 / 07/07 / 08/07 / 09/07 / 10/07 / 11/07 / 12/07 / 01/08 / 02/08 / 03/08 / 04/08 / 05/08 / 06/08 / 07/08 /