Pragmatic concurrency Re: [Haskell-cafe] multiple computations, same input

Robin Green greenrd at greenrd.org
Wed Mar 29 09:23:04 EST 2006


On Wed, 29 Mar 2006 12:50:02 +0100
Jon Fairbairn <jon.fairbairn at cl.cam.ac.uk> wrote:
> There are some observations I'd like to make, and a
> proposal. Since the proposal relates (in a small way) to
> concurrency and is, I think worthwhile, I've cc'd this
> message to haskell-prime.
> 
> 1) choosing the optimal reduction strategy is undecidable
> 
> 2) we shouldn't (in general) attempt to do undecidable
>    things automatically
> 
> 3) Separation of concerns: Pragmatic decisions about
>    evaluation order should be kept separate from the
>    denotational aspect of the code. By this token, seq
>    shouldn't be a function (because it isn't one), but a
>    pragma.  The fact that it's shorter to write seq a b than
>    {-# SEQ a #-} b is a matter of syntax, so shouldn't rate
>    highly in language design decisions. Perhaps we want a
>    different syntax for this kind of pragma, but that's a
>    side issue.

I don't like pragmas because (at least in C) they are defined to be
optional and can be ignored by the compiler. We need optimisation
methods that work across all Haskell implementations (of a given
Haskell standard).

I suggest that a Haskell program should be treated as an executable
specification. In some cases the compiler can't optimise the program
well enough, so we (by which I mean, ordinary programmers, not compiler
geeks) should be able to explicitly provide our own optimisations, as
rewrite rules (generalised ones, or specialised ones for individual
functions). Democratise the means of automated optimisation! Then we
should be able to prove formally that our rewrite rules preserve
functional correctness. This is the approach I am pursuing in the
programming language I am working on, which is a derivative of Haskell.

(In principle you could write rewrite rules in Template Haskell, but I
don't know if anyone has tried that.)

This way of looking at it is nice, because then we don't have to shut
off whole avenues of fruitful thought, on the grounds of "Oh no, the
compiler is far too stupid to do that", or "Oh no, that's far too much
of a special case for this particular example, and it would bloat the
compiler too much to include little things like this".

The way I would optimise the wc example in my language is as follows:

First translate it into a monadic pipeline in the State monad:

wc = evalState $ do
	w <- passthru (length . words)
	l <- passthru (length . lines)
	c <- passthru length
	return (w,l,c)
	where
		passthru = gets

Then convert that monadic action into a semi-lazy imperative pipeline on
lists (semi-lazy because the pipeline is evaluated lazily, but the
side-effects of the pipeline are evaluated strictly - or something
like that - I have difficulty explaining it). This is too involved to go
into here (and I haven't worked out the details of the rewrite rules
yet), but the basic idea looks like this pseudo-shell-script:

words -output w | lines -output l | length -output c >/dev/null
echo "(`cat w`, `cat l`, `cat c`)"
rm -f w l c

Each command in the first line of this pseudo-shell-script copies its
list from standard input to standard output, and stores its result in a
temporary file named by the -output option. (Obviously, in the real
code, temporary files wouldn't be used, and nor would operating system
pipes be used - I just found them convenient in order to analogise my
solution as a shell script.)

Despite the apparent waste of copying a list three times, this is
actually more efficient than the original code because it doesn't need
to store any lists in memory.

There might be better ways to do it, but that's just an idea off the top
of my head.
-- 
Robin


More information about the Haskell-Cafe mailing list