Answered by:
Embedding an arithmetic DSL in F#
Question

Hello,I have to embed a DSL for linear programming (MILP) in F# as close as possible to the following example (dedicated language).[Syntax example]
{string} teams = {"ATL", "NYM", "PHI", "MON"}; int distance [teams][teams] = [ [0, 745, 665, 929], [745, 0, 80, 337], [665, 80, 0, 380], [929, 337, 380, 0] ]; int nbTeams = card (teams); int firstDay = 1; int lastDay = 2 * nbTeams  2 + 1; range days = firstDay..lastDay; //dvar float travels [teams][days][teams][teams]; dvar int travels [teams][days][teams][teams] in 0..1; dexpr int cost [t in teams] = sum (i, j in teams, d in days) distance[i][j] * travels[t][d][i][j]; minimize sum (t in teams) cost[t]; constraints { // Teams follows a route forall (t in teams, d in days, j in teams : (d + 1) in days) sum (i in teams) travels[t][d][i][j] == sum (k in teams) travels[t][d + 1][j][k]; // Each team plays each other other once home, once away forall (t, s in teams : t != s) sum (i in teams, d in days : i != s) travels[t][d][i][s] == 1; // If team A visits B then B plays at home forall (t in teams, d in days : d != lastDay) sum (j in teams) travels[t][d][j][t] == sum (s, j in teams : s != t) travels[s][d][j][t]; // No repeaters forall (s, t in teams, d in days : s != t && (d + 1) in days) sum (j in teams) travels[s][d][j][t] + sum (j in teams) travels[t][d + 1][j][s] <= 1; }
[End syntax example]I still have trouble with multidimensional sparse arrays with .[] syntax sum keyword and similar operators message saying I shouldn't be redefining the comparison operatorTill now I have used objects with operator overloading, I was thinking of combining that with quotes. However, because the quotes are typed I still need something that typechecks even with phony semantics before I can process the quote.Here is as far as I gottype ExprA =  Var of string * int list  IntConstant of int  FloatConstant of float  Plus of ExprA * ExprA  Minus of ExprA * ExprA  Times of ExprA * ExprA type Comparison = Leq  Eq  Geq type ConstrA = ExprA * Comparison * ExprA type Constraint (c : ConstrA) = member v.content = c let inline (<=) x y = ((^a or ^b): (static member (<=) : ^a * ^b > ^c) (x,y)) type Expr (e : ExprA) = member v.content = e static member (+) (e1 : int, e2 : Expr) = Expr (Plus (IntConstant (e1), e2.content)) static member (+) (e1 : Expr, e2 : Expr) = Expr (Plus (e1.content, e2.content)) static member () (e1 : Expr, e2 : Expr) = Expr (Minus (e1.content, e2.content)) static member (*) (e1 : int, e2 : Expr) = Expr (Times (IntConstant (e1), e2.content)) static member (*) (e1 : float, e2 : Expr) = Expr (Times (FloatConstant (e1), e2.content)) static member (*) (e1 : Expr, e2 : Expr) = Expr (Times (e1.content, e2.content)) static member (<=) (e1 : Expr, e2 : int) = Constraint (e1.content, Leq, IntConstant(e2)) static member (<=) (e1 : Expr, e2 : float) = Constraint (e1.content, Leq, FloatConstant(e2)) static member (<=) (e1 : Expr, e2 : Expr) = Constraint (e1.content, Leq, e2.content) static member (==) (e1 : Expr, e2 : int) = Constraint (e1.content, Eq, IntConstant (e2)) static member (==) (e1 : Expr, e2 : float) = Constraint (e1.content, Eq, FloatConstant (e2)) static member (==) (e1 : Expr, e2 : Expr) = Constraint (e1.content, Eq, e2.content) let UIDcounter = ref 0 type dvar<'T> (indexes : int seq) = let mutable name = incr UIDcounter; "Var" + string(!UIDcounter) let indexes = Set.ofSeq (indexes) member t.Item with get i = if indexes.Contains i then new Expr (Var (name, [i])) else failwith ("out of bounds " + name + " : " + string(i)) // Testing let cities = [0..10] let teams = Set.ofSeq (seq { for x in 0..10 > x }) // add workflow for sets : set { for x in 0..10 > x } let y = dvar<float> [0..10] let x = dvar<int> cities let z = dvar<bool> teams x.[10] // add pretty printer for dvars y.[11] 3 * x.[10] 3 * x.[10] + 2 * x.[9] 3.0 * y.[10] 3 * y.[10] Seq.fold (fun total x > total + x) x.[0] (seq {for i in 1..10 > x.[i]}) x.[10] == x.[9] x.[10] == 9 3 * x.[10] + 2 * x.[9] == 9 y.[10] == x.[9] y.[10] == 9.5 y.[10] == 9 3 * y.[10] + 2 * y.[9] == 9 [for i in 0..10 > i * x.[i] == 3] seq { for i in 0..10 do for j in 0..10 > (i + j) * x.[i] == j } seq { // Constraint A for i in 1..2 do yield i * x.[i] == i // Constraint B for j in 3..4 > j * x.[j] == j } x.[10] <= x.[5] x.[10] <= 5 x.[10] <= 5.5 2 * x.[10] <= 5 * x.[5] x.[10] <= y.[5] 3 + 3 * x.[10] + 2.5 * x.[9] + 2 * y.[1] <= 9
 Edited by DiegoOlivierFernandezPons Friday, September 23, 2011 8:48 AM
Friday, September 23, 2011 8:42 AM
Answers

A few thoughts:
What exactly are your problems with multidimensional arrays? Note that you can implement the getter for the Item member to take more than 1 argument as a means to achieve the syntax in your example. That is:
As far as quotations, there is an untyped variant using <@@ ... @@> which combined with the splicing operator may help depending on your particular problem.
type T() = member this.Item with get(x,y) = 1 member this.Item with get(x,y,z) = 2 let x = T() x.[1,2] x.[1,2,3]
Can you elaborate on the problem with comparison operators? Why not implement IComparable as the warnings suggest? Or else just make the operators traditional functions that take arguments of Expr/ExprA?
 Edited by Dan Quirk  MSFTMicrosoft employee Thursday, September 29, 2011 11:57 PM
 Marked as answer by DiegoOlivierFernandezPons Thursday, October 6, 2011 8:25 AM
Thursday, September 29, 2011 10:48 PM
All replies

A few thoughts:
What exactly are your problems with multidimensional arrays? Note that you can implement the getter for the Item member to take more than 1 argument as a means to achieve the syntax in your example. That is:
As far as quotations, there is an untyped variant using <@@ ... @@> which combined with the splicing operator may help depending on your particular problem.
type T() = member this.Item with get(x,y) = 1 member this.Item with get(x,y,z) = 2 let x = T() x.[1,2] x.[1,2,3]
Can you elaborate on the problem with comparison operators? Why not implement IComparable as the warnings suggest? Or else just make the operators traditional functions that take arguments of Expr/ExprA?
 Edited by Dan Quirk  MSFTMicrosoft employee Thursday, September 29, 2011 11:57 PM
 Marked as answer by DiegoOlivierFernandezPons Thursday, October 6, 2011 8:25 AM
Thursday, September 29, 2011 10:48 PM 
I more or less fixed all the issues with the sparseArrays (mainly due to the fact that type constraints are a bit surprizing in F# in the sense that sometimes F# compiles and typechecks things that don't fully work). Still working on the quotes. I suggest closing this questions and adressing specific questions in separate threads.Thursday, October 6, 2011 8:25 AM