Friday, April 7, 2017

More Fun with Functions

This is the fourth 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.

We started this series of posts by using Newton's method to find square roots. Now we're going to use Newton's method to find the root of any function (section 1.3.4). Newton showed that for a function f and its derivative f', we can find a value x where f(x) = 0, by starting with a guess y, and using y - f(y) / f'(y) to get a better guess. As before, we calculate better guesses until the difference between guesses becomes very small. We can find the square root of a number a with this method by using the function f(x) = x**2 - a.

We already have some code that computes guesses repeatedly for square roots. Let's extract a function that does this for any guess calculation. (In math jargon, this is called finding the fixed point.) Here's the F# version:

module Newton = let rec findFixedPoint improveGuess guess = let newGuess = improveGuess guess let goodEnough = abs((guess - newGuess) / guess) < 0.000001 if goodEnough then newGuess else findFixedPoint improveGuess newGuess let squareRoot input = let squareRootFromGuess = findFixedPoint (fun guess -> (guess + input / guess) / 2.0) match input with | 0.0 -> 0.0 | input when input < 0.0 -> raise (new System.ArgumentOutOfRangeException()) | input -> squareRootFromGuess 1.0
Notice how we define a function squareRootFromGuess by calling findFixedPoint with the guess calculation function we want to use. This is called partial application, because findFixedPoint takes two arguments and we're only providing the first. The second argument is supplied when we call squareRootFromGuess.

Now we can use this function with Newton's general guess calculation. This time, let's write NUnit tests in F#, that we can use for both F# and C# versions of production code. F# has all the object-oriented features we need to define abstract classes and methods, inheritance and method overrides. We can even use method names with embedded spaces to get a nice readable test results report from NUnit. Here's a couple of tests and a test fixture class:

open NUnit.Framework open Exploring.Net.FSharp.Newton [<AbstractClass>] type NewtonTest() = abstract member FindSquareRoot: float -> float [<Test>] member this.``initial guess is correct``() = Assert.AreEqual(1.0, this.FindSquareRoot(1.0)) [<Test>] member this.``result gets close enough``() = Assert.AreEqual(2.0, this.FindSquareRoot(4.0), 1E-10); [<TestFixture>] type NewtonTestFSharp() = inherit NewtonTest() override this.FindSquareRoot input = squareRoot2 input
Here's some F# code to pass the tests. We define a derivative function as (f(x+dx) - f(x)) / dx, where dx is a small amount. We define Newton's function to transform a guess into a better guess. We've defined a constant for our small amount, and added checks for floating point overflow.

open System module Newton = let smallAmount = 1E-6 let rec findFixedPoint improveGuess guess = let newGuess = improveGuess guess if Double.IsNaN newGuess || Double.IsInfinity newGuess then newGuess else let goodEnough = abs((guess - newGuess) / guess) < smallAmount if goodEnough then newGuess else findFixedPoint improveGuess newGuess let squareRoot input = ... let findRoot aFunction firstGuess = let derivative = fun x -> (aFunction (x + smallAmount) - aFunction x) / smallAmount let newtonsTransform = fun x -> x - (aFunction x) / (derivative x) findFixedPoint newtonsTransform firstGuess let squareRoot2 input = findRoot (fun x -> x*x - input) 1.0
Now the same in C#. We add a test fixture class to our F# tests.

[<TestFixture>] type NewtonTestCSharp() = inherit NewtonTest() override this.FindSquareRoot input = Newton.SquareRoot2 input
Now refactor the C# square root calculation to extract the FindFixedPoint function and use it to implement the general Newton's method calculation.

public static class Newton { public static double SquareRoot(this double input) { if (input < 0.0) throw new ArgumentOutOfRangeException(); if (input == 0.0) return input; return FindFixedPoint(guess => (guess + input / guess) / 2.0, 1.0); } public static double SquareRoot2(double input) { return FindRoot(x => x * x - input, 1.0); } public static double FindRoot(Func function, double guess) { Func newtonsTransform = x => x - function(x) / Derivative(function)(x); return FindFixedPoint(newtonsTransform, guess); } static Func Derivative(Func function) { return x => (function(x + smallAmount) - function(x)) / smallAmount; } static double FindFixedPoint(Func improveGuess, double initialGuess) { var guess = initialGuess; while (true) { var newGuess = improveGuess(guess); if (double.IsNaN(newGuess) || double.IsInfinity(newGuess)) return newGuess; if (CloseEnough(guess, newGuess)) return newGuess; guess = newGuess; } } static bool CloseEnough(double guess, double newGuess) { return Math.Abs((guess - newGuess) / guess) < smallAmount; } const double smallAmount = 0.000001; }
We've seen how F# lets us pass functions as parameters, assign functions to identifiers, create new functions from existing functions, in fact, do practically anything with functions that we're used to doing with simple data types. But we're also able to do much of the same things in C#. And we've seen a few of the object-oriented features of F# that are comparable to C#. So with two hybrid languages with a combination of object-oriented and functional features, how would we determine which is more suited to a particular problem? I'm not ready to answer that yet, but I'll close with some interesting comments I came across: The myths about the risks of introducing F# in your development team.

Monday, March 6, 2017

Encapsulation Two Ways

This is the third 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.

This time, we're using the half-interval method to find roots of equations, i.e., a value x where f(x) = 0 for a continuous function f (Section 1.3.3). The idea is that, given two points a and b where f(a) < 0 < f(b), then the value x must lie somewhere between a and b. So we check the value of f at the midpoint of the interval. If it is zero, then we've found the root. If it's negative, then the root must be in the right half of the interval. If it's positive, the root's in the left half. We continue choosing smaller and smaller half-intervals until we hit a root or we decide the interval is small enough.

As usual, we start the C# version with a test. The test is split into an abstract class and a concrete class, as before, so we can re-use it later for the F# version.

public abstract class HalfIntervalTest { [Test] public void MidpointIsRoot() { Assert.AreEqual(0.0, FindSineRoot(-0.5, 0.5)); } protected abstract double FindSineRoot(double left, double right); } [TestFixture] public class HalfIntervalCSharpTest: HalfIntervalTest { protected override double FindSineRoot(double left, double right) { return HalfIntervalMethod.FindRoot(Math.Sin, left, right); } }
We're using the sine function and the first test has the root at the midpoint of the initial interval.

But we have a code smell, before we've even written any production code. There's a static method FindRoot with three parameters. For a more object-oriented style, let's encapsulate the interval in its own class, and the function in the HalfIntervalMethod class.

protected override double FindSineRoot(double left, double right) { return new HalfIntervalMethod(Math.Sin).FindRoot(new Interval(left, right)); }
This isn't a series on TDD, so I won't show all the steps to reach the final C# implementation. Here's the tests:

public abstract class HalfIntervalTest { [Test] public void MidpointIsRoot() { Assert.AreEqual(0.0, FindSineRoot(-0.5, 0.5)); } [Test] public void RootIsFoundWithPositiveValueAtLeft() { Assert.AreEqual(Math.PI, FindSineRoot(Math.PI - 0.1, Math.PI + 0.5), 1E-10); } [Test] public void RootIsFoundWithPositiveValueAtRight() { Assert.AreEqual(Math.PI, FindSineRoot(Math.PI + 0.5, Math.PI - 0.1), 1E-10); } [Test] public void ValuesWithSameSignThrowsException() { Assert.Throws(() => FindSineRoot(Math.PI/2.0, Math.PI/2.0 + 1.0)); } protected abstract double FindSineRoot(double left, double right); }
The HalfIntervalMethod class checks that the function values at the interval end points do have opposite signs. We swap the interval if needed so that we have ascending values. Then we iterate choosing the appropriate half-interval until we hit a root or the interval is small enough.

public class HalfIntervalMethod { public HalfIntervalMethod(Func<double, double> function) { this.function = function; } public double FindRoot(Interval interval) { var values = interval.Map(function); if (!values.CrossesZero) { throw new ArgumentException("Values are not opposite signs."); } return FindRootByHalfIntervals(values.Ascending ? interval.Swap : interval); } double FindRootByHalfIntervals(Interval interval) { while (interval.Size >= 1E-10) { var value = function(interval.MidPoint); if (value == 0.0) break; interval = value > 0.0 ? interval.RightHalf : interval.LeftHalf; } return interval.MidPoint; } readonly Func<double, double> function; }
The Interval class encapsulates the endpoints of the interval and has a collection of useful methods. This is a common outcome when using TDD with an object-oriented language. We start by encapsulating some primitive data types and we find a bunch of methods that are attracted to the data. It creates a good abstraction that makes the HalfIntervalMethod code very readable.

public struct Interval { public Interval(double start, double finish) { this.start = start; this.finish = finish; } public double MidPoint => (start + finish) / 2.0; public double Size => Math.Abs(finish - start); public bool CrossesZero => Math.Sign(start) == -Math.Sign(finish) && Math.Sign(start) != 0; public bool Ascending => start < finish; public Interval LeftHalf => new Interval(start, MidPoint); public Interval RightHalf => new Interval(MidPoint, finish); public Interval Swap => new Interval(finish, start); public Interval Map(Func function) => new Interval(function(start), function(finish)); readonly double start; readonly double finish; }
Now the F# version. Before we start, there's a couple of F# practices that I've learned since the last post. First, function names are started with lower case by convention. Second, we can nest functions within other functions to control their visibility, rather than using private modifiers. So here's what my squareRoot function from last time looks like now.

let squareRoot input = let rec squareRootFromGuess guess = let newGuess = (guess + input / guess) / 2.0 let goodEnough = abs((guess - newGuess) / guess) < 0.000001 if goodEnough then newGuess else squareRootFromGuess newGuess match input with | 0.0 -> 0.0 | input when input < 0.0 -> raise (new System.ArgumentOutOfRangeException()) | input -> squareRootFromGuess 1.0
Back to half intervals. We can write an Interval type in F# that's the same as the C# version: with encapsulated data and member functions. But the tutorials I've been reading suggest using data types with independent functions to fully exploit the functional capabilites of F#. So here goes:

module Interval = type IntervalType = {Start: float; Finish: float} let create start finish = {Start = start; Finish = finish} let midpoint interval = (interval.Start + interval.Finish) / 2.0 let size interval = abs(interval.Finish - interval.Start) let crossesZero interval = sign(interval.Start) = -sign(interval.Finish) && sign(interval.Start) <> 0 let ascending interval = interval.Start < interval.Finish let leftHalf interval = create interval.Start (midpoint interval) let rightHalf interval = create (midpoint interval) interval.Finish let swap interval = create interval.Finish interval.Start let map aFunction interval = create (aFunction interval.Start) (aFunction interval.Finish)
Now let's use this in the half-interval method test class. The Interval module has a constructor method that we can call from C#. In the F# code I've read so far, this seems to be a common pattern.

[TestFixture] public class HalfIntervalFSharpTest: HalfIntervalTest { protected override double FindSineRoot(double left, double right) { return FSharp.HalfIntervalMethod.findSineRoot(FSharp.Interval.create(left, right)); } }
Here's the F# implementation that passes the tests:

open Interval module HalfIntervalMethod = let findRoot aFunction interval = let rec findRootByHalfInterval interval = if size interval < 1E-10 then midpoint interval else match aFunction (midpoint interval) with | 0.0 -> midpoint interval | value -> findRootByHalfInterval ((if value < 0.0 then rightHalf else leftHalf) interval) let values = map aFunction interval if crossesZero values then findRootByHalfInterval (if ascending values then interval else swap interval) else raise (new System.ArgumentException("Values are not opposite signs.")) let findSineRoot interval = findRoot sin interval
A few final thoughts on the F# version compared to the C# version. We're using tail recursion again to iterate to the answer. Notice how we can select the right and left intervals by choosing a function to apply to the current interval: (if value < 0.0 then rightHalf else leftHalf) interval. This is the first little example of the power of functions as first-class objects.

In C#, we use a class to compose data: an interval is composed of two numbers. The class also encapsulates both data and methods. Public class members can be accessed from outside the class. Inside the class, private data and methods can be accessed from any class methods. In F#, we've used two different mechanisms for data composition and encapsulation. A type is used to compose data but we've used function nesting to control encapsulation. A nested function can only be used from within the enclosing function.

Next time: more fun with functions.

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\exploring.net\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\exploring.net\source\Console\bin\Debug>console fr ? 10 42 ? 100000 42 ? 100000000 42 ?
Next time: encapsulating data and behavior.

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[0], 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.