Questa è un'implementazione del combinatore Y in Scala:
scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)
Y: [T](func: (T => T) => (T => T))T => T
scala> def fact = Y {
| f: (Int => Int) =>
| n: Int =>
| if(n <= 0) 1
| else n * f(n - 1)}
fact: Int => Int
scala> println(fact(5))
120
Q1: come funziona il risultato 120 vieni fuori, passo dopo passo? Perché il Y(func) è definito come func(Y(func)), la Y dovrebbe diventare sempre di più, dove si perde la Y e come è il 120 venire fuori nel processo di peform?
Q2: Qual è la differenza tra
def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))(_:T)
e
def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))
Sono dello stesso tipo nello scala REPL, ma il secondo non può stampare il risultato 120?
scala> def Y[T](func: (T => T) => (T => T)): (T => T) = func(Y(func))
Y: [T](func: (T => T) => (T => T))T => T
scala> def fact = Y {
| f: (Int => Int) =>
| n: Int =>
| if(n <= 0) 1
| else n * f(n - 1)}
fact: Int => Int
scala> println(fact(5))
java.lang.StackOverflowError
at .Y(<console>:11)
at .Y(<console>:11)
at .Y(<console>:11)
at .Y(<console>:11)
at .Y(<console>:11)
risposte:
7 per risposta № 1Prima di tutto, nota che questo non è un Y-Combinator, poiché la versione lambda della funzione usa la variabile libera Y. È l'espressione corretta per Y, ma non un combinatore.
Quindi, per prima cosa mettiamo la parte che calcola il fattoriale in una funzione separata. Possiamo chiamarlo comp:
def comp(f: Int => Int) =
(n: Int) => {
if (n <= 0) 1
else n * f(n - 1)
}
La funzione fattoriale può ora essere costruita in questo modo:
def fact = Y(comp)
Q1:
Y è definito come func (Y (func)). Invochiamo infatti (5) che è in realtà Y (comp) (5), e Y (comp) valuta comp (Y (comp)). Questo è il punto chiave: noi fermati qui perché comp ha una funzione e questo non lo valuta fino a quando necessario. Quindi, il runtime vede comp (Y (comp)) come comp (???) perché la parte Y (comp) è una funzione e verrà valutata solo quando (se) necessaria.
Conoscete i parametri call-by-value e call-by-name in Scala? Se dichiari i tuoi parametri come someFunction(x: Int), verrà valutato non appena viene richiamata una funzione. Ma se lo dichiari come someFunction(x: => Int), quindi x non verrà valutato immediatamente, ma ail punto in cui viene utilizzato. La seconda chiamata è "call by name" e fondamentalmente definisce la tua x come una "funzione che non prende nulla e restituisce un Int". Quindi, se si passa a 5, si passa effettivamente a una funzione che restituisce 5. In questo modo si ottiene una valutazione lazy dei parametri di funzione, poiché le funzioni vengono valutate nel punto in cui vengono utilizzate.
Quindi, il parametro f in comp è una funzione, quindiviene valutato solo quando necessario, che si trova nel ramo else. Ecco perché tutto funziona - Y può creare una catena infinita di funzioni (func (func (func (...)))) ma la catena è pigra. Ogni nuovo collegamento viene calcolato solo se necessario.
Quindi, quando invochi il fatto (5), esso scorrerà attraverso il corpo nel ramo else e solo a quel punto verrà valutato f. Non prima. Dal momento che la tua Y è passata in comp () come parametro f, ci immergeremo nuovamente in comp (). Nel richiamo ricorsivo di comp () calcoleremo il fattoriale di 4. Quindi andremo di nuovo nel ramo else della funzione comp, quindi ci immergiamo in un altro livello di ricorsione (calcolo fattoriale di 3). Nota che in ogni chiamata di funzione il tuo Y ha fornito un comp come argomento per comp, ma è valutato solo nel ramo else. Una volta raggiunto il livello che calcola il fattoriale di 0, il ramo di se verrà innescato e smetteremo di immergerci più in basso.
Q2:
Questo
func(Y(func))(_:T)
è lo zucchero della sintassi per questo
x => func(Y(func))(x)
il che significa che abbiamo avvolto l'intera cosa in una funzione. Non abbiamo perso nulla facendo questo, solo guadagnato.
Cosa abbiamo guadagnato? Bene, è lo stesso trucco della risposta a una domanda precedente; in questo modo lo realizziamo func(Y(func)) verrà valutato solo se necessario poiché è racchiuso in una funzione. In questo modo eviteremo un loop infinito. Espansione di una funzione (singolo parametro) f in una funzione x => f (x) viene chiamata eta-espansione (puoi leggere di più a riguardo Qui).
Ecco un altro semplice esempio di eta-espansione: diciamo che abbiamo un metodo getSquare() che restituisce un semplice square() funzione (ovvero, una funzione che calcola il quadrato di un numero). Invece di restituire direttamente square (x), possiamo restituire una funzione che accetta x e restituisce square (x):
def square(x: Int) = x * x
val getSquare: Int => Int = square
val getSquare2: Int => Int = (x: Int) => square(x)
println(square(5)) // 25
println(getSquare(5)) // 25
println(getSquare2(5)) // 25
Spero che questo ti aiuti.
0 per risposta № 2
Non conosco la risposta, ma cercherò di indovinare def Y[T](f: ...) = f(...) il compilatore può provare a sostituire Y(f) con semplicemente f. Questo creerà una sequenza infinita di f(f(f(...))). Applicazione parziale f crei un nuovo oggetto e tale sostituzione diventa impossibile.