Использование ссылочной прозрачности для предварительного вычисления значений в haskell

Question

Допустим, у нас есть такая программа:

list = [1..10000000]

main = print $ sum list

Я хочу, чтобы это было скомпилировано так, чтобы исполняемый файл просто печатал 50000005000000, не занимая столько времени и усилий.

По сути, любое выражение, которое будет обязательно вычислено (может быть, здесь поможет анализ строгости), может быть предварительно вычислено во время компиляции (т.е. мы используем ссылочную прозрачность, чтобы сказать, что на самом деле не имеет значения, когда мы вычисляем значение).

Вкратце: "должно быть вычислено" + referential-прозрачность = может быть предварительно вычислено

Это будет похоже на запуск программы до тех пор, пока мы не столкнемся с чем-то, что зависит от входных данных (т.е. ядро ​​программы, то, что является общим для всех входных данных, будет предварительно вычислено)

Существует ли существующий механизм для достижения этого в настоящее время (на Хаскеле или на любом другом языке)? [Пожалуйста, не указывайте на что-то вроде шаблонов в C++, так как он не имеет ссылочной прозрачности.]

Если нет, то насколько сложна эта проблема? [Каковы сопутствующие технические (и теоретические) проблемы?]

Answer 1

Это не безопасно в общем случае. Причина в том, что выражения на Haskell могут быть чистыми, но они также могут не завершаться. Компилятор всегда должен завершаться, поэтому лучшее, что вы можете сделать, это "оценить 1000 шагов этого результата". ¹ Но если вы добавите такое ограничение, что если вы компилируете программу для запуска на кластере суперкомпьютера с терабайтами ОЗУ, а компилятору не хватает памяти?

Вы можете добавить множество ограничений, но в конечном итоге вы уменьшите оптимизацию до медленной формы постоянного свертывания (особенно для большинства программ, вычисления которых зависят от пользовательского ввода во время выполнения). И с тех пор sum [1..10000000] здесь занимает полсекунды, вряд ли это подпадет под какой-либо разумный предел.

Конечно, конкретные случаи, подобные этому, часто можно оптимизировать, и GHC часто оптимизирует такие сложные выражения, как это. Но компилятор не может просто безопасно вычислить любое выражение во время компиляции; оно должно быть очень ограниченным, и можно поспорить, насколько полезным оно будет при этих ограничениях. Это компилятор, а не интерпретатор:)

¹ Это может значительно замедлить компиляцию любой программы, которая содержит много бесконечных циклов - что, поскольку Haskell не является строгим, более вероятно, чем вы думаете). Или, чаще, любая программа, которая содержит много длительных вычислений.

Answer 2

Общим ответом на выполнение вычислений во время компиляции является использование 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 3

Похоже, работа для суперкомпиляции! Этот вопрос звучит как его описание, а обсуждение вопроса о недопущении отражает проблемы, с которыми сталкиваются разработчики суперкомпиляторов. В вики GHC я видел, что кто-то работает над производственным суперкомпилятором, но не знаю, что с этим случилось.