Monday, April 30, 2012

Modular programming for portable F# libraries

I've been battling a few more rounds with F# portable class libraries. Getting them to work on PCs wasn't a walk in the park, but it seems I've got it working at last. Although this particular problem is not the main topic of this post, I expect many will run into the same issue, so I'll dedicate a few lines to its resolution.

The setting

I have a portable F# library which performs some physics calculations. Typical stuff you would expect in a portable library. It's unimaginatively but aptly named PortableLibrary1.
There is also an F# application project to run the simulation in a windows console (as in "text console", no xbox fun involved at this stage yet) application.
The application project refers to the library project.

The problem

The application compiles fine, but crashes when run with an exception stating that some version of FSharp.Core.dll could not be loaded.

The solution

Insert the following lines into the app.config file in the application's project:

<runtime>
  <assemblyBinding xmlns="urn:schemas-microsoft-com:asm.v1">
    <dependentAssembly>
      <assemblyIdentity name="FSharp.Core" publicKeyToken="b03f5f7f11d50a3a" culture="neutral"/>
      <bindingRedirect oldVersion="2.3.5.0" newVersion="4.3.0.0"/>
    </dependentAssembly>
  </assemblyBinding>
</runtime>

Thanks to Brian and his answer on stackoverflow.

We can run portable code on the PC, but the problems I mentioned in my previous post are still there, namely:

  1. I can't reference functions and types from Microsoft.Xna.Framework because there is no portable version (that I know of).
  2. There are core functions that are not available in the portable core, e.g. Thread constructors.

I will show below a solution to these two problems (my apologies to all bird lovers out there).

Signatures and modules

F# has its origins in ML, and some ML languages (standard ML, Ocaml) offer a module system that separates interfaces (which are called signatures) and implementations (call structures). Unfortunately, the module system of F# isn't as powerful. It's probably difficult, if not impossible, to fully emulate modules in F#. Nevertheless, there may some nice aspects of ML modules that can be imitated in F#.
  • The module system distinguishes interfaces and implementations.
  • Signatures specify a number of related types and operations operating on them in an abstract way.
  • Structures provide a number of concrete types and functions satisfying the specification in the structure they implement.
A signature of vector math could look as shown below:

signature VectorMath
  type V
  val add: V * V -> V
  val dot: V * V -> float32
  val len: V -> float32

In the .NET world, there is something that might play the role of signatures, namely interfaces. The problem is how to express that module VectorMath should have a type V? Interfaces can be used to specify operations, but not nested types. In my solution, I have used generics:
type VectorMath<'V> =
    interface
        abstract Add : 'V * 'V -> 'V
        abstract Subtract : 'V * 'V -> 'V
        abstract Dot : 'V * 'V -> float32
        abstract Scale : float32 * 'V -> 'V
        abstract Len : 'V -> float32
        abstract Len2 : 'V -> float32
        abstract Zero : 'V
        abstract AreEqual : 'V * 'V -> bool
    end

Note that the dimension of the vector type V is not constrained. This signature allows to perform interesting operations on vectors regardless of whether we are working in 2d or 3d.
Operations that depend on the number of dimensions are found in additional signatures:
type Vector2Math<'V> =
    interface
        inherit VectorMath<'V>
        abstract Cross : 'V * 'V -> float32
        abstract UnitX : 'V
        abstract UnitY : 'V
        abstract Create : float32 * float32 -> 'V
    end

type Vector3Math<'V> =
    interface
        inherit VectorMath<'V>
        abstract Cross : 'V * 'V -> 'V
        abstract UnitX : 'V
        abstract UnitY : 'V
        abstract UnitZ : 'V
        abstract Create : float32 * float32 * float32 -> 'V
    end

Modules implementing these signatures are written using any .NET type that can implement interfaces. In F#, discriminated unions do the job. As a side note, I tend to use single-discriminant DUs a lot in my F# code. I see them as C's typedefs the way they should have been.
type XnaVector3Math =
    | XnaVector3Math
    interface PortableLibrary1.Vector3Math<Vector3> with
        member this.Add(v1, v2) = v1 + v2
        member this.Subtract(v1, v2) = v1 - v2
        member this.Scale(x, v) = x * v
        member this.Dot(v1, v2) = Vector3.Dot(v1, v2)
        member this.Cross(v1, v2) = Vector3.Cross(v1, v2)
        member this.Len(v) = v.Length()
        member this.Len2(v) = v.LengthSquared()
        member this.AreEqual(v1, v2) = v1 = v2
        member this.UnitX = Vector3.UnitX
        member this.UnitY = Vector3.UnitY
        member this.UnitZ = Vector3.UnitZ
        member this.Zero = Vector3.Zero
        member this.Create(x, y, z) = new Vector3(x, y, z)

Keep in mind the problem I wanted to solve was how to remove the dependency on the XNA dll from the portable library. The interfaces are part of the portable library, the implementation is in the application's code.
The same method can be used to send missing bits of Thread from the application (which has access to the missing bits) to the portable code.

Using signatures

The code for the physics simulation is shown below, not so much for its value as a physics engine, but to judge of the usability of signatures.
type SystemState<'V> =
    { mass : float32[]
      pos : 'V[]
      speed : 'V[] }

let computeForces (ops : #VectorMath<'V>) state =
    let forces =
        [|
            for mass, pos in Array.zip state.mass state.pos do
                let force =
                    Array.zip state.mass state.pos
                    |> Array.map (fun (mass', pos') ->
                        if ops.AreEqual(pos, pos') then
                            ops.Zero
                        else
                            let relPos = ops.Subtract(pos', pos)
                            let dist = relPos |> ops.Len
                            ops.Scale(mass * mass' / (dist * dist * dist), relPos))
                    |> Array.fold (fun x y -> ops.Add(x, y)) ops.Zero
                yield force
        |]

    forces

let update (ops : #VectorMath<'V>) dt state =
    let inline (.*) k v = ops.Scale(k, v)
    let inline (.+.) v1 v2 = ops.Add(v1, v2)

    let forces = computeForces ops state
    let accels =
        Array.zip state.mass forces
        |> Array.map (fun (mass, force) -> (1.0f / mass) .* force)

    let speeds =
        Array.zip state.speed accels
        |> Array.map (fun (speed, accel) ->
            speed .+. (dt .* accel))

    let positions =
        Array.zip state.pos speeds
        |> Array.map (fun (pos, speed) ->
            pos .+. (dt .* speed))

    { state with
        pos = positions
        speed = speeds }

let initialize (ops : #Vector3Math<'V>) =
    let rnd = new System.Random(0)
    let nextFloat() = rnd.NextDouble() |> float32

    let N = 1000

    let masses =
        Array.init N (fun _ -> nextFloat() * 1000.0f)

    let positions =
        Array.init N (fun _ ->
            let len = nextFloat() * 100.0f
            ops.Scale(len, ops.Create(nextFloat(), nextFloat(), nextFloat())))

    let speeds =
        Array.init N (fun _ -> ops.Zero)

    { mass = masses
      pos = positions
      speed = speeds }

let centerOfMass (ops : #VectorMath<'V>) state =
    let wpos =
        Array.zip state.pos state.mass
        |> Array.map (fun (pos, mass) -> ops.Scale(mass, pos))
        |> Array.fold (fun wpos x -> ops.Add(wpos, x)) ops.Zero

    let mass = Array.sum state.mass
    
    ops.Scale(1.0f / mass, wpos)

Discussion

This approach has a number of problems, compared with traditional F# modules.
  1. Additional level of indirection when calling operations. In performance-critical situations, this can matter.
  2. Additional ops parameter sprinkled in all functions that use the signature. A bit tiresome to write. Call sites aren't as badly affected, thanks to partial application and currying.
  3. Need to specify the signatures. Will I need to duplicate all of XNA's API in signatures?
There are a number of non-problems, i.e. problems that have pretty good solutions:
  1. Operator overloading: See update for an example on how to use operators to improve the look of expressions involving vector math.
  2. Callers need not pass ops explicitly at each call site, as shown below:
In the library:
let mkModule ops =
    (fun () -> initialize ops),
    update ops,
    centerOfMass ops

In the application:
let initialize, update, centerOfMass = PortableLibrary1.mkModule MyVector3Math
let state = initialize()
let center0 = centerOfMass state

The benefits include:
  1. Truly write-once-run-everywhere library code. I should be able to use my library code in a game for Sony devices using the Playstation Suite SDK, or for smart phones (actually, not quite, due to limitations regarding generic virtual methods in Mono).
  2. Looser coupling between libraries. It's up to the top level, the application, to specify implementations. That's the right thing to do, since that's the only part that should be aware of the target platform and its  specifics.
Programmers with a background in OOP might wonder why I did not use an interface for the vector type itself, instead of providing an interface for a module. Note that would not really help me here, as XNA's Vector3 and Vector2 don't implement this interface (of which they know nothing). I would need some bridging type anyway.
Providing abstraction on the module-level, as opposed to the "object" level allows to group related types in a module specification. A more complete vector math signature would include matrices and operations that operate on vectors and matrices. The OOP approach forces these operations into one of the vector and matrix types, which I have always found a bit arbitrary.

No comments: