Clear Lines Blog

Hacking together @wbfacts, a World Bank Twitter Bot

mathias — Tue, 22 Dec 2015 14:43:05 -1300

This is my modest contribution to the F# Advent Calendar 2015. Thanks to @sergey_tihon for organizing it! Check out the epic stuff others have produced so far on his website or under the #fsAdvent hashtag on Twitter. Also, don’t miss the Japan Edition of #fsAdvent for more epicness…

Sometime last year, in a moment of beer-fueled inspiration, I ended up putting together @fsibot, the ultimate mobile F# IDE for the nomad developer with a taste for functional-first programming. This was fun, some people created awesome things with it, other people, not so much, and I learnt a ton.

People also had feature requests (of course they did), some obviously crucial (Quines! We need quines!), some less so. Among others came the suggestion to support querying the World Bank for data, and returning results as a chart.

So... Let's do it! After a bit of thought, I decided I would not extend @fsibot to support this, but rather build a separate bot, with its own external DSL. My thinking here was that adding this as a feature to @fsibot would clutter the code; also, this is a specialized task, and it might make sense to create a dedicated language for it, to make it accessible to the broader public who might not be familiar with F# and its syntax.

You can find the code for this thing here.

The World Bank Type Provider

Let's start with the easy part - accessing the World Bank data and turning it into a chart. So what I want to do is something along the lines of 'give me the total population for France between 2000 and 2005', and make a nice columns chart out of this. The first step is trivial using the World Bank type provider, which can be found in the FSharp.Data library:

open FSharp.Data

let wb = WorldBankData.GetDataContext ()
let france = wb.Countries.France
let population = france.Indicators.``Population, total``
let series = [ for year in 2000 .. 2005 -> year, population.[year]]

Creating a chart isn't much harder, using FSharp.Charting:

open FSharp.Charting

let title = sprintf "%s, %s" (france.Name) (population.Name)
let filename = __SOURCE_DIRECTORY__ + "/chart.png"

Chart.Line(series, Title=title)
|> Chart.Save(filename)

Wrapping up calls to the Type Provider

Next, we need to take in whatever string the user will send us over Twitter, and convert it into something we can execute. Specifically, what we want is to take user input along the lines of "France, Total population, 2000-2005", and feed that information into the WorldBank type provider.

Suppose for a moment that we had broken down our message into its 4 pieces, a country name, an indicator name, and two years. We could then call the WorldBank type provider, along these lines:

type WB = WorldBankData.ServiceTypes
type Country = WB.Country
type Indicator = Runtime.WorldBank.Indicator

let findCountry (name:string) =
    wb.Countries 
    |> Seq.tryFind (fun c -> c.Name = name)

let findIndicator (name:string) (c:Country) =
    c.Indicators 
    |> Seq.tryFind (fun i -> i.Name = name)

let getValues (year1,year2) (indicator:Indicator) =
    [ for year in year1 .. year2 -> year, indicator.[year]]

We can then easily wrap this into a single function, like this:

let getSeries (country,indicator,year1,year2) =
    findCountry country
    |> Option.bind (findIndicator indicator)
    |> Option.map (getValues (year1,year2))

Defining our language

This is a bit limiting, however. Imagine that we wanted to also support queries like "France, Germany, Italy, Total population, total GDP, 2000". We could of course pass in everything as lists, say,

["France";"Germany"], ["Total population"], [2000],

… but we'd have to then examine how many elements the list contains to make a decision. Also, more annoyingly, this allows for cases that should not be possible: ideally, we wouldn't want to even allow requests such as

[], [], [2000; 2010; 2020].

One simple solution is to carve out our own language, using F# Discriminated Unions. Instead of lists, we could, for instance, create a handful of types to represent valid arguments:

type PLACE =
    | COUNTRY of string
    | COUNTRIES of string list

type MEASURE =
    | INDICATOR of string

type TIMEFRAME = 
    | OVER of int * int
    | IN of int

This is much nicer: we can now clean up our API using pattern matching, eliminating a whole class of problems:

let cleanAPI (place:PLACE) (values:MEASURE) (timeframe:TIMEFRAME) =
    match (place, values, timeframe) with
    | COUNTRY(country), INDICATOR(indicator), OVER(year1,year2) ->             
        // do stuff
    | COUNTRIES(countries), INDICATOR(indicator), OVER(year1,year2) -> 
        // do different stuff
    | // etc...

Parsing user input

The only problem we are left with now is to break a raw string - the user request - into a tuple of arguments. If we have that, then we can compose all the pieces together, piping them into a function that will take a string and go all the way down to the type provider.

We are faced with a decision now: we can go the hard way, powering our way through this using Regex and string manipulation, or the easy way, using a parser like FParsec. Let's be lazy and smart!

Note to self: when using FParsec from a script file, make sure you #r FParsecCS before FParsec. I spent a couple of hours stuck trying to understand what I was doing wrong because of that one.

Simply put, FParsec is awesome. It allows you to define small functions to parse input strings, test them on small pieces of input, and compose them together into bigger and badder parsers. Let's illustrate: suppose that in our DSL, we expect user requests to contain a piece that looks like "IN 2010", or "OVER 2000 - 2010" to define the timeframe.

In the first case, we want to recognize the string “IN”, followed by spaces, followed by an integer; if we find that pattern, we want to retrieve the integer and create an instance of IN:

let pYear = spaces >>. pint32 .>> spaces
let pIn =
    pstring "IN" >>. pYear
    |>> IN

If we run the parser on a well-formed string, we get what we expect:

run pIn "IN  2000 "
> 
val it : ParserResult<TIMEFRAME,unit> = Success: IN 2000

If we pass in an incorrectly formed string, we get a nice error diagnosis:

run pIn "IN some year "
> 
val it : ParserResult<TIMEFRAME,unit> =
  Failure:
Error in Ln: 1 Col: 4
IN some year 
   ^
Expecting: integer number (32-bit, signed)

Beautiful! The second case is rather straightforward, too:

let pYears = 
    tuple2 pYear (pstring "-" >>. pYear)
     
let pOver = 
    pstring "OVER" >>. pYears
    |>> OVER

Passing in a well-formed string gives us back OVER(2000,2010):

run pOver "OVER 2000- 2010"
> 
val it : ParserResult<TIMEFRAME,unit> = Success: OVER (2000,2010)

Finally we can compose these together, so that when we encounter either IN 2000, or OVER 2000 - 2005, we parse this into a TIMEFRAME:

let pTimeframe = pOver <|> pIn

I won't go into the construction of the full parser - you can just take a look here. The trickiest part was my own doing. I wanted to allow messages without quotes, that is,

COUNTRY France

and not

COUNTRY "France"

The second case is much easier to parse (look for any chars between ""), especially because there are indicators like, for instance, "Population, total". The parser is pretty hacky, but hey, it mostly works, so... ship it!

Ship it!

That's pretty much it. At that point, all the pieces are there. I ended up ~~copy pasting~~ taking inspiration from the existing @fsibot code, using LinqToTwitter to deal with reading and writing to Twitter, and TopShelf to host the bot as a Windows service, hosted on an Azure VM, and voila! You can now tweet to @wbfacts, and get back a nice artisanal chart, hand-crafted just for you, with the freshest data from the World Bank:

@brandewinder "France, Population, total" pic.twitter.com/8Bx4cfYNia
— World Bank Facts (@wbfacts) December 23, 2015

@brandewinder "In 2005, Population, total in France was 63179356.000"
— World Bank Facts (@wbfacts) December 23, 2015

A couple of quick final comments:

One of the most obvious issues with the bot is that Twitter offers very minimal support for IntelliSense (and by minimal, I mean 'none'). This is a problem, because we lose discoverability, a key benefit of type providers. To compensate for that, I added a super-crude string matching strategy, which will give a bit of flexibility around misspelled country or indicator names. This is actually a fun problem - I was a bit pressed by time, but I'll probably revisit it later.
In the same vein, it would be nice to add a feature like "find me an indicator with a name like GDP total". That should be reasonably easy to do, by extending the language to support instructions like HELP and / or INFO.
The bot seems like a perfect case for some Railway-Oriented Programming. Currently the wiring is pretty messy; for instance, our parsing step returns an option, and drops parsing error messages from FParsec. That message would be much more helpful to the user than our current message that only states that “parsing failed". With ROP, we should be able to compose a clean pipeline of functions, along the lines of parseArguments >> runArguments >> composeResponse.
The performance of looking up indicators by name is pretty terrible, at least on the first call on a country. You have been warned :)
That's right, there is no documentation. Not a single test, either. Tests show a disturbing lack of confidence in your coding skills. Also, I had to ship by December 22nd :)

That being said, in spite of its many, many warts, I am kind of proud of @wbfacts! It is ugly as hell, the code is full of duct-tape, the parser is wanky, and you should definitely not take this as ‘best practices’. I am also not quite clear on how the Twitter rate limits work, so I would not be entirely surprised if things went wrong in the near future… In spite of all this, hey, it kind of runs! Hopefully you find the code or what it does fun, and perhaps it will even give you some ideas for your own projects. In the meanwhile, I wish you all happy holidays!

You can find the code for this thing here.

I also wanted to say thanks to Tomas Petricek, for opening my eyes to discriminated unions as a modeling tool, and Phil Trelford for introducing me to FParsec, which is truly a thing of beauty. They can be blamed to an extent for inspiring this ill-conceived project, but whatever code monstrosity is in the repository is entirely my doing :)

And… ping me on Twitter as @brandewinder if you have questions or comments!

Wonderland Katas, F# style

mathias — Sun, 08 Nov 2015 13:06:14 -1300

A couple of days ago, I stumbled across the Wonderland Clojure Katas, by @gigasquid. It's a wonderful project, with 7 independent coding exercises, inspired by Lewis Carrol's "Alice in Wonderland". I love that type of stuff, and saw that @byronsamaripa had already made a Scala port, so I figured, why not port it to F#?

As it happens, I had to travel to Seattle this week; this gave me enough idle airplane time to put together a first version here. I also had a chance to chat with @tomaspetricek and @reedcopsey, which always helps - thanks for the great input, guys :)

I am sure improvements can be made, but it's good enough to ship, so... let's ship it. I have only solved a couple of Katas myself so far, and focused mainly on getting the infrastructure in place. I tried to stay true to the spirit of the original project, but at the same time, F# and Clojure are different, so I also made some changes, and figured it might be interesting to discuss them here. I'd love to hear feedback, so try it out, and let me know what you think, and how to make it better!

Overall structure

The Clojure version is organized in separate projects, one per Kata, each with source code and a separate test suite. This is perfectly reasonable, and I considered the same organization, but in the end, opted for something a bit different. When exploring some code in F#, I tend to work primarily in the scripting environment, so I decided to collapse the code and tests in one single script file for each Kata. This is a TDD-inspired pattern I often follow: I simply write my assertion in the script itself, without any testing framework, and get to work. As an example, for the alphabet cipher, I would start with something like this:

let encode key message = "encodeme"
encode "scones" "meetmebythetree" = "egsgqwtahuiljgs"

... and then proceed from there, implementing until it works, that is, until the assertion evaluates to true when I run the script.

Given that most of the Katas come with a test suite pre-implemented, sticking to simple assertions like this would have been a bit impractical. Rather than implement my own crude testing function, I decided to use Unquote, and included a test suite in each script, using the following pattern:

#r @"../packages/Unquote/lib/net45/Unquote.dll"
open Swensen.Unquote 

let tests () = 

    // verify encoding
    test <@ encode "vigilance" "meetmeontuesdayeveningatseven" = "hmkbxebpxpmyllyrxiiqtoltfgzzv" @>
    test <@ encode "scones" "meetmebythetree" = "egsgqwtahuiljgs" @> 

// run the tests
tests ()

That way, the only thing you need to do is change the code that sits on the top section of the script, select all, and execute. tests () will run the tests, producing outputs like:

Test failed: 

encode "vigilance" "meetmeontuesdayeveningatseven" = "hmkbxebpxpmyllyrxiiqtoltfgzzv"
"encodeme" = "hmkbxebpxpmyllyrxiiqtoltfgzzv"
false 

Test failed: 

encode "scones" "meetmebythetree" = "egsgqwtahuiljgs"
"encodeme" = "egsgqwtahuiljgs"
false

The upside is, the whole code is in one place, and Unquote produces a nice analysis of what needs to be fixed. The downside is, you have to run the tests manually, without any pretty test runner, and I had to take a dependency, managed with Paket. I think it's worth it, especially because I am considering changing some of the tests to use property-based testing with FsCheck, but if you have opinions on making this simpler or better, I'd love to hear it.

Types

The other main difference with the Clojure original revolves around types. In some cases, this was necessary, just to "make it work". As an example, the card game war Kata uses a card deck, which in Clojure is defined in a couple of lines:

(def suits [:spade :club :diamond :heart])
(def ranks [2 3 4 5 6 7 8 9 10 :jack :queen :king :ace])

The F# side requires slightly heavier artillery, because I can't just mix-and-match integers and "heads":

type Suit =
    | Spade
    | Club
    | Diamond
    | Heart 

type Rank =
    | Value of int
    | Jack
    | Queen
    | King
    | Ace 

type Card = Suit * Rank

In this particular case, the lightness of Clojure is clearly appealing. In other cases, though, I deliberately changed the model, to get some benefits out of types. The best example is the fox, goose, bag of corn Kata. The Clojure version represents the world like this:

(def start-pos [[[:fox :goose :corn :you] [:boat] []]])

We have 3 vectors, representing who is currently on the left bank of the river, the boat, and the right bank of the river. This works, and I had an initial F# version that was essentially the same, using 3 sets to represent the 3 locations. However, this required writing a few annoying tests to validate whether states where possible. I am lazy, and thought this would be a good place to use types, so I took the liberty to modify the domain this way:

type Location =
    | LeftBank
    | RightBank
    | Boat 

type Positions = {
    Fox:    Location
    Goose:  Location
    Corn:   Location
    You:    Location }

This is a bit heavier than the Clojure version, but quite convenient. First, I am guaranteed that my goose can be in one and only one place at a time. Then, positions are fairly easy to decipher. Finally, checking that the Goose is safe, for instance, simply becomes

let gooseIsSafe positions =
    (positions.Goose <> positions.Fox)
    || (positions.Goose = positions.You)

Long story short: I really enjoyed the exercise of taking the Clojure representation, and rewriting it as I would with my F# hat on. In some cases, the 2 versions are virtually identical. The alphabet cipher, or wonderland number, for instance, differ only because of the added type annotations. They could be removed, but I thought they made the intent more obvious:

In other cases, F# types introduced a bit of verbosity, sometimes with clear benefits, sometimes less obviously so.

Tests

In a totally different direction, going through the unit tests was a fun exercise. Tests tend to bring out the inner, closet mathematician in me, with questions such as ‘does a solution exist’, and ‘is the solution unique’? This was no exception, and I caught myself repeatedly asking these questions.

Let's start with a simple one: is there a wonderland number at all? And might there be more than one? Of course, this is rather silly. In general, I think it's safe to assume that the Kata has not been created to trick me. Checking that there is at least a solution is rather quick, and scanning all possible 6-digit numbers isn't too bad either. However... if I were to generalize this, and search for, say, a wonderland with 50 digits, what should the signature be? Should it be an option, or a (possibly empty) list of integers, assuming I could have more than one?

Perhaps more interesting: in the doublets case, how do I know that doublets ("head", "tail") = ["head"; "heal"; "teal"; "tell"; "tall"; "tail"] IS the right solution? And what if I had multiple possible doublets? Should I prefer a shorter doublet to a longer one? If we swapped the words source to a larger dictionary, for instance, we could well end up with a different, shorter solution, and our test would break. A possible approach around that issue would be to use property-based testing, checking for an invariant along the lines of:

"if doublets returns a non-empty solution, each pair should differ by exactly one character"

However, a trivial implementation then would be "always return an empty list". Don't even try to return doublets - do nothing, and you will never be wrong! It's a very efficient implementation, but it's clearly not very satisfying. I am actually not entirely sure how one should go about writing a good test suite, to cover the case of an arbitrary source of words. Perhaps generate words such that there is a unique shortest doublet, and words with no doublets?

Parting words

First, big thanks to @gigasquid for creating the original Clojure project; it's an awesome idea, and I had a great time digging into it. Reading through the Clojure code was quite interesting, and rekindled my interest in learning a LISP-family language. In 2016, I will learn Racket!

Then, big thanks again to @tomaspetricek and @reedcopsey for discussing the code with me, it was both helpful and fun! And I hear this may or may not have inspired Tomas to try something awesome, looking forward to what might come out of it...

Again, this is work in progress; I still haven't solved the Katas, and might change a couple of things here and there as I do so. @isaac_abraham suggested to provide some indication as to which Katas might be easier than others, I'll add that as soon as I go through them. If you have suggestions or comments, about the code, the setup, or anything that might help make this better or more accessible, feel free to ping me on Twitter, or to simply send a pull request or issue on Github. Until then, hope you have fun with it!

Language Safety Score, revisited

mathias — Sat, 08 Aug 2015 12:42:20 -1300

A couple of weeks ago, I came across this blog post by Steve Shogren, which looks at various programming languages, and attempts to define a “language safety score”, by taking into account a list of language criteria (Are nulls allowed? Can variables be mutated? And so on), aggregating them into an overall safety score – and finally looking for whether the resulting score was a reasonable predictor for the observed bug rate across various projects.

I thought this was an interesting idea. However, I also had reservations on the methodology. Picking a somewhat arbitrary list of criteria, giving them indiscriminately the same weight, and summing them up, didn’t seem to me like the most effective approach – especially given that Steve had already collected a nice dataset. If the goal is to identify which language features best predict how buggy the code will be, why not start from there, and build a model which attempts to predict the bug rate based on language features?

So I decided to give it a shot, and build a quick-and-dirty logistic regression model. In a nutshell, logistic regression attempts to model the probability of observing an event, based on a set of criteria / features. A prototypical application would be in medicine, trying to predict, for instance, the chances of developing a disease, given patient characteristics. In our case, the disease is a bug, and the patient a code base. We’ll use the criteria listed by Steve as potential predictors, and, as a nice side-product of logistic regression, we will get a quantification of how important each of the criteria is in predicting the bug rate.

I’ll discuss later some potential issues with the approach; for now, let’s build a model, and see where that leads us. I lifted the data from Steve’s post (hopefully without typos), with one minor modification: instead of scoring criteria as 1, 0 or –1, I just retained 1 or 0 (it’s there or it’s not there), and prepared an F# script, using the Accord framework to run my logistic regression.

Note: the entire script is here as a Gist.

#I @"../packages"
#r @"Accord.3.0.1-alpha\lib\net45\Accord.dll"
#r @"Accord.MachineLearning.3.0.1-alpha\lib\net45\Accord.MachineLearning.dll"
#r @"Accord.Math.3.0.1-alpha\lib\net45\Accord.Math.dll"
#r @"Accord.Statistics.3.0.1-alpha\lib\net45\Accord.Statistics.dll"

let language, bugrate, criteria = 
    [|  "F#",           0.023486288,    [|1.;1.;1.;0.;1.;1.;1.;0.;0.;0.;1.;1.;1.;0.|]
        "Haskell",      0.015551204,    [|1.;1.;1.;0.;1.;1.;1.;1.;1.;0.;1.;1.;0.;1.|]
        "Javascript",   0.039445132,    [|0.;0.;0.;0.;0.;0.;0.;0.;0.;0.;1.;0.;1.;0.|] 
        "CoffeeScript", 0.047242288,    [|0.;0.;0.;0.;0.;0.;0.;0.;0.;0.;1.;0.;1.;0.|] 
        "Clojure",      0.011503478,    [|0.;1.;0.;0.;0.;0.;1.;0.;1.;1.;1.;0.;0.;0.|] 
        "C#",           0.03261284,     [|0.;0.;1.;0.;0.;1.;1.;0.;0.;0.;1.;0.;1.;0.|] 
        "Python",       0.02531419,     [|0.;0.;0.;0.;0.;0.;0.;0.;0.;0.;1.;0.;1.;0.|] 
        "Java",         0.032567736,    [|0.;0.;0.;0.;0.;0.;0.;0.;0.;0.;1.;0.;1.;0.|] 
        "Ruby",         0.020303702,    [|0.;0.;0.;0.;0.;0.;0.;0.;0.;0.;1.;0.;1.;0.|] 
        "Scala",        0.01904762,     [|1.;1.;1.;0.;1.;1.;1.;0.;0.;0.;1.;0.;0.;0.|] 
        "Go",           0.024698375,    [|0.;0.;1.;0.;0.;1.;1.;0.;0.;0.;1.;0.;1.;0.|] 
        "PHP",          0.031669293,    [|0.;0.;0.;0.;0.;0.;0.;0.;0.;0.;1.;0.;1.;0.|] |]
    |> Array.unzip3

open Accord.Statistics.Models.Regression
open Accord.Statistics.Models.Regression.Fitting 

let features = 14
let model = LogisticRegression(features)
let learner = LogisticGradientDescent(model)

let rec learn () = 
    let delta = learner.Run(criteria, bugrate)
    if delta > 0.0001
    then learn ()
    else ignore ()

learn () |> ignore

And we are done – we have trained a model to predict the bug rate, based on our 14 criteria. How is this working? Let’s find out:

for i in 0 .. (language.Length - 1) do    
    let lang = language.[i]
    let predicted = model.Compute(criteria.[i])
    let real = bugrate.[i]
    printfn "%16s Real: %.3f Pred: %.3f" lang real predicted

> 
              F# Real: 0.023 Pred: 0.023
         Haskell Real: 0.016 Pred: 0.016
      Javascript Real: 0.039 Pred: 0.033
    CoffeeScript Real: 0.047 Pred: 0.033
         Clojure Real: 0.012 Pred: 0.011
              C# Real: 0.033 Pred: 0.029
          Python Real: 0.025 Pred: 0.033
            Java Real: 0.033 Pred: 0.033
            Ruby Real: 0.020 Pred: 0.033
           Scala Real: 0.019 Pred: 0.020
              Go Real: 0.025 Pred: 0.029
             PHP Real: 0.032 Pred: 0.033

Looks pretty good. Let’s confirm that with a chart, using FSharp.Charting:

#load "FSharp.Charting.0.90.12\FSharp.Charting.fsx"
open FSharp.Charting

let last = language.Length - 1

Chart.Combine [
    Chart.Line ([ for i in 0 .. last -> bugrate.[i]], "Real", Labels=language)
    Chart.Line ([ for i in 0 .. last -> model.Compute(criteria.[i])], "Pred") ] 
|> Chart.WithLegend()

What criteria did our model identify as predictors for bugs? Let’s find out.

let criteriaNames = [|
    "Null Variable Usage"
    "Null List Iteration"
    "Prevent Variable Reuse"
    "Ensure List Element Exists"
    "Safe Type Casting"
    "Passing Wrong Type"
    "Misspelled Method"
    "Missing Enum Value"
    "Variable Mutation"
    "Prevent Deadlocks"
    "Memory Deallocation"
    "Tail Call Optimization"
    "Guaranteed Code Evaluation"
    "Functional Purity" |]    
        
for i in 0 .. (features - 1) do 
    let name = criteriaNames.[i]
    let wald = model.GetWaldTest(i)
    let odds = model.GetOddsRatio(i)
    (printfn "%28s odds: %4.2f significant: %b" name odds wald.Significant)

> 
         Null Variable Usage odds:  0.22 significant: true
         Null List Iteration odds:  0.86 significant: true
      Prevent Variable Reuse odds:  0.64 significant: true
  Ensure List Element Exists odds:  1.05 significant: true
           Safe Type Casting odds:  1.00 significant: false
          Passing Wrong Type odds:  0.86 significant: true
           Misspelled Method odds:  1.05 significant: true
          Missing Enum Value odds:  0.78 significant: true
           Variable Mutation odds:  0.86 significant: true
           Prevent Deadlocks odds:  0.64 significant: true
         Memory Deallocation odds:  0.74 significant: true
      Tail Call Optimization odds:  0.22 significant: true
  Guaranteed Code Evaluation odds:  1.71 significant: true
           Functional Purity odds:  0.69 significant: true

How should you read this? The first output, the odds ratio, describes how much more likely it is to observe success than failure when that criterion is active. In our case, success means “having a bug”, so for instance, if your language prevents using nulls, you’d expect 1.0 / 0.22 = 4.5 times less chances to write bugs. In other words, if the odds are close to 1.0, the criterion doesn’t make much of a difference. The closer to zero it is, the lower the predicted bug count, and vice-versa.

Conclusions and caveats

The 3 most significant predictors of a low bug rate are, in order, no nulls, tail calls optimization, and (to a much lesser degree) lazy evaluation. After that, we have honorable scores for avoiding variable reuse, preventing deadlocks, and functional purity.

So… what’s the bottom line? First off, just based on the bug rates alone, it seems that using functional languages would be a safer bet than Javascript (and CoffeeScript) to avoid bugs.

Then, now would be a good time to reiterate that this is a quick-and-dirty analysis. Specifically, there are some clear issues with the dataset. First, we are fitting 12 languages on 14 criteria – that’s not much to go on. On top of that, there is some data redundancy. None of the languages in our sample has “ensure list element exists” (4th column is filled with zeroes), and all of them guarantee memory de-allocation (11th column filled with ones). I suspect there is some additional redundancy, because of the similarity between the columns.

Note: another interesting discussion would be whether the selected criteria properly cover the differences between languages. I chose to not go into that, and focus strictly on using the data as-is.

I ran the model again, dropping the 2 columns that contain no information; while this doesn’t change the predictions of the model, it does impact a bit the weight of each criterion. The results, while similar, do show some differences:

("Null Variable Usage", 0.0743885639)
("Functional Purity", 0.4565632287)
("Prevent Variable Reuse", 0.5367456237)
("Prevent Deadlocks", 0.5374379877)
("Tail Call Optimization", 0.7028982809)
("Missing Enum Value", 0.7539575884)
("Null List Iteration", 0.7636177784)
("Passing Wrong Type", 0.7636177784)
("Variable Mutation", 0.7646027916)
("Safe Type Casting", 1.072641105)
("Misspelled Method", 1.072641105)
("Guaranteed Code Evaluation", 2.518831684)

Another piece of information I didn’t use is how many commits were taken into consideration. This matters, because the information gathered for PHP is across 10 times more commits than F#, for instance. It wouldn’t be very hard to do – instead of regressing against the bug rate, we could count the clean and buggy commits per language, and proceed along the lines of the last example described here.

In spite of these issues, I think this constitutes a better base to construct a language score index. Rather than picking criteria by hand and giving them arbitrary weights, let the data speak. Measure how well each of them explains defects, and use that as a basis to determine their relative importance.

That’s it for today! Big thanks to Steve Shogren for a stimulating post, and for making the data available. And again, you can find the script here as a Gist. If you have comments or questions, ping me on Twitter!

F# as a Ubiquitous Language

mathias — Tue, 12 May 2015 13:50:00 -1300

As much as we people who write code like to talk about code, the biggest challenge in a software project is not code. A project rarely fails because of technology – it usually fails because of miscommunications: the code that is delivered solves a problem (sometimes), but not the right one. One of the reasons we often deliver the wrong solution is that coding involves translating the world of the original problem into a different language. Translating one way is hard enough as it is, but then, rarely are users comfortable with reading and interpreting code – and as a result, confirming whether the code “does the right thing” is hard, and errors go un-noticed.

This is why the idea of Ubiquitous Language, coined by Eric Evans in his Domain Driven Design book, always appealed to me. The further apart the languages of the domain expert and the code are, the more likely it is that something will be lost in translation.

However, achieving this perfect situation, with “a language structured around the domain model and used by all team members to connect all the activities of the team with the software” [source], is hard. I have tried this in the past, mainly through tests. My idea at the time was that tests, especially BDD style, could perhaps provide domain experts with scenarios similar enough to their worldview that they could serve as a basis for an active dialogue. The experience wasn’t particularly successful: it helped some, but in the end, I never got to the point where tests would become a shared, common ground (which doesn’t mean it’s not possible – I just didn’t manage to do it).

Fast forward a bit to today – I just completed a project, and it’s the closest I have ever been to seeing Ubiquitous Language in action. It was one of the most satisfying experiences I had, and F# had a lot to do with why it worked.

The project involved some pretty complex modeling, and only two people – me and the client. The client is definitely a domain expert, and on the very high end of the “computer power user” spectrum: he is very comfortable with SQL, doesn’t write software applications, but has a license to Visual Studio and is not afraid of code.

The fact that F# worked well for me isn’t a surprise – I am the developer in that equation, and I love it, for all the usual technical reasons. It just makes my life writing code easier. The part that was interesting here is that F# worked well for the client, too, and became our basis for communication.

What ended up happening was the following: I created a GitHub private repository, and started coding in a script file, fleshing out a domain model with small, runnable pieces of code illustrating what it was doing. We would have regular Skype meetings, with a screen share so that I could walk him through the code in Visual Studio, and explain the changes I made - and we would discuss. Soon after, he started to run the code himself, and even making small changes here and there, not necessarily the most complicated bits, but more domain-specific parts, such as adjusting parameters and seeing how the results would differ. And soon, I began receiving emails containing specific scenarios he had experimented with, using actual production data, and pointing at possible flaws in my approach, or questions that required clarifications.

So how did F# make a difference? I think it’s a combination of at least 2 things: succinctness, and static typing + scripts. Succinctness, because you can define a domain with very little code, without loosing expressiveness. As a result, the core entities of the domain end up taking a couple of lines at the top of a single file, and it’s easy to get a full picture, without having to navigate around between files and folders, and keep information in your head. As an illustration, here is a snippet of code from the project:

type Window = { Early:DateTime; Target:DateTime; Late:DateTime }

type Trip = { 
    ID:TripID
    Origin:Location
    Destination:Location
    Pickup:Window
    Dropoff:Window
    Dwell:TimeSpan }

type Action = 
    | Pickup of Trip 
    | Dropoff of Trip
    | CompleteRoute of Location

This is concise, and pretty straightforward – no functional programming guru credentials needed. This is readable code, which we can talk about without getting bogged down in extraneous details.

The second ingredient is static typing + scripts. What this creates is a safe environment for experimentation. You can just change a couple of lines here and there, run the code, and see what happens. And when you break something, the compiler immediately barks at you – just undo or fix it. Give someone a running script, and they can start playing with it, and exploring ideas.

In over 10 years writing code professionally, I never had such a collaborative, fruitful, and productive interaction cycle with a client. Never. This was the best of both worlds – I could focus on the code and the algorithms, and he could immediately use it, try it out, and send me invaluable feedback, based on his domain knowledge. No noise, no UML diagrams, no slides, no ceremony – just write code, and directly communicate around it, making sure nothing was amiss. Which triggered this happy tweet a few weeks back:

Being able to just show the code to a client and have him immediately catch domain modelling errors: priceless. F# is awesome. #fsharp
— Mathias Brandewinder (@brandewinder) February 25, 2015

We were looking at the code together, and my client spotted a domain modeling mistake, right there. This is priceless.

As a side-note, another thing that is priceless is “F# for Fun and Profit”. Scott Wlaschin has been doing an incredible work with this website. It’s literally a gold mine, and I picked up a lot of ideas there. If you haven’t visited it yet, you probably should.

Taking a peek at F# on StackOverflow

mathias — Sun, 03 May 2015 16:34:00 -1300

I got curious the other day about how to measure the F# community growth, and thought it could be interesting to take a look at this through StackOverflow. As it turns out, it’s not too hard to get some data, because StackExchange exposes a nice API, which allows you to make all sorts of queries and get a JSON response back.

As a starting point, I figured I would just try to get the number of questions asked per month. The API allows you to retrieve questions on any site, by tag, between arbitrary dates. Responses are paged: you can get up to 100 items per page, and keep asking for next pages until there is nothing left to receive. That sounds like a perfect job for the FSharp.Data JSON Type Provider.

First things first, we create a type, Questions, by pointing the JSON Type Provider to a url that returns questions; based on the structure of the JSON document it receives, the Type Provider creates a type, which we will then be able to use to make queries:

#I"../packages"
#r @"FSharp.Data.2.2.0\lib\net40\FSharp.Data.dll"
open FSharp.Data
open System

[<Literal>]
let sampleUrl = "https://api.stackexchange.com/2.2/questions?site=stackoverflow"
type Questions = JsonProvider<sampleUrl>

Next, we’ll need to grab all the questions tagged F# between 2 given dates. As an example, the following would return the second page (questions 101 to 200) from all F# questions asked between January 1, 2014 and January 31, 2015:

https://api.stackexchange.com/2.2/questions?page=2&pagesize=100&fromdate=1420070400&todate=1422662400&tagged=F%23&site=stackoverflow

There are a couple of quirks here. First, the dates are in UNIX standard, that is, the number of seconds elapsed from January 1, 1970. Then, we need to keep pulling pages, until the response indicates that there are no more questions to receive, which is indicated by the HasMore property. That’s not too hard: let’s create a couple of functions, first to convert a .NET date to a UNIX date, and then to build up a proper query, appending the page and dates we are interested in to our base query – and finally, let’s build a request that recursively calls the API and appends results, until there is nothing left:

let fsharpQuery = "https://api.stackexchange.com/2.2/questions?site=stackoverflow&tagged=F%23&pagesize=100"

let unixEpoch = DateTime(1970,1,1)
let unixTime (date:DateTime) = 
    (date - unixEpoch).TotalSeconds |> int64

let page (page:int) (query:string) = 
    sprintf "%s&page=%i" query page
let between (from:DateTime) (``to``:DateTime) (query:string) = 
    sprintf "%s&&fromdate=%i&todate=%i" query (unixTime from) (unixTime ``to``)

let questionsBetween (from:DateTime) (``to``:DateTime) =
    let baseQuery = fsharpQuery |> between from ``to``
    let rec pull results p = 
        let nextPage = Questions.Load (baseQuery |> page p)
        let results = results |> Array.append nextPage.Items
        if (nextPage.HasMore)
        then pull results (p+1)
        else results
    pull Array.empty 1

And we are pretty much done. At that point, we can for instance ask for all the questions asked in January 2015, and check what percentage were answered:

let january2015 = questionsBetween (DateTime(2015,1,1)) (DateTime(2015,1,31))

january2015 
|> Seq.averageBy (fun x -> if x.IsAnswered then 1. else 0.)
|> printfn "Average answer rate: %.3f"

… which produces a fairly solid 78%.

If you play a bit more with this, and perhaps try to pull down more data, you might experience (as I did) the Big StackExchange BanHammer. As it turns out, the API has usage limits (which is totally fair). In particular, if you ask for too much data, too fast, you will get banned from making requests, for a dozen hours or so.

This is not pleasant. However, in their great kindness, the API designers have provided a way to avoid it. When you are making too many requests, the response you receive will include a field named “backoff”, which indicates for how many seconds you should back off until you make your next call.

This got me stumped for a bit, because that field doesn’t show up by default on the response – only when you are hitting the limit. As a result, I wasn’t sure how to pass that information to the JSON Type Provider, until Max Malook helped me out (thanks so much, Max!). The trick here is to supply not one sample response to the type provider, but a list of samples, in that case, one without the backoff field, and one with it.

I carved out an artisanal, hand-crafted sample for the occasion, along these lines:

[<Literal>]
let sample = """
[{"items":[
   {"tags":["f#","units-of-measurement"],//SNIPPED FOR BREVITY}],
   "has_more":false,
   "quota_max":300,
   "quota_remaining":294},
 {"items":[
   {"tags":["f#","units-of-measurement"],//SNIPPED FOR BREVITY}],
   "has_more":false,
   "quota_max":300,
   "quota_remaining":294,
   "backoff":10}]"""

type Questions = JsonProvider<sample,SampleIsList=true>

… and everything is back in order – we can now modify the recursive request, causing it to sleep for a bit when it encounters a backoff. Not the cleanest solution ever, but hey, I just want to get data here:

let questionsBetween (from:DateTime) (``to``:DateTime) =
    let baseQuery = fsharpQuery |> between from ``to``
    let rec pull results p = 
        let nextPage = Questions.Load (baseQuery |> page p)
        let results = results |> Array.append nextPage.Items
        if (nextPage.HasMore)
        then
            match nextPage.Backoff with
            | Some(seconds) -> System.Threading.Thread.Sleep (1000*seconds + 1000)
            | None -> ignore ()
            pull results (p+1)
        else results
    pull Array.empty 1

So what were the results? I decided, quite arbitrarily, to count questions month by month since January 2010. Here is how the results looks like:

Clearly, the trend is up – it doesn’t take an advanced degree in statistics to see that. It’s interesting also to see the slump around 2012-2013; I can see a similar pattern in the Meetup registration numbers in San Francisco. My sense is that after a spike in interest in 2010, when F# launched with Visual Studio, there hasn’t been much marketing push for the language, and interest eroded a bit, until serious community-driven efforts took place. However, I don’t really have data to back that up – this is speculation.

How this correlates to overall F# adoption is another question: while I think this curves indicates growth, the number of questions on StackOverflow is clearly a very indirect measurement of how many people actually use it, and StackOverflow itself is a distorted sample of the overall population. Would be interesting to take a similar look at GitHub, perhaps…

Catch of the month, April 2015

mathias — Fri, 01 May 2015 16:14:00 -1300

About a month ago, I vaguely recall a discussion on Twitter – if memory serves me, @rickasaurus was involved – around sharing articles. This inspired me to try something. Every morning, I start my day with an espresso first, followed by reading blog posts for half an hour or so. While I get a lot from these quick reading sessions, I rarely go back to the material afterwards, and thought it would be interesting to keep track of a few, and revisit them at the end of the month. I also decided I would primarily focus on slightly out-of-topic areas, that is, pieces with ideas loosely connected to my daily work, but which I found inspiring or stimulating.

Long story short – here is a collection of links I found interesting this month, with minimal commentary on why I found them interesting. I also tried to mention the source when I remembered it; I am always curious to hear how people come across information, I figured others might be interested in my sources.

Lovers and liars: How many sex partners have you really had?

Since my days studying decision analysis, I have been interested by the topic of heuristics and biases, that is, what strategies we use to process information and form decisions – and how far we are from “rational agents”. There is a lot of food for thought in this experiment; one bit I found intriguing was the suggestion that gender had an influence on what strategy is used to produce an estimate, I wish there was more about that.

The best and worst times to have your case reviewed by a judge

Decision making again. I love a well-designed experiment – in this case, the whole story is there, in just one simple chart. Also a reminder that taking regular snacks during your workday is important.

What is the most efficient algorithm to check if a number is a Fibonacci Number? [via @hammett]

Because every functional programmer loves a Fibonacci sequence :)

Captivating Geometric GIFs by Florian de Looijby [via @ptrelford]

Beautiful – I need to look into how one creates gifs programmatically!

Data science done well looks easy - and that is a big problem for data scientists [via @tggleeson]

An interesting discussion on a topic that has been in the back of my mind for a bit: the discourse around data science / machine learning tends to emphasize fancy techniques and algorithm, and not the data work, even though it is an essential part of the job.

Donut math: how donut.c works [via @flangy]

No comment – pure awesome.

Are we kidding ourselves on competition?

A provocative and intriguing argument: rational investors should diversify, and as a result, firms that act in the best interest of their shareholders have an incentive to avoid competition and collude.

Hacking an epic NHL goal celebration with a hue light show and real-time machine learning [via @rasbt]

Love it – a gross misuse of brain and computer power, and a very interesting machine learning project.

Parasitic populations solve algorithm problems in half the time

I have a long-standing fascination for optimization techniques that mimic the behavior of populations, mixed together with randomness (ant colonies, bee colonies, swarms…). The idea to introduce a parasite in the system to preserve diversity (and avoid concentrating all the resources on one single search region, I presume) sounds really interesting, I just wish the full article was available – the link merely hints at the idea.

That’s it for April – I’ll keep doing this for myself anyways, if anybody is interested, I’ll be happy to post these once a month.

Rewriting a logistic regression from C# to F# (part 2)

mathias — Mon, 30 Mar 2015 16:34:00 -1300

In our previous post, we looked at James McCaffrey’s code, “Gradient Descent Training Using C#” from MSDN magazine, and took a stab at rewriting the first part in F#, to clarify a bit the way the dataset was created. Today, we’ll dive in the second block, which implements the logistic regression using gradient descent. Again, we won’t discuss why the algorithm works – the article does a pretty good job at that – and focus instead purely on the F# / C# conversion part.

Let’s begin by taking a look at the core of the C# code, which lives in the LogisticClassifier class. I took the liberty to do some minor cleanup, and remove some parts which were un-necessary, so as to make it a bit easier to see what is going on:

public class LogisticClassifier
{
    private int numFeatures; // number of x variables aka features
    private double[] weights; // b0 = constant
    private Random rnd;

    public LogisticClassifier(int numFeatures)
    {
        this.numFeatures = numFeatures;
        this.weights = new double[numFeatures + 1]; // [0] = b0 constant
        this.rnd = new Random(0);
    }

    public double[] Train(double[][] trainData, int maxEpochs, double alpha)
    {
        // alpha is the learning rate
        int epoch = 0;
        int[] sequence = new int[trainData.Length]; // random order
        for (int i = 0; i < sequence.Length; ++i)
            sequence[i] = i;

        while (epoch < maxEpochs)
        {
            ++epoch;

            if (epoch % 100 == 0 && epoch != maxEpochs)
            {
                double mse = Error(trainData, weights);
                Console.Write("epoch = " + epoch);
                Console.WriteLine("  error = " + mse.ToString("F4"));
            }

            Shuffle(sequence); // process data in random order

            // stochastic/online/incremental approach
            for (int ti = 0; ti < trainData.Length; ++ti)
            {
                int i = sequence[ti];
                double computed = ComputeOutput(trainData[i], weights);
                int targetIndex = trainData[i].Length - 1;
                double target = trainData[i][targetIndex];

                weights[0] += alpha * (target - computed) * 1; // the b0 weight has a dummy 1 input
                for (int j = 1; j < weights.Length; ++j)
                    weights[j] += alpha * (target - computed) * trainData[i][j - 1];             
            }
        } // while
        return this.weights; // by ref is somewhat risky
    } // Train

    private void Shuffle(int[] sequence)
    {
        for (int i = 0; i < sequence.Length; ++i)
        {
            int r = rnd.Next(i, sequence.Length);
            int tmp = sequence[r];
            sequence[r] = sequence[i];
            sequence[i] = tmp;
        }
    }

    private double Error(double[][] trainData, double[] weights)
    {
        // mean squared error using supplied weights
        int yIndex = trainData[0].Length - 1; // y-value (0/1) is last column
        double sumSquaredError = 0.0;
        for (int i = 0; i < trainData.Length; ++i) // each data
        {
            double computed = ComputeOutput(trainData[i], weights);
            double desired = trainData[i][yIndex]; // ex: 0.0 or 1.0
            sumSquaredError += (computed - desired) * (computed - desired);
        }
        return sumSquaredError / trainData.Length;
    }

    private double ComputeOutput(double[] dataItem, double[] weights)
    {
        double z = 0.0;
        z += weights[0]; // the b0 constant
        for (int i = 0; i < weights.Length - 1; ++i) // data might include Y
            z += (weights[i + 1] * dataItem[i]); // skip first weight
        return 1.0 / (1.0 + Math.Exp(-z));
    }
} // LogisticClassifier

Just from the length of it, you can tell that most of the action is taking place in the Train method, so let’s start there. What we have here is two nested loops. The outer one runs maxEpoch times, a user defined parameter. Inside that loop, we randomly shuffle the input dataset, and then loop over each training example, computing the predicted output of the logistic function for that example, comparing it to a target, the actual label of the example, which can be 0 or 1, and adjusting the weights so as to reduce the error. We also have a bit of logging going on, displaying the prediction error every hundred outer iteration. Once the two loops are over, we return the weights.

Two things strike me here. First, a ton of indexes are involved, and this tends to obfuscate what is going on; as a symptom, a few comments are needed, to clarify how the indexes work, and what piece of the data is organized. Then, there is a lot of mutation going on. It’s not necessarily a bad thing, but I tend to avoid it as much as possible, simply because it requires keeping more moving parts in my head when I try to follow the code, and also, as McCaffrey himself points out in a comment, because “by ref is somewhat risky”.

As a warm up, let’s begin with the error computation, which is displayed every 100 iterations. Rather than having to remember in what column the actual expected value is stored, let’s make our life easier, and use a type alias, Example, so that the features are neatly tucked in an array, and the value is clearly separated. We need to compute the average square difference between the expected value, and the output of the logistic function for each example. As it turns out, we have already implemented the logistic function in the first part in the code, so re-implementing it as in ComputeOutput seems like un-necessary work – we can get rid of that part entirely, and simply map every example to the square error, and compute the average, using pattern matching on the examples to separate clearly the features and the expected value:

type Example = float [] * float

let Error (trainData:Example[], weights:float[]) =
    // mean squared error using supplied weights
    trainData
    |> Array.map (fun (features,value) -> 
        let computed = logistic weights features
        let desired = value
        (computed - desired) * (computed - desired))
    |> Array.average

Some of you might argue that this could be made tighter – I can think of at least two possibilities. First, using a Tuple might not be the most expressive approach; replacing it with a Record instead could improve readability. Then, we could also skip the map + average part, and directly ask F# to compute the average on the fly:

type Example = { Features:float[]; Label:float }

let Error (trainData:Example[], weights:float[]) =
    trainData
    |> Array.averageBy (fun example -> 
        let computed = logistic weights example.Features
        let desired = example.Label
        (computed - desired) * (computed - desired))

I will keep my original version the way it is, mostly because we created a dataset based on tuples last times.

We are now ready to hit the center piece of the algorithm. Just like we would probably try to extract a method in C#, we will start extracting some of the gnarly code that lies in the middle:

for (int ti = 0; ti < trainData.Length; ++ti)
{
    int i = sequence[ti];
    double computed = ComputeOutput(trainData[i], weights);
    int targetIndex = trainData[i].Length - 1;
    double target = trainData[i][targetIndex];

    weights[0] += alpha * (target - computed) * 1; // the b0 weight has a dummy 1 input
    for (int j = 1; j < weights.Length; ++j)
        weights[j] += alpha * (target - computed) * trainData[i][j - 1];             
}

Rather than modify the weights values, it seems safer to compute new weights. And because we opted last week to insert a column with ones for the constant feature, we won’t have to deal with the index misalignment, which requires separate handling for b0 and the rest. Instead, we can write an update operation that takes in an example and weights, and returns new weights:

let update (example:Example) (weights:float[]) =
    let features,target = example
    let computed = logistic weights features
    weights 
    |> Array.mapi (fun i w -> 
        w + alpha * (target - computed) * features.[i])

Array.mapi allows us to iterate over the weights, while maintaining the index we are currently at, which we use to grab the feature value at the corresponding index. Alternatively, you could go all verbose and zip the arrays together – or all fancy with a double-pipe and map2 to map the two arrays in one go. Your pick:

Array.zip weights features
|> Array.map (fun (weight,feat) -> 
    weight + alpha * (target - computed) * feat)

(weights,features) 
||> Array.map2 (fun weight feat -> 
    weight + alpha * (target - computed) * feat)

We are now in a very good place; the only thing left to do is to plug that into the two loops. The inner loop is a perfect case for a fold (the Aggregate method in LINQ): given a starting value for weights, we want to go over every example in our training set, and, for each of them, run the update function to compute new weights. For the while loop, we’ll take a different approach, and use recursion: when the epoch reaches maxEpoch, you are done, return the weights, otherwise, keep shuffling the data and updating weights. Let’s put that all together:

let Train (trainData:Example[], numFeatures, maxEpochs, alpha, seed) =
           
    let rng = Random(seed)
    let epoch = 0

    let update (example:Example) (weights:float[]) =
        let features,target = example
        let computed = logistic weights features
        weights 
        |> Array.mapi (fun i w -> 
            w + alpha * (target - computed) * features.[i])

    let rec updateWeights (data:Example[]) epoch weights =
        
        if epoch % 100 = 0 
        then printfn "Epoch: %i, Error: %.2f" epoch (Error (data,weights))
        
        if epoch = maxEpochs then weights
        else
            let data = shuffle rng data
            let weights = 
                data 
                |> Array.fold (fun w example -> update example w) weights
            updateWeights data (epoch + 1) weights
    // initialize the weights and start the recursive update
    let initialWeights = [| for _ in 1 .. numFeatures + 1 -> 0. |]
    updateWeights trainData 0 initialWeights

And that’s pretty much it. We replaced the whole class by a couple of functions, and all the indexes are gone. This is probably a matter of taste and comfort with functional concepts, but in my opinion, this is much easier to follow.

Before trying it out, to make sure it works, I’ll take a small liberty, and modify the Train function. As it stands right now, it returns the final weights, but really, we don’t care about the weights, what we want is a classifier, which is a function that, given an array, will predict a one or a zero. That’s easy enough, let’s return a function at the end instead of weights:

// initialize the weights and start the recursive update
let initialWeights = [| for _ in 1 .. numFeatures + 1 -> 0. |]
let finalWeights = updateWeights trainData 0 initialWeights
let classifier (features:float[]) = 
    if logistic finalWeights features > 0.5 then 1. else 0.
classifier

We can now wrap it up, and see our code in action:

printfn "Begin Logistic Regression (binary) Classification demo"
printfn "Goal is to demonstrate training using gradient descent"

let numFeatures = 8 // synthetic data
let numRows = 10000
let seed = 1

printfn "Generating %i artificial data items with %i features" numRows numFeatures    
let trueWeights, allData = makeAllData(numFeatures, numRows, seed)

printfn "Data generation weights:"
trueWeights |> Array.iter (printf "%.2f ")
printfn ""

printfn "Creating train (80%%) and test (20%%) matrices"
      
let trainData, testData = makeTrainTest(allData, 0)
printfn "Done"

let maxEpochs = 1000
let alpha = 0.01

let classifier = Train (trainData,numFeatures,maxEpochs,alpha,0)

let accuracy (examples:Example[]) = 
    examples 
    |> Array.averageBy (fun (feat,value) -> 
        if classifier feat = value then 1. else 0.)

accuracy trainData |> printfn "Prediction accuracy on train data: %.4f"
accuracy testData |> printfn "Prediction accuracy on test data: %.4f"

We used a small trick to compute the accuracy – we mark every correct call as a one, every incorrect one as a zero, which, when we compute the average, gives us directly the proportion of cases that were called correctly. On my machine, I get the following output:

> 
Prediction accuracy on train data: 0.9988
Prediction accuracy on test data: 0.9980

Looks good enough to me, the implementation seems to be working. The whole code presented here is available as a gist here. I’ll leave it at that for now (I might revisit it later, and try to make this work with DiffSharp at some point, if anyone is interested) – feel free to ask questions, or drop me a comment on Twitter!

Rewriting a logistic regression from C# to F# (part 1)

mathias — Sun, 22 Mar 2015 17:27:00 -1300

I will admit it, I got a bit upset by James McCaffrey’s column in MSDN magazine this month, “Gradient Descent Training Using C#”. While the algorithm explanations are quite good, I was disappointed by the C# sample code, and kept thinking to myself “why oh why isn’t this written in F#”. This is by no means intended as a criticism of C#; it’s a great language, but some problems are just better suited for different languages, and in this case, I couldn’t fathom why F# wasn’t used.

Long story short, I just couldn’t let it go, and thought it would be interesting to take that C# code, and do a commented rewrite in F#. I won’t even go into why the code does what it does – the article explains it quite well – but will instead purely focus on the implementation, and will try to keep it reasonably close to the original, at the expense of some additional nifty things that could be done.

The general outline of the code follows two parts:

Create a synthetic dataset, creating random input examples, and computing the expected result using a known function,
Use gradient descent to learn the model parameters, and compare them to the true value to check whether the method is working.

You can download the original C# code here. Today we’ll focus only on the first part, which is mainly contained in two methods, MakeAllData and MakeTrainTest:

static double[][] MakeAllData(int numFeatures, int numRows, int seed)
{
  Random rnd = new Random(seed);
  double[] weights = new double[numFeatures + 1]; // inc. b0
  for (int i = 0; i < weights.Length; ++i)
    weights[i] = 20.0 * rnd.NextDouble() - 10.0; // [-10.0 to +10.0]

  double[][] result = new double[numRows][]; // allocate matrix
  for (int i = 0; i < numRows; ++i)
    result[i] = new double[numFeatures + 1]; // Y in last column

  for (int i = 0; i < numRows; ++i) // for each row
  {
    double z = weights[0]; // the b0 
    for (int j = 0; j < numFeatures; ++j) // each feature / column except last
    {
      double x = 20.0 * rnd.NextDouble() - 10.0; // random X in [10.0, +10.0]
      result[i][j] = x; // store x
      double wx = x * weights[j + 1]; // weight * x 
      z += wx; // accumulate to get Y
    }
    double y = 1.0 / (1.0 + Math.Exp(-z));
    if (y > 0.55)  // slight bias towards 0
      result[i][numFeatures] = 1.0; // store y in last column
    else
      result[i][numFeatures] = 0.0;
  }
  Console.WriteLine("Data generation weights:");
  ShowVector(weights, 4, true);

  return result;
}

MakeAllData takes a number of features and rows, and a seed for the random number generator so that we can replicate the same dataset repeatedly. The dataset is represented as an array of array of doubles. The first columns, from 0 to numFeatures – 1, contain random numbers between –10 and 10. The last column contains a 0 or a 1. What we are after here is a classification model: each row can take two states (1 or 0), and we are trying to predict them from observing the features. In our case, that value is computed using a logistic model: we have a set of weights (which we also generate randomly), corresponding to each feature, and the output is

logistic [ x1; x2; … xn ] = 1.0 / (1.0 + exp ( - (w0 * 1.0 + w1 * x1 + w2 * x2 + … + wn * xn))

Note that w0 plays the role of a constant term in the equation, and is multiplied by 1.0 all the time. This is adding some complications to a code where indices are already flying left and right, because now elements in the weights array are mis-aligned by one element with the elements in the features array. Personally, I also don’t like adding another column to contain the predicted value, because that’s another implicit piece of information we have to remember.

In that frame, I will make two minor changes here, just to keep my sanity. First, as is often done, we will insert a column containing just 1.0 in each observation, so that the weights and features are now aligned. Then, we will move the 0s and 1s outside of the features array, to avoid any ambiguity.

Good. Instead of creating a Console application, I’ll simply go for a script. That way, I can just edit my code and check live whether it does what I want, rather than recompile and run every time.

Let’s start with the weights. What we are doing here is simply creating an array of numFeatures + 1 elements, populated by random values between –10.0 and 10.0. We’ll go a bit fancy here: given that we are also generating random numbers the same way a bit further down, let’s extract a function that generates numbers uniformly between a low and high value:

let rnd = Random(seed)
let generate (low,high) = low + (high-low) * rnd.NextDouble()
let weights = Array.init (numFeatures + 1) (fun _ -> generate(-10.0,10.0))

The next section is where things get a bit thornier. The C# code creates an array, then populates it row by row, first filling in the columns with random numbers, and then applying the logistic function to compute the value that goes in the last column. We can make that much clearer, by extracting that function out. The logistic function is really doing 2 things:

first, the sumproduct of 2 arrays,
and then, 1.0/(1.0 + exp ( – z ).

That is easy enough to implement:

let sumprod (v1:float[]) (v2:float[]) =
    Seq.zip v1 v2 |> Seq.sumBy (fun (x,y) -> x * y)

let sigmoid z = 1.0 / (1.0 + exp (- z))

let logistic (weights:float[]) (features:float[]) =
    sumprod weights features |> sigmoid

We can now use all this, and generate a dataset by simply first creating rows of random values (with a 1.0 in the first column for the constant term), applying the logistic function to compute the value for that row, and return them as a tuple:

open System

let sumprod (v1:float[]) (v2:float[]) =
    Seq.zip v1 v2 |> Seq.sumBy (fun (x,y) -> x * y)

let sigmoid z = 1.0 / (1.0 + exp (- z))

let logistic (weights:float[]) (features:float[]) =
    sumprod weights features |> sigmoid

let makeAllData (numFeatures, numRows, seed) =

    let rnd = Random(seed)
    let generate (low,high) = low + (high-low) * rnd.NextDouble()
    let weights = Array.init (numFeatures + 1) (fun _ -> generate(-10.0,10.0))
    
    let dataset = 
        [| for row in 1 .. numRows ->
            let features = 
                [|  
                    yield 1.0 
                    for feat in 1 .. numFeatures -> generate(-10.0,10.0) 
                |]
            let value = 
                if logistic weights features > 0.55 
                then 1.0 
                else 0.0
            (features, value)
        |]

    weights, dataset

Done. Let’s move to the second part of the data generation, with the MakeTrainTest method. Basically, what this does is take a dataset, shuffle it, and split it in two parts, 80% which we will use for training, and 20% we leave out for validation.

static void MakeTrainTest(double[][] allData, int seed,
  out double[][] trainData, out double[][] testData)
{
  Random rnd = new Random(seed);
  int totRows = allData.Length;
  int numTrainRows = (int)(totRows * 0.80); // 80% hard-coded
  int numTestRows = totRows - numTrainRows;
  trainData = new double[numTrainRows][];
  testData = new double[numTestRows][];

  double[][] copy = new double[allData.Length][]; // ref copy of all data
  for (int i = 0; i < copy.Length; ++i)
    copy[i] = allData[i];

  for (int i = 0; i < copy.Length; ++i) // scramble order
  {
    int r = rnd.Next(i, copy.Length); // use Fisher-Yates
    double[] tmp = copy[r];
    copy[r] = copy[i];
    copy[i] = tmp;
  }
  for (int i = 0; i < numTrainRows; ++i)
    trainData[i] = copy[i];

  for (int i = 0; i < numTestRows; ++i)
    testData[i] = copy[i + numTrainRows];
}

Again, there is a ton of indexing going on, which in my old age I find very hard to follow. Upon closer inspection, really, the only thing complicated here is the Fischer-Yates shuffle, which takes an array and randomly shuffles the order. The rest is pretty simply – we just want to shuffle, and then split into two arrays. Let’s extract the shuffle code (which happens to also be used and re-implemented later on):

let shuffle (rng:Random) (data:_[]) =
    let copy = Array.copy data
    for i in 0 .. (copy.Length - 1) do
        let r = rng.Next(i, copy.Length)
        let tmp = copy.[r]
        copy.[r] <- copy.[i]
        copy.[i] <- tmp
    copy

We went a tiny bit fancy again here, and made the shuffle work on generic arrays; we also pass in the Random instance we want to use, so that we can control / repeat shuffles if we want, by passing a seeded Random. Does this work? Let’s check in FSI:

> [| 1 .. 10 |] |> shuffle (Random ());;
val it : int [] = [|6; 7; 2; 10; 8; 5; 4; 9; 3; 1|]

Looks reasonable. Let’s move on – we can now implement the makeTrainTest function.

let makeTrainTest (allData:_[], seed) =

      let rnd = Random(seed)
      let totRows = allData.Length
      let numTrainRows = int (float totRows * 0.80) // 80% hard-coded

      let copy = shuffle rnd allData
      copy.[.. numTrainRows-1], copy.[numTrainRows ..]

Done. A couple of remarks here. First, F# is a bit less lenient than C# around types, so we have to be explicit when converting the number of rows to 80%, first to float, then back to int. As an aside, this used to annoy me a bit in the beginning, but I have come to really like having F# as this slightly psycho-rigid friend who nags me when I am taking a dangerous path (for instance, dividing two integers and hoping for a percentage).

Besides that, I think the code is markedly clearer. The complexity of the shuffle has been nicely contained, and we just have to slice the array to get a training and test sets. As an added bonus, we got rid of the out parameters, and that always feels nice and fuzzy.

I’ll leave it at for today; next time we’ll look at the second part, the learning algorithm itself. Before closing shop, let me make a couple of comments. First, the code is a tad shorter, but not by much. I haven’t really tried, and deliberately made only the changes I thought were needed. What I like about it, though, is that all the indexes are gone, except for the shuffle. In my opinion, this is a good thing. I find it difficult to keep it all in my head when more than one index is involved; when I need to also remember what columns contain special values, I get worried – and just find it hard to figure out what is going on. By contrast, I think makeTrainTest, for instance, conveys pretty directly what it does. makeAllData, in spite of some complexity, also maps closely the way I think about my goal: “I want to generate rows of inputs” – this is precisely what the code does. There is probably an element of culture to it, though; looping over arrays has a long history, and is familiar to every developer, and what looks readable to me might look entirely weird to some.

Easier, or more complicated than before? Anything you like or don’t like – or find unclear? Always interested to hear your opinion! Ping me on Twitter if you have comments.

First impressions with DiffSharp, an F# autodiff library

mathias — Sat, 21 Feb 2015 12:23:00 -1300

A few weeks ago, I came across DiffSharp, an automatic differentiation library in F#. As someone whose calculus skills have always been rather mediocre (thanks Wolfram Alpha!), but who needs to deal with gradients and the like on a regular basis because they are quite useful in machine learning and numerical methods, the project looked pretty interesting: who wouldn’t want exact and efficient calculations of derivatives? So I figured I would take a couple of hours to experiment with the library. This post is by no means an in-depth evaluation, but rather intended as “notes from the road” from someone entirely new to DiffSharp.

Basics

Suppose I want to compute the derivative of f(x) = √ x at, say, 42.0. Double-checking Wolfram Alpha confirms that f has derivative f’(x) = 1 / (2 x √ x) .

Once DiffSharp is installed via Nuget, we can automatically evaluate f’(x) :

#r @"..\packages\DiffSharp.0.5.7\lib\DiffSharp.dll"
open DiffSharp.AD.Forward

let f x = sqrt x
diff f 42. |> printfn "Evaluated: %f"
1. / (2. * sqrt 42.)  |> printfn "Actual: %f"

Evaluated: 0.077152
Actual: 0.077152

val f : x:Dual -> Dual
val it : unit = ()

First off, obviously, it worked. Without any need for us to perform anything, DiffSharp took in our implementation of f, and computed the correct value. This is really nifty.

The piece which is interesting here is the inferred signature of f. If I were to remove the line that immediately follows the function declaration, f would have the following signature:

val f : x:float –> float

The moment you include the line diff f 42., the inferred type changes drastically, and becomes

val f : x:Dual –> Dual

This is pretty interesting. Because we call diff on f, which expects Duals (a type that is defined in DiffSharp), our function isn’t what we originally defined it to be – and calling f 42.0 at that point (for instance) will fail, because 42.0 is a float, and not a Dual. In other words, DiffSharp leverages type inference pretty aggressively, to convert functions into the form it needs to perform its magic.

Edit: Atilim Gunes Baydin suggested another way around that issue, which is inlining f. The following works perfectly well, and allows to both differentiate f, and use this against floats:

let inline f x = sqrt x
let f' = diff f
f 42.

Thanks for the input!

This has a couple of implications. First, if you work in a script, you need to be careful about how you send your code to the F# interactive for execution. If you process the sample code above line by line in FSI, the evaluation will fail, because f will be inferred to be float –> float. Then, you will potentially need to annotate your functions with type hints, to help inference. As an example, the following doesn’t work:

let g x = 3. * x
diff g 42.

As is, g is still inferred to be of type float –> float, because of the presence of the constant term, which is by default inferred as a float. That issue can be addressed at least two ways – by explicitly marking x or 3. as dual in g, like this:

let g x = (dual 3.) * x
let h (x:Dual) = 3. * x

That’s how far we will go on this – if you want to dive in deeper, the Type Inference page discusses the topic in much greater detail

A tiny example

So why is this interesting? As I mentioned earlier, differentiation is used heavily in numeric algorithms to identify values that minimize a function, a prime example being the gradient descent algorithm. The simplest example possible would be finding a (local) minimum of a single-argument function: starting from an arbitrary value x, we can iteratively follow the direction of steepest descent, until no significant change is observed.

Here is a quick-and-dirty implementation, using DiffSharp:

let minimize f x0 alpha epsilon =
    let rec search x =
        let fx' = diff f x
        if abs fx' < epsilon
        then x
        else
            let x = x - alpha * fx'
            search x
    search x0

Edit, 3/4/2015: fixed issue in code, using abs fx’ instead of fx’

Because DiffSharp handles the differentiation part automatically for us, with only 10 lines of code, we can now pass in arbitrary functions we want to minimize, and (with a few caveats…), and get a local minimum, no calculus needed:

let epsilon = 0.000001

let g (x:Dual) = 3. * pown x 2 + 2. * x + 1.
minimize g 0. 0.1 epsilon |> printfn "Min of g at x = %f"

let h (x:Dual) = x + x * sin(x) + cos(x) * (3. * x  - 7.)
minimize h 0. 0.1 epsilon |> printfn "Min of h at x = %f"

> 
Min of g at x = -0.333333
Min of h at x = -0.383727

Let’s make sure this is reasonable. g is a quadratic function, which has a minimum or maximum at –b/2*a, that is, –2 / 2 x 3 - this checks out. As for h, inspecting the function plot confirms that it has a minimum around the identified value:

Edit, 3/4/2015: changed function h to a simpler shape.

Conclusion

I have barely started to scratch the surface of DiffSharp in this post, but so far, I really, really like its promise. While I limited my examples to single-variable functions, DiffSharp supports multivariate functions, and vector operations as well. The way it uses type inference is a bit challenging at first, but seems a reasonable price to pay for the resulting magic. My next step will probably be a less tiny example, perhaps a logistic regression against realistic data. I am very curious to try out the algebra bits – and also wondering in the back of my head how to best use the library in general. For instance, how easy is it to construct a function from external data, and turn it into the appropriate types for DiffSharp to work its magic? How well does this integrate with other libraries, say, Math.NET? We’ll see!

In the meanwhile, I’d recommend checking out the project page, which happens to also be beautifully documented! And, as always, you can ping me on twitter for comments or question.

Fun with L-system

mathias — Sun, 11 Jan 2015 18:37:00 -1300

I had the great pleasure to speak at CodeMash this week, and, on my way back, ended up spending a couple of hours at the Atlanta airport waiting for my connecting flight back to the warmer climate of San Francisco – a perfect opportunity for some light-hearted coding fun. A couple of days earlier, I came across this really nice tweet, rendering the results of an L-system:

{start:'FFPF',rules:{F:'PF++F[FF-F+PF+FPP][F]FFPF',P:''},'α':60} pic.twitter.com/JZGDV4ghFy
— LSystemBot (@LSystemBot) January 10, 2015

I ended up looking up L-systems on Wikipedia, and thought this would make for some fun coding exercise. In a nutshell, a L-system is a grammar. It starts with an alphabet of symbols, and a set of rules which govern how each symbol can be transformed into another chain of symbols. By applying these rules to a starting state (the initial axiom), one can evolve it into a succession of states, which can be seen as the growth of an organism. And by mapping each symbol to operations in a logo/turtle like language, each generation can then be rendered as a graphic.

So how could we go about coding this in F#? If you are impatient, you can find the final result as a gist here.

First, I started with representing the core elements of an L-System with a couple of types:

type Symbol = | Sym of char

type State = Symbol list

type Rules = Map<Symbol,State>

type LSystem = 
    { Axiom:State
      Rules:Rules }

A symbol is a char, wrapped in a single-case discriminated union, and a State is simply a list of Symbols. We define the Rules that govern the transformation of Symbols by a Map, which associates a particular Symbol with a State, and an L-System is then an Axiom (the initial State), with a collection of Rules.

Let’s illustrate this on the second example from the Wikipedia page, the Pythagoras tree. Our grammar contains 4 symbols, 0, 1, [ and ], we start with a 0, and we have 2 rules, (1 → 11), and (0 → 1[0]0). This can be encoded in a straightforward manner in our domain, like this:

let lSystem =
    { Axiom = [ Sym('0') ]
      Rules = [ Sym('1'), [ Sym('1'); Sym('1') ]
                Sym('0'), [ Sym('1'); Sym('['); Sym('0'); Sym(']'); Sym('0') ]]
              |> Map.ofList }

Growing the organism by applying the rules is fairly straightforward: given a State, we traverse the list of Symbols, look up for each of them if there is a matching rule, and perform a substitution if it is found, leaving it unchanged otherwise:

(*
Growing from the original axiom
by applying the rules
*)

let applyRules (rs:Rules) (s:Symbol) =
    match (rs.TryFind s) with
    | None -> [s]
    | Some(x) -> x

let evolve (rs:Rules) (s:State) =
    [ for sym in s do yield! (applyRules rs sym) ]

let forward (g:LSystem) =
    let init = g.Axiom
    let gen = evolve g.Rules
    init |> Seq.unfold (fun state -> Some(state, gen state))

// compute nth generation of lSystem
let generation gen lSystem =
    lSystem
    |> forward 
    |> Seq.nth gen
    |> Seq.toList

What does this give us on the Pythagoras Tree?

> lSystem |> generation 1;;
val it : Symbol list = [Sym '1'; Sym '['; Sym '0'; Sym ']'; Sym '0']

Nice and crisp – that part is done. Next up, rendering. The idea here is that for each Symbol in a State, we will perform a substitution with a sequence of instructions, either a Move, drawing a line of a certain length, or a Turn of a certain Angle. We will also have a Stack, where we can Push or Pop the current position of the Turtle, so that we can for instance store the current position and direction on the stack, perform a couple of moves with a Push, and then return to the previous position by a Pop, which will reset the turtle to the previous position. Again, that lends itself to a very natural model:

(*
Modelling the Turtle/Logo instructions
*)

type Length = | Len of float
type Angle = | Deg of float

// override operator later
let add (a1:Angle) (a2:Angle) =
    let d1 = match a1 with Deg(x) -> x
    let d2 = match a2 with Deg(x) -> x
    Deg(d1+d2)

type Inst =
    | Move of Length
    | Turn of Angle
    | Push
    | Pop

let Fwd x = Move(Len(x))
let Lft x = Turn(Deg(x))
let Rgt x = Turn(Deg(-x))

We can now transform our L-system state into a list of instructions, and convert them into a sequence of Operations, in that case Drawing lines between 2 points:

type Pos = { X:float; Y:float; }
type Dir = { L:Length; A:Angle }

type Turtle = { Pos:Pos; Dir:Dir }
type ProgState = { Curr:Turtle; Stack:Turtle list }

let turn angle turtle = 
    let a = turtle.Dir.A |> add angle
    { turtle with Dir = { turtle.Dir with A = a } }

type Translation = Map<Symbol,Inst list>

type Ops = | Draw of Pos * Pos

let pi = System.Math.PI

let line (pos:Pos) (len:Length) (ang:Angle) =
    let l = match len with | Len(l) -> l
    let a = match ang with | Deg(a) -> (a * pi / 180.)
    { X = pos.X + l * cos a ; Y = pos.Y + l * sin a }

let execute (inst:Inst) (state:ProgState) =
    match inst with
    | Push -> None, { state with Stack = state.Curr :: state.Stack }
    | Pop -> 
        let head::tail = state.Stack // assumes more Push than Pop
        None, { state with Curr = head; Stack = tail }
    | Turn(angle) -> 
        None, { state with Curr =  state.Curr |> turn angle }
    | Move(len) -> 
        let startPoint = state.Curr.Pos
        let endPoint = line startPoint len state.Curr.Dir.A
        Some(Draw(startPoint,endPoint)), { state with Curr = { state.Curr with Pos = endPoint } }

let toTurtle (T:Translation) (xs:Symbol list) =

    let startPos = { X = 400.; Y = 400. }
    let startDir = { L = Len(0.); A = Deg(0.) }
    let init = 
        { Curr = { Pos = startPos; Dir = startDir }
          Stack = [] }
    xs 
    |> List.map (fun sym -> T.[sym]) 
    |> List.concat
    |> Seq.scan (fun (op,state) inst -> execute inst state) (None,init)
    |> Seq.map fst
    |> Seq.choose id

We simply map each Symbol to a List of instructions, transform the list of symbols into a list of instructions, and maintain at each step the current position and direction, as well as a Stack (represented as a list) of positions and directions. How does it play out on our Pythagoras Tree? First, we define the mapping from Symbols to Instructions:

let l = 1.
let T = 
    [ Sym('0'), [ Fwd l; ]
      Sym('1'), [ Fwd l; ]
      Sym('['), [ Push; Lft 45.; ]
      Sym(']'), [ Pop; Rgt 45.; ] ]
    |> Map.ofList

… and we simply send that toTurtle, which produces a list of Draw instructions:

> lSystem |> generation 1 |> toTurtle T;;
val it : seq<Ops> =
  seq
    [Draw ({X = 400.0;
            Y = 400.0;},{X = 401.0;
                         Y = 400.0;}); Draw ({X = 401.0;
                                              Y = 400.0;},{X = 401.7071068;
                                                           Y = 400.7071068;});
     Draw ({X = 401.0;
            Y = 400.0;},{X = 401.7071068;
                         Y = 399.2928932;})]

Last step – some pretty pictures. We’ll simply generate a html document, rendering the image using SVG, by creating one SVG line per Draw instruction:

let header = """
<!DOCTYPE html>
<html>
<body>
<svg height="800" width="800">"""

let footer = """
</svg>
</body>
</html>
"""

let toSvg (ops:Ops seq) =
    let asString (op:Ops) = 
        match op with
        | Draw(p1,p2) -> sprintf """<line x1="%f" y1="%f" x2="%f" y2="%f" style="stroke:rgb(0,0,0);stroke-width:1" />""" p1.X p1.Y p2.X p2.Y 

    [ yield header
      for op in ops -> asString op
      yield footer ]
    |> String.concat "\n"

open System.IO

let path = "C:/users/mathias/desktop/lsystem.html"
let save template = File.WriteAllText(path,template)

And we are pretty much done:

> lSystem |> generation 8 |> toTurtle T |> toSvg |> save;;
val it : unit = ()

… which produces the following graphic:

Pretty neat! Just for fun, I replicated the Sierpinski Triangle example as well:

let sierpinski () =

    let lSystem =
        { Axiom = [ Sym('A') ]
          Rules = [ Sym('A'), [ Sym('B'); Sym('>'); Sym('A'); Sym('>'); Sym('B') ]
                    Sym('B'), [ Sym('A'); Sym('<'); Sym('B'); Sym('<'); Sym('A') ]]
                  |> Map.ofList }

    let l = 1.
    let T = 
        [ Sym('A'), [ Fwd l; ]
          Sym('B'), [ Fwd l; ]
          Sym('>'), [ Lft 60.; ]
          Sym('<'), [ Rgt 60.; ] ]
        |> Map.ofList

    lSystem 
    |> generation 9
    |> toTurtle T
    |> toSvg 
    |> save

… which results in the following picture:

That’s it for tonight! I had a lot of fun coding this (it certainly made the flight less boring), and found the idea of converting code to turtle instructions, with a stack, pretty interesting. Hope you enjoyed it, and if you end up playing with this, share your creations on Twitter and ping me at @brandewinder!

Gist for the whole code here

The 2014 F# Tour in numbers

mathias — Wed, 31 Dec 2014 10:59:00 -1300

Well, we are in the last hours of 2014, and I am nearly recovered from the craziness that was the F# Europa Tour 2014, so here we go – the Tour, in cold, hard facts (after all, I am a numbers’ guy):

40 days of travelling across Europe.
16 talks.
5 workshops (about 50 hours total).
9 countries.
6991 miles (11,250 kilometers) travelled, roughly (this is straight-line city to city, so the actual number is probably a good deal larger).
14 hours of bus.
roughly 50 hours of train.
roughly 28 hours of plane.
12 cities visited (and spoken at!).
I lost track of how many gallons of beer were ingested. This is big data.
500 attendees? Maybe more? See previous data point.
Delivered hundreds of shiny fsharp.org stickers to F# Communities across Europe. [btw, in case you didn't hear - the F# Software Foundation is now a full-fledged, legally established entity, and YOU can be a member. Check it out!]

Now for the important qualitative questions:

Where did I eat the best bacon? This came as a surprise to me, but I have to say, the bacon I ate in Dublin, Ireland was amazing. Twice.
Where does one find the best beer in Europe? This is a hard one – I had a chance to sample great beers from all over the place. I would say, Munich and its Biergarten rules, but the live beers at BuildStuff in Vilnius, Lithuania, were a very nice surprise.
What’s the weirdest thing I ate? This one goes to Norway and its Lutefisk, a traditional Christmas fish dish. It’s definitely a regional specialty, as in, a specialty which didn’t expand beyond a limited regional area, for good reasons. For the record, I actually enjoyed it!
What was the worst travelling mistake? Booking a last minute train ticket from Paris to Aarhus, Denmark, to realize in the train that instead of a nice sleeping car, I would be spending 22 hours sitting in a train with no food on board.
Biggest scare: every person who has given a talk will tell you, relying on the internet and anything live in a presentation is a rookie mistake. This is great advice, which is why I completely ignored it. It all worked just fine, but learning that Azure had been down for a couple of hours, right before a talk at BuildStuff which 100% required a live deployment to Azure to work, did give me some cold sweat.

Would I do it again? In a heartbeat! It was a bit crazy, and definitely exhausting, but a ton of fun. All of you who helped out making this happen, from the bottom of my heart, thank you! The F# Community is absolutely fantastic, packed with energy and a good, friendly vibe, and everywhere I went felt like family. You all kept me going, so again, thank you (you know who you are)! In the meanwhile, I wish you all a happy year 2015 ahead, let’s make that one even better than 2014, and I hope to see many of you again this year! And, as always, feel free to ping me on Twitter as @brandewinder.

Obviously, the F# Europe tour has arrived in Munich. Prost! #fsharp pic.twitter.com/vP3VG6n8Of
— Mathias Brandewinder (@brandewinder) November 11, 2014

... and the F# tour is now in Vilnius! Live beer, grand time & awesome people. #buildstufflt #fsharp pic.twitter.com/kIJBhQNOwP
— Mathias Brandewinder (@brandewinder) November 19, 2014

In case you wondered, @sforkmann is not ALWAYS working on @paket. Here he is helping @altnetberlin #fsharp dojo pic.twitter.com/BcW8JnP7mM
— Mathias Brandewinder (@brandewinder) November 26, 2014

Nice crowd for @nnugbergen F# #machinelearning hands-on, VS, emacs, vim, XS & monodevelop in the house! #fsharp pic.twitter.com/fu0SkkSnZV
— Mathias Brandewinder (@brandewinder) December 10, 2014

Textogramme

tryphon — Sat, 20 Dec 2014 01:55:23 -1300

This post is December 20th' part of the English F# Advent #fsAdvent series; make sure to also check out the Japanese series, which also packs the awesome!

As I was going around Paris the other day, I ended up in the Concorde metro station. Instead of the standard issue white tiles, this station is decorated with the French constitution, rendered as a mosaic of letters.

[Source: Wikipedia]

My mind started wandering, and by some weird association, it reminded me of Calligrammes, a collection of poems by Guillaume Apollinaire, where words are arranged on the page to depict images that compliment the text itself.

[Source: Wikipedia]

After some more drifting, I started wondering if I could use this as an inspiration for some playful F# fun. How about taking a piece of text, an image, and fusing them into one?

There are many ways one could approach this; being rather lazy, I thought a reasonably simple direction would be to decompose the original image into dark and light blocks, and fill them with the desired text. As simple as it may sound, the task is not entirely trivial. First, we need to decide on an appropriate threshold to separate "dark" and "light" areas on the image, to get a contrast good enough to recognize the image rendered in black & white. Then, we also have to resize the image appropriately into a new grid, where the characters from the original text fit the mapped dark area as closely as possible.

Note: I don't think the warning "don't put this in production, kids" is useful, unless someone thinks there is a market for Calligramme as a Service. However, I'll say this: this is me on "vacation hacking fun" mode, so yes, there are quite probably flaws in that code. I put it up as a Gist here - flame away, or tell me how to make it better on Twitter ;)

Separating dark and light

So how could we go about splitting an image into dark and light pixels? First, we can using the color brightness from the System.Drawing namespace to determine how light the color of an individual pixel is:

open System.Drawing

let brightness (c:Color) = c.GetBrightness ()

let pixels (bmp:Bitmap) =
    seq { for x in 0 .. bmp.Width - 1 do
            for y in 0 .. bmp.Height - 1 ->
                (x,y) |> bmp.GetPixel }

We still need to decide what boundary to use to separate the image between dark and light. What we want in the end is an image which is reasonably balanced, that is, it should be neither overwhelmingly dark or light. A simple way to enforce that is to arbitrarily constrain one third of the pixels at least to be either dark or light. Then, we want a boundary value that is as clear cut as possible, for instance by finding a value with a large brightness change margin. Let's do that:

let breakpoint (bmp:Bitmap) =
    let pixelsCount = bmp.Width * bmp.Height
    let oneThird = pixelsCount / 3
    let pixs = pixels bmp
    let threshold = 
        pixs
        |> Seq.map brightness
        |> Seq.sort
        |> Seq.pairwise
        |> Seq.skip oneThird
        |> Seq.take oneThird
        |> Seq.maxBy (fun (b0,b1) -> b1 - b0)
        |> snd
    let darkPixels = 
        pixs 
        |> Seq.map brightness
        |> Seq.filter ((>) threshold)
        |> Seq.length
    (threshold,darkPixels)

We iterate over every pixel, sort them by brightness, retain only the middle third, and look for the largest brightness increase. Done - breakpoint returns both the threshold value (the lightness level which decides whether a pixel will be classified as dark or light), as well as how many pixels will be marked as dark.

Resizing

Now that we have a boundary value, and know how many pixels will be marked as dark, we need to determine the size of the grid where our text will be mapped. Ignoring for a moment rounding issues, let's figure out a reasonable size for our grid.

First, how many characters do we need? We know the number of dark pixels in the original image - and in our target image, we want the same ratio of text to white space, so the total number of characters we'll want in our final image will be roughly total chars ~ text length * dark pixels / (width * height).

Then, what should the width of the target image, in characters? First, we want [1] target width * target height ~ total chars. Then, ideally, the proportions of the target image should be similar to the original image, so target width / target height ~ width / height, which gives us target height ~ target width * height / width. Substituting in [1] gives us target width * target width * height / width ~ total chars, which simplifies to target width ~ sqrt (total chars * width / height).

Translating this to code, conveniently ignoring all the rounding issues, we get:

let sizeFor (bmp:Bitmap) (text:string) darkPixels =
    let width,height = bmp.Width, bmp.Height
    let pixels = width * height
    let textLength = text.Length
    let chars = textLength * pixels / darkPixels 
    let w = (chars * width / height) |> float |> sqrt |> int
    let h = (w * height) / width
    (w,h)

Rendering

Good, now we are about ready to get down to business. We have an original image, a threshold to determine which pixels to consider dark or light, and a "target grid" of known width and height. What we need now is to map every cell of our final grid to the original image, decide whether it should be dark or light, and if dark, write a character from our text.

Ugh. More approximation ahead. At that point, there is no chance that the cells from our target grid map the pixels from the original image one to one. What should we do? This is my Christmas vacation time, a time of rest and peace, so what we will do is be lazy again. For each cell in the target grid, we will retrieve the pixels that it overlaps on the original image, and simply average out their brightness, not even bothering with a weighted average based on their overlap surface. As other lazy people before me nicely put it, "we'll leave that as an exercise to the reader".

Anyways, here is the result, a mapping function that returns the coordinates of the pixels intersected by a cell, as well as a reducer, averaging the aforementioned pixels by brightness, and a somewhat un-necessary function that transforms the original image in a 2D array of booleans, marking where a letter should go (I mainly created it because I had a hard time keeping track of rows and columns):

let mappedPixels (bmp:Bitmap) (width,height) (x,y) =

    let wScale = float bmp.Width / float width
    let hScale = float bmp.Height / float height

    let loCol = int (wScale * float x)
    let hiCol = 
        int (wScale * float (x + 1)) - 1
        |> min (bmp.Width - 1)
    let loRow = int (hScale * float y)
    let hiRow = 
        int (hScale * float (y + 1)) - 1
        |> min (bmp.Width - 1)

    seq { for col in loCol .. hiCol do
            for row in loRow .. hiRow -> (col,row) }

let reducer (img:Bitmap) pixs =
    pixs 
    |> Seq.map img.GetPixel
    |> Seq.averageBy brightness

let simplified (bmp:Bitmap) (width,height) threshold =

    let map = mappedPixels bmp (width,height)
    let reduce = reducer bmp
    let isDark value = value < threshold

    let hasLetter = map >> reduce >> isDark

    Array2D.init width height (fun col row ->
        (col,row) |> hasLetter)

Almost there - wrap this with 2 functions, applyTo to transform the text into a sequence, and rebuild, to recreate the final string function:

let applyTo (bmp:Bitmap) (width,height) threshold (text:string) =
    
    let chars = text |> Seq.toList
    let image = simplified bmp (width,height) threshold
    
    let nextPosition (col,row) =
        match (col < width - 1) with 
        | true -> (col+1,row) 
        | false -> (0,row+1)
    
    (chars,(0,0)) 
    |> Seq.unfold (fun (cs,(col,row)) ->
        let next = nextPosition (col,row)
        match cs with
        | [] -> Some(' ',(cs,next))
        | c::tail ->
            if image.[col,row]
            then 
                Some(c,(tail,next))
            else Some(' ',(cs,next)))

let rebuild (width,height) (data:char seq) =
    seq { for row in 0 .. height - 1 -> 
            data 
            |> Seq.map string
            |> Seq.skip (row * width)
            |> Seq.take width
            |> Seq.toArray  
            |> (String.concat "") }
    |> (String.concat "\n")

Trying it out

Let's test this out, using the F# Software Foundation logo as an image, and the following text, from fsharp.org, as a filler:

F# is a mature, open source, cross-platform, functional-first programming language. It empowers users and organizations to tackle complex computing problems with simple, maintainable and robust code.

Run this through the grinder…

let path = @"c:/users/mathias/pictures/fsharp-logo.jpg"
let bmp = new Bitmap(path)

let text = """F# is // snipped // """

let threshold,darkPixels = breakpoint bmp
let width,height = sizeFor bmp text darkPixels

text
|> applyTo bmp (width,height) threshold    
|> rebuild (width,height)

… and we get the following:

                        
           F#           
           is           
         a matu         
        re, open        
        source, c       
      ross-platfor      
     m, fun  ctiona     
    l-firs t   progr    
   amming  l   anguag   
  e. It  emp    owers   
 users  and      organi 
 zation s to     tackle 
   compl ex    computi  
   ng pro bl  ems wit   
    h simp l e, main    
     tainab le and      
      robust code.

Not too bad! The general shape of the logo is fairly recognizable, with some happy accidents, like for instance isolating "fun" in "functional". However, quite a bit of space has been left empty, most likely because of the multiple approximations we did along the way.

Improved resizing

Let's face it, I do have some obsessive-compulsive behaviors. As lazy as I feel during this holiday break, I can't let go of this sloppy sizing issue. We can't guarantee a perfect fit (there might simply not be one), but maybe we can do a bit better than our initial sizing guess. Let's write a mini solver, a recursive function that will iteratively attempt to improve the fit.

Given a current size and count of dark cells, if the text is too long to fit, the solver will simply expand the target grid size, adding one row or one column, picking the one that keeps the grid horizonal/vertical proportions closest to the image. If the text fits better in the new solution, keep searching, otherwise, done (similarly, reduce the size if the text is too short to fit).

For the sake of brevity, I won't include the solver code here in the post. If you are interested, you can find it in the gist here.

Below are the results of the original and shiny new code, which I ran on a slightly longer bit of text.

Before:

                                  
               F#is               
              amatur              
             eopenso              
            urcecross             
           -platformfun           
          ctional-firstp          
         rogramminglangua         
        geItempowersusersa        
       ndorganiz  ationstot       
      acklecomp    lexcomput      
     ingproble ms   withsimpl     
    emaintain abl    eandrobus    
   tcodeF#ru nson     LinuxMacO   
  SXAndroid iOSWi      ndowsGPUs  
 andbrowse rsItis       freetouse 
  andisope nsourc       eunderanO 
  SI-approv edlic      enseF#isu  
   sedinawid eran     geofappli   
     cationar eas   andissuppo    
      rtedbybo th   anactive      
      opencommu    nityandin      
       dustry-le  adingcomp       
         aniesprovidingpr         
          ofessionaltool          
          s

… and after:

               F #               
              is am              
             atu reo             
            pens ourc            
           ecros s-pla           
          tformf unctio          
         nal-fir stprogr         
        ammingla nguageIt        
       empowers   usersand       
      organiza t   ionstota      
     cklecomp le    xcomputi     
    ngproble msw     ithsimpl    
   emaintai nabl      eandrobu   
  stcodeF# runso       nLinuxMac 
 OSXAndro  idiOS       WindowsGP 
  Usandbro wsers      Itisfreet  
   ouseandi sope     nsourceun   
    deranOSI -ap    provedlic    
     enseF#is us   edinawide     
      rangeofa p  plication      
       areasand  issupport       
        edbyboth anactive        
         opencom munitya         
          ndindu stry-l          
           eadin gcomp           
            anie spro            
             vid ing             
              pr of              
               e s

We still have a small mismatch, but the fit is much better.

And this concludes our F# Advent post! This was a rather useless exercise, but then, the holidays are about fun rather than productivity. I had fun doing this, and hope you had some fun reading it. In the meanwhile, I wish you all a holiday period full of fun and happiness, and… see you in 2015! And, as always, you can ping me on twitter if you have comments or questions. Cheers!

Some completely useless fun with the logistic map

Admin — Sun, 26 Oct 2014 17:01:00 -1300

From time to time, I get absorbed by questions for no clear reason. This is one of these times – you have been warned.

So here is the question: can I use a logistic map to encode an arbitrary list of 1s and 0s into a single float, and generate back the series by applying the logistic map? I don’t think there is a clear theoretical or practical interest in this question, but for some reason I couldn’t shake it off, and had to do it.

Just to clarify a bit what I have in mind, here is the expression for the logistic map:

x(n+1) = alpha * x(n) * (1-x(n))

This is a recurrence relation, and has been well studied, because it illustrates very nicely some important ideas in chaos theory. In particular, for x0 in ] 0.0; 1.0 [ and values of alpha between 0 and 4, the series will remain in the interval ] 0.0; 1.0 [, and for certain values of alpha, 4.0 for instance, the series will exhibit a chaotic behavior.

Anyways – so here is what I have in mind. If I gave you an arbitrary float in the unit interval, I could “decrypt” binary values this way:

let f x = 4. * x * (1. - x)

let decrypt root = 
    root 
    |> Seq.unfold (fun x -> Some(x, f x)) 
    |> Seq.map (fun x -> if x > 0.5 then 1 else 0)

let test = decrypt 0.12345 |> Seq.take 20 |> Seq.toList

Running that example produces the following result:

val test : int list =
[1; 1; 0; 1; 1; 1; 1; 0; 0; 1; 0; 1; 1; 0; 1; 1; 0; 0; 0; 1; 1; 1; 0; 0; 0;
1; 1; 0; 1; 0; 0; 0; 1; 0; 1; 1; 0; 0; 0; 1; 0; 0; 0; 1; 0; 1; 1; 1; 1; 1;
1; 1; 0; 1; 0; 0; 1; 1; 0; 0; 0; 1; 1]

This illustrates how, from a single float value, in this case, 0.12345, I could generate a list of 0s and 1s. The question is, can I generate any sequence? That is, if I gave you (for instance) the following series [ 0; 1; 1; 0; 1 ], could you give me a float that would produce that sequence? And are there sequences that I couldn’t generate by that mechanism?

As it turns out, any sequence is feasible. If I start from the last number in the series (1 in our case), the value that generated it, x4, had to be in [0.5;1.0], because it got rounded up to 1. But then, x4 = f(x3), which implies that 4.0 * x3 * (1.0 – x3) belongs in [0.5;1.0]. I’ll let you work through the math here (it involves solving a second-degree polynomial) – what you should end up with is that there are exactly 2 segments that, when transformed by f, result in [0.5;1.0] (see the diagram below for a more visual explanation, illustrating how to find the two segments that f transforms into a given segment x(n)).

Because we know that the 4th value in our series is a 0, we also know that x3 has to be in [0.0; 0.5], so we can just compute the intersection of f inverse (interval(x4)) and [0.0; 0.5], and repeat the process over and over again, until we have finished covering the sequence and reached x0, and we are left with one interval. Any number we pick in that interval will produce the desired sequence.

So how does this look in code? Not awesome, but not too bad. invf is the inverse of f, which returns 2 possible values – and backsolve computes the current interval x has to belong to, given the interval its successor has to be in, and the desired value, a 0 or a 1:

let f x = 4. * x * (1. - x)

let decrypt root = 
    root 
    |> Seq.unfold (fun x -> Some(x, f x)) 
    |> Seq.map (fun x -> if x > 0.5 then 1 else 0)

let empty (lo,hi) = lo >= hi
// two inverses, low value then high value
let invf x = (1.-sqrt(1.-x))/2.,(1.+sqrt(1.-x))/2.

// interval = where f(x) needs to be
// binary = whether x is 0 or 1
let backsolve interval binary =
    let lo,hi = 
        match binary with
        | 0 -> (0.0,0.5)
        | 1 -> (0.5,1.0)
        | _ -> failwith "unexpected"
    
    let lo',hi' = interval
    let constraint2 = 
        let x1,x2 = invf lo'
        let y1,y2 = invf hi'
        (x1,y1),(y2,x2) // this is union
    // compute intersect
    let (lo1,hi1),(lo2,hi2) = constraint2
    let sol1 = (max lo1 lo,min hi1 hi)
    let sol2 = (max lo2 lo,min hi2 hi)
    if empty sol1 then sol2 else sol1 

let solve (xs:int list) = 
    let rec back bins curr =
        match bins with
        | [] -> curr
        | hd::tl -> back tl (backsolve curr hd)
    back (xs |> List.rev) (0.,1.)

Does this work? Let’s try out, by generating a random sequence of 20 0s and 1s, and checking that if we encrypt and decrypt it, we get the initial series:

let validate xs =
    let l = List.length xs
    let lo,hi = solve xs
    decrypt (0.5*(lo+hi)) |> Seq.take l |> Seq.toList

let rng = System.Random ()
let sample = List.init 25 (fun _ -> rng.Next(2))
sample = validate sample

It does work – up to a limit. If you start expanding the length of the series you are trying to encrypt, at some point you will observe that the encrypted/decrypted version stops matching the original. This should not come as a surprise: we are operating in finite precision here, so there would be something deeply flawed if we managed to encode a potentially infinite amount of information, by simply using a float. However, in the world of math, where infinite precision exists, we could transform any sequence of 0s and 1s, of any length, into a segment in [ 0.0; 1.0]. Pretty useless, but fun.

One thing I started playing with was representing segments better, with a discriminated union. After all, the algorithm can be expressed entirely as a sequence of interval unions and intersections – I’ll let that to the reader as a fun F# modeling problem!

If you have questions, or even, who knows, find the problem interesting, ping me on Twitter!

More F# Tourism: Europa F# 2014

Admin — Sun, 12 Oct 2014 06:46:00 -1300

Well, last year’s F# tour was so much fun, I figured I would try to do it again, in Europe this time. I am becoming quite fond of F# tourism: after all, what better way to discover a place than going there and meeting locals who happen to have at least one common interest – and spread the F# love in the process?

Anyways, if everything goes according to plan, I should be visiting F# communities in 7 different countries in 6 weeks :) As an aside, if you are running a meetup/user group that is somewhat on my way, have a couch I can crash on, and would like me to stop by, ping me on twitter. I can’t make promises (obviously the schedule is a bit tight already), but if can, I will.

One thing I find pretty exciting is that all of a sudden, conferences are starting to have very nice F# and functional programming offerings. In particular, huge props to:

Build Stuff in Vilnius: the conference last year was fantastic, fun, diverse, stimulating, and just a great atmosphere. And the F#/functional lineup this year is awesome. Trust me, if you can go – just go, you won’t regret it.
NDC London: when you see a major conference like NDC putting together one entire track solely dedicated to functional programming, you know something is happening. I am really stoked – at that point, I don’t see why I would attend conferences without a solid functional track. My daily work is primarily functional, and in my (biased) opinion, functional is where a lot of the innovation is happening lately. So… thanks to NDC for bridging the gap, and putting together a program that I can enjoy!

At any rate, here is the current plan – stay tuned for updates and more details, and hope to see you somewhere along the way!

Nov 3 & 4: Aarhus, Denmark

Nov 6 & 7: London, UK

Progressive F# Tutorials

Nov 8: London, UK

Hack & Chat! Community Hackathon

Nov 10: Dublin, Ireland

Functional Kats: Coding dojo: a gentle introduction to Machine Learning with F#

Nov 11: Munich, Germany

Munich .NET user group: F# for the C# developer

Nov 12: Zurich, Switzerland

Zurich F# Meetup: Coding dojo: a gentle introduction to Machine Learning with F#

Nov 17, Paris

Paris F# Meetup: The great @fsibot caper

Nov 19-23: Vilnius, Lithuania

Build Stuff: talks & workshop

Nov 24: Lodz, Poland

Details TBA

Nov 25 & 26: Berlin, Germany

Berlin Alt.NET: F# for the C# developer
Berlin Alt.NET: Coding dojo: a gentle introduction to Machine Learning with F#

Nov 27: Frankfurt, Germany

Frankfurt .NET group: TBA

Dec 1 – 5: London, UK

NDC London: talks & workshop

Dec 8 & 9: Oslo, Norway

Workshop: F# via Machine Learning

F# Coding Breakfasts & Lunches: let’s code together!

Admin — Sun, 21 Sep 2014 11:40:00 -1300

If you have ever come across my blog before, it will probably come as no surprise if I tell you that I enjoy coding with F# tremendously. However, there is another reason why I enjoy F#, and that is the Community aspect. One thing we have been trying to do in San Francisco is to build a group that is inclusive, and focused on learning together.

This is why we started the coding dojos a while back: one of our members mentioned that while he was convinced from talks that F# was a good language, presentations were not quite enough to help him get over the hump and feel comfortable coding, so we started sessions completely focused on writing code in groups to solve fun problems. This has been an amazingly fun experience.

During a discussion with my sister last year, we ended up talking about gender inequality, a topic that is also dear to my heart – and, in her great wisdom, she made the following remark: scheduling a meeting at 6:00 PM is possibly the worst time you could pick for a mom. In hindsight, this is totally obvious; it also goes to show that everyone has blind spots. For that matter, it applies more broadly: choosing to go coding after work instead of going back home is not feasible for everyone. So I thought, why not try meetings in completely different time slots?

At the same time, I came across the Alt.NET Paris group (which is pretty awesome); one thing they do is run Coding Breakfasts, which they expanded into Coding Mojitos, and Coding Candies. I really liked the idea, and adapted it a bit for F# Coding Breakfast.

Here is the format we have been following so far:

If you want people to carve out a bit of time in a working day, respecting their time is crucial. So the format is strict: start on time, code in pairs for 45 minutes, show-and-tell for 15 minutes, and then, off you go!
In order to be able to code something from scratch in 45 minutes, the problem needs to be reasonably small, and accessible for beginners. We have been working initially on some of the 99 ocaml problems, and lately settled on Project Rosalind, which people seemed to find more interesting.
Some of the early feedback I got was that knowing the problems in advance would help, especially for beginners – so every time we pick and announce two problems. If people want to work on other stuff, that’s fine, too :). As an illustration, here is how the current prototypical event invite looks like.
One of the nice aspects is that the logistics requirements are virtually zero. Essentially all you need is a couple of tables, and ideally some wifi. In San Francisco, we have been meeting in a bakery. People show up around 8:15 in the morning, grab coffee and pastries, and start coding. No projector, no speaker – just open your laptop and go.
While the equipment of the venue is not that important, location matters. If you want to reach people before they go to work, it makes sense to find a place that is close to offices. In San Francisco, we are meeting downtown, close to public transportation.
I shamelessly borrowed another idea, this time from the NashFP group. They have a GitHub organization repository, which makes it possible for everyone to share their code, see what others have been doing, and potentially reuse bits of code.

So far, we have had 4 breakfasts in San Francisco, and the response has been very positive. It’s usually a smaller crowd than the evenings, but different people show up, and it has a different energy than evening sessions. Minds are still fresh (well, most minds – I have a hard time booting my brain before 9 AM), there is light outside...

Fun times tackling @ProjectRosalind problems at #fsharp breakfast this morning with @dplattsf & crew! #fb http://t.co/Y6RmTbt3bb
— Mathias Brandewinder (@brandewinder) March 12, 2014

The next step in San Francisco is to try out different time slots. After all, mornings are also not convenient for all, so this week, we will have our first F# Coding Lunch, hosted at Terrace Software (thanks Clayton!). Same general idea, but, you guessed it, 12:00 to 1:00. We’ll see how that goes!

So if you are considering starting or developing an F# community in your area, I encourage you to try that out! It is tremendously easier to setup than an evening presentation (you don’t really need a venue or a speaker), it has potential to be owned or replicated by multiple people (my dream is to see regular F# breakfasts everywhere in the Bay Area), and I suspect it would make a great way to introduce F# in a company as well…

If you have questions or comments, ping me on Twitter – I’d love to hear your thoughts or ideas!