[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Unspecified order of evaluation in Scheme




   From: Mitchell Wand <wand@ccs.neu.edu>
   Date: Fri, 23 Sep 1994 14:04:54 -0400
   Cc: will@ccs.neu.edu, rrrs-authors@martigny.ai.mit.edu

   > Date: Fri, 23 Sep 1994 10:37:52 -0400
   > From: myra@saul.cis.upenn.edu (Myra VanInwegen)
   > Posted-Date: Fri, 23 Sep 1994 10:37:52 -0400
   > To: wand@ccs.neu.edu
   > Subject: Unspecified order of evaluation in Scheme

   > Hello-

   > Reading the R^4 report on Scheme, the TexInfo version, I find on page
   > 15:

   > 	Note: Although the order of evaluation is otherwise unspecied ...
   > 	The order of evaluation may be chosen differently for each procedure
   > 	call.

   > Can the order of evaluation be chosen differently for different
   > executions of the *same* procedure call? In other words, is Scheme
   > non-deterministic?

   > -Myra VanInwegen
   > myra@saul.cis.upenn.edu

   My copy says:

	*Note:* In contrast to other dialects of Lisp, the order of evaluation is
	unspecified, and the operator expression and the operand expressions are
	always evaluated with the same evaluation rules.

	*Note:* Although the order of evaluation is otherwise unspecified, the
	effect of any concurrent evaluation of the operator and operand
	expressions is constrained to be consistent with some sequential order of
	evaluation.  The order of evaluation may be chosen differently for each
	procedure call.

   I'm sure this has been discussed many times, but I forget the answer.

   I would read the phrase "the operator expression and the operand expressions
   are always evaluated with the same evaluation rules" as precluding the
   possibility that different executions of the same procedure call have
   different orders of evaluation.

   But I defer to the language lawyers on these issues.  Gentlemen, can you
   refresh my memory?

I'm not a language lawyer, but here is my opinion anyway:

The answer to the question clearly also depends on the answer to the
question about what constitutes ``the same'' procedure call.  What I'm
thinking about is a scenario with some kind of optimizing compiler
which does automatic inlining and such.  It is possible that such a
compiler produces several copies of the same procedure call as it
appeared in the original source code.

Unless extreme care is taken, the subsequent code generation phase
could produce different evaluation orders for different copies.  Since
the precise effect of optimization is hard - if not impossible - to
pin down, it seems like a good idea to say that the evaluation order
is undefined, and even different invocations of the same call can
differ here.

Macro expansion can have similar effects of duplicating procedure call
sites.  However, macro-expansion is usually explained in terms of
source-to-source transformations.  Semantic issues like evaluation
order is kept out of the picture until all macros are expanded.

I would go with the most general interpretation of the rule:

	* the language definition does not mandate any particular
	  evaluation order
	* the actual evaluation of the arguments for each individual
	  call at runtime must be consistent with some sequential
	  order of evaluation
	* this sequential order (which is only used as a reference order)
	  can be chosen without further constraints for each
	  individual call

Actually, I don't like the second point.  What it says is basically
that there are (C-style) sequence points between arguments of a
procedure call, but it is left open how the arguments are to be filled
into the spaces between those sequence-points.  Why have the sequence
points in the first place?

Consider:

	(a (b (c) (d)) (e (f) (g)))

Here are possible orders of evaluation:

[call to a comes always last.]

Let's pick: call to e before call to b (the other possible choice
works similarly)

Now we are also committed to both f and g coming before b.
Furthermore, b's arguments are evaluated *after* the call to e.  This
leaves us with only 4 possible choices.

g f e d c b a
f g e d c b a
g f e c d b a
f g e c d b a

Correct me if I'm wrong, but in C you are not constrained that much.
In C you can also have:

g f d e c b a
g f d c e b a

and various permutations of the goups consisting of g, f, d, and c.

-Matthias