Here's the basic spec:
A program is an array of cells, each cell containing some code, and they are all connected to their neighbors in a grid lattice, with the connections being represented by pointers to queues (A can put data in B's queue and B can put data in A's queue, because A and B are neighbors in the grid). Syntactically, you separate cells in the same row by "|" and rows by newlines.
Each cell has four pieces of code (which may be blank, thus, NOPs), separated by ":", so a single cell has this structure:
<other cells>|<code response for message received from up>:<response for right>:<response for down>:<response for left>|<other cells>
Within each code block the following instructions can be used:
T<expr1><expr2> - Returns the value of expr1.value-expr2.value.
C<loc><expr> - Sends the value of expr to loc and returns the value of expr.
G<loc> - Returns the oldest message in the queue from loc. If no message from loc exists, block until a message arrives and intercept it.
A<expr><expr1><expr2> - Evaluate to expr1 if expr is 0, otherwise evaluate to expr2.
Fix'd. Thx guys!
Other characters will be ignored and may be used for comment and code clarification. "(",",", and ")" may be useful.
Each of the "<loc>" type arguments above can take a single character, which gives a reference to "up neighbor","right neighbor", "down neighbor", and "left neighbor" respectively, in this manner:
Code: Select all
The entire zeroth row is predefined with cells that always receive user input and send it to the cell below it.
The entire zeroth column is predefined to block waiting for messages from cells to their right, and output the data to standard out.
All cells left undefined are given the default cell code of:
That is, they consume any messages they are passed immediately and do nothing with them.
All messages sent between cells consist of a single byte.
Every program begins with an initialization string like so:
Program interpretation goes in this manner.
To begin, the init string is processed in order as if it were user input.
For the rest of the time:
All cells will execute code corresponding to messages it received in FCFS order. That is, if a cell has a message delivered to its queue from its right neighbor, it will execute its "code response for message from right." The only exception is if a cell is currently blocking waiting for a message, in which case it will ignore all messages until that message is received. If it is not blocked, it will greedily consume messages until it blocks again or runs out, whichever comes first. (As you can see, this would operate quite nicely on parallel processors.)
So, e.g., a program to add two numbers together might look like:
The second cell will subtract the second input "0" from the first input "0" for a result of zero, which it puts in the first cell's queue. The first cell will subtract "0" from "0" also, giving zero, and then proceed to block for user input, consecutively subtracting from zero the next two values input for a total of -sum. Finally, it subtracts this value from the value of zero it retrieved from the cell to the right earlier to give a result of 0-(-sum)=sum, which it sends to the left into column 0. As previously stated, this will cause sum to be printed to stdout.
So, for those of you who have read this far, what do you think? I think it's Turing-complete.
What things do you think would be nice to change? Would you consider writing code for it if an interpreter were available, just to challenge yourself? What if there were a GUI to edit cells graphically and watch the contents of queues as the program runs?