Bullet Physics demo DirectX C++ app on Windows Phone 8

I’ve finally gotten around to updating my original Windows Store Bullet Physics demo (http://taumuon-jabuka.blogspot.co.uk/2012/04/bullet-physics-and-directx-11-on.html) to build for the Windows 8 final release.

While I was at it, I also got it working for Windows Phone 8 – code is on github https://github.com/taumuon/WP8-Bullet. There weren’t many changes. In building Bullet for ARM, I got around lots of parameter alignment issues by defining BT_USE_DOUBLE_PRECISION. This was the quickest thing to do, and may have performance implications but the performance running on my Nokia Lumia 920 seems encouraging. It wouldn’t have been a much bigger change to instead see if ARM is defined.

 

ViewGene now has mapping

The newly-released version of my genealogy/family tree Windows 8 app now has Bing Maps integration, which allows the migration paths of all ancestors to be plotted.

I wanted to see visually how my ancestors moved, after researching how my ancestors moved from villages in the 17th century into towns, and then larger towns.

I’d love to see anyone else’s migration paths!

The below is just a made up sample – I’ll share my map after sanitising the data.

Try it in the Windows Store.

Option pricing in F# using the Explicit Finite Difference method

It's been a little while since I've coded any F#, so I've done a little coding kata to polish off the rust.

I've converted the explicit finite difference option pricing example from (Paul Wilmott Introduces Quantitative Finance).

I followed similar steps as those I performed in my previous blog post on the binomial tree option pricing; I converted the VBA code into very similar looking imperative F# code, before refactoring out the loops into recursive calls.

It was a useful exercise as converting the algorithm made me actually focus on the mechanics of how it worked, much more than simply translating VBA code into imperative F#. It’d be interesting to hear in the comments whether people find it easy to read.

The code is available https://gist.github.com/taumuon/4999749.

ViewGene

This blog has been quiet for a while, but I've been busy working on a Windows Store genealogy application, ViewGene.

This is quite a niche application, but it was written to cope with a couple of use cases which are missing from other family tree websites and applications – it's useful to have it open in conjunction with your favourite family tree software or website.

The first problem is that many of the family tree websites, when showing the whole tree (pedigree chart) of ancestors, compress the tree to make the best use of screen real estate. This is fine to save paper, but it does make it very difficult, when navigating the tree, to know what the generation is of any ancestor on the screen.

ViewGene ensures that ancestors of any generation all appear at the same vertical level – this makes it easy to see which branches of the tree need more investigation. This view wouldn't necessarily work well when printed out, but touch-based pan and zoom do mean that it's easy to zoom out to see the 'shape' of the tree, and to zoom in to see the individual details, meaning that it works for interactively investigating the data.

The second use-case is to validate and see the lifelines of the ancestors. Many of the family tree websites allow free-form entry of dates. This means that it is easy to mistype and enter a date of the wrong century, or to enter semantically incorrect dates such as a child born before the father. The Timeline Fan chart allows for some of these problems to be easily seen. The chart also allows the user to see, for example, which ancestors were alive on a given census year.

The current release includes very limited validation, to check that dates match allowable GEDCOM formats, but does not check for semantically incorrect dates. Also, there is very basic date inference for missing dates. If I devote any more time to the application, I'll want to improve both of these points – it should be possible to validate that children were conceived whilst both parents were alive, and that siblings can't have been born in the same gestation period etc.

Windows Store application observations

The chart functionality is quite generic, and would work well on any touch-screen platform (such as iOS), much of the development effort was spent in building an application following Windows Store idioms.

The first was to ensure that the application works when snapped (though this could do with further improvement). The second was to use semantic zoom, which definitely makes it easier to navigate through a large number of individuals in the GEDCOM file). Adding a very large number of individuals to the GridView results in Invalid Quota exceptions being thrown. Even if this weren't the case, there would be a usability issue in navigating through so many individuals. To fix this, if there are a large number of individuals in the GEDCOM file the application adds a further level of navigation through the first letter of the surname.

It would be quite easy to add images to the application (such as pictures of ancestors, or scans or pdfs of documentation), but it is quite tricky in a Windows Store application – the GEDCOM file contains paths to images, but it is not possible from a Windows Store application to open files other than via the open file dialog. It may be possible to work around that by instead presenting an open folder dialog (which would allow access to all files and sub-folders within that folder) and then allowing the user to choose the GEDCOM file from a list, but that definitely feels clunky.

The Pedigree Chart is implemented as an ItemsControl, populated with either Boxes or Lines, with an ItemsTemplateSelector to distinguish between them. It works well, and there are no obvious performance issues, but the ItemsControl does crash if too many items are added, so the number of ancestors are limited to 1000.

The timeline fan is implemented as C++/CX WinRT component, deriving from SurfaceImageSource, with all drawing being performed in Direct2D. If I get time to invest in this, I want to switch out to a VirtualSurfaceImageSource, so that the amount of information presented is customised to the zoom level on the screen.

Non Windows Store issues

There are a few issues not related to a Windows Store application.

The application currently does not have editing – the GEDCOM format is too flaky to be a reliable interchange format; it does not round-trip without the possibility of corrupting the user's information. Ideally, the application would allow connecting to a website to obtain the user's family tree information, but ancestry.com does not provide a user-accessible API. Geni.com does, and if I get time I intend to investigate that.

It is also trickier than it needs to be to implement mapping – it looks fairly easy to integrate with Bing maps, but the problem is that location data in the GEDCOM file doesn't necessarily match up with the required data for plotting points on the map. It is possible to ask the data to enter that information, but then the application should maintain it. This isn't too much of a problem, but it should be maintained per GEDCOM file, and to allow the user to re-import updated GEDCOM files would rely on GEDCOM merging.

The GEDCOM parser is written in C#, mostly as a GoF state machine, with some functional elements. When I originally started coding this up, I intended to start by creating a clunky procedural looking parser (which maintains the state with many flags), then show how an OO GoF pattern was nicer, then show how a F# implementation is nicer still. If I get time I still intend to create a F# version of the parser.

Speaking of F#, the layout logic for the timeline fan is implemented in a functional way, but would be nicer in F# - the problem is that it then needs to communicate with the WinRT component to do the drawing. F# can't directly interop with WinRT, so it would be necessary to create a C# wrapper or consumer of the F# library just for this – and it seems overkill.

Overall, developing a Windows Store app is fairly easy if you have Silverlight or WPF skills. There are quite a number of features I want to add to the application, but how much time I'm going to dedicate to it depends on feedback or download numbers of the current version of the app.

Binomial Tree Option Pricing in F#

This post will look at implementing the binomial tree algorithm in an imperative style, and refactoring it to be more functional.

The wikipedia page on the binomial options pricing model provides pseudo-code for the pricing of an American Put option.

That code can be implemented almost identically in F#.

and is called as follows:

Functional programmers have probably died a little on the inside on seeing that code, but one of the good thing about F# being multi-paradigm is that it's easy to take code of this form and implement it, and test it for correctness before refactoring.

I did actually look at whether the results of the code were as expected at this point, but I'll cover this later in this blog post.

The first thing to do is to change the initial values V to be created more functionally:

Now, the main algorithm consists of two parts, an outer loop where each 'level' of the tree is calculated stepping up towards the root, using the results of the previous level’s nodes (the nodes nearest to the leaves). The inner loop iterates over all of the nodes at a given level calculating the option's value at that node.

First off, the outer loop can be replaced with a recursive method:

The next change is quite minor – it's for each pass of the inner loop to create a new array, instead of mutating the vi array:

This change now means that there's no need for any mutable state, so the initial values can be created as a sequence instead of an array, and the inner loop can be written in a functional style:

I find this code style is clearer to understand than following the array mutations to see what each part of the code is doing and how those parts interact.

If I was implementing this in C# I'd probably change the variable names to be more descriptive (e.g. strikePrice, riskFreeRate etc) but as one of the key advantages of F# is its succinctness it makes more sense to leave the well-known symbols in. Anyone implementing the algorithm with knowledge of the domain would know what the symbols mean without the more verbose names.

Validating the results

The calculated option value with the requested parameters is 4.486090. Running the EqutyOptions example in the .NET port of QuantLib, QLNet (http://sourceforge.net/projects/qlnet), with the same parameters gives the following results:

The figures are in the same ballpark, but the difference is curious.

Chapter 45 of GPU GEMS 2  creates the initial values in this way:

This gives a result of 4.486375 which still doesn't match QLNet, but is nearer.

The result of running the Cox version of Bubo's code from here http://cs.hubfs.net/topic/None/59053 also equals 4.486375, which matches the results of using this initialisation function. As an aside, I like how that examples shows how F# partial function application allows the variations on the algorithm to be composed, and much more succinctly than using OO.

Bubo’s Tian model does match QuantLib's result exactly. I'll have to dig a bit deeper to figure out which variations on the binomial tree model these different examples are using.

The code is available here: https://github.com/taumuon/FSharp-Binomial-Tree

Metro Bullet source code

I've updated the demo that shows the Bullet Physics Engine in a DirectX 11 Metro application to build in the Release Preview drop of Visual Studio (original blog post: http://taumuon-jabuka.blogspot.co.uk/2012/04/bullet-physics-and-directx-11-on.html ).

The code needs some tweaks - I need to change the manifest, and change some stuff over to Platform::Agile, but it builds and runs so I thought I'd get it out there.

The code is available at: https://github.com/taumuon/Metro-Bullet

More playing with monads

This blog post will look at using the continuation monad to sum the nodes in a tree, and then look at a case where a more complex monad is needed.

The book Real World Functional Programming gave an example of an unbalanced tree, which was deeply nested such that recursing over the tree to sum the values would blow the stack:

The solution provided was to sum the tree using continuation passing:

This is now able to sum the tree without crashing, but the code doesn’t flow as well as in the original sumTree method. However, monads can come to the rescue again, in this case the continuation monad:

The code flow now is easier to understand. The continuation passing style and continuation monad turns the code flow inside out, which isn’t a big deal, but means that the func to perform on the result needs to be passed in:

Parallel sum

This is all well and good, but to exploit multicore machines, I want to take advantage of the parallelism in the tree summation algorithm, by summing the different branches of the nodes using tasks. A naïve implementation to do this may be:

The problem with this is that it runs slower than the sequential case for a large balanced tree –if there are only 4 cores in the system it’s counter-productive to create thousands of tasks. The current depth of the tree should be passed around, and tasks spawned until traversal reaches that depth:

This is now faster for a large balanced tree, but for the deeply nested unbalanced tree it throws a StackOverflowException. Note that sumTreeParallel coped with arbitrarily nested trees, as the work to be done no longer kept being pushed onto the stack.

More state is being passed around (the current depth), which is external to the main business logic – it does feel like the state monad could be used here. First though, this is fixed up so that it has the efficiency of the parallel summation, but can cope with arbitrarily deeply nested trees:

Urghhhh. The code is definitely more convoluted now – I played with using the state monad to pass the depth around, but it’s not tail recursive. I thought that it might be possible to make use of the continuation monad here, but the problem is, is that it really needs aspects of both the state and continuation monads. I’m not sure how monad combinations work in F#, but I thought I’d throw this out here to see if anyone shows me the light. The post The Mother of All Monads does say that all other monads could be implemented in terms of the continuation monad, but I couldn’t see an example of anyone implementing the state monad in terms of the continuation monad.