Functional I/O (Historical Debugging)

[Part 14 of the FScheme series]

Historical Debugging in VS2010 is quite the engineering feat! We can actually pull off something similar in our interpreter with amazing ease. Because of the pure nature of our functional I/O system (last two posts) and the already centrally managed world state and input it’s very straight forward to implement.

Adding a Historian

First we need to keep a history of the world. We’ll use a double linked list so we can easily walk backward and forward in time:

let mutable history = new LinkedList<Expression>()
let mutable current = new LinkedListNode<Expression>(Symbol(“Dummy world”))

On each ‘tick’ we’ll append to the history. We’ll also allow stopping and restarting of the passage of time (with a ‘running’ flag). We’re blindly tracking each entire world state. You can imagine a more memory-efficient implementation that only tracks input history and replays forward from the initial state or that maintains only “key frames” of computed world state and partially replays forward as needed. That would be interesting to build but let’s start with the simplest thing that could possibly work:

let form () =
    let f = new Form(Text = “Canvas”, Width = w * s + 16 – 1, Height = h * s + 38 – 1, Visible = true)
    let running = ref false
    let time slice =
        running := false
        if slice <> null then
            current <- slice
            paint (); f.Refresh()
    let debug = function
        | Keys.S -> running := false
        | Keys.G -> running := true
        | Keys.Left -> time current.Previous
        | Keys.Right -> time current.Next
        | Keys.W -> print current.Value |> printfn “World: %s”
        | _ –> ()
    let t = new Thread(new ThreadStart(fun () –>
        while true do
            if running.Value then
                current <- history.AddAfter(current, eval’ “tick”)
                paint (); f.Refresh()
    f.Paint.Add(fun a -> lock bmp (fun () -> a.Graphics.DrawImage(bmp, 0, 0)))
    f.MouseMove.Add(fun a -> mouseX := a.X / s; mouseY := a.Y / s)
    f.Closing.Add(fun _ -> t.Abort())
    f.KeyDown.Add(fun a -> debug a.KeyCode)
    current <- history.AddFirst(eval’ “init”)
    running := true

The system behaves just as it always has; ticking off the progress of time upon being (run). But now we can press ‘S’top or ‘G’o to suspend things, we can press/hold left and right arrow keys to move back and forth through history, and we can print the current world state with ‘W’.

Now you can cheat at the “Pong” game from last post. If you miss the ball, just back up and try again; rewriting history!

Also, you might notice bugs in the implementation. For example the ball appears to go off the screen when it bounces. You can flip through the history to just before and after it happens and look at the world state. Sure enough, it goes one pixel off before reversing directions… great. Jump on CodePlex and fix it! 🙂

The beauty of debugging this style of functional I/O code is that any bug is sure to be found in the transition from one state to the next. The ‘tick’ function, given a particular state, is returning the wrong thing. Just pin down which transition is broken and fix the logic or assumption in the ‘tick’. If you’re into TDD then first add a unit test passing the particular state in and asserting the expected result. Pure functions are so very much easier to test and debug.

[Side note: I want to plug another paper worth reading if you’re interested in functional I/O systems.]

Comments (2)

  1. Tom says:

    I am a budding functional programming zealot, and have been crunching through every resource I can find on F#.  Additionally, I recently began working through Structure and Interpretation of Computer Programs, which is exposing me to Scheme and all of its wonders.  This blog series is awesome, particularly the resources for describing simulation and the showing how to bake Scheme into F# (if one desires).  My main goal is to build an extensible discrete event simulation framework using functional programming and some non-imperative programming paradigms.  The linked papers and coding samples have provided another dimension of understanding for me (after ~5 books and multiple papers).  Great writing, great examples.  Thanks      

  2. Sounds like an interesting project! Did you see Conal Elliott’s comment ( a while back? That guy has done some amazing work in the area.

    Also, BTW, hey I envy you going through SICP for the first time – it’s a real treat! Savor it! Hopefully you’ve stumbled on the old lecture videos, and Brian Harvey’s too:

    Have fun!