June 25, 2009 -- 9:00 AM

This site will serve as a diary and reference for my work on the upcoming ICFP 2009 programming contest. All code committed will be available on GitHub and can be cloned from git://github.com/m4dc4p/func-n-stein.git.

June 25, 2009 -- 11:43 AM

All times PDT, by the way.

Downloaded the spec, read through it, seems a lot like last years problem. I have to implement a virtual machine and then solve a bunch of orbit problems? Sounds doubly tough. For starters I think I will implement something to write the submission format, and submit an empty solution. We'll see what happens.

June 25, 2009 -- 2:03 PM

Got code to write a solution and have submitted an empty solution. Not sure if double representation will be written correctly - does Haskell write it in "IEEE 764" notation automatically? Had to do some pointer conversions to write doubles as binary data:

          v <- allocaBytes 8 $ \p -> do 
                   poke p val 
                   mapM (\i -> peekElemOff (castPtr p) i) [0, 1]

''val'' is our double value. I write to 8 byte memory location, then read out as two 32-bit values:

          -- write to file
          hPutWord (int2Word addr)
          hPutWord (v !! 0)
          hPutWord (v !! 1)

''hPutWord'' fixes the type, as it takes a Word32 and writes it to a file:

 hPutWord :: Word32 -> IO ()
 hPutWord w = with w $ \p -> do
      hPutBuf h p (sizeOf w)

I do se a bug above, where I am not writing the value in little-endian order. Better fix that!

June 25, 2009 -- 2:52 PM

Fairly confident output file format is being written correctly. At least the competition server doesn't complain When I submit solutions that write to the correct config port. Also cabalized early so it won't be too painful later -- I expect dependencies to grow.

Now I'll write some code to read the executable file format.

June 25, 2009 -- 3:37 PM

Got some code that seems to read the executable file format (''ReadObf.hs''). Lots of grungy work with pointers, bits and bytes here. Reading words and doubles is a lot like writing them:

        getWord p i = do
            v <- peekElemOff (castPtr p) i
            return $ (v :: Word32)
        getDouble p i = do
            v <- peekElemOff (castPtr p) i
            return $ (v :: Double)

where ''p'' points to the buffer containing the file in memory and ''i'' is an absolute offset to start reading from. For some reason the file format alternates between (instr, val) and (val, instr). I created two nearly identical functions to read each:

        toInstrE i = do
            -- With even addresses, instruction comes first.
            instr <- getWord p i 
            val <- getDouble p (i + 1)
            return $ Instr instr val
        toInstrO i = do
            -- With odd addresses, value comes first.
            val <- getDouble p i
            instr <- getWord p (i + 2)
            return $ Instr instr val

''Instr Word32 Double'' will represent a raw instruction, before it is translated to an op code/value pair for the machine. Then I need to iterate over the array to convert each 96-bit value into an ''Instr'' value. ''foldM'' looked like the right fit:

    instrs <- foldM (\is (f, i) -> f i is) [] (zip (cycle [applyE, applyO]) [0,3..size])

Ouch! ''applyE'' and ''applyO'' let me alternate the function I am using to convert values:

        applyE i instrs = do
            is <- toInstrE i
            return (is : instrs)
        applyO i instrs = do
            is <- toInstrO i
            return (is : instrs)

''[0,3..size]'' give me the indices to read process every 3 words in the buffer. ''cycle [applyE, applyO]'' gives me a list of alternating functions to apply. I zip those together and fold. My instructions pop out the other end!

June 25, 2009 -- 10:51 PM

Everything looked good until I tried to convert the bytes read from the executable format to opcodes. "Unrecognized D-type op: 9" -- WTF? All I can say is - bastards! The instructions are stored in reverse binary. For example, the spec says a D-type op code occupies bits "31 - 28", with value from 0x1 - 0x6. I assumed the bits were in 28 - 31, in that order. No! I am pretty sure 0x1 is represented as "1000" (from 31 - 28), not "0001"! Well, hopefully this page on bit-twiddling tricks has an algorith for reversing a word. I should be able to hide that from the rest of the program and convert to opcodes.

June 26, 2009 -- 6:40 AM

I'm still not sure if the instruction word needs to be reversed, because I wasted a bunch of time trying to figure out why I was reading illegal instructions in the .obf file. I went to bed last night stuck -- it seemed I was reading the file incorrectly, or at least that's all I could guess. I figured it had something to do with ''little-endianess,'' which I felt unsure of. I was all ready to go back to first principles and experiment with reading and writing obf files. Fortunately I decided to look over the problem description again while I was eating breakfast. Lo and behold, I had the executable format wrong -- I coded it so that the instruction came first on even frames. That's wrong -- it's odd frames! Making that small switch allowed me to read the obf file correctly.

Now to determine if the instructions are stored reversed or not.

June 26, 2009 -- 6:53 AM

Bingo! No reversal needed. Hallelujah. A quick test showed that parsing the obf file failed with the reversal added. Ergo, it must be wrong. Now let's implement our machine.

June 26, 2009 -- 2:45 PM

The machine seems to be working and is fairly performant, though not amazing. 10000 iterations on bin1 go pretty fast. 100,000 or 1,000,000 get progressively worse. Hopefully it won't be too bad. Simulating a machine with mutable memory is always interesting in Haskell. The magic of ''runSTUArray'' is saving me here. Each iteration of the machine is run inside the ST monad, which allows me to modify a mutable array (from Machine.hs):

step :: Machine -> STUArray s Int Val -> (OpCode, Addr) -> ST s (STUArray s Int Val)
step m mem (op, addr) = ...

''mem'' is my mutable array. While the machine executes its program once, I can update the array as much as I like. You can see that in action in the ''exec'' function:

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..])

''foldM'' takes care of executing all instructions, while step updates the mutable array as needed. The final array is returned by runSTUArray as an immutable array, meaning its like any other Haskell value.

This is a fast way to deal with mutable values but there are some downsides. Since I want to keep a trace of the output around, I can't reuse the same array on subsequent iterations (at least, not safely). That is why you see ''thaw'' in there, instead of ''unsafeThaw''.

The second is that runSTUArray can only return a single array. The machine has several mutable values: memory, output ports, and the status register. I have no idea if output ports can be written to more than once, but better safe than sorry. So the mutable array above actually holds all those values, and I split it up at the end of each execution (where ''newMem'' is the final state of memory after the iteration):

    outputs = runSTUArray $ do
        -- output ports after memory in array.
        newListArray (0, outputSize) (map (newMem !) [memSize .. memSize + outputSize - 1])
    statusA = runSTUArray $ do
        -- status bit at end of memory
        newListArray (0, 1) [newMem ! (memSize + outputSize)] 

Since I still have no idea how to do the math for these problems, I'm going to try and use chalkboard (from Hackage) to write a visualizer so I can see what these orbits look like ...

June 28, 2009 10:45 AM

Got visualization for the first problem working with Chalkboard last night. What a great little library. Funny enough, it's also by Andy Gill, one of the contest organizers. My only complaint is speed - it's unbearably slow at resoulutions past 200 x 200. Good enough for me though

I found the site with the math I need for at least the first problem, http://www.braeunig.us/space/. Very understandable and much clearer than the Wikipedia entry referenced in the contest document.

Reading the contest blog, it seems the first problem is actually scored based on fuel used, not remaining. Hohmann is the wrong approach to the problem in that case, but I'm still going to implement it just to see how it behaves.

June 29, 11:00 AM

I submitted my final program and traces for the first scenario. Unfortunately I never managed to get a score. My visualization worked beautifully, and it seemed like I was making the transfer orbit correctly. However, I suspect I'm reading some value backwards or have a sign error. Ah well, it was a fun time and I thought the machine I implemented was pretty slick. Very fast and didn't leak a lot of memory. Here's to next year!

For the curious, the repo is available from git://github.com/m4dc4p/func-n-stein.git. With the Haskell Platform installed it's really easy to build. First get chalkboard and chalkboard-viewer from Hackage (or use caball install). In the source directory, type:

> cabal build
> dist\build\func-n-stein\func-n-stein -s hohmann -c 1001

and the first scenario will be run. To visualize it:

> dist\build\hohmann-vis\hohmann-vis hohmann_1001.trc

Only the first scenario is supported, with config values 1001 - 1004.