Archive

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 test.il [/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
    stloc.0
    // n = i
    ldarg.0
    stloc.1   
    // while (n <= j)
repeat_outer:   
    ldloc.1
    ldarg.1
    bgt done   
    // n’ = n
    ldloc.1
    stloc.2   
    // c = 1
    ldc.i4 1
    stloc.3    
    // while (n’ <> 1)
repeat_inner:   
    ldc.i4 1
    ldloc.2
    beq end_inner
    // c++
    ldc.i4 1
    ldloc.3
    add
    stloc.3
    // if n’%2 = 0
    ldloc.2
    ldc.i4 2
    rem
    ldc.i4 0
    beq case_even   
    // n’ = 3*n+1
    ldloc.2
    ldc.i4 3
    mul
    ldc.i4 1
    add
    stloc.2
    br repeat_inner
case_even:   
    // n’ = n’/2
    ldloc.2
    ldc.i4 2
    div
    stloc.2   
    br repeat_inner
end_inner:
    // n++
    ldloc.1
    ldc.i4 1
    add
    stloc.1
    // if c > maxlen
    ldloc.3
    ldloc.0
    ble repeat_outer
    ldloc.3
    stloc.0
    br repeat_outer
done:
    ldloc.0
    ret
}

Here is the entire program on skydrive:

https://skydrive.live.com/embedicon.aspx/.Public/test.il?cid=b46559fe42938868&sc=documents

Enjoy.

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 } |> Seq.map 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

    maxLen

 

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)

{

    __asm

    {

        xor    eax, eax    ; maxLen = 0

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

repeat_for:       

        cmp ecx, j

        jg    done       

        push eax

        mov ebx, 1        ; c = 1

        mov edx, ecx    ; np = n

repeat_while:       

        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

case_even:

        mov edx, eax    ; np = np / 2

        jmp repeat_while

term_loop:

        pop    eax

        inc ecx            ; [n++]

        cmp    ebx, eax     ; if c > maxlen

        jle repeat_for

        mov eax, ebx    ; c = maxlen

        jmp repeat_for

done:

    }

}

 

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:

NeonFlamesApp

Source code on skydrive:

https://skydrive.live.com/embedicon.aspx/.Public/NeonFlamesRepo.zip?cid=b46559fe42938868&sc=documents

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> =

            map.[value]

 

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

            if map.ContainsKey(value) |> not then

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

            map.[value].Add(i)

 

        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) |> Seq.map (fun i -> entries.[i])       

 

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

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

 

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

            assert(Option.isNone e.id)

            e.id <- Some(Guid.NewGuid())

            let i = entries.Count

            entries.Add(e)

            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 =

            assert(Option.isSome e.id)

            let i = this.IndexOf(e)

            let ilast = entries.Count-1

            let elast = entries.[ilast]

            entries.[i] <- elast

            entries.RemoveAt(ilast);

            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 |> Seq.map (fun i -> entries.[i])

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

 

        member private this.IndexOf(template : Entry) =       

            assert(Option.isSome template.id)

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

 

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>

                index.Add(v,i)

            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

                result.Create(e)

            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)) |> List.map (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

                phoneBook.FindByFirstName(e.firstName)

            else

                phoneBook.FindByLastName(e.lastName)

            |>

            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”

        phoneBook.Save(fileName)

        let phoneBook’ = PhoneBook.Load(fileName)

        Seq.zip (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

            phoneBook.Create(e)

        for deleteFlag, e in entries do

            if deleteFlag then

                phoneBook.Delete(e)

        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,_) -> e.id <- Option.None) entries

        let phoneBook = new PhoneBook()

        for e, e’ in entries do

            phoneBook.Create(e)

            e’.id <- e.id

            phoneBook.Update(e’)

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

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

        Seq.zip 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

 

 

PhoneBookLibraryTest.runTests

 

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))

    {

        result.push_back(vector<T>());

        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;

}

 

Usage:

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.

vskrasch

Darn.

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;

 

    is.unsetf(ios_base::skipws);

 

    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)

        {

            result.push_back(vector<T>());

            newLine = false;

        }

 

        if (*token == “\n”)

            newLine = true;

        else

            result.back().push_back(lexical_cast<T>(trim_copy(*token)));

    };

 

    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