Issue: PUSH-EVALUATION-ORDER (Version 3)

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

I propose this revision of the discussion of this issue, with
minor corrections according to comments sent in my previous two
messages this afternoon commenting on version 2 of the proposal.

Issue:         PUSH-EVALUATION-ORDER
References:    CLtL p. 99 (generalized variables)
               p. 270 (PUSH)
               All macros that manipulate generalized variables
               (SETF, PSETF, GETF, REMF, INCF, DECF, PUSH, PUSHNEW,
               POP, CHECK-TYPE, ASSERT, CTYPECASE, CCASE, SHIFTF,
               ROTATEF, and all macros defined by DEFINE-MODIFY-MACRO).
Category:      CLARIFICATION
Edit History:  Jeff Peck, 15-Oct-1987, version 1.
               Larry Masinter, 23-Oct-87, version 2.
               David Moon, 8-Nov-87, version 3.

Problem Description:

In the form: (PUSH (ref1) (CAR (ref2)))
It is unclear whether (ref1) should be evaluated before (ref2). 

CLtL, page 99, in a discussion of generalized variable macros, states:
"Other macros that manipulate generalized variables include ... PUSH....
 Macros that manipulate generalized variables must guarantee the
 `obvious' semantics: subforms of generalized-variable references
 are evaluated ... in exactly the same order as they appear in
 the *source* program."

That is, the sub-forms of Place should be evaluated once, left to right.

"The expansion of these macros must consist of code that follows these
 rules or has the same effect as such code.  This is accomplished by
 introducing temporary variables bound to the subforms of the
 reference."

This paragraph and a discussion of SETF on the previous pages may also
be interpreted as requiring that *all* subforms of such macro calls
should be evaluated once, in source order, left to right.

However, CLtL, page 270 states:
 "The effect of (PUSH Item Place) is roughly equivalent to
    (SETF Place (CONS Item Place))
  except that the latter would evaluate any subforms of Place twice
  while PUSH takes care to evaluate them only once."

That is, the effect of the form (PUSH Item Place) is to evaluate 
(SETF Place (CONS Item Place)) but with subforms of Place only evaluated
once.

Place and Item appear in different order in the PUSH form and the
indicated equivalent SETF form.  Should the PUSH form have primacy over
the obvious SETF form with respect to the left-to-right evaluation?

Are all subforms in a macro call guaranteed to be evaluated in order, or
only those subforms representing generalized variable references?

The same question arises for other forms which manipulate generalized
variables, e.g., PUSHNEW, INCF, DECF, and those defined with
DEFINE-MODIFY-MACRO.


Test Case:

(LET ((REF2 (LIST '())))
 (PUSH (PROGN (PRINC "1") 'REF-1)
       (CAR (PROGN (PRINC "2") REF2))))

If the subforms evaluate in left-to-right order, this will print 12
rather than 21.

Proposal: PUSH-EVALUATION-ORDER:ITEM-FIRST

Explicitly state that for the macros that manipulate generalized
variables (PUSH, PUSHNEW, GETF, REMF, INCF, DECF, SHIFTF, ROTATEF,
PSETF, SETF, POP, and those defined with DEFINE-MODIFY-MACRO) the
subforms of the macro call (including but not limited to subforms of the
generalized variable reference) are evaluated exactly as many times as
they appear in the source program, and in exactly the same order as they
appear in the source program.  Explicitly state that for the macros
CHECK-TYPE, ASSERT, CTYPECASE, and CCASE, that rule is followed except
where CLtL specifies to the contrary.

In this context, "subform" means a form (that is, something whose
syntactic use is such that it will be evaluated) that is nested inside
another form.  It does not mean any object nested inside a form
regardless of syntactic context.

For example, PUSH is expected to behave as if described as:

 (PUSH Item Place) is roughly equivalent to
 (SETF Place (CONS Item Place)) except that the subforms of Place
 are evaluated only once, and Item is evaluated before Place."

The phase "subforms of the reference" which appears several times in
CLtL should be made more specific to be "subforms of the macro call,"
referring to the entire form that calls the generalized-variable
manipulating macro.

Rationale:

This is the unstated intention of the page 97-100 discussion of
generalized-variable referencing macros, and indeed the intended
definition of "obvious semantics" for all macros.

Current practice:

Many implementations do not currently follow this evaluation order. In
the form (PUSH Item Place), Lucid, Franz, Kyoto and Xerox evaluate Place
then Item. Symbolics evaluates Item then Place.


For example, in Franz:

(macroexpand '(push (ref1) (car (ref2))))

    (LET* ((#:G8 (REF2))
           (#:G7 (CONS (REF1) (CAR #:G8))))
      (EXCL::.INV-CAR #:G8 #:G7)) 
    
In Symbolics Common Lisp, it returns:
    
    (LET* ((#:G5 (REF1))
           (#:G4 (REF2)))
      NIL
      (SYS:RPLACA2 #:G4 (VALUES (CONS #:G5 (CAR #:G4)))))


Adoption Cost:

Minimal, PUSH etc. could simply be defined by the appropriate macros.

Cost of non-adoption:

Obvious programs may be non-portable, although it should be rare that
order of evaluation will affect actual operation. 

Benefits:

The implementation and semantics of PUSH become obvious to all.  

Esthetics:

Common Lisp defines order of evaluation as left-to-right; this
clarification ensures consistency across the language. 

Discussion:

David Moon (Symbolics) argues that the unstated intention of page 99
is the definition of the language, while admitting that:

"The quoted paragraphs could be taken to restrict order of evaluation
only of the subforms of (CAR (ref2)), not all of the subforms of the
PUSH form."

However, the second to last paragraph on page 99

  As an example of these semantic rules, in the generalized-variable
  reference (setf reference value), the value form must be evaluated
  after all the subforms of the reference because the value form
  appears to the right of them.

makes it clear, if it is still talking about the same semantic rules,
that in this context the phrase "generalized-variable reference" was
meant to refer to the entire macro call, not just the Place, and that
order of evaluation rules are not limited to subforms of Places.  We
suggest that the next specification of Common Lisp should adopt more
consistent terminology.

No performance impact is expected; while some macro expansions may
appear to be more verbose, most compilers deal reasonably with the
required order of evaluation.