Částečné hodnocení - Partial evaluation

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Květen 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v výpočetní, dílčí hodnocení je technika pro několik různých typů optimalizace programu podle specializace. Nejpřímější aplikací je výroba nových programů, které běží rychleji než originály, přičemž je zaručeno, že se budou chovat stejně.

A počítačový program prog je viděn jako mapování vstupních dat do výstupních dat:

${ displaystyle prog: I _ { text {static}} krát I _ { text {dynamic}} do O,}$

kde ${ displaystyle I _ { text {static}}}$, statická data, je část vstupních dat známá v době kompilace.

Částečný hodnotitel se transformuje ${ displaystyle langle prog, já _ { text {static}} rangle}$ do ${ displaystyle prog ^ {*}: I _ { text {dynamic}} to O}$ předpočítáním všech statických vstupů v době kompilace. ${ displaystyle prog ^ {*}}$ se nazývá „zbytkový program“ a měl by běžet efektivněji než původní program. Akt částečného hodnocení se říká, že „reziduuje“ ${ displaystyle prog}$ na ${ displaystyle prog ^ {*}}$.

Projekce Futamura

Obzvláště zajímavý příklad použití částečného hodnocení, který poprvé popsal v 70. letech Yoshihiko Futamura,^[1] je Když prog je tlumočník programovacího jazyka.

Li Já_statický je zdrojový kód navržený pro běh uvnitř tohoto tlumočníka, poté vznikne částečné vyhodnocení tlumočníka s ohledem na tato data / program prog*, verze tlumočníka, která spouští pouze tento zdrojový kód, je napsána v implementačním jazyce tlumočníka, nevyžaduje doplňování zdrojového kódu a běží rychleji než původní kombinace tlumočníka a zdroje. V tomto případě prog* je ve skutečnosti kompilovaná verze Já_statický.

Tato technika je známá jako první projekce Futamury, které jsou tři:

1. Specializace tlumočníka pro daný zdrojový kód, čímž se získá spustitelný soubor.
2. Specializace specializátoru pro tlumočníka (jak je použit v # 1), čímž se získá kompilátor.
3. Specializace specializátoru pro sebe (jak je použit v # 2), čímž se získá nástroj, který dokáže převést libovolného tlumočníka na ekvivalentní kompilátor.

Kromě toho použití nástroje v # 3 samo o sobě přináší samotný nástroj, takže je to Quine.

Poprvé je popsal Futamura v roce 1983.^[2]

Viz také

• Provedení funkce v době kompilace
• Memoizace
• Částečné použití
• Specializace algoritmu běhu
• s_mn teorém
• Snížení síly
• Metaprogramování šablon

Reference

Obecné odkazy

• Yoshihiko Futamura, https://web.archive.org/web/20110629171734/http://www.brics.dk/~hosc/local/HOSC-12-4-pp381-391.pdf Částečné vyhodnocení výpočetního procesu - přístup ke kompilátoru-kompilátoru
• Charles Consel a Olivier Danvy (1993). "Výukové poznámky k částečnému vyhodnocení". Proceedings of the Twentieth Annual ACM Symposium on Principles of Programming Languages: 493–501.

externí odkazy

• Neil D. Jones, Carsten K. Gomard a Peter Sestoft: Částečné vyhodnocení a automatické generování programu (1993) Kniha, plný text k dispozici online.
• Workshop ACM SIGPLAN 1999 o částečném hodnocení a manipulaci s programem založeným na sémantice (PEPM'99)
• C ++ Templates as Partial Evaluation, 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99)
• C ++ šablony jako částečné vyhodnocení jiná verze včetně Catatu (pdf)
• Aplikování dynamického částečného vyhodnocení na dynamické reflexní programovací jazyky