ICFP Programming Contest

  • [アーティクル]

This years' installment of the ICFP Programming Contest is coming up this weekend.  For those who haven't had the chance to try out this programming contest before, I definitely recommend it.  I've done the contest 3 of the last 5 years, and each time has been an amazing experience.  This year, we've got a couple of teams here who'll be doing the contest, and we're excited to see what the organizers have in store. 

The task for the contest changes quite a bit each year, but tends to incorporate themese like implementing interpreters/compilers for simple languages/runtimes and solving optimization or state-space exploration problems related to these interperpreters or programs written to run on these interpreters.  In each of the last two years' contests, some really fun puzzle elements have been incoporated into the contest, along with richer storytelling.

"Universal Machine" in F#

Of the years I've done the ICFP programming contest, my favorite so far has been the 2006 contest.  It was truly an inspired creation, and I am rather in awe of the group from CMU who put it together.  If you didn't do the contest in 2006, you can still go back to the site and try it out - which I can definitely recommend.

The contest started seemingly simply - pointing to a spec for a virtual machine (the "UM"), a binary to run on the virtual machine (the "Codex") and a "decryption key" to use: '(\b.bb)(\v.vv)06FHPVboundvarHRAk'. 

Earlier this week, to re-live some of the fun of the 2006 contest, and to get mentally ready for this years contest, I re-implemented the UM, this time in F#.  Here's what it looks like (take a look at the spec linked above for an expalanation of what it's doing):

 open System
open System.IO

type UM(p0 : byte[], input : Stream,  output : Stream) = 

    // Read byte[] in as little-endian uint[]
    let p0AsUInts =
        [| for i in 0..4..(p0.Length-4) ->
            ((uint32 p0.[i])<<<24) + 
            ((uint32 p0.[i+1])<<<16) + 
            ((uint32 p0.[i+2])<<<8) + 
            ((uint32 p0.[i+3])) |]
    // The resizable array of memory pages starts with just the input
    let mem = ResizeArray.create 1 p0AsUInts
    // The registers are initialized to 0
    let reg = [|0u;0u;0u;0u;0u;0u;0u;0u|]

    // The main loop of the interpreter.  Should be *fast*.
    let rec cycle finger =
        let arr = mem.[0]
        let op = arr.[finger]
        let code = op >>> 28
        let (a,b,c) = (int ((op >>> 6) &&& 0b111u), int ((op >>> 3) &&& 0b111u), int ((op) &&& 0b111u))
        let (a2, value) = (int (op >>> 25) &&& 0b111, op &&& 0b1111111111111111111111111u)
        match code with
        | 0u -> (if reg.[c] <> 0u then reg.[a] <- reg.[b]); cycle (finger+1)
        | 1u -> (reg.[a] <- mem.[int reg.[b]].[int reg.[c]]); cycle (finger+1)
        | 2u -> (mem.[int reg.[a]].[int reg.[b]] <- reg.[c]); cycle (finger+1)
        | 3u -> (reg.[a] <- reg.[b] + reg.[c]); cycle (finger+1)
        | 4u -> (reg.[a] <- reg.[b] * reg.[c]); cycle (finger+1)
        | 5u -> (reg.[a] <- reg.[b] / reg.[c]); cycle (finger+1)
        | 6u -> (reg.[a] <- ~~~ (reg.[b] &&& reg.[c])); cycle (finger+1)
        | 7u -> ()
        | 8u -> (mem.Add(Array.zeroCreate (int reg.[c])); reg.[b] <- uint32 (mem.Count - 1)); cycle (finger+1)
        | 9u -> (mem.[int reg.[c]] <- [||]); cycle (finger+1)
        | 10u -> (output.WriteByte(byte reg.[c])); cycle (finger+1)
        | 11u -> (reg.[c] <- uint32 (input.ReadByte() % 255)); cycle (finger+1)
        | 12u -> (if reg.[b] <> 0u then mem.[0] <- Array.copy mem.[int reg.[b]]); cycle (int reg.[c])
        | 13u -> (reg.[a2] <- value); cycle (finger+1)
        | _ -> failwith "Did not understand %A" (op, code, a, b, c)

    /// Start the Universal Machine running
    member this.Run() =
        cycle 0

let program = File.ReadAllBytes("codex.umz");
let ee = UM(program, Console.OpenStandardInput(), Console.OpenStandardOutput())

//Try the following if too much is printed to the screen 
//let ee = UM(program, Console.OpenStandardInput(), new FileStream("umix.um", FileMode.Create))ee.Run()

Performance

This code is doing a lot of bit-level operations in F#.  The meat of the code is the tight loop that runs executing the "cycle" function.  Since this is the runtime that the provided binary will run on, it needs to be fast.  And, fortunately, it is.  On my laptop, this loop runs about 15million iterations per second.  Of course, there are opportunities to improve on the performance of this code, but this turns out to be fast enough for the problem, and it's convenient that you get this performance profile by default.

 

That Doesn't Look Very Functional?

This code is not particularly 'functional'.  But it is totally reasonable F# code.  We often talk about F# as a hybrid functional, imperative and OO programming language.  This is an example where the problem domain really suggests the use of some imperative programming ideas.  The problem defines some global state: the memory, and the registers.  Since we're going to be modifying these constantly during the execution of the runtime, it makes sense to use mutable arrays to store the contents.  F# makes this nice and easy to do.

 

Wrapping it up with a little OO

As I menionted in a previous blog post, it's really easy to transition between prototyping and component design with F#.  The code above wraps up the state and algorithm for the UM in a simple type definition.  This provides nice encapsulation and abstraction over the specific binary to run, and the input and output streams to use.  And it also wraps up the F# code in a type which could just as easily be consumed from C# or any other .NET langauge.

Comments