Quali sono combinatori super e le forme applicative costanti?

Question

sto lottando con quali Super combinatori sono:

A supercombinator è una costante, o un combinatore che contiene solo supercombinators come subespressioni.

E anche con quello che costanti forme applicative sono:

Ogni combinatore eccellente che non è un'astrazione lambda. Questo include espressioni veramente costanti come 12, ((+) 1 2), [1,2,3] funzioni nonché parzialmente applicati quali ((+) 4). Si noti che questo ultimo esempio è equivalente in eta astrazione per \ x -> (+) 4 x che non è un CAF

.

Questo è solo non facendo alcun senso per me! Non è ((+) 4) proprio come "realmente costante" come 12? CAF suonano come valori per la mia mente semplice.

Answer 1

Queste pagine wiki Haskell si fa riferimento sono vecchi, e credo che, purtroppo scritto. Particolarmente spiacevole è che si mescolano fino CAF e supercombinators. Supercombinators sono interessanti, ma estranei a GHC. CAF sono ancora molto una parte di GHC, e possono essere comprese senza riferimento ad supercombinators.

---

Quindi cominciamo con supercombinators . Combinatori derivano da combinatoria logica , e, nell'uso qui, consistere di funzioni che si applicano solo la valori passati l'uno all'altro in una o un'altra forma - cioè combinano loro argomenti. Il set più famoso dei combinatori sono S, K, ed io , che nel loro insieme sono Turing- completare. Supercombinators, in questo contesto, sono funzioni costruite solo valori passati, combinatori e altri supercombinators. Quindi, qualsiasi supercombinator può essere espansa, mediante sostituzione, in un vecchio combinatore semplice.

Alcuni compilatori per i linguaggi funzionali (non GHC!) Usa combinatori e supercombinators alle fasi intermedie in compilation. Come con qualsiasi tecnologia compilatore simile, il motivo per fare questo è quello di ammettere analisi di ottimizzazione che viene più facilmente eseguito in una semplificata, il linguaggio come minimo. Un tale linguaggio di base costruita su supercombinators è di Edwin Brady epico .

---

Constant forme applicative sono qualcosa di completamente diverso. Sono un po 'più sottile, e hanno un paio di grattacapi. Il modo di pensare di loro è un aspetto di attuazione compilatore senza alcun significato semantico separata ma con un potenziale effetto profondo sulla prestazione di esecuzione. Quanto segue non può essere una perfetta descrizione di un CAF, ma sarà cercare di trasmettere la mia intuizione di ciò che si è, dal momento che non ho visto un davvero buona descrizione qualsiasi altro luogo per me per culla da . Il pulito descrizione "autorevole" nel Commento GHC Wiki recita:

Constant Moduli applicative, o CAF in breve, sono valori di primo livello definito in un programma. Essenzialmente, essi sono oggetti che non sono allocato dinamicamente in fase di esecuzione, ma, invece, fanno parte della statica i dati del programma.

Questo è un buon inizio. Pure, funzionali, lingue pigri possono essere considerati in un certo senso come una macchina riduzione del grafico. La prima volta che si richiede il valore di un nodo, che le forze sua valutazione, che a sua volta può richiedere i valori di sottonodi, ecc Uno un nodo viene valutata, i bastoni valore risultante muoversi (anche se non è di restare - poiché questo è un puro linguaggio potremmo sempre mantenere i sottonodi vivono e ricalcolare senza alcun effetto semantico). Un CAF è davvero solo un valore. Ma, nel contesto, un particolare tipo di valore - quello che il compilatore in grado di determinare ha un significato completamente dipendente dalle sue sotto-nodi. Vale a dire:

foo x = ...
  where thisIsACaf = [1..10::Int]

        thisIsNotACaf = [1..x::Int]
        thisIsAlsoNotACaf :: Num a => [a]
        thisIsAlsoNotACaf = [1..10] -- oops, polymorphic! the "num" dictionary is implicitly a parameter.

        thisCouldBeACaf = const [1..10::Int] x -- requires a sufficiently smart compiler
        thisAlsoCouldBeACaf _ = [1..10::Int] -- also requires a sufficiently smart compiler

Quindi perché ci importa se le cose sono CAF? Fondamentalmente perché a volte abbiamo davvero non vogliamo per ricalcolare qualcosa (ad esempio, un memotable!) E così vogliamo fare in modo che sia condivisa correttamente. Altre volte abbiamo davvero do vogliamo per ricalcolare qualcosa (ad esempio un enorme noiosa facile per generare l'elenco - come ad esempio i naturali - che siamo solo a piedi sopra) e non hanno il bastone in giro in memoria per sempre . Una combinazione di nominare le cose e legandoli sotto lascia o la scrittura in linea, ecc permette tipicamente Precisiamo questo genere di cose in un modo intuitivo naturale. Di tanto in tanto, però, il compilatore è più intelligente o più stupidi di quanto ci aspettiamo, e qualcosa che pensiamo dovrebbe essere calcolato solo una volta è sempre ricalcolato, o something non vogliamo di aggrapparsi a viene tirato fuori come un CAF. Poi, abbiamo bisogno di pensare le cose attraverso con più attenzione. Vedere la discussione per avere un'idea su alcune delle accorgimenti coinvolto: Un buon modo per evitare " condivisione "?

[A proposito, non mi sento all'altezza, ma chiunque voglia dovrebbero sentirsi liberi di prendere come gran parte di questa risposta come vogliono per cercare di integrarla con le pagine Wiki Haskell esistenti e di migliorare / aggiornamento li]

Answer 2

Matt si trova proprio di che la definizione è fonte di confusione. E 'persino contraddittorie. Un CAF è definito come:

Ogni combinatore eccellente che non è un'astrazione lambda. Ciò comprende espressioni veramente costanti quali 12, ((+) 1 2), [1,2,3] come pure parzialmente funzioni applicato come ((+) 4).

Quindi, ((+) 4) è visto come un CAF. Ma nella frase successiva c'è stato detto che è equivalente a qualcosa che non è un CAF:

questo ultimo esempio è equivalente in eta astrazione \ x -> (+) 4 x che non è un CAF.

Sarebbe più pulito per escludere funzioni parzialmente applicate per il fatto che sono equivalenti a astrazioni lambda.