Advanced Kotlin syntax abuse
Kotlin’s operator overloading and infix notations provide a great opportunity to create a more natural reading codebase, but they also provide a great opportunity to create wonderfully nonsensical code.
In this article, I’m going to show how this outputs Hello World!
Brainfuck
First if you’re not already familiar with the language Brainfuck, BF for short from now on. It’s an esoteric, Turing complete language that consists of just a handful of symbols:
+Add 1-Subtract 1>Move to the next memory address<Move to the previous memory address[if the current memory address is zero, skip to the matching]]if the current memory address is non-zero, skip back to the matching[.Print the current address as a char,Read a value from the input
A “Hello world!” in BF is:
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.If you would like to understand how this produces this output, Wikipedia explains this well https://en.wikipedia.org/wiki/Brainfuck#Hello_World! This article is more about how I created this travesty of a syntax to be acceptable to the Kotlin complier!
Note that the above BF hello world mostly matches up with my Kotlin hello world example albeit with some different symbols.
+Add 1-Subtract 1rrather than>to move to the next memory addresslrather than<to move to the previous memory address[if the current memory address is zero, skip to the matching]]if the current memory address is non-zero, skip back to the matching[oPrint the current address as a charnNOOP, its purpose explained later
Getting started
A BF program, like any other, is a list of commands. So I decided I needed to model a Command, and a Program:
sealed class Command {
object Add : Command()
object Subtract : Command()
object MoveRight : Command()
object MoveLeft : Command()
object Print : Command()
class Loop(val loopContent: Program)
}class Program(val commands: List<Command>)
Note that I have modelled the loop command as containing another program within the loop. I now have a tree structure.
I want to keep this all immutable, so I will make an append method, that will create a new program with the additional command. But first, I’d like a way of testing this all, so I’m going to create some toString methods:
sealed class Command {
object Add : Command() {
override fun toString() = "+"
}
object Subtract : Command() {
override fun toString() = "-"
}
object MoveRight : Command() {
override fun toString() = ">"
}
object MoveLeft : Command() {
override fun toString() = "<"
}
object Print : Command() {
override fun toString() = "."
}
class Loop(val loopContent: Program) : Command() {
override fun toString() = "[$loopContent]"
}
}class Program(val commands: List<Command> = emptyList()) {
override fun toString(): String {
return commands.joinToString(separator = "")
}
}
Now our test cases can ensure that the program contents are as expected before we actually get to the point of wanting to execute it.
@Test
fun `can append command`() {
assertEquals("+", Program(emptyList()).append(Command.Add).toString())
}
@Test
fun `can append 2 commands`() {
assertEquals("+-", Program(emptyList()).append(Command.Add).append(Command.Subtract).toString())
}
@Test
fun `can append a loop`() {
assertEquals(
"+[.]", Program(emptyList()).append(Command.Add)
.append(Command.Loop(Program(emptyList()).append(Command.Print))).toString()
)
}fun Program.append(command: Command) = Program(commands + command)
We can now build the whole hello world in this fashion and assert the program structure is correct.
val helloWorld: Program = Program(emptyList()).append(Command.Add).append(Command.Add).append(Command.Add).append(Command.Add)
.append(Command.Add).append(Command.Add)
.append(Command.Add).append(Command.Add)
.append(
Command.Loop(
Program(emptyList()).append(Command.MoveRight).append(Command.Add).append(Command.Add)
.append(Command.Add).append(Command.Add).append(
Command.Loop(
Program(emptyList()).append(Command.MoveRight).append(Command.Add).append(Command.Add)
.append(Command.MoveRight).append(Command.Add).append(Command.Add)
.append(Command.Add).append(Command.MoveRight).append(Command.Add)
.append(Command.Add).append(Command.Add).append(Command.MoveRight)
.append(Command.Add).append(Command.MoveLeft).append(Command.MoveLeft)
.append(Command.MoveLeft).append(Command.MoveLeft).append(Command.Subtract)
)
).append(Command.MoveRight).append(Command.Add).append(Command.MoveRight)
.append(Command.Add)
.append(Command.MoveRight).append(Command.Subtract).append(Command.MoveRight)
.append(Command.MoveRight).append(Command.Add)
.append(Command.Loop(Program(emptyList()).append(Command.MoveLeft)))
.append(Command.MoveLeft)
.append(Command.Subtract)
)
).append(Command.MoveRight).append(Command.MoveRight).append(Command.Print).append(Command.MoveRight)
.append(Command.Subtract).append(Command.Subtract)
.append(Command.Subtract).append(Command.Print).append(Command.Add).append(Command.Add)
.append(Command.Add).append(Command.Add)
.append(Command.Add).append(Command.Add).append(Command.Add).append(Command.Print).append(Command.Print)
.append(Command.Add).append(Command.Add)
.append(Command.Add).append(Command.Print).append(Command.MoveRight).append(Command.MoveRight)
.append(Command.Print).append(Command.MoveLeft).append(Command.Subtract)
.append(Command.Print).append(Command.MoveLeft).append(Command.Print).append(Command.Add)
.append(Command.Add).append(Command.Add).append(Command.Print)
.append(Command.Subtract).append(Command.Subtract).append(Command.Subtract).append(Command.Subtract)
.append(Command.Subtract)
.append(Command.Subtract).append(Command.Print).append(Command.Subtract).append(Command.Subtract)
.append(Command.Subtract)
.append(Command.Subtract).append(Command.Subtract).append(Command.Subtract).append(Command.Subtract)
.append(Command.Subtract)
.append(Command.Print).append(Command.MoveRight).append(Command.MoveRight).append(Command.Add)
.append(Command.Print).append(Command.MoveRight).append(Command.Add)
.append(Command.Add).append(Command.Print)Oh boy, that badly needs a refactor and some cleaner syntax but at least the test is neat:
@Test
fun `can build hello world program structure`() {
assertEquals(
"++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.",
helloWorld.toString()
)
}Before we do any refactoring, let’s try and make this work with an execute method.
First we need to model the memory of the machine, known as a tape.
class Tape(size: Int = 30000) {
private val data = Array(size) { 0 }
private var pointer = 0;
}This is just an array and a movable pointer into that array.
Executing commands is pretty trivial, and you should see that they line up easily with the descriptions of the symbols given earlier in the article.
The hardest part about writing a BF machine is getting the loops working correctly, but our in-memory tree structure makes even this easy.
fun Program.execute(tape: Tape = Tape(), writer: PrintWriter = PrintWriter(System.out.writer())) {
for (command in commands) {
when (command) {
is Command.Add -> tape.add()
is Command.Subtract -> tape.subtract()
is Command.MoveRight -> tape.moveRight()
is Command.MoveLeft -> tape.moveLeft()
is Command.Print -> writer.print(tape.currentAsChar())
is Command.Loop -> while (tape.current() != 0) {
command.loopContent.execute(tape, writer)
}
}
}
writer.flush()
}class Tape(size: Int = 30000) {
private val data = Array(size) { 0 }
private var pointer = 0;
fun add() {
data[pointer]++
}
fun subtract() {
data[pointer]--
}
fun moveRight() {
pointer++
}
fun moveLeft() {
pointer--
}
fun current(): Int {
return data[pointer]
}
fun currentAsChar(): Char {
return current().toChar()
}
}
Now to run it:
@Test
fun `run hello world`() {
val stringWriter = StringWriter() helloWorld.execute(Tape(), PrintWriter(stringWriter))
assertEquals("Hello World!\n", stringWriter.toString())
}
It all works, so time to refactor.
Firstly, Program(emptyList) appears a lot, it’s always the same and as Program is immutable, this can be extracted to a constant, n. I have chosen n to stand for NOOP, it does nothing, in fact it’s not really an command at all, just an empty program. It’s the identity program, like an identity matrix, it changes no program it is appended to.
val n = Program(emptyList())Now I want to start overloading operators. Firstly so that this test passes:
@Test
fun `add command`() {
assertEquals("+", (n + n).toString())
}And I’m going to let IntelliJ be my accomplice:
//Not complete!
operator fun Program.plus(program: Program): Program {
return append(Command.Add)
}This will get us past the first test, but not this one:
@Test
fun `add commands preserve left and right programs`() {
assertEquals("<+>", (n.append(Command.MoveLeft) + n.append(Command.MoveRight)).toString())
}However, this will:
operator fun Program.plus(program: Program)
= append(Command.Add).append(program)With the help of a new append overload to concatenate whole programs:
fun Program.append(program: Program)
= Program(commands + program.commands)Our first crime against Kotlin has now been committed, plus now does not only add the left and right operands, but inserts a command too so that the the whole is now greater than the sum of the parts, which is a fine saying, but not very mathematically accurate!
So how do we get multiple + s in a row to make sense, well we’ll write a test and let IntelliJ tell us how!
@Test
fun `multiple plus symbols`() {
assertEquals("<++>", (n.append(Command.MoveLeft) + + n.append(Command.MoveRight)).toString())
}
Thanks IntellJ, you’re making this easy!
operator fun Program.unaryPlus()
= n.append(Command.Add).append(this)I’m not sure why unary plus can be overridden to be honest, or when you might even want to use it. Unary minus makes some sense, a way to produce a negative version of your type, and maybe Kotlin just allows the unary plus for completeness?
In any case, we can now start to construct the hello world, we can have the 8 + symbols at the front of the program:
@Test
fun `8 plus symbols`() {
assertEquals("++++++++", (+ + + + + + + + n).toString())
}Note the presence of n, without which the compiler would have no idea we’re talking about the Program type. We can insert these wherever we need to tell the Kotlin compiler about the type.
Also note that for the first time here, we’ve got to the point where white space matters. Using IntelliJ auto-formatter will bring all these unary pluses together and cause a syntax error. It’s our first big clue that we’re getting off the beaten path here!
That’s it for the plus, and the procedure for deriving the minus support is identical.
operator fun Program.unaryMinus()
= n.append(Command.Subtract).append(this)operator fun Program.minus(program: Program)
= append(Command.Subtract).append(program)
In a way the behavior of these minus implementations are even more unexpected than that of the plus implementations as nothing is subtracted, the programs only get longer!
The Loop
The next interesting language feature to misuse is the array indexer to give us the loop syntax.
I employ the same pattern, write what I want it to look like and let IntelliJ make its suggestions in good faith:
@Test
fun `loops using array syntax`() {
assertEquals(">[-]", (n.append(Command.MoveRight) [ n.append(Command.Subtract) ]).toString())
}
operator fun Program.get(loopInner: Program)
= append(Command.Loop(loopInner))Ok, that was quick let’s recap what I’ve done there, I’ve taken an overload that was designed to let you look stuff up in your custom classes as though they were arrays/lists and I’ve made it create a mutation of the current program with an appended loop command which contains another program. This is a truly terrible misuse of this feature!
But where does applying that leave helloWorld:
val helloWorld: Program = + + + + + + + + n [
n.append(Command.MoveRight) + + + + n[
n.append(Command.MoveRight) + + n
.append(Command.MoveRight) + +
+ n.append(Command.MoveRight) +
+ + n.append(Command.MoveRight)
+ n.append(Command.MoveLeft).append(Command.MoveLeft)
.append(Command.MoveLeft).append(Command.MoveLeft) - n
].append(Command.MoveRight) + n.append(Command.MoveRight) +
n.append(Command.MoveRight) - n.append(Command.MoveRight)
.append(Command.MoveRight) +
n[n.append(Command.MoveLeft)]
.append(Command.MoveLeft)
- n
].append(Command.MoveRight).append(Command.MoveRight).append(Command.Print).append(Command.MoveRight) - - -
n.append(Command.Print) + + + + + + + n.append(Command.Print).append(Command.Print) + + +
n.append(Command.Print).append(Command.MoveRight).append(Command.MoveRight).append(Command.Print).append(Command.MoveLeft) -
n.append(Command.Print).append(Command.MoveLeft).append(Command.Print) + + + n.append(Command.Print) - - - - - -
n.append(Command.Print) - - - - - - - - n.append(Command.Print).append(Command.MoveRight).append(Command.MoveRight) +
n.append(Command.Print).append(Command.MoveRight) + + n.append(Command.Print)Move Left and Right
A lot of things remaining can be seen to be extractable, things like n.append(Command.MoveRight).
I’d love to use > and < but, although these can be overridden in a way, they both boil down to the overridable compareTo which doesn’t tell you which operator was actually used so I am forced to choose my own symbols for these commands.
val o = n.append(Command.Print)
val r = n.append(Command.MoveRight)
val l = n.append(Command.MoveLeft)
val helloWorld: Program = + + + + + + + + n [ r + + + + n [
r + + r + + + r + + + r +
l.append(Command.MoveLeft).append(Command.MoveLeft).append(Command.MoveLeft) - n
].append(Command.MoveRight) + r + r - r
.append(Command.MoveRight) + n [ l ]
.append(Command.MoveLeft) - n
].append(Command.MoveRight).append(Command.MoveRight).append(Command.Print).append(Command.MoveRight) - - -
o + + + + + + + o.append(Command.Print) + + +
o.append(Command.MoveRight).append(Command.MoveRight).append(Command.Print).append(Command.MoveLeft) -
o.append(Command.MoveLeft).append(Command.Print) + + +o - - - - - -
o - - - - - - - - o.append(Command.MoveRight).append(Command.MoveRight) +
o.append(Command.MoveRight) + + oSo, now all that is left are a few appends. What if we just replace them with what we want and let IntelliJ suggest something, it’s worked so far:
infix fun Program.l(program: Program)
= append(Command.MoveLeft).append(program)infix fun Program.r(program: Program)
= append(Command.MoveRight).append(program)infix fun Program.o(program: Program)
= append(Command.Print).append(program)
Now we have arrived at our horrific destination:
val helloWorld: Program =
+ + + + + + + + n [ r + + + + n [ r + + r + + + r + + + r +
l l l l - n ] r + r + r - r r + n [ l ] l - n ] r r o r - -
- o + + + + + + + o o + + + o r r o l - o l o + + + o - - -
- - - o - - - - - - - - o r r + o r + + oI must be careful of new line locations at this point, but this can be solved by wrapping in ( ) .
All that remains is to change our execute method into an invoke:
operator fun Program.invoke(tape: Tape = Tape(), writer: PrintWriter = PrintWriter(System.out.writer())) { ... same as executeAnd we can now actually execute BrainFuck inside Kotlin, simply by wrapping in ( )and using a following pair of () to cause the invocation.
(
+ + + + + + + + n [ r + + + + n [ r + + r + + + r + + + r + l l
l l - n ] r + r + r - r r + n [ l ] l - n ] r r o r - - - o + +
+ + + + + o o + + + o r r o l - o l o + + + o - - - - - - o - -
- - - - - - o r r + o r + + o
)()Which makes for an interesting sight in the IDE as the seemingly random colours hint at our overloading of various vals and infix methods:
What’s next?
This is a Turing complete language within a language, add support for the input stream , with say i and you can truly implement anything you wish with just these symbols:
Doom anyone?
Code available at https://github.com/westonal/KotlinBrainFuck
Special thanks to Danny Preussler who reviewed this, and who’s recent talk at devfest Romania 2020 inspired me to write this long standing idea up.
