An Encoding of Interaction Nets in OCaml

Nikolaus Huber, Wang Yi · 2025

Read An Encoding of Interaction Nets in OCaml by Nikolaus Huber, Wang Yi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-20463.txt.

Introduction

Nikolaus Huber and Wang Yi show, in a 2025 paper, how to build a diagram-based programming language inside a mainstream one, with proof it behaves. Interaction nets are a visual language where programs are graphs that rewrite themselves. That design naturally allows many rewriting steps to run in parallel. Their encoding in OCaml captures the nets' moving parts and also the original type system that keeps nets well-formed.

The emphasis is on guarantees. By leaning on the host language's own type checker, illegal net configurations are rejected before the program ever runs. The encoding is deliberately small and plain, meant to be read as much as executed. The authors present it as a foundation for experimenting with parallel graph rewriting. No new language needs building first. The point is craftsmanlike: the right host makes an exotic model of computation feel ordinary.

Catalog record

CREATORNikolaus Huber, Wang Yi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-20463

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Encoding of Interaction Nets in OCaml Nikolaus Huber, Wang Yi Abstract Interaction nets constitute a visual programming language grounded in graph transformation. Owing to their distinctive properties, they inherently facilitate parallelism in the rewriting step. This paper showcases a simple and concise approach to encoding interaction nets within the programming language OCaml, emphasising correctness guarantees. To achieve this objective, we encode not only the interaction net primitives, but also Lafont’s original type system. 1 Introduction Interaction nets, introduced by Lafont in [ 13 ] , are a model of computation based on graph rewriting. They have, among other things, been used as a basis for optimal [ 4 , 14 ] and efficient implementations [ 15 ] of the \lambda -calculus. Interaction nets offer a number of desirable properties, such as locality of reduction, strong confluence, and Turing completeness. Owing to the locality of reduction, highly parallel implementations can be devised, while the confluence guarantees determinism. They have been studied both as a model for the dynamics of computation and also as a programming language itself. However, only a few implementations are still actively maintained. In this paper, we study a method of encoding interaction nets into the general purpose programming language OCaml. Unlike previous efforts, our focus is not on the efficiency of reduction, but rather on embedding Lafont’s original type system to provide stronger correctness guarantees. By utilising advanced type system features of the host language, we can statically enforce Lafont’s typing discipline without relying on dynamic checks. To the best of our knowledge, this is the first encoding of interaction nets in OCaml, and the first attempt at embedding Lafont’s type system into the type system of another language. Given OCaml’s recent addition of native support for expressing parallelism, we therefore also explore whether interaction nets can serve as a general implementation scheme for parallel algorithms in the language. The structure of this paper is as follows: In Section 2 we give an overview of the model of interaction nets together with the graphical notation we will be using throughout the paper, followed by a brief introduction to OCaml and an overview of previous work. In Section 3 we illustrate our method of encoding interaction nets into OCaml by way of showing a concrete example. In Section 4 we look at the runtime behaviour of different encoded nets, and investigate if they can make use of OCaml’s support for parallelism. Finally, we give directions for future work and conclude in Section 5 . 2 Preliminaries 2.1 Interaction nets We briefly recall the basic notions of interaction nets. For a more complete presentation, the interested reader is referred to [ 13 ] . Interaction nets consist of the following elements: • A set \Sigma of symbols . These symbols are used as labels for nodes, which are referred to as agents . Each agent has a fixed set of ports , through which they connect with other agents. An agent has exactly one distinguished principle port , and a (possibly empty) set of auxiliary ports . The number of auxiliary ports is fixed for each symbol. We assume the existence of a function ar:\Sigma\rightarrow\mathbb{N} , such that, for all \alpha\in\Sigma , ar(\alpha) is the number of auxiliary ports associated with the symbol \alpha . Figure 1(a) illustrates the usual graphical notation for agents of three different symbols \alpha , \beta , and \gamma . The principle port is depicted as an arrow, auxiliary ports are numbered clockwise from the principle port. In the given example ar(\alpha)=3 , ar(\beta)=0 , and ar(\gamma)=1 . • A net N is an undirected graph built from agents over the set \Sigma . Each edge of the graph connects two agent ports together, such that there is only one edge per port. A port that is not connected is called a free port . The set of free ports of a net is called its interface . • A set \mathcal{R} of rules . A pair of agents (\alpha,\beta)\in\Sigma\times\Sigma is called an active pair if they are connected through their principle ports (this is related to the concept of a redex in term rewriting). The application of an interaction rule ((\alpha,\beta)\rightarrow N)\in\mathcal{R} replaces an active pair by a net N in such a way that the interface of N coincides exactly with the auxiliary ports of \alpha and \beta . Intuitively, this means, that all auxiliary connections of the active pair must be connected to the new net, and no new free ports can be introduced in the process. Figure 1(b) shows an example of the graphical notation for rules. (a) Example agents (b) Example rule Figure 1 : Graphical notations for agents and rules Rewriting happens through the application of interaction rules to active pairs. Since every agent only has one distinct principle port, the rewriting process is local, and two different active pairs can be rewritten in parallel. Some additional requirements are necessary to guarantee determinism: For each pair (\alpha,\beta) there can only be at most one rule in \mathcal{R} , and if there is no rule for a specific active pair it cannot be further reduced. Since there is no notion of orientation, rules are symmetric, meaning that (\alpha,\beta)\rightarrow N and (\beta,\alpha)\rightarrow N describe the same rule. With these restrictions in place it can be shown [ 13 ] , that the reduction sequence is strongly confluent. 2.2 Typed interaction nets Already in the original paper [ 13 ] , Lafont remarks that not all possible connections between agents have a valid semantic interpretation. In the next section, we will introduce agents representing boolean and integer values, as well as agents representing functions over those values. A function agent expecting a particular type at its principle port cannot be reduced when paired with an agent of the wrong type. Therefore, Lafont introduced a rudimentary type system, where each port of an agent is assigned both a value type , and a polarity . Value types can include integers, booleans, floats, lists, etc. The polarity encodes if a port is meant to be an input or an output. An example can be seen in Figure 2 . It is up to convention if inputs receive positive, or negative polarity, as long as the assignment is consistent throughout. In this paper, we will follow the same convention as in [ 13 ] , where inputs have negative, and outputs positive polarity. Only ports of the same type, but opposite polarity, can be connected to each other. Rules are well typed if their left-hand side is well typed (i.e., the principle ports of the active pair have the same type and opposite polarity), and if the net on the right-hand side is well typed, taking into account the interface types provided by the auxiliary connections of the active pair. Figure 2 : Examples of typed agents 2.3 OCaml OCaml is an industrial-strength (primarily functional) programming language which arose as an extension of the Caml dialect of the ML language family. While it is a general-purpose language, it has a strong background in theorem proving (e.g., Coq [ 2 ] ), static analysis (e.g., Frama-C [ 12 ] ), and formal methods software.

Read the complete text