Tuesday, January 24, 2017

Starting the New Year with Newton

My New Year's resolution is to learn more about the F# language. I'm particularly interested in how F# code can play in an existing C# code base. I also want to see how F#, a functional language with some object-oriented features, compares to C#, an OO language with some functional capabilities. You can follow my progress here and see all my code on github.

I decided to start by picking some coding exercises from the classic Structure and Interpretation of Computer Programs and writing each one, first in C# and then in F#.

Our first exercise will be Newton's method for calculating a square root (section 1.1.7). Isaac Newton determined that for any number x and a guess y of the square root, a better guess is (y + x/y) / 2. We can use this formula to generate better and better guesses until we decide we're close enough. We'll use 1 as the initial guess and stop when the change between two successive guesses is very small.

We start the C# version with a test.

```[TestFixture] public class NewtonTest { [Test] public void InitialGuessIsCorrect() { Assert.AreEqual(1.0, Newton.SquareRoot(1.0)); } } ```
And make it pass.

```namespace Exploring.Net.CSharp { public class Newton { public static double SquareRoot(double input) { return 1.0; } } } ```
Another test.

``` [Test] public void ResultGetsCloseEnough() { Assert.AreEqual(2.0, Newton.SquareRoot(4.0), 1E-10); } ```
Usually we'd use TDD to help us discover our solution, but in this case, we already know the algorithm we're going to use. So we just implement it.

``` public static double SquareRoot(double 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; } ```
A couple more tests to handle edge cases.

``` [Test] public void NegativeInputThrowsException() { Assert.Throws(() => Newton.SquareRoot(-1.0)); } [Test] public void ZeroIsHandled() { Assert.AreEqual(0.0, Newton.SquareRoot(0.0)); } ```
And our implementation is complete.

``` public static double SquareRoot(double input) { if (input < 0.0) throw new ArgumentOutOfRangeException(); if (input == 0.0) return input; ... } ```
I want to make sure we're handling very large and small numbers, so two more tests, which pass without any more code. Yay!

``` [Test] public void LargeResultIsCalculated() { Assert.AreEqual(1E50, Newton.SquareRoot(1E100), 1E40); } [Test] public void SmallResultIsCalculated() { Assert.AreEqual(1E-50, Newton.SquareRoot(1E-100), 1E-40); } ```
Now we can write a little console program to play with our square root calculator.

```class Program { static void Main(string[] args) { while (true) { System.Console.Write("? "); var input = System.Console.ReadLine(); if (string.IsNullOrEmpty(input)) break; System.Console.WriteLine(Newton.SquareRoot(double.Parse(input))); } } } ```
Here it is in action.

```D:\my\code\exploring.net\source\Console\bin\Debug>console ? 1 1 ? 2 1.41421356237309 ? 3 1.73205080756888 ? 4 2 ```
Now for the F# version. My first thought is to figure out how to write tests in F#, but we already have a set of tests for a square root implementation and it'd be nice if we could reuse them. Let's start by refactoring our test class into an abstract base class and a test implementation class. The base class contains all the tests with the actual square root calculation replaced with an abstract method.

```public abstract class NewtonTest { [Test] public void InitialGuessIsCorrect() { Assert.AreEqual(1.0, SquareRoot(1.0)); } ... protected abstract double SquareRoot(double input); } [TestFixture] public class NewtonCSharpTest: NewtonTest { protected override double SquareRoot(double input) { return Newton.SquareRoot(input); } } ```
The tests still pass. We write an initial F# implementation.

```namespace Exploring.Net.FSharp module Newton = let SquareRoot input = 1.0 ```
And a test class for it. (We've put the C# and F# versions in different namespaces so we can reference them both from the same file.)

```[TestFixture] public class NewtonCSharpTest: NewtonTest { protected override double SquareRoot(double input) { return CSharp.Newton.SquareRoot(input); } } [TestFixture] public class NewtonFSharpTest: NewtonTest { protected override double SquareRoot(double input) { return FSharp.Newton.SquareRoot(input); } } ```
We have the first test passing for our F# version and the rest failing. We implement the rest of the algorithm.

```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 ```
All the tests pass! But is this what an experienced F# developer would write? At this point. I don't know. But I have my first F# program working and I'll learn more as I write more code. Let's change our console program to work with both versions.

```class Program { static void Main(string[] args) { while (true) { System.Console.Write("? "); var input = System.Console.ReadLine(); if (string.IsNullOrEmpty(input)) break; System.Console.WriteLine(SquareRoot(args, double.Parse(input))); } } static double SquareRoot(string version, double input) { if (version == "c") return CSharp.Newton.SquareRoot(input); if (version == "f") return FSharp.Newton.SquareRoot(input); throw new ApplicationException("unknown version"); } } ```
And both versions return the same results.

```D:\my\code\exploring.net\source\Console\bin\Debug>console c ? 1 1 ? 2 1.41421356237309 ? 3 1.73205080756888 ? 4 2 ? D:\my\code\exploring.net\source\Console\bin\Debug>console f ? 1 1 ? 2 1.41421356237309 ? 3 1.73205080756888 ? 4 2 ? ```
So there's my first lesson done. Next time, we'll look more closely at the differences between the C# and F# versions.