metaprogramming - 从有限的输入集生成代码

Question

假设我有一个映射(具有已知类型)，例如

1:错误，4:假的，8:是的，16:真

我想生成一个接受输入并给出正确输出的函数。我不关心不在上述映射中的任何输入会发生什么，例如 3 永远不会被期望。

例如，一个天真的解决方案是使用 switch 语句生成函数

f(int x) {
    if x == 1 return false;
    else if x == 4 return false;
    else if x == 8 return true;
    else if x == 16 return true;
}

我希望能够生成不随输入集在内存中缩放的代码。

f(int x) {
    return x >= 8;
}

这个问题有名字吗？我应该研究哪个领域？

Answer 1

您想“猜测”为未提供的输入生成什么代码。

你做不到。

[编辑:在进一步的讨论中，我现在很清楚他不关心这些输入。我将按原样保留答案，因为人们会像我一样假设他必须关心。无论如何，在这个答案的末尾提供了令人惊讶的建议]。

假设您有一个对手要在所有输入上指定一个函数 f，但他/她只为您提供了一个样本，如您的示例所示。一些固定的输入集。您现在应用一个 oracle，它猜测 f(9) true。您的对手立即表明她的函数 f(9) 实际上是 false。同样，如果您猜测 f(9) 为假。

对手总是可以制造与您的代码生成器猜测不匹配的输入/输出对。所以你根本无法做到正确。

您可以做的是接受您的猜测可能是错误的，并尝试选择一个复杂度最低的函数来解释您目前所见的输入/输出对。您的示例本质上就是其中之一。

如果您认为“简单”函数比复杂函数更能逼近世界，您可以生成代码并希望您不会遇到自然界的对手。

不要指望它是可靠的。

有了这些警告，OP 可能会对 GNU SuperOptimizer 感兴趣.这找到了产生一组提供的输入/输出对的短机器指令序列[实际上，我认为你给它计算答案的函数，就像 OP 的原始函数一样] 通过“显然”从字面上尝试每个指令序列的疯狂想法。

super 优化器背后的天才之处在于，这种特技实际上适用于短指令序列。

我认为修改它以生成通用的“C”指令(例如有效的 C 操作)会很容易，因为我相信它无论如何都使用 C 操作来模拟机器指令。您可能必须修改您的函数以针对无关紧要的输入生成“不关心”的结果，并告诉 GNU super 优化器“不关心”是一个有效的结果。这实际上也是对 GNU super 优化器的一个有用的补充，以达到其最初的目的。