Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
by Mathias 22. December 2015 14:43

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:

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.

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…

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!

by Mathias Brandewinder 20. December 2014 01:55

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.

Guillaume-Apollinaire-Calligramme-La_Mandoline,_l’œillet_et_le_bambou

[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!

Comments

Comment RSS