Blood32

From Esolang
Jump to navigation Jump to search
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
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:

Cell States
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.

Tokens
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.

Operations Table
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 op -- 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)
}

The Goblins Operation

The Goblins Operation is an modified goto operation that enables subroutine like behaviors. The operation is named after the hemoglobin in blood, and it is a goto statement that goes to the instruction immediately after the last executed goto statement. In this language there are no stacks, return statements, or recursive behaviors. However, this operation allows for a block of statements to be run at multiple points in a programs execution, as if calling a subroutine or a macro. As the name suggests, this operation can have unpredictable side effects if a block starts running at an unintended time.

As indicated in Pointer Operations, the Goblins Operation is written as G() and runs at the label -180339. So G() and G(-180339) are equivalent. The label -180339 is used for this operation because it minimizes the chances of side effects. (It is unlikely a programmer would use this label with a goto operation or a branch because is is six digits long, negative, and its significant digit is not 5 or 0.) The label is taken from the digits of phi Φ which has a value of 1.6180339...

This operation is counterintuitive, so an example program is included here:

Goblins Operation Example

[0,0]
T: 1000001
{
<ascii value A, decimal 65, hex 41>
G(3)
G(1)
G(2)
G(3)
E()
<note that if the exit operation is removed, Label 1 is executed, then Label 3, in a loop>
<block one>
L(1)
C()
G()
<block two>
L(2)
N()
G()
<block three>
L(3)
H()
G()
}
<
Note that block 3 is run twice, at the beginning and end of the program. 
Without the goblins operation, this would require two nearly identical blocks
that are distinguished only by labels and goto operations.
The expected output is as follows:
41
A
65
41
>

Pointer Behaviors

A behavior refers to how a pointer moves. There are many behaviors a pointer can have; so it is good to have a way to name them.

EGG

  • a pointer acting on the X axis or on a line parallel to it

SEED

  • a pointer acting on the Y axis or on a line parallel to it

SPORE

  • a pointer on the tape

TURING MACHINE

  • a pointer that runs a Turing machine on an axis or on a line parallel to an axis

TURING EGG

  • a Turing machine on the X axis

TURING SEED

  • a Turing machine on the Y axis

TURING SPORE

  • a pointer that runs a Turing machine on the tape

SCRIBE

  • a pointer that writes to the tape and prints to console

ERASER

  • writes blank to any cell it finds

HONEST

  • writes one to any cell it finds

DISHONEST

  • writes zero to any cell it finds

INVERTER

  • inverts the truth value of any non blank cell

SWITCH

  • periodically inverts a cell

PATROL

  • an eraser that moves along an axis

AUTO

  • a pointer that runs a cellular automaton. There can be many more kinds than listed here.

LIFE

  • runs the game of life

ANT

  • runs Langton's Ant

RULE 110

  • runs rule 110

BISHOP

  • moves only diagonally

TRUTTLE

  • a pointer that executes a G(l) operation for a line l in the source code.

ARTIST

  • draws lines or shapes on the grid

RECTANGLE

  • draws a rectangle

SQAURE

  • draws a square

ELLIPSE

  • draws an ellipse

CIRCLE

  • draws an circle

TRIANGLE

  • draws a triangle

ARC

  • draws an arc

RASCAL

  • erratically changes cells on the tape

DEMON

  • an eraser that jumps around erratically

BOUNCE

  • bounces around in parabolic arcs, like a ball

FLUID

  • changes between the behaviors listed above. Various subtypes can be described: ARTIST FLUID, AUTO FLUID, TURING FLUID

ANGEL

  • a fluid that changes behaviors erratically. Subtypes include ARTIST ANGEL, AUTO ANGEL, TURING ANGEL

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

see Turing Completeness

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

Conversion Table
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.

External resources

Download Blood32 Interpreter (Java)

Source and Docs