Simplifying (?) State with C# Async

I got some great feedback on my last blog post about using F#’s async feature to simplify state. One of the more interesting requests was from @FreeQaz who tweeted me:

In all honesty, my 1st reaction was “I wouldn’t do it in C#”, but then that itch started, and I started to think “How bad could it be?”. So, 1st step, port the original state to C#. This was easy and the code is here:

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace CSharpXnaUsingAsync
{
 public class GameAsync : Game
 {
  GraphicsDeviceManager graphicsDeviceManager;
  SpriteBatch spriteBatch;
  float x = 0.0f, y = 0.0f, dx = 4.0f, dy = 4.0f;
  Texture2D sprite;

 public GameAsync()
 {
  graphicsDeviceManager = new GraphicsDeviceManager(this);
  Content.RootDirectory = "Content";
 }

 protected override void Initialize()
 {
  spriteBatch = new SpriteBatch(graphicsDeviceManager.GraphicsDevice);
  graphicsDeviceManager.PreferredBackBufferWidth = 640;
  graphicsDeviceManager.PreferredBackBufferHeight = 480;
  graphicsDeviceManager.ApplyChanges();
  base.Initialize();
 }

 protected override void LoadContent()
 {
  sprite = Content.Load("Sprite");
 }

 protected override void Update(GameTime gameTime)
 {
  if (x > 608.0f || x < 0.0f) dx = -dx;   if (y > 448.0f || y < 0.0f) dy = -dy;

  x = x + dx;
  y = y + dy;
 }

 protected override void Draw(GameTime gameTime)
 {
  GraphicsDevice.Clear(Color.CornflowerBlue);
  spriteBatch.Begin();
  spriteBatch.Draw(sprite, new Vector2(x, y), Color.White);
  spriteBatch.End();
 }
}

 static class Program
 {
  static void Main(string[] args)
  {
   using (GameAsync game = new GameAsync())
   {
    game.Run();
   }
  }
 }
}

Interestingly, this code doesn’t look so bad in C#. It’s not great, but it’s not awful either. In fact I bet you write C# like this all the time in your day-to-day C# life, and never think too hard about it. What was highlighted as mutable state in the F# version is quietly hidden away as is the norm in C#. Now the key F# features my last post relied on in my last post were Async workflows and the Async.AwaitEvent method. C# has async/await, but the implementation is pretty different to the F# version. And C# has no out of the box equivalent to AwaitEvent, so I’ll have to write one. Here’s how that went (full source on Github here):

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using System.Threading.Tasks;

namespace CSharpXnaUsingAsync
{
 public class GameAsync : Game
 {
  readonly GraphicsDeviceManager graphicsDeviceManager;
  readonly TaskCompletionSource<object> initializeTCS = new TaskCompletionSource<object>();     
  readonly TaskCompletionSource<object> loadContentTCS = new TaskCompletionSource<object>(); 
  TaskCompletionSource<GameTime> updateTask = new TaskCompletionSource<GameTime>(); 
  TaskCompletionSource<GameTime> drawTask = new TaskCompletionSource<GameTime>();  
  public GameAsync()  
  {   
   graphicsDeviceManager = new GraphicsDeviceManager(this);   
   Content.RootDirectory = "Content";  
  }

  protected override void Initialize()  
  {   
   graphicsDeviceManager.PreferredBackBufferWidth = 640;   
   graphicsDeviceManager.PreferredBackBufferHeight = 480;   
   graphicsDeviceManager.ApplyChanges();   
   base.Initialize();   
   initializeTCS.SetResult(null);  
  }  

  protected override void LoadContent()  
  {   
   loadContentTCS.SetResult(null);  
  }  

  protected override void Update(GameTime gameTime) 
  {   
   updateTask.SetResult(gameTime);   
   updateTask = new TaskCompletionSource<GameTime>();  
  }  
  
  protected override void Draw(GameTime gameTime)  
  {   
   drawTask.SetResult(gameTime);   
   drawTask = new TaskCompletionSource<GameTime>();  
  }  

  public Task InitializeTask  
  {   
   get { return initializeTCS.Task; }  
  }  

  public Task LoadContentTask  
  {
   get { return loadContentTCS.Task; }  
  }  

  public Task UpdateTask  
  {
   get { return updateTask.Task; } 
  }  

  public Task DrawTask 
  {
   get { return drawTask.Task; }  
  }
 }
 static class GameWorkflow 
 {
  static async void StartWorkflow(GameAsync game)   
  {   
   await game.InitializeTask;
   var spriteBatch = new SpriteBatch(game.GraphicsDevice);  
   await game.LoadContentTask;
   var sprite = game.Content.Load<Texture2D>("Sprite"); 
   await Loop(game, spriteBatch, sprite, 0.0f, 0.0f, 4.0f, 4.0f);  
  }

  static async Task Loop(GameAsync game, SpriteBatch spriteBatch, Texture2D sprite, float x, float y, float dx, float dy)
  { 
   var updateTime = await game.UpdateTask;   
   if (x > 608.0f || x < 0.0f) dx = -dx;
   if (y > 448.0f || y < 0.0f) dy = -dy; 
   x = x + dx;
   y = y + dy; 
   var drawTime = await game.DrawTask; 
   game.GraphicsDevice.Clear(Color.CornflowerBlue); 
   spriteBatch.Begin(); 
   spriteBatch.Draw(sprite, new Vector2(x, y), Color.White);  
   spriteBatch.End();
   await Loop(game, spriteBatch, sprite, x, y, dx, dy);
  } 

  public static IDisposable RunGame()
  { 
   var game = new GameAsync(); 
   StartWorkflow(game);
   game.Run();
   return game;  
  } 
 } 
 
 static class Program 
 {  
  static void Main(string[] args)  
  {
   using (GameWorkflow.RunGame()) { };
  }
 }
}

So, this is a bit more complex than the F# version!I’ve used TaskCompletionSource to act like an event triggering in the F# version. This works really well for the “seeding” stage – Initialize and LoadContent, although the reliance on generics means I have to fudge in a type to make the compiler happy, even when I don’t *really* care about the value (note in the F# version “unit” is a real type unlike “void” in C#).In order to do the same thing for Update and Draw, I need to set the result (which I *do* care about this time – the GameTime) and then mutate the underlying TaskCompletionSource as you can only set the result once on a TaskCompletionSource.The GameWorkflow class handles all the C# async/await magic – the RunGame() method starts the async workflow using the async void antipattern. The nested async loop from the F# version has to be separated out to be able to parameterize the next frame.So, what have we lost in translation?

  1. The only things that are immutable are the 2 TaskCompletionSources and the GraphicsDeviceManager. Everything else is still mutable, and we cant change that due to C#.
  2. Because we had to break out the async loop into its own function it no longer captures the “seed” state from the initialization. This means if we add in more things (ie more sprites or models) we either have to encapsulate those in some class to pass in or keep adding parameters to the Loop method.
  3. The state hasn’t been simplified, and in fact this solution is almost twice as long as the original!

The previous post took something that would have been idiomatic C# (mutation based approach) and transformed it into what would look more like an idiomatic F# approach – constrained mutations. By the end of that post we had something that looked like natural F#.Ironically, taking the default idiomatic C# solution and applying the pattern from F# yielded something quite ugly, completely non-idiomatic, and with little of the benefit of the F# version (for example there is hardly any less mutation, and we’ve had to alter the control flow significantly from the F# version).By the time I had finished the 2nd iteration over this code it didn’t seem wise to apply the 3rd pass from the previous post. Feel free to send a pull request if you think it would be beneficial!

Conclusion

We now live in a polyglot world. Java and Scala play nicely on the JVM. Java and Clojure too. C# and F# are complementary tools on the .NET framework, and using a best of breed approach to development tools is probably the right choice. In the above example, we can see where F# shines compared to C# in terms of the async programming model. However there are areas where you might want to choose C#, or are not presented F# as an option. In those cases it may be advisable to stick to the idiomatic path, unless you can reap some greater rewards by straying from it.

Note: I’m tempted to do an RX version, just too see if that works any better from a C# language perspective. Let me know if you’re interested!

Posted in Uncategorized | 1 Comment

Simplifying State with Async (with XNA/WPF examples)

Now, let me start this post by saying I love XNA/Monogame. XNA was Microsoft’s first (and currently last) attempt to have a first class managed framework for writing games. Luckily the excellent Monogame project has picked up Microsoft’s slack and put XNA on Mac, Linux, iOS, Android, PS Vita, Windows 8, and more.

I remember back in the late 90’s writing DirectX 7 code in C++ and the ridiculous amount of boilerplate associated with it – setting up a Win32 Window, initialising DirectDraw, initialising Direct3D, doing voodoo incantations and maybe after a couple of hours of tinkering you’d have an empty window. XNA just made it easy to create a new project and start writing a game in seconds.

But, as good as XNA is, it’s still rooted in mid-noughties Microsoft OO conventions. Which means that using it in modern languages makes it feel somewhat awkward.

Now, if you want to follow along at home, you’re going to need XNA for a modern Visual Studio (as MS no longer support it officially in the newer IDEs), and you’re going to need this pure F# XNA Template. You’ll need to install XNA before trying to create a new application in VS.

Code Sample – Version 1

Upon creating a new project using that template, you’re going to see a simple XNA Game implementation, using idiomatic XNA conventions.

open Microsoft.Xna.Framework
open Microsoft.Xna.Framework.Graphics

type XnaGame() as this =
    inherit Game()
    
    do this.Content.RootDirectory <- "XnaGameContent"
    let graphicsDeviceManager = new GraphicsDeviceManager(this)

    let mutable sprite : Texture2D = null
    let mutable spriteBatch : SpriteBatch = null
    let mutable x = 0.f
    let mutable y = 0.f
    let mutable dx = 4.f
    let mutable dy = 4.f

    override game.Initialize() =
        graphicsDeviceManager.GraphicsProfile ("Sprite")
        
    override game.Update gameTime = 
        if x > 608.f || x < 0.f then dx <- -dx 
        if y > 448.f || y < 0.f then dy <- -dy 
        
        x <- x + dx
        y <- y + dy

    override game.Draw gameTime = 
        game.GraphicsDevice.Clear(Color.CornflowerBlue)
        spriteBatch.Begin()
        spriteBatch.Draw(sprite, Vector2(x,y), Color.White)
        spriteBatch.End()

let game = new XnaGame()
game.Run()

Most F# developers are probably feeling a bit ill at this point. But to drive home what I hope to fix, let’s highlight the obvious:

  1. Mutable state everywhere! (x,y,dx,dy, sprite, spriteBatch)
  2. Therefore null can be almost everywhere! (sprite, spriteBatch) – even option types wouldn’t help us that much here.
  3. Given there’s so much mutation, it’s hard to tell what is mutable for what reason – x, y, dx and dy are the game state, spriteBatch and sprite are framework code that have to be initialised at specific points after the constructor.
  4. XNA prefers if the Update and Draw cycles are decoupled, so in order to carry state between the 2 calls the framework really enforces mutation through every part of it’s design, leaving the developer little choice in the way of choice.

F# to the rescue (and a WPF diversion)

One of the things I like most about F# is the ability to take a problem in one programming model and solve it in another one. in this small WPF example, we transform from a traditional event based model to async workflow, which makes the code look entirely synchronous, and changes the model from event driven to recursive loops.

open System
open System.Windows
open System.Windows.Controls
open System.Windows.Shapes
open System.Windows.Media
open System.Threading

type DrawingWindow() as window =
   inherit Window()

   let canvas = Canvas(HorizontalAlignment=HorizontalAlignment.Stretch,
                       VerticalAlignment=VerticalAlignment.Stretch)
   do window.Content <- canvas

   let rec addLine() = async {
      let! pt1 = Async.AwaitEvent window.MouseDown
      let pt1 = pt1.GetPosition canvas
      let! pt2 = Async.AwaitEvent window.MouseUp
      let pt2 = pt2.GetPosition canvas
      let line = Line(X1 = pt1.X, X2 = pt2.X, Y1 = pt1.Y, Y2 = pt2.Y,
                      Stroke = Brushes.Black, StrokeThickness=3.0)
      canvas.Children.Add(line) |> ignore
      return! addLine()
   }
   do addLine() |> Async.StartImmediate


type DrawingApplication() =
   inherit Application()
   override app.OnStartup _=
      let window = DrawingWindow()
      window.ShowDialog() |> ignore

[<EntryPoint>]
[<STAThread>]
let main argv =
   let app = DrawingApplication()
   app.Run()

The addLine async workflow is where the magic happens – we await our 1st triggering event (in this case a mouse down), capture some information, then await our exiting event (in this case a mouse up), perform the action (draw the line), then do start again.
The C# equivalent, would likely have ended up capturing the intermediate state between events a class level mutable fields, or worse, some shoehorned in Rx “goodness”.

One of the most common misconceptions I hear about async (in both C# and F#) is that it’s about threads – I prefer describe it as simply “non-blocking” – notice this WPF example has nothing to do with threads, despite relying on async.

Therefore async can be used to help simplify code, even if it has nothing to do with threading.

Back to XNA

Back in XNA, we don’t have events already exposed like WPF. But we can add them, and trigger them at the keys points – Initialise, LoadContent, and then in a loop over Update and Draw.

We can then expose the events as async Workflows, and then consume the game logic entirely outside the XNA Game implementation. Notice that now the gameLoop() workflow has no explicit mutation – each frame is awaited, rendered and then the state accumulates into the next update.

open Microsoft.Xna.Framework
open Microsoft.Xna.Framework.Graphics

type XnaGame() as this =
    inherit Game()

    let initializeEvt = Event<_>()
    let loadEvt = Event<_>()
    let updateEvt = Event<_>()
    let drawEvt = Event<_>()

    do this.Content.RootDirectory <- "XnaGameContent"
    let graphicsDeviceManager = new GraphicsDeviceManager(this)

    override game.Initialize() =
       graphicsDeviceManager.GraphicsProfile <- GraphicsProfile.HiDef
       graphicsDeviceManager.PreferredBackBufferWidth <- 640
       graphicsDeviceManager.PreferredBackBufferHeight <- 480
       graphicsDeviceManager.ApplyChanges() 
       initializeEvt.Trigger()<
       base.Initialize()

    override game.LoadContent() =
       loadEvt.Trigger()
 
    override game.Update gameTime = 
       updateEvt.Trigger gameTime

    override game.Draw gameTime = 
       drawEvt.Trigger gameTime
 
    member game.InitializeAsync = Async.AwaitEvent initializeEvt.Publish
    member game.LoadContentAsync = Async.AwaitEvent loadEvt.Publish
    member game.UpdateAsync = Async.AwaitEvent updateEvt.Publish
    member game.DrawAsync = Async.AwaitEvent drawEvt.Publish

let game = new XnaGame()


let gameWorkflow = async {
   do! game.InitializeAsync
   let spriteBatch = new SpriteBatch(game.GraphicsDevice)
   do! game.LoadContentAsync
   let sprite = game.Content.Load<Texture2D>("Sprite")

   let rec gameLoop x y dx dy = async {
      let! time = game.UpdateAsync
      let dx = if x > 608.f || x < 0.f then -dx else dx
      let dy = if y > 448.f || y < 0.f then -dy else dy
      let x = x + dx
      let y = y + dy
      let! time = game.DrawAsync
      game.GraphicsDevice.Clear(Color.CornflowerBlue)
      spriteBatch.Begin()
      spriteBatch.Draw(sprite, Vector2(x,y), Color.White)
      spriteBatch.End()
      return! gameLoop x y dx dy
   }
   return! gameLoop 0.f 0.f 4.f 4.f
}


gameWorkflow |> Async.StartImmediate

game.Run()

Using async workflows we’ve managed to move all the framework related code into it’s own place (the Game class) and the essentially syncronous application flow into an async workflow.

This works great in this sample, but keen XNA game developers will notice that in this sample the Update and Draw are in lockstep with each other – this isn’t always the case. Now we’ve transformed our mutation-heavy, frame-based application and turned it a simple recursive loop with accumulating state, we can tackle this final problem and call this a success.

If Update and Draw both trigger the same event, but differentiated using different cases of a Discriminated Union, we can safely await the single event, and act appropriately. Note that IsFixedTimeStep is now set to false.

open Microsoft.Xna.Framework
open Microsoft.Xna.Framework.Graphics

type LoopState = 
| Update of GameTime
| Draw of GameTime

type XnaGame() as this =
   inherit Game()

    let initializeEvt = Event<_>()
    let loadEvt = Event<_>()
    let loopEvt = Event<_>()

    do this.Content.RootDirectory <- "XnaGameContent"
    let graphicsDeviceManager = new GraphicsDeviceManager(this)

    override game.Initialize() =
       graphicsDeviceManager.GraphicsProfile <- GraphicsProfile.HiDef
       graphicsDeviceManager.PreferredBackBufferWidth <- 640
       graphicsDeviceManager.PreferredBackBufferHeight <- 480
       graphicsDeviceManager.ApplyChanges() 
       game.IsFixedTimeStep <- false
       initializeEvt.Trigger()
       base.Initialize()

    override game.LoadContent() =
       loadEvt.Trigger()
 
    override game.Update gameTime = 
       loopEvt.Trigger (Update gameTime)

    override game.Draw gameTime = 
       loopEvt.Trigger (Draw gameTime)
    member game.InitializeAsync = Async.AwaitEvent initializeEvt.Publish
    member game.LoadContentAsync = Async.AwaitEvent loadEvt.Publish
    member game.LoopAsync = Async.AwaitEvent loopEvt.Publish

let game = new XnaGame()

let gameWorkflow = async {
    do! game.InitializeAsync
    let spriteBatch = new SpriteBatch(game.GraphicsDevice)
    do! game.LoadContentAsync
    let sprite = game.Content.Load<Texture2D>("Sprite")

    let rec gameLoop x y dx dy = async {
       let! nextState = game.LoopAsync
       match nextState with
       | Update time -> 
           let dx = if x > 608.f || x < 0.f then -dx else dx
           let dy = if y > 448.f || y < 0.f then -dy else dy
           let x = x + dx
           let y = y + dy
           return! gameLoop x y dx dy
       | Draw time -> 
           game.GraphicsDevice.Clear(Color.CornflowerBlue)
           spriteBatch.Begin()
           spriteBatch.Draw(sprite, Vector2(x,y), Color.White)
           spriteBatch.End()
           return! gameLoop x y dx dy
    }
    return! gameLoop 0.f 0.f 4.f 4.f
}

gameWorkflow |> Async.StartImmediate

game.Run()

And with that we’re done.

Conclusion

XNA/Monogame is a great tool for writing games, and F# offers many benefits to game developers. However the 2 technologies working together do have some rough edges, which can be transformed into advantages using some basic features of F#.

Features such as F# async empower developers to find ways to tame the accidental complexity, introduced by external frameworks such as XNA or WPF.

The XNA Code for this post is hosted here

Posted in Async, F#, Monogame, XNA | Tagged , , , , | 6 Comments

It just works(™)!

I was recently a guest on the .NET Rocks podcast and one of the things that came up was this notion in F# of “if it compiles – it works”. Given the constraints of time on the show (and technical difficulties with sound on my end) I wanted to give a fuller take on why I think this is so, as I can imagine to people not used to F# (or Functional Programming) it may sound like Snake Oil.

No Nulls

Tony Hoare has referred to NULL as his billion dollar mistake. If you’ve written C#, C, C++, Java, et al, just stop and think about how many times you’ve hit unexpected Null Reference Exceptions (hell, the designers of Javascript thought it such a good idea they added “undefined” too!). These are usually trivial to fix – if you own the code. If the exception is in a framework then you might end up having to catch Null Reference Exceptions all over your code and deal with the uncertainty of the state that the unhanded exception has left you in.

In F# classes (and records) are non-nullable by default. This means that if you stick with the happy path you cannot get a null reference exception (in your own code). If you really need to represent a state of Something or Nothing then the Option type is a built in type that allows you to access the values safely via pattern matching or the Option module. Don Syme posted a very entertaining post about this close to a year ago (I wonder if Don should call it his billion dollar saving?).

Of course you can still have nullable classes in F#- but you have to explicitly state this with the AllowNullLiteral attribute – a clear indication that something may go wrong later.

But even Bret “The Hitman” Hart knows this is silly!!

And for the record – “?.” in C# 6 is a lame attempt to solve null in C#.

Immutability

In F# values are immutable by default. This means that state is consistent throughout the application. Imagine passing a list into a void method which add a value to the end. In F# (using the build in List type – which is of course immutable) the append would only affect the local copy of the list in the method – it would have no effect. To capture the change in F# you would have to change the void method (or unit in F#) to return the new list.

Immutability is often discussed as a great way to avoid data races in multithreaded code, but even in more trivial cases it is incredibly useful to know that the state of an object cannot change midway through a method. In C# you may not think twice about a series of void return methods which mutate properties/fields of a class, but this means the state of a class is constantly in flux which may make it hard to reason about it’s state at any given time. This often leads to bugs (especially if you can set references to NULL!).

F# is not a “pure” functional language – hence mutation is allowed, but only if you specify it. This means that by looking through your code for the mutable keyword or the <- operator you can identify potentially problematic areas of your code without even running it.

Return values must be explicitly ignored

Because by default a function has no side-effect, to ignore its result would have been effectively a no-op. The complier therefore forces you to explicitly ignore the return value and this removes an entire class of errors. If you are ignoring lots of results, it’s probably a code smell that you are mutating state in functions – the clue that you are doing something fishy is explicit in the code.

Functional SOLID

One of the things I talked about on the show was Functional SOLID. SOLID is a system which “intend(s) to make it more likely that a programmer will create a system that is easy to maintain and extend over time” (Wikipedia). For an OO programmer it is important to have rules about what to do to create clean extensible software because the defaults lead you to the opposite.

Breaking down how SOLID might apply to a functional language:

Single Responsibility – a function (by default) has no side-effect. Therefore values in => value out. A function therefore by default can only have a single responsibility.

Open-Close – a function can be extended (but not modified) by using higher order functions.

Liskov Substitution (design by contract) – a function signature could be said to be a  stable contract and using the default single responsibility of a function, you are more likely (but not guaranteed) to get the same behaviour, provided the contract is clearly defined. Use higher order functions in place of classes/interfaces.

Interface Segregation – what could be a smaller interface than a function? Use higher order functions in place of interfaces.

Dependency Inversion – what easier way to invert a dependancy than higher order functions?

When you read the above list, it boils down to 2 things – use functions and higher order functions. These are the defaults of functional programming (as opposed to rules imposed by programmers), hence there is no need for SOLID for functional languages.

I made up the term “Functional SOLID” simply to delete it. Consider it my Randall Stevens.

Even More!!!!

Boolean traps exist in all kinds of code – a simple true/false which should be one of the simplest things to reason about but often isn’t.  But things can get even more complex with numbers – what if the int that your function takes is supposed to represent quantity of apples and not seconds since the epoch.

Units of measure help make sure your float of Kg doesn’t end up being used as a float of metres.

But taking things at a more basic level, F# doesn’t even allow implicit conversion between number types – a relatively experienced C# programmer may guess correctly what type x is – and the pitfalls of the automatic conversion:

var x = 1.3 * 2;

but the F# programmer has the compiler watch his/her back:

let x = 1.3 * 2;
error FS0001: The type 'int' does not match the type 'float'

This may seem like paranoia, but as there is no clear default, the compiler default is to make you choose. Which seems fair enough to me.

Conclusion

It’s easy to become institutionalised in a world of OO, where null is the norm,  mutation is everywhere, and large unwieldy classes reign supreme. It doesn’t have to be that way.

Hopefully I’ve helped illustrate some of the ways that F# (and other functional languages) can help reduce common errors in code. As you can see from every example, it’s the default behaviour that gets you to the happy place. You can deviate should you want/need to, but that’s an explicit choice to opt-out of safety, whereas the default for OO languages is to have no safety by default.

Posted in C#, F#, thought | 4 Comments

Book Review: F# for Quantitative Finance

I was recently given the opportunity to review the book F# for Quantitative Finance by Johan Astborg. 

Cover

Disclaimer:

I work in the finance industry, but I don’t do “Quant stuff” for a living. I’m not going to review the correctness of the book as I have to trust the author and the proof readers. 

Book structure

The book has 3 distinct sections – an Introduction to F#, required maths knowledge, and then application of the previous 2 in the context of Black-Scholes and Monte Carlo, following through into volatility, options and a full trading app.

It’s hard to fault the structure – if theres anything I’m not sure I agree with is the F# briefing – Quantitative finance doesn’t seem like a great “Hello World” app so I’d expect most readers to already be familiar with the language before starting this book. That being said, a target audience of people who already know the techniques described in this book may find it handy to have a short (it’s about 75 pages) run through of the language to help them get through the later chapters where they may be more familiar with the subject, but less so with F#.

The next sections go through some basic maths (Averages, Variance, Standard Deviations) in F# and then introduces Math.NET for some of the more complex maths. Personally I think this is a wise choice – Math.NET is incredibly powerful and integrates well with F# and allows the author to spend more time on (at this stage) explaining what the methods mean (and plotting them using FsChart). Once a brief detour of using charts to display data from Yahoo Finance is made (which really showcases the power of F#) its into the options pricing and Black-Scholes formula (by this point around the halfway mark in the book). 

At this point you are really going to want to read this near a PC (if you’ve not already). The algorithms are best understood by using a tactile approach in my opinion – in other words typing out the code and playing with it. It’s incredibly satisfying to see charts based of an algorithm you have just typed (but may barely understand at this point) and provides an excellent way to try to further understand. A description of Monte-Carlo method and the theory is over.

Next up is where it gets hairy. Exploring volatility is a really dense chapter and will probably require several re-reads to understand if you’re not already familiar with the subject. Luckily the author has a clear writing style – but the subject matter is just tricky to digest in 1 go. It doesn’t take long to move past and then we get back into more of F# strengths in domain modelling.

A nice detour into using QuickFIX/N for setting up a trading system (I’ve heard people moan about FIX, but certainly it doesn’t seem so scary with this library) and it’s back into trading options and strategies for trading options. This chapter is quite long and contains detailed explanations of some of the options strategies (such as long/short straddle and long/short butterfly) along with charts to show the payoff. It’s a code heavy chapter, and once again I’d recommend having Visual Studio handy to play with the code.

Finally a trading screen is built up using the information from the previous 6 chapters, which really helps solidify some of the concepts previously described. It’s worth spending some time to at least have a basic understanding of whats come before as this chapter does reference a lot of the previous techniques without heavily retreading it. The book is then finished off with an appendix.

Content

The F# code is neatly laid out and most samples weigh in at under 1 page. One thing I especially appreciate is type annotations in the book – without the benefit of intellisense this is a godsend for helping digest an already tricky topic. 

The samples make nice use of FSChart for visualisation, which helps keep the noise ratio down when charting, although a couple of samples do seem to go the extra mile to show how to do a full WinForms app in place of just FSChart – I’m not sure if there’s a reasoning behind this.

The writing style does vary a little – the more intense chapters are a little terser in terms of explanation, but the code is usually sufficient to provide a starting point for self-discovery. In the “lighter” chapters, the writer covers the topics swiftly, but with plenty of detail. 

The book weighs in at just under 300 pages, which means it’s not especially heavyweight, but it does cover a lot of ground. Personally, I’d ditch the F# tutorial at the beginning, but then I already know F#. 

Summary

F# for Quantitative Finance is a handy book to read if you’ve an interest in quantitative finance. It’s well written and utilises key strengths of F# to make the topic less scary (although by no means easy). I’m not hugely qualified to say how complete a book it is, but what it does cover is clearly written and understandable.

F# for Quantitative Finance is available here.

Posted in F#, Review | Tagged , | 1 Comment

Building a C# compiler in F#

A little over a year ago I wrote a post about Roslyn.

Recently (after seeing Mads Torgersen‘s excellent NDC-london talk) I was inspired to attempt to write my own mini-C# compiler to address some of the missing features in C#.

Mads Torgersen repeating what I said a year ago

Mads Torgersen repeating what I said a year ago

Roslyn

Roslyn is a Microsoft project to rewrite the VB and C# compilers in their respective languages. After Mads talk, and listening to the (proposed) new features for C# 6 I couldn’t help but feel a little underwhelmed with the direction of C#.

Mads’ justification seems reasonable on the face of it – C# 2, 3,4 & 5 have all had major new language additions (namely generics, linq, dynamic & async) and that C# 6 is more of a ‘tidy the pain points’ release. But I had a number of ideas for improvements, and unfortunately only two are in C#6 (primary constructor and read-only auto-properties).

To make matters worse, it is not one of the goals of Roslyn to allow language extensions – C# spec is still owned by the C# team, and Roslyn wont allow you to add your own syntax. I get this – it would be fairly terrible if every codebase was C# + custom changes. But I can understand the desire from users to at least open source Roslyn (especially as it doesn’t run on Mono according to Glenn Block of ScriptCS fame – although I haven’t verified this myself).

It was this desire to play with language features that MS are not going to implement that drew me to writing my own C# compiler.

Before we begin

Phil Trelford’s excellent series on writing a SmallBasic compiler has to be the the best intro to building a compiler in .NET today – it covers parsing and compiling actual code from SmallBasic. Interestingly we had the similar idea at the same time about writing a parser & compiler for C#.

Now, I didn’t do any compiler theory in uni, I’ve never written a compiler before and I’ve only ever looked at Reflection Emit in anger. But despite these limitations I have a fairly capable C# 0.5 compiler (in that it is a subset of the C# 1 compiler). Which means you can do it too – it took me less than a month.

The source code for the compiler is here. It currently supports compilation of

  1. Classes
    1. Methods
      1. Local Variables
      2. Return values
      3. for, while and do while loops
      4. Comparisons and arithmetic
      5. Method calls (static, instance and “this”, on built in and custom defined types)
      6. Constructor calls
    2. Fields (no initialization)
    3. Constructors
  2. Interfaces
    1. Methods
  3. Enums
    1. Custom values – always 0 based
  4. Empty Structs

Big things currently missing (most are trivial plumbing, but I’ve just not had time or inclination yet) –

  1. Foreach, lock, switch, if/else
  2. Full range of modifiers (ie static, virtual, sealed, etc)
  3. Properties
  4. Struct bodies
  5. Constructor Bodies
  6. Field initialization
  7. Inheritance
  8. Attributes

But even with those limitations it’s still possible to write some basic programs.

Given C# is a (fairly) rigid spec, and this is a small version I’ve allowed myself some liberties:

  • There is code that should compile that doesn’t (even with above limitations).
  • There is code that shouldn’t compile that does.
  • As this is my first attempt at a C# Abstract Syntax Tree (Abbr AST) there are bits that are (in retrospect) plainly wrong, but work OK for now. Phil’s C# AST is more robust and at some point I’ll switch to using his.
  • You can only compile 1 file at a time.
  • Performance is pretty weak (of the compiler). Given the above limitation it’s not a big deal, but you wouldn’t want to build entity framework with it (courtesy of F# for fun and profit).
  • There are entirely unimplemented features – some I will address, some I wont (switch for example is so weak in C# it doesn’t feel worth the effort).
  • Error messages are virtually non-existent – most compile errors are handled with a “failwith” which will simply throw an exception.
  • It can only compile DLLs currently.

I don’t want to go into too much detail about specifics of the code here – the full source is available if you want it, and you can ask me questions in the comments, should you feel the need. What I’d like to talk about is some of the conceptual issues from transforming a piece of text, into a loose structure, into a tighter structure, into IL.

Parsing C#

Phil’s blog post about parsing C# is an excellent start of turning C# code into F# Discriminated unions. I took a slightly different direction of using fslex and fsyacc to transform plain text into code, but the basic principle is the same – Discriminated Unions are great for describing Syntax Trees.

Both approaches to parsing have pros and cons. FParsec has some clear advantages of fslex/fsyacc – error messages are much better and you can easily use it from fsi while Fslex/fsyacc require a pre-compile step and are more verbose, but (to me) have an easier to learn syntax and a less steep learning curve. A more detailed comparison of fparsec vs parser-generator can be found here.

Transforming an AST into IL

Inception

Once we have a description of the code structure loaded into an AST  the fun begins. There are a number of problems solved by the C# compiler that are really convenient for the developer, but are tricky for the compiler writer.

  • No header files means that the compiler must decide the optimal path for generating types (unlike languages with header files where the public type definition must be predefined – by the programmer).
  • Mutually recursive types means that you cant simply compile in the order the code is presented.
  • Void as a type/not a type (Void exists in the system namespace, yet it doesn’t make sense as a type in any other place than a method declaration)
  • Null as a thing, but not really a thing.

You can think of the AST loaded from a text file as a loose representation of the code. You can write a completely valid AST that is utterly nonsensical from an execution point of view (for example calling non-existent methods, using undeclared values, type-mismatches, etc). One of the 1st tasks we need to do with this loose structure is to build it into a strongly typed and validatable AST. In the source I’ve simply gone from Expr to TExpr (where T stands for Typed).

To be able to build a typed representation we first need to stub out the type (class, interface or struct). This is because we may have a Method that returns an instance of a class defined later in the code. By “stubbing” the types we can stash them away to look up later.

Once we have stubbed the types, we need to do the same thing with the body of a type – a method may depend on a field, a property or another method, so we define the stub for methods ready to fill in later, but keep the method stub in a structure (in fact a tuple of method builder and a function to build it’s body) – think function prototypes in C. By the end of this stage we have a complete list of all user defined types, and members of those types, but importantly, there is no actual *code* emitted – purely code structure.

The “builder” function returned then converts the AST to a “Typed” AST, which is then validatable – I currently skip validation and skip to IL Generation. But it is now rich in metadata about the code – metadata which is used to convert the Typed AST into CIL.

Gotchas

The premise is actually deceptively simple – the devil is in the details.

  • The Reflection.Emit APIs do inheritance patently wrong – this cost me about 2 days of development time (although had I RTFM first I could have avoided this)
    • TypeBuilder derives from Type, so exposes Type’s methods, but they fall over at runtime unless you call CreateType first, which prevents further modification. The same problems apply to MethodBuilder (derives from MethodInfo), ConstructorBuilder (derives from ConstructorInfo), FieldBuilder (derives from FieldInfo) and PropertyBuilder (derives from PropertyInfo)
    • This means any userdefined types must be stored seperately from referenced assembly types for appropriate lookup on methods, fields, etc, rather than calling existing methods. F# really helps keep the ceremony down as you can partially apply functions pre-loaded with these definitions, rather than passing lots of data-structures around.
  • IL Generation is fairly finnicky – for example to call a method on a struct local variable you must load the struct using ldloca instead of the usual ldloc.
    • F# Pattern matching makes light work of handling these cases – once you know they exist.
    • The entire IL generator code which covers most use cases is ~150LOC. This is the most complex file in the project, but is hardly difficult.

Conclusion

People seem to be waiting for Roslyn to solve either meta-programming or scripting problems they either have now or think they’ll have in the future. The excellent .NET Rocks podcast has had a lot of people on recently to talk about what they’ve either done with Roslyn or plan to do, and it feels like a lot of it is entirely plausible without Roslyn.

The spirit of this post is to encourage you to not wait and to build it yourself. You probably don’t need the full C# 5 experience for a scripting language in your app. Rather than wait (Roslyn still has no official release date) I want to show you that it is not only possible, but entirely feasible to do this right now with a little thought as to what you are going to achieve – the provided source provided weighs in around only 800 lines of code so it’s not heavyweight by any stretch. The worst case scenario is that you rewrite your feature using Roslyn (once it is released)/Mono C# Compiler/CSharpCodeProvider, and you have some fun and learn something new in the meantime. Which doesn’t seem like such a bad case. Remember kids – this is the year of code – time to stop procrastinating and write something!

F# is a powerful choice for writing a compiler – Discriminated Union types, Record-Types, pattern-matching, immutable-by-default (the code provided is almost purely immutable – I cheated in 1 place, with a generic dictionary) and 1st class function and tuples makes light work of defining a syntax tree and transforming it into executable IL code. In fact I can’t begin to imagine how painful it would be to write a compiler without these features……

Code – https://github.com/neildanson/MicroCS

Posted in C#, Compiler, F# | 4 Comments

Building Mono on a Raspberry Pi (Hard Float)

The cool thing about the Raspberry Pi is that it is really really cheap and really really popular.

Until recently the worst thing about the Raspberry Pi has been the lack of hardfp version of Mono, leaving us .NET developers with 2 options:

  1. Learn something new (like Scala)
  2. Run the softfp Mono on the older Debian Squeezy Linux Distro

Now I know C# developers will be balking at the idea of #1, which only leaves #2.

Until now…….

Now Mono supports hardfp and a recent Mono (3.2.7), which is Good News(tm) as that means it supports the sgen GC as we’ll has the hardware floating point extensions on the ARM6 on the Pi.

Instructions are available here, but I hit a couple of small wrinkles on a fresh Raspbian install, so for my benefit and yours:

Step by Step

A couple of people have commented about how they needed to sudo some of these things (I didn’t need to – don’t know why), but remember, when in doubt sudo

  1. Ensure you have 2GB+ free on your SD card and a lot of time to spare
  2. Launch a terminal window/ssh into your Pi
  3. sudo apt-get update
  4. sudo apt-get install mono-complete
  5. sudo apt-get install automake
  6. sudo apt-get install libtool
  7. git clone git://github.com/mono/mono.git
  8. cd mono
  9. ./autogen.sh –prefix=/usr/local –enable-nls=no 
  10. Note the above step reads two dashes before prefix and enable-nls. Thanks crazy fonts (and eagle eyed readers)
  11. sudo make
  12. Wait a long time (6 hours +)
  13. Ignore the errors and hope they don’t mean anything
  14. sudo make install
  15. Wait some more
  16. Ignore the errors and hope they don’t mean anything
  17. PROFIT!

Now type mono –version and hopefully see this:

pi@raspberrypi ~/mono $ mono --version
Mono Runtime Engine version 3.2.7 (master/e94da6d Tue Dec 10 00:31:36 UTC 2013)
Copyright (C) 2002-2013 Novell, Inc, Xamarin Inc and Contributors. www.mono-project.com
TLS:           __thread
SIGSEGV:       normal
Notifications: epoll
Architecture:  armel,vfp+hard
Disabled:      none
Misc:          softdebug 
LLVM:          supported, not enabled.
GC:            sgen

For directions on how to be able to build and run Winforms apps see this excellent post here

Posted in C#, Mono, Uncategorized | 29 Comments

Desktop class performance on a mobile phone?

I recently bought an iPhone 5S (this is partly why I’ve taken a short detour from the platform game – this will resume in my next post!). Once again Apple have managed to create hype around a new CPU which (according to Apple) is as powerful as a desktop PC. Now a desktop PC could range from a crappy little Atom to a new Mac Pro, so the term is perhaps a little vague.

I’m going to try to define it :)

So I go back to my Raytracer. Modified the code a tiny amount, so it runs on my Mac under Mono and iOS under Xamarin iOS. This seems pretty fair to me – Mono-a-Mono if you will. Then I moved it to Android and tested on Windows as well – because why not?

So how does a mobile ARM Dual Core CPU running (according to reports) somewhere around 1.3Ghz compare to an i7 Quad Core with hyper-threading @2.6Ghz? Or a Snapdragon quad-core on a different mobile OS?

All builds in release mode, tested outside the debugger (in no particular order):

Device Time OS Runtime CPU Spec
iPhone 5S 3.43 iOS 7 Xamarin iOS 7.03 (sgen/llvm) A7@1.3Ghz x2
Macbook Pro Retina (2012) (i7 3720QM) 1.04 MacOS Mavericks Mono 3.3 sgen i7 @2.6Ghz x4 (x2 HT)
Macbook Pro Retina (2012) 0.20 Windows 7 .NET 4.5 i7 @2.6Ghz x4 (x2 HT)
iPad 3 9.6 iOS 7 Xamarin iOS 7.03 (sgen/llvm) A5X @1Ghz x2
iPod Touch 4th Gen DNF iOS 6 Xamarin iOS 7.03 (sgen/llvm) A4 @ 800Mhz
Nexus 7 (2013) 2.5 Android Jelly Bean 4.3 Xamarin Android 4.10 Snapdragon S4 @ 1.4Ghz x4
Samsung S4 3.2 Android Jelly Bean 4.3 Xamarin Android 4.10 Snapdragon 600 @1.8Ghz x4
i7 W3520 0.68 Windows 7 .NET 4.5 i7 Xeon @2.67Ghz x4 (x2HT)
i5 E6410 0.44 Windows 7 .NET 4.5 i5 @2.67Ghz x2 (x2HT)
Intel Atom 5.32 Windows 8.1 .NET 4.5 N270 @ 1.6Ghz (x2HT)

Try the code on your own machine – source here (as I quickly and dirtily knocked this together you’ll see I don’t do any clever code sharing – maybe a second pass later!). I haven’t optimised this at all, but the core code is *exactly the same* so is as fair as I can make it – the only different is how the results are displayed.

What does this prove?

Nothing really. But I was bored and fancied seeing how fast my own code ran on my new toy. Is the A7 a desktop class processor? Well it’s somewhere between an Intel Atom and an Snapdragon S4/600, so you should make your own call there. It’s pretty fast, regardless of how it compares to a desktop CPU.

There are some unexpected results above – the i5 being faster than the i7 Xeon and the Nexus 7 being faster than the S4, but each test was run multiple times and the figures were the average of 3 runs with outliers excluded.

I guess if anything it proves that Microsoft/Xamarin have done an awesome job on giving me the tools to have an idea, code it in minutes and run it on 4 different platforms really easily. And that’s a good thing, right?

Posted in Android, benchmarking, F#, iOS, Mono, performance | Tagged , , , , , | 2 Comments