λ Lambda Reducer
Calcolo lambda non tipizzato: alberi sintattici e riduzione passo dopo passo
Descrizione
Il calcolo lambda è il linguaggio minimo su cui si fonda la programmazione funzionale: una sola forma di astrazione λx.M, una sola forma di applicazione M N, e nient’altro. Da qui derivano i combinatori, i numerali di Church, i booleani e la ricorsione tramite il combinatore Y, che sono anche alla base dello Scheme di SICP.
Il riduttore mostra ogni espressione come albero sintattico e applica le riduzioni una alla volta, evidenziando i redex e le rinominazioni.
Cosa si può fare
- Scegliere un esempio: identità, combinatori K e S, numerali di Church (SUCC e ADD), booleani AND, combinatore Y e Omega.
- Scrivere una propria espressione:
λx.λy.x y,\x.x, applicazioni con più argomenti, nomi di più lettere. - Ridurre a passi: ordine normale (sinistra-esterno) o applicativo (argomenti prima), oppure clic diretto su un redex.
- Seguire l’α-conversione: quando una sostituzione catturerebbe una variabile libera, il binder viene rinominato (per esempio
ydiventay'). - Leggere la cronologia: ogni passo mostra il redex ridotto, le rinominazioni e il risultato in testo.
- Vedere gli scopi: passando sul λ (o toccandolo) si evidenziano tutte le occorrenze legate della variabile.
Il modello
- α-conversione: rinominare un parametro legato senza cambiare il significato, per esempio
λx.xdiventaλy.y. Serve a evitare la cattura quando si sostituisce. - β-riduzione: un redex
(λx.M) Nsi riduce sostituendoNper le occorrenze libere dixinM. - Ordine normale: riduce il redex più a sinistra e più esterno; se esiste una forma normale, questa strategia la trova.
- Ordine applicativo: riduce prima gli argomenti, come fa Scheme.
- Limite di passi: ogni espressione può eseguire al massimo 200 passi. Omega =
(λx.x x)(λx.x x)non termina e si ferma al limite.
Limiti. Il riduttore lavora sul calcolo puro: niente numeri o booleani primitivi, solo le loro codifiche di Church. Le definizioni dei preset (per esempio TRUE = λx.λy.x) vengono sostituite nell’espressione prima della riduzione.
Applicazioni pratiche
- Didattica dei linguaggi funzionali: vedere come la programmazione si riduce a sostituzioni e alberi.
- Corso di teoria della calcolabilità: osservare la divergenza di Omega e la ricorsione di Y.
- Studio di SICP: verificare a mano le codifiche di Church usate nel libro.
Sperimenta l’app sul desktop virtuale aprendo l’icona λ Lambda dal gruppo Mini Apps.