Redukce grafu - Graph reduction

Ve vědě o počítačích , snížení graf realizuje efektivní verzi non-přísné posouzení, což hodnotící strategie , kde argumenty funkce nejsou okamžitě vyhodnoceny. Tato forma nestriktního hodnocení je také známá jako líné hodnocení a používá se ve funkčních programovacích jazycích . Tuto techniku ​​poprvé vyvinul Chris Wadsworth v roce 1971.

Motivace

Následuje jednoduchý příklad vyhodnocení aritmetického výrazu:

${\ displaystyle {\ begin {aligned} & {} && ((2 + 2) + (2 + 2)) + (3 + 3) \\ & {} & = & ((2 + 2) + (2+ 2)) + 6 \\ & {} & = & ((2 + 2) +4) +6 \\ & {} & = & (4 + 4) +6 \\ & {} & = & 8 + 6 \ \ & {} & = & 14 \ end {zarovnáno}}}$

Výše uvedená redukční sekvence využívá strategii známou jako redukce nejvzdálenějšího stromu . Stejný výraz lze vyhodnotit pomocí nejvnitřnější redukce stromu , čímž se získá redukční sekvence:

${\ displaystyle {\ begin {aligned} & {} && ((2 + 2) + (2 + 2)) + (3 + 3) \\ & {} & = & ((2 + 2) +4) + (3 + 3) \\ & {} & = & (4 + 4) + (3 + 3) \\ & {} & = & (4 + 4) +6 \\ & {} & = & 8 + 6 \ \ & {} & = & 14 \ end {zarovnáno}}}$

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 přidání je asociativní operace.

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 lze také reprezentovat jako směrovaný acyklický graf , který umožňuje 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 redukci 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 dychtivé hodnocení .

Redukce kombinátorového grafu

Redukce kombinatorického grafu je základní implementační technikou pro funkční programovací jazyky, při které se program převádí na kombinátorovou reprezentaci, která je mapována na datovou strukturu řízeného grafu v paměti počítače, a provádění programu pak sestává z přepisování částí tohoto grafu („redukce „it) tak, aby směřovaly k užitečným výsledkům.

Dějiny

Koncept redukce grafu, který umožňuje sdílení hodnocených hodnot, byl poprvé vyvinut Chrisem Wadsworthem v jeho Ph.D. disertační práce. Tato disertační práce byla citována Peterem Hendersonem a Jamesem H. Morrisem Jr. v článku z roku 1976 „Líný hodnotitel“, který představil pojem líného hodnocení. V roce 1976 David Turner začlenil líné hodnocení do SASL pomocí kombinátorů. SASL byl časný funkční programovací jazyk, který poprvé vytvořil Turner v roce 1972.

Viz také

• Stroj na redukci grafů
• SECD stroj

Poznámky

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 jazyků funkčního programování , Prentice Hall, 1987. Plný text online. [1]