Quick minilanguage to steer a submarine with Quackery
Tags: adventofcode, concatenative, esoteric, programming
Published: 2021-12-03 11:46:00

Every year I try to solve [Advent of Code](adventofcode.com) with some esolang for as long as possible. This year's language of choice was [Quackery](github.com/GordonCharlton/Quackery): a cute concatenative language based on Lisp and Forth, and when I saw the second puzzle I knew that language was perfect.

### The problem
Puzzle for day 2 of this year's AoC is about steering a submarine and figuring up what coordinates you end up on. Input is a set of simple commands like this:
```
forward 5
down 5
forward 8
up 3
down 8
forward 2
```
Each command consists of one of three directions: `forward`, `up` or `down`, and a number indicating how far in this direction to swim. The important note is that we care about **depth** and **horizontal distance**, so `down` would **increase** depth, and `up` would **decrease** it.

### The idea
A standard approach to such problem would be to iterate over the input string word by word and changing some state based on what words are read. For anyone accustomed to concatenative languages this should sound familiar: it's exactly what the interpreter does to execute code! Given that one of the rules of concatenative programming is to never write the same code twice we should use the interpreter itself to interpret our input for us.

### About Quackery
Quackery is a stack based concatenative language. Every word executed interacts with the main Data Stack: numbers put themselves on the stack and operators and user defined words act on top values of the stack. There are plenty of stack shuffling words to arrange the top of the stack for other operators. Most notable are:
* `dup` - duplicate the top of the stack
* `drop` - remove the top of the stack
* `swap` - swap top two values on the stack

The rest will be explained when used.

### The implementation
The Quackery inerpreter already recognises numbers so the only thing we need to define are direction words: `forward`, `up` and `down`. In addition to that we need some state that these words would update, which I chose to be two numbers on the stack indicating depth and horizontal distance.

To make things nicer I will define a state constructor word which just puts two zeroes on the stack:
```Factor
( state: depth, horizontal-distance )
[ 0 0 ] is new-state ( -- state )
```
Parenthesis in Quackery indicate comments, just as in Forth.


`up` and `down` should take a number that follows them and add or subtract from the second item on the stack:
```Factor
[ swap ]'[ + swap ] is down ( state 'n -- state )

[ swap ]'[ - swap ] is up ( state 'n -- state )
```
`]'[` is used to take the item following the word currently executed, so it would be the number after `up` or `down`.

`forward` is a bit tricky because it's already defined as a *builder word* in Quackery, and redefining builders requires some trickery. I need to first define a normal word with the behaviour I want `forward` to have and then redefine the builder `forward` to build that behaviour:
```Factor
[ ]'[ + ] is forward-behaviour ( state 'n -- state )

[ dip [ ' forward-behaviour
        nested join ] ]      builds forward ( [ $ -- [ $ )
```

Now that the interpreter can understand our input as source code we just need to run it on said source code:
```Factor
[ dip new-state
  quackery * ]   is solve-puzzle ( input -- n )
```
`dip` takes the top item off the stack, runs the operator that follows it (in this case `new-state`) and puts the item back on the stack. Coordinates are multiplied at the end to produce the answer that AoC will accept.

Full code, along with the second part of the puzzle, can be found in my [AoC github repo](https://github.com/olus2000/AoC/tree/main/2021/Quackery).

### Conclusion
This solution is a very minimalistic way of showing how easy and convenient it is to implement new languages in stack languages. This is a very useful feature because you don't need to implement a whole new interpreter, just define what each command does and tell the user what commands you support.

If you want to fully understand the code I wrote there check out [The Book of Quackery](https://github.com/GordonCharlton/Quackery/blob/main/The%20Book%20of%20Quackery.pdf), a 100 page tutorial and documentation for the Quackery language written by it's author and available for free as a PDF. It's very newbie-friendly.