Programování výpočetních funkcí - Programming Computable Functions

Ve vědě o počítačích , programování vyčíslitelných funkcí (PCF) je napsaný funkcionální jazyk představil Gordon Plotkin v roce 1977, na základě předchozí nepublikovaného materiálu Dana Scotta . Lze jej považovat za rozšířenou verzi typovaného lambda kalkulu nebo za zjednodušenou verzi moderních typovaných funkčních jazyků, jako je ML nebo Haskell .

Zcela abstraktní model pro PCF byl nejprve dán Milner (1977). Protože však Milnerův model byl v podstatě založen na syntaxi PCF, byl považován za méně než uspokojivý (Ong, 1995). První dva plně abstraktní modely nevyužívající syntaxi byly formulovány v průběhu 90. let minulého století. Tyto modely jsou založeny na herní sémantice (Hyland a Ong, 2000; Abramsky, Jagadeesan a Malacaria, 2000) a Kripkeho logických vztazích (O'Hearn a Riecke, 1995). Nějakou dobu se zdálo, že ani jeden z těchto modelů nebyl zcela uspokojivý, protože nebyly účinně prezentovatelné. Nicméně, Ralph nakladač prokázaly, že žádný účinně reprezentativní zcela abstraktní model by mohl existovat, protože otázka programu ekvivalence v finitary fragmentu PCF není rozhodnutelný.

Syntax

Tyto typy PCF jsou definovány jako indukčně

• nat je typ
• Pro typy σ a τ existuje typ σ → τ

Kontext je seznam dvojic X: å , kde x je název variabilní a σ je typ, takže žádný název proměnné duplikovány. Poté definujeme typizační úsudky termínů v kontextu obvyklým způsobem pro následující syntaktické konstrukce:

• Proměnné (pokud x: σ je součástí kontextu Γ , pak Γ ⊢ x  : σ )
• Aplikace (výrazu typu σ → τ na výraz typu σ )
• λ-abstrakce
• Y pevný bod kombinátor (což z hlediska typu å z hlediska typu å → å )
• Operace následník ( succ ) a předchůdce ( pred ) na nat a konstanta 0
• Podmíněné, pokud s pravidlem psaní:

${\ Displaystyle {\ frac {\ Gamma \; \ vdash \; t \ ;: {\ textbf {nat}}, \ quad \ quad \ Gamma \; \ vdash \; s_ {0} \;: \ sigma, \ quad \ quad \ Gamma \; \ vdash \; s_ {1} \;: \ sigma} {\ Gamma \; \ vdash \; {\ textbf {if}} (t, s_ {0}, s_ {1}) \;: \ sigma}}}$

( nat s zde budou interpretovány jako booleány s konvencí jako nula označující pravdu a jakékoli jiné číslo označující nepravdu)

Sémantika

Denotační sémantika

Poměrně přímočarou sémantikou jazyka je Scottův model . V tomto modelu

• Typy jsou interpretovány jako určité domény .
  • ${\ Displaystyle [\! [{\ textbf {nat}}] \!]: = \ mathbb {N} _ {\ bot}}$ (přirozená čísla se spodním prvkem sousedí, s plochým uspořádáním)
  • ${\ Displaystyle [\! [\ sigma \ to \ tau \,] \!]}$je interpretován jako doména Scott-spojitých funkcí od do s bodovým uspořádáním.${\ Displaystyle [\! [\ sigma] \!] \,}$${\ Displaystyle [\! [\ tau] \!] \,}$
• Kontext je interpretován jako produkt${\ Displaystyle x_ {1}: \ sigma _ {1}, \; \ tečky, \; x_ {n}: \ sigma _ {n}}$${\ Displaystyle [\! [\ sigma _ {1}] \!] \ times \; \ dots \; \ times [\! [\ sigma _ {n}] \!]}$
• Termíny v kontextu jsou interpretovány jako spojité funkce${\ Displaystyle \ Gamma \; \ vdash \; x \;: \; \ sigma}$${\ displaystyle [\! [\ Gamma] \!] \; \ to \; [\! [\ sigma] \!]}$
  • Variabilní termíny jsou interpretovány jako projekce
  • Abstrakce a aplikace lambda jsou interpretovány s využitím karteziánské uzavřené struktury kategorie domén a spojitých funkcí
  • Y se interpretuje tak, že se vezme nejméně pevný bod argumentu

Tento model není pro PCF plně abstraktní; ale je zcela abstraktní pro jazyk získaný přidáním paralely nebo operátoru do PCF (str. 293 v odkazu Hyland a Ong 2000 níže).

Poznámky

Reference

• Scott, Dana S. (1969). „Typově teoretická alternativa k CUCH, ISWIM, OWHY“ (PDF) . Nepublikovaný rukopis .Objevil se jako Scott, Dana S. (1993). „Typově teoretická alternativa k CUCH, ISWIM, OWHY“ . Teoretická počítačová věda . 121 : 411–440. doi : 10,1016/0304-3975 (93) 90095-b .
• Plotkin, Gordon D. (1977). „LCF považován za programovací jazyk“ (PDF) . Teoretická počítačová věda . 5 (3): 223–255. doi : 10,1016/0304-3975 (77) 90044-5 .
• Milner, Robin (1977). „Plně abstraktní modely napsaných λ-kalkulů“ (PDF) . Teoretická počítačová věda . 4 : 1–22. doi : 10,1016/0304-3975 (77) 90053-6 . hdl : 20.500.11820/731c88c6-cdb1-4ea0-945e-f39d85de11f1 .
• Mitchell, John C. (1996). „Jazyk PCF“. Základy pro programovací jazyky .
• Abramsky, S., Jagadeesan, R. a Malacaria, P. (2000). „Úplná abstrakce pro PCF“ . Informace a výpočet . 163 (2): 409–470. doi : 10,1006/inco.2000.2930 .Správa CS1: více jmen: seznam autorů ( odkaz )
• Hyland, JME & Ong, C.-HL (2000). „O úplné abstrakci pro PCF“ . Informace a výpočet . 163 (2): 285–408. doi : 10,1006/inco.2000.2917 .
• O'Hearn, PW & Riecke, J. G (1995). „Kripke logické vztahy a PCF“ . Informace a výpočet . 120 (1): 107–116. doi : 10.1006/inco.1995.1103 .
• Loader, R. (2001). „Konečný PCF není rozhodnutelný“ . Teoretická počítačová věda . 266 (1–2): 341–364. doi : 10,1016/S0304-3975 (00) 00194-8 .
• Ong, C.-HL (1995). „Korespondence mezi operativní a denotační sémantikou: problém úplné abstrakce pro PCF“ . In Abramsky, S .; Gabbay, D .; Maibau, TSE (eds.). Handbook of Logic in Computer Science . Oxford University Press. s. 269–356. Archivovány od originálu na 2006-01-07 . Citováno 2006-01-19 .

externí odkazy

• Úvod do RealPCF
• Lexer a Parser pro PCF napsané v SML