Standalone

Brainfuck VM

Part I

Brainfuck Programs

Download quests in Questplay

Can Starknet support languages other than Cairo? The short answer: yes. The more convoluted explanation lies in the challenge ahead...

Brainfuck Language

In 1993, Physics student Urban Müller set out to create the smallest compiler for a Turing-complete language. The result was Brainfuck, a stupidly minimal language that is celebrated by the developer community to this day.

Brainfuck is an esoteric language. It is not designed to be usable or practical. Rather, it merely serves as a fun proof-of-concept!

A Brainfuck computer has a ticker tape-like memory; an array of cells and a data pointer that can read and write on individual cells.

The machine supports 8 simple instructions. If you are unfamiliar with them, here is a 2-minute masterclass .

Instruction	Description
`>`	Move the pointer to the right
`<`	Move the pointer to the left
`+`	Increment the memory cell at the pointer
`-`	Decrement the memory cell at the pointer
`.`	Output the character signified by the cell at the pointer
`,`	Input a character and write it onto the cell at the pointer
`[`	Jump to the matching `]` if the cell at the pointer is 0
`]`	Jump back to the matching `[` if the cell at the pointer is non-zero

Brainfuck in Cairo

The mission is simple: we want to implement a Brainfuck machine in Cairo. A Brainfuck program can be represented as an array of short strings (i.e., Array<felt252>).

// Hello World program
[
    '++++++++[>++++[>++>+++>+++>+<<<',
    '<-]>+>+>->>+[<]<-]>>.>---.+++++',
    '++..+++.>>.<-.<.+++.------.----',
    '----.>>+.'
]

We want our BF programs to support two methods, check and execute.

trait ProgramTrait {
    fn check(self: @Array<felt252>);
    fn execute(self: @Array<felt252>, input: Array<u8>) -> Array<u8>;
}

check reverts if the program has invalid syntax. It reverts if the program has a non-instruction character, or when the brackets [ and ] are imbalanced.
execute runs self with the given input and returns the appropriate output.

Here are some important constraints:

The program only needs to support a memory of size 256 cells. > and < should wrap around the edges of the memory.
Each cell can hold a value between 0 and 255. + and - should overflow/underflow silently.
You are allowed to use logic/utils.cairo to hold any helper classes/functions you might need.

Your Task

In src/logic/program.cairo, implement ProgramTrait. Remember to respect the specified constraints.

Run tests in Questplay

The language on the tablets is deceptively simple. The problem is you’ve been overcomplicating the translation process…