I want to share my friend's crazy project because it demonstrates how a simple Turing-machine-like programming language is actually equivalent to usual real-world computers.
I think we all know the theory that all Turing complete programming languages are equivalent in terms of their powers. If languages A and B are Turing complete, A can emulate B and vice versa. But that's not obvious at all. How can a simple programming model like Turing Machine can run "real" programs such as ones that run on a general-purpose PC? If it is possible in theory, it can be demonstrated.
Recently, my friend, Shinichiro Hamaji, who is the winner of ICFP Programming Contest '09 and a winner of IOCCC 2011, wanted to implement a Lisp in Brainfuck (don't ask me what's the motivation behind it — I'd guess the answer is just "because I can"). He did that before in sed, makefile and Befunge.
Brainfuck is more primitive language than those. It is a Turing-machine-like language; you have an infinitely long tape and a tape head that can move to the left or to the right. You can only read or write a cell where the tape head is currently at, and except the tape, you have no memory.
This is a program to print out "Hello world" in Brainfuck.
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.
As you can see, it is extremely hard to write code in Brainfuck. Even if you can write a simple one like a "hello world", it is impossible to implement a Lisp in Brainfuck. It is way beyond human abilities. So he took a different approach. He first implemented an emulator for a hypothetical computer, or a virtual machine, using Brainfuck. The virtual machine is a simplified version of real-world computers, so it gives us a nice layer on top of raw Brainfuck to run ordinary programs. The virtual machine has a random-access memory instead of a sequential tape, six 16-bit registers (two of them are for the stack pointer and the base pointer), a few arithmetic instructions (such as ADD, SUB, etc), memory load/store instructions, and a few jump instructions (such as JMP or JE).
Then he retargeted 8cc C compiler which I wrote a few years ago in my spare time to the virtual machine. Now we have a compiler for the virtual machine. Implementing a Lisp in C was an easy part compare to everything else. Here is the source code of the interpreter.
So, we now have the virtual machine written in Brainfuck, the C compiler written in C which compiles C programs into the virtual machine instructions, the Lisp interpreter written in C, and a few Lisp programs that runs on the Lisp interpreter. Theoretically, when you combine all of them, you can run the Lisp programs on Brainfuck.
What's the result? It actually worked! The compiled Lisp interpreter in Brainfuck is huge and unreadable to human, but when it runs on a Brainfuck interpreter, it can correctly interpret Lisp programs. We know that in theory Brainfuck is as powerful as general-purpose programming languages, and we understand how the conversion works (because I partly created it). However, it still feels really magical to me that C programs can be converted to Brainfuck. They look so different... but as the theory tells us, they are actually the same in their expressiveness whether you believe it or not. He demonstrated that. It is truly astonishing.
There are currently a few technical problems in compiling large C programs, but theoretically it is possible to self-host the C compiler on Brainfuck when the retargeting is complete. Once it's done, we port our "tool chain" to Brainfuck. That would be very cool.
Here is the link to the project. https://github.com/shinh/bflisp