Tuesday, August 6, 2013

map in F# and IL assembly

I played with F# last night, and it made me realize how mature Haskell is compared to F#. It's too bad you can't compile Haskell code into a .NET assembly.

The map function in F# is pretty concise, compared to the wordy C# version.  Here it is:

let rec map (f : ('a -> 'b), ps : 'a list) =
    if ps = list.Empty
        then list.Empty
        else list.Cons(f(ps.Head), map(f, ps.Tail))

This is not so terribly different from the Haskell version of map, which could be written as follows:

map' :: (t -> a) -> [t] -> [a]
map' _ [] = []
map' f (p:ps) = (f p) : (map' f ps)

There are a number of differences (including the F# requirement that we use rec to indicate a recursive function), but the important similarities are that we can write a higher order function, and we have generic types.

So, what does the F# version look like in IL assembly?  To begin with, the method header is reassuring, because it shows that the generic type parameters go all the way down to the IL assembly level:

.method public static class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!b> map<a,b>
class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!a,!!b> f,
class [FSharp.Core]Microsoft.FSharp.Collections.FSharpList`1<!!a> p
) cil managed

We can see that F# provides its own list and function objects, which makes sense given that this functionality isn't standard for the rest of the .NET world.  However, the body of the function reveals something disappointing.  It processes the whole list!  Rather than paste the entire function body here, I'll just write a brief pseudocode paraphrase of it:

IL_0002: push ps.Length onto the stack
IL_0007: if non-zero branch to IL_0013
IL_000d: push an empty list onto the stack
IL_0012: return
IL_0013: push the head of ps onto the stack
IL_001a: invoke function f and push the result onto the stack
IL_0021: push the tail of ps onto the stack
IL_0026: call map and push the result onto the stack
IL_002b: call cons and push the result onto the stack
IL_0030: return

So, from what I have seen here, though F# may look like Haskell on the surface, underneath the covers it is far less advanced.  However, the IL asm natively supports some functionality (like generic type parameters) that suggest it would be possible to build a really powerful functional language that compiled into IL asm.

No comments:

Post a Comment