In this episode, the intcode computer is born.

Part 1

03f2564

Part 1 consisted of implementing a simulator capable of evaluating programs described in intcode. Intcode is a list of comma-separated integers, each of which may be an instruction or address at any given moment. Later challenges add even more items to that list.

I was initially going to split this up into nice structures and functors (a type-level function that converts structures into structures), but I struggled do so.

In the end, memory and the interpreter all lived in the same structure. The only operations to support were arithmetic, so it wasn’t an issue at the time.

The actual solution then becomes another parsing problem (the instructions), composed with a “fixer” that writes some values into memory, composed with an interpret-to-finish operation, composed with reading the 0th element of the resulting memory.

I am proud that I recognized this as a state-machine problem, and found a way to encode every computation for an intcode program in a state-machine complete with transition function (more on that in future episodes ).

For a good overview of state-machines and other topics, I recommend Elements of the Theory of Computation, by Lewis and Papadimitriou.

I’m still working out all the ramifications, but I believe that the intcode computer (especially with later-day modifications) is Turing complete; at the very least, with a few modifications of today’s architecture, the halting problem for intcode becomes undecidable. So I believe this means we do not have a finite state-machine, but rather a possibly-infinite state-machine.

Briefly, a state-machine is the tuple \((\Sigma, \delta)\) where \(\Sigma\) is the arbitrarily-complex set of states and \(\delta : \Sigma \to \Sigma\) is the transition function. Note that a state may be a simple object, such as a single symbol, or a complex object, like a tuple of a memory object, an instruction pointer, and a few machine registers. (Traditionally, the input set is \(\Sigma\) and the states are elements of \(K\); however, in the case of intcode, a state include the “input” elements such as next instruction pointer, etc.)

Given this machine, one feeds an input state \(\sigma \in \Sigma\) through repeated applications of \(\delta\). So, for example, the \(n\)-th iteration of the machine is the value \(\delta(\delta(\delta(\dots(\sigma)\dots))) = \delta^n(\sigma)\). When we reach a special state \(\omega \in \Sigma\) that we designate the “halting state,” the machine halts. (We can refine this to include any state \(\omega\) in the set of halting states \(\Omega\), if we wish—and in fact, later intcode simulators do).

We can now model an interpreter for this state-machine as the closures of \(\delta\)—call it \(\Delta\)—which is the application of \(\delta\) until we reach a halting state. Alternately, if we make each halting state a fix-point (if \(f(x) = x\), then \(x\) is a fix-point of \(f\)), then \(\Delta\) is still the closure of \(\delta\), though now until we reach the fix-point.

I am least proud of the fact that this version used exceptions. Ick.

Part 2

9b0f469

I wrapped some List exceptions for convenience. I also wrapped instructions with their parameters and added a decode function that reads memory to create the next instruction. Most of the rest is unchanged.

Part 2 mainly consisted of searching a (relatively small) search-space for values which produced a certain target, so I implemented that outside of all the intcode structures. I slapped together a search space (cartesian product), a runner function, and a checker function. Then I added a first function which finds the first (noun, verb) pair that produces the requisite target. It constrains the search space to the given bound (later chosen to be n=99).

Then the solution consists of loading up the program, running it in the search space, and extracting the answer from the pair.

3ad3126

This commit was the slight refactoring to use more standard naming conventions. SML programmers typically prefer lower case, then camelCase, for types and identifiers. Structures are the special guys that get TitleCase, while functors require Fn at the end and signatures are in SHOUTYCAPS.

fa5bcae

This very short commit was another refactor: semantically, I tend to associate compilation with source-transformation. All we do with an intcode program is load it into a runnable state, so no transforming done there.

While we’re discussing these kinds of programs (compilers and interpreters), I should mention that I’m probably going to write an intcode assembler by the time this is all said and done. It’s not too difficult. Going the other way is impossible without executing the code, though, as an instruction might later be read and modified by a different instruction. I could even support labels… hm .

Categories: Blog

Previous Next

Back to posts