Y combinator

cr7

Eli Bendersky ha un blog che seguo da sempre. Oggi –ahemm qualche giorno fa– posta questo: Some notes on the Y combinator. Roba che ho letto quando era già sera, non ho capito tanto (ahemmm niente, nada, zilch) e me lo sono sognato tutta la notte.
Non so se avete idea di quale possa essere la personificazione (incubosa) di Y? Credo di no. E non chiedetemi di raccontarvela; diciamo che al mattino vi sentite un po’ come ci si sente in questi tempi pre-referendum😦

Eli rockz (al solito) e parte con il link alla Wiki, ottimo (al solito).
Ma a me, per la mia storia & sono vecchio (auto-cit.) viene subito una domanda, forse solo mia, forse peregrina, forse senza senso, forse troppo ovvia, ma in ogni caso questa: “serve? quando si usa?“. Notare che non metto in discussione che si possa usare, mica mi metto contro Haskell Curry, Eli, et al. (notare che per l’occasione uso anche l’Oxford comma, solo questa volta).

Eli svolge in dettaglio tutta la lezione. Come si usa in questi casi parte con il Lisp, cioè un dialetto della famiglia, uno che ultimamente è di moda (perso non conosco nessuno che lo usi, ma non conosco neanche chi usi un Lisp).

Clojure (ecco, sa quello) è immediato (quasi) per il lisper anche niubbo (come me). Ad esempio la funzione factorial-rec di Eli:

(defn factorial-rec [n]
  (if (zero? n)
    1
    (* n (factorial-rec (- n 1)))))

in Racket diventa:

(define [factorial n]
    (if (zero? n)
        1
        (* n (factorial (- n 1)))))

C’è solo una una keyword che cambia nome (defn invece di define) e una parentesi spostata!
Ricordo che () e [] sono intercambiabili; anche se nessun racketeer scriverebbe come qui sopra.
Passo-passo si arriva a Y combinator – a tool for making anonymous functions recursive.

Ah! capito (forse): è come lambda, una variante (super) di lambda😀
Se sono impreciso è perché fin lì ci arrivo, porta passiensa (auto-cit.).

Non ho riprodotto l’esempio con Clojure (dovrei reinstallarlo) ma ecco, con Racket:

(define Y
  ((lambda (f)
     (f f))
   (lambda (z)
     (lambda (f)
       (f (lambda (x) (((z z) f) x)))))))

(define factorial
  (Y (lambda (recursive-factorial)
       (lambda (x)
         (if (<= x 0)
             1
             (* x (recursive-factorial (- x 1))))))))

(print (factorial 1000))

1000 può sembrare grosso ma no, nope:

y0

Ho eseguito 5 run ottenendo per real 236, 196, 203, 250 e 194 ms.

Confronto con la versione ricorsiva liscia, questa:

y1

Il tempo di esecuzione è simile al precedente (e troppo piccolo per essere significativo), comunque ho rilevato 209, 207, 242, 191 e 200 ms.

Reindirizzando l’output su file posso poi confrontare i risultati

y2

ovviamente😀

Ma Eli va avanti: The Y combinator in Python.
Finally, just to show that the Y combinator isn’t something unique to the Lisp family of languages, here’s a Python implementation:

ycombinator = lambda func: \
    (lambda self: func(lambda n: (self(self))(n)))(
        lambda self: func(lambda n: (self(self))(n)))

factorial = lambda recurse: \
    lambda n: \
        1 if n == 0 else n * recurse(n - 1)

print((ycombinator(factorial)) (400))

y3

Velocissimo per n non troppo grande altrimenti

y4

che finisce con

y5

Sì dice sempre Eli It’s even possible to create the Y combinator in C++. Static typing makes it somewhat less elegant than in the more dynamic languages, but C++14’s generic lambdas help a lot.

Resta la mia domanda iniziale, serve?
Ci ho googlato su un po’, trovato un esempio in JavaScript, suggerimento If you’re ready for a long read, Mike Vanier has a great explanation collegato a un riassunto commendevole: long story short, it allows you to implement recursion in a language that doesn’t necessarily support it natively. Tutto qui.

Trovata anche la risposta (l’altra non quella universale (42)): How are Y combinators used in practice?
They are not used in practice. They are nice theorical tool to provide recursion in a language without built-in recursion. Because all practical programming languages supports recursion natively, there is no use for Y.
Già detto che Quora rockz! :grin:?

OK, caso chiuso (?)😀

:mrgreen:

Post a comment or leave a trackback: Trackback URL.

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: