inet-lisp-st

This project is a single-threaded implementation of interaction nets as a lisp-like language.

Single-threaded environment allow us to support multiple principal ports, with which rules can be expressed by subgraph matching.

Syntax

(define-node <name> <port-name> ...)
(define-rule <pattern> <exp> ...)
(define-rule* (<pattern> ...) <exp> ...)
(define <name> <exp>)
(define (<name> <arg-name> ...) <exp> ...)

Examples

Natural Number

Define three nodes (zero), (add1) and (add):

(define-node zero value!)
(define-node add1 prev value!)
(define-node add target! addend result)

value!   value!        value
  |        |             |
(zero)   (add1)        (add)
           |           /   \
          prev    target!  addend

The rule between (add1) and (add):

(define-rule (add (add1 prev) addend result)
  (add1 (add prev addend) result))

     value             value            value
       |                 |                |
     (add)      =>                =>    (add1)
     /   \                 \              |
(add1)   addend           addend        (add)
   |                 |                  /   \
 prev              prev              prev   addend

The rule between (zero) and (add):

(define-rule (add (zero) addend result)
  (connect addend result))

     value          value         value
       |              |             |
     (add)     =>             =>    |
     /   \              \            \
(zero)   addend        addend       addend

Example interaction:

       |                   |                   |              |
     (add)               (add1)              (add1)         (add1)
     /   \                 |                   |              |
(add1)    (add1)         (add)               (add1)         (add1)
   |        |    =>      /   \       =>        |        =>    |
(add1)    (add1)    (add1)    (add1)         (add)          (add1)
   |        |          |        |            /   \            |
(zero)    (zero)    (zero)    (add1)    (zero)   (add1)     (add1)
                                |                  |          |
                              (zero)             (add1)     (zero)
                                                   |
                                                 (zero)

The whole program with test:

(define-node zero value!)
(define-node add1 prev value!)
(define-node add target! addend result)

(define-rule (add (zero) addend result)
  (connect addend result))

(define-rule (add (add1 prev) addend result)
  (add1 (add prev addend) result))

(define (two) (add1 (add1 (zero))))

(inspect-run (add (two) (two)))

List

(define-node null value!)
(define-node cons head tail value!)
(define-node append target! rest result)

(define-rule (append (null) rest result)
  (connect rest result))

(define-rule (append (cons head tail) rest result)
  (cons head (append tail rest) result))

(define-node sole value!)

(inspect-run
  (append
    (cons (sole) (cons (sole) (cons (sole) (null))))
    (cons (sole) (cons (sole) (cons (sole) (null))))))

More

For more examples, please see the examples/ directory.

Docs

• Programming with Interaction Nets
• 反应网编程

Community

• Discord / concatenative #inet

Install

Dependencies:

• debian/ubuntu: sudo apt install libx11-dev

Compile:

git clone https://github.com/cicada-lang/inet-lisp-st
cd inet-lisp-st
make -j
make test

The compiled binary ./bin/inet-lisp-st is the command-line program.

$ ./bin/inet-lisp-st
inet-lisp-st 0.1.0

commands:
  run -- run files
  play -- play files
  info -- print system info
  test-self -- run self test
  test-modules -- run test for modules
  version -- print version
  help -- print help message

For examples:

./bin/inet-lisp-st run examples/readme/nat.test.lisp

Development

make -j       # compile src/ files to lib/ and bin/
make run      # compile and run the command-line program
make test     # compile and run test
make clean    # clean up compiled files

Using tsan (ThreadSanitizer) to test data race in parallel program:

make clean && TSAN=true make -j

Implementations

• inet-cute
• inet-js
• inet-forth
• inet-lisp-st

References

Papers:

• 1990-interaction-nets
• 1997-interaction-combinators

Books:

• scalable c

Contributions

To make a contribution, fork this project and create a pull request.

Please read the STYLE-GUIDE.md before you change the code.

Remember to add yourself to AUTHORS. Your line belongs to you, you can write a little introduction to yourself but not too long.

License

GPLv3