Last time we watched our elegant map function blow up in our face. This time we’ll find out how to fix the problem.
The Tail Instruction
On page 261 of .Net IL Assembler there’s a short blurb about the tail instruction. I never really understood what the tail call did. I’ve actually never seen a tail call in IL before. I don’t believe either the VB or C# compiler generates the instruction.
The tail instruction
· Abandons the current method
· Discards the stack frame
· Passes the arguments to tail called method
Point 2 looks like it well could solve our stack overflow exception. Will it?
No Work after the Recursive Call
For F# to make a function tail recursive no work can be done after the recursive call. This means the recursive call must be the last thing we do in our function. Rewriting our function makes it more obvious the add is the last thing we’re doing in the function.
#light
let rec map(f : ‘a -> ‘b) (l : ‘a list) =
if l.IsEmpty then
[]
else
let t = List.tl l
let h = List.hd l
let hb = f h
let lb = map f t
hb :: lb
let result = map (fun x -> x + x) [1..80000]
printfn “%A” result
System.Console.ReadLine()
Since we can’t do our add after the recursive call, we have no other option than to do our add before the recursive call. And if we do the add before, we’ll have to pass the list with the transformed values along with us.
#light
let map(f : ‘a -> ‘b) (l : ‘a list) =
let rec map_cps(f : ‘a -> ‘b) (la : ‘a list) (lb : ‘b list) =
if la.IsEmpty then
List.rev lb
else
let t = List.tl la
let h = List.hd la
let hb = f h
let lb = hb :: lb
map_cps f t lb
map_cps f l []
let result = map (fun x -> x + x) [1..80000]
printfn “%A” result
System.Console.ReadLine()
Notice how our recursive function is now the last call in our function? Let’s tidy it back up so we’re a bit closer to our original function.
#light
let map(f : ‘a -> ‘b) (l : ‘a list) =
let rec map_cps(f : ‘a -> ‘b) (la : ‘a list) (lb : ‘b list) =
match la with
| h :: t -> map_cps f t (f h :: lb)
| [] -> List.rev lb
map_cps f l []
let result = map (fun x -> x + x) [1..80000]
printfn “%A” result
System.Console.ReadLine()
The Tail Instruction Appears
If we analyze our new map function in Reflector we see that illusive IL instruction finally make an appearance on the CLR.
IL_000a: call class [FSharp.Core]Microsoft.FSharp.Collections.List`1<!0> class [FSharp.Core]Microsoft.FSharp.Collections.List`1<!!B>::get_uniq_Empty()
IL_000f: tail.
IL_0011: call !!1 class [FSharp.Core]Microsoft.FSharp.Core.FastFunc`2<class [FSharp.Core]Microsoft.FSharp.Core.FastFunc`2<!!0,!!1>,class [FSharp.Core]Microsoft.FSharp.Collections.List`1<!!0>>::InvokeFast3<class [FSharp.Core]Microsoft.FSharp.Collections.List`1<!!1>,class [FSharp.Core]Microsoft.FSharp.Collections.List`1<!!1>>(class [FSharp.Core]Microsoft.FSharp.Core.FastFunc`2<!0,class [FSharp.Core]Microsoft.FSharp.Core.FastFunc`2<!1,class [FSharp.Core]Microsoft.FSharp.Core.FastFunc`2<!!0,!!1>>>,
And when we run our program we get the following.
No stack overflow and a whole lot of number.
Why aren’t we the Mathematician and the Compiler the Computer Scientist?
Unfortunately, we programmers still have to worry about how to implement algorithms. Perhaps, some day the F# compiler will tail optimize all our recursive call for us and we can concentrate on the important stuff. Until that day, we’ll find ourselves digging through IL instructions looking for those precious tail calls. Happy hunting!