A Brief Introduction to Esoteric Languages

This is the companion reference for A Brief Introduction to Esoteric Languages, my lecture for a friend’s college class. The video should be legible to other viewers, and the material here should be (mostly) understandable without watching the video.

The Esolangs

Listed roughly in order of appearance in the talk, with the exception of Piet, which was moved to fit in with the other multicoded esolangs.

INTERCAL

Don Woods, 1972.

A “prehistoric esolang”, Compiler Language With No Pronounceable Acronym (INTERCAL) was also the first joke language. I didn’t cover it because the gags aren’t that interesting.

FALSE

Wouter van Oortmerssen, 1993

Arguably the first “true” esoteric language. A language designed to 1) have the smallest possible compiler and 2) be really hard to understand. Notable for inspiring both brainfuck and Befunge. Brainfuck took these goals further, while Befunge went in a different direction.

Brainfuck

Urban Müller, 1993.

Arguably the most famous esoteric language, and the one that made esolangs go mainstream. Made when Müller saw FALSE and thought “I can do better than that.” While FALSE’s compiler was a whole kilobyte, Brainfuck’s compiler was 240 bytes. At the time Müller also ran the Aminet, so had enough reach to initially spread Brainfuck. The funny name and unusual coding puzzle did the rest.

The brainfuck runtime consists of an array of cells, all initialised to zero. There are eight commands:

It’s implementation-defined what happens if you decrement a 0 cell or move the pointer past the last cell. Every compiler and runtime would make its own decisions. Every other symbol is a noop, which 1) makes brainfuck relatively easy to comment, and 2) means you can secretly embed brainfuck programs in other language programs (multicoding).

Brainfuck is in the class of “Turing tarpits”, languages that are so small and simple they’re close to pure Turing machines. While it’s Turing complete, actually doing anything with brainfuck is going to be a challenge. Because brainfuck is TC you can use it to prove other languages TC: if you can write a brainfuck interpreter in language P, then P is Turing complete. For example, here’s a proof that Piet is Turing complete:

In the talk I gave an program that multiplies two numbers. Here’s an annotated version of the code:

+++>++<      setup: set 2 and 3 as x & y
[            while cell A is not 0
-              decrement cell A
>[->+>+<<]     add cell B to C & D
                (Now B = 0 & C = y)
>[-<+>]        move C to B
                (Now B = y & C = 0)
<<             move back to A
]            end while

This adds cell B (y) to cell D x times, meaning D is now the value x*y. In the process we “lose” the value of x. All math is done as in-place mutation, such is the price of minimalism. You can step through the script yourself here.

Brainfuck Derivatives

Ook!, Cow, etc. People reskin Brainfuck because 1) It’s a good introduction to writing your own esolang, and 2) it lets you be lolrandom. A language for cows!!!

Years ago I wrote my own brainfuck derivative. I am not proud of this.

Befunge

Chris Pressey, 1993.

While FALSE and Brainfuck aimed for minimal compilers, Befunge aimed to be as hard to compile as possible. Pressey used a whole lot of tricks to do this. The most famous one is that the language is 2D.¹ The instruction counter starts at the top left and moves right, wrapping back left if it touches the edge of the program area. Some instructions manipulate the data stack, while others change the direction the counter moves.

1v
 2
 >@

This would push 1 to the stack, then 2, then end program (`@`). There are other control-flow operators, too. One is `_`, which pops a value and sets the direction as left unless the popped value was 0, in which case it sets the direction as right.

In addition to a single pushdown stack, there’s another place you can store data: the Befunge source code itself. `g` can read a program instruction as a value and `p` can modify the source code to store a value. Of course, if the instruction counter reaches a stored value, it will execute that value as an instruction. Writing a `v` to a cell that originally had a `<` could radically change your entire program semantics mid-run, further adding to the difficulty of writing a compiler.

There are a few different Befunge standards. I wrote the talk around Befunge-93, which you can try online here. Befunge-93 is technically not Turing complete because it restricts the board to 2000 cells, but later versions remove this limit.

Shakespeare

Karl Wiberg and Jon Åslund, 2001.²

(The full name is “Shakespeare Programming Language”, or SPL, but everybody refers to it as Shakespeare.)

A language designed to look like a Shakespeare play. Every variable is a character name, and assignments of values are based on the number of adjectives. This is easier to demonstrate with an example:

[Enter Hamlet and Romeo]

Hamlet:
  You dirty lying coward!

Romeo:
 You are as brave as the difference 
 between a handsome tree and me! 

Try it online!

Hamlet is setting the value of Romeo to a number x. Since “cowards” is a ‘not nice’ noun, we start with -1. Then we double it for every adjective, so Romeo := 2 * 2 * (-1) = -4. Similarly, “hero” is a ‘nice’ noun, so “brave hero” is 2. This means that Romeo’s statment is equivalent to Hamlet := 2 - Romeo. Other programmatic constructs, like control flow, are also embedded as dialogue.

Wiberg and Åslund developed Shakespeare for a class on syntactic analysis, so didn’t create a compiler, just a converter to C. Languages like Shakespeare, where the source code can also be interpreted as a cultural artifact, are called multicoded. Shakespeare is Turing complete and any brainfuck program can be converted into a Shakespeare program.³

Piet

David Morgan-Mar, 2003.

Piet is a visual programming language in the truest sense: every Piet program is an executable picture. The first Piet programs looked like sacks of random pixels:

But over time some dedicated “Piet artists” developed their own styles. This is a program by Thomas Schoch, one of the first notable artists:

Like Shakespeare, Piet is a multicoded language. Unlike Shakespeare, Piet programs work as art. Or at least, it’s significantly more feasible to make a Piet program that’s good art vs a Shakespeare program that’s a good play.

TryItOnline accepts Piet code, but you have to upload it as a hexdump. Instead you should use this.

BodyFuck

Nik Hanselmann, 2010.

Brainfuck with a webcam! You move your body to make symbols, turning the act of programming into a dance. No way to delete a symbol, though, so you better not make any mistakes.

Arguably not a “complete” esolang, really just a novel way of writing brainfuck. But this is my talk and what I say goes.

Chef

David Morgan-Mar, 2003.

A programming language where the source code looks like a recipe. Chef is arguably the most common multicoded language. This is because it’s a staple of Ian Bogost’s Introduction to Computational Media class, where they make and eat Chef programs every semester.

Also there was a guy who wrote “hello world” and then baked it as a cake.

Orca

100 Rabbits (Rek and Devine), 2018.

A 2D livecoding environment, primarily designed to drive MIDI synthesizers, but that’s not the only way people’ve used it. Here’s an example of someone driving an NES game using Orca:⁴

I don’t know how to explain how Orca works in text form. Here’s the brief demo I did as part of the talk:

(Note I made a mistake here, colon is the midi command. Semicolon is UDP.)

It’s the exact kind of language you’d expect to see from two artists who live on a boat, and I say that out of pure admiration.

While best used via the desktop version, you can also try it online here. One good tutorial is here, which also comes with built-in instruments.

GolfScript

Darren Smith, 2007.

The first language designed entirely for code golfing: writing programs in as few characters as possible. It achieves this by prioritizing terseness over all other code constraints. The runtime model is stack based- values and functions are pushed on the stack, then operators pop values from the stack and manipulate them. As an example, if I wrote 2 3 +, it would push 2 onto the stack, then 3, then pop them both, add them together, and push 5 on the stack. Using a stack saves a lot of syntax overhead. To further shorten programs, GolfScript overloads every operator to do different things based on the type. In different contexts, * can mean multiply, or “apply function n times”, or “duplicate array”, or “reduce array”.

Curiously, GolfScript also has some full-text words, like “rand”, “while”, and “abs”, which make some scripts longer than they need to be. Nonetheless, GolfScript took the codegolfing world by storm, quickly becoming the dominant golfing language. This inspired people to make successors.

Later Golflangs

(I called these “supergolfing” languages in the talk, but that’s not a community term, just something I used for clarity.)

Above and beyond GolfScript’s golfing tricks, there are two low-hanging fruit:

1. Opcodes. Special instructions that do entire problems for you. GolfScript has one-character operators for things like “split array by character” or “map-filter”. Pyth has one-character operators for things like “All prime factors of a number” and “titlecase sentence”.
2. Using the whole byte. Standard ASCII only has about 90 printing characters– That’s wasting almost two-thirds of the byte. If you use a different character encoding you can pack more visible characters— and more opcodes— into the extra 146 characters.

There’s also smaller tricks. Pyth has common constants, so you can shave a byte writing T instead of 10. Jelly has both 1- and 2-character opcodes, so that ÆP and Æp do completely different things (“is prime” and “largest smaller prime”, respectively). Both have a symbol for “input”, so you don’t have waste characters moving it around the stack.

According to Martin Ender, a famous golfer and esolanger, a lot of the challenge for language designers is in finding the right opcodes:

It seems to be a bit of a misconception among less experienced golfing language designers that just throwing together a bunch of built-ins is all it takes to create a great golfing language: it’s generally not very helpful to have a “FizzBuzz” built-in, because while that lets you solve this particular problem in a single byte, it also wastes that byte for another useful command (because it’s probably not going to be used in any other program). So for a start, you’d rather want to think about a good set of built-ins that combine easily to build lots of different short programs.

He also says “the first generation or two of golfing languages don’t normally stand a chance against any of these modern ones”, which I find absolutely delightful.

MetaGolfScript

Anonymous, 2014 (?).

Actually an infinite family of esolangs. From the formal definition:

A non-empty MetaGolfScript-N program behaves identically to the same program in GolfScript, regardless of N. An empty MetaGolfScript-N program behaves identically to the Nth possible GolfScript program. Programs are enumerated first by size, then by lexicographic order. E.g. program 0 is empty, program 1 contains a single NUL character, and so forth.

For example, take the string “ABC”. That’s 66 67 68 in 1-indexed ASCII. If we treat it as “base-256 representation of a number”, in decimal that would be 256² * 66 + 256¹ * 67 + 256⁰ * 68, or 4342596. So MetaGolfScript-4342596 will execute “ABC” given an empty input. This makes the metagolf family the ultimate language for code golfing: for any given problem, there exists a metagolf dialect that solves it in zero characters.

As far as I know, the inventor is completely anonymous. It’s an IP address that made only one modification to the esolang wiki. So we don’t know if this was made as a computationally interesting idea, as a cultural statement, or just to troll code golfing communities. This sparked some debate on the Code Golf & Coding Challenges Stack Exchange (CGCC):⁵ how do you score a metagolf entry? By the size of the flag passed in? By the length of the name of the language? Eventually, the community settled on formally ruling against metagolf entries. Because if you submit one to a code golf challenge, you’re pretty obviously acting in bad faith and will be shunned by the community.⁶

Hexagony

Martin Ender, 2015.

While most 2D languages use a square grid, hexagony uses a hexagonal grid. Also, instead of one instruction pointer, it has six. The name is a portmanteau of “hexagon” and “agony”. Here’s a hello world:

   H ; e ;
  / ; o ; W
 @ > r ; l ;
l ; ; o ; Q \
 ; 0 P ; 2 <
  d ; P 1 ;
   . . . .

(ref)

Hexagony is exceedingly popular on the CGCC because 1) The creator, Martin Ender, is also a prolific code golfer and community contributor and 2) look at it it’s a friggin’ hexagon.

Hexagony also has a surprising number of auxiliary tools. There’s a hexagony colorer and even a fantastic online IDE.

Notes and Errata

Additional comments on portions of the talk.

On the Diversity of Esolangs

I showed three examples of esolangs that don’t otherwise appear in the talk:

• Folders: An esolang where “code” is a set of nested folders. The first version encoded some information in the names of the folders, while the current version encodes everything in the nesting. Also notable for being by Daniel Temkin, who also runs esoteric.codes.
• Grasp: An esolang where the source code is in the form of a directed graph.
• Malbolge: The most conspicuous absence from the talk. Invented in 1998 by Ben Olmstead, Malbolge was designed to be as hard to program in as possible. It pulls all sorts of nasty tricks:
  • The data format is ternary, not binary.
  • There’s only three data registers. All other data must be stored in the same memory space as the program instructions and can be executed as program instructions.
  • Each step of the program, the next executed instruction depends on the character read and the C register, mod 94.
  • But there’s only eight commands, and the other 86 values of C are NOPs.
  • After every instruction, the previous character is cryptographically encrypted.
  • And more!!!

It took two years for someone to write Hello World. Olmstead thought it would be impossible to write anything more interesting in it. He was wrong.

Brainfuck is Turing Complete

The code shown for a “C compiler in brainfuck” is actually for a brainfuck compiler written in brainfuck. It is taken from here.

It’s unlikely we’ll ever see an actual C compiler in brainfuck, in part because spec-compliant C compilers are themselves incredibly difficult. Instead here’s some video games.

BrainFuck derivatives

In the talk I said that people started making brainfuck derivatives and moved into making other esolangs. There are two high profile examples of this:

• David-Morgan Mar made “Ook!”, then Piet and Chef.
• Edwin Brady made “Whitespace”, then Idris (the logo I showed in the talk).

Idris isn’t actually an esolang. It’s a cutting-edge language in formal verification, where the type system is so powerful you can prove arbitrary properties about the code. That means that (to a certain extent), if the code is incorrect, it won’t compile. Here’s an example of a provably correct leftpad.

It’s not esolang, but I find it delightful that Brady also wrote Whitespace and I like giving him a hard time for that.

BodyFuck

The creator of BodyFuck does a lot of computational art, like kepler and braids.

Orca

There’s a mistake in the live demo: I said that the ; command sends MIDI signals. It actually sends UDP packets, which you can use to control things besides synths. The actual MIDI command is :.

I didn’t go into this too much, but I’m exceptionally fascinated with Orca. For me it’s not the livecoding or music, but the “bangs”. OOPers like to talk about message passing, but Orca has literal message passing. You can see messages fly through the air and collide into functions. Orca doesn’t really capitalize on this (it’s just a means to an end), so I want to see what happens when that cognitive model made the central idea.⁷

The music sample is from Richard’s Instagram.

On Testing Primes

Links to the various solutions:

• Python
• Perl
• APL
• GolfScript
• Pyth
• Jelly
• Hexagony

The MetaGolfScript solution was reverse engineered from the GolfScript solution via this J script:

x =: '~.,{*.!+}*.*\%'
256 #. >: x: a. i. x

Try it online!⁸

On GolfScript’s / Operator

In the talk I said that [1 2 3] {2*} / is a map. This was a deliberate oversimplification: it will double every element in the array, but push each value individually onto the stack. The proper map operator is %, which will push the mapping as a single array. I also left out the fourth use of /, “do-while-collect”, for conceptual simplicity. 1 {20<} {2*}/ → [1 2 4 8 16].

On Testing Primes in GolfScript

The GolfScript for testing primes is ~.,{*.!+}*.*\% (tio link). This is based on Wilson’s Theorem: n is a prime if and only if (n - 1)! ≡ -1 (mod n). A corollary of that is (n - 1)!² % n is 0 if n is composite and 1 if n is prime. This does mean taking the square of the factorial, an incredibly inefficient algorithm, but it’s a compact one, and that’s all that matters in golfing.

We’ll start by explaining a “simpler” program, ~.,(;{*}*.*\%, which is equivalent but fails for n = 1, and then provide the full program. You can follow along with the reference if you’d like. Assume stdin is 5, which starts us off with this:

"5"           # STACK
~.,(;{*}*.*\% # REMAINING PROGRAM

~ converts the top element of the stack to an integer, and then . duplicates it.

5 5
,(;{*}*.*\%

The , converts the top 5 into [0 1 2 3 4]. Then ( takes the first element out of the array and pushes it to the front of the stack.

5 [1 2 3 4] 0
;{*}*.*\%

Then ; pops the top element and discards it, which gets rid of the zero. After that, we push the {*} block onto the stack as a value.

5 [1 2 3 4] {*}
*.*\%

When given an array and a block, * reduces over the array. This means that {*}* is an idiom for “product of array”.

5 24
.*\%

As before, . duplicates the top value. So .* will square the top value.

5 576
\%

Finally, \ swaps the top two elements of the stack, and % is modulus.

1

Once the program ends we dump the stack to stdout. 5 is prime! Woot!

I said this doesn’t work for n=1. That’s because running 1, gives us [0], meaning ( would empty the array. We hit a problem ‘round here:

1
\%

Since there’s only one value on the stack, \ raises an error. Oops. We have to leave the 0 in the array, but then the product of the array will be 0. We instead need to reduce with the “safe” product {*.!+}. ! maps falsy values to 1 and truthy values to 0:

0 1 *.!+
0 .!+
0 0 !+
0 1 +
1

2 3 *.!+
6 .!+
6 6 !+
6 0 +
6

This means that {*.!+} is identical to {*}, except for the first 0 1, which it instead maps to 1. This gives us a final script of ~.,{*.!+}*.*\%.

Note that this involves squaring a factorial. To test if 73 is prime you have to divide it from a 208-digit number. It’s redonkulously inefficient but fewer bytes than doing a regular primality test, which is why it’s the better golfing answer.

On Supergolfing

I made two mistakes in the section on Jelly:

1. In the talk I mistakenly said that it uses Unicode “to pack in more opcodes”. Most golfing challenges are scored on bytes, not characters, so a single two-byte Unicode character scores the same as two ASCII characters. Instead, Jelly uses a different encoding than ASCII pack in more useful characters. The byte 0000 0100 in ASCII is the End of Transmission signal, while in Jelly it’s ¥. Some golfing languages do use Unicode, but the main saving is in a better codepage.
2. I said Æ was “is prime”, but it’s actually the prefix for 2-byte arithmetic functions. ÆP is “is prime”.

Learning More

Some references if you liked the talk/page and want to dive deeper.

Major Resources

• TryItOnline: The easiest way to try most of the languages I talked about (though see next section for exceptions).
• Esolang Wiki: If it’s out there, it’s probably here. Note that it also contains a lot of joke languages and Trivial Brainfuck Substitutions, which can make browsing a bit difficult.
• esoteric.codes: Daniel Temkin’s site. Absolutely fantastic. His piece The Aesthetics of Multicoding Esolangs was a cornerstone of my research.

Running Stuff Online

TryItOnline is fantastic, but it’s not perfect. Some languages don’t use an ASCII format, and some languages have better tools with more features (like step-through).

• brainfuck: here. Step-through.
• Befunge-93: here. Step-through, shows stack.
• Piet: npiet accepts images. TIO just accepts hexdumps.
• Orca: here for the web version, here for a web version + preconfiged synthesizer.
• MetaGolfScript: the esolang wiki only provides a python2 script. You can use this to turn strings into MGS numbers and this to convert numbers back to strings.
• Hexagony: here. Step-through, multiple views, debugger, data model.

Other Interesting Esolangs

Some ones I find interesting but didn’t talk about:

• Malbolge, discussed in more detail here.
• Velato, a multicoded language where the source code is also musical notes.
• sha-fuck. A language designed itself as a puzzle. The definition makes it almost impossible to write a syntactically-correct program, the challenge is to find one. Solved here.
• Game-environment languages: If I had another month to work on this talk, this would be the first thing I’d have added. Many video games have items in them that, if used correctly, can enable total (or a useful subset of) computation. What makes these interesting is that they’re unintentional: computation arises as an emergent phenomena. Because of this the languages aren’t “intelligently designed” and have all sorts of weird powers and limitations. But players use them because, regardless of their jankiness, GELs give them more power than developers explicitly intended. Some examples:
  • Minecraft Redstone Computers
  • Super Mario Maker Calculators
  • Dwarf fortress Minecart Computers

Creator Pages

Many Esolang creators have additional pages for their work:

• David Morgan-Mar: https://www.dangermouse.net/esoteric/
• Chris Pressey: https://catseye.tc/article/Languages
• Wouter van Oortmerssen: http://strlen.com/programming-languages/
• 100 Rabbits (Rek and Devine): https://100r.co/site/home.html
• Nik Hanselmann: http://nik.works/

Used Media