Archive for October, 2011

IL Code

.Net languages compile to IL code which stands for Intermediate Language which corresponds to java byte code in the java world. An informative introduction to IL can be found here. An IL file can be compiled to an executable using ILAsm.exe; i.e.

ILAsm.exe [/debug]

All programs that passes ILAsm are not runnable though and may cause an InvalidProgramException to be thrown. If this is the case running

PEVerify test.exe

might return useful information about the actual problem. More information about PEVerify can be found here. When your program is up and running you can attach to the process and debug it using visual studio just like any other program, assuming you passed /debug to ILAsm.exe.

Ok, now that we got the foundations the natural question to ask (doh) is how the previous entry might look like when hand coded in IL. Here it is:

.method static int32 solve(int32, int32) cil managed
    .maxstack 10   
    .locals init (int32, int32, int32, int32)  // maxLen, n, n’, c
    // maxLen = 0
    ldc.i4 0
    // n = i
    // while (n <= j)
    bgt done   
    // n’ = n
    // c = 1
    ldc.i4 1
    // while (n’ <> 1)
    ldc.i4 1
    beq end_inner
    // c++
    ldc.i4 1
    // if n’%2 = 0
    ldc.i4 2
    ldc.i4 0
    beq case_even   
    // n’ = 3*n+1
    ldc.i4 3
    ldc.i4 1
    br repeat_inner
    // n’ = n’/2
    ldc.i4 2
    br repeat_inner
    // n++
    ldc.i4 1
    // if c > maxlen
    ble repeat_outer
    br repeat_outer

Here is the entire program on skydrive:


Categories: Uncategorized

The 3n+1 problem–the hard way

A sample problem from the book Programming challenges is published here and it has been named The 3n+1 problem. It does not take a great effort to come up with a solution; in F# it might look like:

let threeNPlusOne = Seq.unfold (fun n -> let n’ = if n%2=0 then n/2 else n*3+1 in Some(n,n’))


let cycleLength n = 1 + n |> threeNPlusOne |> Seq.takeWhile ((<>) 1) |> Seq.length


let solve i j = seq { i..j } |> cycleLength |> Seq.max


Or maybe, using a more imperative style, it might look like:

let solve i j =

    let mutable maxLen = 0

    for n in i..j do

        let mutable n’ = n

        let mutable c = 1

        while n’ <> 1 do

            n’ <- if n’%2=0 then n’/2 else n’*3+1

            c <- c + 1

        if c > maxLen then

            maxLen <- c



Ok, that was fun for a little while but not a real challenge. Rewriting the solution in assembler makes it more interesting:

int solve(int i, int j)




        xor    eax, eax    ; maxLen = 0

        mov ecx, i      ; for n = i..j


        cmp ecx, j

        jg    done       

        push eax

        mov ebx, 1        ; c = 1

        mov edx, ecx    ; np = n


        cmp edx, 1

        je  term_loop   ; while (np <> 1)

        inc    ebx            ; c++

        mov eax, edx

        shr eax, 1

        jnc case_even

        mov eax, edx    ; np = np * 3 + 1

        shl edx, 1

        add edx, eax

        inc edx

        jmp repeat_while


        mov edx, eax    ; np = np / 2

        jmp repeat_while


        pop    eax

        inc ecx            ; [n++]

        cmp    ebx, eax     ; if c > maxlen

        jle repeat_for

        mov eax, ebx    ; c = maxlen

        jmp repeat_for





Erhmm. That’s all for today. Good night. Smile

Categories: Uncategorized

Neon flames ported to F# and WPF

I found this extremely cool chrome experiment by Jonas Wagner the other day. When looking at the code it seemed pretty simple (yet clever) and I decided to port it to F# in order to learn the details. Here is the result:


Source code on skydrive:

Categories: Uncategorized

FsCheck–Unit testing in F#

October 5, 2011 1 comment

Ayende posted another hiring question; here and here. Ignoring the fact that I think that this is too big a task for such an occasion I sat down and tried to come up with a solution. To keep things short and clear I picked F# as the language of my choice. Hold on; here comes the phone book library, all in one piece:

module PhoneBookLibrary =

    open System

    open System.Collections.Generic

    open System.IO

    open System.Runtime.Serialization.Formatters.Binary


    type PhoneType = Work | Cellphone | Home


    type Entry = { mutable id : option<Guid>; firstName : string; lastName : string; phone : option<PhoneType>; number : option<string> }


    type EnumerationMethod = FirstName | LastName


    type Index<‘a>() =

        let map = new SortedDictionary<‘a,List<int>>()


        member this.Lookup(value : ‘a) : List<int> =



        member this.Add(value : ‘a, i : int) : unit =

            if map.ContainsKey(value) |> not then

                map.[value] <- new List<int>()



        member this.Remove(value : ‘a, i: int) : unit =

            map.[value].Remove(i) |> ignore


        member this.Values

            with get() : seq<int> =                        

                seq {

                    for v in map.Values do

                        for i in v do

                            yield i



    type PhoneBook() =       

        let entries = new List<Entry>()

        let indexByFirstName = new Index<string>()

        let indexByLastName = new Index<string>()


        static member Load(fileName : string) : PhoneBook =

            let formatter = new BinaryFormatter()

            use stream = new FileStream(fileName, FileMode.Open)

            formatter.Deserialize(stream) :?> PhoneBook


        member this.Save(fileName : string) : unit =

            let formatter = new BinaryFormatter()

            use stream = new FileStream(fileName, FileMode.Create)

            formatter.Serialize(stream, this)


        member this.FindByFirstName(firstName : string) : seq<Entry> =

            indexByFirstName.Lookup(firstName) |> (fun i -> entries.[i])       


        member this.FindByLastName(lastName : string) : seq<Entry> =

            indexByLastName.Lookup(lastName) |> (fun i -> entries.[i])       


        member this.Create (e : Entry) : unit =        


   <- Some(Guid.NewGuid())

            let i = entries.Count


            indexByFirstName.Add(e.firstName, i)

            indexByLastName.Add(e.lastName, i)


        member this.Update (e’ : Entry) : unit =

            assert(Option.isSome e’.id)

            let i = this.IndexOf(e’)

            let e = entries.[i]

            entries.[i] <- e’

            if e’.firstName <> e.firstName then

                indexByFirstName.Remove(e.firstName, i)

                indexByFirstName.Add(e’.firstName, i)           

            if e’.lastName <> e.lastName then

                indexByLastName.Remove(e.lastName, i)

                indexByLastName.Add(e’.lastName, i)


        member this.Delete (e : Entry) : unit =


            let i = this.IndexOf(e)

            let ilast = entries.Count-1

            let elast = entries.[ilast]

            entries.[i] <- elast


            indexByFirstName.Remove(e.firstName, i)             

            indexByLastName.Remove(e.lastName, i)

            if i <> ilast then

                indexByFirstName.Remove(elast.firstName, ilast)             

                indexByLastName.Remove(elast.lastName, ilast)

                indexByFirstName.Add(elast.firstName, i)             

                indexByLastName.Add(elast.lastName, i)


        member this.Enumerate (em : EnumerationMethod) : seq<Entry> =

            match em with

            | FirstName -> indexByFirstName.Values |> (fun i -> entries.[i])

            | LastName -> indexByLastName.Values |> (fun i -> entries.[i])


        member private this.IndexOf(template : Entry) =       


            entries.FindIndex(new Predicate<Entry>(fun x -> =       


Oups. Sorry for that. Anyway, I needed to test my code and I hade a look at FsCheck and I was really impressed. Look at this:

module PhoneBookLibraryTest =

    open PhoneBookLibrary

    open FsCheck


    let generateIndex<‘a> =

        gen {

            let index = new Index<‘a>()

            let! count = Gen.choose(0, 10)

            for i in 1..count do

                let! v, i = Arb.generate<‘a*int>


            return index



    let generateEntry =

        gen {

            let! fn = Gen.elements [ “Daniel”; “Anders”; “Roy”; “Bertil” ]

            let! ln = Gen.elements [ “Svensson”; “Andersson”; “Fredriksson”; “Abrahamsson”; “Patriksson” ];

            let! t = Gen.elements [ None; Some(Work); Some(Cellphone); Some(Home)];

            let! no = Gen.elements [  None; Some(“12346”); Some(“12347”); Some(“12348”); Some(“12349”)];

            return { id = Option.None; firstName = fn; lastName = ln; phone = t; number = no }



    let generatePhoneBook =

        gen {

            let! numEntries = Gen.choose (0, 100)

            let result = new PhoneBook()

            for i in 1..numEntries do

                let! e = generateEntry


            return result



    let generateEnumerationMethod = Gen.elements [ EnumerationMethod.FirstName; EnumerationMethod.LastName ]


    type CustomGenerators =

        static member PhoneBook() = Arb.fromGen generatePhoneBook   

        static member EnumerationMethod() = Arb.fromGen generateEnumerationMethod

        static member Entry() = Arb.fromGen generateEntry

        static member Index() = Arb.fromGen generateIndex


    Arb.register<CustomGenerators>() |> ignore


    // Index.Add, Index.Lookup

    let valuesInIndexCanBeFound (values : list<string*int>) =

        let index = new Index<string>()

        for v, i in values do

            index.Add(v, i)

        values |>

        Seq.forall (fun (v,i) -> index.Lookup(v).IndexOf(i) >= 0)


    // Index.Remove

    let valuesCanBeRemovedFromIndex (values : list<string*int*bool>) =

        let index = new Index<string>()

        for v, i, _ in values do

            index.Add(v, i)

        for v, i, deleteFlag in values do

            if deleteFlag then

                index.Remove(v, i)

        let existingValues = index.Values |> Seq.toList |> List.sort

        let expectedValues = values |> List.filter (fun (_,_,x) -> not(x)) |> (fun (_,i,_) -> i) |> List.sort

        assert(existingValues = expectedValues)

        existingValues = expectedValues


    // Index.Values

    let indexValuesAreSorted (index : Index<string>) = true // todo


    // PhoneBook.FindByFirstName, PhoneBook.FindByLastName

    let everyEntryCanBeBeFoundByFirstNameOrLastName (phoneBook : PhoneBook) (enumerationMethod : EnumerationMethod) (useFirstName : bool) =

        let exists e =

            if useFirstName then





            Seq.exists (fun x -> x = e)

        phoneBook.Enumerate(enumerationMethod) |>

        Seq.forall exists


    // PhoneBook.Enumerate

    let enumerationOfAPhoneBookIsOrdered (phoneBook : PhoneBook) (enumerationMethod : EnumerationMethod) =

        let entries = phoneBook.Enumerate(enumerationMethod)

        let compare =

            match enumerationMethod with

            | EnumerationMethod.FirstName -> (fun (e1,e2) -> e1.firstName <= e2.firstName)

            | EnumerationMethod.LastName ->(fun (e1,e2) -> e1.lastName <= e2.lastName)

        entries |>

        Seq.pairwise |>   

        Seq.forall compare


    // PhoneBook.Save, PhoneBook.Load

    let aSavedPhoneBookShouldLoadToAnEquivalentObject (phoneBook : PhoneBook) =

        let fileName = “c:\\temp\\phonebook.bin”


        let phoneBook’ = PhoneBook.Load(fileName) (phoneBook.Enumerate EnumerationMethod.FirstName) (phoneBook’.Enumerate EnumerationMethod.FirstName) |>

        Seq.forall (fun (e1,e2) -> e1 = e2)


    // PhoneBook.Create, PhoneBook.Delete

    let entriesCanBeDeleted (entries : list<bool*Entry>) =

        let phoneBook = new PhoneBook()

        for _, e in entries do


        for deleteFlag, e in entries do

            if deleteFlag then


        let numExistingEntries = Seq.length (phoneBook.Enumerate EnumerationMethod.FirstName)

        let numNonDeletedEntries = entries |> Seq.filter (fst>>not) |> Seq.length

        numExistingEntries = numNonDeletedEntries


    // PhoneBook.Create, PhoneBook.Update

    let entriesCanBeUpdated (entries : list<Entry*Entry>) =

        List.iter (fun (e,_) -> <- Option.None) entries

        let phoneBook = new PhoneBook()

        for e, e’ in entries do


            e’.id <-


        let updatedEntries = phoneBook.Enumerate EnumerationMethod.FirstName |> Seq.toList

        let targetEntries = entries |> snd |> List.sortBy (fun x -> x.firstName) updatedEntries targetEntries |>

        Seq.forall (fun (e1, e2) -> e1 = e2)


    let runTests =

        // Index

        Check.Quick valuesInIndexCanBeFound

        Check.Quick valuesCanBeRemovedFromIndex

        Check.Quick indexValuesAreSorted

        // Phonebook

        Check.Quick everyEntryCanBeBeFoundByFirstNameOrLastName

        Check.Quick enumerationOfAPhoneBookIsOrdered

        Check.Quick aSavedPhoneBookShouldLoadToAnEquivalentObject

        Check.Quick entriesCanBeDeleted

        Check.Quick entriesCanBeUpdated





Go try it out! The library is also available as a nuget package.

Categories: Uncategorized

C++ CSV parser – Reaching for perfection

Digging down into split_iterators and failing to combine these with istream_iterators I took one step back and ended up with a piece of code that I think is both clear and efficient. Look at this:

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <boost/lexical_cast.hpp>

#include <boost/algorithm/string.hpp>


template<class T>

std::vector<std::vector<T>> ParseCsv(std::istream& is)


    using namespace std;

    using namespace boost;

    typedef iterator_range<string::iterator> range_t;


    vector<vector<T>> result;

    string row;

    while(getline(is, row))



        vector<range_t> values;

        split(values, row, is_any_of(","), token_compress_on);

        transform(values.begin(), values.end(), back_inserter(result.back()), [](range_t& r) {

            return boost::lexical_cast<T>(std::string(r.begin(), r.end()));




    return result;




vector<vector<int>> result = ParseCsv<int>(ifstream("test.csv"));


Nice. Seems like boost is essential nowadays for C++ programming. Can’t live without it.

Categories: Uncategorized

Clean, typesafe, efficient and … internal compiler error?

I tried to push my CSV parser even further but I just ran out of luck.



Categories: Uncategorized

More on CSV parsers in C++

October 2, 2011 2 comments

I was watching Herb Sutter talking about the new C++ the other day. The video was from the Windows build conference and the talk was really good by the way. Anyway, Herb claims that modern C++ is clean, type safe and efficient. This got me thinking about my CSV parsers which I was not really happy with. My main concern is clarity but not without sacrificing too much efficiency.

I started playing around with the boost tokenizer trying to get more out of it. After a while I also re-discovered the lexical_cast from the boost library which provides a short and clean way to convert strings to integers or doubles. Combining this with the stream iterators this was my result:

#include <iostream>

#include <string>

#include <fstream>

#include <boost/tokenizer.hpp>

#include <boost/lexical_cast.hpp>

#include <boost/algorithm/string.hpp>


template<class T>

std::vector<std::vector<T>> ParseCsv(std::istream& is)


    using namespace std;

    using namespace boost;

    typedef istream_iterator<char> iterator;

    typedef char_separator<char> separator;

    typedef tokenizer<separator, iterator, string> Tokenizer;




    vector<vector<T>> result;

    Tokenizer tokens(iterator(is), iterator(), separator(“,”, “\n”));   

    bool newLine = true;   

    for(auto token = tokens.begin(); token != tokens.end(); ++token)


        if (newLine)



            newLine = false;



        if (*token == “\n”)

            newLine = true;





    return result;



Usage is simple:


vector<vector<int>> result = ParseCsv<int>(ifstream(“test.csv”));


I think I like this one better than my previous attempts; assuming though that boost is available.

Categories: Uncategorized