Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!sdd.hp.com!spool.mu.edu!snorkelwacker.mit.edu!bloom-beacon!dont-send-mail-to-path-lines
From: mday@brokaw.lcs.mit.EDU ("Mark S. Day")
Newsgroups: comp.lang.scheme
Subject: Fixing the order of evaluation.
Message-ID: <9104101530.AA06329@brokaw.LCS.MIT.EDU>
Date: 10 Apr 91 15:30:05 GMT
References: <dig-Scheme-3.182@mc.lcs.mit.edu>
Sender: daemon@athena.mit.edu (Mr Background)
Organization: The Internet
Lines: 99


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