On Wed, 29 Mar 2006 12:50:02 +0100
Jon Fairbairn
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