[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]


I merely appended the salient points of the discussion so far to the end of this. 
References:    CLtL p. 99 (generalized variables)
               p. 270 (PUSH)
               All macros that manipulate generalized variables
               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
               Larry Masinter, 14-Nov-87, version 4

Not ready for release

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

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

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

Test Case:

(LET ((REF2 (LIST '())))
       (CAR (PROGN (PRINC "2") REF2))))

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


Explicitly state that for the macros that manipulate generalized
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.


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)))
      (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. 


The implementation and semantics of PUSH become obvious to all.  


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


David Moon  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 serious performance impact is expected; while some macro expansions
may appear to be more verbose, most compilers deal reasonably with the
required order of evaluation.

Problems with this version:

The rules for CHECK-TYPE, ASSERT, CTYPECASE, and CCASE need to be 


    (defmacro wrong-order (x y) `(get ,y ,x))

If the user writes (push a (wrong-order (frob) (baz)))

are we willing to guarantee that "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. "? No..

Note that the same issue arises for
(setf (wrong-order (frob) (baz)) 1)

so this point in no way shoots down what we originally set out to do

A more complicated version of wrong-order, for example, one with a loop
in it, would make it impossible to guarantee that statement.  So we have
to change the statement.  I think what we mean is that evaluation
of the direct subforms of the macro call and of generalized-variable
references in the macro call is ordered, but evaluation of subforms of
those subforms is determined by the recursive evaluation process as normal.

What about

(rotatef (wrong-order (frob 1) (frob 2))
         (wrong-order (frob 3) (frob 4))

If the user writes an "incorrect" setf-method, e.g.,

    (defsetf wrong-order (x y) (z) `(setf (get ,y ,x) ,z))

this is not an issue since CLtL p.103 says "This binding permits the
body forms to be written without regard for order-of-evaluation issues."
Of course a user could write an incorrect define-setf-method.