Sequenziamento o continuazione-Passatura in Pure Lambda-Calculus

Question

Sto cercando di risolvere il seguente esercizio dato da qui .

Considera la seguente rappresentazione del numero. Come definire l'aggiunta?

|0| = λx.x
|1| = λx.λx.x
 ...
|n + 1| = λx.|n|

.

Il successore e gli operatori del predecessore sono facili da definire:

Succ n = λx.n
Pred n = n (λx.x)

.

Una soluzione "ovvia" per la definizione dell'aggiunta è utilizzare l'operazione del successore più il test per zero insieme al combinatore di punti fissi, qualcosa come (YF) per F Dato di seguito (l'operatore Se e Booleans sono definiti come al solito):

F = λf.(λm n. if (Is0 m) n (Succ (f (Pred m) n))

.

Ma definendo IS0 sembra non banale. Il problema è che un numero | n | consuma n + 1 argomenti e n argomenti sono semplicemente cancellati da esso. Quindi, se applico una tale funzione, sembra ragionevole impedire la sua applicazione quando diventa chiaro che il numero, ad es. non è un'identità. Immagino sia una sorta di continuazione, ma non riesco a immaginare come modellarlo nel Pure Lambda-Calculus. Forse qualcuno conosce qualche consiglio che può aiutare?

Un operatore di sequenziamento può anche aiutare a definire l'aggiunta. Se un'applicazione di un numero | M | è in ritardo fino a quando un numero | n | è applicato a tutti i suoi argomenti, il risultato sarà esattamente Un numerale | N + M | . Forse esiste una variante di un tale combinatore di sequenziamento nel Pure Lambda-Calculus?

La risposta fornita dall'autore dell'esercizio utilizza un'operazione non purea (cioè, isproceri che controlla se il suo argomento è una funzione).

UPDRE: Non è difficile da eseguire un CPS in Lambda-Calculus (i dettagli per CBV possono essere trovati qui ). Sembra che non sia abbastanza per risolvere il problema.

Uffi : Se abbiamo una versione di Quote-Eval funzioni per il Pure Lambda-Calculus, quindi ci deve essere una funzione $ EQ $ , che riconosce se le espressioni lambda-espressioni quotate sono sintatticamente uguali, e possiamo costruire is0 usando $ EQ $ . Ma dubito che $ EQ $ è definibile. La ragione è "Genericity Lemma" (Barendregt Book, Lemma 14.3.24). Se fossimo in grado di testare l'uguaglianza sui termini Lambda-termini quotati ( $ EQ $ ( quote $ \ Omega $ ) ( Quote $ \ Lambda xx $ )) restituire $ False $ e la Genericity implica che ( $ EQ $ ( Quote $ \ Lambda xx $ ) ( Quote $ \ Lambda xx $ )) Restituirebbe anche $ false $ . Questo contradditto una possibilità di costruire Quote nel Pure Lambda-Calculus?

Answer 1

Non penso che troverai quello che stai cercando nel Pure Lambda Calculus. La chiave è questa affermazione che hai fatto:

.

Un operatore di sequenziamento può anche aiutare a definire l'aggiunta. Se un'applicazione di un numero | M | è ritardato fino a un numero | n | è applicato a tutti i suoi argomenti, ...

Bene, i modelli del calcolo della lambda dovrebbero essere come:

$$ u \ cong u ^ u $$

E il punto di Questo è che ogni valore semantico $ u \ in u $ può essere applicato a qualcosa. Quindi non ha senso parlare di qualcosa di essere "applicato a tutti i suoi argomenti". Non c'è valore che non può essere applicato a più argomenti nel calcolo della lambda puro.

Non conosco la mano di un modello / argomento che questa rappresentazione di Naturals rende impossibile implementare IsZero, anche se alcuni pensieri lo sembra improbabile. Tuttavia, se deve essere possibile nel Pure Lambda Calculus, dovrà percepire un senso semanticamente e non essere basato su nozioni solo sintattiche.

Modifica: qui è uno schizzo di un argomento. Una definizione di $ \ mathsf {ISZERO} $ deve eventualmente ridurre come:

$$ \ MathSF {ISZERO} \ N \ Rantsquigarrow ^ * n \ Everlightarrow v $$

Il motivo è che l'applicazione a un certo numero di valori è l'unico meccanismo nel calcolo della lambda per distinguere effettivamente tra numeri. Deve essere il caso che: $$ 0 \ Everlightarrow v=mathsf {true} \\ \ mathsf {s} n \ overligrow v=mathsf {false} $$ Tuttavia, per ogni $ \ Everlightarrow V $ È il caso che: $$ || \ Everligrow V | + K | \ Everligarrow v= | k | $$ (dove $ | \ Everlightarrow v | $ è la lunghezza di $ \ Everlightarrow V $ ). Ma solo $ | 1 |=mathsf {false} $ (se questa è la convenzione scelta). In inglese, non vi è alcun limite per il numero di termini necessari per ottenere un booleano applicando un numero. Quindi non ci può essere una $ \ Everlightarrow V $ che soddisfa le equazioni per tutti i numeri, e quindi $ \ MAWSF {ISZERO} $ non può essere definito.

Answer 2

Il modo più semplice per definire l'aggiunta in Lambda-calcolo è trattare i numeri come se fossero elenchi collegati e catenate gli elenchi.Per fare questo diritto, è necessario utilizzare variabili aggiuntive per sostituire le variabili esterne di ciascun numero, quindi l'espressione risultante per il secondo numero può essere sostituita per la variabile interna dell'espressione risultante per il primo numero.Questo produce la seguente espressione per l'aggiunta:

  λw.λx.λy.λz.w y (x y z)

.