Zmenšení grafu - Graph reduction
v počítačová věda, redukce grafu implementuje efektivní verzi non-přísného hodnocení, an strategie hodnocení kde argumenty funkce nejsou okamžitě vyhodnoceny. Tato forma non-strict hodnocení je také známá jako líné hodnocení a použitý v funkční programovací jazyky. Tato technika byla poprvé vyvinuta Chris Wadsworth v roce 1971.
Motivace
Následuje jednoduchý příklad vyhodnocení aritmetického výrazu:
Výše uvedená redukční sekvence využívá strategii známou jako zmenšení nejvzdálenějšího stromu. Stejný výraz lze vyhodnotit pomocí nejvnitřnější redukce stromu, čímž se získá redukční sekvence:
Všimněte si, že objednávka redukce je explicitně přidána v závorkách. Tento výraz mohl být také jednoduše vyhodnocen zprava doleva, protože sčítání je asociativní úkon.
Zastoupen jako strom, výše uvedený výraz vypadá takto:
Odtud pochází termín redukce stromu. Když jsme zastoupeni jako strom, můžeme si představit nejvnitřnější redukci jako práci zdola nahoru, zatímco nejvzdálenější funguje shora dolů.
Výraz může být také reprezentován jako a směrovaný acyklický graf, umožňující sdílení dílčích výrazů:
Pokud jde o stromy, vnější a nejvnitřnější redukce platí také pro grafy. Proto máme redukce grafu.
Nyní může hodnocení s redukcí vnějšího grafu probíhat následovně:
Všimněte si, že hodnocení nyní vyžaduje pouze čtyři kroky. Vnější redukce grafu se označuje jako líné hodnocení a nejvnitřnější redukce grafu se označuje jako nedočkavé hodnocení.
Redukce kombinátorového grafu
Redukce kombinátorového grafu je základní implementační technika pro Funkcionální programování jazyky, ve kterých je program převeden na a kombinátor reprezentace, která je mapována na a řízený graf datová struktura v paměti počítače a spuštění programu pak spočívá v přepsání částí tohoto grafu („jeho zmenšení“), aby se posunulo k užitečným výsledkům.
Dějiny
Koncept redukce grafu, který umožňuje sdílení vyhodnocených hodnot, byl poprvé vyvinut v Chris Wadsworth v jeho 1971 Ph.D. disertační práce.[1] Tato disertační práce byla citována Peterem Hendersonem a Jamesem H. Morrisem Jr. v článku z roku 1976 „Líný hodnotitel“[2] který zavedl pojem líného hodnocení. V roce 1976 David Turner zapracoval líné hodnocení do SASL pomocí kombinátorů.[3]SASL byl časný funkční programovací jazyk, který poprvé vytvořil Turner v roce 1972.
Viz také
Poznámky
- ^ Hudak, Paul (září 1989). "Koncepce, vývoj a aplikace funkčních programovacích jazyků". ACM Výpočetní průzkumy. 21 (3): 359–411. CiteSeerX 10.1.1.83.6505. doi:10.1145/72551.72554.
- ^ Líný hodnotitel
- ^ Hudak, Paul; Hughes, John; Peyton Jones, Simon; Wadler, Philip. „A History of Haskell: Being Lazy with Class“. Konference o historii programovacích jazyků 2007.
Reference
- Bird, Richard (1998). Úvod do funkčního programování pomocí Haskell. Prentice Hall. ISBN 0-13-484346-0.
Další čtení
- Simon Peyton Jones, Implementace funkčních programovacích jazyků, Prentice Hall, 1987. Plné znění online.[1]