[Haskell-cafe] Reflections on the ICFP 2009 programming contest

Justin Bailey jgbailey at gmail.com
Mon Jun 29 14:40:28 EDT 2009

Anyone have thoughts to share? I'd love to read others' experiences
but there isn't much coming up with searches or on redditt ...

I was happiest with the VM I implemented. Sadly, I wasn't able to
solve any of the scenarios, but my VM ran damn fast. That didn't seem
to matter so much this year as it did two years ago - I think I am
still scarred by Endo's DNA ..

Anyways, for those who care, the heart of my VM implementation was a
monadic fold over the program, with a mutable array representing the
machine's memory, all inside ''runSTUArray.'' I used a simple data
type to represent the machine:

data Machine = Machine { instrs :: [OpCode]
                       , dataMem :: UArray Int Val
                       , outputs :: UArray Int Val
                       , status :: !Int
                       , inputs :: IntMap Val }

where ''dataMem'' holds the data memory area. To execute a program, I
folded over the ''instrs'' list and updated memory as I went:

exec :: Machine -> Input -> Machine
exec m@(Machine { instrs = instrs }) inps =
    let m' = m { inputs = readInputs inps }
        newMem = runSTUArray $ do
            mem' <- thaw (dataMem m)
            foldM (step m') mem' (zip instrs [0..])

I considered ''unsafeThaw'' in the above, but performance didn't hurt
me much and it seemed safer. Since I was recording all output I was
worried that would break referential integrity. In any case, when the
fold was finished I just assigned ''newMem'' to the new machine and
moved to the next iteration.

''step'' takes the mutable array and updates it while the program
executes. I won't show the whole body, as it just a separate
definition for each opcode, just the type:

  step :: Machine -> STUArray s Int Val -> (OpCode, Addr) -> ST s
(STUArray s Int Val)

The only downside to this approach was the machine had three mutuable
states: memory, output, and status. runSTUArray only wants to return a
single array so inside step I had to hold all values in one array. Not
a big deal but a little ugly.

I kept a diary of my experience over the weekend at
http://icfp2009.codeslower.com. I started out with such optimism ...
Stil, I'm glad to have done it. Lots of fun! My thanks to the

More information about the Haskell-Cafe mailing list