Kódování kostela - Church encoding - Wikipedia

v matematika, Kódování kostela je prostředek reprezentující data a operátory v lambda kalkul. The Církevní číslice jsou reprezentací přirozených čísel pomocí lambda notace. Metoda je pojmenována pro Alonzo Church, který tímto způsobem nejprve zakódoval data do lambda kalkulu.

Termíny, které jsou obvykle považovány za primitivní v jiných notacích (například celá čísla, booleovské hodnoty, páry, seznamy a označené odbory), jsou mapovány na funkce vyššího řádu pod kódováním kostela. The Church-Turingova teze tvrdí, že jakýkoli vypočítatelný operátor (a jeho operandy) může být reprezentován pod kódováním Church. V netypový lambda kalkul jediným primitivním datovým typem je funkce.

Církevní kódování není zamýšleno jako praktická implementace primitivních datových typů. Jeho použití je ukázat, že jiné primitivní datové typy nepředstavují žádný výpočet. Úplnost je reprezentativní. K překladu reprezentace do běžných datových typů jsou zapotřebí další funkce pro zobrazení lidem. Obecně není možné rozhodnout, zda jsou dvě funkce prodlouženě stejné kvůli nerozhodnutelnost rovnocennosti z Církevní věta. Překlad může funkci nějakým způsobem použít k načtení hodnoty, kterou představuje, nebo k vyhledání její hodnoty jako doslovného výrazu lambda.

Lambda kalkul se obvykle interpretuje jako použití intenzionální rovnost. Existují Potenciální problémy s interpretací výsledků z důvodu rozdílu mezi intencionální a extenzivní definicí rovnosti.

Církevní číslice

Církevní číslice jsou reprezentacemi přirozená čísla pod kódováním kostela. The funkce vyššího řádu což představuje přirozené číslo n je funkce, která mapuje jakoukoli funkci ${ displaystyle f}$ k jeho n-složit složení.^[1] Jednoduše řečeno, „hodnota“ číslice je ekvivalentní počtu, kolikrát funkce zapouzdří svůj argument.

{ displaystyle f ^ { Circ n} = Underbrace {F Circ Circ Cdots Circ}} {{{text} {krát}}}. ,}

Všechny církevní číslice jsou funkce, které mají dva parametry. Církevní číslice 0, 1, 2, ..., jsou v dokumentu definovány následovně lambda kalkul.

Začínání s 0 funkci vůbec nepoužíváte, pokračujte 1 použití funkce jednou, 2použití funkce dvakrát, 3 použití funkce třikrát atd.:

{ displaystyle { begin {array} {r | l | l} { text {Number}} & { text {definice funkce}} & { text {výraz 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 {pole}}}

Církevní číslo 3 představuje akci aplikace jakékoli dané funkce třikrát na hodnotu. Zadaná funkce se nejprve použije na zadaný parametr a poté postupně na vlastní výsledek.^[1] Konečným výsledkem není číslice 3 (pokud není zadaný parametr 0 a funkce je a nástupnická funkce ). Samotná funkce, a nikoli její konečný výsledek, je církevní číslice 3. Církevní číslo 3 znamená jednoduše udělat cokoli třikrát. Je to ostensive ukázka toho, co se rozumí „třikrát“.

Výpočet s církevními číslicemi

Aritmetický operace s čísly mohou být reprezentovány funkcemi na církevních číslech. Tyto funkce mohou být definovány v lambda kalkul nebo implementovány ve většině funkčních programovacích jazyků (viz převod lambda výrazů na funkce ).

Funkce přidání ${ displaystyle operatorname {plus} (m, n) = m + n}$ používá identitu ${ displaystyle f ^ { circ (m + n)} (x) = f ^ { circ m} (f ^ { circ n} (x))}$ .

{ displaystyle operatorname {plus} equiv lambda m. lambda n. lambda f. lambda x.m f (n f x)}

Funkce nástupce ${ displaystyle operatorname {succ} (n) = n + 1}$ je β-ekvivalent na ${ displaystyle ( operatorname {plus} 1)}$ .

{ displaystyle operatorname {succ} equiv lambda n. lambda f. lambda x.f (n f x)}

Funkce násobení ${ displaystyle operatorname {mult} (m, n) = m * n}$ používá identitu ${ displaystyle f ^ { circ (m * n)} (x) = (f ^ { circ n}) ^ { circ m} (x)}$ .

{ displaystyle operatorname {mult} equiv lambda m. lambda n. lambda f. lambda x.m (n f) x}

Funkce umocňování ${ displaystyle operatorname {exp} (m, n) = m ^ {n}}$ je dáno definicí církevních číslic, ${ displaystyle n h x = h ^ {n} x}$ . V definici náhrada ${ displaystyle h až m, x až f}$ dostat ${ displaystyle n m f = m ^ {n} f}$ a,

{ displaystyle operatorname {exp} m n = m ^ {n} = n m}

což dává výraz lambda,

{ displaystyle operatorname {exp} equiv lambda m. lambda n.n m}

The ${ displaystyle operatorname {pred} (n)}$ funkce je obtížnější pochopit.

{ Displaystyle operatorname {pred} equiv lambda n. lambda f. lambda x.n ( lambda g. lambda h.h (g f)) ( lambda u.x) ( lambda u.u)}

Církevní číslice používá funkci n krát. Funkce předchůdce musí vrátit funkci, která použije svůj parametr n - 1 krát. Toho je dosaženo vybudováním kontejneru F a X, který je inicializován způsobem, který poprvé vynechá použití funkce. Vidět předchůdce pro podrobnější vysvětlení.

Funkci odčítání lze zapsat na základě funkce předchůdce.

{ displaystyle operatorname {minus} equiv lambda m. lambda n. (n operatorname {pred}) m}

Tabulka funkcí na církevních číslech

Funkce	Algebra	Identita	Definice funkce	Lambda výrazy
Nástupce	${ 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 x.f (n f x)}$	...
Přidání	${ 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 x.m f (n f x)}$	${ displaystyle lambda m. lambda n.n operatorname {úspěch} m}$
Násobení	${ displaystyle m * n}$	${ displaystyle f ^ {m * n} x = (f ^ {m}) ^ {n} x}$	${ displaystyle operatorname {znásobit} m n f x = m (n f) x}$	${ Displaystyle lambda m. lambda n. lambda f. lambda x.m (n f) x}$	${ Displaystyle lambda m. lambda n. lambda f.m (n f)}$
Umocňování	${ displaystyle m ^ {n}}$	${ displaystyle n m f = m ^ {n} f}$ ^[2]	${ displaystyle operatorname {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 n.n m}$
Předchůdce *	${ 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 x.n ( lambda g. lambda h.h (g f)) ( lambda u.x) ( lambda u.u)}$
Odčítání *	${ displaystyle m-n}$	${ displaystyle f ^ {m-n} x = (f ^ {- 1}) ^ {n} (f ^ {m} x)}$	${ displaystyle operatorname {minus} m n = (n operatorname {před}) m}$	...	${ displaystyle lambda m. lambda n.n operatorname {před} m}$

* Všimněte si, že v kódování Církve

${ displaystyle operatorname {pred} (0) = 0}$
${ displaystyle m$

Odvození funkce předchůdce

Funkce předchůdce použitá v kódování kostela je,

{ displaystyle operatorname {pred} (n) = { začátek {případů} 0 & { mbox {if}} n = 0, n-1 & { mbox {jinak}} konec {případů}}}

.

K vytvoření předchůdce potřebujeme způsob, jak tuto funkci aplikovat o 1 čas méně. Číslice $n$ použije funkci $F$ $n$ krát do $X$ . Funkce předchůdce musí používat číslici $n$ použít funkci $n -1$ krát.

Před implementací funkce předchůdce je zde schéma, které zabalí hodnotu do funkce kontejneru. Definujeme nové funkce, které se použijí místo $F$ a $X$ , volala $vč$ a $inic$ . Funkce kontejneru se nazývá $hodnota$ . Na levé straně tabulky je číslice $n$ aplikován na $vč$ a $inic$ .

{ displaystyle { begin {array} {r | r | r} { text {Number}} & { text {using init}} & { text {using const}} hline 0 & operatorname {init } = operatorname {hodnota} x & 1 & operatorname {inc} operatorname {init} = operatorname {hodnota} (f x) & operatorname {inc} operatorname {const} = operatorname {hodnota} x 2 & operatorname {inc} ( operatorname {inc} operatorname {init}) = operatorname {hodnota} (f (f x)) & operatorname {inc} ( operatorname {inc} operatorname {const}) = operatorname {hodnota} (f x) 3 & operatorname {inc} ( operatorname {inc} ( operatorname {inc} operatorname {init})) = operatorname {hodnota} (f (f (f x))) & operatorname {inc} ( operatorname {inc} ( operatorname {inc} operatorname {const })) = operatorname {hodnota} (f (f x)) vdots & vdots & vdots n & n operatorname {inc} operatorname {init} = operatorname {hodnota} (f ^ {n} x) = operatorname {hodnota} (n f x) & n operatorname {inc} operatorname {const} = operatorname {hodnota} (f ^ {n-1} x) = o peratorname {hodnota} ((n-1) f x) konec {pole}}}

Obecným pravidlem opakování je,

{ displaystyle operatorname {inc} ( operatorname {hodnota} v) = operatorname {hodnota} (f v)}

Pokud existuje také funkce pro načtení hodnoty z kontejneru (tzv $výpis$ ),

{ displaystyle operatorname {extrakt} ( operatorname {hodnota} v) = v}

Pak $výpis$ lze použít k definování $samenum$ fungovat jako,

{ displaystyle operatorname {samenum} = lambda n. lambda f. lambda x. operatorname {extrakt} (n operatorname {inc} operatorname {init}) = lambda n. lambda f. lambda x. operatorname {extrakt} ( operatorname {hodnota} (n f x)) = lambda n. lambda f. lambda xn f x = lambda nn}

The $samenum$ funkce není skutečně užitečná. Nicméně, jak $vč$ volání delegátů z $F$ k argumentu jeho kontejneru to můžeme zařídit u první aplikace $vč$ obdrží speciální kontejner, který ignoruje svůj argument umožňující přeskočit první aplikaci $F$ . Zavolejte tento nový počáteční kontejner $konst$ . Pravá strana výše uvedené tabulky ukazuje rozšíření o $n$ $vč$ $konst$ . Poté nahrazením $inic$ s $konst$ ve výrazu pro $stejný$ funkce získáme funkci předchůdce,

{ displaystyle operatorname {pred} = lambda n. lambda f. lambda x. operatorname {extrakt} (n operatorname {inc} operatorname {const}) = lambda n. lambda f. lambda x. operatorname {extrakt} ( operatorname {hodnota} ((n-1) f x)) = lambda n. lambda f. lambda x. (n-1) f x = lambda n. (n-1)}

Jak je vysvětleno níže, funkce $vč$ , $inic$ , $konst$ , $hodnota$ a $výpis$ lze definovat jako,

{ displaystyle { begin {aligned} operatorname {hodnota} & = lambda v. ( lambda hh v) operatorname {extrakt} k & = k lambda uu operatorname {inc} & = lambda g. lambda hh (g f) operatorname {init} & = lambda hh x operatorname {const} & = lambda ux end {zarovnáno}}}

Což dává výraz lambda pro $před$ tak jako,

{ displaystyle operatorname {pred} = lambda n. lambda f. lambda x.n ( lambda g. lambda h.h (g f)) ( lambda u.x) ( lambda u.u)}

Hodnota kontejneru Kontejner hodnot použije funkci na svou hodnotu. Je definován, ${ displaystyle operatorname {hodnota} v h = h v}$ tak, ${ displaystyle operatorname {hodnota} = lambda v. ( lambda h.h v)}$ Vč The $vč$ funkce by měla mít hodnotu obsahující $proti$ , a vrátit novou hodnotu obsahující $F v$ . ${ displaystyle operatorname {inc} ( operatorname {hodnota} v) = operatorname {hodnota} (f v)}$ Nechť g je kontejner hodnot, ${ displaystyle g = operatorname {hodnota} v}$ pak, ${ displaystyle g f = operatorname {hodnota} v f = f v}$ tak, ${ displaystyle operatorname {inc} g = operatorname {hodnota} (g f)}$ ${ displaystyle operatorname {inc} = lambda g. lambda h.h (g f)}$	Výpis Hodnotu lze extrahovat použitím funkce identity, ${ displaystyle I = lambda u.u}$ Použitím $Já$ , ${ displaystyle operatorname {hodnota} v I = v}$ tak, ${ displaystyle operatorname {extrakt} k = k I}$ Const Provádět $před$ the $inic$ funkce je nahrazena $konst$ to neplatí $F$ . Potřebujeme $konst$ uspokojit, ${ displaystyle operatorname {inc} operatorname {const} = operatorname {hodnota} x}$ ${ displaystyle lambda h.h ( operatorname {const} f) = lambda h.h x}$ Což je splněno, pokud ${ displaystyle operatorname {const} f = x}$ Nebo jako lambda výraz, ${ displaystyle operatorname {const} = lambda u.x}$

Další způsob definování před

Pred lze také definovat pomocí párů:

{ displaystyle { begin {seřazeno} operatorname {f} = & lambda p. operatorname {pair} ( operatorname {druhý} p) ( operatorname {succ} ( operatorname {druhý } p)) operatorname {nula} = & ( lambda f. lambda x. x) operatorname {pc0} = & operatorname {dvojice} operatorname {nula} operatorname {nula} operatorname {pred} = & lambda n. operatorname {první} (n operatorname {f} operatorname {pc0}) konec {zarovnáno}}}

Toto je jednodušší definice, ale vede ke složitějšímu výrazu pro pred. Rozšíření pro ${ displaystyle operatorname {před} operatorname {tři}}$ :

{ displaystyle { begin {seřazeno} operatorname {pred} operatorname {three} = & operatorname {first} ( operatorname {f} ( operatorname {f} ( operatorname {f} ( operatorname {pair} operatorname {zero} operatorname {zero})))) = & operatorname {first} ( operatorname {f} ( operatorname {f} ( operatorname { pair} operatorname {nula} operatorname {one}))) = & operatorname {first} ( operatorname {f} ( operatorname {pair} operatorname {one} operatorname {two})) = & operatorname {first} ( operatorname {pair} operatorname {two} operatorname {three}) = & operatorname {two} end {aligned} }}

Divize

Divize přirozených čísel lze implementovat,^[3]

{ displaystyle n / m = operatorname {if} n geq m operatorname {then} 1+ (n-m) / m operatorname {else} 0}

Výpočet ${ displaystyle n-m}$ vyžaduje mnoho beta redukcí. Pokud redukci neprovedete ručně, na tom až tak nezáleží, ale je lepší tento výpočet nemusíte provádět dvakrát. Nejjednodušší predikát pro testování čísel je IsZero zvažte tedy podmínku.

{ displaystyle operatorname {IsZero} ( operatorname {minus} n m)}

Ale tato podmínka je ekvivalentní k ${ displaystyle n leq m}$ , ne ${ displaystyle n$ . Pokud se použije tento výraz, pak se výše uvedená matematická definice rozdělení převede do funkce na církevních číslech jako,

{ displaystyle operatorname {divide1} n m f x = ( lambda d. operatorname {IsZero} d (0 f x) (f ( operatorname {divide1} d m f x))) ( operatorname {minus} n m)}

Podle potřeby má tato definice jediné volání ${ displaystyle operatorname {minus} n m}$ . Výsledkem však je, že tento vzorec dává hodnotu ${ displaystyle (n-1) / m}$ .

Tento problém lze opravit přidáním 1 do n před zavoláním rozdělit. Definice rozdělit je pak,

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

divide1 je rekurzivní definice. The Y kombinátor lze použít k implementaci rekurze. Vytvořte novou funkci s názvem div podle;

V levé ruce ${ displaystyle operatorname {divide1} rightarrow operatorname {div} c}$
Na pravé straně ${ displaystyle operatorname {divide1} rightarrow c}$

dostat,

{ 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 {minus} n m)}

Pak,

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

kde,

{ displaystyle { začátek {zarovnáno} 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 {zarovnáno}}}

{ displaystyle { begin {zarovnáno} operatorname {true} & equiv lambda a. lambda b.a operatorname {false} & equiv lambda a. lambda b.b end {zarovnáno}}}

{ displaystyle { begin {zarovnáno} operatorname {minus} & = 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 {zarovnáno}}}

Dává,

{ 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)}

Nebo jako text pomocí pro $λ$ ,

rozdělit = ( n. (( f. ( xx x) ( xf (xx))) ( c.  n.  m.  f.  x. ( d. ( nn ( x) . ( a.  bb)) ( a.  ba)) d (( f.  xx) fx) (f (cdmfx))) (( m.  nn ( n.  f.  xn ( g.  hh (gf)) ( ux) ( uu)) m) nm))) (( n.  f.  x. f (nfx)) n))

Například 9/3 je reprezentováno

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

Pomocí kalkulačky lambda kalkulátoru se výše uvedený výraz sníží na 3 pomocí normálního pořadí.

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

Podepsaná čísla

Jeden jednoduchý přístup k rozšíření církevních čísel na podepsaná čísla je použít církevní dvojici obsahující církevní číslice představující kladnou a zápornou hodnotu.^[4] Celočíselná hodnota je rozdíl mezi dvěma církevními číslicemi.

Přirozené číslo se převede na podepsané číslo,

{ displaystyle operatorname {konvertovat} _ {s} = lambda x. operatorname {pair} x 0}

Negace se provádí záměnou hodnot.

{ displaystyle operatorname {neg} _ {s} = lambda x. operatorname {pár} ( operatorname {druhý} x) ( operatorname {první} x)}

Hodnota celého čísla je přirozenější, pokud je jeden z dvojice nula. The OneZero funkce splňuje tuto podmínku,

{ displaystyle operatorname {OneZero} = lambda x. operatorname {IsZero} ( operatorname {první} x) x ( operatorname {IsZero} ( operatorname {druhý} x) x ( operatorname {OneZero} operatorname {pair} ( operatorname {pred} ( operatorname {první} x)) ( operatorname {pred} ( operatorname {druhý} x)))) }

Rekurzi lze realizovat pomocí kombinátoru Y,

{ displaystyle operatorname {OneZ} = lambda c. lambda x. operatorname {IsZero} ( operatorname {první} x) x ( operatorname {IsZero} ( operatorname {druhý} x ) x (c operatorname {dvojice} ( operatorname {pred} ( operatorname {první} x)) ( operatorname {pred} ( operatorname {druhý} x)))) }

{ displaystyle operatorname {OneZero} = Y operatorname {OneZ}}

Plus a minus

Sčítání je definováno matematicky na páru,

{ 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}]}

Poslední výraz je přeložen do lambda kalkulu jako,

{ displaystyle operatorname {plus} _ {s} = lambda x. lambda y. operatorname {OneZero} ( operatorname {pair} ( operatorname {plus} ( operatorname {první} x) ( operatorname {první} y)) ( operatorname {plus} ( operatorname {druhý} x) ( operatorname {druhý} y)))}

Podobně je definováno odčítání,

{ 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}]}

dávat,

{ displaystyle operatorname {minus} _ {s} = lambda x. lambda y. operatorname {OneZero} ( operatorname {pair} ( operatorname {plus} ( operatorname {první} x) ( operatorname {druhý} y)) ( operatorname {plus} ( operatorname {druhý} x) ( operatorname {první} y)))}

Znásobte a rozdělte

Násobení může být definováno,

{ 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}]}

Poslední výraz je přeložen do lambda kalkulu jako,

{ displaystyle operatorname {mult} _ {s} = lambda x. lambda y. operatorname {pair} ( operatorname {plus} ( operatorname {mult} ( operatorname {první} x) ( operatorname {první} y)) ( operatorname {mult} ( operatorname {druhý} x) ( operatorname {druhý} y))) ( operatorname {plus} ( operatorname {mult} ( operatorname {první} x) ( operatorname {druhý} y)) ( operatorname {mult} ( operatorname {druhý} x) ( operatorname {první} y)))}

Podobná definice je zde uvedena pro dělení, kromě této definice musí být jedna hodnota v každém páru nulová (viz OneZero výše). The divZ Funkce nám umožňuje ignorovat hodnotu, která má nulovou složku.

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

divZ se potom použije v následujícím vzorci, který je stejný jako pro násobení, ale s mult nahrazen divZ.

{ displaystyle operatorname {divide} _ {s} = lambda x. lambda y. operatorname {pair} ( operatorname {plus} ( operatorname {divZ} ( operatorname {první} x) ( operatorname {první} y)) ( operatorname {divZ} ( operatorname {druhý} x) ( operatorname {druhý} y))) ( operatorname {plus} ( operatorname {divZ} ( operatorname {první} x) ( operatorname {druhý} y)) ( operatorname {divZ} ( operatorname {druhý} x) ( operatorname {první} y)))}

Racionální a reálná čísla

Racionální a vypočítatelná reálná čísla mohou být také zakódována do lambda kalkulu. Racionální čísla mohou být kódována jako dvojice podepsaných čísel. Vypočitatelná reálná čísla mohou být kódována omezujícím procesem, který zaručuje, že rozdíl od skutečné hodnoty se liší o číslo, které může být tak malé, jak potřebujeme.^[5]^[6] Uvedené odkazy popisují software, který lze teoreticky převést na lambda kalkul. Jakmile jsou definována reálná čísla, komplexní čísla jsou přirozeně kódována jako dvojice reálných čísel.

Výše popsané datové typy a funkce ukazují, že jakýkoli datový typ nebo výpočet lze zakódovat do lambda kalkulu. To je Church-Turingova teze.

Překlad s jinými vyjádřeními

Většina jazyků v reálném světě podporuje strojově nativní celá čísla; the kostel a vyloučit z církve funkce převádějí mezi nezápornými celými čísly a jejich odpovídajícími církevními číslicemi. Funkce jsou uvedeny zde Haskell, Kde \ odpovídá λ lambda kalkulu. Implementace v jiných jazycích jsou podobné.

typ Kostel A = (A -> A) -> A -> Akostel :: Celé číslo -> Kostel Celé číslokostel 0 = \F -> \X -> Xkostel n = \F -> \X -> F (kostel (n-1) F X)vyloučit z církve :: Kostel Celé číslo -> Celé číslovyloučit z církve cn = cn (+ 1) 0

Církevní booleové

Církevní booleové jsou církevní kódování booleovských hodnot skutečný a Nepravdivé. Některé programovací jazyky je používají jako implementační model pro booleovskou aritmetiku; příklady jsou Pokec a Pico.

Logickou logiku lze považovat za volbu. Církevní kódování skutečný a Nepravdivé jsou funkce dvou parametrů:

skutečný vybere první parametr.
Nepravdivé zvolí druhý parametr.

Tyto dvě definice jsou známé jako Church Booleans:

{ displaystyle { begin {aligned} operatorname {true} & equiv lambda a. lambda b.a operatorname {false} & equiv lambda a. lambda b.b end {zarovnáno}}}

Tato definice umožňuje predikáty (tj. Funkce, které se vracejí logické hodnoty ) přímo působit jako klauzule if. Funkce vrací logickou hodnotu, která se poté použije na dva parametry, vrátí první nebo druhý parametr:

{ displaystyle operatorname {predikát} x operatorname {pak-klauzule} operatorname {else-klauzule}}

hodnotí na tehdejší klauzule -li predikát X hodnotí na skutečnýa do klauzule else -li predikát X hodnotí na Nepravdivé.

Protože skutečný a Nepravdivé vyberte první nebo druhý parametr, který lze kombinovat, aby poskytovaly logické operátory. Všimněte si, že existují dvě verze ne, záleží na strategie hodnocení který je vybrán.

{ displaystyle { begin {zarovnáno} operatorname {a} & = lambda p. lambda qp q p operatorname {nebo} & = lambda p. lambda qp p q operatorname {not} _ {1} & = lambda p. lambda a. lambda bp b a { scriptstyle { text {(Toto je správná implementace pouze v případě, že je strategie hodnocení v pořadí.)} }} operatorname {not} _ {2} & = lambda pp ( lambda a. lambda bb) ( lambda a. lambda ba) = lambda pp operatorname {false} operatorname { true} { scriptstyle { text {(Toto je správná implementace pouze v případě, že strategie hodnocení je normální pořadí.)}}} operatorname {xor} & = lambda a. lambda ba ( operatorname { not} b) b operatorname {if} & = lambda str. lambda a. lambda bp a b end {zarovnáno}}}

Nějaké příklady:

{ displaystyle { begin {zarovnáno} operatorname {a} operatorname {true} operatorname {false} & = ( lambda p. lambda qp q p) operatorname {true} operatorname {false } = operatorname {true} operatorname {false} operatorname {true} = ( lambda a. lambda ba) operatorname {false} operatorname {true} = operatorname {false} operatorname {nebo} 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 {true} operatorname {not} _ { 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 = operatorname {false} operatorname {not} _ {2} operatorname {true} & = ( lambda pp ( lambda a. lambda bb) ( lambda a. lambda ba)) ( lambda a. lambda ba) = ( lambda a. lambda ba) (Los Angeles mbda a. lambda bb) ( lambda a. lambda ba) = ( lambda b. ( lambda a. lambda bb)) ​​( lambda a. lambda ba) = lambda a. lambda bb = operatorname {false} end {zarovnáno}}}

Predikáty

A predikát je funkce, která vrací logickou hodnotu. Nejzákladnějším predikátem je ${ displaystyle operatorname {IsZero}}$ , který se vrací ${ displaystyle operatorname {true}}$ pokud je jeho argumentem církevní číslice ${ displaystyle 0}$ , a ${ displaystyle operatorname {false}}$ pokud je jeho argumentem jakákoli jiná církevní číslice:

{ displaystyle operatorname {IsZero} = lambda n.n ( lambda x. operatorname {false}) operatorname {true}}

Následující predikát testuje, zda je první argument menší než nebo stejný jako druhý:

{ displaystyle operatorname {LEQ} = lambda m. lambda n. operatorname {IsZero} ( operatorname {minus} m n)}

,

Kvůli identitě

{ Displaystyle x = y equiv (x leq y land y leq x)}

Test rovnosti může být proveden jako,

{ displaystyle operatorname {EQ} = lambda m. lambda n. operatorname {a} ( operatorname {LEQ} m n) ( operatorname {LEQ} n m)}

Církevní páry

Církevní páry jsou kódováním církve pár (dva-tice) typ. Dvojice je reprezentována jako funkce, která přebírá argument funkce. Po zadání argumentu použije argument na dvě složky páru. Definice v lambda kalkul je,

{ displaystyle { begin {aligned} operatorname {pair} & equiv lambda x. lambda y. lambda zz ​​x y operatorname {first} & equiv lambda pp ( lambda x . lambda yx) operatorname {druhý} & equiv lambda pp ( lambda x. lambda yy) end {zarovnáno}}}

Například,

{ displaystyle { begin {seřazeno} & operatorname {first} ( operatorname {pair} 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 {zarovnáno}}}

Seznam kódování

An (neměnný ) seznam je sestaven z uzlů seznamu. Základní operace na seznamu jsou;

Funkce	Popis
nula	Vytvořte prázdný seznam.
isnil	Vyzkoušejte, zda je seznam prázdný.
nevýhody	Připravte danou hodnotu na (případně prázdný) seznam.
hlava	Získejte první prvek seznamu.
ocas	Získejte zbytek seznamu.

Níže uvádíme čtyři různá znázornění seznamů:

Vytvořte každý uzel seznamu ze dvou párů (aby byly prázdné seznamy).
Vytvořte každý uzel seznamu z jednoho páru.
Seznam reprezentujte pomocí funkce pravého skládání.
Seznam reprezentujte pomocí Scottova kódování, které bere případy výrazu shody jako argumenty

Dva páry jako uzel seznamu

Neprázdný seznam může být implementován církevním párem;

První obsahuje hlavu.
Druhý obsahuje ocas.

To však neposkytuje reprezentaci prázdného seznamu, protože neexistuje žádný ukazatel „null“. Pro reprezentaci null může být pár zabalen do jiného páru, který dává volné hodnoty,

První - Je nulový ukazatel (prázdný seznam).
Za druhé obsahuje hlavu.
Za druhé obsahuje ocas.

Pomocí této myšlenky lze základní operace se seznamy definovat takto:^[7]

Výraz	Popis
${ displaystyle operatorname {nil} equiv operatorname {pár} operatorname {true} operatorname {true}}$	První prvek dvojice je skutečný což znamená, že seznam je null.
${ displaystyle operatorname {isnil} equiv operatorname {první}}$	Načíst indikátor nuly (nebo prázdného seznamu).
${ displaystyle operatorname {zápory} equiv lambda h. lambda t. operatorname {pár} operatorname {false} ( operatorname {pair} h t)}$	Vytvořte uzel seznamu, který není null, a dejte mu hlavu h a ocas t.
${ displaystyle operatorname {hlava} equiv lambda z. operatorname {první} ( operatorname {druhá} z)}$	druhý. první je hlava.
${ displaystyle operatorname {ocas} equiv lambda z. operatorname {druhý} ( operatorname {druhý} z)}$	sekunda. sekunda je ocas.

V nula uzel druhý není nikdy přístupná, za předpokladu, že hlava a ocas se vztahují pouze na neprázdné seznamy.

Jeden pár jako uzel seznamu

Případně definujte^[8]

{ displaystyle { begin {aligned} operatorname {cons} & equiv operatorname {pair} operatorname {head} & equiv operatorname {first} operatorname {tail} & equiv operatorname { second} operatorname {nil} & equiv operatorname {false} operatorname {isnil} & equiv lambda ll ( lambda h. lambda t. lambda d. operatorname {false}) operatorname {true} end {aligned}}}

kde poslední definice je zvláštní případ generála

{ displaystyle operatorname {seznam procesů} equiv lambda l.l ( lambda h. lambda t. lambda d. operatorname {klauzule hlavy a ocasu}) operatorname {nula klauze}}

Seznam reprezentujte pomocí pravý záhyb

Jako alternativu ke kódování pomocí církevních párů lze seznam kódovat jeho identifikací funkce pravého skládání. Například seznam tří prvků x, yaz lze zakódovat pomocí funkce vyššího řádu, která při použití na kombinátor ca hodnotu n vrátí c x (c y (c z n)).

{ displaystyle { begin {aligned} 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 {hlava } & equiv lambda ll ( lambda h. lambda th) operatorname {false} operatorname {tail} & equiv lambda l. lambda c. lambda nl ( lambda h. lambda t. lambda gg h (t c)) ( lambda tn) ( lambda h. lambda tt) end {zarovnáno}}}

Tuto reprezentaci seznamu lze zadat jako Systém F.

Seznam reprezentujte pomocí kódování Scott

Alternativní reprezentací je Scottovo kódování, které využívá myšlenku pokračování a může vést k jednoduššímu kódu.^[9] (viz také Mogensen – Scott kódování ).

V tomto přístupu používáme skutečnost, že seznamy lze pozorovat pomocí výrazu shody vzorů. Například pomocí Scala zápis, pokud seznam označuje hodnotu typu Seznam s prázdným seznamem Nula a konstruktor Nevýhody (h, t) můžeme prohlédnout seznam a vypočítat nilCode v případě, že je seznam prázdný a consCode (h, t) když seznam není prázdný:

seznam zápas {  případ Nula        => nilCode  případ Nevýhody(h, t) => consCode(h,t)}

„Seznam“ je dán tím, jak působí na „nilCode“ a „consCode“. Proto definujeme seznam jako funkci, která přijímá takové argumenty 'nilCode' a 'consCode', takže místo výše uvedené shody vzoru můžeme jednoduše napsat:

{ displaystyle operatorname {seznam} operatorname {nilCode} ( operatorname {consCode} h t)}

Označme 'n' parametr odpovídající 'nilCode' a 'c' parametr odpovídající 'consCode'. Prázdný seznam je ten, který vrací nulový argument:

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

Neprázdný seznam s hlavou 'h' a ocasem 't' je dán vztahem

{ displaystyle operatorname {zápory} h t ekviv lambda n. lambda c. c h t}

Obecněji, an algebraický datový typ s ${ displaystyle m}$ alternatives se stává funkcí s ${ displaystyle m}$ parametry. Když ${ displaystyle i}$ th konstruktor má ${ displaystyle n_ {i}}$ argumenty, odpovídá odpovídající parametr kódování ${ displaystyle n_ {i}}$ argumenty také.

Scottovo kódování lze provádět v netypovém lambda kalkulu, zatímco jeho použití u typů vyžaduje typový systém s rekurzí a polymorfismus typu. A list with element type E in this representation that is used to compute values of type C would have the following recursive type definition, where '=>' denotes function type:

typ Seznam =   C =>                    // nil argument  (E => Seznam => C) =>     // cons argument  C                       // result of pattern matching

A list that can be used to compute arbitrary types would have a type that quantifies over C. A list generic^{[je zapotřebí objasnění ]} v E would also take E as the type argument.

Viz také

Lambda calculus
Systém F for Church numerals in a typed calculus
Mogensen–Scott encoding
Von Neumann definition of ordinals — another way to encode natural numbers: as sets

Poznámky

^ ^A ^b Nový druh vědy [1]
^ This formula is the definition of a Church numeral n with f -> m, x -> f.
^ Allison, Lloyd. "Lambda Calculus Integers".
^ Bauer, Andrej. "Andrej's answer to a question; "Representing negative and complex numbers using lambda calculus"".
^ "Exact real arithmetic". Haskell.
^ Bauer, Andrej. "Real number computational software".
^ Pierce, Benjamin C. (2002). Typy a programovací jazyky. MIT Stiskněte. p. 500. ISBN 978-0-262-16209-8.
^ Tromp, John (2007). "14. Binary Lambda Calculus and Combinatory Logic". In Calude, Cristian S (ed.). Randomness And Complexity, From Leibniz To Chaitin. World Scientific. 237–262. ISBN 978-981-4474-39-9.
As PDF: Tromp, John (14 May 2014). "Binary Lambda Calculus and Combinatory Logic" (PDF). Citováno 2017-11-24.
^ Jansen, Jan Martin (2013). "Programming in the λ-Calculus: From Church to Scott and Back". LNCS. 8106: 168–180. doi:10.1007/978-3-642-40355-2_12.

Reference

Directly Reﬂective Meta-Programming
Church numerals and booleans explained by Robert Cartwright at Rice University
Theoretical Foundations For Practical 'Totally Functional Programming' (Chapters 2 and 5) All about Church and other similar encodings, including how to derive them and operations on them, from first principles
Some interactive examples of Church numerals
Lambda Calculus Live Tutorial: Boolean Algebra

[NKS_note_b-1] A ^b Nový druh vědy [1]

[Church_numeral_definition-2] This formula is the definition of a Church numeral n with f -> m, x -> f.

[3] Allison, Lloyd. "Lambda Calculus Integers".

[4] Bauer, Andrej. "Andrej's answer to a question; "Representing negative and complex numbers using lambda calculus"".

[5] "Exact real arithmetic". Haskell.

[6] Bauer, Andrej. "Real number computational software".

[7] Pierce, Benjamin C. (2002). Typy a programovací jazyky. MIT Stiskněte. p. 500. ISBN 978-0-262-16209-8.

[8] Tromp, John (2007). "14. Binary Lambda Calculus and Combinatory Logic". In Calude, Cristian S (ed.). Randomness And Complexity, From Leibniz To Chaitin. World Scientific. 237–262. ISBN 978-981-4474-39-9.
As PDF: Tromp, John (14 May 2014). "Binary Lambda Calculus and Combinatory Logic" (PDF). Citováno 2017-11-24.

[9] Jansen, Jan Martin (2013). "Programming in the λ-Calculus: From Church to Scott and Back". LNCS. 8106: 168–180. doi:10.1007/978-3-642-40355-2_12.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]