Έχουν δημοσιευτεί Σάββατο, 10 Φεβρουαρίου 2007 4:05 μμ από το μέλος PALLADIN

The Y combinator

Y fixed point combinator είναι ένα από τα πιο περίεργα και γοητευτικά
"αντικείμενα" που έχω συναντήσει σε αυτό που ονομάζουμε "Computer Science".
Γενικά ο Y combinator χρησιμοποιείται για να ορίσουμε recursive anonymous functions.

Πρόσφατα, εντόπισα ένα πολύ καλο άρθρο από τον Wes Dyer
για το πως μπορούμε να οδηγηθούμε και να καταλάβουμε το γιατι υπάρχει και το πώς δουλεύει.
Ο Wes Dyer είναι developer στον compiler της C# και μέσα από το blog του παρουσιάζει
τις νέες functional δυνατότητες της C# 3.0.

Πρίν από κάποια χρονια είχα εντοπίσει μια διαφορετική υλοποίηση που με είχε προβληματίσει αρκετά...
Ο κώδικας που είχα βρει:

static Func<A, R> Fix<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
   Func<A, R> g = null;
   Func<A, R> g = a => f(g)(a);
   return g;
}

Πρόσφατα, επικοινώνησα μαζί του για να ακούσω την άποψή του και για να μου σχολιάσει τις διαφορες αναμεσα στις δύο υλοποιήσεις. Η απάντησή του έχει αρκετό ενδιαφέρον και με κάλυψε απόλυτα.
Παραθέτω ένα κομμάτι από το κείμενο της απάντησης:

"In some sense the fixed point combinator that I
presented originally is more beautiful.

static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
   Recursive<A, R> rec = r => a => f(r(r))(a);
   return rec(rec);
}

Because it doesn't use the g = null combined with lazy evaluation to
reference itself.  Note that g is defined in terms of g whereas in Y rec is
*not* defined in terms of rec.  There is no recursion in the definition of
rec, yet when used it allows for recursion.  Wild eh?  To do this the
recursion has been moved to the type system.  Recursive is a delegate type
is that defined in terms of itself.

delegate Func<A,R> Recursive<A,R>(Recursive<A,R> r);

So in some senses the definition of Y is more interesting that the
definition of Fix although they accomplish the same thing."


Κλείνοντας, θέλω να αναφέρω τα πολύ σημαντικά lectures από δύο μεγάλους μάγους.

http://www.swiss.ai.mit.edu/classes/6.001/abelson-sussman-lectures/

Πραγματικά διαχρονικές ιδέες.

Happy coding...

Share



Καταχώρηση στις κατηγορίες:

Ενημέρωση για Σχόλια

Αν θα θέλατε να λαμβάνετε ένα e-mail όταν γίνονται ανανεώσεις στο περιεχόμενο αυτής της δημοσίευσης, παρακαλούμε γίνετε συνδρομητής εδώ

Παραμείνετε ενήμεροι στα τελευταία σχόλια με την χρήση του αγαπημένου σας RSS Aggregator και συνδρομή στη Τροφοδοσία RSS με σχόλια

Σχόλια:

Χωρίς Σχόλια

Ποιά είναι η άποψή σας για την παραπάνω δημοσίευση;

(απαιτούμενο) 
απαιτούμενο 
προαιρετικό
απαιτούμενο 
ÅéóÜãåôå ôïí êùäéêü:
CAPTCHA Image