Isotopical Blog

Ruby has better support for lambdas than most “mainstream” languages, but it’s missing one important feature — a way to reference the lambda itself. Not being able to reference itself makes recursion using a lambda somewhat difficult. For example, say I wanted to define factorial using a recursive lambda. A lot of rubyists would suggest using self.

lambda{|n| n.zero? ? 1 : n * self.call(n-1)}

Unfortunately, self is evaluated in the context of the calling block, so it doesn’t return the lambda as you might hope; it returns main or whatever context you’re calling the lambda from, usually resulting in an error, or at least not what you were hoping for. The only way, as far as I can tell, to reference the lambda is by assigning it to a variable:

fac = lambda{|n| n.zero? ? 1 : n * fac.call(n-1)}

Again, this is not ideal. Not only does it pollute the calling context, it relies on the variable name it’s assigned to. It works, but it’s ugly. The only solution I’ve been able to come up with is to wrap it in another lambda:

# Ruby 1.8.7
lambda{|n| (fac=lambda{|n| n.zero? ? 1 : n * fac.call(n-1)}).call(n) }
# Ruby 1.9
->(n){(fac=->(n){n.zero? ? 1 : n * fac.(n-1)}).(n)}

This is better from a purity standpoint, but it’s still ugly code. I’ve heard talk of some way to reference the current block in upcoming versions of Ruby, but I haven’t been able to find any concrete information on the subject. If anyone has news, let me know.

Update 2008-10-06 20:42

Apparently what I was looking for here is the Y combinator. Nex3 does a far better job of explaining it than I could hope to, but here’s the code to make it happen:

def Y
  lambda { |f| f.call(f) }.call(
    lambda do |g|
      yield(lambda { |*n| g.call(g).call(*n) })
    end)
end

Y { |this| lambda { |n| n == 0 ? 1 : n * this.call(n - 1) } }.call(12) #=> 479001600

Thanks to sjs for pointing this out.

With Ruby 1.9 sneaking up on us, it’s probably time to start getting excited about new features, so here goes. Ruby 1.9 has a completely new syntax for lambdas that maps perfectly onto actual lambda calculus.

Crash course in lambda calculus: Generally speaking, expressions are specified as “(λ parameters. result) argument”, everything is left-associative, and functions are called like “f v”, where f is a function and v is a value (or a function…) Thus, the expression:

(λ f. f 3) (λ x. x + 2)

evaluates to 5, since the expression on the left consumes a function and calls it with the value 3, while the expression on the right returns its argument plus two. Note that referring to values and functions as two distinct concepts here is technically incorrect, but helps to explain what happens. To do the same thing in Ruby 1.8.7, one would write:

# Ruby 1.8.7
lambda{|f| f[3]}[lambda{|x| x+2}]

In Ruby 1.9, some new syntactic sugar has been added:

# Ruby 1.9
->(f){f.(3)}.(->(x){x+2})

The “->” is supposed to be read as a lambda (λ), since relying on unicode characters in code is generally bad news. Not only is this significantly less syntactic overhead than the equivalent code in 1.8.7, it feels less like an ugly hack and more like an acutally-supported feature.

# λ x. x
->(x){x}

I hope this new lambda syntax encourages more people to write ruby with a more functional style. At the moment, it’s certainly an underused ‘facet’ of ruby.

Randall Munroe of XKCD fame has said on multiple occasions that he chose the name XKCD mostly at random, considering only that it’s an unpronounceable combination of letters that hadn’t been previously used in any significant way. I’m not so sure. I’m apparently not the first one to realize this, but if you take A=1, B=2, and so on, adding up the values of XKCD gives 42.

I figured this out while I was playing around with Reg Braithwaite’s wonderful String#to_proc library. Here’s the code I used.

[?x,?k,?c,?d].map(&'_-96').fold(&'+')

In short, this generates an array of the ascii values for the letters x, k, c, and d, converts them from a=97 to a=1, then sums them. Unlike Symbol#to_proc, which is standard in recent versions of ruby, String#to_proc substitutes underscores with the current value.