Code generation for mathematical problems [closed]

Question

I would like to write a program that takes in a description of a mathematical (optimization) problem, parses it, and generates compact, efficient C code that solves it. I have a hacked up solution to a much smaller, more specific problem, in python, but it is ugly and just relies on templating the C code - so I have a whole mess of strings that look like

for (k = 0; k <= %s; k += %s) a[k] = v[k]/%s * a[i];

And then there is a mess of complex conditional logic, and at some point the above line gets written to solve_problem.c, after filling in the correct values of %s.

It actually gets much more complicated, because typically the problem is parameterized by matrices with certain structure, etc, and the approach above, while workable, is sort of starting to fall apart under its own weight.

So I suppose what I'm looking for is high-level advice on how to represent these sorts of problems in code, or rather just examples of other projects where this has been solved. Someone told me to use OCaml or F# and look at FFTW, but something simpler would be appreciated.

I'm sorry for being so inarticulate, but it's difficult for me to even express what I'm looking for to myself, which is, I think, the root of the problem.

Answer 1

for (k = 0; k <= %s; k += %s) a[k] = v[k]/%s * a[i];

You are asking for ways to represent code like the above. This could be represented by the value:

For("k", Int 0, Leq(Var "k", a), Set("k", Add(Var "k", b)),
    SetElt(Var "a", Var "k",
           Mul(Div(GetElt(Var "v", Var "k"), c, GetElt(Var "a", Var "i")))))

given a type like this:

type Expr =
  | Int of int
  | Var of string
  | Leq of Expr * Expr
  | Mul of Expr * Expr
  | Div of Expr * Expr
  | Set of string * Expr
  | SetElt of Expr * Expr * Expr
  | GetElt of Expr * Expr
  | For of string * Expr * Expr * Expr

I wrote a very simple high-level VM called HLVM that you might find enlightening because it uses such representations in a simple way. The definitions are here and a bunch of tests written using those definitions are here.

This representation is far more powerful than string munging because the pattern match compiler does exhaustiveness and redundancy checking for you, making it easy to write functions over values of this Expr type including optimization passes and code generators.

Answer 2

You are trying to implement a compiler, and this is how you should approach your problem. There is an input language which describes your optimization problem, and the output language is C.

You can chop up your problem into the following tasks (not necessarily solved in this order):

1. Design a data structure which represents the abstract syntax for your input language.
2. Design a data structure which represents the abstract syntax of your output language, which in your case is (a subset of) C.
3. Design concrete syntax of your input language.
4. Implement a lexer and a parser which converts concrete syntax to abstract syntax.
5. Implement a pretty printer which converts the abstract syntax of your output language to concrete syntax.
6. Implement a compiler which takes an optimization problem, expressed in abstract syntax, into the output, again expressed in abstract syntax.

If you are not used to implementing languages and compilers you will be tempted to take shortcuts. For example, you might consider parsing using regular expressions. Or you might think it is a good idea to skip the abstract syntax, and just generate the C source directly. I strongly advise against this. Abstraction is your friend because it will make your problem manageable.

You should carefully choose the language in which you will implement the whole thing. Of course, something like Ocaml is perfect for the job. But if you do not know Ocaml already, you should just stick to whatever language you are most comfortable with. You should not try to implement parsers by hand, there are plenty of parser generators out there. It is worth learning one. You may find my PL Zoo helpful.