Abstraktní syntaxe vyššího řádu - Higher-order abstract syntax
Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace.Srpna 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v počítačová věda, vyšší syntaxe abstraktního řádu (zkráceně HOAS) je technika pro reprezentaci abstraktní syntaxové stromy pro jazyky s proměnnou pojiva.
Vztah k abstraktní syntaxi prvního řádu
Abstraktní strom syntaxe je abstraktní protože to je matematický objekt která má ze své podstaty určitou strukturu. Například v abstraktní syntaxe prvního řádu (FOAS) stromy, jak se běžně používají v překladače, stromová struktura implikuje relaci subexprese, což znamená, že k disambiguaci programů nejsou zapotřebí žádné závorky (jak jsou, v konkrétní syntaxe ). HOAS odhaluje další strukturu: vztah mezi proměnnými a jejich vazebnými místy. V reprezentacích FOAS je proměnná obvykle reprezentována identifikátorem, přičemž vztah mezi vazebným místem a použitím je indikován pomocí stejný identifikátor. U HOAS neexistuje pro proměnnou žádný název; každé použití proměnné odkazuje přímo na vazebné místo.
Existuje celá řada důvodů, proč je tato technika užitečná. Za prvé, činí vazebnou strukturu programu explicitní: stejně jako není třeba vysvětlovat prioritu operátoru v reprezentaci FOAS, není třeba mít po ruce pravidla vazby a rozsahu k interpretaci reprezentace HOAS. Zadruhé, programy, které jsou alfa-ekvivalent (lišící se pouze v názvech vázaných proměnných) mají shodná reprezentace v HOAS, což může zefektivnit kontrolu ekvivalence.
Implementace
Jeden matematický objekt, který lze použít k implementaci HOAS, je a graf kde proměnné jsou spojeny s jejich vazebnými místy prostřednictvím hrany. Další populární způsob implementace HOAS (například v kompilátorech) je s de Bruijn indexy.
Použití v logických rámcích
V doméně logické rámce, pojem abstraktní syntaxe vyššího řádu se obvykle používá k označení konkrétní reprezentace, která používá pořadače metajazyk kódovat vazebnou strukturu jazyk objektu.
Například logický rámec LF má konstrukci λ, která má typ šipky (→). Kódování prvního řádu konstrukce jazykového objektu nechat
bude (pomocí Twelf syntax):
exp: type.var: type.v: var -> exp.let: exp -> var -> exp -> exp.
Tady, exp
je rodina výrazů objektového jazyka. Rodina var
je reprezentace proměnných (implementována snad jako přirozená čísla, která nejsou zobrazena); konstanta proti
je svědkem skutečnosti, že proměnné jsou výrazy. Konstanta nechat
je výraz, který má tři argumenty: výraz (který je vázán), proměnnou (na kterou je vázán) a další výraz (že je proměnná vázána uvnitř).
The kanonický HOAS reprezentace stejného jazyka objektu by byla:
exp: type.let: exp -> (exp -> exp) -> exp.
V tomto znázornění se proměnné na úrovni objektu výslovně nezobrazí. Konstanta nechat
vezme výraz (který je vázán) a funkci metaúrovně exp
→ exp
(tělo nájmu). Tato funkce je vyšší řád část: výraz s volnou proměnnou je představován jako výraz s díry které jsou při použití vyplněny funkcí metaúrovně. Jako konkrétní příklad bychom vytvořili výraz na úrovni objektu
nechť x = 1 + 2v x + 3
(za předpokladu přirozených konstruktorů pro čísla a sčítání) pomocí podpisu HOAS výše jako
let (plus 1 2) ([y] plus y 3)
kde [y] e
je Twelfova syntaxe pro tuto funkci .
Tato konkrétní reprezentace má výhody, které přesahují ty výše: pro jednoho, opětovné použití metaúrovně pojmu vazby, kódování má vlastnosti, jako je zachování typu substituce bez nutnosti je definovat / prokázat. Tímto způsobem může použití HOAS drasticky snížit množství standardní kód co do činění s vazbou v kódování.
Abstraktní syntaxe vyššího řádu je obecně použitelná pouze tehdy, když proměnné objektového jazyka lze chápat jako proměnné v matematickém smyslu (tj. Jako záskoky pro libovolné členy nějaké domény). To často platí, ale ne vždy: například z kódování HOAS nelze získat žádné výhody dynamický rozsah jak se objevuje v některých dialektech Lisp protože proměnné s dynamickým rozsahem nepůsobí jako matematické proměnné.
Viz také
Reference
- Dale Miller; Gopalan Nadathur (1987). Logický programovací přístup k manipulaci se vzorci a programy (PDF). IEEE Symposium on Logic Programming. 379–388.
- Frank Pfenning, Conal Elliott (1988). Abstraktní syntaxe vyššího řádu (PDF). Sborník řízení ACM SIGPLAN PLDI '88. 199–208. doi:10.1145/53990.54010. ISBN 0-89791-269-1.
- J. Despeyroux; A. Felty; A. Hirschowitz (1995). High-Order Abstract Syntax in Coq. Přednášky z informatiky. 902. str. 124–138. doi:10.1007 / BFb0014049. ISBN 978-3-540-59048-4. Archivovány od originál dne 30. 8. 2006.
- Martin Hofmann (1999). Sémantická analýza abstraktní syntaxe vyššího řádu. 14. výroční IEEE Symposium on Logic in Computer Science. p. 204. ISBN 0-7695-0158-3.
- Dale Miller (2000). Abstraktní syntaxe pro variabilní pořadače: Přehled (PDF). Computational Logic - {CL} 2000. str. 239–253. Archivovány od originál (PDF) dne 02.12.2006.
- Eli Barzilay; Stuart Allen (2002). Odráží abstraktní syntaxi vyšších řádů v Nuprl (PDF). Věta prokazující logiku vyšších řádů 2002. s. 23–32. ISBN 3-540-44039-9. Archivovány od originál (PDF) dne 2006-10-11.
- Eli Barzilay (2006). Samohostitelský hodnotitel využívající HOAS (PDF). ICFP Workshop o schématu a funkčním programování 2006.