Brainfuck Assembly Language

Brainfuck Assembly Language

Paradigm(s)	imperative
Designed by	User:Olus2000
Appeared in	2020
Memory system	Cell-based
Dimensions	one-dimensional
Computational class	Turing complete
Major implementations	PICO-8
Influenced by	Brainfuck
File extension(s)	.p8 .bal

Brainfuck Assembly Language (BAL) is an assembly language for a theoretically possible Brainfuck Processing Unit (BPU). It is meant to make hardware implementation of brainfuck easier for amateurs, especially on common 8-bit and multiple-of-8-bit components. It translates one-to-one to machine code.

Language Overview

BAL running machines operate directly on RAM (base specification is 256B), initialised to zeros and with the program loaded at the beginning of the memory. The RAM both serves as a brainfuck memory array and contains the executable code which means the program may modify itself during execution. It uses two registers: IP (Instruction Pointer) and DP (Data Pointer) to access memory which are also initialised at 0. Instruction set is the same as in brainfuck, but now each instruction takes a single integer argument written directly after the command which defaults to 0. The new commands are:

Command	Description	Compiles to
+n	Add n to the memory cell at the data pointer	0b000(n - 1)
-n	Subtract n from the memory cell at the data pointer	0b001(n - 1)
>n	Add n to the data pointer	0b010(n - 1)
<n	Subtract n from the data pointer	0b011(n - 1)
[n	Add n to the instruction pointer if the cell at the data pointer is 0	0b100(n - 1)
]n	Subtract n from the instruction pointer if the cell at the data pointer is non-zero	0b101(n - 1)
,n	Input a character and store it in the cell at the pointer. n is passed as additional info to the peripherals.	0b110n
.n	Output the character signified by the cell at the pointer. n is passed as additional info to the peripherals.	0b111n
n	(Non-standard) A literal value to be inserted into the executable. Will be interpreted as one of the above when executed.	n

If a command is written without an argument an implicit argument is applied to it: 1 for +-><[], and 0 for ,.. This will result in setting argument bits to 0 in compilation. Any addition and subtraction is subject to wrapping caused by overflow which is considered a feature of BAL and BPUs. Anything outside the listed commands and their arguments should be treated as a comment.

Concept

The idea behind BAL is that the fact that brainfuck has only eight commands which can be represented by 3-bit numbers doesn't fit very well with any multiple-of-8-bit architecture. Using one byte per command is very suboptimal, wasting five out of every eight bits. Another way was to fit two into each byte, wasting only two out of every eight bits, but made jumps awkward to implement in hardware. Yet another idea for improvement was to encode them in a one-hot byte which simplifies hardware implementation and opens a possibility for merging commands. None of those solutions answered the problems of the enormous sizes of brainfuck programs (which makes them hard to fit into cheap RAM chips), hardware implementation of jumping to matching parenthesis or communication with peripherals.

The final concept compiles each command into top three bits, leaving five (or however many your architecture allows) for the argument which usually represents how many times the command should be repeated and allows for exchanging additional information with peripherals making it the superior extension for brainfuck when considering hardware implementation.

Implementations

Specification of BAL leave a lot of room to make very different systems, although the author gives some values the language was designed with in mind. Things that are left for the hardware designer to decide include memory word size (proposed 8-bit), memory size (proposed 256B, addressable in 8 bits) and meaning of arguments passed to , and .. Here are some implementations and their values and instructions:

PICO-8

General info
Author	User:Olus2000
Word size	8-bit
Memory size	4kiB
, arguments
0 - 30	Take the bitfield of the 6 button states for player n % 8 as input
31	Take a random byte as input
. arguments
0	Halt
4	Set cursor X to output value
5	Set cursor Y to output value
6	Add output value to cursor X
7	Add output value to cursor Y
8	Set pixel color at cursor to n % 16
9	Update the screen and wait for the next frame
other	No-op

If you make an implementation please insert it's specification here in a similar table.

Computational class

Similar to brainfuck given unbounded word size or memory size BAL is Turing complete. This can be easily proven because simulating brainfuck in BAL is trivial and brainfuck is Turing complete in these cases.

Ternary variation

As we are approaching the end of the Moore's Law some people talk about switching to a ternary system for computing. Main advantage of base three is its minimal radix economy among integer bases and a natural representation of negative numbers if using the balanced variant. As it turns out BAL converts cleanly into balanced ternary by merging symmetrical operations (+ and -, > and <, [ and ]) and making use of naturally occurring negative numbers for command arguments.

The table uses following symbols: + - ternary value 1, 0 - ternary value 0, - - ternary value -1, n - argument supplied to the command, ~n - ternary negation of the argument supplied to the command. As normal the argument is truncated or padded with zeros to fill the part of the trite not used by the command.

Command	Description	Compiles to
+n/-n	Add n/~n to the memory cell at the data pointer	00n/00~n
>n/<n	Add n/~n to the data pointer	0+n/0+~n
[n/]n	Add n/~n to the instruction pointer if the cell at the data pointer is not 0	0-n/0-~n
,n	Input a character and store it in the cell at the pointer. n is passed as additional info to the peripherals.	-n
.n	Output the character signified by the cell at the pointer. n is passed as additional info to the peripherals.	+n
n	(Non-standard) A literal value to be inserted into the executable. Will be interpreted as one of the above when executed.	n

The main drawback of this approach is that it lacks the "jump if zero" command, but it can be constructed using the "jump if not zero" and concious memory management.

External resources

• PICO-8 implementation of a BPU listed above