Jiresch, E. R. W. (2012). Extending interaction nets towards the real world [Dissertation, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-60418
interaction nets; side effects; monads; functional programming; graph rewriting
en
Abstract:
Interaction nets sind ein formales Berechnungsmodell: Sie verwenden Graphen und Regeln zur Graphersetzung ("rewriting"), um Berechnung zu beschreiben.<br />Im Vergleich zu etablierten Modellen wie Turingmaschinen oder dem Lambda-Kalkül bieten interaction nets zwei besondere Eigenschaften: Visualisierung und parallele Evaluierung. Rewriting-regeln werden in einer grafischen Notation definiert, wodurch Algorithmen visualisiert werden. Durch starke Beschränkungen dieser Regeln kann jedes interaction nets Programm parallel evaluiert werden.<br />Diese Eigenschaften machen interaction nets zu einer vielversprechenden Basis für eine zukünftige Programmiersprache. Um Korrektheit von paralleln Programmen zu zeigen, wäre ein formales Modell mit paralleler Evaluierung als "first-class citizen" von großem Vorteil. Unglücklickerweise sind interaction nets ein sehr einfaches und eingeschränktes Berechnungsmodell: Ahnlich dem Lambda-Kalkül ist es nicht praktikabel, ein Programm für reale Anwendungen zu spezifizieren. Interaction nets mangelt es an vielen features von Programmiersprachen, die zum Erstellen komplexer Funktionen notwendig sind.<br />Das Ziel dieser Dissertation ist es, interaction nets näher an die Verwendbarkeit als praktikable Programmiersprache zu bringen. Um Seiteneffekte (I/O, State manipulation, exception handling,. . . ) zu bewältigen, definieren wir Monaden in interaction nets, die auf generic interaction rules basieren. In Kombination mit nested patterns erlauben diese die komfortable Definition von Funktionen höherer Ordnung direkt in interaction nets. Diese Erweiterungen sind konservativ: Mit annehmbaren Einschränkungen erhalten diese die günstigen Eigenschaften des Basismodells. Zusätzlich zu diesen theoretischen Resultaten behandeln wir die Implementierung dieser Features und präsentieren einen Ansatz, um parallele Evaluierung von interaction nets mittels Grafikprozessoren (GPUs) zu realisieren.<br />
de
Interaction nets are a formal model of computation. They use graphs and graph replacement (or rewriting) rules to describe computation. Compared to prominent models such as Turing machines or the lambda-calculus, interaction nets offer two main differences "out of the box": visualization and parallel evaluation.<br />Rewriting rules and input graphs are given in a graphical notation, visualizing an algorithm. Due to strong restrictions on the shape of these rewriting rules, any interaction nets program can be evaluated in parallel.<br />The above properties indicate that interaction nets could be a useful foundation for a programming language. To ensure correctness of parallel programs, a formal model that features parallel evaluation as a "first-class citizen" could be indispensable. Unfortunately, interaction nets are a very basic and restricted model of computation: similar to the lambda-calculus, it is not feasible to specify practical, real-world applications with the basic model.<br />Interaction nets lack many features of a practical programming language needed to conveniently express complex functions.<br />The goal of this thesis is to bring interaction nets closer to real-world usability. In order to tackle computational side effects (I/O, state manipulation,. . . ), we define monads in interaction nets, which are based on generic interaction rules. In combination with nested patterns, these rules allow us to conveniently define higher-order functions directly in interaction nets. We show that these extensions are conservative: under reasonable constraints, they preserve the beneficial properties of the base model. In addition to these theoretical results, we discuss the implementation of these features and present an approach to realize parallel evaluation of interaction nets on graphics processing units (GPUs).<br />