While Selfcompiler

This project is the result of my bachelor’s thesis together with Luca Marceca, which explored the Turing completeness of the theoretical programming language While. The source code and the compiled self-compiler are available under the MIT license. Additionally, a web app was built to make the self-compiler usable directly in the browser, completely client-sided.

While

While is a very simple programming language mainly used for theoretical demonstrations in the context of computability and Turing completeness. It only has operations for addition, subtraction, and while-loops. The only data type it supports is bigint. Here is an example of code for computing a Fibonacci number within the created web app:

Benchmarks

For basic arithmetic operations, the performance of the resulting self-compiler is close to that of native x86 C using the GMP library.

Fun Facts

Let’s finish with some fun facts about this project:

• The resulting While code for the self-compiler is 100,000 instructions long.
• It takes about 14 minutes to compile the self-compiler with itself on a modern system.