Kyrkans kodning - Church encoding

I matematik är kyrkans kodning ett sätt att representera data och operatörer i lambda -kalkylen . De Kyrkans siffror är en representation av de naturliga talen med hjälp av lambda notation. Metoden är uppkallad efter Alonzo -kyrkan , som först kodade data i lambda -kalkylen på detta sätt.

Termer som vanligtvis anses primitiva i andra notationer (som heltal, booleaner, par, listor och taggade fackföreningar) mappas till högre ordningsfunktioner under kyrkans kodning. Den Church-Turings hypotes hävdar att någon beräkningsbar operatören (och dess operander) kan representeras enligt Church kodning. I den oskrivna lambda -kalkylen är funktionen den enda primitiva datatypen .

Kyrkans kodning är inte avsedd som en praktisk implementering av primitiva datatyper. Dess användning är att visa att andra primitiva datatyper inte krävs för att representera någon beräkning. Fullständigheten är representativ. Ytterligare funktioner behövs för att översätta representationen till vanliga datatyper för visning för människor. Det är i allmänhet inte möjligt att avgöra om två funktioner är extensivt lika på grund av att det inte går att bestämma likvärdighet från kyrkans sats . Översättningen kan tillämpa funktionen på något sätt för att hämta värdet den representerar, eller slå upp dess värde som en bokstavlig lambda -term.

Lambda calculus brukar tolkas som att den använder intensiv jämlikhet . Det finns potentiella problem med tolkningen av resultat på grund av skillnaden mellan den intensiva och extensiva definitionen av jämlikhet.

Kyrkliga siffror

Kyrkliga siffror är representationer av naturliga nummer under kyrkans kodning. Den högre ordningens funktion som representerar naturliga tal n är en funktion som avbildar varje funktion till dess n -faldig komposition . I enklare termer motsvarar siffrans "värde" det antal gånger funktionen inkapslar sitt argument. ${\ displaystyle f}$

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

Alla kyrkliga siffror är funktioner som har två parametrar. Kyrkans siffror 0 , 1 , 2 , ..., definieras enligt följande i lambda -beräkningen .

Börja med att 0 inte använder funktionen alls, fortsätt med 1 tillämpa funktionen en gång, 2 tillämpa funktionen två gånger, 3 tillämpa funktionen tre gånger, etc .:

${\ displaystyle {\ begin {array} {r | l | l} {\ text {Number}} & {\ text {Function definition}} & {\ text {Lambda expression}} \\\ 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}}}$

Kyrkans siffra 3 representerar handlingen att tillämpa en given funktion tre gånger på ett värde. Den levererade funktionen tillämpas först på en levererad parameter och sedan successivt på sitt eget resultat. Slutresultatet är inte siffran 3 (om inte den angivna parametern råkar vara 0 och funktionen är en efterföljande funktion ). Själva funktionen, och inte dess slutresultat, är kyrkans siffra 3 . Kyrkans siffra 3 betyder helt enkelt att göra vad som helst tre gånger. Det är en påtaglig demonstration av vad som menas med "tre gånger".

Beräkning med kyrkliga siffror

Aritmetiska operationer på tal kan representeras av funktioner på kyrkans siffror. Dessa funktioner kan definieras i lambda -kalkyl eller implementeras på de flesta funktionella programmeringsspråk (se hur du konverterar lambda -uttryck till funktioner ).

Tilläggsfunktionen använder identiteten . ${\ displaystyle \ operatorname {plus} (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)}$

Efterföljarfunktionen är β-ekvivalent med . ${\ displaystyle \ operatorname {succ} (n) = n+1}$${\ displaystyle (\ operatorname {plus} \ 1)}$

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

Multiplikationsfunktionen använder identiteten . ${\ displaystyle \ operatorname {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}$

Den exponentieringsfunktionen ges av definitionen av kyrkans siffror, . I definitionen ersätt för att få och, ${\ displaystyle \ operatorname {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 \ operatorname {exp} \ m \ n = m^{n} = n \ m}$

vilket ger lambda uttryck,

${\ displaystyle \ operatorname {exp} \ equiv \ lambda m. \ lambda nn \ m}$

Den funktionen är svårare att förstå. ${\ displaystyle \ operatorname {pred} (n)}$

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

En kyrklig siffra använder en funktion n gånger. Föregångarfunktionen måste returnera en funktion som tillämpar dess parameter n - 1 gånger. Detta uppnås genom att bygga en behållare runt f och x , som initieras på ett sätt som utelämnar tillämpningen av funktionen första gången. Se föregångaren för en mer detaljerad förklaring.

Subtraktionsfunktionen kan skrivas utifrån föregångarfunktionen.

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

Tabell över funktioner på kyrkliga siffror

Fungera	Algebra	Identitet	Funktionsdefinition	Lambda uttryck
Efterträdare	${\ 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)}$	...
Tillägg	${\ 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 \ operatorname {succ} m}$
Multiplikation	${\ displaystyle m*n}$	${\ displaystyle f^{m*n} \ x = (f^{m})^{n} \ x}$	${\ displaystyle \ operatorname {multiplicera} \ 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)}$
Exponentiering	${\ displaystyle m^{n}}$	${\ displaystyle n \ m \ f = m^{n} \ f}$	${\ 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 nn \ m}$
Föregångare *	${\ 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)}$
Subtraktion *	${\ displaystyle mn}$	${\ displaystyle f^{mn} \ x = (f^{-1})^{n} (f^{m} x)}$	${\ displaystyle \ operatorname {minus} \ m \ n = (n \ operatorname {pred}) \ m}$	...	${\ displaystyle \ lambda m. \ lambda nn \ operatorname {pred} m}$

* Observera att i kyrkans kodning,

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

Avledning av föregångarfunktionen

Föregångarfunktionen som används i kyrkans kodning är,

${\ displaystyle \ operatorname {pred} (n) = {\ begin {cases} 0 & {\ mbox {if}} n = 0, \\ n-1 & {\ mbox {annars}} \ end {cases}}}$.

För att bygga föregångaren behöver vi ett sätt att tillämpa funktionen 1 färre tid. En siffra n tillämpar funktionen f n gånger på x . Föregångarfunktionen måste använda siffran n för att tillämpa funktionen n -1 gånger.

Innan du implementerar föregångarfunktionen, här är ett schema som omsluter värdet i en behållarfunktion. Vi kommer att definiera nya funktioner som ska användas istället för f och x , kallade inc och init . Behållarfunktionen kallas värde . Den vänstra sidan av tabellen visar en siffra n som tillämpas på inc och init .

${\ displaystyle {\ begin {array} {r | r | r} {\ text {Number}} & {\ text {Använda init}} & {\ text {Använda const}} \\\ hline 0 & \ operatorname {init } = \ operatorname {värde} \ x & \\ 1 & \ operatorname {inc} \ \ operatorname {init} = \ operatorname {värde} \ (f \ x) & \ operatorname {inc} \ \ operatorname {const} = \ operatorname {värde} \ x \\ 2 & \ operatorname {inc} \ (\ operatorname {inc} \ \ operatorname {init}) = \ operatorname {värde} \ (f \ (f \ x)) & \ operatorname {inc} \ (\ operatorname {inc} \ \ operatorname {const}) = \ operatorname {värde} \ (f \ x) \\ 3 & \ operatorname {inc} \ (\ operatorname {inc} \ (\ operatorname {inc} \ \ operatorname {init})) = \ operatorname {värde} \ (f \ (f \ (f \ x))) & \ operatorname {inc} \ (\ operatorname {inc} \ (\ operatorname {inc} \ \ operatorname {const })) = \ operatorname {värde} \ (f \ (f \ x)) \\\ vdots & \ vdots & \ vdots \\ n & n \ operatorname {inc} \ \ operatorname {init} = \ operatorname {value} \ (f^{n} \ x) = \ operatorname {value} \ (n \ f \ x) & n \ operatorname {inc} \ \ operatorname {const} = \ operatorname {value} \ (f^{n-1} \ x) = \ o peratorname {värde} \ ((n-1) \ f \ x) \\\ end {array}}}$

Den allmänna återkommande regeln är,

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

Om det också finns en funktion för att hämta värdet från behållaren (kallat extrakt ),

${\ displaystyle \ operatorname {extract} \ (\ operatorname {value} \ v) = v}$

Sedan kan extrakt användas för att definiera samma funktion som,

${\ displaystyle \ operatorname {samenum} = \ lambda n. \ lambda f. \ lambda x. \ operatorname {extract} \ (n \ operatorname {inc} \ operatorname {init}) = \ lambda n. \ lambda f. \ lambda x. \ operatorname {extract} \ (\ operatorname {value} \ (n \ f \ x)) = \ lambda n. \ lambda f. \ lambda xn \ f \ x = \ lambda nn}$

Den samenum funktion är inte i sig användbar. Men som inc delegater som anropar f till dess containerargument kan vi ordna att inc på den första applikationen får en speciell behållare som ignorerar dess argument så att den första applikationen av f kan hoppas över . Kalla denna nya initiala behållare konst . Höger sida av tabellen ovan visar expansioner av n inc const . Genom att ersätta init med const i uttrycket för samma funktion får vi föregångarfunktionen,

${\ displaystyle \ operatorname {pred} = \ lambda n. \ lambda f. \ lambda x. \ operatorname {extract} \ (n \ operatorname {inc} \ operatorname {const}) = \ lambda n. \ lambda f. \ lambda x. \ operatorname {extract} \ (\ operatorname {value} \ ((n-1) \ f \ x)) = \ lambda n. \ lambda f. \ lambda x. (n-1) \ f \ x = \ lambda n. (n-1)}$

Som förklaras nedan kan funktionerna inc , init , const , värde och extrakt definieras som,

${\ displaystyle {\ begin {align} \ operatorname {value} & = \ lambda v. (\ lambda hh \ v) \\\ operatorname {extract} k & = k \ \ lambda uu \\\ operatorname {inc} & = \ lambda g. \ lambda hh \ (g \ f) \\\ operatorname {init} & = \ lambda hh \ x \\\ operatorname {const} & = \ lambda ux \ end {align}}}$

Vilket ger lambda -uttrycket för pred som,

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

Ett annat sätt att definiera pred

Pred kan också definieras med par:

${\ displaystyle {\ begin {align} \ operatorname {f} = & \ \ lambda p. \ \ operatorname {pair} \ (\ operatorname {second} \ p) \ (\ operatorname {succ} \ (\ operatorname {second) } \ p)) \\\ operatorname {zero} = & \ (\ lambda f. \ lambda x. \ x) \\\ operatorname {pc0} = & \ \ operatorname {pair} \ \ operatorname {zero} \ \ operatorname {zero} \\\ operatorname {pred} = & \ \ lambda n. \ \ operatorname {first} \ (n \ \ operatorname {f} \ \ operatorname {pc0}) \\\ end {align}}}$

Detta är en enklare definition, men leder till ett mer komplext uttryck för pred. Expansionen för : ${\ displaystyle \ operatorname {pred} \ operatorname {three}}$

${\ displaystyle {\ begin {align} \ 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 { par} \ \ operatorname {zero} \ \ operatorname {one}))) \\ = & \ \ operatorname {first} \ (\ operatorname {f} \ (\ operatorname {pair} \ \ operatorname {one} \ \ operatorname {two})) \\ = & \ \ operatorname {first} \ (\ operatorname {pair} \ \ operatorname {two} \ \ operatorname {three}) \\ = & \ \ operatorname {two} \ end {align} }}$

Division

Uppdelning av naturliga nummer kan genomföras av,

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

Beräkning tar många betareduktioner. Om det inte görs för hand, spelar det ingen roll så mycket, men det är att föredra att inte behöva göra denna beräkning två gånger. Det enklaste predikatet för att testa siffror är IsZero så tänk på villkoret. ${\ displaystyle nm}$

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

Men detta villkor motsvarar , inte . Om detta uttryck används, översätts den matematiska definitionen av division som ges ovan till funktion på kyrkliga siffror som, ${\ 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))) \ (\ operatorname {minus} \ n \ m)}$

Som önskat har denna definition ett enda samtal till . Resultatet är dock att denna formel ger värdet av . ${\ displaystyle \ operatorname {minus} \ n \ m}$${\ displaystyle (n-1)/m}$

Detta problem kan åtgärdas genom att lägga till 1 till n innan du kallar divide . Definitionen av splittring är då,

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

divide1 är en rekursiv definition. Den Y Combinator kan användas för att implementera rekursion. Skapa en ny funktion som heter div by;

• I vänster sida ${\ displaystyle \ operatorname {divide1} \ rightarrow \ operatorname {div} \ c}$
• I höger sida ${\ displaystyle \ operatorname {divide1} \ rightarrow c}$

att få,

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

Sedan,

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

var,

${\ displaystyle {\ begin {align} \ 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 {align}}}$

${\ displaystyle {\ begin {align} \ operatorname {true} & \ equiv \ lambda a. \ lambda ba \\\ operatorname {false} & \ equiv \ lambda a. \ lambda bb \ end {align}}}$

${\ displaystyle {\ begin {align} \ 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 {align}}}$

Ger,

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

Eller som text, med \ för λ ,

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

Till exempel representeras 9/3 av

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

Med hjälp av en lambda -kalkylator minskar ovanstående uttryck till 3, med normal ordning.

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

Signerade nummer

Ett enkelt tillvägagångssätt för att utvidga kyrkans siffror till signerade nummer är att använda ett kyrkopar som innehåller kyrkosiffror som representerar ett positivt och ett negativt värde. Heltalet är skillnaden mellan de två kyrkans siffror.

Ett naturligt tal konverteras till ett signerat nummer med,

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

Negation utförs genom att byta värden.

${\ displaystyle \ operatorname {neg} _ {s} = \ lambda x. \ operatorname {pair} \ (\ operatorname {second} \ x) \ (\ operatorname {first} \ x)}$

Heltalet är mer naturligt representerat om ett av paret är noll. Den OneZero funktionen uppnår detta tillstånd,

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

Rekursionen kan implementeras med hjälp av Y -kombinatorn,

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

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

Plus och minus

Tillägg definieras matematiskt på paret av,

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

Det sista uttrycket översätts till lambda calculus som,

${\ displaystyle \ operatorname {plus} _ {s} = \ lambda x. \ lambda y. \ operatorname {OneZero} \ (\ operatorname {pair} \ (\ operatorname {plus} \ (\ operatorname {first} \ x) \ (\ operatorname {first} \ y)) \ (\ operatorname {plus} \ (\ operatorname {second} \ x) \ (\ operatorname {second} \ y))))}$

På samma sätt definieras subtraktion,

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

ger,

${\ displaystyle \ operatorname {minus} _ {s} = \ lambda x. \ lambda y. \ operatorname {OneZero} \ (\ operatorname {pair} \ (\ operatorname {plus} \ (\ operatorname {first} \ x) \ (\ operatorname {second} \ y)) \ (\ operatorname {plus} \ (\ operatorname {second} \ x) \ (\ operatorname {first} \ y))))}$

Multiplicera och dela

Multiplikation kan definieras av,

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

Det sista uttrycket översätts till lambda calculus som,

${\ displaystyle \ operatorname {mult} _ {s} = \ lambda x. \ lambda y. \ operatorname {pair} \ (\ operatorname {plus} \ (\ operatorname {mult} \ (\ operatorname {first} \ x) \ (\ operatorname {first} \ y)) \ (\ operatorname {mult} \ (\ operatorname {second} \ x) \ (\ operatorname {second} \ y))) \ (\ operatorname {plus} \ (\ operatorname {mult} \ (\ operatorname {first} \ x) \ (\ operatorname {second} \ y)) \ (\ operatorname {mult} \ (\ operatorname {second} \ x) \ (\ operatorname {first} \ y)))}$

En liknande definition ges här för division, förutom i denna definition måste ett värde i varje par vara noll (se OneZero ovan). Den divZ Funktionen gör det möjligt att bortse från det värde som har ett nollkomponent.

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

divZ används sedan i följande formel, som är densamma som för multiplikation, men med mult ersatt av divZ .

${\ displaystyle \ operatorname {divide} _ {s} = \ lambda x. \ lambda y. \ operatorname {pair} \ (\ operatorname {plus} \ (\ operatorname {divZ} \ (\ operatorname {first} \ x) \ (\ operatorname {first} \ y)) \ (\ operatorname {divZ} \ (\ operatorname {second} \ x) \ (\ operatorname {second} \ y))) \ (\ operatorname {plus} \ (\ operatorname {divZ} \ (\ operatorname {first} \ x) \ (\ operatorname {second} \ y)) \ (\ operatorname {divZ} \ (\ operatorname {second} \ x) \ (\ operatorname {first} \ y)))}}$

Rationella och reella tal

Rationella och beräkningsbara reella tal kan också kodas i lambda -beräkning. Rationella nummer kan kodas som ett par signerade nummer. Beräkningsbara tal kan kodas av en begränsande process som garanterar att skillnaden från det verkliga värdet skiljer sig från ett tal som kan göras så litet som vi behöver. Referenserna beskriver programvara som i teorin kan översättas till lambda -kalkyl. När riktiga tal har definierats kodas naturligt komplexa tal som ett par riktiga tal.

Datatyperna och funktionerna som beskrivs ovan visar att vilken datatyp eller beräkning som helst kan kodas i lambda -kalkyl. Detta är Church-Turing-tesen .

Översättning med andra representationer

De flesta verkliga språk har stöd för maskinfödda heltal; de kyrkliga och unchurch funktioner konvertera mellan nonnegative heltal och deras motsvarande kyrkans siffror. Funktionerna ges här i Haskell , där \motsvarar λ i Lambda -kalkylen. Implementeringar på andra språk liknar varandra.

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

Kyrkobooleaner

Kyrkobooleaner är kyrkan som kodar för de booleska värdena sanna och falska. Vissa programmeringsspråk använder dessa som en implementeringsmodell för booleska räkningar; exempel är Smalltalk och Pico .

Boolsk logik kan betraktas som ett val. Kyrkans kodning av sant och falskt är funktioner av två parametrar:

• true väljer den första parametern.
• false väljer den andra parametern.

De två definitionerna är kända som Church Booleans:

${\ displaystyle {\ begin {align} \ operatorname {true} & \ equiv \ lambda a. \ lambda ba \\\ operatorname {false} & \ equiv \ lambda a. \ lambda bb \ end {align}}}$

Denna definition tillåter predikat (dvs. funktioner som returnerar logiska värden ) att direkt fungera som if-satser. En funktion som returnerar en booleska, som sedan tillämpas på två parametrar, returnerar antingen den första eller den andra parametern:

${\ displaystyle \ operatorname {predicate-} x \ \ operatorname {then-clause} \ \ operatorname {else-clause}}$

utvärderar till då-klausul om predikat-x utvärderas till sant , och till annat-klausul om predikat-x utvärderas till falskt .

Eftersom sant och falskt väljer den första eller andra parametern kan de kombineras för att tillhandahålla logiska operatörer. Observera att det finns flera möjliga implementeringar av inte .

${\ displaystyle {\ begin {align} \ operatorname {och} & = \ lambda p. \ lambda qp \ q \ p \\\ operatorname {eller} & = \ lambda p. \ lambda qp \ p \ q \\\ operatorname {not} _ {1} & = \ lambda p. \ lambda a. \ lambda bp \ b \ a \\\ operatorname {not} _ {2} & = \ lambda pp \ (\ lambda a. \ lambda bb ) \ (\ lambda a. \ lambda ba) = \ lambda pp \ operatorname {false} \ operatorname {true} \\\ operatorname {xor} & = \ lambda a. \ lambda ba \ (\ operatorname {not} \ b ) \ b \\\ operatorname {if} & = \ lambda p. \ lambda a. \ lambda bp \ a \ b \ end {align}}}$

Några exempel:

${\ displaystyle {\ begin {align} \ operatorname {och} \ 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 {eller} \ 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) (\ 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 {Justerat}}}$

Predikat

Ett predikat är en funktion som returnerar ett booleskt värde. Det mest grundläggande predikatet är , som återkommer om dess argument är kyrkans siffra , och om dess argument är någon annan kyrkans siffra: ${\ displaystyle \ operatorname {IsZero}}$${\ displaystyle \ operatorname {true}}$${\ displaystyle 0}$${\ displaystyle \ operatorname {false}}$

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

Följande predikat testar om det första argumentet är mindre än eller lika med det andra:

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

På grund av identiteten,

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

Testet för jämlikhet kan genomföras som,

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

Kyrkopar

Kyrkopar är kyrkans kodning av paret (två-tupel). Paret representeras som en funktion som tar ett funktionsargument. När den får sitt argument kommer den att tillämpa argumentet på parets två komponenter. Definitionen i lambda calculus är,

${\ displaystyle {\ begin {align} \ operatorname {pair} & \ equiv \ lambda x. \ lambda y. \ lambda zz \ ​​x \ y \\\ operatorname {first} & \ equiv \ lambda pp \ (\ lambda x . \ lambda yx) \\\ operatorname {second} & \ equiv \ lambda pp \ (\ lambda x. \ lambda yy) \ end {align}}}$

Till exempel,

${\ displaystyle {\ begin {align} & \ 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 {align}}}$

Lista kodningar

En ( oföränderlig ) lista är konstruerad från listnoder. De grundläggande operationerna på listan är;

Vi ger fyra olika representationer av listor nedan:

• Bygg varje listnod från två par (för att möjliggöra tomma listor).
• Bygg varje listnod från ett par.
• Representera listan med den högra vikningsfunktionen .
• Representera listan med Scotts kodning som tar fall av matchuttryck som argument

Två par som listnod

En icke -undantagslista kan implementeras av ett par i kyrkan;

• Först innehåller huvudet.
• Andra innehåller svansen.

Detta ger dock inte en representation av den tomma listan, eftersom det inte finns någon "null" pekare. För att representera null kan paret vara inslaget i ett annat par, vilket ger fria värden,

• Först - Är nollpekaren (tom lista).
• För det andra. Först innehåller huvudet.
• Second.Second innehåller svansen.

Med hjälp av denna idé kan de grundläggande listoperationerna definieras så här:

Uttryck	Beskrivning
${\ displaystyle \ operatorname {nil} \ equiv \ operatorname {pair} \ \ operatorname {true} \ \ operatorname {true}}$	Det första elementet i paret är sant vilket betyder att listan är null.
${\ displaystyle \ operatorname {isnil} \ equiv \ operatorname {first}}$	Hämta null (eller tom lista) indikator.
${\ displaystyle \ operatorname {cons} \ equiv \ lambda h. \ lambda t. \ operatorname {pair} \ operatorname {false} \ (\ operatorname {pair} h \ t)}$	Skapa en listnod, som inte är noll, och ge den ett huvud h och en svans t .
${\ displaystyle \ operatorname {head} \ equiv \ lambda z. \ operatorname {first} \ (\ operatorname {second} z)}$	andra. först är huvudet.
${\ displaystyle \ operatorname {tail} \ equiv \ lambda z. \ operatorname {second} \ (\ operatorname {second} z)}$	andra. andra är svansen.

I en noll nod andra aldrig nås, förutsatt att huvud och svans endast tillämpas på nonempty listor.

Ett par som listnod

Alternativt definiera

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

där den sista definitionen är ett specialfall av generalen

${\ displaystyle \ operatorname {process-list} \ equiv \ lambda ll (\ lambda h. \ lambda t. \ lambda d. \ operatorname {head-and-tail-clause}) \ operatorname {nil-klausul}}$

Representera listan med högervikt

Som ett alternativ till kodningen med hjälp av kyrkkopplar kan en lista kodas genom att identifiera den med sin högra vikningsfunktion . Till exempel kan en lista med tre element x, y och z kodas av en högre ordningsfunktion som när den appliceras på en kombinator c och ett värde n returnerar cx (cy (czn)).

${\ displaystyle {\ begin {align} \ 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 {tail} & \ equiv \ lambda l. \ lambda c. \ lambda nl \ (\ lambda h. \ lambda t. \ lambda gg \ h \ (t \ c)) \ (\ lambda tn) \ (\ lambda h. \ lambda tt) \ end {align}}}$

Denna lista representation kan viss typ i System F .

Representera listan med Scott -kodning

En alternativ representation är Scott -kodning, som använder tanken på fortsättningar och kan leda till enklare kod. (se även kodning Mogensen – Scott ).

I detta tillvägagångssätt använder vi det faktum att listor kan observeras med hjälp av mönster matchande uttryck. Om vi till exempel använder Scala -notation, om det listbetecknar ett värde av typen Listmed tom lista Niloch konstruktör kan Cons(h, t)vi inspektera listan och beräkna nilCodeom listan är tom och consCode(h, t)när listan inte är tom:

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

'Listan' ges av hur den fungerar på 'nilCode' och 'consCode'. Vi definierar därför en lista som en funktion som accepterar sådana 'nilCode' och 'consCode' som argument, så att vi istället för ovanstående mönstermatchning helt enkelt kan skriva:

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

Låt oss beteckna parametern som motsvarar 'nilCode' och 'c' den parameter som motsvarar 'consCode'. Den tomma listan är den som returnerar nollargumentet:

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

Listan som inte är tom med huvudet 'h' och svansen 't' ges av

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

Mer allmänt blir en algebraisk datatyp med alternativ en funktion med parametrar. När den konstruktören har argument, tar motsvarande parameter för kodningen också argument. ${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle i}$${\ displaystyle n_ {i}}$${\ displaystyle n_ {i}}$

Scott -kodning kan göras i otypad lambda -kalkyl, medan dess användning med typer kräver ett typsystem med rekursion och typpolymorfism. En lista med elementtyp E i denna representation som används för att beräkna värden av typ C skulle ha följande definition av rekursiv typ, där '=>' betecknar funktionstyp:

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

En lista som kan användas för att beräkna godtyckliga typer skulle ha en typ som kvantifierar över C. En generisk lista Eskulle också ta Esom typargument.

Se även

• Lambda -kalkyl
• System F för kyrkliga siffror i en maskinskriven kalkyl
• Mogensen – Scott kodning
• Von Neumann definition av ordinaler - ett annat sätt att koda naturliga tal: som uppsättningar

Anteckningar

Referenser

• Direktreflekterande metaprogrammering
• Kyrksiffror och booleaner förklarade av Robert Cartwright vid Rice University
• Teoretiska grunder för praktisk 'helt funktionell programmering' (kapitel 2 och 5) Allt om kyrkan och andra liknande kodningar, inklusive hur man härleder dem och hur de fungerar, från de första principerna
• Några interaktiva exempel på kyrkosiffror
• Lambda Calculus Live Tutorial: Boolean Algebra