Il calcolo lambda è un sistema formale nella logica matematica per esprimere calcoli basati sull'astrazione e applicare funzioni utilizzando l'associazione e la sostituzione di variabili. Questo è un modello universale che può essere applicato alla progettazione di qualsiasi macchina Turing. Il calcolo lambda fu introdotto per la prima volta da Church, un famoso matematico, negli anni '30.
Il sistema consiste nella creazione di membri lambda e nell'esecuzione di operazioni di riduzione su di essi.
Spiegazioni e applicazioni
La lettera greca lambda (λ) è usata nelle espressioni lambda e nei termini lambda per denotare il legame di una variabile in una funzione.
Il calcolo Lambda può essere non digitato o digitato. Nella prima variante, le funzioni possono essere utilizzate solo se sono in grado di ricevere dati di questo tipo. I calcoli lambda tipizzati sono più deboli, possono esprimere un valore inferiore. Ma, d' altra parte, ti permettono di provare più cose.
Uno dei motivi per cui ci sono così tanti tipi diversi è il desiderio degli scienziati di fare di più senza rinunciare all'opportunità di dimostrare forti teoremi del calcolo lambda.
Il sistema ha applicazioni in molte aree diverse di matematica, filosofia, linguistica e informatica. Innanzitutto, il calcolo lambda è un calcolo che ha svolto un ruolo importante nello sviluppo della teoria dei linguaggi di programmazione. Sono gli stili di creazione funzionale che i sistemi implementano. Sono anche un argomento caldo di ricerca nella teoria di queste categorie.
Per manichini
Il calcolo lambda è stato introdotto dal matematico Alonzo Church negli anni '30 come parte della sua ricerca sui fondamenti della scienza. Il sistema originale si dimostrò logicamente incoerente nel 1935 quando Stephen Kleen e JB Rosser svilupparono il paradosso di Kleene-Rosser.
Più tardi, nel 1936, Church individuò e pubblicò solo la parte rilevante per i calcoli, quello che ora è chiamato il calcolo lambda non tipizzato. Nel 1940 introdusse anche una teoria più debole ma logicamente coerente nota come sistema di tipo primo. Nel suo lavoro, spiega l'intera teoria in termini semplici, quindi si può dire che Church ha pubblicato il calcolo lambda per i manichini.
Fino agli anni '60, quando la sua relazione con i linguaggi di programmazione divenne chiara, λ era solo un formalismo. Grazie alle applicazioni di Richard Montagu e di altri linguisti nella semantica del linguaggio naturale, il calcolo ha preso il posto d'onore sia nella linguistica che nell'informatica.
Origine del simbolo
Lambda non sta per una parola o un acronimo, deriva da un riferimento in Principal Mathematics di Russell seguito da due cambiamenti tipografici. Esempio di notazione: per una funzione f con f (y)=2y + 1 è 2ŷ + 1. E qui usiamo un accento circonflesso ("cappello") su y per etichettare la variabile di input.
La chiesa originariamente intendeva usare simboli simili, ma i tipografi non sono stati in grado di posizionare il simbolo del "cappello" sopra le lettere. Quindi, invece, l'hanno stampato originariamente come "/\y.2y+1". Nel successivo episodio di montaggio, i dattilografi hanno sostituito "/ \" con un carattere visivamente simile.
Introduzione al calcolo lambda
Il sistema consiste in un linguaggio di termini, che sono scelti da una certa sintassi formale, e un insieme di regole di trasformazione che ne consentono la manipolazione. L'ultimo punto può essere considerato come una teoria equazionale o come una definizione operativa.
Tutte le funzioni nel calcolo lambda sono anonime, il che significa che non hanno nomi. Prendono solo una variabile di input e il currying viene utilizzato per implementare grafici con più variabili.
Termini Lambda
La sintassi del calcolo definisce alcune espressioni come valide e altre come non valide. Proprio come diverse stringhe di caratteri sono programmi C validi e alcuni no. L'espressione effettiva del calcolo lambda è chiamata "termine lambda".
Le tre regole seguenti forniscono una definizione induttiva che può essereapplicare alla costruzione di tutti i concetti sintatticamente validi:
La stessa variabile x è un termine lambda valido:
- se T è LT e x è non costante, allora (lambda xt) è chiamato astrazione.
- se T e s sono concetti, allora (TS) è chiamato applicazione.
Nient' altro è un termine lambda. Quindi, un concetto è valido se e solo se può essere ottenuto applicando ripetutamente queste tre regole. Tuttavia, alcune parentesi possono essere omesse in base ad altri criteri.
Definizione
Le espressioni Lambda sono costituite da:
- variabili v 1, v 2, …, v n, …
- simboli di astrazione 'λ' e punto '.'
- parentesi ().
L'insieme Λ può essere definito induttivamente:
- Se x è una variabile, allora x ∈ Λ;
- x non è costante e M ∈ Λ, allora (λx. M) ∈ Λ;
- M, N ∈ Λ, quindi (MN) ∈ Λ.
Designazione
Per mantenere ordinata la notazione delle espressioni lambda, vengono comunemente utilizzate le seguenti convenzioni:
- Fra parentesi omesse: MN invece di (MN).
- Si presume che le applicazioni rimangano associative: si può scrivere MNP invece di ((MN) P).
- Il corpo dell'astrazione si estende ulteriormente a destra: λx. MN significa λx. (MN), non (λx. M) N.
- La sequenza delle astrazioni è ridotta: λx.λy.λz. N può essere λxyz. N.
Variabili libere e vincolate
L'operatore λ connette la sua non costante ovunque si trovi nel corpo dell'astrazione. Le variabili che rientrano nell'ambito sono chiamate vincolate. Nell'espressione λ x. M, la parte λ x viene spesso definita legante. Come a suggerire che le variabili diventano un gruppo con l'aggiunta di X x a M. Tutte le altre instabili sono dette libere.
Ad esempio, nell'espressione λ y. x x y, y - vincolato non permanente e x - libero. E vale anche la pena notare che la variabile è raggruppata in base alla sua astrazione "più vicina". Nell'esempio seguente, la soluzione del calcolo lambda è rappresentata da una singola occorrenza di x, che è correlata al secondo termine:
λ x. y (λ x. z x)
L'insieme delle variabili libere M è indicato come FV (M) ed è definito dalla ricorsione sulla struttura dei termini come segue:
- FV (x)={x}, dove x è una variabile.
- VV (λx. M)=VV (M) {x}.
- VV (MN)=VV (M) ∪ VV (N).
Una formula che non contiene variabili libere è chiamata chiusa. Le espressioni lambda chiuse sono anche note come combinatori e sono equivalenti ai termini della logica combinatoria.
Abbreviazione
Il significato delle espressioni lambda è determinato da come possono essere abbreviate.
Ci sono tre tipi di tagli:
- α-transform: modifica delle variabili associate (alpha).
- β-riduzione: applicazione di funzioni ai loro argomenti (beta).
- η-transform: copre la nozione di estensionalità.
Ecco anche quistiamo parlando delle equivalenze risultanti: due espressioni sono β-equivalenti se possono essere β-trasformate nella stessa componente, e α / η-equivalenza è definita in modo simile.
Il termine redex, abbreviazione di fatturato riducibile, si riferisce a sottoargomenti che possono essere ridotti da una delle regole. Calcolo Lambda per manichini, esempi:
(λ x. M) N è un beta redex nell'espressione per sostituire N con x in M. Il componente a cui si riduce un redex è chiamato suo ridotto. La riduzione (λ x. M) N è M [x:=N].
Se x non è libero in M, λ x. M x anche em-REDEX con regolatore M.
α-trasformazione
Le rinominazioni Alpha ti consentono di cambiare i nomi delle variabili associate. Ad esempio, x. x può dare λ y. y. I termini che differiscono solo nella trasformazione alfa sono detti α-equivalenti. Spesso, quando si utilizza il calcolo lambda, gli equivalenti α sono considerati reciproci.
Le regole esatte per la conversione alfa non sono del tutto banali. Innanzitutto, con questa astrazione, vengono rinominate solo le variabili associate allo stesso sistema. Ad esempio, la trasformata alfa λ x.λ x. x può portare a λ y.λ x. x, ma questo potrebbe non portare a λy.λx.y Quest'ultimo ha un significato diverso dall'originale. Questo è analogo al concetto di programmazione con shadowing variabile.
In secondo luogo, una trasformazione alfa non è possibile se risulta essere catturata da un' altra astrazione non permanente. Ad esempio, sostituendo x con y in λ x.λ y. x, quindi puoi ottenereλy.λy. u, che non è affatto la stessa cosa.
Nei linguaggi di programmazione con ambito statico, la conversione alfa può essere utilizzata per semplificare la risoluzione dei nomi. Allo stesso tempo, facendo attenzione che il concetto di variabile non mascheri la designazione nell'area di contenimento.
Nella notazione dell'indice De Bruyne, due termini alfa-equivalenti qualsiasi sono sintatticamente identici.
Sostituzione
Le modifiche scritte da E [V:=R] sono il processo di sostituzione di tutte le occorrenze libere della variabile V nell'espressione E con il turnover R. La sostituzione in termini di λ è definita dalla lambda della ricorsione calcolo sulla struttura del concetto come segue (nota: xey - solo variabili e M e N - qualsiasi espressione λ).
x [x:=N] ≡ N
y [x:=N] ≡ y se x ≠ y
(M 1 M 2) [x:=N] ≡ (M 1 [x:=N]) (M 2 [x:=N])
(λ x. M) [x:=N] ≡ λ x. M
(λ y. M) [x:=N] y λ y. (M [x:=N]) se x ≠ y, a condizione che y ∉ FV (N).
Per la sostituzione in un'astrazione lambda, a volte è necessario trasformare in α un'espressione. Ad esempio, non è vero che (λ x. Y) [y:=x] risulta in (λ x. X) perché la x sostituita avrebbe dovuto essere libera, ma alla fine è stata vincolata. La sostituzione corretta in questo caso è (λ z. X) fino a α-equivalenza. Si noti che la sostituzione è definita in modo univoco fino a lambda.
β-riduzione
La riduzione beta riflette l'idea di applicare una funzione. Beta-riduttivo è definito in terminisostituzione: ((X V. E) E ') è E [V:=E'].
Ad esempio, supponendo una codifica 2, 7, ×, c'è la seguente β-riduzione: ((λ n. N × 2) 7) → 7 × 2.
La riduzione beta può essere vista come la stessa del concetto di riducibilità locale sotto deduzione naturale tramite l'isomorfismo di Curry-Howard.
η-trasformare
Questa conversione esprime l'idea di estensibilità, che in questo contesto è che due funzioni sono uguali quando danno lo stesso risultato per tutti gli argomenti. Questa conversione scambia tra λ x. (F x) ef ogni volta che x non sembra libero in f.
Questa azione può essere considerata come la stessa del concetto di completezza locale nella deduzione naturale attraverso l'isomorfismo di Curry-Howard.
Forme normali e fusione
Per un calcolo lambda non tipizzato, la regola di β-riduzione generalmente non è né forte né debole normalizzante.
Tuttavia, si può dimostrare che la riduzione β si fonde quando si esegue prima della trasformazione α (cioè, due forme normali possono essere considerate uguali se è possibile una trasformazione α dall'una all' altra).
Pertanto, sia i termini fortemente normalizzanti che i termini debolmente aggiustanti hanno un'unica forma normale. Per i primi termini, è garantito che qualsiasi strategia di riduzione si traduca in una configurazione tipica. Considerando che per condizioni debolmente normalizzanti, alcune strategie di riduzione potrebbero non trovarlo.
Metodi di programmazione aggiuntivi
Ci sono molti modi di dire di creazione per il calcolo lambda. Molti di essi sono stati originariamente sviluppati nel contesto dell'utilizzo dei sistemi come base per la semantica di un linguaggio di programmazione, applicandoli efficacemente come costrutto di basso livello. Poiché alcuni stili includono un calcolo lambda (o qualcosa di molto simile) come snippet, queste tecniche trovano impiego anche nella creazione pratica, ma possono quindi essere percepite come oscure o estranee.
Costanti con nome
Nel calcolo lambda, una libreria assume la forma di un insieme di funzioni precedentemente definite, dove i termini sono solo costanti concrete. Il calcolo puro non ha il concetto di immutabili con nome poiché tutti i termini lambda atomici sono variabili. Ma possono anche essere imitati prendendo il mutabile come nome della costante, usando un'astrazione lambda per legare quel volatile nel corpo e applicando quell'astrazione alla definizione prevista. Quindi se usi f per rappresentare M in N, potresti dire
(λ f. N) M.
Gli autori spesso introducono un concetto sintattico come consentire di scrivere le cose in un modo più intuitivo.
f=da M a N
Concatenando tali definizioni, è possibile scrivere un "programma" di calcolo lambda come zero o più definizioni di funzione seguite da un singolo membro lambda, utilizzando quelle definizioni che costituiscono la maggior parte del programma.
Una notevole limitazione di questo è che il nome f non è definito in M,poiché M è al di fuori dell'ambito vincolante dell'astrazione lambda f. Ciò significa che un attributo di funzione ricorsivo non può essere utilizzato come M con let. La sintassi letrec più avanzata, che consente di scrivere definizioni di funzioni ricorsive in questo stile, utilizza invece combinatori a virgola fissa.
Analogi stampati
Questo tipo è un formalismo tipizzato che utilizza un simbolo per rappresentare un'astrazione di funzione anonima. In questo contesto, i tipi sono generalmente oggetti di natura sintattica assegnati a termini lambda. La natura esatta dipende dal calcolo in questione. Da un certo punto di vista, LI tipizzati possono essere considerati come perfezionamenti di LI non tipizzati. Ma d' altra parte, possono anche essere considerate una teoria più fondamentale e il calcolo lambda non tipizzato è un caso speciale con un solo tipo.
Le LI tipizzate sono le fondamenta dei linguaggi di programmazione e la spina dorsale di linguaggi funzionali come ML e Haskell. E, più indirettamente, stili di creazione imperativi. I calcoli lambda tipizzati svolgono un ruolo importante nello sviluppo di sistemi di tipi per linguaggi di programmazione. Qui, la tipizzazione di solito acquisisce le proprietà desiderate del programma, ad esempio, non causerà una violazione dell'accesso alla memoria.
I calcoli lambda tipizzati sono strettamente correlati alla logica matematica e alla teoria della dimostrazione attraverso l'isomorfismo di Curry-Howard e possono essere pensati come un linguaggio interno delle classi di categoria, ad esempio, cheè semplicemente lo stile delle chiusure cartesiane.
