Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!apple!snorkelwacker.mit.edu!ai-lab!zurich.ai.mit.edu!jinx
From: jinx@zurich.ai.mit.edu (Guillermo J. Rozas)
Newsgroups: comp.lang.scheme
Subject: Re: Order of evaluation (was Re: evaluating () should be an error
Message-ID: <JINX.91Mar27153708@martigny.ai.mit.edu>
Date: 27 Mar 91 20:37:08 GMT
References: <2977@kraftbus.cs.tu-berlin.de> <1991Mar26.155905.12906@daffy.cs.wisc.edu>
	<kiran.670017354@copper> <1991Mar26.224805.23381@cs.ubc.ca>
	<harlan.670038398@copper> <1991Mar27.101357.20383@news.cs.indiana.edu>
	<1055@argosy.UUCP>
Sender: news@ai.mit.edu
Reply-To: jinx@zurich.ai.mit.edu
Organization: M.I.T. Artificial Intelligence Lab.
Lines: 58
In-reply-to: freeman@argosy.UUCP's message of 27 Mar 91 19:04:33 GMT

In article <1055@argosy.UUCP> freeman@argosy.UUCP (Jay R. Freeman) writes:

   Path: ai-lab!mintaka!olivea!decwrl!argosy!freeman
   From: freeman@argosy.UUCP (Jay R. Freeman)
   Newsgroups: comp.lang.scheme
   Date: 27 Mar 91 19:04:33 GMT
   References: <2977@kraftbus.cs.tu-berlin.de> <1991Mar26.155905.12906@daffy.cs.wisc.edu> <kiran.670017354@copper> <1991Mar26.224805.23381@cs.ubc.ca> <harlan.670038398@copper> <1991Mar27.101357.20383@news.cs.indiana.edu>
   Sender: news@argosy.UUCP
   Reply-To: freeman@cleo.UUCP (Jay R. Freeman)
   Organization: MasPar Computer Corporation, Sunnyvale, CA
   Lines: 15

   Possibly one reason for not specifying the order of evaluation of
   arguments to a procedure is to make one step toward an implementation
   that can run on an asynchronous MIMD processor -- the idea is to farm
   out each argument evaluation to its own processor and collect the
   results as they come in.  Such an implementation would quite likely
   evaluate the arguments in different orders each time the same code
   was run.

   (I'm *not* saying that that's *all* you have to do to make a Scheme
   that can run on an asynchronous MIMD processor -- but "a journey of
   1000 MIPS, er, miles, begins with a single step.")

					     -- Jay Freeman

	     <canonical disclaimer -- I speak only for myself>

Unfortunately this is not allowed.  The intent of the current wording
is to allow arbitrary sequential orders, but not interleaved (or
parallel) evaluation.  In other words, the arguments are evaluated
sequentially in an unspecified order.

The reason for this decision is that unless a way of synchronizing
stores (and the corresponding reads) is provided, interleaved
evaluation will generate incorrect results for programs for which any
sequential order will give correct results.

The prototypical example is a structure-copying routine.  When copying
a pair it may do something like

(define (hash-copy-pair pair)
  (let ((the-car (hash-copy (car pair)))
	(the-cdr (hash-copy (cdr pair))))
    (hash-cons the-car the-cdr)))

where hash-copy and hash-cons manage a table of associations to
guarantee isomorphism.

Now consider the case of HASH-COPYing a pair with eq? car and cdr.
Any sequential order of execution of the arguments to the LET
procedure will generate the correct answer, but interleaved evaluation
may not since the operation of looking up an object in the table and
generating a copied ID for it should be indivisible, but interleaved
evaluation may break this assumption.

In the presence of a standard test-and-set operation, allowing
parallel evaluation would be reasonable.