7

Let's say we have a program like this :

list = [1..10000000]

main = print $ sum list

I want this to be compiled such that the executable just prints 50000005000000, without taking as much time and effort.

Basically, any expression that will be surely computed (maybe the strictness analysis can help here) can be pre-computed during compilation time (ie we use referential-transparency to say it doesn't really matter when we compute the value).

In short : "has to be computed" + referential-transparency = can be pre-computed

This would be like running the program till we hit something that depends upon the input (i.e. the core of the program, that which is common across all inputs, will be pre-computed)

Is there an existing mechanism to achieve this currently (in Haskell or any other language)? [Please don't point to something like templates in C++ as it doesn't have referential-transparency in the first place.]

If not, how tough is this problem ? [What are the accompanying technical (and theoretical) issues ?]

Karan
  • 559
  • 5
  • 12

3 Answers3

12

This is not safe in the general case. The reason is that Haskell expressions may be pure, but they can also fail to terminate. The compiler should always terminate, so the best you could do would be "evaluate 1,000 steps of this result".1 But if you do add such a limit, what if you're compiling a program to run on a supercomputer cluster with terabytes of RAM, and the compiler runs out of memory?

You can add lots of limits, but in the end you'll reduce the optimisation to a slow form of constant folding (especially so for the majority of programs whose computations depend on run-time user input). And since sum [1..10000000] takes half a second here, it's unlikely it'd fall under any reasonable limit.

Of course, specific cases like this one can often be optimised away, and GHC often does optimise away complicated expressions like this. But the compiler can't just evaluate any expression at compile-time safely; it would have to be very constrained, and it's arguable how helpful it would be under those constraints. It's a compiler, not an interpreter :)

1 Which would massively slow down the compilation of any program which does contain a lot of infinite loops — which, since Haskell is non-strict, is more likely than you might think). Or, more commonly, any program which contains a lot of long-running computations.

ehird
  • 40,602
  • 3
  • 180
  • 182
  • well we can have a limit on time and space usage – Karan Apr 10 '12 at 18:03
  • I've expanded my answer to explain why that probably wouldn't help, and would likely cause the optimisation to not help for this example. – ehird Apr 10 '12 at 18:06
  • Well the time and space limits were basically for user convinience; but for expressions that /have to be computed/, it doesn't matter if they cause massive space/time explosion because that will appear anyways (it's your choice : run-time or compile-time). – Karan Apr 10 '12 at 18:17
  • as for infinite loops, let's take lists defined like `ones = 1:ones`, here only the parts that are surely needed are computed; for example if `ones!!72` will surely be computed, the just find it during compile-time – Karan Apr 10 '12 at 18:19
  • 1
    True and very well explained. Still, I'm sometime wanting GHC to reduce expressions at compile-time, very often when dealing with values construction from literal conversions, for example `fromString "long string literal in i18n module"`. Perhaps GHC already does the job, but I don't know how to be sure. – Paul R Apr 10 '12 at 18:21
  • Could it be done in a dependently typed language where you have to prove termination? – glaebhoerl Apr 10 '12 at 20:22
  • @illissius: Sure; you don't even need dependent-types if your language is [total](http://en.wikipedia.org/wiki/Total_functional_programming). However, it still has all the other problems I mention; you probably don't care about the difference between "this code never finishes compiling" and "this code takes a year to compile". – ehird Apr 10 '12 at 21:05
11

The general-purpose answer to doing compile-time computation is to use Template Haskell. But for this specific use case, you can use the vector package and the LLVM backend, and GHC will optimize away this sum.

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

(In case it's not immediately obvious, 0x2d79888896b40 is 50000005000000.)

Daniel Wagner
  • 145,880
  • 9
  • 220
  • 380
  • can you briefly explain why ghc is able to optimise for vectors here and not for lists ? (and if llvm is the reason for this magic; can we borrow that kind of logic from there to ghc?) – Karan Apr 10 '12 at 18:25
  • 3
    The vector library includes library-specific rules that teach the compiler how to optimize the code. – Don Stewart Apr 10 '12 at 18:32
  • @DanielWagner : `main = print (V.sum $ V.map (^2) $ V.enumFromN (1 :: Int) 10000000)` takes more time; and if I change it to 100000000 (10^8), it takes 10 times as much time !! – Karan Apr 10 '12 at 18:48
  • 1
    @Karan I've seen your comment, and have the feeling you're hoping for a followup, but not sure what to say that won't simply be repeating things from my answer above. If you do more computation, it's less likely it can be optimized away, even by the best optimizing compilers. For these cases, as I said in my answer above, the general-purpose solution is to use Template Haskell. – Daniel Wagner Apr 11 '12 at 20:57
  • @DanielWagner : Thanks for the follow-up :) . But I don't want to use Template Haskell as I think (or thought) this is something GHC should be able to optimize by itself (but it seems I am wrong). – Karan Apr 12 '12 at 11:30
1

Sounds like a job for Supercompilation! The question sounds like a description of it and the discussion of nontermination mirrors the issues faced by supercompiler developers. I saw on the GHC wiki that someone was working on a production supercompiler for it but don't what's become of that.

GarethR
  • 724
  • 5
  • 7
  • hey thanks for adding the term "supercompilation" to my vocabulary :) – Karan Apr 12 '12 at 11:32
  • but I think supercompilation is more ambitious than what I want here; maybe more of http://en.wikipedia.org/wiki/Partial_evaluation where (Input_static) = NULL (but when Input_dynamic has no effect on output; it's like you know everything already and can run your program at compile-time itself) – Karan Apr 12 '12 at 11:36
  • 1
    Oh that's a great link - gotta love wikipedia. According to this paper, supercompilation and partial evaluation are strongly related, see http://research.microsoft.com/en-us/um/people/simonpj/papers/supercompilation/design-space.pdf. No compiler will do an arbitrarily large computation at compile time, as others have stated, not only because it's impossible in the general case but also because the compiler writer can't make that trade on your behalf. – GarethR Apr 13 '12 at 00:39