Strictness confusion

[Simon Peyton-Jones]

Interesting:

1.   When GHC decides that 'foo' is strict, it does not *require* that
every caller must evaluate the argument before the call.  So GHC does
not assume that foo always gets an evaluated argument.  Indeed, if GHC
sees the call (foo v), where foo is strict, it does not evaluate v
before the call.  Nor in the case of (map foo xs).

2.  When GHC sees 
	case x of
	    pat -> .....(case x of DEFAULT -> e)...
	    ...
it removes the (case x of DEFAULT ->), because it can "see" that x is
already evaluated. [A 'seq' turns into one of those (case x of DEFAULT)
things.]  This transformation is done by the simplifier, which keeps an
environment mapping variables to information about their degree of
evaluation.

However, if the outer case was
	case (f x) of
	   pat  -> ...
then GHC does not record anything about x, even if f is strict.  I guess
it could, by making use of f's strictness information.

But then what about 
	case (f (g x)) of ...
where both f and g are strict?  Etc.  

One could imagine either 
a) Beefing up the existing simplifier optimisation in a relatively ad
hoc way.
    Advantage: applies even if the (case x of DEFAULT) thing shows up
much later
    Disadvantage: probably a bit ad hoc, and the simplifier is already v
complicated

b) Adding a new top-down sweep to the strictness analyser.  Actually it
could be
    done separately  from strictness analysis, but would use much of the
same code
    (e.g. "what demand is placed on x by evaluating (f (g x))?").
    Advantage: doesn't complicated the already-complex simplifier
	The new pass ("case optimisation", perhaps) could remove some
stuff
	from the too-complex simplifier
    Disadvantage: a new pass


I'm not terribly inclined to do this myself, unless someone convinces me
that there are big gains to be had, but I'd be happy to support someone
who already knows GHC a bit (Ian?) if you want to have a go.

Simon



| -----Original Message-----
| From: glasgow-haskell-users-bounces at haskell.org
[mailto:glasgow-haskell-users-
| bounces at haskell.org] On Behalf Of Ian Lynagh
| Sent: 25 June 2004 02:39
| To: glasgow-haskell-users at haskell.org
| Subject: Strictness confusion
| 
| 
| Hi all,
| 
| If I have the following module:
| 
| ----------8<--------------------8<----------
| module Q (foo) where
| 
| foo :: String -> [String] -> Bool
| #ifdef FIRST
| foo x _ | x `seq` x == "." = True
| #else
| foo x _ |         x == "." = True
| #endif
| foo x xs = x `seq` any (x ==) xs
| ----------8<--------------------8<----------
| 
| then I would expect the code to be identical regardless of whether
FIRST
| is defined or not. However, the following shows that (without the
first
| seq) GHC forces the evaluation of x due to the seq in the last line.
| But, as I understand it, it should know that x has already been
| evaluated (to WHNF). This also seems to affect what gets inlined in
| larger examples.
| 
| Am I confused?
| 
| $ rm -f *.o
| $ /usr/bin/ghc -ddump-simpl -cpp -O -c Q.hs -DFIRST > 1
| $ rm -f *.o
| $ /usr/bin/ghc -ddump-simpl -cpp -O -c Q.hs > 2
| $ diff -u1000 1 2
| --- 1   Fri Jun 25 02:11:46 2004
| +++ 2   Fri Jun 25 02:12:02 2004
| @@ -1,32 +1,34 @@
| 
|  ==================== Tidy Core ====================
|  Q.a :: GHC.Base.Char
|  [GlobalId]
|  NoCafRefs Str: DmdType m
|  Q.a = GHC.Base.C# '.'
| 
|  Q.lvl :: [GHC.Base.Char]
|  [GlobalId]
|  NoCafRefs Str: DmdType
|  Q.lvl = GHC.Base.:
|           @ GHC.Base.Char Q.a (GHC.Base.[] @ GHC.Base.Char)
| 
|  Q.foo :: GHC.Base.String -> [GHC.Base.String] -> GHC.Base.Bool
|  [GlobalId]
|  Arity 2 NoCafRefs Str: DmdType SL
|  Q.foo = \ x :: GHC.Base.String ds :: [GHC.Base.String] ->
|           case GHC.Base.eqString x Q.lvl of wild {
|             GHC.Base.True -> GHC.Base.True;
|             GHC.Base.False ->
| +             case x of tpl { __DEFAULT ->
|               GHC.List.any
|                 @ GHC.Base.String
| -               (\ ds1 :: GHC.Base.String -> GHC.Base.eqString x ds1)
| +               (\ ds1 :: GHC.Base.String -> GHC.Base.eqString tpl
ds1)
|                 ds
| +             }
|           }
| 
| 
| 
| 
|  ==================== Tidy Core Rules ====================
| 
| 
| $
| 
| 
| Thanks
| Ian
| 
| _______________________________________________
| Glasgow-haskell-users mailing list
| Glasgow-haskell-users at haskell.org
| http://www.haskell.org/mailman/listinfo/glasgow-haskell-users