Blood32
| Paradigm(s) | Imperative |
|---|---|
| Designed by | User:PixelatedStarfish |
| Appeared in | 2021 |
| Memory system | Cell-based |
| Computational class | Turing complete |
| Major implementations | Blood32 Interpreter (Java) |
| Influenced by | bf, Befunge, Python, User:Truttle1 |
| Influenced | Vessel |
| File extension(s) | .bld32 |
Blood32 is a language designed to simulate a Turing machine with terse syntax. It is a language designed for experimentation with abstract, low-level computation. Programming in this language is challenging, as it does not feature many of the constructs common to high-level imperative languages, such as functions, variables, and structures.
Blood32 stands for Boolean Language of Orthogonalized Data (with 32 bit integers). It can also be called by its file extension, .bld32, or simply Blood. It was created by User:PixelatedStarfish in June of 2021 and consists of a grid of cells, a tape, and a pointer. Influences include a language by Urban Müller that is impolite to name, Befunge, and Python. The name "Blood32" was chosen after the author watched several Truttle1 videos while recovering from a nosebleed; the 32 is added to distinguish the language from the fluid after which it is named.
As a result of the language design goals, it is somewhat difficult to determine whether this language is truly high level or low level according to how the terms are commonly used. The language simulates computer memory at a low level, but the syntax of language itself can certainly be compiled to a lower, machine friendly level. Low level is usually applied to languages that can be processed directly on a chip or virtual machine, but it is by no means a strict term.
A compiler for this language would be much simpler than what is typical for a high level language. Compiling this language to some assembly code would only be a matter of direct translation. In other words, such a compiler would not require a symbol table for variables or a means to interpret scope. Many high level constructs are not implemented in this language to allow for a simpler interpreter. The Goblins Operation is arguably the highest level operation the language features, as it requires an additional memory pointer. Ultimately, it is unclear if any of these factors alone, or even together, place the language into the high level or low level. For lack of a better term, this language can be termed "middle-level", not quite as high level as C, but not low level enough to be considered a true assembly language per se, only very close to one.
Memory
In Blood32, memory is stored on cells. Cells can be located on a grid, or on an unbounded tape.
Cells
A cell is a boolean that can have a position (x, y) on the grid, or a position on the tape. Cell states are as follows:
| State | Description |
|---|---|
| 0 | 0 or false |
| 1 | 1 or true |
| B | blank or null, can be used to separate numbers or characters in tape initialization. |
The tape
The tape is a one dimensional array of cells. Each cell has an index that is a nonnegative integer. By default, the tape has 64 cells, but writing to higher indices will extend the tape. The tape is unbounded in the positive direction, so it can be useful for simulating a Turing machine.
The tape is initialized with ' T: ' and a string of booleans
T:
a blank tape
T: 101010B
a tape with cells initialized
The grid
The grid is a two dimensional array of cells. It can initialized to a size. Cells can also be initialized to values.
[10,10]
a 10 by 10 grid
[10,10] (1,2,3)
a 10 by 10 grid with cell (1, 2) set to 3
Syntax
Tokens
Tokens in the language. Note that operations to initialize the gird and tape must precede the pointer.
| Token | Description |
|---|---|
| [x, y] | create an x by y grid |
| T: 1010B | a tape set to 1010B |
| (x, y, v) | set cell (x, y) to v |
| X() | an operation for the pointer, must be inside '{' and '}' |
| { | indicates where pointer operations begin |
| } | end program |
| < Live, genuine comment text! Amazing! > | a comment, anything between '<' and '>' is ignored. |
Pointer operations
There are 23 distinct operations that a program can execute. Operations can take up to two parameters. A parameter is always a nonnegative integer (hence, Blood32)
Each operation has two identifiers (called letts) so that if a key is out on a programmer's keyboard, they can still code operations in this language. Each operation is followed by a newline.
| Operation | Alternative | Description |
|---|---|---|
| D() | F() | writes a one or zero to the current cell randomly |
| E() | Q() | end program |
| A() | I() | ask for a boolean input from user and write it to current cell |
| C() | @() | output tape to console as an ASCII character |
| N() | M() | output tape to console as a decimal value |
| B() | V() | output tape as a binary value |
| H() | K() | output tape as a hex value |
| O() | P() | output tape as is |
| R(i) | #(i) | read value of current cell and write to location i on tape |
| G(l) | $(l) | go to label l in source. If there is no label l, go to start. |
| G() | $() | Goblins -- label -180339 -- goto the last goto executed, and continue to execute from the next line |
| T(i) | %(i) | jump to location i on the tape |
| T(+) | %(+) | increment to next cell on tape |
| T(-) | %(-) | decrement to previous cell on tape |
| W(v) | &(v) | write val v to current cell |
| J(x, y) | ^(x, y) | jump to cell (x, y) on grid, use + or - to increment and decrement |
| Y(l) | U(l) | Branch: Go to line l if the value of current cell is not zero |
| Z(l) | *(l) | Branch: Go to line l if the value of current cell is zero |
| L(l) | ?(l) | A label: identified by integer l. If there is no label l, go to first op. |
| X() | :() | reset tape to blank |
| S() | ~() | Show grid (Print each cell in the grid) |
| _(s) | !(s) | Add s millisecond delay to execution |
| _() | !() | Add one second delay to execution |
Grammar
The grammar for Blood32 as described in EBNF. See EBNF here.
program ::= grid, tape, pointer
grid := '[' Nz, Nz ']' {cellSet, newLine}
tape := "T:" {bool}, newLine
pointer := '{' {Op, newLine} '}'
Op := Lett '(' [Nz | Nz , Nz] ')'
cellSet := '(' Nz, Nz, Nz ')'
Nz := a nonnegative integer | '+' | '-'
newLine := ' \n '
bool := '0' | '1' | 'B'
Lett :=
'A' | 'B' | 'C' | 'D' | 'E' | 'F' | 'G' | 'H' | 'I' |
'J' | 'K' | 'L' | 'M' | 'N' | 'O' | 'P' | 'Q' | 'R' |
'S' | 'T' | 'U' | 'V' | 'W' | 'X' | 'Y' | 'Z' | '!' |
'@' | '#' | '$' | '%' | '&' | '^' | '*' | '?' | ':' |
'~' | '_'
Program Examples
These examples do not include blank lines, but blank lines can be added to a program for readability. It should also be noted that tape initializations cannot have newlines.
Hello World
See Hello World
<a grid of 0 cells>
[0,0]
<set tape to 'HELLO WORLD' with ASCII values in binary (reversed)>
T: 00100010B00110010B01001010B11110010B11101010B000001B11110010B00110010B00110010B10100010B0001001
<note that if the tape input is interrupted by a newline in this source, the newline should be ignored>
{
C()
}
Truth Machine
See Truth Machine
<This truth machine sets the leftmost cell randomly to 1 or 0. If 0, print a 0. If 1, print 1 endlessly>
<a one cell grid>
[1,1]
<tape is empty>
T:
{
<set leftmost cell to a random value 0 or 1>
D()
< start of a conditional statement >
Z(0)
Y(1)
<do zero case>
L(0)
R(0)
B()
E()
<do one case>
L(1)
R(0)
B()
<loop>
G(1)
}
Quine
See Quine
T: B1011111B0101B100101B000101B1100001B0101B100101B000101B1111001B0101B1101111B0101B1011101B000011B001101B000011B1101101
[0,0]
{
O()
C()
}
Logic Gates
see Logic Gates
<Logic Gates>
[2,1]
T:
{
O()
J(0,0)
A()
J(0,1)
A()
J(0,0)
G(4) <select gate>
<not gate>
L(2)
J(0,0)
Y(0)
*(1)
<and gate>
L(3)
J(0,0)
*(0)
J(0,1)
*(0)
Y(1)
<or gate>
L(4)
J(0,0)
Y(1)
J(0,1)
Y(1)
G(0)
<true>
L(1)
T(0)
W(1)
O()
E()
<false>
L(0)
T(0)
W(0)
O()
E()
}
Looping Counter
see Looping Counter
This program runs on an infinite number of cells in the tape and sets them to false (0).
<Fills the entire tape, after one eternity>
[0,0]
T:
{
T(0)
L(0)
T(+)
W(0)
_()
B()
G(0)
}
Tobysil
Tape Oriented Byte Sized Language is a restriction of Blood32 such that it has the fewest number of operations needed to be Turing complete. In other words it's a Turing tarpit.
Restrictions
- The grid is of size [0,0]
- The tape is initialized to blank
- The pointer is limited to O(), C(), L(l), T(i), W(v), and Z(l).
Permitted
- Alternates are permitted.
- ' + ' and ' - ' are permitted.
- Comments are permitted.
W() and T() are a serviceable substitute for initializing the tape
A modified version of the truth machine is possible (using cell 0 as the input). A hello world program is also possible. The quine, as described above, is not possible, as each operation to write to the tape would need to be written to the tape in a later operation.
If you find Blood32 is just not challenging enough, you can try this out. Good luck!
On the Turing Completeness of Blood32
Urban Müller's language (bf) is Turing complete. By translating each command in bf to Blood32, it can be shown that one language can be translated to other, which proves that Blood32 is also Turing complete. Routines to be implemented are identified in brackets.
To simulate a bf tape that accepts bytes at each cell a grid of [8, 30000] can be used
| Blood32 | bf | Desc |
|---|---|---|
| J(0, +) | > | increment |
| J(0, -) | < | decrement |
| [binary add] | + | add 1 to cell |
| [binary sub] | - | take 1 from cell |
| [read byte to tape and call C()] | . | Output ASCII value at cell |
| [call A() on each bit of byte] | , | Take input at cell |
| Z(x) | [ | Jump past ' ] ' (to label x) |
| Y(n) | ] | goto ' [ ' (label n) if cell is greater than 0 |
Implementing these routines in code would make for a stronger proof. That said, the logic gates program and looping counter provide substantial evidence this can be done, because such routines would be implemented via logic gates and a counter. Assuming the routines can be implemented, this language is translatable to bf. This makes Blood32 Turing Complete.
It can also be said that since Blood32 is designed to simulate a Turing Machine, it must be Turing complete by definition.