So. I like Brainfuck. I find the challenge of writing code in it fun / fascinating. And a few years ago, i figured out an "easy" way of writing code with it: using it like Forth, by using the tape like a stack.
The idea was as such: treat everything on the "left" of the current position as data; treat everything on the "right" as empty space that can be used for temporary computations and to which the stack can extend. This formalism makes it easier to reason about what's happening, and therefore easier to combine simple snippets into a bigger program. For instance, the following code doubles the current value at the top of the stack, in two steps:
duplicate the current value
[->+>+<<]>>[-<<+>>]<
add the current value to the previous one
[-<+>]<
The next step was to name those snippets: it's not possible to create actual functions and to jump to them, but it's possible to simply inline those snippets everywhere they are useful. The first approach was to use the C preprocessor:
#define CLEAR [-]
#define DUPC [->+>+<<]>>[-<<+>>]<
#define ADDC [-<+>]<
#define SWAPC [->+<] < [->+<] >> [-<<+>>] <
But, four years ago, i had a terrible idea. If I were to write a custom language, and a parser for it, i could translate more complex expressions than just simple snippets. For instance, given a snippet cond and a snippet body, it should be possible to express a while loop:
while (COND) {
BODY
}
can translate to
COND
[-<
BODY
COND
]<
Even better: we could typecheck functions. For instance, we could ensure that the condition of the while loop has a type that says "this snippet only adds one boolean to the stack", and we could ensure that the body of the loop doesn't touch the stack, allowing us to reason about the function as a whole.
And thus was born BFS. The language is ill-defined, the code is ugly, but it does exactly what it says on the tin: it translates bs files in bf. It even has its own Prelude, written in the language itself. This is what a fizzbuzz looks like in it:
const C upper_bound = 20
// is the byte at the top of the stack lower than the upper bound?
def inline below_upper_bound() [C] -> [C,B] {
lec_(upper_bound)
}
// checks whether the current byte can be divided by the given argument
// replaces the current byte with the result, converted back to byte
def can_be_divided_by(C n) [C] -> [C] {
pushc(n) swapc modc c_to_b not b_to_c
}
def main() {
pushc(1)
while (below_upper_bound) {
// [x]
dupc
dupc
// [x, x, x]
can_be_divided_by(3)
// [x, x, a], where a is 1 if x can be divided by 3, 0 otherwise
swapc
// [x, a, x]
can_be_divided_by(5)
// [x, a, b], where b is 1 if x can be divided by 5, 0 otherwise
pushc(2)
mulc
// [x, a, 2*b]
addc
// [x, a+2*b]
// the top value is 3 if both a and b are 1
if (eqc_(3)) {
prints("fizzbuzz!\n")
}
// the top value is 2 if b is 1
if (eqc_(2)) {
prints("buzz!\n")
}
// the top value is 1 if a is 1
if (eqc_(1)) {
prints("fizz!\n")
}
// otherwise
if (eqc_(0)) {
// bring x to the top and print it
swapc
printc_ord prints("\n")
swapc
}
popc
inc(1)
}
popc
}
it translates to the following brainfuck:
>+[->+>+<<]>>[<<+>>-]++++++++++++++++++++[<[->>+>+<<<]>>>[<<<+>>>-]<[[-]>+<]+>[<->-]<[<<+>[-]+>-]<-<
->]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-]<[[-]<[->+>+<<]>>[<<+>>-]<[->+>+<<]>>[<<+>>-]+++>[-]+[-<[->>+<<]
<[->+<]>>>[<<<+>>>-]<]<<[->>+>+<<<]>>>[<<<+>>>-]<<[->>+>+<<<]>>>[<<<+>>>-]<[<[->>+>+<<<]>>>[<<<+>>>-
]<[[-]>+<]+>[<->-]<[<<+>[-]+>-]<-<->]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-]<[-<<[->>+>+<<<]>>>[<<<+>>>-]<
[<->-]<<[->>+>+<<<]>>>[<<<+>>>-]<<[->>+>+<<<]>>>[<<<+>>>-]<[<[->>+>+<<<]>>>[<<<+>>>-]<[[-]>+<]+>[<->
-]<[<<+>[-]+>-]<-<->]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-]<]<<[-]>[<+>-]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-
]+[-<[->>+<<]<[->+<]>>>[<<<+>>>-]<]+++++>[-]+[-<[->>+<<]<[->+<]>>>[<<<+>>>-]<]<<[->>+>+<<<]>>>[<<<+>
>>-]<<[->>+>+<<<]>>>[<<<+>>>-]<[<[->>+>+<<<]>>>[<<<+>>>-]<[[-]>+<]+>[<->-]<[<<+>[-]+>-]<-<->]<[[-]>+
<]>[<+>-]<[[-]>+<]+>[<->-]<[-<<[->>+>+<<<]>>>[<<<+>>>-]<[<->-]<<[->>+>+<<<]>>>[<<<+>>>-]<<[->>+>+<<<
]>>>[<<<+>>>-]<[<[->>+>+<<<]>>>[<<<+>>>-]<[[-]>+<]+>[<->-]<[<<+>[-]+>-]<-<->]<[[-]>+<]>[<+>-]<[[-]>+
<]+>[<->-]<]<<[-]>[<+>-]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-]++<[->>+<<]>[->[->+<]>[<<<+>>+>-]<<]>[-]<<[
<+>-]<[->+>+<<]>>[<<+>>-]+++<[->-<]>[<+>-]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-]<[[-]++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++.+++++++++++++
++++..------------------------.+++++++++++++++++++.+++++..[-]+++++++++++++++++++++++++++++++++.[-]++
++++++++.[-]]<[->+>+<<]>>[<<+>>-]++<[->-<]>[<+>-]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-]<[[-]+++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++++++
+++++.+++++..[-]+++++++++++++++++++++++++++++++++.[-]++++++++++.[-]]<[->+>+<<]>>[<<+>>-]+<[->-<]>[<+
>-]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-]<[[-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++.+++.+++++++++++++++++..[-]++++++++++++++++++++++++++++++
+++.[-]++++++++++.[-]]<[->+>+<<]>>[<<+>>-]<[->-<]>[<+>-]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-]<[[-]+[-<[-
>>+<<]<[->+<]>>>[<<<+>>>-]<]<[->+>+<<]>>[<<+>>-]<[->+>+<<]>>[<<+>>-]<[->+>+<<]>>[<<+>>-]++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>[-]+[-<[->>
+<<]<[->+<]>>>[<<<+>>>-]<]>[-]+[-<[->>+<<]<[->+<]<[->+<]>>>>[<<<<+>>>>-]<]<<[->>+>+<<<]>>>[<<<+>>>-]
<<[->>+>+<<<]>>>[<<<+>>>-]<[<[->>+>+<<<]>>>[<<<+>>>-]<[[-]>+<]+>[<->-]<[<<+>[-]+>-]<-<->]<[[-]>+<]>[
<+>-]<[[-]>+<]+>[<->-]<[-<<<+>[->>+>+<<<]>>>[<<<+>>>-]<[<->-]<<[->>+>+<<<]>>>[<<<+>>>-]<<[->>+>+<<<]
>>>[<<<+>>>-]<[<[->>+>+<<<]>>>[<<<+>>>-]<[[-]>+<]+>[<->-]<[<<+>[-]+>-]<-<->]<[[-]>+<]>[<+>-]<[[-]>+<
]+>[<->-]<]<[-]<[-]+[-<[->>+<<]<[->+<]<[->+<]>>>>[<<<<+>>>>-]<]+++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>[-]+[-<[->>+<<]<[->+<]>>>[<<<+>>>-]<
]<<[->>+>+<<<]>>>[<<<+>>>-]<<[->>+>+<<<]>>>[<<<+>>>-]<[<[->>+>+<<<]>>>[<<<+>>>-]<[[-]>+<]+>[<->-]<[<
<+>[-]+>-]<-<->]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-]<[-<<[->>+>+<<<]>>>[<<<+>>>-]<[<->-]<<[->>+>+<<<]>>
>[<<<+>>>-]<<[->>+>+<<<]>>>[<<<+>>>-]<[<[->>+>+<<<]>>>[<<<+>>>-]<[[-]>+<]+>[<->-]<[<<+>[-]+>-]<-<->]
<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-]<]<<[-]>[<+>-]++++++++++>[-]+[-<[->>+<<]<[->+<]>>>[<<<+>>>-]<]>[-]+
[-<[->>+<<]<[->+<]<[->+<]>>>>[<<<<+>>>>-]<]<<[->>+>+<<<]>>>[<<<+>>>-]<<[->>+>+<<<]>>>[<<<+>>>-]<[<[-
>>+>+<<<]>>>[<<<+>>>-]<[[-]>+<]+>[<->-]<[<<+>[-]+>-]<-<->]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-]<[-<<<+>[
->>+>+<<<]>>>[<<<+>>>-]<[<->-]<<[->>+>+<<<]>>>[<<<+>>>-]<<[->>+>+<<<]>>>[<<<+>>>-]<[<[->>+>+<<<]>>>[
<<<+>>>-]<[[-]>+<]+>[<->-]<[<<+>[-]+>-]<-<->]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->-]<]<[-]<[-]+[-<[->>+<<]
<[->+<]>>>[<<<+>>>-]<]++++++++++>[-]+[-<[->>+<<]<[->+<]>>>[<<<+>>>-]<]<<[->>+>+<<<]>>>[<<<+>>>-]<<[-
>>+>+<<<]>>>[<<<+>>>-]<[<[->>+>+<<<]>>>[<<<+>>>-]<[[-]>+<]+>[<->-]<[<<+>[-]+>-]<-<->]<[[-]>+<]>[<+>-
]<[[-]>+<]+>[<->-]<[-<<[->>+>+<<<]>>>[<<<+>>>-]<[<->-]<<[->>+>+<<<]>>>[<<<+>>>-]<<[->>+>+<<<]>>>[<<<
+>>>-]<[<[->>+>+<<<]>>>[<<<+>>>-]<[[-]>+<]+>[<->-]<[<<+>[-]+>-]<-<->]<[[-]>+<]>[<+>-]<[[-]>+<]+>[<->
-]<]<<[-]>[<+>-]<<<[++++++++++++++++++++++++++++++++++++++++++++++++.[-]>+++++++++++++++++++++++++++
+++++++++++++++++++++.[-]<]>[++++++++++++++++++++++++++++++++++++++++++++++++.[-]]>+++++++++++++++++
+++++++++++++++++++++++++++++++.[-]<<[-]++++++++++.[-]+[-<[->>+<<]<[->+<]>>>[<<<+>>>-]<]]<[-]<+[->+>
+<<]>>[<<+>>-]++++++++++++++++++++[<[->>+>+<<<]>>>[<<<+>>>-]<[[-]>+<]+>[<->-]<[<<+>[-]+>-]<-<->]<[[-
]>+<]>[<+>-]<[[-]>+<]+>[<->-]<]
As often: by combining very basic bricks, we end up creating something absurdly complex. 😺
Which, finally, brings us to the Advent of Code. The reason why BFS' Prelude has support for Int32 operations in the first place is because i tried solving day one of the advent of code a few years ago, and realized that the values would not fit into a single byte.
This year, i went back to it, and realized that i wasn't missing much: the basic loop of iterating and detecting newlines, while not trivial, didn't require anything that wasn't already in the language. What was missing was just the ability to compare the integers to find the maximum one. It turns out that it could be done... without directly writing any Brainfuck:
// consumes two 32-bit integer, pushes true if the one on top of the stack
// is strictly smaller than the second one, pushes false otherwise
def impure lti() [I,I] -> [B] {
// do A - B, popping the top int
subi
// drop three bytes, keeping only the most significant
popc popc popc
// check that the sign bit is set / that we did an underflow
pushc(128) lec
}
def inline maxi() [I,I] -> [I] {
// if the first integer is greater than the second one, swap them
if (dupi2 gti) {
swapi
}
// drop the top one
popi
}
Hence this piece of code for part 1.
For part 2, the problem was sorting values. BFS has currently no support for anything not on the stack, like having a heap, and random access in it (i've thought about it, but it would be a nightmare to implement). As a result... I've implemented a bubble sort in partially pure Brainfuck. :3
The trick is that we rely on the fact that no group has a sum of 0, and we use a 0 integer as a signal value to indicate the end of the list. To implement a bubble sort, we move the lower value below the zero, go back to the top, and continue so until the 0 is on the top. This is extremely ad-hoc, and requires some manual memory accounting: while traversing the list to bring the lowest item to the beginning, we have to move every value 12 bytes to the right to ensure we have a large enough buffer to operate.
// while there's still values in the list
while(nei_(0)) {
// traverse right to left until we encounter the 0
while(nei_(0)) {
// move the smaller item to the left
// this requires ~10 free bytes on the right
dupi2 lti [- < swapi >] <
// move the bigger one far away to free some local buffer
[->>>>>>>>>>>>+<<<<<<<<<<<<]<
[->>>>>>>>>>>>+<<<<<<<<<<<<]<
[->>>>>>>>>>>>+<<<<<<<<<<<<]<
[->>>>>>>>>>>>+<<<<<<<<<<<<]<
}
// we've reached the end, copy the lowest element back
>>>>>>>>>>>>
> [-<<<<<<<<<<<<+>>>>>>>>>>>>]
> [-<<<<<<<<<<<<+>>>>>>>>>>>>]
> [-<<<<<<<<<<<<+>>>>>>>>>>>>]
> [-<<<<<<<<<<<<+>>>>>>>>>>>>]
<<<<<<<<<<<<
// and put it behind the 0, so that it's "out"
swapi
// copy everything back: since we're on a 0, we don't use a while,
// we force the first iteration of the loop.
>+
[-<
>>>>>>>>>>>>
> [-<<<<<<<<<<<<+>>>>>>>>>>>>]
> [-<<<<<<<<<<<<+>>>>>>>>>>>>]
> [-<<<<<<<<<<<<+>>>>>>>>>>>>]
> [-<<<<<<<<<<<<+>>>>>>>>>>>>]
<<<<<<<<<<<<
nei_(0)
]
// move back to the last item of the list
<<<<<
}
// we're done and on the 0, move back to the list
<<<<
And that's it! Here's the code for part 2.
I am not entirely sure where i was going with this... i hope this was somewhat interesting? And maybe it'll motivate others to play with Brainfuck? 😺
