Dal momento che le lingue con prima classe ricorsivale funzioni sono complete di Turing, dovrebbero essere in grado di esprimere qualsiasi cosa sia possibile esprimere in qualsiasi altro linguaggio di programmazione. Pertanto, dovrebbe essere possibile modellare espressioni condizionali (cioè istruzioni if) con funzioni di prima classe. Qualcuno potrebbe illustrare come farlo?
risposte:
6 per risposta № 1Il solito codifica dei booleani, a causa della Chiesa, è
$$ {sf vero} = lambda x. lambda y. X qquad {sf false} = lambda x. lambda y. y $$
Approssimativamente, "true" è la funzione che prende due argomenti $ x, y $ (prima prende $ x $, quindi prende anche $ y $) e restituisce il primo. Invece, "false" restituisce il secondo.
If-then-else viene quindi codificato applicando un booleano codificato ai rami "then" e "else". In questo modo, il valore booleano sceglie il valore corretto da restituire.
$$ {sf if} b {sf then} t {sf else} e = b, t, e $$
È quindi facile controllare le cosiddette leggi "$ beta $":
$$ {sf if true then} t {sf else} e = {sf true}, t, e = (lambda x.lambda y.x), t, e = (lambda y.t), e = t $$
e
$$ {sf if false then} t {sf else} e = {sf false}, t, e = (lambda x.lambda y.y), t, e = (lambda y.y), e = e $$
In sostanza, queste leggi stabiliscono cosa succede quando "costruisci" un booleano (usando le costanti $ sf true, false $), e poi "distruggilo" in seguito (usandolo in $ sf se poi altrimenti $).
Usando le funzioni in questo modo, si possono scrivere codifiche per tutti i tipi di dati usuali, come i naturali, le coppie, le varianti, gli elenchi, gli alberi, ecc.