Fuck, I've been rereading http://mvanier.livejournal.com/2897.html for the past several hours and it might as well be written in Esperanto. Am I just not cut out for EXPERT PROGRAMMING‽
Y combinator is a rather simple way to represent recursion, however you won't really need to use it in practice, unless you're working with a language which doesn't support recursion, but supports first class functions, which is something rather rare and only encountered in more theorethical languages (like pure lambda calculus).
I don't really understand why you have trouble understanding the Y combinator, maybe it's because you don't know Scheme or Common Lisp well enough? Even so, you should be able to understand it, since one can express it in very small subsets of Scheme or CL, or even simpler languages like pure lambda calculus.
the Y-combinator is just a δ-rule added to the typed lambda-calculus in order to make recursion work again. which was broken by introducing types to the lambda-calculus
Here, check this perl code out. $fact contains an anonymous recursive function not using anything outside of its scope. $y_fact is the same thing only with Y.
my $fact=sub{
my($func,$arg)=@_;
return 1 if $arg==0;
return $arg*$func->($func,$arg-1)
};
my $y=sub{
my($func)=@_;
return sub{
return $func->($func,@_);
}
};
print $fact->($fact,5),"\n"; # prints 120
my $y_fact=$y->($fact);
print $y_fact->(5),"\n"; # prints 120, too. So much for Y combinator...
The only difference from paper someone linked to is that my function accepts two arguments at once while their accepts one and returns a function that accepts another one (but the dead dog taught us this is the same thing).
Name:
FrozenVoid meme fan2010-10-23 9:30
function Y(f) {
function g(h) {
return function(x) {
return (f(h(h)))(x);
};
}
return g(g);
}
Name:
Anonymous2010-10-23 9:36
>>21
The difference is that your recursive case uses f(f, arg-1) where the recursive case with a real Y combinator would be f(arg-1), abstracting out finding the fixed point from computing the factorial. Having Y proves constructively that every function has at least one fixed point (in the context of untyped lambda calculus).
>>23
Practically though, this is only syntactic sugar. Any function that can be written your way can also be written my way. The only difference that in each call to my function I have to specify it as first argument. Y is a wrapper that does it for me by putting that function I otherwise would have to specify myself into environment of function it returns. If you're >>20 I want you to apologize for the nonsense you wrote without thinking.
*YOU HAVE BEEN VISITED BY LE TOP LEL OF COMEDY GOLD** POST THIS IN 3 threads or lose your sides!
░░░░░░░▄▀▀▀░▄▄▄▄░░░▀▀▀▀▀▀▀▀▄▄░▀
░░░░░░░█░░░░░░░░▀▀▀▀▀▄▄▄▄▄▄▄▄▀░░█
░░░░░▄▀░░░░░░░░░░▄░░░░░░░░▄▄░░░░░▀▄
░░░▄▀░░░░░▄▀▀▀█▄░▀░░░░▄▀▀▀██▀▀▄░░░░░▀
░░▄▀░░▄▄░░▀▀▀▀████▀░░░▀▄▄▀▀▀▀▄█░░░░░░█
░▄▀░▄▀█░░▄▄░░░░░░░█░░░░░▄▄▄░░░▀▀░░░░░░█
▄▀░░█░█░▀░░▀▀▄░░░░░█░░░░░░░▀▀▀▀▀▄░░░░░█
▀▄░░▀░█░░░▄░░░░░░▄▀░░░░▀▄░░░▄▄░░▀▄░█░▄▀
░░▀▄░░░░█▀▄░░░░░▀█░░░░▀▀░█▄▀▄░█░░░█░█
░░░░█░░█░▀▄▀▄▄░░░░▀▀▀░░░▄█▀░▄▀█░░░░▄
░░░░░█░░█░▀▀▄░▀▄▄▄▄▄▄▄▀█░▄█▀▄▀░░░░░
░░░░░█░░▀▄▄░░▀█░░░█░░▄▄▀▀▄▄█▀░░░░▀
░░░░▄▀░░░▀▄▀▀▄░▀▀▀▀▀▀▄▄▀▀▀▄▀░░░░▀
░░░▄▀░░░░░░▀▄░█▄▄▄▄▀▀░▀▄▀▀░░░▄▀▀
░░▄▀░░░░░░░░░▀▄▄▄▄█▄▄▀▀░░░░▄
░░█░░░░░░▀▄▄░░░▄▄▄▄▄▄▀░░░▄▀
░░█░░░░░░░░░▀▀▀▄▄▄▄▄▄▄▀▀
░░░█░░░░░░▀▀▀▀▀░░░░▄
░░░▀▀▄▄▄▄▄▄▄▄▄▀▀▀
A boy died in 1932 by a homicidal murderer. He buried him in the ground when he was still alive. The murdered chanted, "Toma sota balcu" as he buried him. Now that you have read the chant, you will meet this little boy. In the middle of the night he will be on your ceiling. He will suffocate you like he was suffocated. If you post this, he will not bother you. Your kindness will be rewarded.