Title: Extending interaction nets towards the real world
Language: English
Authors: Jiresch, Eugen Robert Winfried 
Qualification level: Doctoral
Keywords: interaction nets; Seiteneffekte; Monaden; Funktionale Programmierung; Graphersetzung
interaction nets; side effects; monads; functional programming; graph rewriting
Advisor: Gramlich, Bernhard
Issue Date: 2012
Number of Pages: 102
Qualification level: Doctoral
Abstract: 
Interaction nets sind ein formales Berechnungsmodell: Sie verwenden Graphen und Regeln zur Graphersetzung ("rewriting"), um Berechnung zu beschreiben.
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.
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.
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.

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.
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.
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.
Interaction nets lack many features of a practical programming language needed to conveniently express complex functions.
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).
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-60418
http://hdl.handle.net/20.500.12708/12949
Library ID: AC07814346
Organisation: E185 - Institut für Computersprachen 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

File Description SizeFormat
Extending interaction nets towards the real world.pdf775.61 kBAdobe PDFThumbnail
 View/Open
Show full item record

Page view(s)

15
checked on Feb 18, 2021

Download(s)

47
checked on Feb 18, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.