Urban Müller/Tamedia TX 2017 Transcript

Urban Müller: So, hello everyone, my name is Urban Müller, I work at search.ch, and, uh, I'm going to hold probably the most useless talk of this whole conference.

I'm going to talk about the language brainfuck that I invented, or how I learned to change the problem.

Back in 1993, I was doing the moderation of the largest Amiga software archive, and somebody uploaded a pretty weird program. It was called "FALSE", a newly invented programming language, which was designed to be small, to be, create a small compiler for.

It had about 30 commands, a pretty classical stack machine, you could put integers on top of the stack, you could drop elements from the stack, duplicate elements from the stack, and you could do arithmetic. For example, multiplications. It also had simple I/O, like writing the current stack element as an ASCII character to standard out.

The surprising thing was, even back then, the size of the compiler, which was 1024 bytes, was ridiculously small.

My first reaction when I encountered this program - hmmm. Can we do better? And, improving on the size of the compiler for that language would have been pretty hard. I don't like hard. I like to make my life easy. And this is probably the only semi-useful, uh, idea in this talk: if the program doesn't fit the problem, change the problem.

In this case, this meant: let's get rid of operators. All operators can be expressed as increments by 1. So, we just have the +1, nothing else. Of course, -1 we need as well. All numbers can be expressed by increments from 0. All variables can be expressed by places on the stack - in my case, of tape - because you can move around, not only right, to the top. And the lambda calculus, which was present in, uh, the FALSE language for loop construct, I replaced by simpler while construct.

This resulted in the following language. I don't know how many of you know it, but I'm going to quickly pace through it in case you don't.

The language had 8 instructions: two instructions for moving the pointer on the tape, to the right and to the left; two instructions for incrementing the value at the pointer position by 1, or decrease it by 1; two instructions for writing a byte, or reading a byte from standard in, standard out; and finally, two instructions for creating a while loop. Which, all those elements are easily translatable to the C programming language.

Cmd	C	Description
>	p++;	Move pointer one to the right
<	p--;	Move pointer one to the left
+	++*p;	Increment data at the pointer
-	--*p;	Decrement data at the pointer
.	putchar(*p);	Output data at pointer to stdout
,	*p=getchar();	Read stdin and store one byte at pointer
[	while(*p) {	Iterate while data at the pointer is nonzero
]	}	End of iteration block

Brainfuck source code looks like this - hope you can read it from the back, um - two numbers, adding two numbers means you repeat: moving one right, incrementing that cell, move back, decrement that cell, and, when this cell becomes 0, you've got the sum in the cell to the right. So in the end, you have to move one to the right, because that's where the sum is.

[>+<-]>

Multiplying two numbers is a little bit more complicated - all reads of a number are destructive. Once you've read a number in a while loop, it's gone. So what you have to do? You create a loop: while your first most element, v0, is nonzero, you add/move (this is the same thing) the first value to the second and the third. In the second one, we're going to build our product. And the third is only to, uh, be able to copy the value back to the original position. So, uh, it's still there when we do the next iteration of the loop.

[> [>+>+<<-] >>[<<+>>-] <-]

As you can see, this gets complicated pretty fast.

But, that wasn't the point. I wasn't going to do any real programming in this language. I only want to create a nice, little, small compiler, which I did. Uh, I programmed the compiler in, uh, assembly language for the Motorola 68000 (which was the CPU of the Amiga), um, which is a third 16 and 32 bit CPU.

Um, in order to get it small, I had to use some of the bytes three times: once, it was being executed as anybody in a program would; the second, uh, use of the byte was as a copy source, because I need to write the bytes to the output where we would take those bytes from. Well, if I've got, for example, an add instruction in my, uh, own source code already, well, let's use that one instead of having a large table of instruction output. And the third, use of the, uh, same byte was, it was used as a table: where do I get an offset table, where do you get the code from that I need to write to the output.

All of this work was quite a lot of work, resulted in a compiler that was 240 bytes long, later reduced to 200 bytes.

After I, uh, completed the whole compiler, which was my whole point, I still needed a name for the language. I was trying, and failing, to express things like, uh, uselessness and confusion, and chose the name, brainfuck. Which, later on, turned out to be a better name than I had originally intended.

I released the compiler, and I moved on to other things. The language had served its purpose. Or so I thought.

Twenty years later, we can see there's 700,000 pages on Google that mentioned brainfuck. It's not 100% of programming language, but mostly, what have I done?

I semi-expected that other people would create compilers and interpreters, because it's very easy. I mean, you can write that one in half an hour. But, it's everywhere now. Perl 6 has builtin support for, uh, brainfuck. Which was an exercise for them, because they can support just about any language, but this was the easiest one.

Short interpreters, umm, I'll give you a link to the presentation where you can look it up, there's a ton of them. The very shortest one, uh, I couldn't find in time for the presentation, it was 57 bytes. In x86 assembly. It's, incredible. I mean, it's 1 line, 1 text line of code. It fits in a signature.

Or, there's the IDE's, Visual Brainfuck, in the browser, where you can actually see the virtual machine working and moving around the tape, and changing the values, and creating output.

Two things I forgot to mention here: there's even a brainfuck that only used mov instructions in x86, can, uh, execute any brainfuck program, doesn't use any other instruction. And, uh, there's a brainfuck implementation in Minecraft. People are weird.

Less expected is that there are brainfuck CPUs. What's easy to create a compiler for is also quite easy to create hardware for, so, you're looking at a 256 core brainfuck CPU.

Because the language is so easy to understand, it is also very easy to modify. So people created variants. Tons and tons of variants. For example, uh, the programming language Ook! is orangutan-compatible, it only, uh, knows the commands "Ook Ook". Smallfuck is just 4 different commands, uh, sorry, that's the one with only 1 bit per cell. And Brainloller, uh, allows you to program graphically, with your, um, instruction pointer moving around, the uh, two-dimensionally on the grid of the picture.

But the most unexpected thing - people started writing programs. You're looking at a Mandelbrot that was rendered by brainfuck. I mean, I mean, ... why? Or even worse, these people scare me... Uh, people found a way to write a Quine in brainfuck, which is a program that manages to output its own source code. I don't know where to begin.

->+>+++>>+>++>+>+++>>+>++>>>+>+>+>++>+>>>>+++>+>>++>+>+++>>++>++>>+>>+>++>++>+>>>>+++>+>>>>++>++>>>>+>>++>+>+++>>>++>>++++++>>+>>++>+>>>>+++>>+++++>>+>+++>>>++>>++>>+>>++>+>+++>>>++>>+++++++++++++>>+>>++>+>+++>+>+++>>>++>>++++>>+>>++>+>>>>+++>>+++++>>>>++>>>>+>+>++>>+++>+>>>>+++>+>>>>+++>+>>>>+++>>++>++>+>+++>+>++>++>>>>>>++>+>+++>>>>>+++>>>++>+>+++>+>+>++>>>>>>++>>>+>>>++>+>>>>+++>+>>>+>>++>+>++++++++++++++++++>>>>+>+>>>+>>++>+>+++>>>++>>++++++++>>+>>++>+>>>>+++>>++++++>>>+>++>>+++>+>+>++>+>+++>>>>>+++>>>+>+>>++>+>+++>>>++>>++++++++>>+>>++>+>>>>+++>>++++>>+>+++>>>>>>++>+>+++>>+>++>>>>+>+>++>+>>>>+++>>+++>>>+[[->>+<<]<+]+++++[->+++++++++<]>.[+]>>[<<+++++++[->+++++++++<]>-.------------------->-[-<.<+>>]<[+]<+>>>]<<<[-[-[-[>>+<++++++[->+++++<]]>++++++++++++++<]>+++<]++++++[->+++++++<]>+<<<-[->>>++<<<]>[->>.<<]<<]

(Quine by Brian Raiter)

So, uh, now that we are done, I had to write something in brainfuck too for this presentation.

Hmm. Write a brainfuck for this presentation. What you're looking at is brainfuck.

It's actually quite easy. All you have to do is to create slides, in Google Docs, download those slides as pdf, explode the slides into separate PNGs, convert every PNG into a SIXEL image. Nobody knows SIXEL. Brainfuck does. Because, this is a simple, um, ASCII based terminal emulator, that was a part of the feature set in the latest VT-340 terminals. So, you add for the magic string, and poof! You got a big map graphics in your, uh, terminal. And it is supported by Xterm. So we are in an Xterm here.

Those SIXEL graphics, I had to convert them to brainfuck source, compile it to see, then compile to executable. And now you are looking at a full screen Xterm with that brainfuck program, running in it. I mean, nothing to it really is there.

Well, it looks like we're missing the last page of the presentation in this version. Um. There are some problems with brainfuck. I never submitted it to the unseen committee, which means there are lots and lots of variants. You should never let me design a language anymore, because people disagree about how large a memory cell is, people disagree what's happening when you underflow, people disagree what's happening when you read the character, and you're at the end of file.

So, there's lots of brainfuck sources and lots of implementations, and sometimes they stick together. Sometimes they don't.

So, after what you've learned, there's only one thing left to do - unfortunately, um, a little bit hard without the last slide. You should tell me what I am based on my T-shirt. Uh, I guess you're not gonna manage from behind, maybe somebody in the front row manages?

>++++++++[<+++
+++++>-]<+++++
++.--..++++++.

Apart from that, thank you very much for your attention. And please ask any questions you might still ask, for some reasons I don't understand.

[appause]

No questions? Okay, I guess I have to give up now. Yep, it's a brainfuck source code, which you can actually, uh, come by this T-shirt from Get Digital - I'm not getting any percentage, sorry - which says "GEEK". It outputs "GEEK" if you execute it. And I wanted to have you shout it at me - GEEK!

I guess we're done here. Ah, one more question.

[pause]

Uh, there are brainfuck compilers in brainfuck, which was the question there, so there's also brainfuck interpreters in brainfuck, and, uh, one of the most popular uses of brainfuck is in, uh, polyglot programs, meaning one source code, uh, that can be, uh, the input for different interpreters, and brainfuck is very, um, easy to get in there because it ignores all the characters that it doesn't know. So there's some programs that have, like 65 different languages in ... it's the same source code for 65 different languages, and always, bring focus one of them.

[pause]

The question was, uh, whether he can write brainfuck that's been transpiled to JavaScript. I, well there are, but it's probably to our project to do that. So, basically, the answer was always do it yourself, it's so easy. But, um, what you can do definitely is like I mentioned, uh, compile it to just about any architecture, and if you want to use only mov instructions.

[pause]

Uh, the question was, uh, what do you call brainfuck users? I would rather not disclose. laughs

[pause]

That was it? Okay. Thanks, very much, fine.