# Programming Exercise 1: Brainfuck-Interpreter ## Implementation Write an efficient interpreter for Brainfuck with 8-bit cells by compiling Brainfuck to bytecode. Unmatched brackets are valid as long as the branch is never taken. You can define your bytecode as you like, but focus on efficient generation, optimization, and interpretation. Combine instruction sequences (both sequences of identical operations and loop patterns) and implement at least one of the following optimizations: - Superinstructions/combined execution of multiple neighboring instructions - Threaded interpretation There is no strict limitation on the programming language, but it has to compile to machine code, should be human-readable, have minimal dependencies besides compiler and standard library, and *must* include a command to compile and run the program on Linux at the beginning. ## Analysis (write answers as comment in your code) Find suitably large and complex code examples to test the correctness and performance of your submission and document the results. Compare the compile-time and the run-time -- at what point are the optimizations worth the effort? How can more advanced optimizations be implemented? Why is this difficult? Give one Brainfuck code example and explain which optimization could lead to better bytecode. # Submission Send an e-mail to engelke+cghomework@in.tum.de until 2022-10-26, 23:59 with: - Subject: "Homework 1: YourMatrNr YourName" - A single(!) .tar.xz file attached named with "hw1-YourMatrNr-YourLastName.tar.xz", which contains a single folder "hw1-YourMatrNr-YourLastName", which contains your submission - The message body can remain empty - Include a Makefile with compilation directives s.t. `make` compiles the code - Avoid external dependencies and complex build systems (no cmake, cargo, etc.) - Put the source in a single source file - Include answers to theory questions as comments in the source file