Referenz-Transparenz Mit to-Pre Rechenwerte in Haskell

Question

Lassen Sie uns sagen, dass wir ein Programm wie dieses:

list = [1..10000000] 

main = print $ sum list 

Ich will das so zusammengestellt werden, dass die ausführbare Datei nur 50000005000000 druckt, ohne so viel Zeit zu nehmen und Anstrengung.

Grundsätzlich jeder Ausdruck, der (hier hilft vielleicht die Strikt Analyse kann) kann sicher berechnet wird seine vorausberechneten während der Kompilierung (dh wir verwenden Referenztransparenz zu sagen, dass es nicht wirklich wichtig macht, wenn wir berechnen der Wert).

Kurz: „muss berechnet werden“ + Referenztransparenz = vorausberechnet

Das ist wie läuft das Programm würde werden können, bis wir etwas, das auf dem Eingang hängt getroffen (dh der Kern das Programm, das, was über alle Eingänge gemeinsam ist, wird im Voraus berechnet werden)

gibt es zur Zeit() in Haskell oder einer anderen Sprache dieses ein bestehender Mechanismus zu erreichen? [Bitte nicht zu so etwas wie Vorlagen in C++, da es nicht referenzielle Transparenz in erster Linie hat.]

Wenn nicht, wie hart dieses Problem? [Was sind die begleitenden technischen (und theoretisch) Fragen?]

Answer 1

Die Allzweck-Antwort auf Kompilierung-Berechnung zu tun ist Template Haskell zu verwenden. Aber für diesen speziellen Anwendungsfall können Sie das Paket vector und das LLVM-Backend verwenden, und GHC wird diese Summe optimieren.

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 

(Im Fall ist es nicht ohne weiteres ersichtlich, 0x2d79888896b40 ist 50000005000000.)

Answer 2

Dies ist im allgemeinen Fall nicht sicher. Der Grund dafür ist, dass Haskell Ausdrücke reine sein können, aber sie können scheitern auch zu beenden. Der Compiler sollte immer beendet werden, also wäre es am besten, wenn Sie "1000 Schritte dieses Ergebnisses auswerten" würden. Aber wenn Sie eine solche Grenze fügen, was ist, wenn Sie ein Programm kompilieren mit Terabyte RAM auf einem Supercomputer-Cluster ausgeführt werden, und der Compiler läuft aus dem Speicher?

Sie können viele Limits hinzufügen, aber am Ende werden Sie die Optimierung auf eine langsame Form der konstanten Faltung reduzieren (besonders für die Mehrheit der Programme, deren Berechnungen von Laufzeit-Benutzereingaben abhängen). Und da sum [1..10000000] hier eine halbe Sekunde dauert, ist es unwahrscheinlich, dass sie unter ein vernünftiges Limit fällt.

Natürlich spezifische Fälle wie diese können oft wegoptimiert werden und GHC tut oft komplizierte Ausdrücke wie diese optimieren entfernt. Der Compiler kann jedoch nicht einfach jeden Ausdruck zur Kompilierzeit auswerten; es müsste sehr eingeschränkt sein, und es ist fraglich, wie hilfreich es unter diesen Bedingungen wäre. Es ist ein Compiler, nicht ein Dolmetscher :)

Welche massiv die Erstellung eines Programms verlangsamen würde die nicht viel Endlosschleifen enthalten -, die seit Haskell nicht streng ist, ist wahrscheinlicher als du denkst vielleicht). Oder, häufiger, jedes Programm, das viele lang laufende Berechnungen enthält.

Answer 3

Klingt wie ein Job für Supercompilation! Die Frage klingt wie eine Beschreibung davon und die Diskussion der Nicht-Terminierung spiegelt die Probleme wider, mit denen Supercompiler-Entwickler konfrontiert sind. Ich habe im GHC-Wiki gesehen, dass jemand an einem Produktions-Supercompiler dafür gearbeitet hat, aber was ist daraus geworden?