*** Concurrent Brainfuck *** Concurrent Brainfuck pushes brainfuck into the new millenium. It extens Branfuck with a simple multithreading concept that formed after the co-routine concept found in some other programming languages. *** Concurrent Brainfuck - officialistical specification draft V0.4beta *** -1. Preamble: To avoid such horrible diversity between implementations as seen in machine Code, C or Brainfuck, Concurrent Brainfuck has an exact and unambiguous specification. (See the portable Brainfuck document at http://www.muppetlabs.com/~breadbox/bf/standards.html to see Brian Raiters excellent effort to shut the stable door when the horse has bolted. This document tries to conform to Brians Spec in the sense that every program written conforming to the portable brainfuck rules should not lead to unexpected behaviour on a Concurrent Brainfuck machine.) 0. Comments in Parentheses are informal only, they are offered to give additional hints and explanations, but don't impose restrictions. 1. This specification is not normative, all other specifications that yield indistinguishable behaviour compared to this spec is also valid. 2. The Concurrent Brainfuck virtual machine consists of: - an array of at least 9999 memory cells, each one is capable of storing at least an signed 16 bit binary integer using two'S complement arithmetics (-32768 to +32767) and is initialized to zero before the first access. (The array may be larger, and crossing the arrays bounds may lead to dynamic extension, runtime errors, wrap around or ignoring the instruction. The cells may have a larger range of values or even be "unlimited" numbers like the python2.2 integers, the GNU gmp package or the Java BigIntegers, thus being only limited by the amount of available memory. At overflow, the cells may wrap around, keep the largest or smallest possible value, generate a runtime error or even jump to a random value.) - a program array that contains the Concurrent Brainfuck code, this array is not visible to the brainfuck program itsself. (At least not by standard Concurrent Brainfuck means.) - a dynamic list of threads, each one consisting of a program counter pointing to the current instruction and an address register pointing to the current memory cell. On startup, there is exactly one thread, having the program counter pointing to the first command in the program array and the memory counter positioned in such a way that 9998 consecutive ">" operations won't hit the array bounds. (This means "on the first cell" in simple implementations that have a memory array internally indexed from 0 to 9998, but such wording doesn't make much sense in those implementations that dynamically extend the array or allow access to cells "to the left" of the start cell.) - a thread counter array that contains one entry for every } symbol in the program source, initialized to 0. - a standard input and a standard output char stream. Both streams represent the char written by its ASCII code number. Implementations may extend the range of possible characters using ISO-Latin-1 or Unicode character number, but must ensure that such a character can be stored in a memory cell without loss. (This e. G. forbids 32-Bit Unicode on machines with 16 bit memory cells.) 3. Concurrent Brainfuck defines 11 opcodes. All opcodes implicitly move the program counter of the current thread to the next opcode after their execution. (This sentence is especially important to understand the full meaning of the opcodes "[]{}|".) When the program counter points to the last opcode after execution, and thus cannot be moved to the next opcode, the thread terminates. As soon as the last thread terminates (by "falling over" or by a } instruction), the Brainfuck program terminates. + increases the current memory cell by 1 - decreases the current memory cell by 1 < makes the memory pointer point to the next lower memory cell > makes the memory pointer point to the next higher memory cell . outputs the character in the current memory cell to stdout , reads the next character from stdin into the current memory cell [ jumps to the matching ] when the current memory cell is 0 ] jumps to the matching [ when the current memory cell is not 0 { creates a new thread for each | between itsself and the matching }, ignoring any | contained between nested {}s. Each of the new threads has the same current memory cell as the current thread, but the program counter is initialized to point to the corresponding |. Also increases the thread count of the corresponding } for each thread created. } If the thread count for this } is >0, decrease it by one and terminate the current thread. | makes the program counter point to the command just before the next }, ignoring any }s that belong to nested pairs {}s. 4. Syntactical and sematical sugar: - Opcodes not defined in this document yield undefined behaviour, maybe even runtime errors. The recommended behaviour for implementors is to ignore them, but the programmer could not count on this. - []s and {}s must be matching / balanced in the usual sense, but they may be nested or overlapping. (Thus, the sequence "++[-{]|.}" is a legal Concurrent Brainfuck program, starting 2 additional threads, each one printing cell 0. "{{+|>+}|>>+}" is legal as well.) Additionally, there may be no | outside the outermost {}s. Breaking this rule yields undefined behaviour, implementations should raise an error in this case, but programmers cannot rely on this. - The opcodes + and - are atomic operations - The different threads are to be preemtively scheduled in round-robin, pseudo-random or every other order that makes shure that starvation is avoided. (Without this restriction, it would be allowed for the implementation to execute the threads "batch-like", means it only schedules another thread when the current one terminates. This would create deadlocks as soon as the current thread loops waiting for a result produced by another thread.) - Each implementation must be capable of running at least 42 threads in parallel. Trying to create more threads than possible must result in an immediate abnormal program termination, and should raise a run time error.