Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!ucsd!ucbvax!hplabs!otter.hpl.hp.com!otter!sfk
From: sfk@otter.hpl.hp.com (Steve Knight)
Newsgroups: comp.lang.scheme
Subject: Re: Re: Order of evaluation (was Re: evaluating () should be an error
Message-ID: <6260002@otter.hpl.hp.com>
Date: 29 Mar 91 15:26:44 GMT
References: <1991Mar26.224805.23381@cs.ubc.ca>
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Lines: 97

I'm glad to see that the issue of order of evaluation of call-arguments is
still an active issue.  I argued with Jim Miller a while ago, in favour of
a fixed order of evaluation, without much success then I must admit!

There seem to be two arguments in favour of leaving evaluation order 
unspecified.  Firstly, it discourages programmers from exploiting it as a 
feature, which Jim argued was undesirable.  Secondly, there is an 
efficiency issue concerning optimisation of register usage in compilers.
There is also a frequently raised concern about making progress towards
parallel-processor implementations -- but this disregards the serious
issue of synchronisation across shared structures, so I won't discuss
this here.

The argument in favour of specifying an order is essentially one of
robustness.  Unspecified order implies that a faulty program, which relies
on a particular order (by design or accident), may appear to work and may
become highly trusted as a result of its coincidental success.  Shifting
to a new compiler may silently introduce intermittent problems.  A fixed
order eliminates this undesirable behaviour.  Another solution, which I
won't pursue further, is to provide a "lint" facility to diagnose such
problems.  This would obviously have to work across module boundaries.

The structure of the debate resolves itself into a discussion of whether
or not a fixed order of evaluation causes unacceptable efficiency costs
and whether or not the 'porting problem is serious.  It should go without
saying that a free order of evaluation must be as-or-more efficient than
a fixed order.  Neither is there any doubt that the 'porting problem is
undesirable in any language.

My belief is that a key design principle of Lisp-like languages is that
they provide "noisy" protection.  A faulty program never executes the 
fault without complaint.  To ensure this principle, the preconditions of
all constructs must be checked either at run-time or compile-time.  I
also believe that this principle always takes precedence over efficiency
considerations (where feasible).  Free-order of evaluation of call-
arguments contradicts this.

I've not seen any adequate statistics showing the relative costs of 
free Vs. fixed orders.  Intuitively, the cost is likely to be of a small order,
perhaps 10%, and so generally acceptable at development time.  So we are 
mainly concerned with producing high-quality code at delivery time.  Any
statistics should compare four systems of code generation.  
  (1) free-order 
  (2) a couple of fixed-order variants
  (3) the same fixed order variants in the presence of intra-module
      analysis of side-effect free functions
  (4) as above, but with inter-module module analysis
Since I've seen no work that comes remotely close to this -- though it may
exist -- I believe we are reduced to arguing on the basis of structural
understanding.

The seriousness of the 'porting problem is bound to be a matter of
judgement since no worthwhile statistics on this exist (to my knowledge).
One comment that is occasionally voiced is that imperative languages such
as C have the same 'minor' shortcoming and it is not a matter of complaint.
This analogy is flawed in two important ways.  Firstly, the inability to
return structured results in the same free fashion as Scheme changes the
coding style.  It is common to see sequences such as
    foo( x, y, &answer1, &answer2 );
    bar( answer1, answer2 );
in which the order of evaluation is incidentally defined.  Secondly, the
C language suffers from such very serious shortcomings that this issue
drops below the horizon of concern!  (e.g. no automatic store management
policy.)

As a matter of record, I've seen this problem arise with very serious
consequences in the context of a 100,000 line FORTRAN program.  So there
is no doubt in my mind that the consequences of this problem can be 
extremely severe.  What is more arguable is that this situation is unlikely
to arise in Scheme because of different design tradeoffs.

The most serious scenario, in my view, is where a reliance on order of
evaluation is accidentally introduced.  Deliberate reliance, after all, it
can be argued is simply a matter of poor education.  The scenario I have
in mind is in the maintenance of a large program, where it is not 
practical to have a complete understanding of every component one is 
dealing with.  In this case, it is plausible to add a side-effect to 
a routine which is self-evidently side-effecting, without noticing that
the original side-effect is *local*.  The addition may create a non-local
side-effect and imply that some, but not all, calls of the routine are
illegal.

There are several points which need to be expanded on here.  A "local" side
effect is meant to be one which has no synchronisation consequences.  A good
example would be a 1-value cache which optimises repeated calls with the same
arguments.  It should also be noted that an ordinary cross-reference 
listing would not be adequate to check that such a defect was not introduced.
Not only must all calls to the modified routine be checked, but all calls
to the callers must be checked, and all their callers' calls, etc.  It would
be possible to construct such an analysis, of course, which would lead to the
"lint" style solution.

Generally, I believe that the imperative nature of Scheme is under-supported
with undesirable consequences.  The free-order of evaluation is an example
of this.

Steve