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

[Gary Byers]

On Sun, 17 Oct 2010, Kaz Kylheku wrote:

>
> On Sun, 17 Oct 2010 20:22:15 -0600 (MDT), Gary Byers <gb at clozure.com>
> wrote:
>> 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.
>
> The AND parallel construct is a red herring, it turns out.
> Let's eliminate it:
>
>  (loop for x in nil
>        for y = 3 finally (return y))
>
>  #+clisp -> 3
>  #+clozure -> NIL

NIL is a correct answer here, as (actually) is 3.  All that we can say
about the value of Y at the point where the loop terminates is that it's
some "meaningless value of the right type".  NIL certainly qualifies, as
does 3.

>
> Look at that! CLISP's loop assiduously performs
> all the assignments, prior to the first iteration,
> and only then evaluates the termination conditions
> associated with the clauses prior to the loop
> body.

No it doesn't.  If you don't believe me, macroexpand your
example in CLISP and look at what actually happens.

The first assignment (to X) in the prologue can't be
performed: X can't be assigned the value of successive
elements of NIL, because NIL doesn't have any elements.

Assignments of values have to happen in the user-specified
order.  (That means that any assignment to X has to occur before any
assignment to Y.)

The relevent part of CLISP's macroexpansion of this example is:

  (TAGBODY SYSTEM::BEGIN-LOOP
      (PSETQ Y 3) ; this is incorrect in general but may be harmless here.
      (WHEN (ENDP #:LIST-3079) (LOOP-FINISH))
      (SETQ X (CAR #:LIST-3079))
      ...)


e.g., on each iteration it assigns an initial value to Y, then tests
to see if ENDP is true of the list that X iterates over and
conditionally assigns the value of the next element of that list to X.
It's not "peforming all assignments prior to testing for termination";
an assignment to X can't be made without also testing for the termination
condition.


>
> That's exactly what the spec says (6.1.1.6).

6.1.1.6 says that iteration control clauses perform termination tests
"generally" before the body and after initialization.  A FOR/AS <var> IN
<list> clause can't initialize the variable to meaningful value before the
body if the list is NIL.  The simplest case:

(for x in nil finally (return x))

will generally macroexpand into something like:

(block nil
   (let ((x meaningless-value-of-correct-type) ; often, but not necessarily NIL
         (#:temp nil))
     (tagbody
       AGAIN
       (when (endp #:temp) (go END))
       (setq x (car #:temp))
       ...
       (setq #:temp (cdr #:temp))
       (go AGAIN)
       END
       (return x))))

The value that should be returned here is the meaningless value to which
X was bound in the LET.

If you think that X can be initialized to some predictable value before
the termination test, what on earth would that value be ?

What's actually happening in CLISP's case isn't even what you
say is happening.  It's assigning a value to Y before (conditionally)
assigning a value to X.  The test for termination indeed has to
happen before X can be assigned to, but Y can't be assigned to
before X is (6.1.1.4).  You're assuming (in this and the parallel
case) that Y "should" have been initialized before the termination
test.  X can't be initialized until after the termination test, and
Y has to be initialized after X is.

(loop for x in some-list
       for y = x                 ; it's important that X is assigned to
                                 ; before Y is
       do (something-with-x-and-y))

CLISP seems to get this case right (e.g., it doesn't try to assign to
Y before assigning to X and it knows that the termination test has
to be performed before X can be assigned to.)  When we have

   ...
   for y = some-constant
   ...

it "moves" the assignment to Y before the termination test and the
assignment to X.  That's "safe" (the constant can be evaluated at any
time), but not generally correct (the assignments have to happen in
the order they appeared in the user's code).  If indeed CLISP only does
that when the initial value is a constant, it's not nearly as bad as
I'd first thought, but that behavior seems to be the basis for your
belief that that assignment to Y should have happened before what you
think is a "premature" termination test.


All I can say is that if you don't want to listen to me, you should
look at the macroexpansion of your test cases in CLISP and compare
what it actually does with what you think it does; if you continue to
believe what you're saying after seeing evidence to the contrary, I
don't know what the next step would be.

>
> But the workaround is obvious for the above. You can get
> both implementations to return 3 if you rearrange the
> forms:
>
>  (loop for y = 3
>        for x in nil
>        finally (return y))
>
> In my code I did the same thing: dropped all the
> removable AND's, which enabled me to massage
> the order.

Implementations other than CLISP return 3 here because in in this case
that's what they should do (the assignment to Y should precede the
termination test and possible assignment to X).

CLISP gets this right as well, in that it doesn't try to change the order
in which Y and X are initialized.


>
> This is a kludge. It should not be necessary to
> manipulate the order of the
> clauses in order to delay a premature
> termination test.

This claim would make more sense to me if (a) the relationship between
the order of clauses and the order in which initializations occur
wasn't both significant (in some cases) and well-specified (in all
cases), and (b) the termination test could be meaningfully deferred.

Even CLISP believes that the termination test has to precede assignment to
X.

The issue is that CLISP sometimes decides that the assignment to Y can be
moved to a point before the assignment to X and before the termination test
and that other times it can't.  Whether this movement happens or not matters
(if the expression used to generate the initial value of Y has side-effects
and in determining whether the value of Y at the point where termination occurs
is predictable or just "the  meaningless value" to which Y is initially bound.
(That's likely NIL in this case, but that's not guaranteed.)

>
> This seriously violates the whole loop abstraction.
>

Either that, or your model of what actually happens here needs to be revised.

Looking at the macroexpansion of any of these LOOP examples in CLISP
should convince you that there's a difference between what you think is
happening (presumably based on your interpretation of behavior) and what
actually happens in CLISP.  If you don't do that, there's a very good chance
that your model will remain inaccurate.  I don't really care as much about
that as I'm making it sound, but as soon as you made the inaccurate claim
the claim that CLISP got it right and every other implementation got it wrong,
people started accepting that and the signal-to-noise ratio on this list
dropped to near zero, and I do care about that.