Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Aristotle (5147)

Aristotle
  pagaltzis@gmx.de
http://plasmasturm.org/

Blah blah blah blah blah [technorati.com]

Journal of Aristotle (5147)

Tuesday September 05, 2006
11:38 AM

Adventures in functional Perl programming: the Y combinator

[ #30896 ]

A while ago I read several explanations of the Y combinator in order to understand what it’s for and how it works, but recently, I found that I didn’t really understand it. All the examples are in Scheme, which I can read, but find difficult to grok, so I decided I needed to slog through the derivation using Perl in order to get a real grasp on what’s going on.

The Y combinator has been called “an infuriating construct” and I think you’ll see after this explanation just why that isn’t entirely undeserved.

What is is this Y combinator thing, anyway? It’s a combinator that you need in order to write recursive functions without giving them names.

Let’s look at a typical example of a recursive function:

sub fac {
    my ( $n ) = @_;
    $n < 2 ? 1 : $n * fac( $n - 1 );
}

print fac( 10 );

Now we want to write this function as a single expression so we can inline the definition on the print line, as in print sub { ... }->( 10 ) and get the same result.

First, let’s make it nameless using standard Perl.

my $fac;
$fac = sub {
    my ( $n ) = @_;
    $n < 2 ? 1 : $n * $fac->( $n - 1 );
};

print $fac->( 10 );

Well, that’s not really nameless. Instead of fac the function is now called $fac, but it still relies on a name in a (quasi-)global scope to “find” itself. And it can’t be inlined in a single expression either – a far cry from our goal. Let’s try passing it in as a parameter:

my $fac = sub {
    my ( $f, $n ) = @_;
    $n < 2 ? 1 : $n * $f->( $f, $n - 1 );
};

print $fac->( $fac, 10 );

That’s better, since the function can recurse on itself without the need for a global name, but we still can’t inline it. Worse, now everyone who wants to invoke the function needs to know to pass it to itself. Pay particular attention to the call inside the function: $fac->( $n - 1 ) turned into $f->( $f, $n - 1 ) to make this work.

How to get around that? Well, we could use currying to pass the parameter once and have it remembered thereafter:

my $fac_maker = sub {
    my ( $f ) = @_;
    sub {
        my ( $n ) = @_;
        $n < 2 ? 1 : $n * $f->( $n - 1 );
    }
};

print 'Uh, err, I dunno.';

We have a problem here. We need the closure assigned to $f so that it can recurse on itself properly, but to get it so we can pass it in we need to call the currying closure. And after we have done that, however, the curried closure has already closed over the $f variable in that scope and there’s no way to assign to it anymore. Temporal paradoxon?

Maybe if we pass a different but identical copy of the function?

my $fac = sub {
    my ( $f ) = @_;
    sub {
        my ( $n ) = @_;
        $n < 2 ? 1 : $n * $f->( $n - 1 );
    }
}->( sub {
    my ( $n ) = @_;
    $n < 2 ? 1 : $n * $f->( $n - 1 );
} );

print 'Wait, that doesn\'t compile.';

There is a $f in the copy of the function that’s not defined in any relevant scope. What do we do about that? We supply a scope by include a copy of the currying wrapper.

print sub {
    my ( $f1 ) = @_;
    sub {
        my ( $n ) = @_;
        $n < 2 ? 1 : $n * $f1->( $f1 )->( $n - 1 );
    }
}->( sub {
    my ( $f2 ) = @_;
    sub {
        my ( $n ) = @_;
        $n < 2 ? 1 : $n * $f2->( $f2 )->( $n - 1 );
    }
} )->( 10 );

And that works – great. Oh look! There’s a recursive function there which has no name and it’s inlined with the print!

Pay attention to the $f->( $f ) bit. This is necessary because the copy we pass in has to be curried.

So that’s the general approach; two exact copies of the curried closure. We just need to extract the recursion part from the factorial function. How?

Just like good mathematicians, we will introduce a redundant term. It’s obvious that $f->( $x ) is exactly the same as sub { $f->( @_ ) }->( $x ), right? We will do that for the $f->( $f ) bit. Let’s just do it now and I’ll explain why in a bit.

print sub {
    my ( $f1 ) = @_;
    sub {
        my ( $n ) = @_;
        $n < 2 ? 1 : $n * sub { $f1->( $f1 )->( @_ ) }->( $n - 1 );
    }
}->( sub {
    my ( $f2 ) = @_;
    sub {
        my ( $n ) = @_;
        $n < 2 ? 1 : $n * sub { $f2->( $f2 )->( @_ ) }->( $n - 1 );
    }
} )->( 10 );

OK… now why would we want to do such a thing?! What’s the point of this?

The point is that it’s one closure – the $f->( $f ) bit is tucked away. And since the bit we tucked away doesn’t depend on anything in the inner scope, it can be factored out by currying and passing it in.

print sub {
    my ( $f1 ) = @_;
    sub {
        my ( $rec ) = @_;
        sub {
            my ( $n ) = @_;
            $n < 2 ? 1 : $n * $rec->( $n - 1 );
        }
    }->( sub { $f1->( $f1 )->( @_ ) } )
}->( sub {
    my ( $f2 ) = @_;
    sub {
        my ( $rec ) = @_;
        sub {
            my ( $n ) = @_;
            $n < 2 ? 1 : $n * $rec->( $n - 1 );
        }
    }->( sub { $f2->( $f2 )->( @_ ) } )
} )->( 10 );

Having fun yet? But take careful note of what happened here. Look at the inner scope:

sub {
    my ( $rec ) = @_;
    sub {
        my ( $n ) = @_;
        $n < 2 ? 1 : $n * $rec->( $n - 1 );
    }
}

That looks just like what we want! Note too that it doesn’t contain any mention of $f – that means the outer and inner layer of the big monstrosity above are completely independent of each other. So – wait for it… – we can pass the inner layer in!

print sub {
    my ( $curried_rec ) = @_;
    sub {
        my ( $f1 ) = @_;
        $curried_rec->( sub { $f1->( $f1 )->( @_ ) } )
    }->( sub {
        my ( $f2 ) = @_;
        $curried_rec->( sub { $f2->( $f2 )->( @_ ) } )
    } )
}->( sub {
    my ( $rec ) = @_;
    sub {
        my ( $n ) = @_;
        $n < 2 ? 1 : $n * $rec->( $n - 1 );
    }
} )->( 10 );

And there it is: the Y-combinator. Up there in the first anonymous function. We have completely separated the recursion-handling bits from the recursive function itself. Extracting it, we get the following:

sub Y {
    my ( $curried_rec ) = @_;
    sub {
        my ( $f1 ) = @_;
        $curried_rec->( sub { $f1->( $f1 )->( @_ ) } )
    }->( sub {
        my ( $f2 ) = @_;
        $curried_rec->( sub { $f2->( $f2 )->( @_ ) } )
    } )
}

We keep that as a utility function which lets us inline the recursive function quite straightforwardly:

print Y( sub {
    my ( $rec ) = @_;
    sub {
        my ( $n ) = @_;
        $n < 2 ? 1 : $n * $rec->( $n - 1 );
    }
} )->( 10 );

And we’re done.

Note: this explanation is pretty much a straight Perl translation of the most excellent Y-combinator derivation lecture notes of Dr. John Franco. I just spent much longer than him on explaining just how the middle step (passing a clone of the currying closure) comes about.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • Can you give an example of how this might make some code cleaner or more correct?

    • I had to chuckle at your subject. I certainly know the feeling. The upshot is that you can use this to write recursive anonymous closures (avoiding all side-effects).

      I did this as an excercise. I am tiptoeing into the functional world proper lately, but my stance to it remains ambivalent. Perl isn’t quite the most beautiful language, but I find it a whoooole lot easier to read than any Lisp. I doubt that will ever change, irrespective of practice – I find your lack of syntax disturbing. This

      • You would need to do:
        my $fac = do {
            my $f;
            my $tmp = $f = sub {
                my ( $n ) = @_;
                $n < 2 ? 1 : $n * $f->( $n - 1 );
            };
            weaken($f);
            $f;
        };
        If you just weaken f without the tmp variable, you lose all references to it and it goes away before you have a chance to return it.
        • Ah yes, d’uh.

          But didn’t you mean your do {} block to return $tmp rather than $f? $f is the weak reference used inside the function, while $tmp is the strong reference you pass back out to the surrounding expression, no?

          • I don't think it matters which you return. As long as you are assigning $f to something (as above), there will still be a reference to it (from outside the scope of the do block) after $tmp goes out of scope.
            • Ah, when you copy a weak reference, the new reference is strong. Learn something new every day…

              In any case, the necessary code is rather unwieldy – enough so that I’d rather just use a Y combinator…

      • Not precisely... Weaken works on the variable, not the value. This should work:

        my $f;
        $f = sub { ... $f ... };
        weaken $f;
        return $f;
        • That doesn't work. As soon as you weaken $f, the code it refers to goes away because there are no other references to it. You need to keep another reference to it (hence the temp variable in a previous reply).
    • I have used closures + fixed point combintators several times for traversal functions when a named function just was not appropriate. I didn't know about the Y combinator at the time, but if I had, then I would have been able to clean up my code by using it to package up the closure+fixed-point combo into a single CODE ref.

      But aside from that fringe usage, it is not really that useful in day to day life. In languages like Scheme and Haskell where the purity is highly valued it tends to come in handy, b

  • Is there a reference cycle in there? Am I leaking memory every time I use that? Normally you don't give a closure access to itself because you are permanently allocating that memory.

    my $f;
    $f = sub { $f }; # immortal!
    • No, because it's never $f referring to $f - it's always a new anonymous sub.
      • A new anonymous sub that is identical in form but distinct in identity? Hmm. I suppose I don't usually care about identifying functions and could live with this.
    • Test::Memory::Cycle now checks for this =)
  • I found it was actually easier to deal with the Y combinator if you implement it in terms of the U combinator, which is just your basic fixed point combinator.

    sub U {
        my $f = shift;
        sub { $f->($f, @_) };
    }

    sub Y {
        my $f = shift;
        U(sub {
            my $h = shift;
            sub {
                $f->(U($h)->())->(@_)
            }
        })->();
    }

    I also recentl [perl.org]

    • Yes, those bits of code led to a lengthy (if anemic) discussion about Y and U a few days ago [perl.org].

      I’m still trying to wrap my head around the version you present. I think I am starting to get it, but it’s still confusing (as is any version of the Y combinator, really :-)). With the version I posted, I at least get what’s going on, even though the result is clearly much more complicated than the derivation of Y in terms of U.

      • Ah, I was not aware of the previous conversation. Of course all this is made moot by Perl 6 (IIRC the syntax correctly).

        sub ($n) {
            return 1 if $n < 2;
            return $n * $?SUB.($n - 1);
        }

        - Stevan