Rash thoughts about .NET, C#, F# and Dynamics NAV.

In one of my next postings I will show a algorithm, that calculates line segment intersections. As a prerequisite we need an algorithm, which calculates the intersection of two lines. In this post I will consider the following intersection of two lines in the euclidean plan:

We can write this as an equation system with two variables and two equations:

• Ax + r (Bx – Ax) = Cx + s (Dx – Cx)
• Ay + r (By – Ay) = Cy + s (Dy – Cy)

After solving this system we can calculate the intersection:

• Px = Ax + r (Bx – Ax)
• Py = Ay + r (By – Ay)

Putting this all together we can derive the following F#-code:

let calcIntersection (A:Location, B:Location, C:Location, D:Location) =
  let (Ax,Ay,Bx,By,Cx,Cy,Dx,Dy) =
     (A.XPos, A.YPos, B.XPos, B.YPos, C.XPos, C.YPos, D.XPos, D.YPos)
  let d = (Bx-Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx)  

  if  d = 0 then
    // parallel lines ==> no intersection in euclidean plane
    None
  else
    let q = (Ay-Cy)*(Dx-Cx)-(Ax-Cx)*(Dy-Cy) 
    let r = q / d
    let p = (Ay-Cy)*(Bx-Ax)-(Ax-Cx)*(By-Ay)
    let s = p / d

    if r < 0. or r > 1. or s < 0. or s > 1. then
      None // intersection is not within the line segments
    else
      Some(
        (Ax+r*(Bx-Ax)),  // Px
        (Ay+r*(By-Ay)))  // Py

Remarks:

1. If one given line degenerates into a point, then the algorithm gives no intersection.
2. If the given lines are parallel, then the algorithm gives no intersection, even if the lines have an overlap.

Heute ist es endlich soweit – Dynamics NAV 2009 steht offiziell zum Download (1.2GB) auf PartnerSource bereit. Der Download ist zwar bereits seit Samstag verfügbar, aber aus unbekannten strategischen Gründen war diese Information mal wieder "Partner Confidential" und es wurde darum gebeten nicht vor dem 19.11.2009 darüber zu bloggen. Da die Katze jetzt aber offiziell aus dem Sack ist: "Happy Downloading!" 😉

Weitere Information sind im Launch Portal zu finden.

Last time I showed how the immutable set implementation in F# can be used to get a immutable sorted list. As a result of using sets, the shown version doesn’t support repeated items. This lack can be wiped out by using an additional dictionary (immutable "Map" in F#) which stores the count of each item.

At first I define two basic helper functions for the dictionary:

module MapHelper =
  let addToMap map idx = 
    let value = Map.tryfind idx map
    match value with
      | Some(x) -> Map.add idx (x+1) map
      | None -> Map.add idx 1 map
      
  let removeFromMap map idx = 
    let value = Map.tryfind idx map
    match value with
      | Some(x) -> 
         if x > 1 then 
           Map.add idx (x-1) map 
         else 
           Map.remove idx map
      | None -> map
      
open MapHelper

Now I can adjust my sorted list implementation:

// a immutable sorted list - based on F# set
type 'a SortedFList =
 {items: Tagged.Set<'a,Collections.Generic.IComparer<'a>>;
  numbers: Map<'a,int>;
  count: int}
   
  member x.Min = x.items.MinimumElement
  member x.Items = 
    seq {
      for item in x.items do            
        for number in [1..x.GetCount item] do
          yield item}
          
  member x.Length = x.count
  member x.IsEmpty = x.items.IsEmpty
  member x.GetCount item = 
    match Map.tryfind item x.numbers with
      | None -> 0
      | Some(y) -> y
    
  static member FromList(list, sortFunction) = 
    let comparer = FComparer<'a>.Create(sortFunction)        
    let m = list |> List.fold_left addToMap Map.empty
      
    {new 'a SortedFList with 
      items = Tagged.Set<'a>.Create(comparer,list) and
      numbers = m and
      count = list.Length}
      
  static member FromListWithDefaultComparer(list) = 
    SortedFList<'a>.FromList(list,compare)    
      
  static member Empty(sortFunction) = 
    SortedFList<'a>.FromList([],sortFunction)
      
  static member EmptyWithDefaultComparer() = 
    SortedFList<'a>.Empty(compare)            
       
  member x.Add(y) =     
    {x with 
      items = x.items.Add(y);
      numbers = addToMap x.numbers y;
      count = x.count + 1} 
    
  member x.Remove(y) =     
    if x.GetCount y > 0 then
      {x with 
        items = x.items.Remove(y);
        numbers = removeFromMap x.numbers y;
        count = x.count - 1}
    else
      x        

F# supports a powerful implementation of immutable lists (see Dustin’s introduction). But for my current work I needed a sorted list and of course I wanted it the F#-way, which means immutable. I didn’t want to reinvent the wheel so I asked my question in the hubFS forum.

It turned out (thanks to Robert) that F# uses red-black trees to give a fast implementation for the immutable set. This means that a set in F# stores all elements in a balanced binary tree and searching for an element costs only O(log n). As a side effect all elements can be visited in the underlying order, which means the set implementation gives a possibility for implementing a sorted list. The only limitation is that a set usually don’t store objects more than once.

The next problem I got, was that my sorted list needs a specific ordering function. The standard F# set implementation uses structural comparison to give an order, which is not the order I need. But Laurent mentioned the Set.Make function in the F# PowerPack. This function creates a new set type for the given ordering function. The only problem with Set.Make is that it was only designed for OCaml compatibility. But with this hint I was able to put all information together and got a nice immutable sorted list implementation for F#:

// wrap orderingFunction as Collections.Generic.IComparer
type 'a FComparer =
  {compareF: 'a -> 'a -> int}
  static member Create(compareF) =
    {new 'a FComparer with compareF = compareF}
  interface Collections.Generic.IComparer<'a> with
    member x.Compare(a, b) = x.compareF a b    

// a immutable sorted list - based on F# set
type 'a SortedFList =
 {items: Tagged.Set<'a,Collections.Generic.IComparer<'a>> }
   
  member x.Min = x.items.MinimumElement
  member x.Items = seq {for item in x.items do yield item}
  member x.Length = x.items.Count
  member x.IsEmpty = x.items.IsEmpty
    
  static member FromList(list, sortFunction) = 
    let comparer = FComparer<'a>.Create(sortFunction)
    {new 'a SortedFList with 
      items = Tagged.Set<'a>.Create(comparer,list)}
      
  static member FromListWithDefaultComparer(list) = 
    SortedFList<'a>.FromList(list,compare)    
      
  static member Empty(sortFunction) = 
    SortedFList<'a>.FromList([],sortFunction)
      
  static member EmptyWithDefaultComparer() = 
    SortedFList<'a>.Empty(compare)            
       
  member x.Add(y) =     
    {x with items = x.items.Add(y)}    

  member x.Remove(y) =     
    {x with items = x.items.Remove(y)}    

Please note that this implementation stores every item only once. Next time I will show a version which allows to store repeated items.

In the first part of this series I showed a naïve algorithm for the Damerau-Levenshtein distance which needs O(m*n) space. In the last post I improved the algorithm to use only O(m+n) space. This time I will show a more functional implementation which uses only immutable F#-Lists and works still in O(m+n) space. This version doesn’t need any mutable data.

/// Calcs the damerau levenshtein distance.    
let calcDL (a:'a array) (b: 'a array) =       
  let n = a.Length + 1
  let m = b.Length + 1
  
  let processCell i j act l1 l2 ll1 =
    let cost = 
      if a.[i-1] = b.[j-1] then 0 else 1
    let deletion = l2 + 1
    let insertion = act + 1
    let substitution = l1 + cost
    let min1 =  
      deletion 
      |> min insertion 
      |> min substitution

    if i > 1 && j > 1 &&
      a.[i-1] = b.[j-2] && a.[i-2] = b.[j-1] then
        min min1 <| ll1 + cost
    else
      min1
  
  let processLine i lastL lastLastL =
    let processNext (actL,lastL,lastLastL) j =
      match actL with 
        | act::actRest -> 
          match lastL with
            | l1::l2::lastRest -> 
              if i > 1 && j > 1 then
                match lastLastL with
                  | ll1::lastLastRest -> 
                    (processCell i j act l1 l2 ll1 :: actL,
                     l2::lastRest,
                     lastLastRest)
                  | _ -> failwith "can't be"
              else
                (processCell i j act l1 l2 0 :: actL,
                 l2::lastRest,
                 lastLastL)                 
            | _ -> failwith "can't be"
        | [] -> failwith "can't be"
      
    let (act,last,lastLast) =
      [1..b.Length]
        |> List.fold_left processNext ([i],lastL,lastLastL)
    act |> List.rev
    
  let (lastLine,lastLastLine) =               
    [1..a.Length]
      |> List.fold_left
          (fun (lastL,lastLastL) i -> 
             (processLine i lastL lastLastL,lastL))
          ([0..m-1],[])
              
  lastLine.[b.Length]    
 
let damerauLevenshtein(a:'a array) (b:'a array) =
  if a.Length > b.Length then
    calcDL a b
  else
    calcDL b a

I admit the code is still a little messy but it works fine. Maybe I will find the time to cleanup a bit and post a final version.

Last time I showed a naïve implementation of the Damerau-Levenshtein-Distance in F# that needs O(m*n) space. This is really bad if we want to compute the edit distance of large sequences (e.g. DNA sequences). If we look at the algorithm we can easily see that only the last two lines of the (n*m)-matrix are used. This observation leads to a improvement where we compute the distance with only 3 additional arrays of size min(n,m).

/// Calcs the damerau levenshtein distance.    
let calcDL (a:'a array) (b: 'a array) =       
  let n = a.Length + 1
  let m = b.Length + 1
  let lastLine = ref (Array.init m (fun i -> i))
  let lastLastLine = ref (Array.create m 0)
  let actLine = ref (Array.create m 0)
    
  for i in [1..a.Length] do
    (!actLine).[0] <- i      
    for j in [1..b.Length] do          
      let cost = 
        if a.[i-1] = b.[j-1] then 0 else 1
      let deletion = (!lastLine).[j] + 1
      let insertion = (!actLine).[j-1] + 1
      let substitution = (!lastLine).[j-1] + cost
      (!actLine).[j] <- 
        deletion 
        |> min insertion 
        |> min substitution

      if i > 1 && j > 1 then
        if a.[i-1] = b.[j-2] && a.[i-2] = b.[j-1] then
          let transposition = (!lastLastLine).[j-2] + cost  
          (!actLine).[j] <- min (!actLine).[j] transposition
    
    // swap lines
    let temp = !lastLastLine
    lastLastLine := !lastLine
    lastLine := !actLine
    actLine := temp
            
  (!lastLine).[b.Length]

 
let damerauLevenshtein(a:'a array) (b:'a array) =
  if a.Length > b.Length then
    calcDL a b
  else
    calcDL b a

This version of the algorithm needs only O(n+m) space but is not really "functional" style. I will show a more "F#-stylish" version in part III.

Today I am publishing an algorithm for calculating the Damerau-Levenshtein distance in F#. The Levenshtein distance is a metric that allows to measure the amount of difference between two sequences and shows how many edit operations (insert, delete, substitution) are needed to transform one sequence into the other. The Damerau-Levenshtein distance allows the transposition of two characters as an operation. It is often used for spelling corrections or to measure the variation (“edit distance”) between DNA sequences.

let damerauLevenshtein(a:'a array) (b:'a array) =       

  let init i j =

    if j = 0 then i

    elif i = 0 then j else 0

  let n = a.Length + 1

  let m = b.Length + 1

  let d = Array2.init n m init

  for i in [1..a.Length] do

    for j in [1..b.Length] do          

      let cost = 

        if a.[i-1] = b.[j-1] then 0 else 1

      let deletion = d.[i-1, j] + 1

      let insertion = d.[i,j-1] + 1

      let substitution = d.[i-1,j-1] + cost

      d.[i, j] <- 

        deletion 

        |> min insertion 

        |> min substitution

      if i > 1 && j > 1 && a.[i-1] = b.[j-2] && 

           a.[i-2] = b.[j-1] then

        let transposition = d.[i-2,j-2] + cost  

        d.[i, j] <- min d.[i,j] transposition  

  d.[a.Length, b.Length]  

This naïve implementation needs quadratic space (O(m*n)). Since the algorithm is used to calculate the edit distance of large DNA sequences this is extremly bad. Next time I will show how we can get linear space (O(m+n)) for the algorithm.

Last time I showed how it is possible to use parallel map and fold functions to compute the sum of all factorials between 1 and 3000. The result was a nearly perfect load balancing for this task on a two processor machine. This time I will derive a generic function that computes partial results in parallel and folds them to a final result.

Let’s consider our F# example:

let add a b = a + b  

let fac (x:bigint) = 

  [1I..x] |> List.fold_left (*) 1I

let sequential() =

  [1I..3000I]

   |> List.map fac

   |> List.fold_left add 0I

This is the same as:

let calcFactorialSum min max =

  [min..max] 

   |> List.map fac

   |> List.fold_left add 0I  

let f1() = calcFactorialSum    1I 2000I

let f2() = calcFactorialSum 2001I 2200I

let f3() = calcFactorialSum 2201I 2400I

let f4() = calcFactorialSum 2401I 2600I

let f5() = calcFactorialSum 2601I 2800I

let f6() = calcFactorialSum 2801I 3000I

let sequential2() =

  f1() + f2() + f3() + f4() + f5() + f6()

We spitted the summation into 6 independent tasks and computed the sum of the partial results. This has nearly no bearing on the runtime.

But with the help of PLINQ we can compute each task in parallel:

let asParallel (list: 'a list) = 

  list.AsParallel<'a>()

let runParallel functions = 

    ParallelEnumerable.Select(

      asParallel functions, (fun f ->  f() ) )

let pFold foldF seed (data:IParallelEnumerable<'a>)=

  ParallelEnumerable.Aggregate<'a,'b>(

    data, seed, new Func<'b,'a,'b>(foldF))

let calcFactorialsParallel() =

  [f1; f2; f3; f4; f5; f6]

    |> runParallel

    |> pFold add 0I

This time we build a list of functions (f1, f2, f3, f4, f5, f6) and run them in parallel. "runParallel” gives us back a list of the partial results, which we can fold with the function “add” to get the final result.

On my Core 2 Duo E6550 with 2.33 GHz and 3.5 GB RAM I get the following results:

Time Normal: 26.576s

Time Sequential2: 26.205s (Ratio: 0.99)

Time “Parallel Functions”: 18.426s (Ratio: 0.69)

Time PLINQ: 14.990s (Ratio: 0.56) (Last post)

Same Results: true

We can see that the parallel computation of the functions f1 – f6 is much faster than the sequential.

But why is the PLINQ-version (see last post) still faster? We can easily see that each partial function needs a different runtime (e.g. it’s much harder to calculate the factorials between 2800 and 3000 than between 2000 and 2200). On my machine I get:

Time F1: 8.738s

Time F2: 2.663s

Time F3: 3.119s

Time F4: 3.492s

Time F5: 3.889s

Time F6: 4.442s

The problem is that the Parallel Framework can only guess each runtime amount in advance. So the load balancing for 2 processors will not be optimal in every case. In the original PLINQ-version there are only small tasks, and the difference between each runtime is smaller. So it is easier to compute the load balancing.

But of course we can do better if we split f1 into two functions f7 and f8:

let f7() = calcFactorialSum    1I 1500I

let f8() = calcFactorialSum 1501I 2000I

So we can get a better load balancing:

Time F1: 8.721s

Time F7: 4.753s

Time F8: 4.829s

Time Normal: 26.137s

Time “Parallel Functions”: 16.138s (Ratio: 0.62)

Same Results: true

If your wondering how Google computes query results in such a short time you have to read the famous “MapReduce”-Paper by Jeffrey Dean and Sanjay Ghemawat (2004). It shows how one can split large tasks into a mapping and a reduce step which could then be processed in parallel.

With PLINQ (part of the Parallel Extensions to the .NET Framework) you can easily use “MapReduce”-pattern in .NET and especially F#. PLINQ will take care of all the MultiThreading and load balancing stuff. You only have to give PLINQ a map and a reduce (or fold) function.

Lets consider a small example. Someone wants to compute the sum of the factorials of all integers from 1 to 3000. With List.map and List.fold_left this is a very easy task in F#:

#light

open System

let add a b = a + b

let fac (x:bigint) = [1I..x] |> List.fold_left (*) 1I

let sum =

  [1I..3000I]

    |> List.map fac

    |> List.fold_left add 0I

printfn "Sum of Factorials: %A" sum

Of course you could do much much better if you don’t compute every factorial on its own (I will show this in one of the next parts) – but for this time I need an easy function that is time consuming.

This simple Task needs 27 sec. on my Core 2 Duo E6550 with 2.33 GHz and 3.5 GB RAM.

But we can do better if we use parallel map and fold functions with help of PLINQ:

let pMap (mapF:'a -> 'b) (data:IParallelEnumerable<'a>) =

  ParallelEnumerable.Select(data, mapF)

let pFold foldF seed (data:IParallelEnumerable<'a>)=

  ParallelEnumerable.Aggregate<'a,'b>(

    data, seed, new Func<'b,'a,'b>(foldF))

Now we can easily transform our calculation to a parallel version:

let sum =

  [1I..3000I].AsParallel<bigint>()

    |> pMap fac 

    |> pFold add 0I

Putting all together we can write a small test application:

#light 

open System

open System.Linq

open System.Diagnostics

let testRuntime f =

  let watch = new Stopwatch()

  watch.Start()

  (f(),watch.Elapsed)

let add a b = a + b

let fac (x:bigint) = [1I..x] |> List.fold_left (*) 1I

let list = [1I..3000I]

let pMap (mapF:'a -> 'b) (data:IParallelEnumerable<'a>)=

  ParallelEnumerable.Select(data, mapF)

let pFold foldF seed (data:IParallelEnumerable<'a>)=

  ParallelEnumerable.Aggregate<'a,'b>(

    data, seed, new Func<'b,'a,'b>(foldF))

let PLINQ() =

  list.AsParallel<bigint>()

    |> pMap fac

    |> pFold add 0I

let sequential() =

  list

   |> List.map fac

   |> List.fold_left add 0I

let (sumSequential,timeSequential) =

  testRuntime sequential

printfn "Time Normal: %.3fs" timeSequential.TotalSeconds

let (sumPLINQ,timePLINQ) =

  testRuntime PLINQ

printfn "Time PLINQ: %.3fs" timePLINQ.TotalSeconds

timePLINQ.TotalSeconds / timeSequential.TotalSeconds

  |> printfn "Ratio: %.2f"

sumSequential = sumPLINQ

  |> printfn "Same Results: %A"

On my machine I get the following results:

Time Normal: 27.955s

Time PLINQ: 15.505s

Ratio: 0.55

Same Results: true

This means I get nearly a perfect load balancing on my two processors for this task.

In part II I describe how one can compute a series of functions in parallel.

Claus Lundstrøm zeigt in einem schönen Blogpost wie man in NAV2009 den Code auf Seite der ServiceTier (also auch remote) debuggen kann – und zwar über Visual Studio 2008 direkt im generierten C#-Code. Mit dieser Variante ist man nicht mehr gezwungen das Debugging über den Classic-Client zu tun, sondern kann direkt aus dem Dynamics NAV RoleTailored-Client debuggen.

Dummerweise ist der generierte C#-Code, wie das bei generiertem Code eigentlich immer der Fall ist, nicht gerade “optisch schöner” C#-Style und hat auch nur noch wenig mit dem Original-C/AL-Code zu tun – ist aber immerhin lesbar.

Das ist ein wirklich interessanter Ansatz und erlaubt mit etwas Geschick auch UnitTesting für NAV 2009. Dafür werde ich demnächst mal versuchen ein kleines Beispiel zu bloggen.