raganwald
(This is a snapshot of my old weblog. New posts and selected republished essays can be found at raganwald.com.)

Tuesday, February 06, 2007
  Guest Blogger: Tom Moertel derives the Y combinator in Ruby


In a comment on But Y would I want to do a thing like this?, Tom Moertel derived an elegant version of the actual Y combinator in Ruby. I reproduce his words here with permission.

Tom uses the alternate syntax for
call, [...]. I avoided this to keep clear of a tiresome debate about operator overloading. (On one side: those who hate it. On the other side: those that hate Ruby disallowing overloading (...)).

Ok Tom, take it away!



Here’s my original Ruby definition:

def y(&f)
lambda { |*args| f[y(&f)][*args] }
end


To get rid of the recursive call y(&f), let’s replace it with a variable yf, whose value we’ll say is magically equivalent to the result of the recursive call. To effect the binding of yf, we’ll need to wrap the method body in a new lambda expression and pass in the magic value:

def y(&f)
lambda { |yf|
lambda { |*args| f[yf[yf]][*args] }
}[ <<< placeholder for yf: we'll fill this hole next >>> ]
end


So, what value should we pass in for yf? Because the variable represents the value that would have been computed by calling y(&f), which is just the body of the y method, we can fill the hole with a duplicate of the body:

def y(&f)
lambda { |yf|
lambda { |*args| f[yf[yf]][*args] }
}[ lambda { |yf| lambda { |*args| f[yf[yf]][*args] } } ]
end


And we have our Y combinator:

fac = y { |rec| lambda { |n| n < 2 ? 1 : n * rec[n-1] } }
fac[5] # ==> 120


While the combinator works, its implementation repeats itself: there are two copies of the lambda expression

lambda { |yf| lambda { |*args| f[yf[yf]][*args] } }


in the method body. To factor them out, let’s let the variable x represent this expression. Then the method body simplifies to x[x], which is very satisfying. To set x to the correct value, however, we need to add a wrapper lambda that binds x to the original expression. Putting it all together, we arrive at the final version:

def y(&f)
lambda { |x| x[x] } [
lambda { |yf| lambda { |*args| f[yf[yf]][*args] } } ]
end


And it, too, works:

acc_fac = y { |rec| lambda { |n,acc| n < 2 ? acc : rec[n-1, n*acc] } }
tail_fac = lambda { |n| acc_fac[n, 1] }
tail_fac[5] # ==> 120


Cheers! —Tom

Labels: ,

 

Comments on “Guest Blogger: Tom Moertel derives the Y combinator in Ruby:
Here is another derivation of Y combinator in JavaScript: http://blog.csdn.net/g9yuayon/archive/2006/09/24/1271319.aspx.

It's written in Chinese, but the code speaks for itself. :-)
 
I think I finally understand this Y Combinator thing now. Hooray. So I explained it in my words.
 




<< 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 /