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.
Can you give an example of how this might make some code cleaner or more correct?
Re:Ouch. Head hurt. Need beer.
Aristotle on 2006-09-05T17:42:38
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 meant I understood the explanations, but couldn’t grok the code samples in enough to detail for more than a superficial grasp. Hence the decision that I would need to redo this in Perl for myself.
I don’t really have a good example on hand where you’d need to do this, or at least could use this to make something much easier. (Maybe I should page MJD here?) I assume that’s because we’re talking about Perl, where statements roam and side effects abound. A schemer could probably come up with a credible use case.
If side effects are not an issue, you can achieve the same much easier in Perl:
my $fac = do {
my $f;
$f = weaken sub {
my ( $n ) = @_;
$n < 2 ? 1 : $n * $f->( $n - 1 );
};
};(I think: untested. Does weaken return the reference? If not, it gets a good bit more awkward.)
Re:Ouch. Head hurt. Need beer.
runrig on 2006-09-05T19:28:53
You would need to do: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.my $fac = do {
my $f;
my $tmp = $f = sub {
my ( $n ) = @_;
$n < 2 ? 1 : $n * $f->( $n - 1 );
};
weaken($f);
$f;
};Re:Ouch. Head hurt. Need beer.
Aristotle on 2006-09-05T20:41:07
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?
Re:Ouch. Head hurt. Need beer.
runrig on 2006-09-05T20:59:03
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.Re:Ouch. Head hurt. Need beer.
Aristotle on 2006-09-05T21:14:32
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…
Re:Ouch. Head hurt. Need beer.
nothingmuch on 2006-09-05T21:13:44
Not precisely... Weaken works on the variable, not the value. This should work:
my $f;
$f = sub {... $f ... };
weaken $f;
return $f;Re:Ouch. Head hurt. Need beer.
runrig on 2006-09-05T23:03:44
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).Re:Ouch. Head hurt. Need beer.
Stevan on 2006-09-05T18:43:18
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, but thats a whole different paradigm.
Oh yeah and there is also the "street cred" factor too. I heard that at MIT there are roaving bands of Scheme hackers armed with sharpened copies of SICP that prowl the hallways asking people if they know the Y combinator. I don't even want to think about what would happen to you if you didn't know it. *shudder*
- Stevan
Re:Cycles?
Matts on 2006-09-05T19:01:27
No, because it's never $f referring to $f - it's always a new anonymous sub.Re:Cycles?
jjore on 2006-09-05T19:48:55
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.Re:Cycles?
nothingmuch on 2006-09-05T21:07:30
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 recently added the Y and U combinators to Moose::Autobox, so you can just do this:.
print sub {
my $f = shift;
sub {
my $n = shift;
return 1 if $n < 2;
return $n * $f->($n - 1);
}
}->y->(10);
and get that oh so special Ruby-ish feeling in your heart.
- Stevan
Re: the Y Combinator
Aristotle on 2006-09-05T21:00:55
Yes, those bits of code led to a lengthy (if anemic) discussion about Y and U a few days ago.
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. Re: the Y Combinator
Stevan on 2006-09-05T22:02:44
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