Cellbrain
| Paradigm(s) | concurrent,functional,grid |
|---|---|
| Designed by | User:Quintopia |
| Appeared in | 2007 |
| Computational class | Turing complete |
| Reference implementation | None |
| Major implementations | Don't use it (from the Wayback Machine; retrieved on 20 March 2016) |
| Influenced by | Biota,Unlambda |
| File extension(s) | .clb |
Cellbrain, devised by User:Quintopia in 2007, is a grid-based concurrent event-driven language inspired by Biota and Unlambda.
Program Structure
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 of integers (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, cells in a given row are separated by "|" and rows are separated by newlines.
Each cell has four expressions (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>
Instructions
Within each code block the following instructions can be used:
- T<expr1><expr2> - Returns the value of expr1.value-expr2.value. (Mnemonic: Take away)
- C<loc><expr> - Sends the value of expr to loc and returns the value of expr. (Mnemonic: Cat,Copy,Communicate,etc.)
- 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. (Mnemonic: Get)
- A<expr><expr1><expr2> - Evaluate to expr1 if expr is 0, otherwise evaluate to expr2. (Mnemonic: Assess which Alternative)
<expr> can be any instruction, while <loc> can also be any of the characters 'A','C','T','G', but they do not serve as functions in this context. Rather they are pointers to one of the cell's four message queues, corresponding to each of the four cardinal directions in this fashion:
A G C T
Other characters will be ignored and may be used for comment and code clarification. "(",",", and ")" may be useful. Importantly, each code block in a cell contains EXACTLY one expression. Thus, a CNF grammar for a single code block in case-insensitive Cellbrain is:
S->ε|exp exp-> aop aoparg | cop coparg | top dexp | gop loc aoparg-> exp dexp dexp -> exp exp coparg -> loc exp loc-> 'A' | 'C' | 'T' | 'G' | 'a' | 'c' | 't' | 'g' aop-> 'A' | 'a' gop-> 'G' | 'g' top-> 'T' | 't' cop-> 'C' | 'c'
By convention, the rows in a Cellbrain program are named according to the spreadsheet convention: The rows are numbered from top to bottom, and the columns are lettered in alphabetical order from left to right.
Program Execution
All cells in a cellbrain program execute concurrently, processing messages in the order they arrive into any of their four queues by executing the response code for messages arriving from that direction. If a cell tries to receive a message from an empty queue, the entire cell will block until a message is received there. During this time, it will continue to receive messages normally, and it will recommence acting on them in the order received once it unblocks.
Default Cell
Any cell that is not specified in the source will contain the default cell code
GA:GC:GT:GG
which simply consumes any data passed to it.
Input/Output
The zeroth row of the program (implicitly located above the first row in the program source) is an infinite line of cells that receive user input one character at a time and pass it to the cells below them. For instance, if a user types 'a', every cell on the first row will receive a message of 97 in its A queue. The zeroth column (to the left of the first column in the program source) is an infinite line of output cells. Any data passed to any of these cells will be output immediately as characters to the screen.
Initialization/Halting
Every program begins with an initialization string marked by the token "init:" like so:
init:0
When execution begins, this string will be processed as if it were user input. When any data is passed up to the zeroth row, it will cause the program to halt immediately.
Example
A program to add two numbers together:
init:00 C(G,T(G(C),T(T(T(G(A),G(A)),G(A)),G(A)):::|C(G,T(G(A),G(A))
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 to be printed to the screen.
Computational Complexity
With unbounded queue sizes, Cellbrain is almost certainly Turing-complete.
Implementation
An implementation exists, but it sucks. It locks up and hangs. Don't use it. Find it at the external link below and fix it.
External resources
The thread that started it (from the Wayback Machine; retrieved on 20 March 2016)