Alright, so here is the problem to solve. What if you want to make a recursive lambda method. Put in a more Ruby-esque way, how would I make a recursive block. The other goal of this is to try and keep it as clean as possible (zero variables or side-effects, if possible).

Even some Ruby programmers might be be aware of the Object#lamba method in Ruby. Its basically a shortcut for this.

def lambda(&block)
  Proc.new(block)
end

Its just an easy way to create a Proc. So, lets get down and define the code that should work if we can have recursive lambda's. We'll call this new lambda-like method "reclambda" for recursive lambda.

countdown = reclambda do |this, counter|
  puts counter
  this.call(counter - 1) if counter > 1
end

countdown.call(5)

This should print out the numbers 5 through 1. So, it works just like lambda, except you magically get passed back a reference of yourself to work with. You have to think about that for a minute to get why that's unique. You have to get a reference, in the middle of defining a method, for that method itself. All without it having a name. Completely anonymous. To prove its anonymous, this would have to work also.

(reclambda do |this, counter|
  puts counter
  this.call(counter - 1) if counter > 1
end).call(5)

As you can see in this version, we never even have the Proc touch down for a second. It is never stored anywhere. Its created then executed, and while we do that, we are calling ourselves.

See the exact problem with this? Here is my first (and favourite) solution.

def reclambda &block
  this = Proc.new { |*args| block.call(this, *args) }
end

Ok, there is a dirty little trick in this one. It does require one assignment. What you may or may not know is that Proc's are bound the moment they are created to the scope that they are created in. However, not the values in that binding. Just, a reference to the thing itself. So, when the left hand side (the Proc.new part) is first looked at, it isn't executed, but just noted that its binding is this method... and then the Proc is assigned to this, and then finally it is returned to the caller of #reclambda and THEN asked to execute. This order is crucial. And also sheds some light into Proc's. When right before we execute the wrapping Proc with #call(5) in our bit of test code, the definition of the Proc is set to "this", but the execution hasn't occurred only the binding. That is how this bit of black magic survives. We use something in a proc, that is created after the proc is created, but before it is called. Funky, eh?

I was told by Nathan Weizenbaum (the one who gave me the challenge) that setting a variable is cheating. He said "Don't set any"..... so I came up with a more devious solution.

class RecursiveProc < Proc
  alias old_call call
  def call(*args)
    self.old_call(self, *args)
  end
end

def reclambda &block
  RecursiveProc.new { |*args| block.call(*args) }
end

I create a new variation on Proc, that simply chains onto the old Proc#call method and passes a literal reference to the Proc object itself... via self. Then, I simply wrap the block in a RecursiveProc and wait for it to call me... to which I will pass in this.

However, expected, I was told that modifying the environment to support this ruined the academic solution. Oh bahhumbug! I knew that Nathan had something up his sleeve. Here is the functionally-inspired version.

def reclambda
  lambda do |f|
    f.call(f)
  end.call(lambda do |f|
             lambda do |this|
               lambda do |*args|
                 yield(this, *args)
               end
             end.call(lambda do |x|
                       f.call(f).call(x)
                      end)
           end)
end

....I was going to explain this. But, my brain can only explain it by stepping through it. I wish I had my functional neuron's better trained. However, he did win. This does indeed do the same thing, except he never modifies the environment.

Bravo!

However, it is to be noted that Ruby trunk currently has a way to get a reference to yourself if you're a block of any type.

Anybody else got a try in #{FAVORITE_LANGUAGE}?