Skip to content

Latest commit

 

History

History
275 lines (200 loc) · 6.93 KB

README.md

File metadata and controls

275 lines (200 loc) · 6.93 KB

inet-forth

Moore's Law is broken.

Figure 6.11: MIPS/Clock-Frequency Trend for Intel CPUs

(Figure 6.11: MIPS/Clock-Frequency Trend for Intel CPUs, from "Is Parallel Programming Hard, And, If So, What Can You Do About It?", by Paul E. McKenney)

The exponential increase in single-threaded performance halted in about 2003. Therefore, increasing performance will increasingly require parallelism.

How do we program a machine with many cores?

One possible solution is the graph-based computation model -- interaction nets -- where a program in this computation model can automatically make use of any number cores in the machine.

The project -- inet-forth -- is an implementation of interaction nets as a forth-like language.

Syntax

define-node <name> <input-ports> -- <output-ports> end
define-rule <name> <name> <function-body> end
define <name> <function-body> end

Examples

Natural Number

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

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

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

The rule between (add1) and (add):

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

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

To apply this rule is to disconnect and delete (add1) and (add) and reconnect newly exposed wires:

  • ( addend result ) save the wires that were connected to (add) to local variable addend and result.
  • ( prev ) save the wire that was connected to (add1) to local variable prev.
  • prev push local variable to the stack.
  • addend push local variable to the stack.
  • add take two arguments from the stack and create a new (add) node.
  • add1 take one argument from the stack and create a new (add1) node.
  • result push local variable to the stack.
  • connect take two wires from the stack and connect them.

The rule between (zero) and (add):

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

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

To apply this rule is to disconnect and delete (zero) and (add) and reconnect newly exposed wires:

  • ( addend result ) save the wires that were connected to (add) to local variable addend and result.
  • addend push local variable to the stack.
  • result push local variable to the stack.
  • connect take two wires from the stack and connect them.

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! end
define-node add1 prev -- value! end
define-node add target! addend -- result end

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

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

define two
  zero add1 add1
end

two two add

inspect-run

List

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

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

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

define-node sole -- value! end

null sole cons sole cons sole cons
null sole cons sole cons sole cons
append

inspect-run

More

For more examples, please see the examples/ directory.

Docs

Community

Install

Dependencies:

  • debian/ubuntu: sudo apt install libx11-dev

Compile:

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

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

$ ./bin/inet-forth
inet-forth 0.1.0

commands:
  run -- run files
  self-test -- run self test
  version -- print version
  help -- print help message

For examples:

./bin/inet-forth run examples/readme/nat.fth

Development

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

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

gmake clean
LDFLAGS=-fsanitize=thread CFLAGS=-fsanitize=thread gmake -j
gmake self-test

Implementations

References

Papers:

Books:

Languages:

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