[Functional-programming] Cos'è un combinatore Y?


Answers

Un combinatore Y è un "funzionale" (una funzione che opera su altre funzioni) che consente la ricorsione, quando non è possibile 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 expression 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 static-typed (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 costruire 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<Double, Double>, Func<Double, Double>> 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<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> 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 .

Question

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?



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).




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  =  f x

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
   |  E E      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),

E F G

è una scorciatoia per

(E F) 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. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

Una prova formale che

1 + 2  =  3

utilizzando la regola di riscrittura della riduzione beta:

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f (f (f x))                                       Normal form
=  3

combinatori

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

λ x. x

isomorfo alla funzione di identità

id x = x

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

S  =  λ x y z. x z (y z)
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. x x

a se stesso:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     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. x x) (λ y. y y))

diverge sotto una desiderosa riduzione beta per ordine applicativo

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

da allora in una semantica rigorosa

forall f.  f _|_  =  _|_

ma converge sotto la pigra riduzione del normale ordine beta

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  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 (x x)) (λ x. f (x x))

è dato da

   Y g
=  (λ f. (λ x. f (x x)) (λ x. f (x x))) g
=  (λ x. g (x x)) (λ x. g (x x))           =  Y g
=  g ((λ x. g (x x)) (λ x. g (x x)))       =  g (Y g)
=  g (g ((λ x. g (x x)) (λ x. g (x x))))   =  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. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

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])



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);



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' JavaScript (non da me btw.)




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.




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 vincolata.
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 è possibile 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 + dinamica :

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(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))

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.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) 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?

As stated by Mike Vanier : it is possible to define a Y combinator in many statically typed languages, but (at least in the examples I've seen) such definitions usually require some non-obvious type hackery, because the Y combinator itself doesn't have a straightforward static type. That's beyond the scope of this article, so I won't mention it further

And as mentioned by Chris Ammerman : most procedural languages has static-typing.

So answer to this one — not really.




Mi chiedo se ci sia qualche utilità nel tentativo di costruire 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);
    };
});