Mogensen – Scott kódování - Mogensen–Scott encoding

v počítačová věda, Scott kódování je způsob, jak reprezentovat (rekurzivní) datové typy v lambda kalkul. Kódování kostela provádí podobnou funkci. Data a operátory tvoří matematickou strukturu, která je vložený v lambda kalkulu.

Zatímco církevní kódování začíná reprezentacemi základních datových typů a staví se na něm, Scottovo kódování začíná od nejjednodušší metody skládání algebraické datové typy.

Mogensen – Scott kódování rozšiřuje a mírně upravuje Scottovo kódování aplikací kódování na Metaprogramování. Toto kódování umožňuje reprezentaci lambda kalkul termíny, jako data, které mají být provozovány meta programem.

Dějiny

Scottovo kódování se objeví jako první v sadě nepublikovaných poznámek k přednášce od Dana Scott^[1]jehož první citace se v knize objevuje Kombinatorická logika, díl II^[2]. Michel Parigot podal logický výklad a silně normalizace rekurzor pro Scottovy kódované číslice,^[3] odkazovat se na ně jako na „skládaný typ“ reprezentace čísel.Torben Mogensen později rozšířil Scottovo kódování pro kódování termínů Lambda jako dat.^[4]

Diskuse

Lambda kalkul umožňuje ukládání dat jako parametry na funkci, která ještě nemá všechny parametry požadované pro aplikaci. Například,

{ displaystyle (( lambda x_ {1} ldots x_ {n}. lambda c.c x_ {1} ldots x_ {n}) v_ {1} ldots v_ {n}) f}

Může být považován za záznam nebo strukturu, kde pole ${ displaystyle x_ {1} ldots x_ {n}}$ byly inicializovány s hodnotami ${ displaystyle v_ {1} ldots v_ {n}}$ . K těmto hodnotám lze poté přistupovat použitím termínu na funkci F. To se sníží na,

{ displaystyle f v_ {1} ldots v_ {n}}

C může představovat konstruktor pro algebraický datový typ ve funkčních jazycích, jako je Haskell. Nyní předpokládejme, že existují N konstruktory, každý s ${ displaystyle A_ {i}}$ argumenty;

{ displaystyle { begin {pole} {c | c | c} { text {konstruktor}} & { text {zadané argumenty}} & { text {výsledek}} hline (( lambda x_ { 1} ldots x_ {A_ {1}}. Lambda c_ {1} ldots c_ {N} .c_ {1} x_ {1} ldots x_ {A_ {1}}) v_ {1} ldots v_ {A_ {1}}) & f_ {1} ldots f_ {N} & f_ {1} v_ {1} ldots v_ {A_ {1}} (( lambda x_ {1} ldots x_ {A_ {2}}. Lambda c_ {1} ldots c_ {N} .c_ {2} x_ {1} ldots x_ {A_ {2}}) v_ {1} ldots v_ {A_ { 2}}) & f_ {1} ldots f_ {N} & f_ {2} v_ {1} ldots v_ {A_ {2}} vdots & vdots & vdots (( lambda x_ { 1} ldots x_ {A_ {N}}. Lambda c_ {1} ldots c_ {N} .c_ {N} x_ {1} ldots x_ {A_ {N}}) v_ {1} ldots v_ {A_ {N}}) & f_ {1} ldots f_ {N} & f_ {N} v_ {1} ldots v_ {A_ {N}} end {pole}}}

Každý konstruktor vybere jinou funkci z parametrů funkce ${ displaystyle f_ {1} ldots f_ {N}}$ . To poskytuje větvení v toku procesu na základě konstruktoru. Každý konstruktor může mít jiný arity (počet parametrů). Pokud konstruktory nemají žádné parametry, pak sada konstruktorů funguje jako výčet; typ s pevným počtem hodnot. Pokud mají konstruktory parametry, mohou být konstruovány rekurzivní datové struktury.

Definice

Nechat D být datovým typem s N konstruktéři, ${ displaystyle {c_ {i} } _ {i = 1} ^ {N}}$ , takový konstruktor ${ displaystyle c_ {i}}$ má arity ${ displaystyle A_ {i}}$ .

Scott kódování

Scottovo kódování konstruktoru ${ displaystyle c_ {i}}$ datového typu D je

{ displaystyle lambda x_ {1} ldots x_ {A_ {i}}. lambda c_ {1} ldots c_ {N} .c_ {i} x_ {1} ldots x_ {A_ {i}} }

Mogensen – Scott kódování

Mogensen rozšiřuje Scottovo kódování tak, aby kódoval jakýkoli netypovaný lambda výraz jako data. To umožňuje, aby byl lambda výraz reprezentován jako data v rámci lambda kalkulu meta program. Funkce meta mse převede lambda výraz na odpovídající reprezentaci dat lambda termínu;

{ displaystyle { begin {zarovnaný} operatorname {mse} [x] & = lambda a, b, ca x operatorname {mse} [M N] & = lambda a, b, cb operatorname {mse} [M] operatorname {mse} [N] operatorname {mse} [ lambda xM] & = lambda a, b, cc ( lambda x. operatorname {mse} [ M]) konec {zarovnáno}}}

"Termín lambda" je reprezentován jako označená unie se třemi případy:

Konstruktor A - proměnná (arity 1, ne rekurzivní)
Konstruktor b - funkční aplikace (arity 2, rekurzivní v obou argumentech),
Konstruktor C - lambda-abstrakce (arity 1, rekurzivní).

Například,

{ displaystyle { begin {pole} {l} operatorname {mse} [ lambda xf (x x)] lambda a, b, cc ( lambda x. operatorname {mse} [f (x x)]) lambda a, b, cc ( lambda x. lambda a, b, cb operatorname {mse} [f] operatorname {mse} [x x] ) lambda a, b, cc ( lambda x. lambda a, b, cb ( lambda a, b, ca f) operatorname {mse} [x x]) lambda a, b, cc ( lambda x. lambda a, b, cb ( lambda a, b, ca f) ( lambda a, b, cb operatorname {mse} [x] operatorname {mse} [x])) lambda a, b, cc ( lambda x. lambda a, b, cb ( lambda a, b, ca f) ( lambda a, b, cb ( lambda a, b, ca x) ( lambda a, b, ca x))) end {pole}}}

Srovnání s církevním kódováním

Scottovo kódování se shoduje s Kódování kostela pro booleovce. Církevní kódování párů lze zobecnit na libovolné datové typy kódováním ${ displaystyle c_ {i}}$ z D výše jako^{[Citace je zapotřebí ]}

{ displaystyle lambda x_ {1} ldots x_ {A_ {i}}. lambda c_ {1} ldots c_ {N} .c_ {i} (x_ {1} c_ {1} ldots c_ {N }) ldots (x_ {A_ {i}} c_ {1} ldots c_ {N})}

porovnejte to s kódováním Mogensen Scott,

{ displaystyle lambda x_ {1} ldots x_ {A_ {i}}. lambda c_ {1} ldots c_ {N} .c_ {i} x_ {1} ldots x_ {A_ {i}}}

S touto generalizací se kódování Scott a Church shodují na všech vyjmenovaných datových typech (například booleovském datovém typu), protože každý konstruktor je konstanta (žádné parametry).

Pokud jde o praktičnost použití kódování Church nebo Scott pro programování, existuje symetrický kompromis^[5]: Církevní kódované číslice podporují operaci sčítání v konstantním čase a nemají nic lepšího než předchůdce v lineárním čase; Scottově kódované číslice podporují operaci předchůdce v konstantním čase a nemají nic lepšího než operace sčítání v lineárním čase.

Definice typů

Církevně zakódovaná data a operace na nich lze psát systém F, ale data a operace kódované Scottem nejsou zjevně typovatelné v systému F. Zdá se, že jsou vyžadovány univerzální i rekurzivní typy,^[6].Tak jako silná normalizace neplatí pro neomezené rekurzivní typy^[7]„Ukončení programů manipulujících s daty kódovanými Scottem určením řádové typizace vyžaduje, aby systém typů poskytoval další omezení pro vytváření rekurzivně typovaných výrazů.

Viz také

Poznámky

^ Scott, Dana, Systém funkční abstrakce (1968). Přednášky na University of California, Berkeley, (1962)
^ Curry, Haskell (1972). Kombinatorická logika, díl II. Nakladatelská společnost North-Holland. ISBN 0-7204-2208-6.
^ Parigot, Michel (1988). „Programování s důkazy: teorie typů druhého řádu“. Evropské symposium o programování. Přednášky z informatiky. 300: 145–159. doi:10.1007/3-540-19027-9_10. ISBN 978-3-540-19027-1.
^ Mogensen, Torben (1994). "Efektivní vlastní interpretace v lambda kalkulu". Journal of Functional Programming. 2 (3): 345–364. doi:10.1017 / S0956796800000423.
^ Parigot, Michel (1990). "O reprezentaci dat v lambda kalkulu". Mezinárodní seminář o logice počítačových věd. Přednášky z informatiky. 440: 209–321. doi:10.1007/3-540-52753-2_47. ISBN 978-3-540-52753-4.
^ Viz poznámku "Typy pro číslice Scott" Martín Abadi, Luca Cardelli a Gordon Plotkin (18. února 1993).
^ Mendler, Nax (1987). "Rekurzivní typy a omezení typu v lambda kalkulu druhého řádu". Symposium on Logic in Computer Science (2): 30–36.

Reference

Přímo reflexní metaprogramování
Torben Mogensen (1992). Efektivní vlastní interpretace v lambda kalkulu^{[trvalý mrtvý odkaz ]}. Journal of Functional Programming.

[1] Scott, Dana, Systém funkční abstrakce (1968). Přednášky na University of California, Berkeley, (1962)

[2] Curry, Haskell (1972). Kombinatorická logika, díl II. Nakladatelská společnost North-Holland. ISBN 0-7204-2208-6.

[3] Parigot, Michel (1988). „Programování s důkazy: teorie typů druhého řádu“. Evropské symposium o programování. Přednášky z informatiky. 300: 145–159. doi:10.1007/3-540-19027-9_10. ISBN 978-3-540-19027-1.

[4] Mogensen, Torben (1994). "Efektivní vlastní interpretace v lambda kalkulu". Journal of Functional Programming. 2 (3): 345–364. doi:10.1017 / S0956796800000423.

[5] Parigot, Michel (1990). "O reprezentaci dat v lambda kalkulu". Mezinárodní seminář o logice počítačových věd. Přednášky z informatiky. 440: 209–321. doi:10.1007/3-540-52753-2_47. ISBN 978-3-540-52753-4.

[6] Viz poznámku "Typy pro číslice Scott" Martín Abadi, Luca Cardelli a Gordon Plotkin (18. února 1993).

[7] Mendler, Nax (1987). "Rekurzivní typy a omezení typu v lambda kalkulu druhého řádu". Symposium on Logic in Computer Science (2): 30–36.

[1]

[2]

[3]

[4]

[5]

[6]

[7]