The PI language
This is a simple programming language based on the Pi calculus. I wrote it to play with the ideas introduced by the Pi calculus myself without going through extensive literature. An interesting aspect of the Pi calculus is that all logic is defined in a very localized manner; the only way to build larger programs is to figure out a way to let these parts communicate with each other independent of execution order.
I will try to build a fuzzer/prover to establish that a given PI program produces stable results. To work with input and output some special channels are added to the basic Pi calculus.
Hello, World!
! Print "Hello, World!\n" and exit.
<>stdout__H; <>stdout__e; <>stdout__l; <>stdout__l; <>stdout__o;
<>stdout_2C; <>stdout_20;
<>stdout__W; <>stdout__o; <>stdout__r; <>stdout__l; <>stdout__d;
<>stdout_21; <>stdout_0A.
Grammar
The PI core language has the following grammar:
P,Q ::= +x;P | y<-x;P | y<<x;P | y->x;P | y->x. | PQ | (P)
All variable names must match the regular expression [a-zA-Z0-9_]+
. There are
special IO channels to interact with input and output without introducing
data types. The IO channels are:
stdin_read
triggers a byte read.stdin_[0-9A-F]{2}
triggers when a specific byte is read.stdout_[0-9A-F]{2}
writes bytes to the standard output when triggered.stdin__[a-zA-Z0-9]
andstdout__[a-zA-Z0-9]
are aliases.stdin_EOF
triggers when the stdin EOF is reached.DEBUG
prints information about any channel sent to it.
I replaced the replication operator with a subscribe operator which will respawn the subsequent process whenever a new element is received on the subscribed channel. I believe this is more practical and easier to define. To prove that Turing completeness is retained one could try to program a beta reduction algorithm for the Lambda calculus in PI.
Extensions
A supported syntactic sugar is the ability to use multiple arguments at once:
x,y->v,w
is desugared to x->v;x->w;y->v;y->w
. You can write line comments
after a !
(inspired by Fortran, I believe the exclamation mark is perfect for
attracting the readers attention, as if the author is screaming at you to please
understand what is going on). To make working with multiple files more practical
there are two pre-processing directives:
#global: name
declaresname
to be a global channel.#attach: file.pi
instructs the interpreter to include the program infile.pi
and make its global channels available here.
Semantics
Here is a list of scenarios I considered to determine an appropriate simulation algorithm. This list is by no means complete, and I did not start from a formal semantics because I want to start from a practical perspective (and save time). In my simulation algorithm I try to allow future extensions for randomly dropping or delaying processes and messages.
+x,y;x->y;z<-y.
Once a process sends it cannot receive what it sent later on. Hence here z is not equal to x, instead the process waits for the next message through y. It is guaranteed that z is always the message after x.+x,y;(x->y.z<-y.)
Parallel processes in the same block are started simultaneously and can communicate with each other from the start. Thus here z is equal to x. A stricter rule is that receiving processes (subscribers) are started first such that they can always receive the first sent of any process in parallel. Without this rule a lot of constructs become near impossible.x,y;(z<-y;v<-z.x->y;+v;v->x.)
When sending x to y the process cannot expect that the other process receives it right away. To make sure that the other process can receive v through x it has to wait for an acknowledgement.
Note: theoretical computer scientists may find it absurd I do not start from a type theory or formal operational semantics. However I regard this project as a puzzle for myself to discover what works and what doesn't. And I really do dread reading long documents.
Using goroutines
An interesting exercise would be to make a PI interpreter that (ab)uses Go routines and channels. The program processor (before simulation) would have to determine when channels can be marked as dead (e.g. determine the information needed such that the simulator can perform reference counting) such that they can be closed (or else a multitude of open channels will accumulate). I am not sure if it is possible to create a channel that can send arbitary typed channels itself. Otherwise a central channel registry is needed.