Y Combinator in Ruby, Take 2

y.rb

# Y Combinator in Ruby, Take 2
#
# Based off an explanation of Y Combinator here:
# http://article.gmane.org/gmane.comp.lang.perl.perl-mongers.boston/1518
#
# Also inspired by this post from nex3:
# http://nex-3.com/posts/43-fun-with-the-y-combinator-in-ruby 

# Here's an explanation of the Y-Combinator.  It won't work in
# Perl because Perl doesn't do lexical binding of input
# parameters.  JavaScript does and most should know that, so
# I'll do it in JavaScript.
# 
# Our goal is to be able to write a recursive function of 1
# variable using only functions of 1 variables and no
# assignments, defining things by name, etc.  (Why this is our
# goal is another question, let's just take this as the
# challenge that we're given.)  Seems impossible, huh?  As
# an example, let's implement factorial.
# 
# Well step 1 is to say that we could do this easily if we
# cheated a little.  Using functions of 2 variables and
# assignment we can at least avoid having to use
# assignment to set up the recursion.

# X = function (recurse, n) {
#   if (0 == n)
#     return 1;
#   else
#     return n * recurse(recurse, n - 1);
# };
# 
# // This will get X to recurse.
# Y = function (builder, n) {
#   return builder(builder, n);
# };
# 
# // Here it is in action.
# Y(
#   X,
#   5
# );

x = lambda do |recurse, n|
      if (0 == n)
          1
      else
          n * recurse.call(recurse, n-1)
      end
    end

y0 = lambda do |builder, n|
        builder.call(builder, n)
    end

puts y0.call(x,5)

# Now let's see if we can cheat less.  Well firstly we're using
# assignment, but we don't need to.  We can just write X and
# Y inline.
# 
#   // No assignment this time.
#   function (builder, n) {
#     return builder(builder, n);
#   }(
#     function (recurse, n) {
#       if (0 == n)
#         return 1;
#       else
#         return n * recurse(recurse, n - 1);
#     },
#     5
#   );

y1 = lambda do |builder, n|
  builder.call(builder, n)
end.call(lambda do |recurse, n|
  if (0 == n)
      1
  else
      n * recurse.call(recurse, n-1)
  end
end, 5)

puts y1

# But we're using functiions of 2 variables to get a function of 1
# variable.  Can we fix that?  Well a smart guy by the name of
# Haskell Curry has a neat trick, if you have good higher order
# functions then you only need functions of 1 variable.  The
# proof is that you can get from functions of 2 (or more in the
# general case) variables to 1 variable with a purely
# mechanical text transformation like this:
# 
#   // Original
#   F = function (i, j) {
#     ...
#   };
#   F(i,j);
# 
#   // Transformed
#   F = function (i) { return function (j) {
#     ...
#   }};
#   F(i)(j);
# 
# where ... remains exactly the same.  (This trick is called
# "currying" after its inventor.  The language Haskell is also
# named for Haskell Curry.  File that under useless trivial.)
# Now just apply this transformation everywhere and we get
# our final version.
# 
#   // The dreaded Y-combinator in action!
#   function (builder) { return function (n) {
#     return builder(builder)(n);
#   }}(
#     function (recurse) { return function (n) {
#       if (0 == n)
#         return 1;
#       else
#         return n * recurse(recurse)(n - 1);
#     }})(
#     5
#   );

y = lambda do |builder|
  lambda do |n|
    builder.call(builder).call(n)
  end
end.call(lambda do |recurse|
  lambda do |n|
    if (0 == n)
        1
    else
        n * recurse.call(recurse).call(n-1)
    end
  end
end).call(5)

puts y

# You can replace the 4 lines that recursively define factorial with
# any other recursive function that you want.
#

def Y0(&blk)
lambda do |builder|
  lambda do |*args1|
    builder.call(builder).call(*args1)
  end
end.call(blk)
end

f0 = Y0 do |recurse|
  lambda do |n|
    if (0 == n)
        1
    else
        n * recurse.call(recurse).call(n-1)
    end
  end 
end

puts f0.call(5)

#
# The code isn’t really what we were going for, though. We had to modify the
# body of the factorial function to make it work.
# 

def Y1(&blk)
  lambda do |builder|
    lambda do |*args1|
      builder.call(builder).call(*args1)
    end
  end.call(blk)
end

f1 = Y1 do |g|
lambda do |this|
  lambda do |n|
    if (0 == n)
        1
    else
        n * this.call(n-1)
    end
  end
end.call(lambda { |n| g.call(g).call(n) })
end

puts f1.call(5)

# Cleaning up

def Y(&blk)
  lambda do |builder|
    lambda do |*args1|
      builder.call(builder).call(*args1)
    end
  end.call(lambda do |g|
      yield(lambda { |*args2| g.call(g).call(*args2) })
  end)
end

f = Y do |this|
  lambda do |n|
    if (0 == n)
        1
    else
        n * this.call(n-1)
    end
  end
end

puts f.call(5)