less bel canto

So after mucho procrastination I’m finally diving into Erlang. As I’ve said many times before, the new cloud-based web platforms such as Heroku and AppEngine are great for rapid development of simple webapps, but are lacking if you want to do any serious data gathering or hardcore calculations at the back end.

Some initial observations:

Compilation is a serious barrier to rapid learning. If you come from the Ruby/Python web world you’re probably used to typing little snippets of code into the interactive prompts, and seeing what happens. Erlang has an interative shell, but you have to compile files before you can run then. Unfortunately this simple shift from a one-step to a two-step process seems to really mess with my productivity – I just don’t seem to get the quick feedback my brain needs to get the concepts to stick. I’d recommend setting up a Rake file to compile/run target files in a single step – so you can call ‘rake run whatever.erl’ and get that nice quick feedback loop going.

The language reminds me a lot of Python, particularly the heavy use of anonymous functions / functions as first-class objects. Also the libraries don’t look too bad; there’s stuff in there for HTTP clients, HTTP servers, XML parsing, JSON parsing [with Mochiweb], regex; nothing the absence of which would be a deal killer for web programming.

Immutability doesn’t hit you over the head I had thought that moving to a ‘true’ functional language would require a major change in programming mindset. In fact for the most part you can carry on programming as normal, occasionally bumping up against a proverbial wall [why can't I create a loop with a counter variable ? why does updating a dictionary cause a brand new dictionary to be created ?] You then reflect awhile on why that wall might exist, and why your previous assumptions regarding loops/dictionaries/[insert favourite feature of choice] might not have been very heathly. A month ago I couldn’t have told you what a side-effect free language meant or implied. I’m not there yet, but I start to see the benefits – in particular why you need to ban side effects in order to parallelise your code properly. But in the meantime, it’s nice that Erlang introduces these concepts to you gradually.

Concurrency support is a real eye-opener I’d never really considered that processes could be baked into the language rather than the operating system – now of course it makes perfect sense. It’s worth spending some time building sample servers from first principles, at least so you have some idea of what OTP gen_server is doing – see Joe Armstrong’s book or Kevin Smith’s screencasts, both highly recommended.

OTP / Mochiweb could be my replacement for Rails. OTP seems to have good support for distributed processes, error handling, logging. Mochiweb contains a stripped down HTTP server, proper JSON support, and a Rails- like project generation script whose results seem to be OTP-based. There’s still some work to do [which template engine ? which persistence store ?] but I think the combination of the two might provide the Rails replacement I’m looking for, with the all-important support for distributed processes.

Plenty more work to do. Next step is to setup a Mochiweb sample project and see if I can replicate a simple Rails CRUD scaffold.

I really want to use Seaside because of an impedence mismatch I get when designing front ends.

Webapps have come a long way from the days when they were a series of static pages held together by links. A better metaphor for a modern webapp might be a car dashboard; a series of persistent components held together in an grid-like layout, whose state changes dependent on the user interaction.

Most current web frameworks betray their origins and don’t recognise that reality; the view is typically constructed as a series of pages, with little thought towards the commonality of components within those views. Rails, a great framework in so many respects, resorts to ‘partial’ pages – view fragments which can be embedded in other pages. This is a hack at best; if you create a filter bar partial view for example, then you can bet your boots you’ll have to create a related FilterBar model elsewhere to persist it. Don’t Repeat Yourself ?

Seaside recognises this mismatch and takes it to its logical conclusion. View objects are modelled as stateful components, and contain :renderContentOn methods which determine their view. Pages are constructed as trees of components; page rendering is achieved by recursively calling each component’s :renderContentOn method to create a single HTML page.

Sounds great; what’s the problem ?

The problem is the rest of the stack.

Doesn’t play nice with CSS and Javascript

Not so much that it doesn’t play nice, more that it ignores them; Seaside seems to think HTML is the start- and end- of interface design. Which is maybe why all the sample applications look so awful. In the real world you need CSS [lots of it] to make your front end look sexy, and Javascript to make it interactive. In fact I’d go so far as to say that the HTML part is the least problematic of the HTML/CSS/JS trinity; assuming your HTML is mainly made up of divs, you tend to end up with miles more CSS formatting markup than the HTML itself.

So it’s disappointing that having gone to such lengths to create an OO- style view solution, Seaside couldn’t find a way of winding CSS into the equation; according to the last book I read the best practice was simply to use an external CSS sheet.

And as for JS, the last word in Javascript integration for Seaside is apparently Scriptaculous. JQuery anyone ?

No canonical persistence solution

I want my persistence to be like my motoring – easy, reliable and boring. ActiveRecord hits the spot perfectly – don’t think about persistence anymore, get going with coding your app. Unfortunately Seaside provides you with a range of options [Magma, Glorp], none of which I really care about; it’s back to the Java philosophy of “here’s a box of bits and wires; all you need to do is assemble it”.

I. Don’t. Care.

Tell me which one I should be using, and make it get out of my way.

No pushbutton deployment options

Heroku. AppEngine. Don’t come back until it’s that easy.

The problem is, in the real world folk need to Get Things Done. If Seaside came with just one of the warts above, it might be worth diving into for the benefits it brings. But with all the baggage above ?

No way. Sorry Seaside.

So I blogged a couple of days ago about how you might use insights from the Black Scholes formula to price options in the long-term soccer markets. To recap, here are the key points:

• We want to simulate the number of points a team might achieve over the course of the season
• The Season Points markets provide the mean for the distribution
• The simulation can be divided up into 38 [English Premiership] time periods, one for each match
• Match rules define the variance within each time period – 3 points for a win, 1 point for a draw, 0 points for a loss

The graph on the right shows the simulated season points distribution for three sample teams [x-axis shows total simulation points] For the record, the Season Points prices for these three are as follows

which correspond to the peaks of the distributions in the graph on the right.

The area under each graph is 1; each distribution has a relatively ‘normal’ shape. In fact the middle distribution ['Everton'] is slightly flatter than the other two, presumably because of Hull and Liverpool’s closer proximity to the two extremes [0 points and 114 points respectively].

The key point here is that we haven’t needed to provide any external variance/volatility parameter to generate these distributions; they result from simple application of the match rules.

Next step is to convert these points distributions to positional probability.

The reason you need this step is because all the common contracts in the market [Winner, Promotion, Relegation] are a function of a team’s final league position rather than how many points that they achieve. However given we have points distributions for all the teams, it’s easy to calculate where each team finished under each simulation path, and then calculate the probability of each team finishing in each league position.

The graph on the left shows the probability of each team finishing in each position [x-axis shows league position]. This time the shapes are reversed; by virtue of their higher number of season points, Liverpool tend to finish in the higher places [on the left hand side].

The graphs also have very different shapes, determined by the proximity of other teams [not shown] to them; for example the Everton graph has a relatively steep left-hand side [they'll have difficulty breaking into the top four], but a shallow right-hand side [there are many teams below Everton who could easily take Everton's expected 5th/6th place].

There’s a huge amount of hidden information which can be extracted from these Season Points markets

Finally, let’s price some options. Remember we have previously generated a ‘position probability vector’ for each team [the probability of each team finishing in each position]. Market contracts are a simple function of this vector; for example

• ‘Winner’ market pays off 100% if a team finishes in first position; zero otherwise
• ‘Relegation’ market pays off 100% if a team finishes in the bottom three, zero otherwise

An option price is just equal to the sumproduct of this ‘contract payoff vector’ and a team’s positional probability vector. If we perform this calculation for the Relegation market and then compare the results against market prices, we get the graph on the right.

Not a bad fit, but why are there some differences ?

The 64 million dollar question; I’ll try and go some way to explaining in the next post.

Betfair may be doing well, but their SOAP api is stuck in 2002. You can see it was basically designed for Java/DotNet clients when the whole SOAP/WSDL/UDDI stack was all the range, and no-one ever thought you would want to do this stuff in Python, Ruby or anything non-enterprisely.

Well, 2009, here we are and Python, Ruby and friends are most definitely in the ascendency at the expense of their enterprisey brethren. And I want to use the Betfair API. Problem is, given the general disdain of the open source community for the whole WS-clusterfuck, there aren’t really any good SOAP libraries for dynamic languages around. I had a bad experience with soap4r [Ruby] a while back and then an even worse one with Suds [Python], where different versions of the same library returned different results on different platforms.

So here’s my own answer – use Ruby’s excellent XmlSimple library to convert your offending SOAP messages to JSON, and live in a lovely world of ruby Arrays and Hashes.

It’s not quite perfect –

• You can’t build the full SOAP message as XmlSimple/JSON doesn’t differentiate between XML elements and attributes [attributes being required in the SOAP envelope but thankfully not in the body]
• You still have to deal with all the SOAP content types within the messages; but thankfully, once converted to JSON, they’re easy to filter out

But hey, this is open source … get to work!

Basically you need to extend the BetfairApiClient class to include your own methods such as get_all_markets, implementing the bits of the API you’re interested in.

The code also contains an implementation of HTTP post which may be useful; building on the standard net/http libraries to handle HTTPS, custom headers etc.

An ambitious title to mark the start of the new football season this week; I’ve used this code for the past seven years so I think it’s time for it to be open sourced and for me to look at new stuff.

Black Scholes is the original option pricing formula, enabling the pricing of call and put options on a whole range of underlying indices [stocks, bonds, currencies, interest rates] [when suitably modified]. It makes a range of assumptions about the underlying asset:

• the asset’s price process follows a lognormal distribution
• the asset grows at the risk-free rate
• the variance of the asset’s price distribution is determined by an external ‘volatility’ parameter

Once the distribution of asset prices has been generated, the formula then calculates the call and put payoffs as a function of the asset’s terminal values.

I think you can use these insights to price options on a soccer team’s performance over the course of the season.

Sporting Index provides a range of ‘Season Points’ markets on different English and European leagues; these are effectively futures contracts on the number of points a team is likely to get over the course of the season. You can calculate the average number of points a team is expected to get from each match from them, a number which can then be used to determine the mean of the points distribution during the simulation.

Black Scholes models the change in a stock’s price in an incremental time period; the external volatility parameter is used to calculate the range of possible changes during that time period. In this case we can substitute an individual game for that incremental time period; the nice thing is that we don’t need an external volatility parameter since there are only three possible pre-defined outcomes [0, 1, or 3 points]. The number of time periods in the simulation is defined by the number of games in the season – 38 in the case of the English Premiership.

So now we have numbers for a team’s expected points per match (defining the mean of any points distribution we simulate) and have specified a process which we think a points simulation should follow (eliminating the need for an external volatility parameter).

The next step is to value contracts available in the market. In place of calls and puts, we typically have ‘Winner’, ‘Promotion’, ‘Relegation’ markets as standard; Betfair is the best place to get prices from [Betfair also include a whole host of other markets which could be priced in a similar fashion, particularly in the English Premiership - Top Two/Three/Four/Six, Without Big 4, Betfair Handicap etc].

There’s a small sleight of hand here in that these contracts are a function of a team’s league position at the end of the season rather than the number of points they achieve. So under each simulated path the simulated points have to be converted to final league positions [a simple matter of sorting and indexing]. From these position numbers you then need to calculate a ‘positional probability’ matrix [the probability of each team ending up in each position in the league]; option prices are then a sumproduct of contract payoffs and positional probability vectors [see code for more details].

Okay, let’s stay you’re still with me.

What will you find if you do this, and compare the resulting prices to the market ? Well if your experience is similar to mine you’ll see that prices are inline for roughly 90% of the time, but about 10% of the time there is a difference.

What does it mean if there’s a difference in prices ? That the Season Points market is pricing a different underlying asset distribution from the market you’re currently looking at.

Can you make money out of this ?. Yes, in my experience. You need to construct low-risk positions of Winner/Promotion/Relegation contracts on the one hand, and Season Points contracts on the other.

Where can I learn more ? Have a look here to see these ideas in action.

Well, that’s the theory. I’d encourage you to simply run the code below under a standard ruby interpreter – it should give you a better idea of what’s going on. I’ll follow up with a later post on how to apply this code in practice.

Interesting stuff from Zed Shaw’s Lamson project

You see, around 2003 or 2004 the concept of “framework” changed. Before then all you needed was a server with an extension API named so that it rhymed with “Servlet”. As long as your server provided a way to drop a class into the processing queue and let a programmer handle the request you could call that a framework.

Then along came the modern frameworks like Django and Rails that included everything you needed in a bundle that you could use right away. They had ORM, templating, routing, higher level request processing, email support, REST support, and anything else you might need for the 80% of your application you don’t care about.

And then in an interview with Ted Dziuba:

In programming, there are many protocols and standards that are ill understood by the masses. Every now and again, and alpha programmer will come along and put a nice API on top of one of these protocols, which opens the field up to anyone with a computer and enough denial power to turn that humility into self-confidence. Rails did this to web development, JQuery did it to Javascript, and now Lamson is doing it to e-mail.

Now I’ve no idea what I’d do with an ‘email app framework’ other than spam folk with Viagra ads; but if I wanted to, I’d probably reach for Lamson. Because the process Zed outlines above mirrors precisely what I went though with Java in the webapp space circa 2005 [before Rails] and Javascript in the browser space circa 2007 [before JQuery] – spending 100% of time stitching your stack together rather than focusing on the problem domain. Various combinations of Spring, Hibernate, iBatis, JDBC, JSF, JSP, Tapestry, WebWork were, franky, monstrous.

Right off the bat I can think of a few areas which would benefit from this treatment

• ECommerce – loads of crappy functionality here [PayPal API, bank integration], just waiting to be abstracted for the developer. Loads of PHP ecommerce solutions. A few standout packages [Shopify, Goodbarry]; where’s the killer app ?
• Games – I know nothing about games, whether hardcore Quake- style or casual Flash. But whether you’re throwing a ball or ‘fragging a monster, there’s got to be a lot of rendering physics in here that’s abstractable. Why is writing a game so much harder than writing a webapp ?

With respect to the web, Rails is great for what you might call ‘traditional’ sites; anything where all the content comes in from a browser – a blog being the canonical example. But most of the stuff I write tends to rely on a whole load of scrapers going out to the web, fetching data, parsing it and persisting it on a looped basis. How do you implement this in Rails ? Well, there’s no native support. Either you expose certain methods through your Rails controllers and write cron jobs to upload data through them, or you rely on the one of the new cloud-based platforms to implement the feature for you; there certainly seems to be a rush at the moment to implement so-called ‘background processing’ features.

Erlang potentially turns the problem inside out; instead of jamming timer features onto a CRUD webapp framework, take a router- style platform [where multiple processes can exist independently] and have one of those processes setup as a http server, able to communicate with the outside world. But then we come full circle – where’s the Erlang framework that abstracts all the tedious parts of the web stack [routing, templates, persistence etc] ? A Nitrogen / CouchDB stack looks the best bet right now, but you’ll still have to do the work to stitch the two together.

Certainly seems to me there’s room for a new canonical stack for the real time web.

I have an idea for a trading app involving the in-play soccer markets. Now this isn’t my traditional territory – basically I prefer the long term soccer stuff as a) there’s more ’structure’ to the markets [just like fixed income] and b) the pace is slower; prices only move after each game [think chess as opposed to video games; more appropriate at my age]

However in-play is where all the action is, and there’s a huge amount of feed info available. On a Saturday afternoon, Betfair might be showing 10 in-play games at once, each with 4 or more markets; so 40 markets to cover, all changing continuously. How can I grab, parse and persist all that data ?

I started with a simple Python scraper, but the best performance I could get was about 2 seconds per feed [connect to server, download page, parse page, store in database]. Not good enough – with 40 matches to cover, you’re going to get killed reloading each once every 80 [40*2] secs. I could convert to Java to get a performance pickup, but that’s not really the problem here .. I need those feeds to execute in parallel rather than sequentially.

Cue Erlang, and Joe Armstrong’s book.

I did try it six months ago but got bogged down; the whole concurrency-oriented aspect is pretty alien to anyone coming from Ruby or Python. But now I seem to be making better progress; it’s starting to click. For anyone reading the book, I would say:

• Start by figuring out how to compile and run a Hello World program; go to Chapter 6 and use Rake rather than Make [Joe: using Make files is going to scare of 99.9% of web folk]
• Don’t get bogged down in all the language specifics of Chapters 1-5; I’d give Chapters 1-3 a cursory read and move on
• Focus on the concurrency aspect; read and re-read Chapters 7 and 8, and code up the examples
• Section 16:1 ['The Road to the Generic Server'] has some good examples
• The code provided for the book is helpful, but terribly organised! All the different examples are jumbled in together with no kind of packaging, and one Makefile to compile them all at once
• In Chapters 10/11, it’s worth pointing out that the lib_chan module is one of Joe’s own [and is included in the src code], and isn’t part of the standard Erlang distribution
• If you want to compile and run the IRC Lite example [Chapter 11], you need the following files:
  • chat_client.erl
  • chat.conf
  • chat_group.erl
  • chat_server.erl
  • io_widget.erl
  • lib_chan_auth.erl
  • lib_chan_cs.erl
  • lib_chan.erl
  • lib_chan_mm.erl
  • lib_md5.erl
  • mod_chat_controller.erl

Once you get into it, the syntax seems quite familiar. It’s dynamic, so not so far from Ruby and Python. The tail recursion feature is very similar to Python’s filter/map/reduce functionality, or Ruby’s Enumerable module. You can reference functions as first-class objects, so more Python there.

The key example for a beginner IMHO is right at the end of the book on p366; how to take an list-processing action that would normally be processed sequentially, and execute it in parallel. I’ve reproduced it here, with the Ref atom removed [not necessary for demonstration]. If anyone thinks I’m just copying and pasting code from the src into the blog, I’d like to point out that I arrived at this code snippet via an independent process and with a not inconsiderable amount of mental strain!

To compile: erlc -o ebin src/pmap.erl
To run:erl -pa ebin -noshell -s pmap main -s init stop

It’s taken a few days, but I think I’m beginning to get a grip on Erlang’s mojo.

Lots of good comment on AppEngine’s newly- announced support for Java:

• JRuby on Rails on Google AppEngine
• Running Rhino and Helma on Google AppEngine
• Why Google AppEngine shouldn’t include PHP

What’s amazing here is how quickly the JRuby on Rails, Helma etc communities have got round to porting their frameworks to AppEngine; heck, it’s only three days old. I think the ThoughtWorks guys had some kind of early access to the program, but still, you have to admire how quickly it’s been done. I had assumed folk would stick with the default stack provided by Google, just like I do with their Python stack; obviously there’s a lot of pent- up interest out there. [Alternatively, given the paucity of cheap Java hosting alternatives currently available, perhaps I shouldn't be surprised]

I have previously been disparaging about the point of porting Django onto Python AppEngine; however I totally get the importance of porting JRuby on Rails to the new platform. I personally don’t have any interest in the default JSP/Servlet/JDO stack provided by Google; however the JVM provides a mature, stable, fast base on which to support higher level frameworks – JRuby on Rails, Grails, Helma, AppJet, take your pick – maybe if we’re lucky we’ll see some Clojure- or Scala- based stacks emerge.

And here’s the real importance of Java for AppEngine – JVM support opens up a cornucopia of different cloud- based programming models, in a way that Python support doesn’t [I'm still a Python fan BTW]. Now you have the option of coding all your front- end stuff in a nice high level language, then dropping down to Java for all the performance intensive stuff, all in a single application – no more calling out from AppEngine to a separate Java server. A bit like writing a CPython desktop program and then re-writing the slow bits in C – except that Java gives you web portability in a way you can forget about with C.

Reminds me a bit of Microsoft’s CLR – one runtime, many languages supported. Where on earth have Microsoft been in all this ?

Forget Java, It’s all about the JVM.

BTW I keep reading about what a wonderful piece of engineering GWT is. For the record, I just don’t get it; I have no idea why you’d want to generate Javascript from Java, especially now with JQuery being so damn good. Frankly I’d like someone to come up with a Javascript- to- Java compiler – now that really would be worth looking into.

Having ranted about the inadequacies of Django templates, I started to realise I’m pretty much stuck with them for AppEngine development given they are the default option. So … how to get SmartIf and similar to work under AppEngine ?

As I was digging through the webapp.template source code, interesting to find that the AppEngine designers have pretty much the same view of templates as I do –

The main purpose of this module is to hide all of the package import pain you normally have to go through to get Django to work. We expose the Django Template and Context classes from this module, handling the import nonsense on behalf of clients.

Hah! Not alone!

Django requires you to register your extensions with a template ‘registry’. If you look in the SmartIf src, you’ll see the following.

from django import template
register = template.Library()

You need to replace this with an AppEngine registry:

from google.appengine.ext.webapp import template
register=template.create_template_register()

Next, the SmartIf docs say you should include the following declaration at the top of your templates to replace the built-in ‘if’ with the new smart version:

{% load smartif %}

Don’t do this! You will end up in some kind of Django namespace hell. Instead, register the new template with the Appengine template module.

template.register_template_library(path_to_module)

Finally, don’t comment out the line ‘from django import template’; SmartIf uses the template.TemplateSyntaxError class, which exists in the Django template module but not the AppEngine equivalent. So you still need to import the Django template module; just make sure you do it after you’ve registered the extension with the AppEngine template.

Done!

• I’ve been talking to my friends at Smarkets about market making in live soccer games [Match Odds, Correct Score etc]
• I visited a leading bookie’s HQ recently and watched one of their traders managing the book in a live soccer game; he let slip that a lot of the modelling is done using Poisson processes
• I came across this video by the founder of BetAngel software, explaining how in-play soccer prices can often drift in counter- intuitive ways.

All of which generated a minor firestorm in my brain.

With respect to the last point, lets take a typical ‘Correct Score’ soccer market with contracts for each possible outcome – 0-0, 1-0, 0-1, 1-1 etc. When the match starts, the score is 0-0. Let’s say 20 minutes elapse, and no goals have been scored. How would you expect the price for each of these contracts to have moved ?

Intuition says that the price of the 0-0 contract should have increased [a 0-0 draw being more likely], whilst everything else should have decreased.

Not so!

[Kudos to Google Charts for the graph; fantastic utility]

The chart shows the evolution of the prices of four contracts across the 90 minute game, assuming no goals are scored. Not surprisingly, 0-0 [red] increases over the game to 100% by the end of the match. More interestingly, 1-0 [green] actually increases from an initial 17% at the start of the game to approx 30% at around 55 minutes, before decaying away to zero.

Counterintuitive ? I think so. What’s happening here ? Well, there’s two distinct things going on:

• Probability of 0-0 is increasing all the time
• There are a whole range of other probabilities not shown by the graph [2-0, 2-1, 5-0] etc; initially these have small but non-negligible values. However by 55 minutes, if no goal has been scored, their probabilities will have decayed practically to zero

For the first 55 mins, I’d wager that the second effect is declining at a rate greater than the first effect is increasing – so all the other correct scores [1-0, 0-1, 1-1] tend to have positive biases in the early part of the game [given that the sum of the prices of the contracts must add up to 100%].

Interesting, huh ? I’m wondering if this is the start of a possible trading strategy. I haven’t traded the in-play markets before, but the first thing I would want is some kind of model for assessing fair value at any point in time – any deviation from these prices might represent some kind of opportunity. Lots more work to be done here, I’ll blog some more later.

But back to the modelling – how is it done ?

Essentially I modelled the probability of each team scoring a goal as a Poisson process. From Wikipedia:

“The Poisson distribution .. expresses the probability of a number of events occurring in a fixed period of time if these events occur with a known average rate and independently of the time since the last event.”

Sound reasonable for modelling goals – all you need is the expected number of goals a team will score over the course of the game. Once you have this number the Poisson function will give you the probability of a team scoring no goals, 1 goal, 2 goals, n goals etc. You repeat the process for each team, then the probability of a particular score [eg 1-0] is the product of the two probabilities in question (Team A [1 goal] x Team B [0 goals])

To obtain the graphs above, you simply repeat the calculation at regular intervals during the match [say every minute]; the interesting question is then how to scale the ‘expected number of goals’ parameter for time. Unfortunately I can’t find the link, but I came across a site which suggested the correct way to do this was linearly with respect to time – ie if the expected number of goals over 90 mins is 1.5, it’s 0.75 over 45 mins. Again, sounds reasonable; I say ‘interesting’ as this contrasts with dealing with normal distributions / Brownian motion in finance, where typically you scale with respect to the root of time.

I guess I don’t have enough experience with Poisson distributions at this stage to understand why at this stage [or have forgotten more A level maths than I can remember]. Looks promising, but I’d like to understand exactly why the Poisson process occurs, and why it might be a good candidate for modelling goals.

Back to Wikipedia.