6

我想编写一个程序，该程序接受对数学（优化）问题的描述，对其进行解析，并生成解决该问题的紧凑、高效的 C 代码。在 python 中，我对一个更小、更具体的问题有一个破解的解决方案，但它很丑陋，只依赖于 C 代码的模板 - 所以我有一堆看起来像的字符串

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

然后是一堆复杂的条件逻辑，在填写正确的 %s 值后，在某些时候上面的行被写入 solve_problem.c。

它实际上变得更加复杂，因为通常问题是由具有特定结构的矩阵等参数化的，而上述方法虽然可行，但在其自身的影响下开始分崩离析。

所以我想我正在寻找的是关于如何在代码中表示这些类型的问题的高级建议，或者更确切地说只是其他项目已经解决了这个问题的示例。有人告诉我使用 OCaml 或 F# 并查看 FFTW，但更简单的东西将不胜感激。

我很抱歉如此口齿不清，但我什至很难向自己表达我在寻找什么，我认为这就是问题的根源。

4

5 回答 5

8 
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

我编写了一个名为 HLVM 的非常简单的高级 VM，您可能会发现它很有启发性，因为它以简单的方式使用了这种表示。定义在这里，并且使用这些定义编写的一堆测试在这里。

这种表示比字符串处理功能强大得多，因为模式匹配编译器会为您进行详尽和冗余检查，从而可以轻松地在这种Expr类型的值上编写函数，包括优化通道和代码生成器。

于 2012-11-05T11:16:50.557 回答
3

您正在尝试实现编译器，这就是您应该解决问题的方式。有一种输入语言可以描述您的优化问题，输出语言是 C。

您可以将您的问题分解为以下任务（不一定按此顺序解决）：

  1. 设计一个代表输入语言的抽象语法的数据结构。
  2. 设计一个表示输出语言的抽象语法的数据结构，在您的情况下，它是 C 的（一个子集）。
  3. 设计输入语言的具体语法。
  4. 实现一个词法分析器和一个将具体语法转换为抽象语法的解析器。
  5. 实现一个漂亮的打印机，将输出语言的抽象语法转换为具体语法。
  6. 实现一个编译器，它将以抽象语法表示的优化问题带入输出，再次以抽象语法表示。

如果你不习惯实现语言和编译器，你会很想走捷径。例如，您可能会考虑使用正则表达式进行解析。或者您可能认为跳过抽象语法并直接生成 C 源代码是个好主意。我强烈建议不要这样做。抽象是你的朋友，因为它会使你的问题易于管理。

您应该仔细选择实现整个过程所使用的语言。当然，像 Ocaml 这样的东西非常适合这项工作。但是，如果您还不了解 Ocaml，则应该坚持使用您最熟悉的任何语言。您不应该尝试手动实现解析器，那里有很多解析器生成器。值得一学。您可能会发现我的PL Zoo很有帮助。

于 2012-11-03T02:41:54.207 回答
2

我不知道您在优化方面有多少背景，但我怀疑您描述的路径是要走的路。具体来说，如果您可以编写高效的 C 代码来解决优化问题，我会感到惊讶，除非您将自己限制在特定类别的问题上。优化通常区分不同类型的问题（线性与非线性、整数与连续与混合整数规划），每种问题通常使用非常不同的算法来解决解决方案。

您可能想查看Microsoft Solver Foundation以获得一些想法。本质上，MSF 是一个通用 API，它允许您以多种形式声明您的问题（OML，一种用于指定优化问题的声明性语言，还有 C# 和 F#），然后根据性质将问题提供给适当的求解器的问题。

于 2012-11-03T00:17:55.900 回答
1

听起来你想要符号计算之类的东西。查看一些实现，例如：

一般来说，尝试查看优化包，许多支持某种符号表示。

于 2012-11-02T22:18:27.480 回答
1

不知道更简单。建议你看看现有的数学建模工作。我不希望这很简单。求解器代码已经够难了，生成它们也更难。

您需要指定问题细节的方法，以及组装由这些细节控制的答案部分的方法。

我建议：

Sinapse，一个生成数学建模代码的系统；本文讨论了知识是如何组织的以及如何支持有限差分码的生成，

和

求解有限差分方程，麻省理工学院的论文也是如此。

（我在 Sinapse 系统的初始开发过程中工作过）。

于 2012-11-02T21:41:19.177 回答