Phillip Trelford's Array

POKE 36879,255

A Fistful of Dollars

Just over a week ago I took the Eurostar over to Paris for NCrafts, a conference bringing together over 300 software craftsmen and craftswomen:

The event was held in a crypt and featured a good number of F# sessions:

Mathias Brandewinder gave an excellent closing talk on The T in TDD : tests, types, tales.

 NCrafts 2015 - May 2015

In this live coding session, Mathias took the multi-currency money example from Kent Beck’s seminal Test-Driven Development by Example book. First implementing a dollars class in C# driven by a unit test for quick feedback and then contrasting it with a similar implementation in F# using the REPL for immediate feedback.

Unit Test

The system needs to be able to multiply a price in dollars by a number of shares, so that 5 USD * 2 = 10 USD:

public class Tests
{
   [Test]
   public void five_dollars_times_two_should_equal_ten_dollars()
   {
      // arrange
      var five = new Dollars(5);
      // act
      var result = five.Times(2);
      // assert
      Assert.AreEqual(new Dollars(10), result);
   }
}

C# Dollars

Based on the test an immutable dollars class can be implemented:

public class Dollars
{
   private readonly decimal _amount;

   public Dollars(decimal value)
   {
      _amount = value;
   }

   public decimal Amount
   {
      get { return _amount; }  
   }

   public Dollars Times(decimal multiplier)
   {
      return new Dollars(this._amount * multiplier);
   }
}

The code now compiles, but the test fails!

C# Equality

The test fails because in C# class types use reference equality, so we must override Equals:

public class Dollars
{
   private readonly decimal _amount;

   public Dollars(decimal value)
   {
      _amount = value;
   }

   public decimal Amount
   {
      get { return _amount; }  
   }

   public Dollars Times(decimal multiplier)
   {
      return new Dollars(this._amount * multiplier);
   }

   public override bool Equals(object obj)
   {
      var that = obj as Dollars;
      return
         that != null
         ? this.Amount == that.Amount
         : false;
   }
}

Note: at this point FXCop will also recommend that we implement GetHashCode as we’ve implemented Equals.

F# Dollars

In F#, the simplest thing that could possibly work is a measure type which gives compile time type safety:

[<Measure>] type usd

5.0M<usd> * 2.0M = 10.0M<usd>

We can also test it immediately in F# Interactive as above, or alternatively write a unit test as below:

let [<Test>] ``5 USD * 2 = 10 USD`` () =
   Assert.AreEqual(10M<usd>, 5M<usd> * 2M)

Note: F# units of measure are erased at compile time meaning there’s no runtime performance penalty.

F# Money

For a report we’d probably want to encode money dynamically with a currency component. Below I’ve chosen an F# record type:

type Money = { Amount:decimal; Currency:string } with
   member this.Times(multiplier) = { this with Amount = this.Amount * multiplier }

let USD amount = { Amount=amount; Currency="USD" }

USD 10M = (USD 5M).Times(2M)

This succeeds immediately as F# implements equality (and GetHashCode) by default for us on record types.

Unquote

As an aside, I find assertions over numerical types are more natural using the Unquote library which lets you assert equality using the equals operator, i.e.

let [<Test>] ``5 USD * 2 = 10 USD`` () =
   test <@ (USD 5M).Times(2M) = USD 10M @>

Summary

When writing code we may seek quick feedback on our first implementations. In C# we’d typically write reflection based unit tests to get early feedback, in F# we may use F# interactive first for immediate feedback and later promote useful tests to reflection based tests that run as part of our continuous build and may help find regressions.

Also in this scenario implementing types in F# required a lot less boilerplate than the equivalent C# code.

String and StringBuilder revisited

I came across a topical .Net article by Dave M Bush published towards the tail end of 2014 entitled String and StringBuilder where he correctly asserts that .Net’s built-in string type are reference types and immutable. All good so far.

The next assertion is that StringBuilder will be faster than simple string concatenation when adding more than 3 strings together, which is probably a pretty good guess, but lets put it to the test with 4 strings.

The test can be performed easily using F# interactive (built-in to Visual Studio) with the #time directive:

open System.Text

#time

let a = "abc"
let b = "efg"
let c = "hij"
let d = "klm"

for i = 1 to 1000000 do
   let e = StringBuilder(a)
   let f = e.Append(b).Append(c).Append(d).ToString() 
   ()
// Real: 00:00:00.317, CPU: 00:00:00.343, GC gen0: 101, gen1: 0, gen2: 0
   
for i = 1 to 1000000 do
   let e = System.String.Concat(a,b,c,d)
   ()
// Real: 00:00:00.148, CPU: 00:00:00.156, GC gen0: 36, gen1: 0, gen2: 0

What we actually see is that for concatenating 4 strings StringBuilder takes twice as long as using String.Concat (on this run 0.317ms vs 0.148ms) and generates approximately 3 times as much garbage (gen0: 101 vs gen0: 36)!

Underneath the hood the StringBuilder is creating an array to append the strings into. When appending if the current buffer length is exceeded (the default is 16) then a new array must be created. When ToString is called it may, based on a heuristic, decide to return the builder’s array or allocate a new array and copy the value into that. Therefore the performance of StringBuilder is dependent on the initial capacity of the builder and the number and lengths of the strings to append.

In contrast, String.Concat (which the compiler resolves the ‘+’ operator to) calculates the length of the concatenated string from the lengths of the passed in strings, then allocates a string of the required size and copies the values in, ergo, in many scenarios it will require less copying and less allocation.

When concatenating 2, 3 or 4 strings we can take advantage of String.Concat’s optimized overloads, after this the picture changes as an array argument must be passed which requires an additional allocation. However String.Concat may still be faster than StringBuilder in some scenarios where the builder requires multiple reallocations.

But wait there’s more, going back to the ‘+’ operator, if we assign the integer literal expression 1 + 2 + 3 the compiler can reduce the value to 6, equally if we define the strings as const string then the compiler can apply the string concatenations at compile time leading to, in this contrived example, no cost whatsoever.

The moral of the story is when it comes to performance optimization - measure, measure, measure.

Fun Basic Preview

Fun Basic is an extended clone of Microsoft’s Small Basic programming language that runs as an app in the Windows Store. The app provides a range of sample programs from simple turtle graphics through to video games and physics simulations. The samples have been selected from programs in the public domain created by the Small Basic community. Each sample is presented with it’s corresponding source code allowing you to edit the code and run the program.

FunBasic Entry Screenshot

The concept is that you can learn elements of programming by reading the provided programs and editing and enhancing them. The inspiration comes from the type-in programs circulated in computer magazines throughout the 80s, and through which I had some of my earliest forays into programming.

The editor on the other hand affords more modern conveniences including syntax colouring, code completion and tooltips over API calls.

FunBasic 1942 Screenshot

Why not head over to the Windows Store and try the preview (new features will be appearing weekly).

It’s free and there’s games to play! http://tinyurl.com/funbasic

Language resources

Fun Basic provides all the language features of Small Basic and it extends the language with parameters on subroutines. You can learn more about language features in the Small Basic Tutorial.

The app is currently a preview, in future releases extended support for function return values, tuples and pattern matching (using Select Case) will be enabled.

Technical bit

Fun Basic is an offshoot from an extended Small Basic Compiler project I wrote for fun in early 2014 while learning FParsec, a parser combinator libraryfor F#. You can learn more about that effort in my presentation at NDC London “Write Your Own Compiler in 24 Hours” and an interview on .Net Rocks on “Writing Compilers”.

My kids (8 & 12) have been enjoying programming and downloading apps from the Windows Store so last month I set out to cover both of these interests with a Store app version.

Interpreter

The Windows Store sandbox doesn’t support compilation within apps so the compiler was out. Fortunately I’d also knocked together an interpreter for Small Basic during early prototyping so I used this as a basis for the runtime. The interpreter simply pattern matches over the Abstract Syntax Tree (AST) generated by the parser, executing instructions and evaluating expressions.

Library

The next challenge was supporting Small Basic’s runtime library which provides simple graphics and text based operations. This had to be written from scratch as it needed to work against the Windows Store API and run in process with the app. All API calls are made asynchronously and I’ve employed separate canvases for the drawing, shapes and text layers. There’s also support for the Flickr API which unfortunately at the time of writing is broken in Small Basic.

image

Editor

The editor employs the ActiPro SyntaxEditor control to provide syntax colouring, code completion and tool tips. ActiPro’s Language Designer wizard meant I had syntax colouring set up in minutes, and it was relatively easy to set up the code completion and tooltips using my existing parser and AST. I’m planning to enable more of the SyntaxEditor’s features in future versions.

App

To build the app I used the Windows Store Grid App project template that’s built-in to Visual Studio. All that was needed was to customize the grid items with pictures and descriptions for the master view and add the editor and program panels to the detail view.

Logo

Special thanks to Sergey Tihon,, author of the excellent F# Weekly, for putting together a nice logo for the app!

Source Code

The source is open and available on BitBucket, see http://bitbucket.org/ptrelford/funbasic

If you delve in you’ll find a mixture of F#, C# and VB.Net. F# is used for the parser and interpreter, C# for interfaces and small imperative functions and VB.Net for gluing the app together.

Releases

I’m currently releasing new features weekly, let me know if there’s a feature you “must have” via Twitter @ptrelford :)