University of Sussex
Browse
Sato,_Shinya.pdf (3.15 MB)

Design and implementation of a low-level language for interaction nets

Download (3.15 MB)
thesis
posted on 2023-06-08, 21:05 authored by Shinya Sato
Interaction nets are a graphical model of computation based on a restricted form of graph rewriting. A specific net can represent a program with a user-defined set of nodes and computation is modelled by a user-defined set of rewrite rules. This very simple model has had great success in modelling sharing in computation (specifically in the lambda calculus), and there is potential for generating a new theoretical foundation of parallel computation since all computation steps are local and thus can be implemented in parallel. This thesis is about the implementation of interaction nets. Specifically, for the first contributions we define a low-level language as an object language for the compilation of interaction nets. We study the efficiency and properties of different data structures, and focus on the management of the rewriting process which is usually hidden in the graph rewriting system. We provide experimental data comparing the different choices of data structures and select one for further development. For the compilation of nets and rules into this language, we show an optimisation such that allocated memory for agents is reused, and thus we obtain optimal efficiency for the rewriting process. The second part of this thesis describes extensions of interaction nets so that they can be used as a programming language. Interaction nets in their pure form are quite restrictive in expressive power. By extending the notions of agents and rules we can express computation more naturally, yet still preserve the good properties (such as strong confluence) of the rewriting system. We then implement a selection of algorithms using and extending the compilation techniques developed in the first part of the thesis. We also demonstrate experimental results on multi-core CPUs, using the Posix-thread library, thus realising some of the potential for parallel implementation mentioned above.

History

File Version

  • Published version

Pages

229.0

Department affiliated with

  • Informatics Theses

Qualification level

  • doctoral

Qualification name

  • phd

Language

  • eng

Institution

University of Sussex

Full text available

  • Yes

Legacy Posted Date

2015-06-16

Usage metrics

    University of Sussex (Theses)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC