Intcode

This Intcode interpreter is defined across multiple Advent of Code days:

• https://adventofcode.com/2019/day/2
• https://adventofcode.com/2019/day/5
• https://adventofcode.com/2019/day/7
• https://adventofcode.com/2019/day/9

This implementation works with the following passes:

1. Parse input text file into a list of numbers
2. Execute op codes to single-step input/output effects.
3. Execute single-stop effects into big-step effects.

Common use modes:

• List functions: intcodeToList
• Individual machine step processing: Step, new, step
• Input/output interpretation: Effect, new, run

Simple interface

intcodeToList

Arguments

:: [Int]

initial memory

-> [Int]

inputs

-> [Int]

outputs

Run a given memory image as a list transducer.

Use effectList when you want to provide a specific Effect.

Throws: IntcodeFault when machine faults or too few inputs are provided.

>>> intcodeToList [3,12,6,12,15,1,13,14,13,4,13,99,-1,0,1,9] <$> [[0],[10]]
[[0],[1]]

>>> intcodeToList [3,3,1105,-1,9,1101,0,0,12,4,12,99,1] <$> [[0],[10]]
[[0],[1]]

>>> :{
>>> intcodeToList
>>> [3,21,1008,21,8,20,1005,20,22,107,8,21,20,1006,20,31,
>>> 1106,0,36,98,0,0,1002,21,125,20,4,20,1105,1,46,104,
>>> 999,1105,1,46,1101,1000,1,20,4,20,1105,1,46,98,99]
>>> <$> [[7],[8],[9]]
>>> :}
[[999],[1000],[1001]]

runIO :: Effect -> IO ()

Run intcode program using stdio. Non-ASCII outputs are printed as integers.

>>> runIO (run (new [104,72,104,101,104,108,104,108,104,111,104,33,104,10,99]))
Hello!

Machine state

data Machine

Machine state.

Constructors

Machine

Fields

• pc :: !Int

  program counter

• relBase :: !Int

  relative base pointer

• memory :: !(IntMap Int)

  memory updates

• image :: !(PrimArray Int)

  initial memory

Instances

Eq Machine

Defined in Intcode

Methods

(==) :: Machine -> Machine -> Bool

(/=) :: Machine -> Machine -> Bool

Ord Machine

Defined in Intcode

Methods

compare :: Machine -> Machine -> Ordering

(<) :: Machine -> Machine -> Bool

(<=) :: Machine -> Machine -> Bool

(>) :: Machine -> Machine -> Bool

(>=) :: Machine -> Machine -> Bool

max :: Machine -> Machine -> Machine

min :: Machine -> Machine -> Machine

Show Machine

Defined in Intcode

Methods

showsPrec :: Int -> Machine -> ShowS

show :: Machine -> String

showList :: [Machine] -> ShowS

(!)

Arguments

:: Machine

machine

-> Int

position

-> Int

value

Memory lookup from 0-based index.

new

Arguments

:: [Int]

initial memory

-> Machine

new machine

Construct machine from a list of initial values starting at address 0. Program counter and relative base start at 0.

set

Arguments

:: Int

position

-> Int

new value

-> Machine

-> Machine

Update the value stored at a given location in memory.

memoryList :: Machine -> [Int]

Generate a list representation of memory starting from zero. This can get big for sparsely filled memory using large addresses. Returned values start at position 0.

>>> memoryList (set 8 10 (new [1,2,3]))
[1,2,3,0,0,0,0,0,10]

Effects

data Effect

Possible effects from running a machine

Constructors

Output !Int Effect

Output an integer

Input (Int -> Effect)

Input an integer

Halt

Halt execution

Fault

Execution failure

Instances

Show Effect

Defined in Intcode

Methods

showsPrec :: Int -> Effect -> ShowS

show :: Effect -> String

showList :: [Effect] -> ShowS

run :: Machine -> Effect

Big-step semantics of virtual machine. The implementation details of Machine are abstracted away and the program behavior can be observed by interpreting the various Effect constructors.

>>> run (new [1102,34915192,34915192,7,4,7,99,0])
Output 1219070632396864 Halt

>>> run (new [3,1,99])
Input <function>

(>>>) :: Effect -> Effect -> Effect infixl 9

Compose two effects together. Outputs from first argument are used as inputs to the second effect. Composed effect halts when the second machine halts.

>>> let mult n = Input (\i -> Output (i*n) Halt)
>>> let add  n = Input (\i -> Output (i+n) Halt)
>>> effectList (mult 3 >>> add 1) [4]
[13]

effectList

Arguments

:: Effect

program effect

-> [Int]

inputs

-> [Int]

outputs

Evaluate a program's effect as a function from a list of inputs to a list of outputs.

Throws: IntcodeFault when machine faults or too few inputs are provided.

followedBy :: Effect -> Effect -> Effect

Run first effect until it halts, then run the second effect.

>>> Output 1 Halt `followedBy` Output 2 Halt
Output 1 (Output 2 Halt)

feedInput

Arguments

:: [Int]

inputs

-> Effect

-> Effect

Provide an input to the first occurrence of an input request in a program effect. It is considered a fault if a program terminates before using the input.

>>> let mult n = Input (\i -> Output (i*n) Halt)
>>> feedInput [6] (mult 5)
Output 30 Halt

Small-step

data Step

Result of small-step semantics.

Constructors

Step !Machine

no effect

StepOut !Int !Machine

output

StepIn (Int -> Machine)

input

StepHalt

halt

StepFault

bad instruction

Instances

Show Step

Defined in Intcode

Methods

showsPrec :: Int -> Step -> ShowS

show :: Step -> String

showList :: [Step] -> ShowS

step :: Machine -> Step

Small-step semantics of virtual machine.

Opcodes

data Mode

Parameter modes

Constructors

Abs

absolute position

Imm

immediate

Rel

relative position

Instances

Eq Mode

Defined in Intcode

Methods

(==) :: Mode -> Mode -> Bool

(/=) :: Mode -> Mode -> Bool

Ord Mode

Defined in Intcode

Methods

compare :: Mode -> Mode -> Ordering

(<) :: Mode -> Mode -> Bool

(<=) :: Mode -> Mode -> Bool

(>) :: Mode -> Mode -> Bool

(>=) :: Mode -> Mode -> Bool

max :: Mode -> Mode -> Mode

min :: Mode -> Mode -> Mode

Read Mode

Defined in Intcode

Methods

readsPrec :: Int -> ReadS Mode

readList :: ReadS [Mode]

readPrec :: ReadPrec Mode

readListPrec :: ReadPrec [Mode]

Show Mode

Defined in Intcode

Methods

showsPrec :: Int -> Mode -> ShowS

show :: Mode -> String

showList :: [Mode] -> ShowS

data Opcode a

Opcodes parameterized over argument representations.

Constructors

Add !a !a !a

addition: c = a + b

Mul !a !a !a

multiplication: c = a * b

Inp !a

input: a = input()

Out !a

output: output(a)

Jnz !a !a

jump-if-true: if a then goto b

Jz !a !a

jump-if-false: if !a then goto b

Lt !a !a !a

less-than: c = a < b

Eq !a !a !a

equals: c = a == b

Arb !a

adjust-rel-base: rel += a

Hlt

halt

Instances

Functor Opcode

Defined in Intcode

Methods

fmap :: (a -> b) -> Opcode a -> Opcode b

(<$) :: a -> Opcode b -> Opcode a

Foldable Opcode

Defined in Intcode

Methods

fold :: Monoid m => Opcode m -> m

foldMap :: Monoid m => (a -> m) -> Opcode a -> m

foldr :: (a -> b -> b) -> b -> Opcode a -> b

foldr' :: (a -> b -> b) -> b -> Opcode a -> b

foldl :: (b -> a -> b) -> b -> Opcode a -> b

foldl' :: (b -> a -> b) -> b -> Opcode a -> b

foldr1 :: (a -> a -> a) -> Opcode a -> a

foldl1 :: (a -> a -> a) -> Opcode a -> a

toList :: Opcode a -> [a]

null :: Opcode a -> Bool

length :: Opcode a -> Int

elem :: Eq a => a -> Opcode a -> Bool

maximum :: Ord a => Opcode a -> a

minimum :: Ord a => Opcode a -> a

sum :: Num a => Opcode a -> a

product :: Num a => Opcode a -> a

Traversable Opcode

Arguments visited from left to right.

Defined in Intcode

Methods

traverse :: Applicative f => (a -> f b) -> Opcode a -> f (Opcode b)

sequenceA :: Applicative f => Opcode (f a) -> f (Opcode a)

mapM :: Monad m => (a -> m b) -> Opcode a -> m (Opcode b)

sequence :: Monad m => Opcode (m a) -> m (Opcode a)

Eq a => Eq (Opcode a)

Defined in Intcode

Methods

(==) :: Opcode a -> Opcode a -> Bool

(/=) :: Opcode a -> Opcode a -> Bool

Ord a => Ord (Opcode a)

Defined in Intcode

Methods

compare :: Opcode a -> Opcode a -> Ordering

(<) :: Opcode a -> Opcode a -> Bool

(<=) :: Opcode a -> Opcode a -> Bool

(>) :: Opcode a -> Opcode a -> Bool

(>=) :: Opcode a -> Opcode a -> Bool

max :: Opcode a -> Opcode a -> Opcode a

min :: Opcode a -> Opcode a -> Opcode a

Read a => Read (Opcode a)

Defined in Intcode

Methods

readsPrec :: Int -> ReadS (Opcode a)

readList :: ReadS [Opcode a]

readPrec :: ReadPrec (Opcode a)

readListPrec :: ReadPrec [Opcode a]

Show a => Show (Opcode a)

Defined in Intcode

Methods

showsPrec :: Int -> Opcode a -> ShowS

show :: Opcode a -> String

showList :: [Opcode a] -> ShowS

decode

Arguments

:: Int

opcode

-> Maybe (Opcode Mode)

Decode an instruction to determine the opcode and parameter modes.

>>> decode 1002
Just (Mul Abs Imm Abs)

Exceptions

data IntcodeFault

Error when a machine fails to decode an instruction.

Constructors

IntcodeFault

Instances

Eq IntcodeFault

Defined in Intcode

Methods

(==) :: IntcodeFault -> IntcodeFault -> Bool

(/=) :: IntcodeFault -> IntcodeFault -> Bool

Ord IntcodeFault

Defined in Intcode

Methods

compare :: IntcodeFault -> IntcodeFault -> Ordering

(<) :: IntcodeFault -> IntcodeFault -> Bool

(<=) :: IntcodeFault -> IntcodeFault -> Bool

(>) :: IntcodeFault -> IntcodeFault -> Bool

(>=) :: IntcodeFault -> IntcodeFault -> Bool

max :: IntcodeFault -> IntcodeFault -> IntcodeFault

min :: IntcodeFault -> IntcodeFault -> IntcodeFault

Read IntcodeFault

Defined in Intcode

Methods

readsPrec :: Int -> ReadS IntcodeFault

readList :: ReadS [IntcodeFault]

readPrec :: ReadPrec IntcodeFault

readListPrec :: ReadPrec [IntcodeFault]

Show IntcodeFault

Defined in Intcode

Methods

showsPrec :: Int -> IntcodeFault -> ShowS

show :: IntcodeFault -> String

showList :: [IntcodeFault] -> ShowS

Exception IntcodeFault

Defined in Intcode

Methods

toException :: IntcodeFault -> SomeException

fromException :: SomeException -> Maybe IntcodeFault

displayException :: IntcodeFault -> String