Exercise for the Reader

November 25, 2008

F# Arithmetic Specialization Rocks!

Filed under: Functional programming, Numerical methods — Tags: , , — Seth Porter @ 2:17 am

With a title like that, you know you’re in for a rocking good time.

Anyway, every good side project needs at least one new language, and after a long time wandering in the imperative wasteland (C# and, more recently, Java), I decided to give F# a look. It’s amazingly production-ready and very nicely integrated with Visual Studio (syntax highlighting and IntelliSense in a type-theoretic language?!). I know, strong type models and a good interactive mode should leave you happy to work in Notepad, but I’ve gotten awfully used to support from a rich IDE. But what a thrill it was to see, in a nicely formatted tooltip no less, my function’s inferred type:

val myFun : 'a * 'a -> ('a -> 'b) -> ('b * 'b)

Anyway, fun is fun, but my theoretical reason for all this was to try out some numerical recipes without tying my hands too early (as far as working in single / double resolution, or even something more exotic like interval arithmetic). Without getting side-tracked with numerical methods, consider good old linear interpolation:

f(p0, p1, u) = p0 * (1-u) + p1 * u

where ‘u’ varies from 0 to 1, and ‘p0’ and ‘p1’ are the values you’re interpolating between. One thing to note is that ‘p0’ and ‘p1’ can, in general, be anything you want — floating point values, vectors, or anything that can be scaled (by ‘u’) and added together.

So, my first, simplest approximation was very straightforward:

let linearInterp0(p0, p1, u) = p0 * (1-u) + u * p1

Looks good, but the inferred type comes out as ‘val linearInterp0 : int * int * int -> int’. Hmm. Maybe I need to explicitly tell it to be more generic. But ‘let linearInterp0(p0 : ‘a, p1 : ‘a, u) = p0 * u + (1-u) * p1’ (where ‘a is a generic type; loosely equivalent to ‘T myFun<T>(T p0, T p1…)’ in Java) fails to compile, with the helpful warning that ‘1-u’ “causes code to be less generic than indicated by the type annotations”.

Fair enough, looks like that “1” is forcing everything to be an integer. (I discovered later that int is also the default type for under-specified math operations, but let’s keep things simple.) Changing it to ‘1.0’ gives me a type of ‘float * float * float -> float’, or ‘1.0f’ for ‘float32 * float32 * float32 -> float32’ (apparently F# uses ‘float’ for what I think of as ‘double’, and ‘float32’ for single-precision floats). But I want to operate on any of the above (and don’t forget about vectors!). There was also no obvious way to manage one type for P0 and P1, and also retain flexibility on whether to use singles or doubles for ‘u’, but one step at a time.

So, some Googling lead to this thread, which almost broke my spirit right there. (Note that the last reply, from “Andyman”, would have helped a lot, but wasn’t posted at the time.) Either you create your own “numeric” interface, and implement it for all the types you care about, or you use magic global associations functions and create pseudo-generic methods which fail at runtime if called with an inappropriate type. Anyway, I tried a trivial “sum” method using the GetNumericAssociation approach (if you’re following along at home, you’ll need to include a reference to FSharp.PowerPack.dll, and open the ‘Microsoft.FSharp.Math’ namespace):

let sumNA(p0 : 'a, p1 : 'a) =
    let numeric = GlobalAssociations.GetNumericAssociation<'a>()
    numeric.Add(p0, p1)

It has a wonderfully generic type, ‘a * ‘a -> ‘a (again, in Java terms something like ‘T myFunc<T>(T p0, T p1)’). In fact, it’s too generic; it will fail at runtime if GetNumericAssociation fails for the provided type. However, it works for float32 and float, so it’s worth seeing what we get out of the compiler. Using ILDASM on the compiled assembly, the truth comes out:

  IL_0000:  call       class [FSharp.Core]Microsoft.FSharp.Core.Option`1<
         class [FSharp.PowerPack]Microsoft.FSharp.Math.INumeric`1<!!0>>
         [FSharp.PowerPack]Microsoft.FSharp.Math.GlobalAssociations::TryGetNumericAssociation<!!0>()
  IL_0005:  call       instance !0 class [FSharp.Core]Microsoft.FSharp.Core.Option`1<
         class [FSharp.PowerPack]Microsoft.FSharp.Math.INumeric`1<!!A>>::get_Value()
  IL_000a:  ldarg.0
  IL_000b:  ldarg.1
  IL_000c:  tail.
  IL_000e:  callvirt   instance !0 class [FSharp.PowerPack]
         Microsoft.FSharp.Math.INumeric`1<!!A>::Add(!0,!0)

Without worrying about the details of the .Net assembly generics syntax, the key is in that last line — ‘callvirt’. We’re calling a virtual method defined in the ‘INumeric’ interface, albeit with some syntactic sugar. I could do that in C# (or even Java), with less confusion. We’ve also lost the nice equivalence of the mathematical definition and the source code. Sigh. I want something more like C++ templating, but with actual types (instead of almost-textual expansion and all the other downsides of C++).

(more…)

Advertisements

Blog at WordPress.com.