Hampton Lintorn Catlin

Recursive Lambdas

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}?


Comments

Mar 22, 2007
Nathan Weizenbaum said...
Er... my last name is spelled with a "z". It's pretty simple to translate this to other languages, or at least those with functional components. All it requires is some sort of way of defining anonymous functions. For example, here it is in Common Lisp: (define (reclambda f) ((lambda (x) (x x)) (lambda (g) ((lambda (this) (lambda args (apply f this args))) (lambda (x) ((g g) x)))))) As a side note, I can't really take credit for that solution... it's just the Y combinator translated into Ruby. Alonzo Church really did all the work.
Mar 22, 2007
Justin said...
Hey Nathan, Your Y combinator appears to be written in scheme rather than CL (defun is used to create global function definitions in CL, and define is used in scheme). The equivalent CL is: (defun reclambda (f)   (funcall (lambda (x) (funcall x x))            (lambda (g)              (funcall (lambda (this)                         (lambda (args) (funcall f this args)))                       (lambda (x) (funcall (funcall g g) x))))))
Mar 22, 2007
Justin said...
Hey Nathan,
Your Y combinator is actually written in scheme rather than CL. The equivalent CL function is:
(defun reclambda (f)
   (funcall (lambda (x) (funcall x x))
            (lambda (g)
              (funcall (lambda (this)
                         (lambda (args) (funcall f this args)))
                       (lambda (x) (funcall (funcall g g) x))))))

There's also a single-argument-function version of the Y combinator which has a simpler definition [e.g. in scheme]:
(define (y-comb f)
  ((lambda (x) (x x))
   (lambda (x)
     (f (lambda (y) ((x x) y))))))
Calling this version is more or less the same as calling reclambda, but I prefer the single-argument-function version because it more closely resembles the Y combinator from the lambda calculus.
Mar 28, 2007
C.J. said...
Since the use of reclambda is: fact1 = reclambda(lambda {|f,x| if x < 2 then 1 else x * f.call(x-1) end }) print "fact1(12) = #{fact1.call(12)}\n" I don't how this is any better than: def curry(f,g) lambda {|*args| f.call(g,*args) } end def xx(f) curry(f,f) end fact2 = xx(lambda {|f,x| if x < 2 then 1 else x * f.call(f,x-1) end }) print "fact2(12) = #{fact2.call(12)}\n" Which seems much clearer (and still binds no variables). C.J.
Mar 29, 2007
Nathan Weizenbaum said...
Justin: Right! Of course it's Scheme! Just a brain fart on my part. Also, I based my definition of reclambda closely on the Y combinator; I wanted it in that particular form, though, so that calling it would be simpler. The original idea was to implement anonymous, recursion-capable functions as a Lisp macro without changing the syntax for defining them. C.J.: You're implicitly assigning variables by defining named functions. The idea is to do it without any sort of assignment at all.
Jun 3, 2007
Alex Boisvert said...
With the Scala language (http://www.scala-lang.org), object countdown { def call(counter: Int) : Unit = { Console.println(counter) if (counter > 1) call(counter -1) } } countdown.call(5) and passing the recursive lambda to another function is as simple as: doSomething(countdown.call)
Sep 1, 2007
Brian Adkins said...
Here's a JavaScript implementation of the Y Combinator from Douglas Crockford's site: http://www.crockford.com/javascript/little.html function Y(le) { return function (f) { return f(f); }(function (f) { return le(function (x) { return f(f)(x); }); }); }
Oct 24, 2007
Nik said...
Man you don't even know how long I've waited for this since disabling my own Movable Type widget (that doesn't work since Haloscan bypasses that code).
Jan 8, 2008
paddor said...
At the end of this article you mentioned that there's a possibility in the ruby trunk to get a reference to yourself if you're in a block. How?
Oct 7, 2008
roger faith said...
I also wonder if that "reference to the current block" is in trunk anywhere? Thanks! -=R