User:20kdc/HypotheticalBrainfuckToByteByteJump
Description
To be clear, this is here so I don't clutter up the Talk:ByteByteJump page.
This is a summary of how Brainfuck operations map to ByteByteJump operations.
Inspiration from the work of User:zzo38 and User:JulienDelplanque, who are already using the techniques described here (see BytePusher).
The Tape
The tape in a ByteByteJump machine, assuming no I/O to an external tape (which then makes the resulting machine Turing-complete), must be a bounded array. A reasonable mechanism for this is a cyclic tape, with the position in it being made up of addressSize - 1 bytes, and the tape covering all of the possible values of that index.
I/O
, and . are machine-specific operations. For computational complexity reasons it suffices to say that, say, 0xFFFFFF(...) is an input/output port with the exact same semantics as these operations in Brainfuck - this could be replaced with any other input/output mechanism, and there have been proofs that require no such direct input/output mechanism, it just makes this cleaner.
Operations
+ and - just do a bunch of indirect accesses. An indirect access is done through self-modification:
000000: INDEX 00000B 000009
00000B v
000009: PAGE[00] TARGET (...)
Here, 000000 modifies the third byte of 000009's source address, which otherwise points at PAGE. This allows various parts of PAGE to be read by changing INDEX. This technique can be expanded to however many bytes need to be changed.
To actually allow the pointer to be more than one byte, conditional branches must be used - see the next point.
[ and ] should be replaced with conditional branches as with any compiled variant of Brainfuck. How these works in practice is more self-modification.
My personal favorite construction is four addresses, in the order FALSE, FALSE, FALSE, TRUE. Jumping to the first address copies the byte at FALSE to FALSE (a NOP) and jumps to FALSE. Jumping to the second address performs the same copy, but jumps to TRUE. Placing this construction at the end of a page (this is hypothetically better for allocation than at the start) creates a standardized way of creating these, that can then reuse the same conditional branch pages. In a 3-address-byte system such as BytePusher, the boolean values (false and true respectively) are 0xF4 and 0xF7.
For [ and ], the only requirements here are that there is a page of jump values where index 0 is true, and all remaining values are false.
< and > combine the indirect accesses of + and - and the conditional branching to allow having more than 256 cells. The same "is X 0" page used for [ and ]'s implementation works just as well for carrying - < when the lowest pointer byte is 0 borrows, > causing the lowest pointer byte to be 0 carries.
Conclusion
Once the techniques are understood, writing an inefficient but usable converter from Brainfuck to ByteByteJump on the hypothetical test system should be pretty much trivial.
A Much Less Hypothetical Implementation
An implementation of this for arbitrary Brainfuck code (with "!" as a separator) is at: https://20kdc.duckdns.org/bf-bbj24be.bin
It's quite slow, but it works and proves the point.
Source for that is at: https://gitlab.com/20kdc/nim-bbjof/-/tree/master/examples/ts24-brainfuck
C source for an emulator for the required ByteByteJump environment is at: https://20kdc.duckdns.org/bbjts24be.c