[mercury-users] Mercury and imperative programming

[Richard A. O'Keefe]

	Mercury already allows side-effecting I/O at the uniquely-moded,
	deterministic top-level of control.  And it also allows
	destructive update, both at the uniquely moded top-level and in
	mostly uniquely-moded nondeterministic code.

	Why not, then, support full-blown imperative-style programming,
	with familiar imperative syntax (e.g., x:= x+1, array[i]:= x,
	WHILE loops, and FOR statements) in these contexts?  This would
	greatly increase the marketability of Mercury.
	
_Would_ it?

O'CAML allows ``expressions'' like
	let x = a.[i] and y = a.[j] in
	begin a.[i] <- x; a.[j] <- y end
and it DOES have
	while <expr> do <expr>
and	for <id> = <expr> {to/downto} <expr> do <expr>
so you can for example do matrix multiplication as
	for i = 1 to m do
	    for j = 1 to n do
	        let s = ref 00 in begin
	            for k = 1 to p do
			s := !s + a.[i].[k] * b.[k].[j];
	            c.[i].[j] <- !s
	        end

O'CAML has Windows, UNIX, and MacOS implementations, one of the best
compilers around, a powerful object oriented system, a neat Tk-based
GUI kit, lots of good stuff, AND you can treat it pretty much like
Pascal if you really want to.

But I *DON'T* see any rush to O'CAML.  If familiar imperative
syntax would greatly increase the marketability of Mercury,
why hasn't it done any such thing for O'CAML?  The CAML
implementations have been around a lot longer than Mercury has,
so there has been *time* for this wonderful marketability
increase to bear fruit.  But it just plain HASN'T.

Let's face it, anyone shallow enough to swayed by conventional
WHILE and FOR statements already has a wide range of languages
to choose from, including some (like Java) that will look better
on his CV.  Why would anyone choose an unhyped language like
Mercury over a widely hyped language like Java unless they
were interested in finding out what can be accomplished by
doing things DIFFERENTLY?

For what it's worth, I'm currently taking the 1996 New Zealand
Programming Contest problems and writing them up with C and
Haskell solutions.  The Haskell solutions (with never an assignment
statement in sight; Haskell being a relentlessly pure functional
language) are consistently about half the size of the C versions,
and I'm a better C programmer than a Haskell programmer.  Mercury
versions would be somewhere in between, because (a) I've omitted
type specifications whenever I possibly could and (b) I've relied
heavily on higher-order functions.  Come to think of it, so far
the I/O has been easier in Haskell than in C.

	I think declarative programmers need to get away from the
	puritanical idea that assignment and side effects are somehow
	impure and dirty.

I don't think you understand declarative programmers.
Clean/Haskell/Mercury programmers don't think assignments and
side effects are _dirty_ (although they are, by definition,
impore), they think those things are
 - DANGEROUS, and
 - UNNECESSARY.
The danger of side effects is I think beyond dispute; Java pays
a heavy run-time cost to avoid some of the worst problems.
And if you want to convince me that assignments and side effects
are necessary, you'll have to show me imperative code (ok, ok,
imperative code other than APL or J) easier to develop than my
functional code.

	These features have their legitimate uses and their own
	respectable semantics (e.g., bisimulation and predicate
	transformers).

Erk.  I've supervised a Masters student who did some bisimulation
proofs, and I've read some of the literature.  Bisimulation may be
as respectable as you please, EASY TO USE it definitely is NOT.
As for predicate transformers, I'm a fan of them from way back,
BUT with the exception of Euclid, Turing, and Dijkstra's notation,
I'm not aware of any practical notation in which they can actually
be *used*.  Of course, I _am_ behind the times.  How _do_ people
use predicate transformer semantics with (for argument's sake) Java?  

	In any case, Mercury already allows side effects.

Not if you don't plug in bits of C code.  If you stick to plain
Mercury, your program is a relation between an initial and a final
state of the world, and there are no *internal* side effects that
can disrupt the semantics.

	Another advantage would be that one could then use Mercury as a
	nondeterministic imperative langyage (like C with backtracking).
	Compare:  Siskind's Screamer (nondeterministic Scheme).
	
Thanks, but I *have* Screamer.  Here's an exercise for the reader
(ok, I didn't understand this either until Jeff sent me the explanation).
Here are three ways to implement MAP in Scheme:

    (define (MAP1 F L)
      (if (pair? L)
      (cons (F (car L)) (MAP1 F (cdr L)))
      '()))

    Obvious but not tail recursive.  So

    (define (MAP2 F L)
      (let LOOP ((L L) (A '()))
        (if (pair? L)
	    (LOOP (cdr L) (cons (F (car L)) A))
            (reverse A))))
    
    Turns out to be faster than MAP1, but has to reverse that
    list, taking time and turning over storage.  Try again.

    (define (MAP3 F L)
      (let ((DUMMY (list #f)))
        (let LOOP ((E DUMMY) (L L))
	  (if (pair? L)
              (begin
		(set-cdr! E (list (F (car L))))
		(LOOP (cdr E) (cdr L)))
	      (cdr DUMMY)))))

    Most efficient of all.  Basically, we're mimicking the way Prolog
    or Mercury would handle this.  In Scheme we have to introduce one
    dummy node, but that's better than introducing N of them.

In the absence of backtracking (or the call-with-current-continuation
primitive used to implement it), these three implementations cannot
be distinguished.  In the *presence* of backtracking, what happens
and why?  Yes, one of the Scheme systems he put Screamer on top of
did use one of these implementations, and it DID break programs.
And to this day, one of the best Scheme compilers around cannot use
a certain optimisation because it's incompatible with call/cc.

Icon also provides backtracking in a basically imperative language,
and it too can suffer from this kind of problem.  You really DON'T
want to mingle backtracking and side effects if you can avoid it.

--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------