Cos’è un combinatore Y?

Un combinatore Y è un concetto di informatica dal lato “funzionale” delle cose. La maggior parte dei programmatori non sa molto sui combinatori, se ne hanno persino sentito parlare.

  • Cos’è un combinatore Y?
  • Come funzionano i combinatori?
  • Per cosa stanno bene?
  • Sono utili nei linguaggi procedurali?

Se sei pronto per una lunga lettura, Mike Vanier ha una grande spiegazione . Per farla breve, consente di implementare la ricorsione in un linguaggio che non necessariamente la supporta in modo nativo.

Un combinatore Y è un “funzionale” (una funzione che opera su altre funzioni) che consente la ricorsione, quando non è ansible fare riferimento alla funzione da sé. Nella teoria delle scienze informatiche, generalizza la ricorsione , estraendone l’implementazione e quindi separandola dal lavoro effettivo della funzione in questione. Il vantaggio di non aver bisogno di un nome in fase di compilazione per la funzione ricorsiva è una sorta di bonus. =)

Questo è applicabile nelle lingue che supportano le funzioni lambda . La natura basata sulle espressioni di lambda di solito significa che non possono riferirsi a se stessi per nome. Lavorare attorno a questo dichiarando la variabile, riferendoci ad esso, quindi assegnandogli la lambda, per completare il loop di riferimento, è fragile. La variabile lambda può essere copiata e la variabile originale riassegnata, che interrompe l’autoreferenziale.

I combinatori a Y sono complicati da implementare e spesso da usare in linguaggi tipizzati staticamente (quali sono spesso i linguaggi procedurali ), poiché in genere le restrizioni di digitazione richiedono che il numero di argomenti per la funzione in questione sia noto al momento della compilazione. Ciò significa che un y-combinator deve essere scritto per ogni conteggio argomento che è necessario utilizzare.

Di seguito è riportato un esempio di come l’utilizzo e il funzionamento di un Y-Combinator, in C #.

L’uso di un combinatore Y implica un modo “insolito” di build una funzione ricorsiva. Innanzitutto devi scrivere la tua funzione come una parte di codice che chiama una funzione preesistente, piuttosto che essa stessa:

// Factorial, if func does the same thing as this bit of code... x == 0 ? 1: x * func(x - 1); 

Quindi lo trasformi in una funzione che accetta una funzione per chiamare e restituisce una funzione che lo fa. Questo viene chiamato funzionale, poiché accetta una funzione e esegue un’operazione che ne determina un’altra.

 // A function that creates a factorial, but only if you pass in // a function that does what the inner function is doing. Func, Func> fact = (recurs) => (x) => x == 0 ? 1 : x * recurs(x - 1); 

Ora avete una funzione che prende una funzione e restituisce un’altra funzione che assomiglia a un fattoriale, ma invece di chiamare se stessa, chiama l’argomento passato nella funzione esterna. Come rendi questo fattoriale? Passa la funzione interiore a se stessa. Lo Y-Combinator lo fa, essendo una funzione con un nome permanente, che può introdurre la ricorsione.

 // One-argument Y-Combinator. public static Func Y(Func, Func> F) { return t => // A function that... F( // Calls the factorial creator, passing in... Y(F) // The result of this same Y-combinator function call... // (Here is where the recursion is introduced.) ) (t); // And passes the argument into the work function. } 

Piuttosto che la chiamata fattoriale stessa, ciò che accade è che il fattoriale chiama il generatore fattoriale (restituito dalla chiamata ricorsiva a Y-Combinator). E in base al valore corrente di t la funzione restituita dal generatore chiamerà di nuovo il generatore, con t-1, o restituirà 1, terminando la ricorsione.

È complicato e criptico, ma tutto si risolve in fase di esecuzione, e la chiave del suo funzionamento è “l’esecuzione differita” e la rottura della ricorsione per estendersi a due funzioni. La F interna è passata come argomento , per essere chiamata nella successiva iterazione, solo se necessario .

L’ho sollevato da http://www.mail-archive.com/[email protected]/msg02716.html che è una spiegazione che ho scritto diversi anni fa.

Userò JavaScript in questo esempio, ma anche molte altre lingue funzioneranno.

Il nostro objective è essere in grado di scrivere una funzione ricorsiva di 1 variabile usando solo le funzioni di 1 variabile e senza assegnazioni, definendo le cose per nome, ecc. (Perché questo è il nostro objective è un’altra domanda, prendiamo questa come la sfida che viene data.) Sembra imansible, eh? Ad esempio, implementiamo fattoriale.

Bene, il primo passo è dire che potremmo farlo facilmente se abbiamo barato un po ‘. Usando le funzioni di 2 variabili e assegnamento possiamo almeno evitare di dover usare l’assegnazione per impostare la ricorsione.

 // Here's the function that we want to recurse. X = function (recurse, n) { if (0 == n) return 1; else return n * recurse(recurse, n - 1); }; // This will get X to recurse. Y = function (builder, n) { return builder(builder, n); }; // Here it is in action. Y( X, 5 ); 

Ora vediamo se riusciamo a imbrogliare di meno. Bene, in primo luogo stiamo usando il compito, ma non ne abbiamo bisogno. Possiamo semplicemente scrivere X e Y in linea.

 // No assignment this time. function (builder, n) { return builder(builder, n); }( function (recurse, n) { if (0 == n) return 1; else return n * recurse(recurse, n - 1); }, 5 ); 

Ma stiamo usando le funzioni di 2 variabili per ottenere una funzione di 1 variabile. Possiamo aggiustarlo? Beh, un ragazzo intelligente con il nome di Haskell Curry ha un buon trucco, se hai buone funzioni di ordine superiore allora hai bisogno solo di funzioni di 1 variabile. La dimostrazione è che puoi ottenere dalle funzioni di 2 (o più nel caso generale) variabili a 1 variabile con una trasformazione di testo puramente meccanica come questa:

 // Original F = function (i, j) { ... }; F(i,j); // Transformsd F = function (i) { return function (j) { ... }}; F(i)(j); 

dove … rimane esattamente lo stesso. (Questo trucco è chiamato “currying” dopo il suo inventore.Il linguaggio Haskell è anche chiamato per Haskell Curry. File che sotto inutili banalità.) Ora basta applicare questa trasformazione ovunque e otteniamo la nostra versione finale.

 // The dreaded Y-combinator in action! function (builder) { return function (n) { return builder(builder)(n); }}( function (recurse) { return function (n) { if (0 == n) return 1; else return n * recurse(recurse)(n - 1); }})( 5 ); 

Sentiti libero di provarlo. alert () che ritorna, legalo a un pulsante, qualunque cosa. Quel codice calcola fattoriali, in modo ricorsivo, senza utilizzare assegnazioni, dichiarazioni o funzioni di 2 variabili. (Ma provare a tracciare come funziona è probabile che ti faccia girare la testa e passarlo, senza la derivazione, solo leggermente riformattato darà come risultato un codice che è sicuro di confondere e confondere.)

Puoi sostituire le 4 linee che definiscono ricorsivamente fattoriale con qualsiasi altra funzione ricorsiva che desideri.

Mi chiedo se ci sia qualche utilità nel tentativo di build questo da zero. Vediamo. Ecco una funzione fattoriale di base e ricorsiva:

 function factorial(n) { return n == 0 ? 1 : n * factorial(n - 1); } 

Facciamo il refactoring e creiamo una nuova funzione chiamata fact che restituisce una funzione di calcolo fattoriale anonimo invece di eseguire il calcolo stesso:

 function fact() { return function(n) { return n == 0 ? 1 : n * fact()(n - 1); }; } var factorial = fact(); 

È un po ‘strano, ma non c’è niente di sbagliato in questo. Stiamo solo generando una nuova funzione fattoriale ad ogni passaggio.

La ricorsione in questa fase è ancora abbastanza esplicita. La funzione dei fact deve essere consapevole del proprio nome. Parametrizziamo la chiamata ricorsiva:

 function fact(recurse) { return function(n) { return n == 0 ? 1 : n * recurse(n - 1); }; } function recurser(x) { return fact(recurser)(x); } var factorial = fact(recurser); 

È fantastico, ma il recurser deve ancora conoscere il suo nome. Parliamo anche di questo:

 function recurser(f) { return fact(function(x) { return f(f)(x); }); } var factorial = recurser(recurser); 

Ora, invece di chiamare direttamente il recurser(recurser) , creiamo una funzione wrapper che restituisca il suo risultato:

 function Y() { return (function(f) { return f(f); })(recurser); } var factorial = Y(); 

Ora possiamo eliminare del tutto il nome del recurser ; è solo un argomento per la funzione interiore di Y, che può essere sostituita con la funzione stessa:

 function Y() { return (function(f) { return f(f); })(function(f) { return fact(function(x) { return f(f)(x); }); }); } var factorial = Y(); 

L’unico nome esterno ancora referenziato è un fact , ma dovrebbe essere chiaro a questo punto che è anche facilmente parametrizzato, creando la soluzione completa, generica:

 function Y(le) { return (function(f) { return f(f); })(function(f) { return le(function(x) { return f(f)(x); }); }); } var factorial = Y(function(recurse) { return function(n) { return n == 0 ? 1 : n * recurse(n - 1); }; }); 

La maggior parte delle risposte sopra descrivono cosa è il combinatore Y, ma non per quello che è.

Combinatori a punti fissi vengono utilizzati per mostrare che il calcolo lambda è completo . Questo è un risultato molto importante nella teoria del calcolo e fornisce una base teorica per la programmazione funzionale .

Studiare i combinatori a punti fissi mi ha anche aiutato a capire davvero la programmazione funzionale. Non ho mai trovato alcun uso per loro nella programmazione effettiva però.

y-combinator in JavaScript :

 var Y = function(f) { return (function(g) { return g(g); })(function(h) { return function() { return f(h(h)).apply(null, arguments); }; }); }; var factorial = Y(function(recurse) { return function(x) { return x == 0 ? 1 : x * recurse(x-1); }; }); factorial(5) // -> 120 

Edit : Imparo molto guardando il codice, ma questo è un po ‘difficile da digerire senza qualche background – mi dispiace per quello. Con alcune conoscenze generali presentate da altre risposte, puoi iniziare a selezionare ciò che sta accadendo.

La funzione Y è “y-combinator”. Ora date un’occhiata alla linea var factorial cui viene usato Y. Si noti che si passa ad una funzione che ha un parametro (in questo esempio, recurse ) che viene utilizzato anche in seguito nella funzione interna. Il nome del parametro diventa fondamentalmente il nome della funzione interna che consente di eseguire una chiamata ricorsiva (poiché utilizza recurse() nella sua definizione.) Il combinatore y esegue la magia di associare la funzione interna altrimenti anonima con il nome del parametro del funzione passata a Y.

Per la spiegazione completa di come Y fa la magia, controlla l’ articolo collegato (non da me btw.)

Per i programmatori che non hanno approfondito la programmazione funzionale e non si preoccupano di iniziare subito, ma sono curiosamente curiosi:

Il combinatore Y è una formula che consente di implementare la ricorsione in una situazione in cui le funzioni non possono avere nomi ma possono essere passate come argomenti, utilizzate come valori di ritorno e definite all’interno di altre funzioni.

Funziona passando la funzione a se stessa come argomento, in modo che possa chiamarsi.

Fa parte del calcolo lambda, che è davvero matematica ma è effettivamente un linguaggio di programmazione, ed è piuttosto fondamentale per l’informatica e in particolare per la programmazione funzionale.

Il valore pratico giornaliero del combinatore Y è limitato, dal momento che i linguaggi di programmazione tendono a consentire il nome delle funzioni.

Nel caso in cui è necessario identificarlo in una fila di polizia, sembra che questo:

Y = λf. (Λx.f (xx)) (λx.f (xx))

Di solito è ansible individuarlo a causa del ripetuto (λx.f (xx)) .

I simboli λ sono la lettera greca lambda, che dà il nome al calcolo lambda, e ci sono molti termini di stile (λx.t) perché è quello che assomiglia al calcolo lambda.

Altre risposte forniscono una risposta piuttosto concisa a questo, senza un fatto importante: non è necessario implementare il combinatore a virgola fissa in alcun linguaggio pratico in questo modo complicato e farlo non ha alcuno scopo pratico (eccetto “guarda, so che combinatore di Y è”). È un concetto teorico importante, ma di scarso valore pratico.

Un Y-Combinator è un altro nome per un condensatore di stream.

Ecco un’implementazione JavaScript di Y-Combinator e la funzione Factorial (dall’articolo di Douglas Crockford, disponibile all’indirizzo: http://javascript.crockford.com/little.html ).

 function Y(le) { return (function (f) { return f(f); }(function (f) { return le(function (x) { return f(f)(x); }); })); } var factorial = Y(function (fac) { return function (n) { return n <= 2 ? n : n * fac(n - 1); }; }); var number120 = factorial(5); 

Ho scritto una sorta di “guida idiota” allo Y-Combinator sia in Clojure che in Scheme per aiutarmi a fare i conti con esso. Sono influenzati dal materiale in “The Little Schemer”

Nello schema: https://gist.github.com/z5h/238891

o Clojure: https://gist.github.com/z5h/5102747

Entrambi i tutorial sono codice inframmezzato da commenti e dovrebbero essere tagliati e inseribili nel tuo editor preferito.

Il combinatore y implementa la ricorsione anonima. Quindi invece di

 function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) } 

tu puoi fare

 function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) } 

naturalmente, il combinatore y funziona solo in lingue call-by-name. Se vuoi usarlo in qualsiasi normale linguaggio call-by-value, allora avrai bisogno del relativo z-combinator (y-combinator divergerà / infinito-loop).

Un combinatore a punto fisso (o operatore a virgola fissa) è una funzione di ordine superiore che calcola un punto fisso di altre funzioni. Questa operazione è rilevante nella programmazione della teoria del linguaggio perché consente l’implementazione della ricorsione sotto forma di una regola di riscrittura, senza il supporto esplicito del motore di runtime del linguaggio. (src Wikipedia)

Questo operatore può semplificarti la vita:

 var Y = function(f) { return (function(g) { return g(g); })(function(h) { return function() { return f.apply(h(h), arguments); }; }); }; 

Quindi si evita la funzione extra:

 var fac = Y(function(n) { return n == 0 ? 1 : n * this(n - 1); }); 

Alla fine, chiami fac(5) .

Ricorsione anonima

Un combinatore a virgola fissa è una fix funzione di ordine superiore che per definizione soddisfa l’equivalenza

 forall f. fix f = f (fix f) 

fix f rappresenta una soluzione x all’equazione del punto fisso

  x = fx 

Il fattoriale di un numero naturale può essere dimostrato da

 fact 0 = 1 fact n = n * fact (n - 1) 

Usando fix , si possono ricavare prove costruttive arbitrarie su funzioni generiche / μ-ricorsive senza auto-referenzialità non-pornografica.

 fact n = (fix fact') n 

dove

 fact' rec n = if n == 0 then 1 else n * rec (n - 1) 

così

  fact 3 = (fix fact') 3 = fact' (fix fact') 3 = if 3 == 0 then 1 else 3 * (fix fact') (3 - 1) = 3 * (fix fact') 2 = 3 * fact' (fix fact') 2 = 3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1) = 3 * 2 * (fix fact') 1 = 3 * 2 * fact' (fix fact') 1 = 3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1) = 3 * 2 * 1 * (fix fact') 0 = 3 * 2 * 1 * fact' (fix fact') 0 = 3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1) = 3 * 2 * 1 * 1 = 6 

Questa prova formale che

 fact 3 = 6 

utilizza metodicamente l’equivalenza del combinatore a virgola fissa per le riscritture

 fix fact' -> fact' (fix fact') 

Lambda calcolo

Il formalismo di calcolo lambda non tipizzato consiste in una grammatica senza contesto

 E ::= v Variable | λ v. E Abstraction | EE Application 

dove v spazia su variabili, insieme alle regole di riduzione beta ed eta

 (λ x. B) E -> B[x := E] Beta λ x. E x -> E if x doesn't occur free in E Eta 

La riduzione beta sostituisce tutte le occorrenze libere della variabile x nell’astrazione (“funzione”) corpo B dall’espressione (“argomento”) E La riduzione Eta elimina l’astrazione ridondante. A volte viene omesso dal formalismo. Un’espressione irriducibile , a cui non si applica nessuna regola di riduzione, è in forma normale o canonica .

 λ x y. E 

è una scorciatoia per

 λ x. λ y. E 

(multiarità di astrazione),

 EFG 

è una scorciatoia per

 (EF) G 

(applicazione left-associativity),

 λ x. x 

e

 λ y. y 

sono equivalenti alfa .

L’astrazione e l’applicazione sono i due soli “primitivi linguistici” del calcolo lambda, ma consentono la codifica di dati e operazioni arbitrariamente complessi.

I numeri della Chiesa sono una codifica dei numeri naturali simili ai naturali Peano-assiomatici.

  0 = λ f x. x No application 1 = λ f x. fx One application 2 = λ f x. f (fx) Twofold 3 = λ f x. f (f (fx)) Threefold . . . SUCC = λ nf x. f (nfx) Successor ADD = λ nmf x. nf (mfx) Addition MULT = λ nmf x. n (mf) x Multiplication . . . 

Una prova formale che

 1 + 2 = 3 

utilizzando la regola di riscrittura della riduzione beta:

  ADD 1 2 = (λ nmf x. nf (mfx)) (λ g y. gy) (λ h z. h (hz)) = (λ mf x. (λ g y. gy) f (mfx)) (λ h z. h (hz)) = (λ mf x. (λ y. fy) (mfx)) (λ h z. h (hz)) = (λ mf x. f (mfx)) (λ h z. h (hz)) = λ f x. f ((λ h z. h (hz)) fx) = λ f x. f ((λ z. f (fz)) x) = λ f x. f (f (fx)) Normal form = 3 

combinatori

Nel calcolo lambda, i combinatori sono astrazioni che non contengono variabili libere. Più semplicemente: I , il combinatore di identity framework

 λ x. x 

isomorfo alla funzione di id quadro

 id x = x 

Tali combinatori sono gli operatori primitivi dei calcoli combinatori come il sistema SKI.

 S = λ xy z. xz (yz) K = λ x y. x I = λ x. x 

La riduzione beta non è fortemente normalizzante ; non tutte le espressioni riducibili, “redexes”, convergono in forma normale sotto riduzione beta. Un semplice esempio è l’applicazione divergente del combinatore omega ω

 λ x. xx 

a se stesso:

  (λ x. xx) (λ y. yy) = (λ y. yy) (λ y. yy) . . . = _|_ Bottom 

La riduzione delle sottoespressioni più a sinistra (“teste”) è prioritaria. L’ordine applicativo normalizza gli argomenti prima della sostituzione, l’ordine normale no. Le due strategie sono analoghe alla valutazione entusiasta, ad es. C, e alla valutazione lazy, ad esempio Haskell.

  K (I a) (ω ω) = (λ k l. k) ((λ i. i) a) ((λ x. xx) (λ y. yy)) 

diverge sotto una desiderosa riduzione beta per ordine applicativo

 = (λ k l. k) a ((λ x. xx) (λ y. yy)) = (λ l. a) ((λ x. xx) (λ y. yy)) = (λ l. a) ((λ y. yy) (λ y. yy)) . . . = _|_ 

da allora in una semantica rigorosa

 forall f. f _|_ = _|_ 

ma converge sotto la pigra riduzione del normale ordine beta

 = (λ l. ((λ i. i) a)) ((λ x. xx) (λ y. yy)) = (λ l. a) ((λ x. xx) (λ y. yy)) = a 

Se un’espressione ha una forma normale, la riduzione beta dell’ordine normale la troverà.

Y

La proprietà essenziale del combinatore a virgola fissa Y

 λ f. (λ x. f (xx)) (λ x. f (xx)) 

è dato da

  Y g = (λ f. (λ x. f (xx)) (λ x. f (xx))) g = (λ x. g (xx)) (λ x. g (xx)) = Y g = g ((λ x. g (xx)) (λ x. g (xx))) = g (Y g) = g (g ((λ x. g (xx)) (λ x. g (xx)))) = g (g (Y g)) . . . . . . 

L’equivalenza

 Y g = g (Y g) 

è isomorfo a

 fix f = f (fix f) 

Il calcolo lambda non tipizzato può codificare prove costruttive arbitrarie su funzioni generiche / μ-ricorsive.

  FACT = λ n. Y FACT' n FACT' = λ rec n. if n == 0 then 1 else n * rec (n - 1) FACT 3 = (λ n. Y FACT' n) 3 = Y FACT' 3 = FACT' (Y FACT') 3 = if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1) = 3 * (Y FACT') (3 - 1) = 3 * FACT' (Y FACT') 2 = 3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1) = 3 * 2 * (Y FACT') 1 = 3 * 2 * FACT' (Y FACT') 1 = 3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1) = 3 * 2 * 1 * (Y FACT') 0 = 3 * 2 * 1 * FACT' (Y FACT') 0 = 3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1) = 3 * 2 * 1 * 1 = 6 

(Moltiplicazione ritardata, confluenza)

Per il calcolo lambda non tipizzato di Churchian, è stato dimostrato che esiste un infinito ricorsivamente numerabile di combinatori a virgola fissa oltre a Y

  X = λ f. (λ x. xx) (λ x. f (xx)) Y' = (λ x y. xyx) (λ y x. y (xyx)) Z = λ f. (λ x. f (λ v. xxv)) (λ x. f (λ v. xxv)) Θ = (λ x y. y (xxy)) (λ x y. y (xxy)) . . . 

La riduzione beta dell’ordine normale rende il calcolo lambda non esteso non esteso un sistema di riscrittura completo di Turing.

In Haskell, il combinatore a virgola fissa può essere implementato elegantemente

 fix :: forall t. (t -> t) -> t fix f = f (fix f) 

La pigrizia di Haskell si normalizza in un aspetto prima che tutte le sottoespressioni siano state valutate.

 primes :: Integral t => [t] primes = sieve [2 ..] where sieve = fix (\ rec (p : ns) -> p : rec [n | n <- ns , n `rem` p /= 0]) 

  • David Turner: Church's Thesis e Functional Programming
  • Alonzo Church: Un problema irrisolvibile della teoria dei numeri elementari
  • Lambda calcolo
  • Teorema di Church-Rosser

Come novizio per i combinatori, ho trovato l’articolo di Mike Vanier (grazie Nicholas Mancuso) per essere davvero d’aiuto. Mi piacerebbe scrivere un riassunto, oltre a documentare la mia comprensione, se potesse essere di aiuto ad altri sarei molto contento.

Da schifoso a meno schifoso

Usando factorial come esempio, usiamo la seguente funzione almost-factorial per calcolare il fattoriale del numero x :

 def almost-factorial fx = if iszero x then 1 else * x (f (- x 1)) 

Nello pseudo-codice sopra, almost-factorial assume funzione f e numero x ( almost-factorial è al curry, quindi può essere visto come prendere in funzione f e restituire una funzione 1-arity).

Quando calcoli almost-factorial calcola fattoriale per x , delega il calcolo di fattoriale per x - 1 alla funzione f e accumula quel risultato con x (in questo caso moltiplica il risultato di (x – 1) con x).

Può essere visto come almost-factorial in una versione scadente della funzione fattoriale (che può calcolare solo fino al numero x - 1 ) e restituisce una versione meno fattoriale di fattoriale (che calcola fino al numero x ). Come in questa forma:

 almost-factorial crappy-f = less-crappy-f 

Se passiamo ripetutamente la versione meno fattoriale di fattoriale a almost-factorial , alla fine otterremo la nostra funzione fattoriale desiderata f . Dove può essere considerato come:

 almost-factorial f = f 

Fix-point

Il fatto che almost-factorial f = f significa f è il punto fisso della funzione almost-factorial .

Questo è stato un modo davvero interessante di vedere le relazioni delle funzioni di cui sopra ed è stato un momento aha per me. (per favore, leggi il post di Mike sul fix point se non lo hai)

Tre funzioni

Per generalizzare, abbiamo una funzione non ricorsiva fn (come il nostro quasi-fattoriale), abbiamo la sua funzione punto fisso fr (come la nostra f), quindi ciò che fa Y è quando date Y fn , Y restituisce il punto fisso funzione di fn .

Quindi in sintesi (semplificato assumendo che fr accetta solo un parametro; x degenera in x - 1 , x - 2 … in ricorsione):

  • Definiamo i calcoli del nucleo come fn : def fn fr x = ...accumulate x with result from (fr (- x 1)) , questa è la funzione quasi utile – sebbene non possiamo usare fn direttamente su x , sarà utile molto presto. Questa fn non ricorsiva usa una funzione fr per calcolare il suo risultato
  • fn fr = fr , fr è il punto fisso di fn , fr è la funzione utile , possiamo usare fr su x per ottenere il nostro risultato
  • Y fn = fr , Y restituisce il punto fisso di una funzione, Y trasforma la nostra quasi utile funzione fn in utili fr

Derivazione Y (non inclusa)

Salterò la derivazione di Y e andrò a capire Y Il post di Mike Vainer ha molti dettagli.

La forma di Y

Y è definito come (in formato lambda calcolo ):

 Y f = λs.(f (ss)) λs.(f (ss)) 

Se sostituiamo la variabile s nella parte sinistra delle funzioni, otteniamo

 Y f = λs.(f (ss)) λs.(f (ss)) => f (λs.(f (ss)) λs.(f (ss))) => f (Y f) 

Quindi, in effetti, il risultato di (Y f) è il punto fisso di f .

Perché (Y f) funziona?

A seconda della firma di f , (Y f) può essere una funzione di qualsiasi aritmetica, per semplificare, supponiamo (Y f) prende solo un parametro, come la nostra funzione fattoriale.

 def fn fr x = accumulate x (fr (- x 1)) 

da fn fr = fr , continuiamo

 => accumulate x (fn fr (- x 1)) => accumulate x (accumulate (- x 1) (fr (- x 2))) => accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1))) 

il calcolo ricorsivo termina quando il più interno (fn fr 1) è il caso base e fn non usa fr nel calcolo.

Guardando di nuovo su Y :

 fr = Y fn = λs.(fn (ss)) λs.(fn (ss)) => fn (λs.(fn (ss)) λs.(fn (ss))) 

Così

 fr x = Y fn x = fn (λs.(fn (ss)) λs.(fn (ss))) x 

Per me, le parti magiche di questo setup sono:

  • fn e fr interdipendenti l’uno sull’altro: fr ‘wraps’ fn dentro, ogni volta che fr è usato per calcolare x , ‘spawn’ (‘lift’?) an fn e delega il calcolo a fn (passando in sé fr e x ); d’altra parte, fn dipende da fr e usa fr per calcolare il risultato di un problema minore x-1 .
  • Al momento fr è usato per definire fn (quando fn usa fr nelle sue operazioni), il vero fr non è ancora definito.
  • È fn che definisce la vera logica di business. Basato su fn , Y crea fr – una funzione di supporto in una forma specifica – per facilitare il calcolo di fn in modo ricorsivo .

Mi ha aiutato a capire in questo modo in questo momento, spero che aiuti.

A proposito, ho trovato molto buono anche il libro Un’introduzione alla programmazione funzionale attraverso il Lambda Calculus , io sono solo una parte di ciò e il fatto che non ho potuto girare la testa su Y nel libro mi ha portato a questo post.

Ecco le risposte alle domande originali , compilate dall’articolo (che vale TOTALY vale la pena leggere) menzionate nella risposta di Nicholas Mancuso , così come altre risposte:

Cos’è un combinatore Y?

Un combinatore Y è un “funzionale” (o una funzione di ordine superiore – una funzione che opera su altre funzioni) che accetta un singolo argomento, che è una funzione che non è ricorsiva e restituisce una versione della funzione che è ricorsivo.


Un po ‘ricorsivo =), ma una definizione più approfondita:

Un combinatore – è solo un’espressione lambda senza variabili libere.
Variabile libera – è una variabile che non è una variabile vincasting.
Variabile legata – variabile che è contenuta all’interno del corpo di un’espressione lambda che ha il nome di tale variabile come uno dei suoi argomenti.

Un altro modo di pensare a questo è che combinator è un’espressione lambda, in cui è ansible sostituire il nome di un combinatore con la sua definizione ovunque sia trovato e avere tutto ancora funzionante (si otterrà un ciclo infinito se il combinatore contenere riferimento a se stesso, all’interno del corpo lambda).

Il combinatore Y è un combinatore a virgola fissa.

Il punto fisso di una funzione è un elemento del dominio della funzione che è mappato a se stesso dalla funzione.
Vale a dire, c è un punto fisso della funzione f(x) if f(c) = c
Ciò significa f(f(...f(c)...)) = fn(c) = c

Come funzionano i combinatori?

Gli esempi sottostanti presuppongono una digitazione forte + dynamic :

Combinatore Y pigro (normale):
Questa definizione si applica alle lingue con valutazione pigra (anche: differita, call-by-need) – strategia di valutazione che ritarda la valutazione di un’espressione fino a quando il suo valore è necessario.

 Y = λf.(λx.f(xx)) (λx.f(xx)) = λf.(λx.(xx)) (λx.f(xx)) 

Ciò significa che, per una data funzione f (che è una funzione non ricorsiva), la funzione ricorsiva corrispondente può essere ottenuta prima calcolando λx.f(xx) , e quindi applicando questa espressione lambda a se stessa.

Combinatore Y rigoroso (di ordine applicativo):
Questa definizione si applica alle lingue con una valutazione severa (anche: desiderosa, avida) – strategia di valutazione in cui un’espressione viene valutata non appena associata a una variabile.

 Y = λf.(λx.f(λy.((xx) y))) (λx.f(λy.((xx) y))) = λf.(λx.(xx)) (λx.f(λy.((xx) y))) 

È identico a quello pigro nella sua natura, ha solo un wrapper λ extra per ritardare la valutazione del corpo di lambda. Ho fatto un’altra domanda , in qualche modo legata a questo argomento.

Per cosa stanno bene?

Sottratto in prestito dalla risposta di Chris Ammerman : il combinatore Y generalizza la ricorsione, estraendone l’implementazione e quindi separandola dal lavoro effettivo della funzione in questione.

Anche se, Y-combinator ha alcune applicazioni pratiche, è principalmente un concetto teorico, la cui comprensione amplierà la tua visione generale e, probabilmente, aumenterà le tue capacità di analisi e di sviluppo.

Sono utili nei linguaggi procedurali?

Come affermato da Mike Vanier : è ansible definire un combinatore a Y in molti linguaggi tipizzati staticamente, ma (almeno negli esempi che ho visto) tali definizioni di solito richiedono alcuni hackery di tipo non ovvio, perché lo stesso combinatore Y non lo fa t avere un tipo statico semplice. Questo va oltre lo scopo di questo articolo, quindi non ne parlerò più oltre

E come menzionato da Chris Ammerman : la maggior parte delle lingue procedurali ha una tipizzazione statica.

Quindi rispondi a questo – non proprio.

Penso che il modo migliore per rispondere a questo è scegliere una lingua, come JavaScript:

 function factorial(num) { // If the number is less than 0, reject it. if (num < 0) { return -1; } // If the number is 0, its factorial is 1. else if (num == 0) { return 1; } // Otherwise, call this recursive procedure again. else { return (num * factorial(num - 1)); } } 

Ora riscrivilo in modo che non usi il nome della funzione all'interno della funzione, ma continui a chiamarlo in modo ricorsivo.

L'unico posto dove dovrebbe essere visualizzato il nome della funzione factorial è sul sito di chiamata.

Suggerimento: non puoi usare nomi di funzioni, ma puoi usare nomi di parametri.

Lavora il problema Non cercare. Una volta risolto, capirai quale problema risolve il combinatore y.