Saturday, November 12, 2011

Defeating the blank page

Programmers have two ways to approach implementation of complex programs:


  • Start by building bricks, combine them to build larger bricks, repeat until the brick is actually a house.
  • Work the other way around.


  • The second approach is actually the more sensible one for new problems. In general, you know what is the problem you want to solve, not how to solve it. It's therefore easier to write the top-level of an application first.
    The obvious problem is: On what do you build the top level?

    There is a trick I used in F# that I wanted to share.
    Consider the following problem: I want to implement a racing game, which requires multiple data structures to represent the track. In the track editor, the track is basically a curve controlled by a number of points and directions. In the game, the track is a set of triangles used for rendering and simulation. The problem is to convert a track segment defined using the first representation to the second.
    A track segment is either linear (it connects two control points), a fork (for the entrance and exit of the pit lane) or a bridge. We can imagine other kinds of segments (+ and T -shaped crossings), but that's enough for a start.
    I start with this function:
    let triangulate segment =
       match segment with
       | Linear data -> ()
       | Fork data -> ()
       | Bridge data -> ()
    
    It's not doing much, obviously. Let's look at the easy case first. A solution would be to get an ordered set of vertices for one side of the road segment, and another set for the other side.
    | Linear data ->
       let leftSide = getLeftSide data
       let rightSide = getRightSide data
       knit triangles leftSide rightSide
    
    This code isn't valid, because getLeftSide, getRightSide knit and triangles aren't defined. Let's add them as parameters to triangulate:
    let triangulate getLeftSide getRightSide knit triangles segment =
       match segment with
       | Linear data ->
          let leftSide = getLeftSide data
          let rightSide = getRightSide data
          knit triangles leftSide rightSide
    
    After a few more iterations of this I get the following function:
    let triangulate getLeftSide getRightSide getLeftSideOfFork getLeftInner getRightSideOfFork getRightInner intersect glue knit triangles segment =
        let triangulateLinear data =
            let leftSide = getLeftSide data
            let rightSide = getRightSide data
            knit triangles leftSide rightSide
    
        match segment with
        | Linear data ->
            triangulateLinear data
    
        | Fork data ->
            let outSide0 = getLeftSideOfFork data
            let inSide0 = getLeftInner data
            let outSide1 = getRightSideOfFork data
            let inSide1 = getRightInner data
            let inSide0, inSide0', inSide1, inSide1' = intersect inSide0 inSide1
            knit triangles outSide0 (glue inSide0 inSide1')
            knit triangles outSide1 (glue inSide1 inSide0')
            knit triangles inSide0' inSide1'
    
        | Bridge data ->        
            triangulateLinear data.under
            triangulateLinear data.over
    
    The function takes quite a few parameters, maybe too many. I can clean this up later after I have implemented getLeftSide and all other functions.

    Notice how far I can get never worrying about types, yet I never need to worry about whether the parts fit together.

    This way of writing code has helped me get over a number of situations where I was suffering some sort of "blank page syndrome", not knowing where to start to tackle a complex problem.
    Of course, there is no guarantee that the final implementation will keep the same architecture, but at least I'm going forward!