aide-transparence référentielle pré-calcul des valeurs dans haskell

Question

Disons que nous avons un programme comme celui-ci:

list = [1..10000000] 

main = print $ sum list 

Je veux que cela soit compilé tel que l'exécutable qu'afficher 50000005000000, sans prendre autant de temps et effort.

Fondamentalement, toute expression qui sera sûrement calculée (peut-être l'analyse de rigidité peut aider ici) peut être précalculée lors de la compilation (par exemple nous utilisons-transparence référentielle dire qu'il n'a pas vraiment d'importance quand on calcule la valeur).

En bref: « doit être calculée » + référentielle transparence = peut être pré-calculé

Ce serait comme l'exécution du programme jusqu'à ce que nous avons touché quelque chose qui dépend de l'entrée (le noyau de le programme, ce qui est commun à toutes les entrées, sera pré-calculé)

Existe-t-il un mécanisme existant pour le faire actuellement (dans Haskell ou dans une autre langue)? [S'il vous plaît ne pointez pas quelque chose comme des modèles en C++ car il n'a pas de transparence référentielle en premier lieu.]

Si non, quel est le problème de ce problème? [Quels sont les problèmes techniques (et théoriques) qui l'accompagnent?]

Answer 1

La réponse générale au calcul à la compilation est d'utiliser Template Haskell. Mais pour ce cas d'utilisation spécifique, vous pouvez utiliser le package vector et le backend LLVM, et GHC optimisera cette somme.

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 

(Dans le cas où il est pas évident, 0x2d79888896b40 est 50000005000000.)

Answer 2

Ce n'est pas sûr dans le cas général. La raison en est que les expressions Haskell peuvent être pur, mais ils peuvent également ne pas se terminer. Le compilateur devrait toujours se terminer, donc le mieux que vous pourriez faire serait "évaluer 1000 étapes de ce résultat". Mais si vous ajoutez une telle limite, que se passe-t-il si vous compilez un programme à exécuter sur un cluster de superordinateurs avec des téraoctets de RAM et que le compilateur manque de mémoire?

Vous pouvez ajouter beaucoup de limites, mais à la fin vous réduirez l'optimisation à une forme lente de pli constant (particulièrement pour la majorité des programmes dont les calculs dépendent de l'entrée de l'utilisateur au moment de l'exécution). Et puisque sum [1..10000000] prend une demi-seconde ici, il est peu probable qu'il tombe sous une limite raisonnable.

Bien sûr, des cas spécifiques comme celui-ci peuvent souvent être optimisés, et GHC optimise souvent les expressions complexes comme celle-ci. Mais le compilateur ne peut pas évaluer n'importe quelle expression à la compilation en toute sécurité; il faudrait que ce soit très limité, et on peut soutenir que cela serait utile dans le cadre de ces contraintes. Il est un compilateur, pas un interprète :)

qui ralentirait massivement sur la compilation d'un programme qui ne contiennent beaucoup de boucles infinies - qui, depuis Haskell est non stricte, est plus probable qu'improbable tu pourrais penser). Ou, plus communément, tout programme qui contient beaucoup de calculs de longue durée.

Answer 3

Cela ressemble à un travail pour Supercompilation! La question ressemble à une description de celle-ci et la discussion sur la non-terminaison reflète les problèmes rencontrés par les développeurs de super-compilateurs. J'ai vu sur le wiki de GHC que quelqu'un travaillait sur un super-compilateur de production pour cela, mais ce n'est pas ce qui est devenu.