Interaction Nets

An implementation of Interaction Nets in JavaScript.

• Use S-expression as overall syntax.
• Use Forth-like postfix stack-based syntax to build Interaction Nets.

Introduction

Interaction nets is an interesting computation model designed by Yves Lafont in 1990, It uses undirected graphs and graph rewriting to express computations.

It is interesting because:

Our interaction nets are deterministic in a strong sense:

not only the result, but also the computation is unique, up to trivial commutations.

-- Interaction Combinators, Yves Lafont, 1997

References

Papers:

• Interaction Nets, Yves Lafont, 1990 (the founding paper).
• Interaction Combinators, Yves Lafont, 1997.

Books:

• Models of Computation -- An Introduction to Computability Theory, Maribel Fernández, 2009.
  • Chapter 7. Interaction-Based Models of Computation.

Usage

Online playground

Visit the INet Playground.

Command line tool

The command line program is called inet.

Install it by the following command:

npm -g i @cicada-lang/inet

Examples

Natual number

[ PLAYGROUND ]

(define-cons zero 0)
(define-cons add1 1)

(define-elim add 2)
(define-rule (zero add))
(define-rule (add1 add) add add1)

(define-net two
  zero add1
  zero add1
  add)

inet render docs/tests/nat.inet

two.initial	two.finial

List

[ PLAYGROUND ]

(define-cons sole 0) ;; Trivial data for testing.

(define-cons null 0)
(define-cons cons 2)

(define-elim append 2)
(define-rule (null append))
(define-rule (cons append) (let head) append head cons)

(define-net six-soles
  null sole cons sole cons sole cons
  null sole cons sole cons sole cons
  append)

inet render docs/tests/list.inet

six-soles.initial	six-soles.finial

Difference list

[ PLAYGROUND | WIKIPEDIA ]

(define-cons sole 0) ;; Trivial data for testing.

(define-cons null 0)
(define-cons cons 2)

(define-cons diff 2)

(define-elim diff-append 2)
(define-rule (diff diff-append)
  (let that left right)
  left that diff-open right diff)

(define-elim diff-open 2)
(define-rule (diff diff-open)
  (let right) connect right)

(define-net one-two-soles
  wire sole cons diff
  wire sole cons sole cons diff
  diff-append)

(define-net two-two-soles
  wire sole cons sole cons diff
  wire sole cons sole cons diff
  diff-append)

inet render docs/tests/diff-list.inet

one-two-soles.initial	one-two-soles.finial

two-two-soles.initial	two-two-soles.finial

Development

npm install    // Install dependencies
npm run build  // Compile `src/` to `lib/`
npm run watch  // Watch the compilation
npm run test   // Run test

Contributions

Be polite, do not bring negative emotion to others.

• TODO.md
• STYLE-GUIDE.md
• CODE-OF-CONDUCT.md
• When contributing, add yourself to AUTHORS

License

• GPLv3