ziggy@hx.lcs.mit.edu (Michael R. Blair) (04/10/91)
In Scheme Digest Vol.3 No.178, Tim Moore writes: >Date: 5 Apr 91 16:36:03 GMT >From: Tim Moore <moore%defmacro.utah.edu@cs.utah.edu> >Organization: University of Utah CS Dept >In article <JAFFER.91Apr5002735@chamarti.ai.mit.edu> jaffer writes: >>gjc and others suggest fixing the order of evaluation. If this order >>is fixed Scheme will lose the ability to be easily run on multiple >>processors. This will confine scheme to the dustbin of history. >> >As was pointed out earlier, the unspecified order of evaluation has >almost no effect, pro or con, on running Scheme on multi-processors. >Arguments can be evaluated in any order, but evaluation cannot be >interleaved. Uhm, be careful here... nothing was pointed out earlier, rather something was claimed but not demonstrated. Let me clarify why an unspecified order of evaluation *does* matter to multi-processor Scheme's. If the order is unspecified then any order may be chosen so long as it corresponds to some sequential evaluation of the arguments. The intersting case is when two (or more) arguments interfere in the sense that one alters a memory location which the other either reads or writes. If the evaluation order is unspecified then this permits non-determinism, which may well be desirable. Notice that this does *not* violate sequential semantics. Now, the important issue arises when one considers how to keep all the processors in the multi-processor Scheme busy most of the time. This is called ``load balancing''. Good load balancing ensures low latency. Now, consider the situation where all but a couple processors are busy when we encounter an application with multiple arguments. One of these arguments may require many resources to evaluate whereas the other requires few. If we imagine load balancing to be like playing Tetris, the prudent thing to do is to dedicate the few resources we have available to the evaluation of the argument which requires only a few. Imagine, for instance, that we have discovered at compile time or by post-mortem analysis of a prior invocation, that this produces good load balancing by virtue of having sneeked in a full argument eval where only a partial argument eval would otherwise have fit. Specifically, the argument which requires many resources may make only a little progress before blocking due to lack of available resources whereas the arg which requires only a little resources could fully evaluate with the available resources. In short, the less blocking incurred, the less the synchronization/communication overhead will dominate the computation so the more ``real'' work will get done. The important result of this proposed scenario is that if you fix the order of evaluation to disallow non-determinism in the argument evaluation then you would not permit multi-processor Scheme's to exhibit good load balancing in the face of non-determinism. Thus, in your desire to allow programmer's to write questionably more succinct code, code which actually obfuscates the control dependencies between code fragments, you will have relegated Scheme to inferior performance on multi-processor machines, in effect proclaiming Scheme to be a SERIAL language. I personally feel this would be a regrettable trade-off to have made because I personally believe in the virtues of non-determinism and speculative parallelism in multi-processing. (And I also personally feel it is counter-productive to engage in debate as to whether or not changing the language in certain ways would affect multi-processor implementations until I have become versed in the issues which arise in multi-processing implementations. Until that point, I typically phrase my postings as querys rather than as unfounded claims. Proof by lack of imagination is Modus Bogus... and is considered professionally embarassing in credible academic settings.) ------------------------------------------------------------------------------- ziggy@lcs.mit.edu Michael R. Blair MIT Laboratory for Confuser Science (617) 253-6833 [O] -. 545 Technology Square --- Room 437 (617) 577-1167 [H] /\. Cambridge, MA 02139 ------------------------------------------------------------------------------- -- ------------------------------------------------------------------------------- ziggy@lcs.mit.edu Michael R. Blair MIT Laboratory for Confuser Science (617) 253-6833 [O] -. 545 Technology Square --- Room 437 (617) 577-1167 [H] /\. Cambridge, MA 02139
mday@brokaw.lcs.mit.EDU ("Mark S. Day") (04/10/91)
The discussion so far suggests that the people who want to fix the
order of evaluation and the people who want to leave it unspecified
are talking past each other. Both have legitimate concerns and
examples of why the order of evaluation should/shouldn't be fixed.
Rather than arguing about which alternative to pursue, perhaps we can
explore the possibility of allowing both.
An unspecified order of evaluation can be constrained to a specific
order of evaluation, but actually writing the code to do it is clumsy
and obscure, e.g. instead of
(foo a b c)
we have something like
(let*
((foo foo)
(a a)
(b b)
(c c))
(foo a b c))
This is unpalatable, since it has to be repeated on every call. You
might fix the syntactic problem with macros, but then the compiler
doesn't gain anything from the fixed order of evaluation. What would
be nice is a way to abstract the pattern, so that a person who wants
to write programs where the arguments are evaluated (say)
left-to-right is able to set up the evaluation order once and then
write normal-looking Scheme. For example,
(with-eval-order ((x y) (begin x y))
(foo a b c)
...
)
would evaluate the contained expressions so that any pair of neighboring
arguments x,y is evaluated as if they were written with a begin. Note
that the begin is only controlling evaluation order: x still gets the
value of x, y still gets the value of y.
Unfortunately, this simple approach requires that with-eval-order know
how to extend the ordering of two arguments to an arbitrary number of
arguments. It simply pushes the evaluation order problem up one level.
For example,
(with-eval-order ((x y) (begin y x))
(foo a b c)
...
)
is "supposed" to define right-to-left evaluation, but only does so if
the arguments are grouped into pairs in the opposite order from the previous
example, i.e. (foo (a (b c))) instead of (((foo a) b) c).
Instead, consider redefining the underlying implementation's
"evaluation-order function", which I will call %eval-order. The
function is called with a nonnegative integer n indicating the number
of arguments to a called function. It returns a list of the integers
from 1 to n, arranged so that the car is the index of the first
argument to evaluate, etc.
Then we can write the following:
Left-to-right:
(define (%eval-order n) (1-up-to n))
Right-to-left:
(define (%eval-order n) (reverse (1-up-to n))) for right-to-left,
Random:
(define (%eval-order n) (randomly-arrange (1-up-to n)))
Jinx's proposed order:
(define (%eval-order n)
(let ((args (1-up-to n)))
(let ((evens (filter even? args))
(odds (filter odd? args)))
(append (reverse evens) odds))))
This has enough expressive power, but is still not very pretty. It's
probably difficult to get this to work efficiently, and still more
difficult to get a compiler to take advantage of this information.
[But please, no rhetorical excess about its "impossibility". I know
that this requires the compiler to evaluate a function at compile
time, and that in the general case this is a bad idea. But this is a
very special case where we know a lot of constraints on the function,
and could reasonably require that the function not do things that the
compiler can't understand. Let's assume that we want to solve the
engineering problem, instead of discussing the halting problem.]
--Mark Day
mday@lcs.mit.edu MIT Laboratory for Computer Science