aboutsummaryrefslogtreecommitdiff

Inpla: Interaction nets as a programming language

What is Inpla

Inpla is a multi-threaded parallel interpreter of interaction nets. Once you write programs for sequential execution, it works also in multi-threaded parallel execution. Each thread is managed on each CPU-core with POSIX-thread library.

  • The current version is 0.13.4, released on 26 March 2026. (See Changelog.md for details.)
  • The below graph shows speed-up ratio to threads numbers for programs in the following benchmark table.

speedup-ratio

  • Comparison in execution time with other implementations: Haskell (GHC version 8.10.7), OCaml (ocamlopt, the native-code compiler, version 4.13.1), Standard ML of New Jersey v110.74 (interpreter mode) and Python 3.10.6 in execution time.
Haskell OCaml SML Python Inpla8 Inpla8r
n-queens 12 0.23 0.44 0.60 3.79 0.55 0.44
ack(3,11) 2.37 0.57 0.42 - 0.90 0.72
fib 38 1.61 0.15 0.27 9.27 0.46 0.46
bsort 20000 5.03 6.47 2.39 20.02 2.41 1.56
isort 20000 2.15 1.48 0.60 8.83 0.33 0.35
qsort 260000 0.36 0.22 0.27 10.33 0.15 0.11
msort 260000 0.38 0.17 0.29 11.09 0.14 0.13

  • The above table contains execution time in second on average of ten times execution by using Linux PC (Core i7-9700 (8 threads, no Hyper-threading), 16GB memory). The fastest one is shown with bold style. Scripts for the comparison table are in the comparison directory. These are written to have the same algorithms as much as possible, though only the Ackermann function in Inpla is a little optimised to interaction nets computing so that it can take advantage of the parallelism well.

  • Inpla8 and Inpla8r mean 8 threads without/with reuse-annotated execution, respectively. Inpla8 is called with an enable switch to optimise tail calls, as it is off by default since v0.12.2. Inpla8r is not called with this option because this optimisation will not work if the last equation in a rule has the reuse annotations.

  • "n-queens 12" is computation of n-Queens at 12.

  • "ack(3,11)" is computation of Ackermann function. Execution time of Python is a blank due to stack size limitation error.

  • "fib 38" is computation to get the 38th Fibonacci number.

  • "bsort n", "isort n", "qsort n" and "msort n" are computation of bubble sort, insertion sort, quick sort and merge sort for random n-element lists, respectively, followed by a validation check process.
    In the graph quick sort and merge sort are for 800000 elements because the 260000 elements are too small for Inpla to show the performance in parallel. See the description of v0.8.2-1 in Changelog.md for details.

Contents

Getting Started

  • Requirement

  • gcc (>= 4.0), flex, bison

  • Build

  • Single-thread version: Use make command as follows (the symbol $ means a shell prompt):

    $ make

  • Multi-thread version: Use make with thread option:

    $ make thread
    To get the single-thread version again, use make clean; make.

How to Execute

Interactive mode (single-thread version)

  • Inpla starts in the interactive mode by typing the following command (where the symbol $ is a shell prompt):

    ```
    $ ./inpla
    Inpla 0.10.0 : Interaction nets as a programming language [built: 17 September 2022]

    ```

  • The symbol >>> is a prompt of Inpla. After the prompt you can write rules and nets. For instance, the following is a rule for incrementation inc and a net to bind the increment result of 10 to a name r (where // is a comment):

```

inc(ret) >< (int i) => ret~(i+1); // a rule for inc >< (int i)
inc(r)~10; // a net
(1 interactions, 0.16 sec)
r; // show a connected net from the r
11

```

  • To quit this system, use exit command:

```

exit;
```

Interactive mode (multi-thread version)

  • There is an execution option -t that specifies the number of threads in a thread pool. For instance, by invoking with -t 4 Inpla populates 4 threads in the pool:

$ ./inpla -t 4
The default value is setting for the number of cores, so execution will be automatically scaled without specifying this. This option is useful to see the effect by number of threads.

Batch mode and sample files

  • Inpla has also the batch mode in which a file is evaluated. This is available when invoked with an execution option -f filename. There are sample files in the sample folder. Here we introduce some of ones:

Greatest common divisor

  • Sample file: sample/gcd.in

    ```
    // Example program in Python
    // def gcd(a, b):
    // if b==0: return a
    // else: return gcd(b, a%b)

    // Rules
    gcd(ret) >< (int a, int b)
    | b==0 => ret ~ a
    | _ => gcd(ret) ~ (b, a%b);

// Nets
gcd(r) ~ (14,21);
r; // it should be 7
```

  • Execution:

    ```
    $ ./inpla -f sample/gcd.in
    Inpla 0.10.0 : Interaction nets as a programming language [built: 17 September 2022]
    (4 interactions, 0.00 sec)
    7

    $
    ```

Insertion sort

insertion sort
* Sample file: sample/isort.in

```
// Rules
insert(ret, int x) >< [] => ret~[x];
insert(ret, int x) >< (int y):ys
| x<=y => ret~(x:y:ys)
| _    => ret~(y:cnt), insert(cnt, x)~ys;

isort(ret) >< [] => ret~[];
isort(ret) >< x:xs => insert(ret, x)~cnt, isort(cnt)~xs;


// Nets
isort(r)~[3,6,1,9,2];
r;
```

  • Execution:

    ```
    $ ./inpla -f sample/isort.in
    Inpla 0.10.0 : Interaction nets as a programming language [built: 17 September 2022]
    (16 interactions, 0.00 sec)
    [1,2,3,6,9]

    $
    ```

Quick sort

quick sort
* Sample file: sample/qsort.in

```
// Rules
qsort(ret) >< [] => ret~[];
qsort(ret) >< (int x):xs =>
    ret << Append(left, x:right), part(smaller, larger, x)~xs,
    qsort(left)~smaller, qsort(right)~larger;

// Note: `Append' is implemented as the following built-in agent:
//   Append(ret, b)~a  -->  ret ~ a++b
// The ret << Append(left, x:right) is rewritten 
// by the built-in abbreviation into:
//   Append(ret, x:right)~left.

part(smaller, larger, int x) >< [] => smaller~[], larger~[];
part(smaller, larger, int x) >< (int y):ys
| y<x => smaller~(y:cnt), part(cnt, larger, x)~ys
| _   => larger~(y:cnt), part(smaller, cnt, x)~ys;


// Nets
qsort(r)~[3,6,1,9,2];
r;
```

These rules and nets are also written by using abbreviation:

- Abbreviation notation version:

  An abbreviation notation `<<` is introduced in v.0.5.0. We can write also as follows by the `<<`:
  ```
  a,b,...,z << Agent(aa,bb,...,yy,zz)   == for ==  Agent(a,b,...,z,aa,bb,...,yy) ~ zz 
  ```

  For instance, `r << Add(1,2)` is rewritten internally as `Add(r,1)~2`. It is handy to denote ports that take computation results. The following is another version by using the abbreviation:

  ```
  // Rules
  qsort(ret) >< [] => ret~[];
  qsort(ret) >< (int x):xs =>
    ret << Append(left, x:right), 
    smaller, larger << part(x,xs),
    left << qsort(smaller), right << qsort(larger);

  part(smaller, larger, int x) >< [] => smaller~[], larger~[];
  part(smaller, larger, int x) >< (int y):ys
  | y<x => smaller~(y:cnt),  
           cnt, larger << part(x,ys)
  | _   => larger~(y:cnt), 
           smaller, cnt << part(x,ys);

  // Nets
  r << qsort([3,6,1,9,2]);
  r;
  ```

- Execution:

  ```
  $ ./inpla -f sample/qsort.in
  Inpla 0.10.0 : Interaction nets as a programming language [built: 17 September 2022]
  (22 interactions, 0.00 sec)
  [1,2,3,6,9]

  $
  ```

Other samples

  • Evaluation of a lambda term 245II in YALE encoding, where 2, 4, 5 mean church numbers of lambda terms, and I is a lambda term $\lambda x.x$:

    $ ./inpla -f sample/245II.in

  • Samples of linear systemT encoding (see our paper presented at FLOPS 2016).

    $ ./inpla -f sample/linear-systemT.in

How to write programs in Inpla

Gentle_introduction_Inpla.md explains how to make programs in Inpla step by step. Please look it over!

Updates

See Changelog.md for details.

Publications

My repository

License

Copyright (c) 2022 Shinya Sato
Released under the MIT license
http://opensource.org/licenses/mit-license.php

generated by cgit v1.2.3 (git 2.39.1) at 2026-11-10 15:45:39 +0000