6

假设我们有一个这样的程序：

list = [1..10000000]

main = print $ sum list

我希望将其编译为可执行文件仅打印 50000005000000，而无需花费太多时间和精力。

基本上，任何肯定会被计算的表达式（也许严格性分析在这里会有所帮助）都可以在编译期间预先计算（即我们使用引用透明性来表示计算值时并不重要）。

简而言之：“必须计算”+参考透明度=可以预先计算

这就像运行程序，直到我们遇到依赖于输入的东西（即程序的核心，所有输入通用的，将被预先计算）

目前是否有实现这一目标的现有机制（用 Haskell 或任何其他语言）？[请不要指向 C++ 中的模板之类的东西，因为它首先没有引用透明性。]

如果不是，这个问题有多难？[伴随的技术（和理论）问题是什么？]

4

3 回答 3

11

进行编译时计算的通用答案是使用 Template Haskell。但是对于这个特定的用例，你可以使用向量包和 LLVM 后端，GHC 会优化掉这个总和。

sorghum:~% cat >test.hs
import Data.Vector.Unboxed as V
main = print (V.sum $ V.enumFromN (1 :: Int) 10000000)
sorghum:~% ghc --make -O2 -fllvm test.hs
[1 of 1] Compiling Main             ( test.hs, test.o )
Linking test ...
sorghum:~% time ./test
50000005000000
./test  0.00s user 0.00s system 0% cpu 0.002 total
sorghum:~% objdump -d test | grep 2d7988896b40
  40653d:   48 bb 40 6b 89 88 79    movabs $0x2d7988896b40,%rbx
  406547:   49 be 40 6b 89 88 79    movabs $0x2d7988896b40,%r14

（如果不是很明显，0x2d79888896b40是50000005000000。）

于 2012-04-10T18:01:22.400 回答
11

这在一般情况下是不安全的。原因是 Haskell 表达式可能是纯粹的，但它们也可能无法终止。编译器应该总是终止，所以你能做的最好的就是“评估这个结果的 1000 步”。1但是，如果您确实添加了这样的限制，如果您正在编译一个程序以在具有 TB 级 RAM 的超级计算机集群上运行，并且编译器内存不足怎么办？

您可以添加许多限制，但最终您会将优化减少为一种缓慢的常量折叠形式（尤其是对于大多数计算依赖于运行时用户输入的程序而言）。而且由于sum [1..10000000]这里需要半秒钟，所以它不太可能落在任何合理的限制之下。

当然，像这样的特定情况通常可以优化掉，而 GHC 经常会优化掉这样的复杂表达式。但是编译器不能只在编译时安全地评估任何表达式；它必须受到非常严格的限制，并且在这些限制下它会有多大帮助是有争议的。它是编译器，而不是解释器 :)

1这会大大减慢任何包含大量无限循环的程序的编译速度——由于 Haskell 是非严格的，这比你想象的更有可能）。或者，更常见的是，任何包含大量长时间运行计算的程序。

于 2012-04-10T18:01:24.493 回答
1

听起来像是超级编译的工作！这个问题听起来像是对它的描述，关于非终止的讨论反映了超级编译器开发人员面临的问题。我在 GHC wiki 上看到有人正在为它开发一个生产超级编译器，但不知道结果如何。

于 2012-04-12T01:00:02.220 回答