Unspecified order of evaluation in Scheme

[Morry Katz <katz@quilty.Stanford.EDU>]

   From: Mitchell Wand <wand@ccs.neu.edu>
   Date: Fri, 23 Sep 1994 14:04:54 -0400

   > 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

   > 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 cannot comment on the meaning of the IEEE document; however, my
understanding from the discussions of this topic at the RnRS meetins
over the last 8 years has been that the order of evaluation of
operators and operands is completely unspecified so long as the result
is serializable, meaning that it is equivalent to some sequential
execution of the operator and the operands.  This includes the
possibility that the order of evaluation of operator and operands at
the same call site can change from one call to the next.  Way back
when there was a test system that I used that used a random number
generator to choose execution order at every call.  The idea was to
help one heuristically find unintended order of execution dependences
during testing.
--------------------
Morry Katz
katz@cs.stanford.edu
--------------------