Skip to content
/ inpla Public

Inpla: Interaction nets as a programming language (the current version)

License

Notifications You must be signed in to change notification settings

inpla/inpla

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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.0-2, released on 12 September 2024. (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

Related Work

My repository

License

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