Fexpr - Fexpr

v Lisp programovací jazyky, a fexpr je funkce, jejíž operandy jsou předány bez vyhodnocení. Když se volá fexpr, vyhodnotí se pouze tělo fexpru; žádná jiná hodnocení se neuskutečňují, kromě případů, kdy jsou výslovně iniciovány fexpr. Naproti tomu, když je volána běžná funkce Lisp, jsou operandy vyhodnocovány automaticky a funkci jsou poskytovány pouze výsledky těchto hodnocení; a když (tradiční) Lisp makro je voláno, operandy jsou předávány v nevyhodnoceném, ale bez ohledu na výsledek, který makro funkce vrátí, je automaticky vyhodnocen.

Původ názvu "fexpr"

Na začátku Lispu prostředí mapovalo každý symbol na seznam sdružení, spíše než přímo na hodnotu.[1] Standardní klíče pro tyto seznamy zahrnovaly dva klíče používané k ukládání datové hodnoty, které se mají vyhledat, když se symbol objevil jako argument (APVAL a APVAL1); a čtyři klávesy použité k uložení funkce, které se mají vyhledat, když se symbol vyskytl jako operátor. Z funkčních kláves SUBR označil kompilovanou obyčejnou funkci, jejíž operandy byly vyhodnoceny a předány do ní; FSUBR označil kompilovaný speciální formulář, jehož operandy byly předány nevyhodnocené; EXPR označil uživatelsky definovanou běžnou funkci; a FEXPR označil uživatelem definovaný speciální formulář. Jediný rozdíl mezi FEXPR a EXPR byl v tom, zda byly operandy automaticky vyhodnoceny.

V přísném původním použití je FEXPR tedy uživatelem definovaná funkce, jejíž operandy jsou předávány nehodnocené. V pozdějším použití však termín fexpr může popsat jakýkoli prvotřídní funkce jejichž operandy jsou předávány nehodnocené, bez ohledu na to, zda je funkce primitivní nebo definovaná uživatelem.[2]

KlíčObchodyDefinovánFunkce / speciální formulář
APVALdatová hodnota----
APVAL1datová hodnota----
SUBRfunkceSystémfunkce
FSUBRfunkceSystémspeciální forma
EXPRfunkceuživatelfunkce
FEXPRfunkceuživatelspeciální forma

Příklad

Pro jednoduchou ilustraci fungování fexprs je zde uvedena definice fexpr Programovací jazyk jádra, který je podobný Systém. (Podle konvence v jádře jména fexprs vždy začínají $.)

($ definovat! $ f   ($ vau (X y z) E      ($ pokud (>=? (eval X E) 0)           (eval y E)           (eval z E))))

Tato definice poskytuje fexpr s názvem $ f, který trvá tři operandy. Když se volá fexpr, místní životní prostředí je vytvořen rozšířením statického prostředí, kde byl definován fexpr. Poté se vytvoří místní vazby: symboly X, y, a z jsou vázány na tři operandy volání fexpr a symbol E je vázáno na dynamické prostředí, ze kterého je fexpr volán. Tělo fexpru, ($ pokud...), se poté vyhodnotí v tomto místním prostředí a výsledek tohoto vyhodnocení se stane výsledkem volání fexpr. Čistým efektem je, že první operand je vyhodnocen v dynamickém prostředí a v závislosti na tom, zda je výsledek tohoto vyhodnocení nezáporný, je vyhodnocen druhý nebo třetí operand a tento výsledek je vrácen. Druhý operand, třetí nebo druhý, se nevyhodnocuje.

Tento příklad je staticky vymezeno: místní prostředí je rozšířením statického prostředí. Před zhruba rokem 1980 byly jazyky Lisp, které podporovaly fexprs, převážně dynamicky zaměřeny: místní prostředí bylo spíše rozšířením dynamického prostředí než statického prostředí.[3] Stále však bylo nutné uvést místní název dynamického prostředí, aby se tomu zabránilo zachycení názvy místních parametrů.[4]

Mainstreamové použití a podpora

Podpora Fexpr pokračovala i v roce Lisp 1.5, poslední v podstatě standardní dialekt Lispu, než se fragmentoval do několika jazyků.[5] V 70. letech dva dominantní jazyky Lisp[6] — MacLisp a Interlisp - oba podporované fexprs.[7]

V roce 1980 Konference o Lisp a funkčním programování, Kent Pitman představil příspěvek „Special Forms in Lisp“, ve kterém diskutoval o výhodách a nevýhodách maker a fexprs a nakonec fexprs odsoudil. Jeho hlavní námitka spočívala v tom, že v lispském dialektu, který umožňuje fexprs, statická analýza nelze obecně určit, zda operátor představuje běžnou funkci nebo fexpr - statická analýza tedy nemůže určit, zda budou nebo nebudou operandy vyhodnoceny. Zejména kompilátor nemůže zjistit, zda lze subexpresi bezpečně optimalizovat, protože s podvýrazem lze za běhu zacházet jako s nevyhodnocenými daty.

MAKROnabízí adekvátní mechanismus pro specifikaci definic speciálních formulářů a ... FEXPRnení. ... Navrhuje se, že při navrhování budoucích dialektů Lisp je třeba vážně zvážit návrh, který FEXPRz jazyka by měl být úplně vynechán.[8]

Od úpadku jazyků MacLisp a Interlisp, dvou jazyků Lisp, které do roku 1993 vzrostly k dominanci[9] — Systém a Společný Lisp - nepodporují fexprs. novýLISP nepodporuje fexprs, ale nazývá je „makra“. v Picolisp všechny vestavěné funkce jsou fsubrs, zatímco funkce na úrovni Lisp jsou exprs, fexprs, lexprs nebo jejich kombinace.

fexprs od roku 1980

Začínání s Brian Smith je 3-Lisp v roce 1982 bylo navrženo několik experimentálních dialektů Lisp, aby prozkoumaly hranice výpočetní reflexe. Na podporu reflexe tyto Lisps podporují postupy, které mohou reify různé datové struktury související s voláním na ně - včetně nevyhodnocených operandů volání, díky nimž jsou tyto postupy fexprs. Na konci 90. let se fexprs začal spojovat především s výpočetní reflexí.[10]

Bylo získáno několik teoretických výsledků na fexprs. V roce 1993 John C. Mitchell použil Lisp s fexprs jako příklad programovacího jazyka, jehož zdrojové výrazy nemohou být formálně abstraktní (protože konkrétní syntaxi zdrojového výrazu lze vždy extrahovat kontextem, ve kterém je operandem fexpr ).[11] V roce 1998 Mitchell Wand ukázal, že přidání zařízení fexpr do lambda kalkul - zařízení, které potlačuje přepisování operandů - vytváří a formální systém s triviální rovnicí teorie, což znemožňuje optimalizaci typu zdroj bez zdroje bez analýza celého programu.[10] V roce 2007 navrhl John N. Shutt rozšíření lambda kalkulu, které by modelovalo fexprs, aniž by potlačovalo přepisování operandů, čímž se údajně vyhlo Wandovu výsledku.[12]

Viz také

Následující jazyky implementují fexprs nebo blízké ekvivalenty:

Poznámky pod čarou

  1. ^ McCarthy a kol., Příručka programátora Lisp I, s. 88–91.
  2. ^ Pitman, Revidovaný manuál MacLisp, str. 75.
  3. ^ Steele a Gabriel, „Evoluce Lispu“, s. 239–240.
  4. ^ Pitman, Revidovaný manuál MacLisp, str. 62
  5. ^ Steele a Gabriel, „Evoluce Lispu“, str. 231-232.
  6. ^ Steele a Gabriel, „Evoluce Lispu“, s. 235.
  7. ^ Pitman, Revidovaný manuál MacLisp, str. 182.
  8. ^ Pitman, „Zvláštní formuláře v Lispu“, s. 179.
  9. ^ Steele a Gabriel, „Evoluce Lispu“, s. 245–248
  10. ^ A b Hůlka, „Teorie Fexprs je triviální“, s. 189.
  11. ^ Mitchell, „O abstrakci a expresivní síle programovacích jazyků“, část 7.
  12. ^ Shutt, „vau-calculi a teorie fexprs“.

Reference

  • McCarthy, J.; Brayton, R.; Edwards, D.; Fox, P.; Hodes, L.; Luckham, D.; Maling, K.; Park, D.; Russell, S. (Březen 1960), Příručka programátorů LISP I (PDF), Boston, Massachusetts: Skupina umělé inteligence, M.I.T. Výpočetní centrum a Výzkumná laboratoř Zpřístupněno 11. května 2010.
  • John C. Mitchell, „O abstrakci a expresivní síle programovacích jazyků“, Věda o počítačovém programování 212 (1993), s. 141–163. (Zvláštní vydání příspěvků od Symp. Theor. Aspects of Computer Software, Sendai, Japan, 1991.) Zpřístupněno 24. ledna 2008.
  • Kent M. Pitman, „Special Forms in Lisp“, Proceedings of the ACM Conference 1980 on Lisp and Functional Programming, 1980, pp. 179–187. Přístupné 25. ledna 2008.
  • Kent M. Pitman, Revidovaný manuál MacLisp (Sobotní večerní vydání), MIT Laboratory for Computer Science Technical Report 295, 21. května 1983.
  • John N. Shutt, „vau-calculi a teorie fexprs“, diskuse, New England Programming Languages ​​and Systems Symposium Series (NEPLS), 18. října 2007. Abstraktní zpřístupněno 27. ledna 2008.
  • Guy L. Steele a Richard P. Gabriel, „Evoluce Lispu“, Oznámení ACM SIGPLAN 28 č. 3 (březen 1993), s. 231–270.
  • Mitchell Wand, „Teorie Fexprs je triviální“, Lisp a symbolický výpočet 10 č. 3 (květen 1998), s. 189–199. Přístupné 25. ledna 2008.