[plt-scheme] Re: to define, or to let (last try)

From: Bradd W. Szonye (bradd+plt at szonye.com)
Date: Tue Apr 27 14:48:56 EDT 2004

Paul Schlie wrote:
> In turn, let me try for the final time to dispel some rumors:
> - all programs which abide by scheme's syntax are "correct", regardless
>   of their usefulness (and/or ambiguity under R5RS specifications).

That isn't true for any reasonable meaning of the word "correct." It's
bad enough when people claim that a program is correct so long as a
Scheme interpreter accepts it, but now you're claiming that programs are
correct so long as Scheme's *parser* accepts them!

Scheme imposes semantic requirements on programs, not just syntactic
requirements. One of those semantic requirements is that programs must
not depend on the order of argument evaluation, because that order is

> - the present order-of-evaluation ambiguity as presently specified by
>   R5RS doesn't "assert" anything ....

When an R5RS program uses LET, it asserts that it obeys R5RS's rules for
the use of that construct, including the order of evaluation rules.
Specifically, a correct R5RS program cannot depend upon the order of
evaluation, because R5RS does not specify it.

> - if there is a community interest in enabling scheme to specify
>   immutable functions (i.e. functions which are warranted not to be
>   dependant on locally persistent, or externally mutable state) for the
>   nicety of it, for which violations must be detected, then it should be
>   addressed directly, not by attempting to argue for unspecified
>   evaluation order which only ironically enables such function use to be
>   potentially ambiguous, but not deterministically so from implementation
>   to implementation, to no-ones benefit; nor as easily diagnosed as an
>   immutable function definition/assertion would be (which although would
>   be nice, it's not as truly as necessary as eliminating R5RS's presently
>   unspecified evaluation order ambiguity is, as mutable functions are both
>   useful and occasionally necessary, and corresponding their use should not
>   yield ambiguous results under any circumstances).

First, I'd appreciate it if you'd quit repeating this garbage about
unspecified evaluation order being "to no-ones benefit." Several people
have clearly explained its benefits. You may not feel that the benefits
are worth the cost to you personally, but it's ridiculous to claim that
there are no benefits at all.

Second, the alternative construct you propose is either useless or
impossible to implement. It's generally impossible to determine whether
a function logically depends on side effects. You can prove order
independence in many cases, however, by using appropriate domain
knowledge (e.g., by knowing that + and * are commutative). Or you can
enforce it by disallowing side effects entirely, but that's useless for
Scheme since just about everything requires memory allocation.

If you give up the undecidable requirement to detect all violations,
then your construct is reasonable -- but it's also equivalent to R5RS
LET, LETREC, etc. Why bother re-inventing something we already have?

Finally, your proposal makes sequential behavior the "default." Since
non-sequential algorithms work in any order, including the sequential
"default," there's less incentive to explicitly declare which parts of
the program are non-sequential. Based on my experience, most programmers
simply won't bother, which makes review, testing, and maintenance more
difficult. It encourages poor design and coding.

> - still waiting to see someone produce a explicit code fragment which
>   demonstrates the value of unspecified evaluation order, as many counter
>   examples have already been produced. If none can be produced, then maybe
>   it's perceived merits should be reconsidered.

We've already done that, Paul. Like I said before, just because *you*
don't see the value in it doesn't mean that there is no value. Your own
example below demonstrates the benefit of unspecified evaluation order!

>   For the record:
>    (define (first x y) x)
>    (first (read) (read))
>    is both a "correct" and needlessly ambiguous program under R5RS's
>    present specification, and not easily diagnosable as being
>    otherwise.

If you care about the return value of FIRST, that is *not* a correct
R5RS program, because it depends upon specific behavior even though the
behavior is unspecified. It's only correct if you don't care about the
return value, because then you're getting what you want: an unspecified
value. Correct programs must explicitly declare where they depend on a
specific sequence, by using LET* or similar constructs.

Those facts have value: Code reviewers can easily spot where sequencing
matters and where it doesn't. Testers can use automated tools to verify
that the program as coded matches the design requirements. Maintainers
can spot where it's safe to reorder and refactor code. Optimizers can
use the information to set up more efficient call sequences.

We've seen concrete examples for some of these benefits. Anton wrote
BrBackwards to check order independence. The SISC interpreter uses a
custom evaluation order to reduce the cost of continuations.

The unspecified order advocates have already demonstrated these
advantages to you in this and other forums, Paul. I've cited several
excellent programming style and process guides that assert the value of
encoding a program's sequentiality requirements. If you refuse to see
that value, that's your prerogative, but kindly refrain from claiming
that nobody has demonstrated it.
Bradd W. Szonye

Posted on the users mailing list.