L'applicazione pratica di SKI tartaro e BCKW

Question

posso capire come creare e pensare al SCI e BCKW calcolo, ma non sono mai riuscito a trovare usi pratici. Forse non sto cercando abbastanza profondamente? Cioè, mi chiedo se (un esempio solo per favore, non sto insinuando che questo è vero) l'uso di Java Servlet S ampiamente e generatori Python sono un esempio di BCW e io sono solo in grado di vedere attraverso la foresta di alberi?

Answer 1

In Haskell, sono ovunque !

• B <$>
• C flip
• K pure
• id
• S <*>
• W is join

Da un punto di vista Haskell, mezzi <$> "fare in un contesto".

• mezzi (+2) <$> (*3) aggiungere due dopo la moltiplicazione per tre .
• mezzi (+2) <$> [1,2,3] aggiungono due a ogni elemento della lista .
• mezzi (+2) <$> (read . getLine) aggiungono due a il numero che ho appena letto .
• mezzi (+2) <$> someParser aggiungono due a il numero ho appena analizzata .

cose che hanno un contesto sono chiamati funtori . Tutti i vostri iteratori Java / Python / C ++ sono solo strane versioni inside-out di funtori.

Un altro collegamento: la S e K combinatore insieme sono Turing-completo. In Haskell, pure e <*> insieme formano un funtore applicativo.

Naturalmente, la comprensione di come gli altri combinatori adattano richiederà l'apprendimento Haskell. Ma Questo esempio mostra come combinatori vengono così radicata nella lingua.

Answer 2

Lo sci e BCKW calcoli si distaccano dal calcolo lambda (che ha applicazioni ben note nel concetto programmazione funzionale) perché sono in forma libera-punto . Vedi anche tacita programmazione . Essi costituiscono la base per comprendere come costruire programmi funzionali senza argomenti con nome.

Lo vediamo applicazioni di essa in alcune lingue (ad esempio, Joy e Cat ). Una volta ho postato su Lambda-the-Ultimate.org circa il rapporto di SK calcolo Cat e Joy.

Per quanto il suo valore. Calcoli SCI (o SK) BCKW e sono praticamente identici, ma la base BCKW è caduto fuori moda

Answer 3

Sebbene lambda e SCI calcolo non riflettono i sistemi di ingresso e uscita della maggior parte dei linguaggi di programmazione (ad esempio grafica, connessioni di rete, o forse ancora di ingresso e uscita di serie), il modo pratico di programmazione informatica è strutturato corrisponde a Lambda (e pertanto SCI e BCKW), come l'idea di ricorsione e piuttosto le funzioni modo sono chiamati. Molti di questi linguaggi di programmazione hanno astrazioni lambda per l'uso come funzioni.

Answer 4

E 'tutta una questione di controllo.

Forse iniziare ad un livello inferiore. Un sistema applicativo è solo un sistema in cui gli oggetti possono essere applicati ad altri oggetti. Un semplice esempio di un sistema applicativo è bash.     ls | Di Più Si potrebbe supporre che siano in qualche ambiente, e che i mezzi di cui sopra ls sull'ambiente, quindi fare di più. Nella notazione applicativa questo è     più @ (ls @ ambiente) Tuttavia, si potrebbe fare le cose più complicate come     ls | modello grep | Di Più Così ora in notazione applicativa questo è     più @ ((grep @ pattern) @ (ls @ ambiente)). Avviso grep @ modello. Grep è applicato ad un modello, che danno di nuovo il programma in modo che corrisponda quel modello nel risultato di ls. Questo è il punto di applicazione, di applicare un programma per argomenti, la costruzione di nuovi programmi da programmi "atomiche" (aka built-in). Tuttavia, non possiamo fare troppo la programmazione con solo l'applicazione o comandi incorporati primitiva. Abbiamo bisogno di un modo per strutturare il nostro ingresso e l'applicazione dei nostri primitivi al nostro ingresso.

E 'qui che entra in gioco lambda. Utilizzando lambda si può generalizzare il     (Grep @ pattern) Per l'applicazione di grep per qualsiasi ingresso,     (Grep @ X) Tuttavia, dobbiamo avere un modo per ottenere l'ingresso a grep. Così usiamo di solito funzioni.     f (X) = grep @ X Il suddetto processo è chiamato astrazione fuori l'argomento. Ma non v'è alcun motivo di pensare al nome F come essere speciale, quindi abbiamo una sintassi per esso:     lambda X. grep @ X Poi lambda X. grep @ X, può essere applicato ad un ingresso, e l'ingresso verrà sostituito nel corpo e valutata. Tuttavia, sostituendo può ottenere disordinato, variabili vincolate possono essere fastidioso per implementare su una macchina. S-K-I (o B, C, K, W) fornisce un modo per fare cose lambda senza sostituzione, e invece solo scambiando intorno applicazioni.

Per ricapitolare, l'applicazione è ciò che è interamente circa. E 'molto comodo alla ragione, a livello di applicazione di un programma per qualcosa (forse un altro programma). Lambda calcolo fornisce un modo per strutturare l'ingresso e l'applicazione di programmi per argomenti. SCI dà un modo per farlo lambda senza dover esplicitamente sostituto.

Si deve notare che la riduzione SKI è intrinsecamente pigro, quindi qualche considerazione può avere bisogno di essere fatto in un vero e proprio uso mondo della SCI all'applicazione struttura. Infatti, gli argomenti potrebbero ora sono state pienamente valutate, e possono essere una parziale applicazione pure. Si può aggirare il problema con una teoria tipo, e solo valutare un programma sul suo ingresso se il programma è nella posizione della testa della domanda. Vale a dire, se si scrive con termini lambda chiusi, tradotti per le piste, allora se p @ arg1 @ .... Dovrebbe essere il caso che se p è un programma primitivo, allora la riscrittura è stata completata, e quindi tutto è argomenti sono 1) disponibili, 2) completamente valutati. Tuttavia, non ho dimostrato questo, e potrebbe non essere vero con un forte abbastanza tipo di teoria ...