[Openmcl-devel] LOOP parallel for/as termination eval order issue.

[Gary Byers]

On Sun, 17 Oct 2010, Kaz Kylheku wrote:

>
> Hi all,
>
> The following for returns nil in CCL and Allegro, but (1 2 3) in CLISP.

It also returns NIL in the versions of LispWorks, CMUCL, and SBCL that
I have.  It's possible that the behavior that you expect is correct and
that CLISP is the only implementation that gets it right, but I don't
think that that's the case here.

In all implementations, the loop terminates without executing the
(empty) body.  (It's easy to test this empirically.) There isn't any
disagreement on any of the issues that you cite, but in all
implementations but CLISP, Y is bound to NIL at the point where the
loop exits (and has not yet been assigned any non-null value, any of
the successive CDRs of '(1 2 3).)

With all macroexpansion removed, CCL generates something like:

? (pprint (ccl:macroexpand-all '(loop for x in nil and y = '(1 2 3) then (cdr y)
                                       finally (return y))))
(BLOCK NIL
   (LET ((X NIL) (#:LOOP-LIST-306 NIL) (Y NIL))
     (DECLARE (TYPE LIST #:LOOP-LIST-306))
     (TAGBODY (GO ANSI-LOOP::END-LOOP)
      ANSI-LOOP::NEXT-LOOP (SETQ #:LOOP-LIST-306
                                 (CDR #:LOOP-LIST-306))
              (IF (ENDP #:LOOP-LIST-306)
                  (PROGN (GO ANSI-LOOP::END-LOOP)))
              (SETQ X
                    (LET ((#:G307 (CAR #:LOOP-LIST-306)))
                      (SETQ Y (CDR Y))
                      #:G307))
              (GO ANSI-LOOP::NEXT-LOOP)
      ANSI-LOOP::END-LOOP (RETURN-FROM NIL Y))))

(and yes, that is using the MIT/Symbolics LOOP implementation.  Several other
implementations use that version as well; LispWorks certainly doesn't
seem to, but generates code that I believe is correct.)

In that case (where it's determinable at macroexpand-time that the loop will
never be executed), most of the expansion is dead code and no prologue is
even generated.  That seems to be a desirable (if obvious) optimization, and
I believe that it's correct.

A similar case - where the value of the list whose elements X will be bound to
isn't a constant - shows the elided prologue and why it was correct to have
optimized it out in the macroexpansion:

? (pprint (ccl:macroexpand-all '(loop for x in z and y = '(1 2 3) then (cdr y)  finally (return y))))
(BLOCK NIL
   (LET ((X NIL) (#:LOOP-LIST-316 Z) (Y NIL))
     (DECLARE (TYPE LIST #:LOOP-LIST-316))
     (TAGBODY (IF (ENDP #:LOOP-LIST-316)
                  (PROGN (GO ANSI-LOOP::END-LOOP)))
              (SETQ X
                    (LET ((#:G317 (CAR #:LOOP-LIST-316)))
                      (SETQ Y '(1 2 3))
                      #:G317))
      ANSI-LOOP::NEXT-LOOP (SETQ #:LOOP-LIST-316
                                 (CDR #:LOOP-LIST-316))
              (IF (ENDP #:LOOP-LIST-316)
                  (PROGN (GO ANSI-LOOP::END-LOOP)))
              (SETQ X
                    (LET ((#:G318 (CAR #:LOOP-LIST-316)))
                      (SETQ Y (CDR Y))
                      #:G318))
              (GO ANSI-LOOP::NEXT-LOOP)
      ANSI-LOOP::END-LOOP (RETURN-FROM NIL Y))))

The prologue is generated in this case, but the assignment of initial
values to X and Y doesn't happen if the list (Z) is NIL.  (Note that
the expansion of the assignments in the prologue indicates that they
happen "in parallel", as if by PSETQ.)  Among other things, the
parallel assignment means that there's no observable point at which X
could have a new value and Y couldn't (or vice versa.)

CLISP expands into code that's something like:

(block nil
   (let* ((x nil) (y nil) (#:temp nil)) ; simplified
     (tagbody (setq #:temp z y '(1 2 3))
              begin-loop
              (when (endp #:temp) (go end-loop))
              (setq x (car #:temp))
              ...)))

and I don't think that that's correct: the initialization of X and
Y has to happen in parallel and can only happen if Z is non-nil.

I think that the spec's actually pretty clear here: aside from the
descriptions of "parallel assignment" and "parallel binding", section
6.1.1.4 says that assignment of initial values has to happen in the
order specified by the user; the CLISP expansion assigns an initial value
to Y before determining whether X can be assigned an initial value at all.
That isn't "doing those assignments in parallel" or "doing them in the 
right order"; if I had to guess (and I do), I'd guess that it may be "an
understandable but misguided attempt to avoid doing ENDP an extra time."

There might be something that I'm missing here, but if I were a CLISP
user I'd be strongly inclined to report CLISP's behavior as a (fairly
subtle, fairly obscure) bug.