使用参照透明度来预先计算haskell中的值

Question

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

list = [1..10000000]

main = print $ sum list

我想要编译这样,可执行文件只打印50000005000000,而不需要花费太多时间和精力.

基本上,任何可以确定计算的表达式(也许严格性分析可以在这里帮助)都可以在编译期间预先计算(即我们使用参考透明度来表示在计算值时它并不重要).

简而言之:"必须计算"+参考 - 透明度=可以预先计算

这就像运行程序,直到我们点击依赖于输入的东西(即程序的核心,在所有输入中共同的,将被预先计算)

是否存在当前实现此目的的机制(使用Haskell或任何其他语言)？[请不要指向C++中的模板之类的东西,因为它首先没有引用透明度.]

如果没有,这个问题有多难？[伴随的技术(和理论)问题是什么？]

Answer 1

编译时计算的一般目的是使用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.)

Answer 2

这在一般情况下是不安全的.原因是Haskell表达式可能是纯粹的,但它们也可能无法终止.编译器应始终终止,因此您可以做的最好的事情是"评估此结果的1,000个步骤".¹但是如果你确实添加了这样的限制,那么如果你正在编译一个程序以在具有太字节RAM的超级计算机集群上运行,并且编译器内存不足,该怎么办？

您可以添加许多限制,但最终您将优化减少到缓慢形式的常量折叠(特别是对于大多数计算依赖于运行时用户输入的程序).而且由于sum [1..10000000]这里需要半秒钟,因此它不太可能达到任何合理的限制.

当然,像这样的特定情况通常可以被优化掉,而GHC通常会优化掉像这样的复杂表达式.但是编译器不能只是在编译时安全地评估任何表达式; 它必须非常受限制,并且可以说它在这些限制下会有多大帮助.它是一个编译器,而不是一个解释器:)

¹这将其中的任何程序的编译大规模放缓确实含有大量的死循环-这,因为Haskell是不严格的,很可能比你想象的).或者,更常见的是,任何包含大量长时间运行计算的程序.