Brainfuck is one of my favourite languages. Not that I _write_ any code in it, mind you, but there's a bunch of code out there written for it (thank you, you crazy people), and it's so tiny and so simple that you can write an interpreter for it in an hour or two.
Because the syntax is so minimal, there's little point for a naive interpreter to include a parser and you can write it directly as a bytecode interpreter (and my experience has been that most beginners will do exactly that on their first attempt).
However, if you _do_ decide to write a (really basic) parser for it, you can easily end up with a tree walking interpreter instead, and, from there, it's only a tiny jump to start manipulating the AST. E.g. the simplest change you can make is to do away with the separate Increment and Decrement instructions, and replace them with a generic Add instruction, so + and - get parsed as Add 1 and Add -1 respectively. Then you can replace runs of mixed - and + characters as one single Add instruction (--+-+++ becomes Add 1, for example). If you add a Set instruction, the [-] sequence can be translated to Set 0. Likewise, [.>] can become printf(ptr) instead of a loop of putchar(*ptr).
Put all of this together, and it turns out that BF is perfect to introduce people to interpreters, and to demistify the whole "writing a language" thing.
It's quite fun to write a bf->c "compiler" and look at the assembly output that results from compiling that c. The result can be remarkably efficient; GCC will trivially reduce a double-loop of incrementation down to a single multiply instruction for example, it will optimize away pointer manipulation and just use registers, etc.
You are Reading the Name of this Esolang[1] is my favorite of the Brainfuck derivative esolangs.
It consists of "0" and "1" characters which map to Brainfuck symbols via a Huffman encoding as well as brackets which wrap a subprogram which are reduced to "1" if the subprogram halts and "0" if the subprogram loops forever. This means that the problem of deciding whether a given string is a valid You are Reading the Name of this Esolang program is undecidable.
This is one of the most hilarious things I've ever read:
> Pronunciation of You are Reading the Name of this Esolang: The name of the language is pronounced as an English speaker would pronounce "you are hearing the name of this esolang."
Ever since I learned about Brainfuck myself (which I obviously couldn't believe at first that it's an actual thing), I keep peeping at esolangs.org to find some bizarre creations of (often) very bored programmers.
30 years?! Wow, the first time I ever heard of it was 15 years ago. And even then I thought it was some weird university group project that gained internet infamy.
Brainfuck makes it very easy to benchmark various optimizations that you can do to its interpreter.[0] Rendering a Mandelbrot set goes from 28.57 to 6.49 seconds with basic preprocessing!
The Mathematisch Centrum/CWI is responsible not only for incubating Python but for other computing antics, most memorably https://godfatherof.nl/kremvax.html (something Sir Piet* neglects to mention is that in 1984 all US<->Europe usenet traffic went by way of mcvax, so as far as metadata was concerned, the forgery was perfect when seen from the US side!)
* De hoogwelgeboren heer Piet ridder Beertema as he is now?
Quine relay [1] is to this day the most "I will never understand this" brainfuck project I have ever seen.
> This is a Ruby program that generates Rust program that generates Scala program that generates ...(through 128 languages in total, including brainfuck!)... REXX program that generates the original Ruby code again.
It is so mysterious how it's even possible, and hilariously the explanation of how it was made exists in Japanese only. I think at this point it would be easier to learn Japanese than to try to understand this project.
Other things like a brainfuck interpreter in brainfuck are impressive but don't come nearly as close to black magic as quine-relay.
BF loops necessarily need to use more space. How do you determine which cell is free to overwrite? It is often non-trivial because BF data structures are very sensitive to exact strides (e.g. only works when the data pointer is at 5n+4).
Because the syntax is so minimal, there's little point for a naive interpreter to include a parser and you can write it directly as a bytecode interpreter (and my experience has been that most beginners will do exactly that on their first attempt).
However, if you _do_ decide to write a (really basic) parser for it, you can easily end up with a tree walking interpreter instead, and, from there, it's only a tiny jump to start manipulating the AST. E.g. the simplest change you can make is to do away with the separate Increment and Decrement instructions, and replace them with a generic Add instruction, so + and - get parsed as Add 1 and Add -1 respectively. Then you can replace runs of mixed - and + characters as one single Add instruction (--+-+++ becomes Add 1, for example). If you add a Set instruction, the [-] sequence can be translated to Set 0. Likewise, [.>] can become printf(ptr) instead of a loop of putchar(*ptr).
Put all of this together, and it turns out that BF is perfect to introduce people to interpreters, and to demistify the whole "writing a language" thing.