Re: LOOP blows!

On Feb 7, 8:51 pm, Edi Weitz <spamt...@xxxxxxxxxx> wrote:
On Thu, 7 Feb 2008 20:33:58 -0800 (PST), Kaz Kylheku <kkylh...@xxxxxxxxx> wrote:
Try:

  (loop for x = '(1 2 3) for y in x collect y)

If that yields NIL, it shows that the broken LOOP isn't propagating
the '(1 2 3) from the first FOR to the second.

My understanding of the LOOP specification is that your expectation is
wrong.  Amongst other things, in 6.1.1.8 it explicitly says that the
rules in 3.6 have to be obeyed, specifically the one about list
traversal.

That talks about some destructive modification of CDR fields, which we
don't have going on at all.

I'm modifying the variable X. Except I'm ``modifying'' it by assigning
exactly the same value to it (same literal object, EQ!).

Even if the FOR Y = X clause were to work by stepping a hidden integer
K from 0, and evaluating (NTH K X) at every iteration to pull out the
value, it should still work right.

The problem with these implementations that return NIL is that they
use the old value of X before it is initialized. And that contravenes
the idea that the FOR clauses are ordered.

They are ordered because stuff like this works:

(loop for linear below 10
for quadratic = linear then (+ quadratic linear)
collect quadratic)

=> (0 1 3 6 10 15 21 28 36 45)

If the "FOR QUADRATIC =" clause behaved like our "FOR Y IN X", it
should access a NIL value of LINEAR in the first iteration, right? But
it doesn't; it retrieves the value 0, because the clauses are done in
series.

 If the loop above behaved as you'd expect in a conforming
implementation, how would you expect

    (loop for i from 5 downto 2
          for x = (loop for j below i collect j)
          for y in x
          collect y)

to behave?

My interpretation:

In the first iteration, i would get the value 5. Then x would get the
value of the expression (loop for j below i collect j), in other words
(0 1 2 3 4). Then y would be set up to iterate over this (0 1 2 3 4)
list. On the subsequent iterations, the value of x would change to (0
1 2 3), but that's of no consequence, since y steps over the original
list, and new values of X are simply ignored. Termination comes from
the first clause, when i reaches value 2, and so y manages to iterate
only over (0 1 2 3), which is what is collected.

I think the Lisp you're using is broken.

The machine where I'm trying all this has an installation of CLISP
2.38.

Let's see what it does with your example:

[1]> (loop for i from 5 downto 2
for x = (loop for j below i collect j)
for y in x
collect y)
(0 1 2 3)

Bingo; CLISP 2.38 conforms to the Kaz model. I should try the bleeding
edge version; maybe they did something to screw up loop in the last
two years.

FWIW, LispWorks also returns NIL for your example and that seems to be
right to me.

They're just stealing broken code from SBCL. :)

But seriously, what is their macroexpansion?

ACL also returns NIL (I'm trying via their live telnet REPL). ACL's
expansion is:

(BLOCK NIL
(LET ((X NIL))
(LET ((Y NIL) (#:G17 X)) (DECLARE (IGNORABLE Y) (TYPE L IST #:G17))
(WITH-LOOP-LIST-COLLECTION-HEAD (#:G18 #:G19)
(TAGBODY NEXT-LOOP (LOOP-REA LLY-DESETQ X '(1 2 3))
(WHEN (ENDP #:G17) (GO END-LOOP)) (LOOP-REALLY-DESET Q Y (CAR
#:G17))
(LOOP-REALLY-DESETQ #:G17 (CDR #:G17))
(LOOP-COLLECT-RPLACD (#:G18 #:G19) (LIST Y)) (GO NEXT-LOOP) END-
LOOP
(RETURN-FROM NIL (LOOP-COLLECT-ANSWER #:G18)))))))

This #:G17 gensym is used which holds a copy of the original X.

Aha, what this is saying is that the expression in a FOR IN is
special. It is evaluated outside of the normal order of the FOR
expressions, prior to the loop.

The value of X is reduced and assigned to a gensym outside of the loop
itself.

Let's make this super clear:

(loop for x = '(1 2 3) for y in x for z = x do (return x y z))

But this is inconsistent with the way variable references work in the
other for clauses! If I use ACL to evaluate:

(loop for x = 42 for y = x do (return y))

I simply get 42. Macroexpansion:

(BLOCK NIL
(LET ((X NIL))
(LET ((Y NIL))
(TAGBODY
EXCL::NEXT-LOOP
(EXCL::LOOP-REALLY-DESETQ X 42)
(EXCL::LOOP-REALLY-DESETQ Y X)
(RETURN Y)
EXCL::END-LOOP))))

See? Straightforward sequential processing.

So in the clause "for y = x", the way x is referenced is different
from the way it is referenced in "for y in x".

That's the problem. Inconsistent lexical reference semantics from two
very similar contexts!

What a bagbiter.
.

Relevant Pages

  • Re: LOOP blows!
    ... The order of initialization follows the ... There are two `initializations' in execution of LOOP, ... before staring the first iteration. ... |> The first for clause will never terminate. ...
    (comp.lang.lisp)
  • Re: LOOP blows!
    ...     clauses appear in the source. ... This clause is not combined with the ... Right, and ``People'' includes the ones implementing LOOP, apparently, ... You must use your hidden list iteration variable to set up the ...
    (comp.lang.lisp)
  • Re: The LOOP macro (was Re: Be afraid of XML)
    ... >> the finally clause. ... > "A loop macro form expands into a form containing ONE OR MORE BINDINGS ... > "The LOOP EPILOGUE CONTAINS forms that are executed after iteration ...
    (comp.lang.lisp)
  • Re: Re: strange anomalies when using an iteration variable twice in 1 function
    ... >for loop control variables are reused, ... If the array is defined as you described, ... >arrayOfString is not defined the way you think it is. ... aTemplates:= nil; ...
    (alt.comp.lang.borland-delphi)
  • Re: loop variable value in finally forms?
    ... because I'd have never written the loop this way. ... is nil after the list is exhausted. ... internal and single user-given variables can be identical. ... the Iterate package currently behaves differently (it ...
    (comp.lang.lisp)