[R6RS] Low-impact proposal: Evaluation order directive

[Anton van Straaten]

Against all prudence, I have whipped up a simple (?) proposal which 
shouldn't consume much brain-bandwidth.  If something similar has 
already been considered, or if there other reasons this isn't 
appropriate, I'll drop it.

I've read chunks of the archives, all of the wiki, and the December 
vote.  I was pleased to see the (eventually?) unanimous result of the 
vote on evaluation order.  This proposal doesn't affect that vote.

(Note: this turned into quite an essay, which could certainly be edited 
down if I had more time, but the overall idea should be clear after the
next few paragraphs.)


Evaluation order directive
==========================

It would be useful for Scheme to have a standard directive which 
specifies the order of evaluation required by a piece of code.  This 
ought most likely to be a module- or file-level directive.  The exact 
form which this directive would take are left open, for the moment.

If an implementation supports the evaluation order specified by the 
directive, it would be required to evaluate the code in question using 
the specified order.

The directive would *not* place any requirements on implementations to 
support a particular evaluation order.  However, implementations would 
be required to reject any program which specifies an evaluation order 
which is not supported by that implementation.

This would allow code which depends on, say, left-to-right evaluation to 
declare that fact.  An implementation which doesn't support L2R 
evaluation would be required to refuse to compile or run such code.

The directive would also allow code to explicitly assert that it is 
believed to be independent of any particular evaluation order.  Such 
code would, of course, be accepted by any implementation, regardless of 
an implementation's supported evaluation order(s).

Programs would not be required to specify an order of evaluation.  If no 
order is specified, an unspecified order of evaluation would be used. (I 
claim that the semi-tautological nature of the latter sentence 
demonstrates the logical consistency of this proposal.)

Of course, an implementation which does not guarantee any fixed 
evaluation order would be required to refuse to compile or run any code 
which  specifies a particular order.  Such an implementation should only 
accept code which either has no order directive, or code which uses the 
directive to explicitly specify that it is order-independent.


Mixing Orders
-------------

One technical concern with this proposal is the question of what happens 
in an implementation which supports multiple alternative orders of 
evaluation, in the case where different pieces of code (modules or 
whatever) specify different evaluation orders.

Implementations are permitted to refuse to support the possibility of 
mixed evaluation orders, except in the one special case of mixing a 
specified order with an unspecified order.  In that case, it is 
permissible for all code to be evaluated under the specified order.  An 
implementation may nevertheless optionally choose to use other orders 
when evaluating the unspecified-order code.

Implementations are permitted to support the coexistence of multiple 
different evaluation orders, if they so choose.


Motivation
----------

This directive would allow some problems with code portability in Scheme 
to be corrected.  It would also allow ambiguity to be reduced.  (I say 
"allow", because use of the directive is optional.)

Currently, code written to depend on a particular implementation's 
evaluation order does so silently.  This results in potential problems 
for human readers of the code, in determining the intent of the author. 
It also results in potential problems when porting code between 
implementations.

Code which uses this directive would be prevented from inadvertently 
being run under an implementation which does not support the required 
evaluation order.  This rules out one class of portability problems for 
any code which makes use of the directive.  This goes some way towards 
addressing one of the major safety-related objections of those in favor 
of fixing a single evaluation order for all Scheme implementations.

Furthermore, the presence of this directive will help to correct 
problems, both real and perceived, created by what currently amounts to 
an *inconsistent, invisible assertion*.

Scheme code which is intended to be portable necessarily does not rely 
on a fixed evaluation order; whereas code intended for certain 
implementations may rely on a particular order (usually L2R).  This is 
the inconsistency aspect -- different code is written with different 
semantics in mind, with no explicit indication of the assumed semantics.

Even worse, particularly from the perspective of user comprehension of 
this issue, is the closely related "invisible assertion" aspect: the 
idea that the programmer may have deliberately depended on a particular 
semantics, and thus be implicitly communicating information by e.g. the 
choice of binding constructs, without any overt indication that this is 
the case.

Many people understandably have difficulty reasoning about code which 
depends on invisible assertions, especially inconsistent ones.  Others, 
again understandably, find them distasteful.  Allowing these assertions 
to be made explicit is likely to improve understanding of this issue, 
and help to clarify future discussions.

In fact, all this proposal does is make explicit something which is 
already implicit in all Scheme programs.  Support for explicitness is 
necessary in this case, because the implicit information is not the same 
for all Scheme implementations, or even for all programs intended for 
the same implementation.

One final motivating factor is that Scheme is an unusual language in 
terms of the variety of application domains in which it is used.  These 
include programming language theory, scientific computing, and 
commercial computing, each of which is a very diverse category in its 
own right.  Scheme is also a multiparadigmatic language which supports a 
sequential imperative style as well as functional style.

Given this extreme diversity of application, having some flexibility on 
the issue of evaluation order is advantageous, even important.  It means 
that one group of users doesn't necessarily have to suffer because of 
the needs of another very different group.

As Oleg Kiselyov has previously pointed out on c.l.s., there is 
precedent for this sort of behavior, in the Mercury language.  Mercury's 
approach goes further than this proposal, but along similar lines:

http://www.cs.mu.oz.au/research/mercury/information/doc-release/reference_manual_12.html

The third-last paragraph on that page ("This compromise allows Mercury 
to be used in several different ways. ...") summarizes the motivation 
for Mercury.  The relevance to Scheme should be clear.

(Note that Mercury guarantees the availability of numerous evaluation 
modes, whereas this proposal only allows particular evaluation orders to 
be specified, and requires that implementations either use the specified 
order, or refuse to run the code.)


Possible Downside
-----------------

The presence of this directive could create greater pressure from users 
to have implementations support specific evaluation orders.

In practice, it seems likely that the only order for which such pressure 
would arise is left to right (or else operands left to right, followed 
by operator).  For implementations which currently implement some other 
order, or no fixed order, such pressure may be considered undesirable.

OTOH, if that's what users actually want, the directive allows their 
desires to be satisfied, if the implementor is willing.  Support for 
alternative orders, including unspecified order, can nevertheless be 
retained, if the implementor is inclined to support multiple orders.


Conclusion
----------

Implementation of this proposal will have a positive effect on the way 
evaluation order is used and understood in Scheme.  It will achieve 
progress in a controversial area, in a way that addresses concerns on 
both sides of the issue.  It allows implementors to retain maximum 
flexibility and control over evaluation order, yet should require little 
mandatory effort.

Let the "sharp indrawn breath through the front teeth"[*] begin!

-- Anton

[*]
http://www.swiss.ai.mit.edu/ftpdir/scheme-mail/HTML/rrrs-1998/msg00128.html