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
8k Dec 29, 2022
16.6k Jan 1, 2023
20 Dec 27, 2022
4 Feb 15, 2022
22 Dec 30, 2022
2.6k Dec 31, 2022
21 Dec 13, 2022
13 Jan 6, 2023
7 Feb 21, 2022
103 Dec 22, 2022