Robert Pickering's Strange Blog

Last night our alt.net Paris meeting was lucky enough to be visited by JB Evain a veteran of the Mono team. The evening was hosted by Valtech who were kind enough to provide us with a room and a generous supply of pizza. Here’s a little summary of what we learned:

The mono team is composed of about 35 core members on the Novell payroll, as well as volunteers from the community. JB’s entre into the team is a fairly typical story; he worked on various open source projects, before becoming involved with the Mono project as volunteer he took part in a couple of summer of code projects which eventually got him into a full time roll on the project. The team is entirely distributed, JB normally lives and works in Lyon and does not see the other team members in the course of normal working week, thought there big Skype users.

The Mono team has released Mono 2.0 a couple of weeks ago, this includes a suit of Microsoft compatible libraries (things like a complete implementation of Winforms 2.0 , ASP.NET 2.0 and LINQ) and also a set of API that are native to mono (such as the Gtk# library). It is also packaged with a number of third party libraries; these are mainly data access providers. They have an implementation of the C# 3.0 compiler, VB 8.0 and an IL assembler.

We discussed how the Mono project chose what Microsoft libraries to port to Mono. They can’t do everything so their chose has to strategic. It’s mainly guided by a useful little tool called MOMA which analyze assemblies tell you whether they will run on the mono platform, it also feeds back to the Mono team, anonymously, which libraries they need to be ported to allow incompatible app to run on the Mono platform. On top of this they also listen a lot to customer feedback, based on this they’ll probably attempt a port of WCF but not WPF, Mono is more used for server side stuff and already has two good GUI libraries, there’s little demand for another one.

While it’s nice to have a set of Microsoft compatible libraries, the real invitation of the Mono project is the other stuff that it provides. Mono.Security is one small example, where there where things the Mono team considered where missing from Microsoft .NET. Another is better example is Mono.Cecil, a library for parsing and manipulating IL, we talked a lot about this since it was JB who started this project. The really difference between this and Reflection.Emit it that it is designed so that assemblies are not loaded into the AppDomain, a huge advantage if you want to be able to unloaded an assembly or rewrite it. There are some very interesting projects using this library, including the Mono linker and one of which we had a preview and will be announced very soon.

One interesting demo we saw was the C# top-level (REPL) that the Mono team are currently working and should be part of Mono 2.2. It interesting because Microsoft is currently also working on a C# top-level but it will ship as part of .NET 5.0, which of course has no official release date but the best guesstimate is sometime around 2012. The mono team will be able to release their top-level so much earlier than Microsoft because there C# compiler was implemented in C# from the start, were as Microsoft C# is implemented in C++ and is currently being ported to manage code.

Their development methodology, for the Microsoft compatible libraries at least, is to create a suit of NUnit tests against the Microsoft libraries (JB claims they are the world biggest NUnit user). Then when there satisfied they a complete test suite and understand the library well they start implementation of the compatible library. They know it’s done when all the tests pass. There build test environment is almost entirely virtualised (apparently there’s still a few environments that resist virtualisation) and hosted in Novell HQ in America.

Some of Mono existing users use Mono just because they want .NET but they want a version that runs on Linux and Mac. However there are some more interesting use cases, there’s quite a lot of mobile development going on at the moment, Microsoft offer’s a cut down version of the .NET framework called the compact framework to support this, Mono has no compact framework, but its assemblies run on the compact framework. So, some users use the mono Microsoft compatible libraries to replace the bits missing from the compact framework, some even go as far as compiling new assemblies with just the bits they need to avoid bloat of their mobile applications. Another interesting use case is the gaming industry. The gaming industry has huge investment in graphics/physics engines, all written C++. Here generally happy with these want to keep and maintain them, however they don’t want to program higher level features such as character behaviour in C++. Traditionally they’ve been big users of Python and Lua for this but there both relatively slow, however there are people now starting to look at Mono for this, as its languages are JITed to native code so generally have quite good perf. The advantage mono has over Microsoft .NET here is that they can recompile it and link it into their existing graphics/physics engines. They then have the choice of all the .NET languages to write higher level functionality in. I could see F# becoming very popular for this, given that it’s already becoming a popular choice for AI work, Microsoft Applied Games Group are big F# fans.

Anyway, after the main presentation we retired a local bar for drinks and more chatting. Here’s a few photos from the evening.

The next alt.net meeting is on December 2^nd, 19:30 at the Microsoft building at 148 rue de l’université.

To coincide with the release the CTP release of F# Microsoft also released and early version “Solver Foundation”. Don Box described himself as being elated by its release. You can tell it’s an early version as it’s currently the only way to get it is part of “F# Optimization Modelling Language” sample on the MSDN code gallery.

So what does optimization mean in this context? Simply put an optimization problem is the problem of finding the best solution from all feasible solutions. Or (slightly) more formally:

Given a function “f” which takes a value from set “A” and transforms it to a real number, find the element “x0” in set “A” which “f(x0)” is smaller (or greater) than “f(x)” where “x” is all other values in A.

Many problems from physics and mathematics can be modelled using this simple framework and much mathematical research has gone into finding the solution efficiently. For example the travelling salesman can be considered an optimization problem, our function “f” (often referred to as the cost function) is the cost of travelling between the nodes in the chosen order. Our set “A” is the set of all possible routes between the nodes. So it is an optimization problem because we are looking for the element in the set of all possible routes which makes our function “f” – the cost function – return the best (smallest/cheapest) value. Wikipedia currently has two articles on optimization that maybe merged in the future:

http://en.wikipedia.org/wiki/Optimization_(mathematics)

http://en.wikipedia.org/wiki/Optimization_problem

Solvers are pieces of software that aim to solve an optimization problem. To use a solver we generally have to describe the problem to the solver. So if we were trying to solve the travelling salesman problem to the solver we would have to input a description of all possible routes between the nodes in our graph and tell it how to compute the cost function for each element in the set of all possible routes. Depending on the API that the solver offers this might be ease or quite difficult. The Solver Foundation is a set of solvers implemented as a .NET library with a classical object model interface, the F# Optimization Modelling Language is a DSL that offers an alternative way to describe the your problem optimization.

The F# Optimization Modelling Language allows you to solve linear equations. Solving linear equations may sound quite easy, image we have the equation:

20.0 * sa + 15.0 * vz

You can pretty much straight away tell me the maximum value is infinity and the minimum value is negative infinity. If I add a simple constrain the variables “sa” and “vz”:

0 < sa < 500

0 < vz < 200

you can probably still easily tell me that the minimum value is 0 and the maximum is  13000 (20 * 500 + 15 * 200). However if we were to add more constrains and variables the problem would quickly become two difficult to solve with a pen and paper. The DSL uses a using a simplex solver “under the hood” and if you check out the Wikipedia article you can see the maths of this are quite challenging.

So how does the DSL work? The DSL re-interprets an F# quoted expression and inputs this into the SimplexSolver class which is available in the Microsoft.Solver.Foundation.dll. The quoted expression must have the form:

variable declarations

cost/goal function

constraints

More concretely an example of the syntax looks like this:

<@

    let sa = var "SA"

    let vz = var "VZ"

    

    minimise (20.0 * sa + 15.0 * vz)

   

    where

        [

            0.3 * sa + 0.4 * vz >= 2000.;

            0.4 * sa + 0.2 * vz >= 1500.;

            0.2 * sa + 0.3 * vz >= 500.;

            sa <= 9000.;

            vz <= 6000.;

            sa >= 0.;

            vz >= 0. 

        ]

@>

Here we can see we have two variables sa and vz and an we’re trying to find the minimum value of the equation 20.0 * sa + 15.0 * vz, at the end we have a set of constrains that the solution must conform to. As this is a quotation, it is a data structure rather than code, so it can be interpreted rather like a C# expression tree can. So the whole quoted expression is then passed to a function to be interpreted by making calls to the underlying object model exposed by the Microsoft.Planning.Solvers.dll and then hopefully solved. So to put you out of your misery the minimum value of this equation, give the constraints, is 92500.0 where SA = 2000.0 and VZ = 3500.0.

So why would be use a DSL to input this problem rather than using the classical object model? Well in short it’s simpler and easier to use. To illustrate this point I’ve rewritten the previous example as a C# program, which is clearly a lot longer, but worse than that it feels a lot more like programming, the meaning of our expressions is hidden in amongst lots of variable declarations and method calls:

    static void Main(string[] args) {

      SimplexSolver simplexSolver = new SimplexSolver();

      int saId;

      int vzId;

      simplexSolver.AddVariable("SA", out saId);

      simplexSolver.AddVariable("VZ", out vzId);

 

      //0.3 * sa + 0.4 * vz >= 2000.;

      int constraint1;

      simplexSolver.AddRow("constraint1", out constraint1);

      simplexSolver.SetCoefficient(constraint1, saId, 0.3);

      simplexSolver.SetCoefficient(constraint1, vzId, 0.4);

      simplexSolver.SetLowerBound(constraint1, 2000.0);

 

      //0.4 * sa + 0.2 * vz >= 1500.;

      int constraint2;

      simplexSolver.AddRow("constraint2", out constraint2);

      simplexSolver.SetCoefficient(constraint2, saId, 0.4);

      simplexSolver.SetCoefficient(constraint2, vzId, 0.2);

      simplexSolver.SetLowerBound(constraint2, 1500.0);

 

      //0.2 * sa + 0.3 * vz >= 500.;

      int constraint3;

      simplexSolver.AddRow("constraint3", out constraint3);

      simplexSolver.SetCoefficient(constraint3, saId, 0.2);

      simplexSolver.SetCoefficient(constraint3, vzId, 0.3);

      simplexSolver.SetLowerBound(constraint3, 500.0);

 

      //sa <= 9000.;

      simplexSolver.SetUpperBound(saId, 9000.0);

      //vz <= 6000.;

      simplexSolver.SetUpperBound(vzId, 6000.0);

      //sa >= 0.;

      simplexSolver.SetLowerBound(saId, 0.0);

      //vz >= 0. 

      simplexSolver.SetLowerBound(vzId, 0.0);

 

      //minimise (20.0 * sa + 15.0 * vz)

      int goalId;

      simplexSolver.AddRow("goal1", out goalId);

      simplexSolver.SetCoefficient(goalId, saId, 20.0);

      simplexSolver.SetCoefficient(goalId, vzId, 15.0);

      simplexSolver.AddGoal(goalId, 1, true);

 

      simplexSolver.Solve(new SimplexSolverParams());

      double sa = (double)simplexSolver.GetValue(saId);

      Console.WriteLine("SA: {0}", sa);

      double vz = (double)simplexSolver.GetValue(vzId);

      Console.WriteLine("VZ: {0}", vz);

      double goal = (double)simplexSolver.GetValue(goalId);

      Console.WriteLine("Goal: {0}", goal);

      Console.ReadLine();

    }

But at the end of the day I think it’s nice to of the choice of interface to have the choice of interface, especially as currently the F# Optimization Modelling Language only exposes a small sub-set of the Solver Foundation. Sometimes you’ll want to work with the lower level object model; often you’ll want to abstract this away to a DSL which allows you to describe the problem you’re solving rather than having to program it. Probably the most interesting job will be coming up with new DSL to describe specific optimization problems. Any one fancy writing a travelling salesman DSL?

F# is on dotnetrocks again, this time it’s Amanda Laucher and Ted Neward’s turn to talk F# with Carl and Richard. I have to say of all the F# podcast there have been so far this is my favourite. Why? Amanda and Ted do a really great job of articulating what I’ve been thinking about F#, and functional programming in general, for some time now. I think this is because Amanda and Ted have a similar background to me – they both come from the world of line of business applications. This is interesting because if you read the marketing blurb from Microsoft F# is clear target at the scientific/mathematical world, with a foot note that it is a general purpose programming language that can be used for anything you like.

So where’s the interest in F# for the average line of business application, well in short: it’s the business logic. Its seems to be widely agreed that the business logic (or “the domain” if your that way inclined), is the hardest part of the application. If you want simple CRUD app with no business logic, why not use COBOL? It’s great for cracking out that sort of thing. One of the main things developers of complex business logic want is for it to be testable. This is where pure functional programming excels; if a function receives the same input it always returns the same output. What could be more testable than that? While F# doesn’t force you to be pure at least it leads you in that direction. But it’s more that testability, in the world of business logic we’re talking about algoritms, we’re talking about verbs (rather than the nouns of the OO world), and it were talking about really complex business logic we’re probably talking about maths, all things that functional programming is good at. Functional programming encourages us to abstract further, to focus on the what we want to do rather than the how. Taken to its natural extreme this means using language oriented programming techniques and building DSLs to handle business logic. In the world of handling complex business logic being able to design a language that accurate and concisely describes the logic is something of a hole grail. No one’s going to pretend that designing a good DSL is easy in F#, there are no silver bullets, but it does at least hand you some of the tools you need. F#’s rich and flexible type system, gives you a union type that’s excellent for focusing on describing the semantics of a problem and it also gives you several integration points, workflows and quotations, that allow you to tweak or reinterpret the syntax.

People may see this as an attack on the dominance of OO in the programming world, a new FP/OO, but nothing is further from the truth. There’s much more synergy here that people release. It seems to me the concerns of OO and FP are largely orthogonal. OO is concerned with the nouns describing the nouns of a system, with encapsulating data, and describing its structure of data. Its big bother component orientation has really taught us how to put together great libraries. While FP focus on actions and algorithms. In fact there are some that believe people take the whole OO/FP thing too seriously, and that the real advantage of F# is it allows you forget all that and just write great programs for the domain your focusing on.

It’s interesting James Huddleston soon, the editor who commissioned “Foundations of F#”, thought that F#, or a decent of, would one day become the dominant way to program, while I wrote the book assuming would become popular but still quite “niche”. With Amanda and Ted on the case who knows, maybe he’s right?

As mentioned in my previous post, I’ve been reading “Collective Intelligence” by Toby Segaram and I’m really enjoying in it. It’s different to a lot of programming books, in that rather than focusing a specific language or API it focus on a particular set of problems and shows techniques that can be used to crack them.

For example I’ve known for a long time that it’s easy to create an abstract syntax tree (AST) in F#:

/// Untyped expression tree

type Expression =

    | Multiply of Expression * Expression

    | Add of Expression * Expression

    | Subtract of Expression * Expression

    | GreaterThan of Expression * Expression

    | If of Expression * Expression * Expression

    | Constant of int

    | Parameter of int

Here we present a simple AST for representing numeric expressions, while it’s easy to provide a function to evaluate such a tree:

/// Given a list of parameters evaluate the tree

let evaluateExpression parameters =

    let rec innerEval tree =

        match tree with

        | Multiply (x, y) -> innerEval x * innerEval y

        | Add (x, y) -> innerEval x + innerEval y

        | Subtract (x, y) -> innerEval x - innerEval y

        | GreaterThan (x, y) -> if innerEval x > innerEval y then 0 else 1

        | If (pred, tval, fval) -> if innerEval pred = 0 then innerEval fval else innerEval tval

        | Constant value -> value

        | Parameter pos -> List.nth parameters pos

    innerEval

I’ve often had problems coming up with nice simple examples of what you might want to do with such an expression. Well “Collective Intelligence” gave me a great idea of what you can do with such an expression: genetic programming. The example we’re going to look at is presented in chapter 11, pages 251 to 268. The idea is straight forward if you can abstractly represent a program as we can with our numeric expression AST then it’s possible to make random changes to our program. Wants we have made the random changes we can measure which programs are successful and use the successful ones to create a new generation of programs. So what kind of problems can we solve with this approach? Well here’s a nice one, suppose we have a set of points:

X             Y              Result

36           38          1485

17           13          371

13           2             217

24           31          715

13           0             213

38           3             1569

10           11          157

11           32          223

 18          25          433

And we want to find out what function fits best to these points, we can use genetic programming to solve this problem. I’ve given a program below that can solve this problem though genetic programming. I don’t want to go into too many details, you should really buy the book if you want a good explanation, but in a nutshell the algorithm works in the following way:

-          We create a bunch of random function

-          We test how close these get to the predefined points

-          If we find a function that fits we return it

-          Otherwise we breed the most successful function and loop to the testing step

Anyway the full implementation is here, and version can be downloaded here [EDIT: link fixed]:

#light

open System

open Microsoft.FSharp.Math

 

/// Untyped expression tree

type Expression =

    | Multiply of Expression * Expression

    | Add of Expression * Expression

    | Subtract of Expression * Expression

    | GreaterThan of Expression * Expression

    | If of Expression * Expression * Expression

    | Constant of int

    | Parameter of int

 

/// Given a list of parameters evaluate the tree

let evaluateExpression parameters =

    let rec innerEval tree =

        match tree with

        | Multiply (x, y -> innerEval x * innerEval y

        | Add (x, y -> innerEval x + innerEval y

        | Subtract (x, y -> innerEval x - innerEval y

        | GreaterThan (x, y -> if innerEval x > innerEval y then 0 else 1

        | If (pred, tval, fval -> if innerEval pred = 0 then innerEval fval else innerEval tval

        | Constant value -> value

        | Parameter pos -> List.nth parameters pos

    innerEval

 

let simplifyExpression =

    let rec innerEval tree =

        match tree with

        | Multiply (Constant 0, _ -> Constant (0

        | Multiply (_, Constant 0 -> Constant (0

        | Multiply (Constant x, Constant y -> Constant (x * y

        | Add (Constant x, Constant y -> Constant (x + y

        | Subtract (Constant x, Constant y -> Constant (x - y

        | GreaterThan (Constant x, Constant y -> if x > y then Constant 0 else Constant 1

        | If (Constant pred, tval, fval -> if pred = 0 then fval else tval

        | x -> x

    let rec loop tree =

        let tree' = innerEval tree

        if tree' = tree then

            tree

        else

            loop tree

    loop

 

/// print the expression to the console

let printExpression =

    let rec innerPrint ppf tree =

        match tree with

        | Multiply (x, y -> Printf.fprintf ppf "(%a * %a" innerPrint x innerPrint y

        | Add (x, y -> Printf.fprintf ppf "(%a + %a" innerPrint x innerPrint y

        | Subtract (x, y -> Printf.fprintf ppf "(%a - %a" innerPrint x innerPrint y

        | GreaterThan (x, y -> Printf.fprintf ppf "(%a > %a" innerPrint x innerPrint y

        | If (pred, tval, fval -> Printf.fprintf ppf "(if %a then %a else %a" innerPrint pred innerPrint fval innerPrint tval

        | Constant value -> Printf.fprintf ppf "%i" value

        | Parameter pos -> Printf.fprintf ppf "p%i" pos

    innerPrint System.Console.Out

 

let rand = new Random(

 

/// build a random expression with limited depth, a maximum constants value,

/// and a limited number of parameters

let buildRandomExpression maxDepth maxConst noParams =

    let rec innerBuild curDepth =

        if curDepth < maxDepth then

            let nextDepth = curDepth + 1

            match rand.Next(7 with

            | 0 -> Multiply (innerBuild nextDepth, innerBuild nextDepth

            | 1 -> Add (innerBuild nextDepth, innerBuild nextDepth

            | 2 -> Subtract (innerBuild nextDepth, innerBuild nextDepth

            | 3 -> GreaterThan (innerBuild nextDepth, innerBuild nextDepth

            | 4 -> If (innerBuild nextDepth, innerBuild nextDepth, innerBuild nextDepth

            | 5 -> Constant (rand.Next(maxConst

            | 6 -> Parameter (rand.Next(noParams

            | _ -> failwith "assert false"

        else

            match rand.Next(2 with

            | 0 -> Constant (rand.Next(maxConst

            | 1 -> Parameter (rand.Next(noParams

            | _ -> failwith "assert false"

    innerBuild 0

 

/// make a change to an existing tree by replace a node

/// with a randomly generated tree

let mutateExpression maxConst maxParam rate =

    let rec innerMutate currDepth tree =

        let mutate node =

            let newNode =

                if rand.NextDouble( < rate then

                    buildRandomExpression maxConst maxParam (currDepth + 1

                else node

            innerMutate (currDepth + 1 node

        match tree with

        | Multiply (x, y -> Multiply (mutate x, mutate y

        | Add (x, y -> Add(mutate  x, mutate  y

        | Subtract (x, y -> Subtract (mutate  x, mutate  y

        | GreaterThan (x, y -> GreaterThan (mutate  x, mutate  y

        | If (pred, tval, fval -> If (mutate  pred, mutate  fval, mutate  tval

        | Constant value -> Constant( value

        | Parameter pos -> Parameter ( pos

    innerMutate 0

 

 

let (|Binary|Nullary| = function

    | Add(x,y -> Binaryfun(x,y -> Add(x,y,x,y

    | Subtract(x,y -> Binaryfun(x,y -> Subtract(x,y,x,y

    | Multiply(x,y -> Binaryfun(x,y -> Multiply(x,y,x,y

    | GreaterThan(x,y -> Binary(fun (x,y -> GreaterThan(x,y,x,y

    | If(pred,tval,fval -> Binaryfun (x,y -> If (pred,x,y,tval,fval

    | x -> Nullary(x

 

type HoleTree =

  | LeftHole of (Expression * Expression -> Expression * HoleTree * Expression

  | RightHole of (Expression * Expression -> Expression * Expression * HoleTree

  | Hole

 

let rec plug = function

  | LeftHole(con,h,r,t -> con(plug(h,t, r

  | RightHole(con,l,h,t -> con(l, plug(h,t

  | Hole,t -> t

 

 

let rec descendTree top p = function

  | Nullary(x -> Hole, x

  | t when not top && rand.NextDouble( < p -> Hole, t

  | Binary(con,l,r ->

      if rand.NextDouble( < 0.5 then

        let h,t = descendTree false p l

        LeftHole(con,h,r,t

      else

        let h,t = descendTree false p r

        RightHole(con,l,h,t

 

let crossOverExpressions p t1 t2 =

    let h,_ = descendTree true p t1

    let _,t = descendTree true p t2

    plug(h,t

 

let evolve scoreFunction mutRate crossRate breedChance pop maxGen maxDepth maxConst noParams =

 

    let initPop = List.init pop (fun _ -> buildRandomExpression maxDepth maxConst noParams

 

    // the inner loop which will handle each generation

    let rec innerGenEvolve currPop currGen =

   

        // calculate score sort list to find the winner

        let res =

            [ for expr in currPop ->

                scoreFunction expr, expr ]

        let res = List.sort (fun (score1,_ (score2,_ -> compare score1 score2 res

        let score,winner = List.hd res

       

        // print the winner ... just for info

        printfn "\nGen:%i score:%A" currGen score

        printExpression winner

       

        // if we've found winner or reached the maxium gens return

        if score = 0I || currGen = maxGen then

            winner

        else

            // get rid of scores, no longer needed

            let res = List.map snd res

           

            // always keep winner and second

            let winner, second =

                match res with

                | winner :: second :: _ -> winner, second

                | _ -> failwith "assert false"

            let newpop = winner :: second :: []

           

            // select an expression probably towards to top of the list

            let selectExpr( = List.nth res (min (List.length res - 1 (int(log(rand.NextDouble( / log(breedChance

           

            // loop to calculate the new population

            let rec addExpress acc=

                if  List.length acc = pop then

                    acc

                else

                    // cross two expressions then mutate

                    let crossExpress = (crossOverExpressions crossRate (selectExpr( (selectExpr(

                    let newExp = mutateExpression maxConst noParams mutRate crossExpress

                    addExpress (newExp :: acc

             �