Re: More on Full Specification

[willc@tekchips.crl]

	    No, not concurrently.  E*, in the semantics, always evaluates in
	    *some* order.  This isn't overspecification, as Paul Hudak suggests
	    ,but rather a deliberate and desirable design decision.
	
	I wasn't around when the decision was made, so can't say whether it
	was "deliberate" or not, but in what sense is it "desireable"?

The decision was made deliberately, and the argument that carried the day
for requiring that the evaluation happen in some unspecified but sequential
order is the fact that code such as Eric's splay-tree example would break in
the presence of concurrent evaluation unless it was protected by critical
sections, which nobody wanted to deal with.  I was the pretty much the only
person at Brandeis who really wanted to allow concurrent evaluation.

My reading of the report is that the requirement for sequential execution
makes it illegal to evaluate the common subexpression (car x) only once in
the following expression unless it can be proved that at least one of the
procedures goo and moo do not change the car field of x:

  (foo (goo (car x)) (moo (car x)))

  My bet is that Will, when designing the denotational semantics,
  specified the underspecification in the simplest deterministic way he
  could think of, and that's to use something like PERMUTE.  If there
  was a clean way to specify non-determinism, including the
  inter-leaving of evaluations, then perhaps he would have chosen that.

This is correct.  I felt that Scheme is so close to a deterministic
language that the greater accuracy of a non-deterministic semantics
was less important that the greater clarity of a deterministic semantics.

    I guess the bottom line is that we should be VERY careful about what
    things we choose to underspecify, and how.  These decisions can have
    radical effects on portability and correctness.  I think that the
    default should be full specification, and that anything left
    underspecified should have a very good rationale.

I agree with this and I generally agree with Robert Hieb's analysis.
I happen to think, however, that the three concrete underspecifications
that Hieb proposed to fix (value returned by side-effecting procedures,
order of evaluation of arguments, order of evaluation of definitions)
are among the most justified underspecifications in all of Scheme.  Each
of these underspecifications concerns something that programmers ordinarily
do not care about because it doesn't matter; they have the effect of
requiring programmers to write some explicit code in the exceptional case
when they do want to use a specific value or order of evaluation.  If
these underspecifications were "fixed", programs would be harder to read
because you would have to assume that the order matters whenever you see
a procedure call or internal definitions.  As things stand now, you know
the order doesn't matter and this fact makes it easier to understand the
program.

In my opinion, the language would be improved if side-effecting procedures
had to return #!unspecified.  This issue is a little different from the
order of evaluation of arguments and the order of definitions because it
is often (i.e. except for tail-recursive positions) obvious that the value
returned by a side-effecting procedure is just thrown away.  Furthermore we
probably could standardize on some useless value like #!unspecified or 34
if only we could agree, but the perceived need for compatibility with
previous implementations or with Common Lisp makes it difficult for us to
agree.

Peace, Will