The Advent of Code series is back (from last year…)

Part 1

Another intcode challenge! Now, we’re given a new program, new opcodes (I/O!!), and addressing modes (encoded inside opcodes). Also, the program counter no longer constantly increments in groups of 4 (i.e., some opcodes are shorter or longer than others in number of operands). Our job is to feed 1 into a diagnostic program and record the output once it’s successful.

530eaa2

Just copying the old code and the new input.

a33986c

This is a big ol’ rewrite. I added an either type based on scala’s for error/result types; I eliminated exceptions completely using it and dedicated constructors; I grouped all the structures inside each other…

Interestingly, this refactor introduced a new mechanism for reading and writing memory. read and write as primitives still operate in terms of Either.R and Either.L (success and failure). But truly carrying out and using the results uniformly is done with Either.lift: for the try* functions, the caller provides an error handler and a success handler (which must return the same type, typically some kind of option or state or some such). The result is a function which will operate on the results of the primitives (which still must be called: either directly, or via the next functions for some easy reads). One such usage is here:

datatype inst = ADD of arith_addrs
              | MULT of arith_addrs
              | HALT
              | UNKNOWN of opcode
              | MEM_ERR of Memory.readErr
val tryRead = Memory.tryRead MEM_ERR
fun createArith
  (f : arith_addrs -> inst)
  (m : Memory.memory)
  (ip : Memory.addr)
  : inst =
  let val newIp = ip + 4
  in
    tryRead (fn a =>
    tryRead (fn b =>
    tryRead (fn d => f {srcA=a, srcB=b, dest=d, newIp=newIp})
    (Memory.next3 ip m))
    (Memory.next2 ip m))
    (Memory.next ip m)
  end

We alias tryRead to use the MEM_ERR constructor as an error handler. An arithmetic instruction consists of sequenced reads which are combined into an argument to the given instruction constructor. This is used by the decoder to create instructions for evaluation (which also relies on tryRead to fetch an instruction to decode).

In the actual CPU, we employ similar tricks to read several addresses, compute a result, and write it back to memory; the result is a value of type state this time, instead of a value of type inst.

In particular, this new form typically necessitates encoding errors in the type system (either for states or instructions, in these examples).

95cd8a9

This is a doozy. I managed (finally) to functorize the structures and allow for some separation of concerns. Unfortunately, some things still leak through (as seen in the translation functions from various unspecified types to more concrete ones; this was necessary even with the sharing constraints). Months later, I now see the solution may have been to duplicate some type names and increase the sharing constraints. (The DecoderFn’s constraint that Memory use ints seems unavoidable.)

In spite of a few ugly spots, the whole thing comes together remarkably well. I even added an IO signature to encapsulate input and output routines, and an StdIO structure that uses the standard streams.

Intcode is built up by applying functors, and then a Reader struct is built using the intcode program type.

8679875

At long last, we are ready to support addressing modes. We add a mode to the decoder, as well as encode the notion of parameter and destination “registers” in the type system. A parameter includes a function that carries out the read, while a destination includes a function that carries out the write. We thus enforce that some parameter sets are read from while others are written to.

We add a couple of digit-manipulating utilities in order to work with the opcodes.

Finally, we add the parameter/destination encoding into the actual decoder. This certainly complicates reads and writes on the instruction execution side, but it is necessary; when creating an instruction, we have to determine what kinds of registers and modes go together, and set up the appropriate arguments. Execution then pulls them apart and invokes the appropriate sequence of functions. In effect, these instruction parameter sets encode the reads and writes, so the CPU has to invoke memory primitives less often. (In fact, I believe the CPU only uses try* functions now.)

Lastly, we set up a dummy IO structure that provides the appropriate diagnostic input.

1924968

Correcting a bug in the use of modes for writes led me to solve the challenge (the spec is vague on how write modes work…).

Part 2

More opcodes! Yayyyy! And they implement conditional branching…

806e183

Another copy of programs and inputs. I added the new diagnostic code for the challenge here too.

80ae8cc

A boring clarification.

17d18ef

The actual solution.

We add the extra opcodes (a piece of cake at this point; a couple of types, some functions + constructors, and an evaluation function that all build on the read/write mechanisms and the use of functions as values). Most of the heavy work is in the decoder, which creates jump and test instructions. The complex work is in the CPU, though, which has to read appropriate values and handle the results, invoking callbacks as necessary to carry out computations for new instruction pointers or values to test.

I’m learning that the try* functions create an inversion of control flow, where reads/writes appear to happen at the bottom of the code (in the latter parameters). This is also where the computation of what values to write appears, somewhat obfuscating the intent. But the resulting state or value is front-and-center (literally).

Categories: Blog