A: Evaluation order, ghc versus hugs, lazy vs. strict

[Phil Trinder]

Dear All,

Hal's comments on the use of Evaluation Strategies for controlling 
strictness are substantially right, and they are used this way in Eden, a 
parallel Haskell. In Glasgow parallel Haskell(GpH) we use them to control 
parallel evaluation as well. The key reference is 
  Algorithm + Strategy = Parallelism, Journal of Functional Programming, 
  8(1):23--60, January 1998.
  http://www.cee.hw.ac.uk/~dsg/gph/papers/

Highlights are as follows. There are three basic strategies: 

r0, rwhnf, rnf :: Strategy a
r0 - does no evaluation, 
rwhnf - reduces it's argument to Weak Head Normal Form (WHNF). Hal defines this 
  as stratWHNF), and 
rnf - reduces it's argument to normal form (i.e. containing no redexes). It's 
  defined in a class similar to the Eval class

Strategies can be composed, e.g. seqList applies a strategy to every element of 
a list:

seqList :: Strategy a -> Strategy [a]
seqList s [] = ()
seqList s (x:xs) = s x 'seq' (seqList s xs)

so

seqList r0 :: Stratgy [a]    - evaluates just the spine of a list
seqList rwnf :: Strategy [a] - evaluates every element to WHNF
seqList (seqList r0) :: Strategy [[a]]  
                             - evaluates just spines of every sublist in a list 
                               of lists

Analogous parallel strategies, like parList, also exist.

The Strategies.lhs module is distributed with GHC (since version 0.29), so 
simply 'import Strategies' if you want to play.

HTH

Phil
On Fri, 23 Aug 2002 05:10:05 -0700 (PDT) Hal Daume III <hdaume@ISI.EDU> wrote:

> I think there's more to strategies than this.  They are not necessarily
> related to parallel programming and can be used for tuning (in the seq
> sense) "sequential" (perhaps "non-parallel" would be a better
> word) programs.
> 
> The type of strategies is:
> 
>   type Strategy a = a -> ()
> 
> for example, a strategy which reduces its argument to weak head normal
> form could be given by:
> 
>   stratWHNF x = x `seq` ()
> 
> We define a funciton 'using' which uses strategies to do a computation:
> 
>   v `using` s = s x `seq` x
> 
> These are used in parallel programming something like:
> 
>   fib 0 = 1
>   fib 1 = 1
>   fib n = a + b `using` strategy
>     where a = fib (n-1)
>           b = fib (n-2)
>           strategy result = a `par` b `par` result
> 
> This clearly separates the computation "a+b" from the way it is evaluated
> "a in parallel to b in parallel to the result (i.e., a+b)".
> 
> But this can of course be used for sequential programming, too, simply by
> using seq instead of par in the above example.  This enables you to write
> clean code (your functions stay the same, except they are appended with
> `using` strategy), but you can control more precisely when things get
> reduced.
> 
>  - Hal
> 
> --
> Hal Daume III
> 
>  "Computer science is no more about computers    | hdaume@isi.edu
>   than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume
> 
> On 23 Aug 2002, Ketil Z. Malde wrote:
> 
> > Jan Kybic <kybic@ieee.org> writes:
> > 
> > > What are GUM and Strategies? Could you provide any links?
> > 
> >   http://www.cee.hw.ac.uk/~dsg/gph/docs/Gentle-GPH/sec-gph.html
> > 
> > GUM is an implementation of GPH (a parallel Haskell) that
> > runs on top of PVM.
> > 
> > Strategies are about making sure parallel threads actually do the work
> > they're intended to before returning control to the main thread; in
> > other words, ensuring sufficient strictness.  Or something like that.
> > 
> > Grain of salt as applicable, I'm not using any of this yet.
> > 
> > -kzm
> > -- 
> > If I haven't seen further, it is by standing in the footprints of giants
> > _______________________________________________
> > Haskell mailing list
> > Haskell@haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell
> > 
> 
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell

--------------------------------------------------
Phil Trinder
Department of Computing and Electrical Engineering
Heriot Watt University
Riccarton
Edinburgh, EH14 4AS

E-mail: trinder@cee.hw.ac.uk
Teleph: +44 (0)131 451 3435
Depart: +44 (0)131 451 3328
Fasmly: +44 (0)131 451 3327
Intrnt: http://www.cee.hw.ac.uk/~trinder