Interpreting 2048 in toki pona
I had never written a compiler before. “I should make a compiler,” I thought to myself. Inventing a new language is time consuming, so I set out to pick an existing language to work with. I need a simple language. I know! Let me try toki pona!
toki pona is a general-purpose programming language commonly used in everyday conversation. It has simple, consistent grammar, and only a few words to work with. I know! Let’s use noun groups as symbols.
The Data Type
A toki pona “noun” is a simply list of words. For example: moku pan lipu
could mean some kind of edible chips.
I’m too lazy to think of another data type, so let’s have a global table to keep track of noun-noun key-value pairs. This is usually called “symbolic manipulation”, and an essential part of LISP.
A li B toki a set the value of symbol A to the value of symbol B
A li nimi pi B toki a set the value of symbol A to B.
like (quote) in LISP
Oh, toki a
is like //
in C.
List Processing
Lists are overrated. We use A en B
instead.
To cons a list, write:
A li B en nimi pi A
NIL
Every symbol by default evaluates to a list of zero words. I used ala
consistently to denote “nil”, although ixdhtnwpuifgdhbkfghtw
could also work.
Jump
To create a jump label:
mi li A
To jump:
mi tawa e A
Branching
There is only one kind of branching instructions: is-equal.
To compare two values:
A li sama ala sama B
This sets a global “is-equal” flag.
sama la <instr>
: If the “is-equal” flag is true, execute the instruction.
sama ala la <instr>
: If the “is-equal” flag is false, execute the instruction.
That’s it!
I call this dialect of toki pona “toki kama sitelen” because it is a symbolic programming realization language.
Parsing is so simple so I won’t describe it here. Every line of text - also an instruction - is compiled to a bytecode instruction and then interpreted.
If you want to see how the language works in practice, here is a recording of me playing the game 2048 with a 2x2 board. It is written in this language, yes. You can see the bytecode interpreter and the game in its source repository. Making the board 4x4 (like the original 2048 game) is left as an exercise for the reader.
What Have I Learned From This Project
For me, the knowledge gain is probably negative.
I did confirm that what is considered a programming language is kind of arbitrary. Any language that tells a computer what to do can be seen as a programming language. This includes, mouse clicks, key presses, written words and any input alike. One notable aspect of a programming language is that you can describe a wide range of algorithms in it - commonly called “Turing-complete” or “human speech”: unrestricted in nature. In fact, one can analyze the input method of any given program and decide which category of grammar it uses: unrestricted, context-sensitive, context-free, regular.
You can read more about this complexity correspondence between programmable machines and language grammars on Wikipedia. The link is here.
This language is regular. All assembly languages are (excluding macro expansion). However, it can be used to program Turing machines.
Thinking back, the concept-tuple language I made is also regular, and it can encode arbitrary concepts as well. (random thought: If toki pona excels at being vague, the concept-tuple language excels at being precise.) I think that this fact can be used to reduce a lot of complexity, although I’m not sure what it is called - maybe related to programming complexity.
What’s Next
If I ever get interested in revisiting this project, I’ll probably add JIT with MIR. For now though, I am going to forget what I just created.