数学问题的代码生成

Question

我想编写一个程序,它接受一个数学(优化)问题的描述,解析它,并生成解决它的紧凑,高效的C代码.我在python中有一个更小,更具体的问题的黑客攻击解决方案,但它很难看,只是依赖于模板化的C代码 - 所以我有一堆乱七八糟的字符串看起来像

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

然后有一堆复杂的条件逻辑,在填写正确的%s值之后,上面的某行会被写入solve_problem.c.

它实际上变得更加复杂,因为通常问题是通过具有某种结构的矩阵等参数化的,并且上述方法虽然可行,但在其自身重量下开始崩溃.

所以我想我正在寻找的是关于如何在代码中表示这些问题的高级建议,或者更确切地说是其他项目已经解决的例子.有人告诉我使用OCaml或F#并查看FFTW,但更简单的东西将被赞赏.

我很抱歉这么说不好,但我甚至难以表达自己正在寻找的东西,我认为这是问题的根源.

Answer 1

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

您正在寻找代表上述代码的方法.这可以用值表示:

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")))))

给出这样的类型:

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

我写了一个非常简单的高级VM,称为HLVM,你可能会发现它很有启发性,因为它以一种简单的方式使用这种表示.该定义是在这里和一堆使用这些定义笔试都在这里.

这种表示比字符串重叠更强大,因为模式匹配编译器会为您执行详尽无遗和冗余检查,从而可以轻松地在此Expr类型的值上编写函数,包括优化传递和代码生成器.