Lambda calcolo
ciao!devo frequentare il corso di programmazione funzionale e visto che i corsi iniziano fra una settimana,stavo provando a guardarmi le prime cose da solo. Sono arrivata a lambda calcolo e le relative regole e applicazioni. Non riesco a capire come si fa tale riduzioni ai minimi termini
(kx.x(xy))(kz.zx) dove k è alfa allora il mio primo dubbio è il seguente....Io so che se scrivo kx.x applico la funzione a x e il mio output sarà x..allora quando invece ho kx.x(xy) cosa vuol dire? Pensando al passo di riduzione ho pensato che sono i valori di input quindi kx.x ottengo x e lo sostituisco con xy..ma non so. Allora applicando le regole del lambda calcolo,parto dalla parentesi più a sinistra è interna e trovo xy quindi visto che la funzione kx.x che da x mi rimane x(xy) e con il ragionamento della riduzione se xy sono gli input gli sostituisco a x
Infine mi potete spiegare passo per passo e applicazione delle regole da attuare in questo caso?
(kx.x(xy))(kz.zx) dove k è alfa allora il mio primo dubbio è il seguente....Io so che se scrivo kx.x applico la funzione a x e il mio output sarà x..allora quando invece ho kx.x(xy) cosa vuol dire? Pensando al passo di riduzione ho pensato che sono i valori di input quindi kx.x ottengo x e lo sostituisco con xy..ma non so. Allora applicando le regole del lambda calcolo,parto dalla parentesi più a sinistra è interna e trovo xy quindi visto che la funzione kx.x che da x mi rimane x(xy) e con il ragionamento della riduzione se xy sono gli input gli sostituisco a x
Infine mi potete spiegare passo per passo e applicazione delle regole da attuare in questo caso?
Risposte
Ciao,
lambda forse vorresti dire
alfa (la lettera graca alpha) è utilizzata per denominare l'operazione di rinominazione delle variabili: $\alpha$-conversione.
la grammatica del lambda calcolo è:
e ::= x | e e (applicazione) | $\lambda$x.e (astrazione)
l'applicazione è l'unica che ha una regola effettiva: la beta-riduzione, che è in pratica la sostituzione
$(\lambdax.x)\ y\ ->_{\beta} \ x{y|x} -= y$
strategia di riduzione: leftmost-innermost
non ti suggerisco di utilizzare questa. Non sempre porta ad una riduzione ha forma normale (minimi termini), ma usa la leftmost-outermost (più a sinistra e più esterna).
se utilizzi leftmost-innermost oppure leftmost-outermost (non cambia in questo caso):
$(\lambdax.x\ (x\ y))\ (\lambdaz.z\ x) -> (\lambdaz.z\ x)\ ((\lambdaz.z\ x)\ y)\ -> (\lambdaz.z\ x)\ (y\ x)\ -> y\ x\ x$
(kx.x(xy))(kz.zx) dove k è alfa
lambda forse vorresti dire
alfa (la lettera graca alpha) è utilizzata per denominare l'operazione di rinominazione delle variabili: $\alpha$-conversione.
allora il mio primo dubbio è il seguente....Io so che se scrivo kx.x applico la funzione a x e il mio output sarà x..allora quando invece ho kx.x(xy) cosa vuol dire? Pensando al passo di riduzione ho pensato che sono i valori di input quindi kx.x ottengo x e lo sostituisco con xy..ma non so.
la grammatica del lambda calcolo è:
e ::= x | e e (applicazione) | $\lambda$x.e (astrazione)
l'applicazione è l'unica che ha una regola effettiva: la beta-riduzione, che è in pratica la sostituzione
$(\lambdax.x)\ y\ ->_{\beta} \ x{y|x} -= y$
Allora applicando le regole del lambda calcolo,parto dalla parentesi più a sinistra è interna
strategia di riduzione: leftmost-innermost
non ti suggerisco di utilizzare questa. Non sempre porta ad una riduzione ha forma normale (minimi termini), ma usa la leftmost-outermost (più a sinistra e più esterna).
e trovo xy quindi visto che la funzione kx.x che da x mi rimane x(xy) e con il ragionamento della riduzione se xy sono gli input gli sostituisco a x
Infine mi potete spiegare passo per passo e applicazione delle regole da attuare in questo caso?
se utilizzi leftmost-innermost oppure leftmost-outermost (non cambia in questo caso):
$(\lambdax.x\ (x\ y))\ (\lambdaz.z\ x) -> (\lambdaz.z\ x)\ ((\lambdaz.z\ x)\ y)\ -> (\lambdaz.z\ x)\ (y\ x)\ -> y\ x\ x$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo