Grafikreduktion - Graph reduction

In der Informatik , Graph Reduktion implementiert eine effiziente Version von nicht-strengen Bewertung, eine Evaluierungsstrategie , wo die Argumente einer Funktion werden nicht sofort ausgewertet. Diese Form der nicht strengen Auswertung wird auch als Lazy Evaluation bezeichnet und in funktionalen Programmiersprachen verwendet . Die Technik wurde erstmals 1971 von Chris Wadsworth entwickelt .

Motivation

Es folgt ein einfaches Beispiel für die Auswertung eines arithmetischen Ausdrucks:

${\ displaystyle {\ begin {align} & {} && ((2 + 2) + (2 + 2)) + (3 + 3) \\ & {} & = & ((2 + 2) + (2+) 2)) + 6 \\ & {} & = & ((2 + 2) +4) +6 \\ & {} & = & (4 + 4) +6 \\ & {} & = & 8 + 6 \ \ & {} & = & 14 \ end {align}}}$

Die obige Reduktionssequenz verwendet eine Strategie, die als äußerste Baumreduktion bekannt ist . Der gleiche Ausdruck kann unter Verwendung der innersten Baumreduktion bewertet werden , was die Reduktionssequenz ergibt:

${\ displaystyle {\ begin {align} & {} && ((2 + 2) + (2 + 2)) + (3 + 3) \\ & {} & = & ((2 + 2) +4) + (3 + 3) \\ & {} & = & (4 + 4) + (3 + 3) \\ & {} & = & (4 + 4) +6 \\ & {} & = & 8 + 6 \ \ & {} & = & 14 \ end {align}}}$

Beachten Sie, dass die Reduzierungsreihenfolge durch Hinzufügen von Klammern explizit angegeben wird. Dieser Ausdruck hätte auch einfach von rechts nach links ausgewertet werden können, da Addition eine assoziative Operation ist.

Der obige Ausdruck wird als Baum dargestellt und sieht folgendermaßen aus:

Hier kommt der Begriff Baumreduktion her. Wenn wir als Baum dargestellt werden, können wir uns die innerste Reduktion als von unten nach oben arbeitend vorstellen, während die äußerste von oben nach unten arbeitet.

Der Ausdruck kann auch als gerichteter azyklischer Graph dargestellt werden , so dass Unterausdrücke gemeinsam genutzt werden können:

Bei Bäumen gilt die äußerste und innerste Reduzierung auch für Diagramme. Daher haben wir eine Graphreduktion .

Jetzt kann die Auswertung mit äußerster Graphenreduzierung wie folgt erfolgen:

Beachten Sie, dass die Auswertung jetzt nur noch vier Schritte erfordert. Die äußerste Graphreduktion wird als verzögerte Auswertung bezeichnet, und die innerste Graphreduzierung wird als eifrige Auswertung bezeichnet .

Reduktion des Kombinatorgraphen

Kombinator Graphenreduktion ist ein fundamentales Implementierungstechnik für funktionale Programmierung Sprachen, in denen ein Programm in eine umgewandelt wird Kombinator Darstellung , die auf eine zugeordneten ist Digraph - Datenstruktur in einem Computerspeicher, und die Programmausführung besteht dann Teile dieser graphischen Darstellung des Neuschreibens ( "Reduktions "es), um zu nützlichen Ergebnissen zu gelangen.

Geschichte

Das Konzept einer Graphreduktion, mit der ausgewertete Werte geteilt werden können, wurde erstmals 1971 von Chris Wadsworth in seiner Doktorarbeit entwickelt. Dissertation. Diese Dissertation wurde 1976 von Peter Henderson und James H. Morris Jr. in dem Artikel „Ein fauler Bewerter“ zitiert, der den Begriff der faulen Bewertung einführte. 1976 integrierte David Turner die faule Bewertung mithilfe von Kombinatoren in SASL . SASL war eine frühe funktionale Programmiersprache, die erstmals 1972 von Turner entwickelt wurde.

Siehe auch

• Grafikreduktionsmaschine
• SECD-Maschine

Anmerkungen

Verweise

• Bird, Richard (1998). Einführung in die funktionale Programmierung mit Haskell . Prentice Hall. ISBN   0-13-484346-0 .

Weiterführende Literatur

• Simon Peyton Jones , Die Implementierung funktionaler Programmiersprachen , Prentice Hall, 1987. Volltext online. [1]