Sunday, February 12, 2017

Type Inferencing and Tail Recursion

This is the second post in a series on my journey to learn more about the F# language. I'm choosing some coding exercises from Structure and Interpretation of Computer Programs and writing each one in both C# and F#. You can follow my progress here and see all my code on github.

In the last post, we implemented Newton's method for calculating square roots. This time I want to look at a few of the differences between the C# code and the F# code.

Here's the C# code.

public class Newton { public static double SquareRoot(double input) { if (input < 0.0) throw new ArgumentOutOfRangeException(); if (input == 0.0) return input; var guess = 1.0; while (true) { var newGuess = CalculateNewGuess(input, guess); if (CloseEnough(guess, newGuess)) return newGuess; guess = newGuess; } } static double CalculateNewGuess(double input, double guess) { return (guess + input / guess) / 2.0; } static bool CloseEnough(double guess, double newGuess) { return Math.Abs((guess - newGuess) / guess) < 0.000001; } }
Looking at this code again, I realize we could implement SquareRoot as an extension method on the type double.

public static class Newton { public static double SquareRoot(this double input) { ... } }
This lets us use the method in a more OO style. For example, our unit test becomes:

public class NewtonCSharpTest: NewtonTest { protected override double SquareRoot(double input) { return input.SquareRoot(); } }
Now the F# code:

module Newton = let GoodEnough oldGuess newGuess = abs((oldGuess - newGuess) / oldGuess) < 0.000001 let rec SquareRootFromGuess guess input = let newGuess = (guess + input / guess) / 2.0 if GoodEnough guess newGuess then newGuess else SquareRootFromGuess newGuess input let SquareRoot input = match input with | 0.0 -> 0.0 | x when x < 0.0 -> raise (new System.ArgumentOutOfRangeException()) | _ -> SquareRootFromGuess 1.0 input
I've just learned a more compact way to write the SquareRoot function:

let SquareRoot = function | 0.0 -> 0.0 | input when input < 0.0 -> raise (new System.ArgumentOutOfRangeException()) | input -> SquareRootFromGuess 1.0 input
Now let's look at a few of the differences between the C# and F# code. The first obvious difference is the lack of parentheses and braces - F# uses whitespace and indentation instead. I like to format my code to show its structure visually so I like that F# can use this without any additional syntax required.

C#'s default method protection is private and F#'s default is public. To keep our two implementations consistent, we can make our F# helper functions private:

let private GoodEnough oldGuess newGuess = abs((oldGuess - newGuess) / oldGuess) < 0.000001 let rec private SquareRootFromGuess guess input =
At first glance, it seems that F# is dynamically typed, because we haven't specified any types for our functions or their arguments. But in fact, our F# functions are statically typed. The F# compiler is using type inferencing to determine the types for us. Sometimes, we may need to add type annotations if the compiler cannot determine a type. If we peek into the F# assembly, we can see the types:

The biggest difference in our implementations is the way we iterate to our final answer. In F#, we're using a recursive call, while our C# code uses a loop. We could have used recursion in C#, but if we make too many recursive calls, we might cause a stack overflow. In F#, we don't have this worry. The F# compiler will use a tail recursion optimization when a function's return value is a recursive call to the same function. This optimization replaces the current stack frame with a new one for the recursive call, rather than creating a new stack frame.

We can demonstrate this with a sample recursive function. First in C#:

public class Example { public static int Recurse(int count) { return count == 0 ? 42 : Recurse(count - 1); } }
And in F#:

module Example = let rec Recurse input = if input = 0 then 42 else Recurse(input-1)
We call the function with the number of recursive calls we want it to make, and it just returns a fixed value. Let's rewrite our Console program so we can try it out:

public class Program { static void Main(string[] args) { while (true) { System.Console.Write("? "); input = System.Console.ReadLine(); if (string.IsNullOrEmpty(input)) break; System.Console.WriteLine(functions[args[0]]()); } } static string input; static readonly Dictionary<string, Func<string>> functions = new Dictionary<string, Func<string>> { {"c", () => DoubleFunction(CSharp.Newton.SquareRoot)}, {"f", () => DoubleFunction(FSharp.Newton.SquareRoot)}, {"cr", () => IntFunction(CSharp.Example.Recurse)}, {"fr", () => IntFunction(FSharp.Example.Recurse)} }; static string DoubleFunction(Func<double, double> calculate) { return calculate(double.Parse(input)).ToString(); } static string IntFunction(Func<int, int=> calculate) { return calculate(int.Parse(input)).ToString(); } }
Our C# function fails when we hit 50000 recursive calls:

D:\my\code\\source\Console\bin\Debug>console cr ? 10 42 ? 10000 42 ? 50000 Process is terminated due to StackOverflowException.
Our F# version is still going strong at 100 million recursive calls:

D:\my\code\\source\Console\bin\Debug>console fr ? 10 42 ? 100000 42 ? 100000000 42 ?
Next time: encapsulating data and behavior.