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 <[EMAIL PROTECTED]> 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| [EMAIL PROTECTED]
> than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume
>
> On 23 Aug 2002, Ketil Z. Malde wrote:
>
> > Jan Kybic <[EMAIL PROTECTED]> 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
> > [EMAIL PROTECTED]
> > http://www.haskell.org/mailman/listinfo/haskell
> >
>
> ___
> Haskell mailing list
> [EMAIL PROTECTED]
> http://www.haskell.org/mailman/listinfo/haskell
--
Phil Trinder
Department of Computing and Electrical Engineering
Heriot Watt University
Riccarton
Edinburgh, EH14 4AS
E-mail: [EMAIL PROTECTED]
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
___
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell