30 March 2006

C# lambda expressions and constraint programming

Neat thing about C# lambda expressions: the recipient of a lambda gets to choose whether it wants a compiled function or just a parse tree.

    var f = orders.Where(o => o.ShipCity == "London");

Here the lambda o => o.ShipCity == "London" compiles into either a function or an Expression object, depending on the parameter type of orders.Where(). As the caller, you don't care which.

So I got to thinking. Languages that implement constraint programming as a library feature, like Alice ML, seem to end up looking rather clunky:

    fun money sp =
        val v as #[S,E,N,D,M,O,R,Y] = fdtermVec (sp, 8, [0`#9])
        distinct (sp, v, FD.BND); 
        post (sp, S `<> `0, FD.BND); 
        post (sp, M `<> `0, FD.BND); 
        post (sp, `1000`*S `+ `100`*E `+ `10`*N `+ D `+
                  `1000`*M `+ `100`*O `+ `10`*R `+ E `=
                 `10000`*M `+ `1000`*O `+ `100`*N `+ `10`*E `+ Y, FD.BND); 
        branch (sp, v, FD.B_SIZE_MIN, FD.B_MIN); 

It looks a lot nicer in a language like Oz, which has language support for logic variables and so forth.

    proc {Money Root}
       S E N D M O R Y
       Root = sol(s:S e:E n:N d:D m:M o:O r:R y:Y)
       Root ::: 0#9
       {FD.distinct Root}
       S \=: 0
       M \=: 0
                    1000*S + 100*E + 10*N + D
       +            1000*M + 100*O + 10*R + E
       =: 10000*M + 1000*O + 100*N + 10*E + Y
       {FD.distribute ff Root}

(Example from Mozart documentation.)

Now C# doesn't have that, but it seems like a constraint library similar to Alice's, designed in C#, could take advantage of expression trees to make the rules somewhat more readable:

    sp.Post(S => S != 0);
    sp.Post(M => M != 0);
    sp.Post((S, E, N, D, M, O, R, Y) =>
                           1000*S + 100*E + 10*N + D
                         + 1000*M + 100*O + 10*R + E
              == 10000*M + 1000*O + 100*N + 10*E + Y);

Of course, lambdas only help with rules, and there's much more to the problem statement than rules. Still, I wonder if anyone is doing this.

No comments: