Left to right, or parallel, evaluation of arguments to function?

[Rem@IMSSS]

(If you want to reply but your host doesn't know how to reach
 REM@SU-SCORE, try REM%IMSSS@SCORE or if that doesn't work from your
 host then REM@MIT-MC. I eagerly await namedomains&servers which
 should alleviate this problem.)

    Date: Wed, 21 Nov 1984  15:42 EST
    From: "Scott E. Fahlman" <Fahlman@CMU-CS-C.ARPA>
    Subject: left to right order of evaluation
    
    If I understand ... question, ... are asking whether, in a
    normal function call like "(g (foo))", the mapping from the symbol G to
    its definition occurs before or after the call to FOO, which might
    change the definition of G as a side-effect.
    
    I don't think that the manual currently addresses this issue.
    I would advocate leaving this decision to the implementor,
I would state it a little more strongly. It is generally bad programming
practice for a program to modify itself out from under itself. Most
langauges keep program and data totally separate, even putting program on
readonly pages. Some CPUs carry this further, using different segment
registers for program and data, and having data-manipulation instructions
UNABLE to fetch or store relative to the program base register. In LISP we
can be a little lax, doing things like creating an s-expression and then
passing it to EVAL a moment later, or loading and compiling a program qua
data into memory and then immediately making use of the resultant compiled
functions by calling them qua machine-language subroutines. But note that
although with respect to the whole program we are treating "it" as both
program and data at the same time, we always treat a given sub-form either
as one or another at any given moment, and never (in those examples)
modify a form in place while it is in the midst of being executed. At
worst we execute it completely, then while outside of it we modify it in
preparation for the next execution.

In some extreme cases a macro expander may wish to modify the form to be
faster next time, or a UUO link may be optimized during a call, but the
semantics of the form (except for timing) are the same before an after the
destructive modification.

I therefore propose that we say "IT IS AN ERROR" to attempt to modify any
piece of code (interpreted or compiled) to have different semantics, when
that piece of code is currently in the midst of execution, including
functions which are currently in a half-called state while their arguments
are being recursively evaluated. I'm not sure whether or not we should
explicitly allow any destructive modification which doesn't change
semantics, after all such mod may screw up the PC, causing some parts of
the current evaluation to be skipped or double-executed if data is
compressed or expanded in the vicinity.

    Date: Wed, 21 Nov 1984  16:07 EST
    From: "Scott E. Fahlman" <Fahlman@CMU-CS-C.ARPA>
    Subject: left to right order of evaluation
    
    I believe that the first full paragraph on page 61 of the aluminum
    edition specifies left-to-right evaluation of arguments for all function
    calls.
I diasgree. The purpose of the paragraph is to resolve the question of
which dummy arguments match which actual arguments, not the realtime
matter of when the actual arguments are evaluated to yield actual values
which are bound to dummy arguments. It's completely reasonable (to me it
seems) that an implementation would push dotted pairs (dumarg . actarg) on
a stack during resolution of argument matching as described in that
paragraph, but then actually evaluate them in reverse order as they were
popped off the stack and the evaluated results stored in another memory
array-like place (stack, registers, whatever). Note there's no mention of
EVALuating in that paragraph, nor of values, only of PROCESSING of
parameters and arguments, where PROCESSING obviously (to me) means the
matching process and resolution of &REST etc. arguments.

Furthermore, insisting on a particular order of evaluation of arguments in
the general case precludes implementing on a parallel processor such as a
dataflow machine. It would be a royal pain to completely rewrite a
program to replace nearly every function call in the whole program by an
equivalent parallel-evaluation function call, whereas it would be not too
bad to replace the very few places sequential evaluation is really needed
by an explicit sequencial-argument-evaluation macro or special form.

In typical usage, most cases of sequence falls in three classes:
  (1) Arguments must be evaluated before calling the function. SCHEME et
    al with lazy evaluators which may leave arguments
    not-completely-evaluated at the time a function is called present some
    problems here, but I think SCHEME simply has to be smart enough to
    assure that side-effects are emulated as if arguments had been
    evaluated before the function was called.
  (2) Explicit sequential forms such as PROG, PROGN, etc. These clearly
    must evaluate arguments in the prescribed sequence (or in SCHEME
    emulated to have equivalent semantics).
  (3) Case resolution forms such as COND. Either they must be evaluated in
    the expected order, or side-effects must be emulated as if they did.
The only common errant cases seem to be:
  (4) Use of AND or OR to emulate COND, just to save a few parentheses.
  (5) Use of LIST to evaluate several forms in sequence and return a list
    of their results for visual inspction.
I think AND OR LIST and all other functions should be permitted to
evaluate their arguments in arbitrary order, including in parallel, and
when cases 4 and 5 are needed special forms or macros should be used. Thus
(AND (PAIRP FOO) (EQ (CAR FOO) 'FOO)) would be replaced by
(SEQ-AND (PAIRP FOO) (EQ (CAR FOO) 'FOO)) or something similar, but
(AND (LESSP (LENGTH LIST1) 500) (LESSP (LENGTH LIST2) 700)) could be run
in parallel on some machines.

I would like to see Common-LISP take the bold step of PERMITTING the
effective use of dataflow and other parallel-processing machines without
extensive modification of programs.

    Date: Wed 21 Nov 84 16:22:25-EST
    From: Rodney A. Brooks <BROOKS%MIT-OZ@MIT-MC.ARPA>
    Subject: Re: left to right order of evaluation
    I don't think the paragraph on page 61 specifies order of evaluation
    of argument forms. It is talking about application of a function, not
    evaluating arguments to which a function will get applied. From the
    third paragraph on page 61 it seems clear that ``processed'' does
    not include evaluation of argument forms as it talks about intermingling
    binding of variables and ``processing''.
Glad to find somebody agrees with my interpretation of the manual.

    The bottom of page 58 and top of 59 seem to be the place to specify
    order of evaluation and there there is no mention of order of
    evaluation. There should be something explicit there even if it is to
    say the order is undefined.
I agree completely. Note in particular it says "the forms 4 and 5 are
evaluated, producing arguments 4 and 5 for the multiplication", not "the
form 4 is evaluated producing 4, and then the form 5 is evaluated
producing 5, which are the arguments for the multiplication". Clearly it's
ambiguous whether they are done in parallel or in sequence.

    I think the right thing is left to right evaluation of argument forms
    and mute on when the symbol-to-function mapping happens.
Perhaps for the present, although I would still like to see parallel
evaluation of arguments permitted as I described earlier.

[An aside, who's the cretin who picked the font for numbers in the
aluminum edition? Backwards-E is simply garbage. We're implementing a
language for 5*7-matrix and bitmapped displays, not wristwatches using
liquid crystal 7-segment displays, huh? It was a long time perusing the
manual (on other pages where <exist-symbol> wasn't obviously a number)
before I realized they meant the number 3 not some typographic error.]
-------