-allow-extension-for-bottom

[Serge D. Mechveliani]

First, thanks to the people who correct me about `equivalence',
(I skip the name because the letter was addressed privately).

Because we do not mean to compile each program to the equivalent
one of
        error "bottom"


On Mon, Oct 11, 2004 at 12:44:49PM +0100, Simon Peyton-Jones wrote:
> Can you give a small program that runs 1000x faster in one form compared
> with the other?
> 
> Currently, if foo is strict, GHC transforms (2) into (1), not the other
> way round. In general, transforming (1) into (2) looks hard, because it
> means finding the common portions of two expressions.   

Anywhay, this looks like an appropriate business for a clever 
compliler (under some option).

> But I'd be
> interested to see cases where you get a lot of performance from such a
> transformations.
> 
> Simon
> 


I my recent practical example, the program with the factored `if' 
prints out in 1 second a very useful information on the first 
`steps' of a certain proof (the last steps take long),
while the unfactored version holds the whole result until 30 seconds. 
But this is on the toy example. In practice, this may be, say, 
100 hours, because the prover is allowed and expected to think long. 
The simplified version of the program is 

  main = hSetBuffering stdout NoBuffering >> putStr (out "\n")

  out :: String -> String

  out = let valueTakingLong =  last [1 .. (10^7)]  > 0
        in
        if  valueTakingLong  then  ('a' :) . ('b' :)
        else                       ('a' :) . ('b' :)

The author intended 'a' to appear immediately.
But it appears only after a long time.

This is hard to control such things in practice,
one has to take effort to write the factored program.
And usually, this is immaterial whether in  (if p x)  
(p x)  may yield bottom.  

I suspect that
(1) the example can be changed so that the full evaluation time 
    difference will be 1000 times
    (somewhat apply `head' to the above `if' expression ...)

(2) this concerns not only the `if' factoring, this effects the 
    `bottom' treating in general.

What do you think of this?

-----------------
Serge Mechveliani
mechvel at botik.ru



> | -----Original Message-----
> | From: glasgow-haskell-users-bounces at haskell.org
> [mailto:glasgow-haskell-users-
> | bounces at haskell.org] On Behalf Of Serge D. Mechveliani
> | Sent: 11 October 2004 12:22
> | To: haskell at haskell.org
> | Cc: glasgow-haskell-users at haskell.org
> | Subject: -allow-extension-for-bottom
> | 
> | Dear Haskell implementors,
> | 
> | Consider the compilation flag  -allow-extension-for-bottom
> | 
> | which changes the language meaning so that allows to ignore
> | the bottom value. For example, the programs
> | 
> |    (1)   (\ x -> (if p x then  foo (g x)  else  foo (h x)) )
> | and
> |    (2)   (\ x -> foo ((if p x then  g x  else  h x)) )
> | 
> | become equivalent, and many program transformations become
> | possible.
> | I suspect that after compiling and running of a program under
> | -allow-extension-for-bottom  the user will discover many helpful
> | information about the original program.
> | For example, under  -allow-extension-for-bottom  it may run 1000
> | times faster, and then, the user finds out what to change to have
> | a 1000 times speed-up for the original program for the standard
> | Haskell.
> | 
> | Thus, in my particular practical example, it is evident to me that
> | it is better to specify (2). But many similar effects are hard to
> | find out without compiling under  -allow-extension-for-bottom.
> | 
> | Maybe, the compiler could issue the warnings like, say,
> | 
> |   "Consider factoring `if' in ...   This may improve ... "
> | ?
> | 
> | Copy, please, the answer to  mechvel at botik.ru,
> | 
> | -----------------
> | Serge Mechveliani
> | mechvel at botik.ru
> | 
> | 
> | 
> | 
> | _______________________________________________
> | Glasgow-haskell-users mailing list
> | Glasgow-haskell-users at haskell.org
> | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>