Codifica della Chiesa - Church encoding

In matematica , la codifica di Church è un mezzo per rappresentare dati e operatori nel lambda calcolo . I numeri della Chiesa sono una rappresentazione dei numeri naturali utilizzando la notazione lambda. Il metodo prende il nome da Alonzo Church , che per primo ha codificato i dati nel calcolo lambda in questo modo.

I termini che di solito sono considerati primitivi in ​​altre notazioni (come interi, booleani, coppie, elenchi e unioni con tag) sono mappati a funzioni di ordine superiore sotto la codifica Church. La tesi di Church-Turing afferma che qualsiasi operatore calcolabile (ei suoi operandi) può essere rappresentato con la codifica di Church. Nel lambda calcolo non tipizzato l'unico tipo di dati primitivo è la funzione.

La codifica Church non è intesa come un'implementazione pratica di tipi di dati primitivi. Il suo uso è mostrare che altri tipi di dati primitivi non sono necessari per rappresentare alcun calcolo. La completezza è rappresentativa. Sono necessarie funzioni aggiuntive per tradurre la rappresentazione in tipi di dati comuni, per la visualizzazione alle persone. Non è possibile in generale decidere se due funzioni sono estensionalmente uguali a causa dell'indecidibilità dell'equivalenza dal teorema di Church . La traduzione può applicare la funzione in qualche modo per recuperare il valore che rappresenta o cercare il suo valore come un termine lambda letterale.

Il calcolo lambda viene solitamente interpretato come l'uso dell'uguaglianza intensionale . Ci sono potenziali problemi con l'interpretazione dei risultati a causa della differenza tra la definizione intensionale ed estensionale di uguaglianza.

numeri della chiesa

I numeri della chiesa sono le rappresentazioni dei numeri naturali sotto la codifica della chiesa. La funzione di ordine superiore che rappresenta il numero naturale n è una funzione che mappa qualsiasi funzione alla sua composizione n volte . In termini più semplici, il "valore" del numero è equivalente al numero di volte in cui la funzione incapsula il suo argomento. ${\displaystyle f}$

${\displaystyle f^{\circ n}=\underbrace {f\circ f\circ \cdots \circ f} _{n{\text{ volte}}}.\,}$

Tutti i numeri di chiesa sono funzioni che accettano due parametri. I numeri di chiesa 0 , 1 , 2 , ..., sono definiti come segue nel lambda calcolo .

Partendo da 0 non applicando affatto la funzione, procedi con 1 applicando la funzione una volta, 2 applicando la funzione due volte, 3 applicando la funzione tre volte, ecc .:

${\displaystyle {\begin{array}{r|l|l}{\text{Numero}}&{\text{Definizione della funzione}}&{\text{espressione Lambda}}\\\hline 0&0\ f\ x =x&0=\lambda f.\lambda xx\\1&1\ f\ x=f\ x&1=\lambda f.\lambda xf\ x\\2&2\ f\ x=f\ (f\ x)&2=\lambda f.\lambda xf\ (f\ x)\\3&3\ f\ x=f\ (f\ (f\ x))&3=\lambda f.\lambda xf\ (f\ (f\ x))\ \\vdots &\vdots &\vdots \\n&n\ f\ x=f^{n}\ x&n=\lambda f.\lambda xf^{\circ n}\ x\end{array}}}$

Il numero di chiesa 3 rappresenta l'azione di applicare una data funzione tre volte a un valore. La funzione fornita viene prima applicata a un parametro fornito e quindi successivamente al proprio risultato. Il risultato finale non è il numero 3 (a meno che il parametro fornito non sia 0 e la funzione sia una funzione successore ). La funzione stessa, e non il suo risultato finale, è il numero di Chiesa 3 . Il numero 3 della Chiesa significa semplicemente fare qualsiasi cosa tre volte. È una dimostrazione ostensiva di cosa si intende per "tre volte".

Calcolo con i numeri della Chiesa

Le operazioni aritmetiche sui numeri possono essere rappresentate da funzioni sui numeri di Chiesa. Queste funzioni possono essere definite in lambda calcolo o implementate nella maggior parte dei linguaggi di programmazione funzionali (vedi conversione di espressioni lambda in funzioni ).

La funzione di addizione utilizza l'identità . ${\displaystyle \nomeoperatore {più} (m,n)=m+n}$${\displaystyle f^{\circ (m+n)}(x)=f^{\circ m}(f^{\circ n}(x))}$

${\ Displaystyle \ operatorname {plus} \ equiv \ lambda m. \ lambda n. \ lambda f. \ lambda xm \ f \ (n \ f \ x)}$

La funzione successore è -equivalente a . ${\displaystyle \operatorname {succ} (n)=n+1}$${\displaystyle (\nomeoperatore {plus} \ 1)}$

${\ Displaystyle \ operatorname {succ} \ equiv \ lambda n. \ lambda f. \ lambda xf \ (n \ f \ x)}$

La funzione di moltiplicazione utilizza l'identità . ${\displaystyle \nomeoperatore {mult} (m,n)=m*n}$${\displaystyle f^{\circ (m*n)}(x)=(f^{\circ n})^{\circ m}(x)}$

${\ Displaystyle \ operatorname {mult} \ equiv \ lambda m. \ lambda n. \ lambda f. \ lambda xm \ (n \ f) \ x}$

La funzione di elevamento a potenza è data dalla definizione dei numeri di Chiesa, . Nella definizione sostituire per ottenere e, ${\displaystyle \nomeoperatore {exp} (m,n)=m^{n}}$${\displaystyle n\ h\ x=h^{n}\ x}$${\displaystyle h\to m, x\to f}$${\displaystyle n\ m\ f=m^{n}\ f}$

${\displaystyle \nomeoperatore {exp} \ m\ n=m^{n}=n\ m}$

che dà l'espressione lambda,

${\ Displaystyle \ nomeoperatore {exp} \ equiv \ lambda m. \ lambda nn \ m}$

La funzione è più difficile da capire. ${\displaystyle \operatorname {pred} (n)}$

${\ Displaystyle \ operatorname {pred} \ equiv \ lambda n. \ lambda f. \ lambda xn \ (\ lambda g. \ lambda hh \ (g \ f)) \ (\ lambda ux) \ (\ lambda uu)}$

Un numero di Chiesa applica una funzione n volte. La funzione predecessore deve restituire una funzione che applica il suo parametro n - 1 volte. Ciò si ottiene costruendo un contenitore attorno a f e x , che viene inizializzato in modo tale da omettere l'applicazione della funzione la prima volta. Vedi predecessore per una spiegazione più dettagliata.

La funzione di sottrazione può essere scritta in base alla funzione precedente.

${\ Displaystyle \ nomeoperatore {meno} \ equiv \ lambda m. \ lambda n. (n \ nome operatore {pred}) \ m}$

Tabella delle funzioni sui numeri della Chiesa

Funzione	Algebra	Identità	Definizione della funzione	Espressioni lambda
Successore	${\displaystyle n+1}$	${\displaystyle f^{n+1}\ x=f(f^{n}x)}$	${\displaystyle\operatorname {succ} \ n\ f\ x=f\ (n\ f\ x)}$	${\ Displaystyle \ lambda n. \ lambda f. \ lambda xf \ (n \ f \ x)}$	...
aggiunta	${\displaystyle m+n}$	${\displaystyle f^{m+n}\ x=f^{m}(f^{n}x)}$	${\displaystyle\operatorname {plus} \ m\ n\ f\ x=m\ f\ (n\ f\ x)}$	${\ Displaystyle \ lambda m. \ lambda n. \ lambda f. \ lambda xm \ f \ (n \ f \ x)}$	${\ Displaystyle \ lambda m. \ lambda nn \ nomeoperatore {succ} m}$
Moltiplicazione	${\displaystyle m*n}$	${\displaystyle f^{m*n}\ x=(f^{m})^{n}\ x}$	${\displaystyle\operatorname {moltiplicare} \ m\ n\ f\ x=m\ (n\ f)\ x}$	${\ Displaystyle \ lambda m. \ lambda n. \ lambda f. \ lambda xm \ (n \ f) \ x}$	${\displaystyle\lambda m.\lambda n.\lambda fm\ (n\f)}$
elevazione a potenza	${\displaystyle m^{n}}$	${\displaystyle n\ m\ f=m^{n}\ f}$	${\displaystyle\nomeoperatore {exp} \ m\ n\ f\ x=(n\ m)\ f\ x}$	${\ Displaystyle \ lambda m. \ lambda n. \ lambda f. \ lambda x. (n \ m) \ f \ x}$	${\displaystyle\lambda m.\lambda nn\ m}$
Predecessore *	${\displaystyle n-1}$	${\displaystyle \operatorname {inc} ^{n}\operatorname {con} =\operatorname {val} (f^{n-1}x)}$	${\displaystyle if(n==0)\ 0\ else\ (n-1)}$	${\displaystyle\lambda n.\lambda f.\lambda xn\ (\lambda g.\lambda hh\ (g\ f))\ (\lambda ux)\ (\lambda uu)}$
Sottrazione *	${\displaystyle mn}$	${\displaystyle f^{mn}\ x=(f^{-1})^{n}(f^{m}x)}$	${\displaystyle \nomeoperatore {meno} \ m\ n=(n\nomeoperatore {pred} )\ m}$	...	${\displaystyle\lambda m.\lambda nn\nomeoperatore {pred} m}$

* Nota che nella codifica della Chiesa,

• ${\displaystyle \operatorname {pred} (0)=0}$
• ${\displaystyle m<=n\to ​​mn=0}$

Derivazione della funzione predecessore

La funzione precedente utilizzata nella codifica della Chiesa è,

${\displaystyle \operatorname {pred} (n)={\begin{casi}0&{\mbox{se }}n=0,\\n-1&{\mbox{altrimenti}}\end{casi}}}$.

Per costruire il predecessore abbiamo bisogno di un modo per applicare la funzione 1 in meno tempo. Un numero n applica la funzione f n volte a x . La funzione predecessore deve utilizzare il numero n per applicare la funzione n -1 volte.

Prima di implementare la funzione predecessore, ecco uno schema che racchiude il valore in una funzione contenitore. Definiremo nuove funzioni da usare al posto di f e x , chiamate inc e init . La funzione contenitore è chiamata value . Il lato sinistro della tabella mostra un numero n applicato a inc e init .

${\displaystyle {\begin{array}{r|r|r}{\text{Numero}}&{\text{Usando init}}&{\text{Usando const}}\\\hline 0&\operatorname {init } =\nomeoperatore {valore} \ x&\\1&\nomeoperatore {inc} \ \nomeoperatore {init} =\nomeoperatore {valore} \ (f\ x)&\nomeoperatore {inc} \ \nomeoperatore {const} =\nomeoperatore {valore} \ x\\2&\nomeoperatore {inc} \ (\nomeoperatore {inc} \ \nomeoperatore {init} )=\nomeoperatore {valore} \ (f\ (f\ x))&\nomeoperatore {inc} \ (\operatorname {inc} \ \operatorname {const} )=\operatorname {valore} \ (f\ x)\\3&\operatorname {inc} \ (\operatorname {inc} \ (\operatorname {inc} \ \operatorname {init} ))=\operatorname {value} \ (f\ (f\ (f\ x)))&\operatorname {inc} \ (\operatorname {inc} \ (\operatorname {inc} \ \operatorname {const } ))=\operatorname {valore} \ (f\ (f\ x))\\\vdots &\vdots &\vdots \\n&n\operatorname {inc} \ \operatorname {init} =\operatorname {valore} \ (f^{n}\ x)=\nomeoperatore {valore} \ (n\ f\ x)&n\nomeoperatore {inc} \ \nomeoperatore {const} =\nomeoperatore {valore} \ (f^{n-1} \ x)=\o nomeoperatore {valore} \ ((n-1)\ f\ x)\\\end{array}}}$

La regola generale di ricorrenza è,

${\displaystyle \operatorname {inc} \ (\operatorname {valore} \ v)=\operatorname {valore} \ (f\ v)}$

Se c'è anche una funzione per recuperare il valore dal contenitore (chiamata extract ),

${\displaystyle \operatorname {estratto} \ (\operatorname {valore} \ v)=v}$

Quindi estrarre può essere usato per definire la funzione samenum come,

${\displaystyle \operatorname {samenum} =\lambda n.\lambda f.\lambda x.\operatorname {estratto} \ (n\operatorname {inc} \operatorname {init} )=\lambda n.\lambda f.\ lambda x.\nomeoperatore {estratto} \ (\nomeoperatore {valore} \ (n\ f\ x))=\lambda n.\lambda f.\lambda xn\ f\ x=\lambda nn}$

La funzione samenum non è intrinsecamente utile. Tuttavia, poiché inc delega la chiamata di f al suo argomento contenitore, possiamo fare in modo che sulla prima applicazione inc riceva un contenitore speciale che ignori il suo argomento consentendo di saltare la prima applicazione di f . Chiama questo nuovo contenitore iniziale const . Il lato destro della tabella sopra mostra le espansioni di n inc const . Quindi sostituendo init con const nell'espressione per la stessa funzione otteniamo la funzione predecessore,

${\displaystyle \operatorname {pred} =\lambda n.\lambda f.\lambda x.\operatorname {estratto} \ (n\operatorname {inc} \operatorname {const} )=\lambda n.\lambda f.\ lambda x.\nomeoperatore {estratto} \ (\nomeoperatore {valore} \ ((n-1)\ f\ x))=\lambda n.\lambda f.\lambda x.(n-1)\ f\ x =\lambda n.(n-1)}$

Come spiegato di seguito le funzioni inc , init , const , value ed extract possono essere definite come,

${\displaystyle {\begin{allineato}\operatorname {valore} &=\lambda v.(\lambda hh\v)\\\operatorname {estratto} k&=k\\lambda uu\\\operatorname {inc} &= \lambda g.\lambda hh\ (g\ f)\\\operatorname {init} &=\lambda hh\ x\\\operatorname {const} &=\lambda ux\end{aligned}}}$

Che dà l'espressione lambda per pred as,

${\displaystyle\operatorname {pred} =\lambda n.\lambda f.\lambda xn\ (\lambda g.\lambda hh\ (g\ f))\ (\lambda ux)\ (\lambda uu)}$

Un altro modo di definire pred

Pred può anche essere definito utilizzando le coppie:

${\displaystyle {\begin{allineato}\operatorname {f} =&\ \lambda p.\ \operatorname {coppia} \ (\operatorname {secondo} \ p)\ (\operatorname {succ} \ (\operatorname {secondo } \ p))\\\nomeoperatore {zero} =&\ (\lambda f.\lambda x.\ x)\\\nomeoperatore {pc0} =&\ \nomeoperatore {coppia} \ \nomeoperatore {zero} \ \ operatorname {zero} \\\operatorname {pred} =&\ \lambda n.\ \operatorname {first} \ (n\ \operatorname {f} \ \operatorname {pc0} )\\\end{aligned}}}$

Questa è una definizione più semplice, ma porta a un'espressione più complessa per pred. L'espansione per : ${\displaystyle \operatorname {pred} \operatorname {tre}}$

${\displaystyle {\begin{allineato}\operatorname {pred} \operatorname {tre} =&\ \operatorname {primo} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname {f} \ ( \operatorname {coppia} \ \operatorname {zero} \ \operatorname {zero} ))))\\=&\ \operatorname {primo} \ (\operatorname {f} \ (\operatorname {f} \ (\operatorname { coppia} \ \nomeoperatore {zero} \ \nomeoperatore {uno} )))\\=&\ \nomeoperatore {primo} \ (\nomeoperatore {f} \ (\nomeoperatore {coppia} \ \nomeoperatore {uno} \ \nomeoperatore {due} ))\\=&\ \operatorname {primo} \ (\operatorname {coppia} \ \operatorname {due} \ \operatorname {tre} )\\=&\ \operatorname {due} \end{allineato} }}$

Divisione

La divisione dei numeri naturali può essere attuata da,

${\displaystyle n/m=\nomeoperatore {se} \ n\geq m\ \nomeoperatore {allora} \ 1+(nm)/m\ \nomeoperatore {altrimenti} \ 0}$

Il calcolo richiede molte riduzioni beta. A meno che non si faccia la riduzione a mano, questo non importa molto, ma è preferibile non dover fare questo calcolo due volte. Il predicato più semplice per testare i numeri è IsZero, quindi considera la condizione. ${\displaystyle nm}$

${\displaystyle \operatorname {IsZero} \ (\operatorname {meno} \ n\ m)}$

Ma questa condizione è equivalente a , non . Se si usa questa espressione, la definizione matematica di divisione data sopra viene tradotta in funzione sui numeri di Chiesa come, ${\displaystyle n\leq m}$${\displaystyle n<m}$

${\displaystyle \operatorname {divide1} \ n\ m\ f\ x=(\lambda d.\operatorname {IsZero} \ d\ (0\ f\ x)\ (f\ (\operatorname {divide1} \ d\ m\ f\ x)))\ (\ nomeoperatore {meno} \ n\ m)}$

Come desiderato, questa definizione ha una singola chiamata a . Tuttavia il risultato è che questa formula fornisce il valore di . ${\displaystyle \nomeoperatore {meno} \ n\ m}$${\displaystyle (n-1)/m}$

Questo problema può essere corretto aggiungendo 1 a n prima di chiamare divide . La definizione di divisione è quindi,

${\displaystyle \operatorname {divide} \ n=\operatorname {divide1} \ (\operatorname {succ} \ n)}$

divide1 è una definizione ricorsiva. Il combinatore Y può essere utilizzato per implementare la ricorsione. Crea una nuova funzione chiamata div by;

• Nel lato sinistro ${\displaystyle \operatorname {divide1} \rightarrow \operatorname {div} \ c}$
• Nel lato destro ${\displaystyle \operatorname {divide1} \rightarrow c}$

ottenere,

${\displaystyle\operatorname {div} =\lambda c.\lambda n.\lambda m.\lambda f.\lambda x.(\lambda d.\operatorname {IsZero} \ d\ (0\ f\ x)\ (f\ (c\ d\ m\ f\ x)))\ (\ operatorname {meno} \ n\ m)}$

Quindi,

${\displaystyle \operatorname {divide} =\lambda n.\operatorname {divide1} \ (\operatorname {succ} \ n)}$

dove,

${\displaystyle {\begin{allineato}\operatorname {divide1} &=Y\\operatorname {div} \\\operatorname {succ} &=\lambda n.\lambda f.\lambda xf\ (n\ f\ x )\\Y&=\lambda f.(\lambda xf\ (x\ x))\ (\lambda xf\ (x\ x))\\0&=\lambda f.\lambda xx\\\operatorname {IsZero} &=\lambda nn\ (\lambda x.\operatorname {false} )\ \operatorname {true} \end{aligned}}}$

${\displaystyle {\begin{allineato}\operatorname {vero} &\equiv \lambda a.\lambda ba\\\operatorname {falso} &\equiv \lambda a.\lambda bb\end{allineato}}}$

${\displaystyle {\begin{allineato}\operatorname {meno} &=\lambda m.\lambda nn\operatorname {pred} m\\\operatorname {pred} &=\lambda n.\lambda f.\lambda xn\ (\lambda g.\lambda hh\ (g\ f))\ (\lambda ux)\ (\lambda uu)\end{allineato}}}$

Dà,

${\displaystyle \scriptstyle \operatorname {divide} =\lambda n.((\lambda f.(\lambda xx\ x)\ (\lambda xf\ (x\ x)))\ (\lambda c.\lambda n .\lambda m.\lambda f.\lambda x.(\lambda d.(\lambda nn\ (\lambda x.(\lambda a.\lambda bb))\ (\lambda a.\lambda ba))\ d\ ((\lambda f.\lambda xx)\ f\ x)\ (f\ (c\ d\ m\ f\ x)))\ ((\lambda m.\lambda nn(\lambda n.\ lambda f.\lambda xn\ (\lambda g.\lambda hh\ (g\ f))\ (\lambda ux)\ (\lambda uu))m)\ n\ m)))\ ((\lambda n .\lambda f.\lambda xf\ (n\ f\ x))\ n)}$

O come testo, usando \ per λ ,

divide = (\n.((\f.(\x.x x) (\x.f (x x))) (\c.\n.\m.\f.\x.(\d.(\n.n (\x.(\a.\b.b)) (\a.\b.a)) d ((\f.\x.x) f x) (f (c d m f x))) ((\m.\n.n (\n.\f.\x.n (\g.\h.h (g f)) (\u.x) (\u.u)) m) n m))) ((\n.\f.\x. f (n f x)) n))

Ad esempio, 9/3 è rappresentato da

divide (\f.\x.f (f (f (f (f (f (f (f (f x))))))))) (\f.\x.f (f (f x)))

Usando un calcolatore di lambda calcolo, l'espressione sopra si riduce a 3, usando l'ordine normale.

\f.\x.f (f (f (x)))

Numeri firmati

Un approccio semplice per estendere Church Numeri di numeri firmato è usare una coppia Chiesa, contenente numeri Chiesa rappresentano un positivo ed un valore negativo. Il valore intero è la differenza tra i due numeri di Chiesa.

Un numero naturale viene convertito in un numero con segno da,

${\displaystyle \operatorname {convert} _{s}=\lambda x.\operatorname {coppia} \ x\ 0}$

La negazione viene eseguita scambiando i valori.

${\displaystyle \operatorname {neg} _{s}=\lambda x.\operatorname {coppia} \ (\operatorname {secondo} \ x)\ (\operatorname {primo} \ x)}$

Il valore intero è rappresentato più naturalmente se una delle coppie è zero. La funzione OneZero realizza questa condizione,

${\displaystyle \operatorname {OneZero} =\lambda x.\operatorname {IsZero} \ (\operatorname {first} \ x)\ x\ (\operatorname {IsZero} \ (\operatorname {second} \ x)\ x\ (\operatorname {OneZero} \ \operatorname {pair} \ (\operatorname {pred} \ (\operatorname {first} \ x))\ (\operatorname {pred} \ (\operatorname {second} \ x)))) }$

La ricorsione può essere implementata utilizzando il combinatore Y,

${\displaystyle \operatorname {OneZ} =\lambda c.\lambda x.\operatorname {IsZero} \ (\operatorname {primo} \ x)\ x\ (\operatorname {IsZero} \ (\operatorname {secondo} \ x )\ x\ (c\ \operatorname {coppia} \ (\operatorname {pred} \ (\operatorname {primo} \ x))\ (\operatorname {pred} \ (\operatorname {secondo} \ x)))) }$

${\displaystyle \nomeoperatore {OneZero} =Y\nomeoperatore {OneZ}}$

Più e meno

L'addizione è definita matematicamente sulla coppia da,

${\displaystyle x+y=[x_{p},x_{n}]+[y_{p},y_{n}]=x_{p}-x_{n}+y_{p}-y_{n} =(x_{p}+y_{p})-(x_{n}+y_{n})=[x_{p}+y_{p},x_{n}+y_{n}]}$

L'ultima espressione è tradotta in lambda calcolo come,

${\displaystyle \operatorname {plus} _{s}=\lambda x.\lambda y.\operatorname {OneZero} \ (\operatorname {coppia} \ (\operatorname {plus} \ (\operatorname {first} \ x) \ (\operatorname {primo} \ y))\ (\operatorname {più} \ (\operatorname {secondo} \ x)\ (\operatorname {secondo} \ y)))}$

Allo stesso modo la sottrazione è definita,

${\displaystyle xy=[x_{p},x_{n}]-[y_{p},y_{n}]=x_{p}-x_{n}-y_{p}+y_{n}=( x_{p}+y_{n})-(x_{n}+y_{p})=[x_{p}+y_{n},x_{n}+y_{p}]}$

dando,

${\displaystyle \operatorname {meno} _{s}=\lambda x.\lambda y.\operatorname {OneZero} \ (\operatorname {coppia} \ (\operatorname {più} \ (\operatorname {primo} \ x) \ (\operatorname {secondo} \ y))\ (\operatorname {più} \ (\operatorname {secondo} \ x)\ (\operatorname {primo} \ y)))}$

Moltiplicare e dividere

La moltiplicazione può essere definita da,

${\displaystyle x*y=[x_{p},x_{n}]*[y_{p},y_{n}]=(x_{p}-x_{n})*(y_{p}-y_ {n})=(x_{p}*y_{p}+x_{n}*y_{n})-(x_{p}*y_{n}+x_{n}*y_{p})=[ x_{p}*y_{p}+x_{n}*y_{n},x_{p}*y_{n}+x_{n}*y_{p}]}$

L'ultima espressione è tradotta in lambda calcolo come,

${\displaystyle \operatorname {mult} _{s}=\lambda x.\lambda y.\operatorname {coppia} \ (\operatorname {plus} \ (\operatorname {mult} \ (\operatorname {first} \ x) \ (\operatorname {primo} \ y))\ (\operatorname {mult} \ (\operatorname {secondo} \ x)\ (\operatorname {secondo} \ y)))\ (\operatorname {plus} \ (\ nomeoperatore {mult} \ (\nomeoperatore {primo} \ x)\ (\nomeoperatore {secondo} \ y))\ (\nomeoperatore {mult} \ (\nomeoperatore {secondo} \ x)\ (\nomeoperatore {primo} \ e)))}$

Una definizione simile è data qui per la divisione, tranne che in questa definizione, un valore in ogni coppia deve essere zero (vedi OneZero sopra). La funzione divZ ci permette di ignorare il valore che ha una componente zero.

${\displaystyle \operatorname {divZ} =\lambda x.\lambda y.\operatorname {IsZero} \ y\ 0\ (\operatorname {divide} \ x\ y)}$

divZ viene quindi utilizzato nella formula seguente, che è la stessa della moltiplicazione, ma con mult sostituito da divZ .

${\displaystyle \operatorname {divide} _{s}=\lambda x.\lambda y.\operatorname {coppia} \ (\operatorname {plus} \ (\operatorname {divZ} \ (\operatorname {first} \ x) \ (\operatorname {primo} \ y))\ (\operatorname {divZ} \ (\operatorname {secondo} \ x)\ (\operatorname {secondo} \ y)))\ (\operatorname {plus} \ (\ nomeoperatore {divZ} \ (\nomeoperatore {primo} \ x)\ (\nomeoperatore {secondo} \ y))\ (\nomeoperatore {divZ} \ (\nomeoperatore {secondo} \ x)\ (\nomeoperatore {primo} \ e)))}$

Numeri razionali e reali

I numeri reali razionali e calcolabili possono anche essere codificati nel lambda calcolo. I numeri razionali possono essere codificati come una coppia di numeri con segno. I numeri reali calcolabili possono essere codificati mediante un processo di limitazione che garantisce che la differenza dal valore reale differisca di un numero che può essere ridotto quanto necessario. I riferimenti forniti descrivono software che potrebbe, in teoria, essere tradotto in lambda calcolo. Una volta definiti i numeri reali, i numeri complessi vengono codificati naturalmente come una coppia di numeri reali.

I tipi di dati e le funzioni sopra descritti dimostrano che qualsiasi tipo di dati o calcolo può essere codificato nel lambda calcolo. Questa è la tesi di Church-Turing .

Traduzione con altre rappresentazioni

La maggior parte delle lingue del mondo reale supporta gli interi nativi della macchina; le funzioni di chiesa e non di chiesa convertono tra numeri interi non negativi e i loro corrispondenti numeri di chiesa. Le funzioni sono date qui in Haskell , dove la \corrisponde al del Lambda calcolo. Le implementazioni in altre lingue sono simili.

type Church a = (a -> a) -> a -> a

church :: Integer -> Church Integer
church 0 = \f -> \x -> x
church n = \f -> \x -> f (church (n-1) f x)

unchurch :: Church Integer -> Integer
unchurch cn = cn (+ 1) 0

Booleani della chiesa

I booleani della chiesa sono la codifica della chiesa dei valori booleani vero e falso. Alcuni linguaggi di programmazione li usano come modello di implementazione per l'aritmetica booleana; esempi sono Smalltalk e Pico .

La logica booleana può essere considerata come una scelta. La codifica della Chiesa del vero e del falso sono funzioni di due parametri:

• true sceglie il primo parametro.
• false sceglie il secondo parametro.

Le due definizioni sono conosciute come Church Booleans:

${\displaystyle {\begin{allineato}\operatorname {vero} &\equiv \lambda a.\lambda ba\\\operatorname {falso} &\equiv \lambda a.\lambda bb\end{allineato}}}$

Questa definizione consente ai predicati (cioè alle funzioni che restituiscono valori logici ) di agire direttamente come clausole if. Una funzione che restituisce un valore booleano, che viene quindi applicato a due parametri, restituisce il primo o il secondo parametro:

${\displaystyle \operatorname {predicato} x\ \operatorname {quindi-clausola} \ \operatorname {altrimenti-clausola} }$

restituisce then-clause se predicato-x restituisce true , e else-clause se predicato-x restituisce false .

Poiché true e false scelgono il primo o il secondo parametro, possono essere combinati per fornire operatori logici. Nota che ci sono più implementazioni possibili di not .

${\displaystyle {\begin{allineato}\operatorname {e} &=\lambda p.\lambda qp\ q\ p\\\operatorname {o} &=\lambda p.\lambda qp\ p\ q\\\ nomeoperatore {non} _{1}&=\lambda p.\lambda a.\lambda bp\ b\ a\\\nomeoperatore {non} _{2}&=\lambda pp\ (\lambda a.\lambda bb )\ (\lambda a.\lambda ba)=\lambda pp\operatorname {false} \operatorname {true} \\\operatorname {xor} &=\lambda a.\lambda ba\ (\operatorname {non} \ b )\ b\\\nomeoperatore {if} &=\lambda p.\lambda a.\lambda bp\ a\ b\end{allineato}}}$

Qualche esempio:

${\displaystyle {\begin{allineato}\operatorname {e} \operatorname {vero} \operatorname {falso} &=(\lambda p.\lambda qp\ q\ p)\ \operatorname {vero} \ \operatorname {falso } =\nomeoperatore {vero} \nomeoperatore {falso} \nomeoperatore {vero} =(\lambda a.\lambda ba)\nomeoperatore {falso} \nomeoperatore {vero} =\nomeoperatore {falso} \\\nomeoperatore {o} \operatorname {true} \operatorname {false} &=(\lambda p.\lambda qp\ p\ q)\ (\lambda a.\lambda ba)\ (\lambda a.\lambda bb)=(\lambda a .\lambda ba)\ (\lambda a.\lambda ba)\ (\lambda a.\lambda bb)=(\lambda a.\lambda ba)=\operatorname {vero} \\\operatorname {non} _{ 1}\ \operatorname {true} &=(\lambda p.\lambda a.\lambda bp\ b\ a)(\lambda a.\lambda ba)=\lambda a.\lambda b.(\lambda a. \lambda ba)\ b\ a=\lambda a.\lambda b.(\lambda cb)\ a=\lambda a.\lambda bb=\nomeoperatore {falso} \\\nomeoperatore {non} _{2}\ \operatorname {true} &=(\lambda pp\ (\lambda a.\lambda bb)(\lambda a.\lambda ba))(\lambda a.\lambda ba)=(\lambda a.\lambda ba) (\lambda a.\lambda bb)( \lambda a.\lambda ba)=(\lambda b.(\lambda a.\lambda bb))\ (\lambda a.\lambda ba)=\lambda a.\lambda bb=\operatorname {false} \end {allineato}}}$

predicati

Un predicato è una funzione che restituisce un valore booleano. Il predicato più fondamentale è , che restituisce se il suo argomento è il numero di Chiesa e se il suo argomento è qualsiasi altro numero di Chiesa: ${\displaystyle \nomeoperatore {IsZero} }$${\displaystyle \nomeoperatore {vero}}$${\displaystyle 0}$${\displaystyle \nomeoperatore {false} }$

${\displaystyle \operatorname {IsZero} =\lambda nn\ (\lambda x.\operatorname {false} )\ \operatorname {vero} }$

Il predicato seguente verifica se il primo argomento è minore o uguale al secondo:

${\displaystyle \operatorname {LEQ} =\lambda m.\lambda n.\operatorname {IsZero} \ (\operatorname {meno} \ m\ n)}$,

A causa dell'identità,

${\displaystyle x=y\equiv (x\leq y\land y\leq x)}$

Il test per l'uguaglianza può essere implementato come,

${\displaystyle \operatorname {EQ} =\lambda m.\lambda n.\operatorname {e} \ (\operatorname {LEQ} \ m\ n)\ (\operatorname {LEQ} \ n\ m)}$

coppie di chiese

Le coppie di chiese sono la codifica di chiesa del tipo coppia (due tuple). La coppia è rappresentata come una funzione che accetta un argomento di funzione. Quando viene fornito il suo argomento, applicherà l'argomento ai due componenti della coppia. La definizione in lambda calcolo è,

${\displaystyle {\begin{allineato}\operatorname {coppia} &\equiv\lambda x.\lambda y.\lambda zz\ x\ y\\\operatorname {first} &\equiv \lambda pp\ (\lambda x .\lambda yx)\\\operatorname {secondo} &\equiv \lambda pp\ (\lambda x.\lambda yy)\end{allineato}}}$

Per esempio,

${\displaystyle {\begin{allineato}&\operatorname {primo} \ (\operatorname {coppia} \ a\ b)\\=&(\lambda pp\ (\lambda x.\lambda yx))\ ((\ lambda x.\lambda y.\lambda zz\ x\ y)\ a\ b)\\=&(\lambda pp\ (\lambda x.\lambda yx))\ (\lambda zz\ a\ b)\ \=&(\lambda zz\ a\ b)\ (\lambda x.\lambda yx)\\=&(\lambda x.\lambda yx)\ a\ b=a\end{allineato}}}$

Elenco codifiche

Una lista ( immutabile ) è costruita dai nodi della lista. Le operazioni di base sulla lista sono;

Di seguito diamo quattro diverse rappresentazioni degli elenchi:

• Costruisci ogni nodo di lista da due coppie (per consentire liste vuote).
• Costruisci ogni nodo della lista da una coppia.
• Rappresenta l'elenco utilizzando la funzione di piegatura a destra .
• Rappresenta l'elenco usando la codifica di Scott che accetta casi di espressioni di corrispondenza come argomenti

Due coppie come nodo di lista

Una lista non vuota può essere implementata da una coppia di chiese;

• Il primo contiene la testa.
• Il secondo contiene la coda.

Tuttavia questo non fornisce una rappresentazione della lista vuota, perché non c'è un puntatore "null". Per rappresentare null, la coppia può essere avvolta in un'altra coppia, dando valori liberi,

• Primo : è il puntatore nullo (elenco vuoto).
• Second.First contiene la testa.
• Second.Second contiene la coda.

Usando questa idea, le operazioni di base dell'elenco possono essere definite in questo modo:

Espressione	Descrizione
${\displaystyle \operatorname {nil} \equiv \operatorname {coppia} \ \operatorname {vero} \ \operatorname {vero} }$	Il primo elemento della coppia è vero, il che significa che l'elenco è nullo.
${\displaystyle \operatorname {isnil} \equiv \operatorname {first} }$	Recupera l'indicatore nullo (o elenco vuoto).
${\displaystyle \operatorname {contro} \equiv \lambda h.\lambda t.\operatorname {coppia} \operatorname {falso} \ (\operatorname {coppia} h\ t)}$	Crea un nodo di lista, che non è null, e assegnagli una testa h e una coda t .
${\displaystyle \operatorname {testa} \equiv \lambda z.\operatorname {primo} \ (\operatorname {secondo} z)}$	second.first è la testa.
${\displaystyle \operatorname {coda} \equiv \lambda z.\operatorname {secondo} \ (\operatorname {secondo} z)}$	second.second è la coda.

In un nodo nullo il secondo non è mai accessibile, a condizione che head e tail vengano applicati solo a liste non vuote.

Una coppia come nodo di lista

In alternativa, definire

${\displaystyle {\begin{allineato}\operatorname {contro} &\equiv \operatorname {coppia} \\\operatorname {testa} &\equiv \operatorname {primo} \\\operatorname {coda} &\equiv \operatorname { secondo} \\\operatorname {nil} &\equiv \operatorname {false} \\\operatorname {isnil} &\equiv \lambda ll(\lambda h.\lambda t.\lambda d.\operatorname {false} )\ nomeoperatore {vero} \end{allineato}}}$

dove l'ultima definizione è un caso speciale del generale

${\displaystyle \operatorname {processo-elenco} \equiv \lambda ll(\lambda h.\lambda t.\lambda d.\operatorname {clausola di testa e coda})\operatorname {clausola nulla}}$

Rappresenta la lista usando la piega a destra

In alternativa alla codifica tramite coppie di Chiesa, è possibile codificare un elenco identificandolo con la sua funzione di piegatura a destra . Ad esempio, un elenco di tre elementi x, yez può essere codificato da una funzione di ordine superiore che, applicata a un combinatore ce un valore n, restituisce cx (cy (czn)).

${\displaystyle {\begin{allineato}\operatorname {nil} &\equiv\lambda c.\lambda nn\\\operatorname {isnil} &\equiv \lambda ll\ (\lambda h.\lambda t.\operatorname { false} )\ \operatorname {true} \\\operatorname {cons} &\equiv \lambda h.\lambda t.\lambda c.\lambda nc\ h\ (t\ c\ n)\\\operatorname {head } &\equiv \lambda ll\ (\lambda h.\lambda th)\ \operatorname {false} \\\operatorname {coda} &\equiv \lambda l.\lambda c.\lambda nl\ (\lambda h. \lambda t.\lambda gg\ h\ (t\ c))\ (\lambda tn)\ (\lambda h.\lambda tt)\end{allineato}}}$

Questa rappresentazione dell'elenco può essere data di tipo in System F .

Rappresenta l'elenco usando la codifica Scott

Una rappresentazione alternativa è la codifica Scott, che utilizza l'idea delle continuazioni e può portare a un codice più semplice. (vedi anche codifica Mogensen-Scott ).

In questo approccio, utilizziamo il fatto che gli elenchi possono essere osservati utilizzando l'espressione di corrispondenza del modello. Ad esempio, utilizzando la notazione Scala , se listdenota un valore di tipo Listcon elenco vuoto Nile costruttore Cons(h, t), possiamo ispezionare l'elenco e calcolare nilCodenel caso in cui l'elenco sia vuoto e consCode(h, t)quando l'elenco non è vuoto:

list match {
  case Nil        => nilCode
  case Cons(h, t) => consCode(h,t)
}

La 'lista' è data da come agisce su 'nilCode' e 'consCode'. Definiamo quindi una lista come una funzione che accetta tali 'nilCode' e 'consCode' come argomenti, così che invece del pattern match sopra possiamo semplicemente scrivere:

${\displaystyle \operatorname {list} \ \operatorname {nilCode} \ (\operatorname {consCode} \ h\ t)}$

Indichiamo con 'n' il parametro corrispondente a 'nilCode' e con 'c' il parametro corrispondente a 'consCode'. La lista vuota è quella che restituisce l'argomento nil:

${\displaystyle \operatorname {nil} \equiv \lambda n.\lambda c.\ n}$

La lista non vuota con testa 'h' e coda 't' è data da

${\displaystyle\operatorname {cons} \ h\ t\ \ \equiv \ \ \lambda n.\lambda c.\ c\ h\ t}$

Più in generale, un tipo di dato algebrico con alternative diventa una funzione con parametri. Quando il costruttore ha argomenti, anche il parametro corrispondente della codifica accetta argomenti. ${\displaystyle m}$${\displaystyle m}$${\displaystyle i}$${\displaystyle n_{i}}$${\displaystyle n_{i}}$

La codifica Scott può essere eseguita nel calcolo lambda non tipizzato, mentre il suo utilizzo con i tipi richiede un sistema di tipi con ricorsione e polimorfismo di tipo. Un elenco con tipo di elemento E in questa rappresentazione che viene utilizzato per calcolare valori di tipo C avrebbe la seguente definizione di tipo ricorsivo, dove '=>' indica il tipo di funzione:

type List = 
  C =>                    // nil argument
  (E => List => C) =>     // cons argument
  C                       // result of pattern matching

Un elenco che può essere usato per calcolare tipi arbitrari avrebbe un tipo che quantifica su C. Un elenco generico in Eprenderebbe anche Ecome argomento di tipo.

Guarda anche

• Lambda calcolo
• Sistema F per i numeri di chiesa in un calcolo tipizzato
• Codifica Mogensen-Scott
• Definizione di Von Neumann di ordinali - un altro modo per codificare i numeri naturali: come insiemi

Appunti

Riferimenti

• Meta-programmazione direttamente riflessiva
• Numeri di chiesa e booleani spiegati da Robert Cartwright alla Rice University
• Fondamenti teorici per una "programmazione totalmente funzionale" pratica (capitoli 2 e 5) Tutto su Church e altre codifiche simili, incluso come derivarle e operazioni su di esse, dai primi principi
• Alcuni esempi interattivi di numeri della Chiesa
• Esercitazione live sul calcolo lambda: algebra booleana