Questions prompted by the "Excessive Sharing" section, page 405, of SPJ's
"The Implementation of Functional Programming".
This section gives 2 variations of a power list function, semantically
equivalent, but with different space behaviours. Paraphrasing, given a
caller of "length (powerListXXX [1..20])", the powerListBad version gobbles
more and more space as execution proceeds, whilst the powerListGood version
runs in a small amount of constant space. Confirmed under GHC 6.2.2 with
-O2.
powerListBad [] = [[]]
powerListBad (x:xs) = pxs ++ map ((:) x) pxs
where (x:xs) pxs = powerListBad xs
powerListGood [] = [[]]
powerListGood (x:xs) = powerListGood xs ++ map ((:) x) (powerLIstGood xs)
Clearly, in this instance GHC is not transforming either of these
definitions into the other. But are there other compile time transformations
performed by GHC that might result in more (excessive) sharing, in
particular the creation of new common sub-expressions such as pxs? If not,
is that a deliberate design decision?
Since I guess the "excessive" bit of excessive sharing probably can't be
determined until run-time, would it be practical for the run-time system to
do something about it? For example, once the run-time system notices that
the graph size has breached a certain threshold it begins to decouple
references to "reduced" but bulky sections of the graph, forcing them to be
recomputed (from the original expression) at a later time.
_________________________________________________________________
Is your PC infected? Get a FREE online computer virus scan from McAfee®
Security. http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963
_______________________________________________
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
