#667 loop on list incompatibility

[Gabor Balazs]

The following two results should be the same and equal to '(2 3 4 5):

(loop for c from 0 to 1 for i on '(1 2 3 4 5) finally (return i))
=> (3 4 5)

(loop for c from 0 to 1 for i = '(1 2 3 4 5) then (cdr i) finally (return i))
=> (2 3 4 5)

Looking at their macroexpansions, a (WHEN (> C 1) (LOOP-FINISH)) is missing from the loop body of the first version after incrementing C.

[Sam Steingold]

while SBCL does conform to your interpretation, it is not obvious that the standard requires that the iteration variables are available in the loop epilogue (IOW, the code is non-conformant).
what do other implementations do?

[Gabor Balazs]

Hi Sam,

Indeed the standard does not mention explicitly the usage of iteration
variables in the epilogue.
However, I found these in cltl2
https://www.cs.cmu.edu/Groups/AI/html/cltl/cltl2.html indicating that
they should be available:

on page 788:
(loop for i from 1 to 10
thereis (> i 11)
finally (print i))
11
=> NIL

on page 806:
;;; The FINALLY clause prints the last value of I.
;;; The collected value is returned.
(loop for i from 1 to 10
when (> i 5)
collect i
finally (print i))
11
=> (6 7 8 9 10)

Hence I think most implementations allow using iteration variables in
epilogues, and they seem to be consistent.
The examples given in the bug report worked for me for the following
implementations:

ABCL 1.4.0 (Java 1.8.0_151 Oracle Corp.)
Allegro CL 10.0 Free Express Edition
CCL 1.11-r16635
ECL 16.1.3
Lispworks 6.1.1 Personal Edition
SBCL 1.3.20

Thanks,
bg

On Thu, Nov 23, 2017 at 1:11 AM, Sam Steingold sds@users.sf.net wrote:

while SBCL does conform to your interpretation, it is not obvious that the
standard requires that the iteration variables are available in the loop
epilogue (IOW, the code is non-conformant).
what do other implementations do?

---

• [bugs:#667] https://sourceforge.net/p/clisp/bugs/667/ loop on list
  incompatibility*

Status: open
Group: ANSI compliance issue
Labels: loop
Created: Sat Aug 30, 2014 06:08 PM UTC by Gabor Balazs
Last Updated: Sat Aug 30, 2014 06:08 PM UTC
Owner: nobody

The following two results should be the same and equal to '(2 3 4 5):

(loop for c from 0 to 1 for i on '(1 2 3 4 5) finally (return i))
=> (3 4 5)

(loop for c from 0 to 1 for i = '(1 2 3 4 5) then (cdr i) finally (return
i))
=> (2 3 4 5)

Looking at their macroexpansions, a (WHEN (> C 1) (LOOP-FINISH)) is
missing from the loop body of the first version after incrementing C.

---

Sent from sourceforge.net because you indicated interest in
https://sourceforge.net/p/clisp/bugs/667/

To unsubscribe from further messages, please visit
https://sourceforge.net/auth/subscriptions/

[Jörg Höhle]

The use of loop variables in the epilogue is IMHO not the problem. It is legal code, because IMHO the scope of all variables encompasses the epilogue, witness numerous examples using RETURN-FROM.

So what's the problem? The exact value of i.

(loop for c from 0 to 1 for i on '(1 2 3 4 5) finally (return i))
=> (3 4 5) ; wrong IMHO

The relevant piece is 6.1.2.1 Iteration Control http://clhs.lisp.se/Body/06_aba.htm
"If multiple iteration clauses are used to control iteration, variable initialization and stepping[1] occur sequentially by default. The and construct can be used to connect two or more iteration clauses when sequential binding and stepping[1] are not necessary. The iteration behavior of clauses joined by and is analogous to the behavior of the macro do with respect to do*.
The for and as clauses iterate by using one or more local loop variables that are initialized to some value and that can be modified or stepped[1] after each iteration. For these clauses, iteration terminates when a local variable reaches some supplied value or when some other loop clause terminates iteration."

No AND in the above code, so sequential stepping is mandated. Therefore, when the condition on c terminates iteration, i has not yet been stepped.
I'm surprised that despite many ANSI-CL and LOOP tests, bugs can still be found.

OTOH, a different interpretation of CLHS is possible as well. LOOP could join all termination tests, and if not terminating, proceed by assigning values using SETQ or PSETQ -- exactly like DO/DO*.
The key argument is that I found nothing in CLHS except the above about the relative ordering of stepping, which is just assigning new values http://clhs.lisp.se/Body/26_glo_s.htm#step and termination tests.

[Jörg Höhle]

So if I concede that end-test and stepping can be distinct, what about the CLtL2 example?

(loop for i from 1 to 10 thereis (> i 11) finally (print i)) ; 11

CLHS specifically defines the behaviour of the arithmetic FOR/AS:
6.1.2.1.1. http://clhs.lisp.se/Body/06_abaa.htm
"That is, iteration continues until the value var is stepped to the exclusive or inclusive limit supplied by form2."
IOW, the variable is first stepped, then is the end test performed. So the value in well-defined within the epilogue, albeit possibly larger than the limit.

[Gabor Balazs]

Very good summary Jorg. It seems to me that end tests handled the same way
by most implementations.
The CLtL2 example is not very good as the result (> i 11) is still NIL for
(= i 11).
A better one would be:

(loop for i from 1 to 10 thereis (>= i 11) finally (print i)) ; 11 => NIL

For this all implementations I mentioned before print 11 and returns NIL.
Also, CLISP 2.49.60+ (2017-06-25) works the same way as the others.

bg

On Thu, Nov 23, 2017 at 10:58 AM, "Jörg Höhle" hoehle@users.sf.net wrote:

So if I concede that end-test and stepping can be distinct, what about the
CLtL2 example?

(loop for i from 1 to 10 thereis (> i 11) finally (print i)) ; 11

CLHS specifically defines the behaviour of the arithmetic FOR/AS:
6.1.2.1.1. http://clhs.lisp.se/Body/06_abaa.htm
"That is, iteration continues until the value var is stepped to the
exclusive or inclusive limit supplied by form2."
IOW, the variable is first stepped, then is the end test performed. So the
value in well-defined within the epilogue, albeit possibly larger than the
limit.

---

• [bugs:#667] https://sourceforge.net/p/clisp/bugs/667/ loop on list
  incompatibility*

Status: open
Group: ANSI compliance issue
Labels: loop
Created: Sat Aug 30, 2014 06:08 PM UTC by Gabor Balazs
Last Updated: Thu Nov 23, 2017 03:32 PM UTC
Owner: nobody

The following two results should be the same and equal to '(2 3 4 5):

(loop for c from 0 to 1 for i on '(1 2 3 4 5) finally (return i))
=> (3 4 5)

(loop for c from 0 to 1 for i = '(1 2 3 4 5) then (cdr i) finally (return
i))
=> (2 3 4 5)

Looking at their macroexpansions, a (WHEN (> C 1) (LOOP-FINISH)) is
missing from the loop body of the first version after incrementing C.

---

Sent from sourceforge.net because you indicated interest in
https://sourceforge.net/p/clisp/bugs/667/

To unsubscribe from further messages, please visit
https://sourceforge.net/auth/subscriptions/

[Jörg Höhle]

There clearly are lots of diverging opinions about values within FINALLY. I just came across Robert Strandh's A modern implementation of the LOOP macro
(loop for i from 0 below 10 sum i finally (print i))
"we have an example of a non-conforming implementation as explained in section 1.5.1. The reason is that the standard clearly stipulates that every implementation must print 9, whereas MIT loop prints 10."

In his eyes, it must look like one bogus implementation (MIT loop) nevertheless became successful then mandates its bogus result upon others by way of "user expectation".

[Sam Steingold]

yeah, I wonder if we should just abandon our loop in favor of his ;-)
https://github.com/robert-strandh/SICL

[Bruno Haible]

> I wonder if we should just abandon our loop in favor of his ;-) https://github.com/robert-strandh/SICL

46 files to implement the LOOP macro!! The MIT LOOP macro was already written to be extensible (which is overkill for a standardized functionality); this one is not only extensible but also modular (whatever this may mean).

[Sam Steingold]

The problem is that under certain circumstances we separate initializing and binding of a variable.
I wonder if something like "lazy-binding" could help: bind the variable but not initialize its value. until it is explicitly set, accessing it reaches up in the environment. This would require something like lazy-let with the following test cases:

(let ((a 1))
  (lazy-let (a b)
    (print a) ; prints 1
    (print b) ; error - unbound variable
    (setq a 10) ; inner binding of a is activated
    (print a) ; prints 10
    (setq b 22)) ; binding of b is activated
  (print b) ; error - unbound variable
  (print a)) ; prints 1

while it is easy to avoid lazy-let above by putting let after second print, it is not so easy with loop because we need the binding to exist around the main tagbody but to do initialization in the preamble inside tagbody.

Loop expansion then will loop like this:

(lazy-let (all the loop local variables thay are now bound by let)
  (tagbody 
     preamble - set all the loop local variables thay are now bound by let
     ...
     )) ; close tagbody and lazy-let

wdyt?

oops, sorry, this is more relevant to https://sourceforge.net/p/clisp/bugs/375/
see also https://sourceforge.net/p/clisp/mailman/message/36162784/

[Jörg Höhle]

Quite on the contrary, my current thoughts are strongly influenced by "how can we immediately bind with the correct values (not wasting time for other initializations)?" I'll write down my proposal ASAP, but have no time now. But the original bug report, unlike bug #375 is about FINALLY, not initialisation. In clisp, currently both are mixed up, because the order of FOR clauses currently influences the stepping in weird and unforeseen ways.

[Sam Steingold]

consider (loop for x across v do (print x)).
x is initialized in let to nil.
yes, we can init it to aref (after testing (length v)!) but then we will have two (aref v 0) calls and two length checks - one in let and one in the iteration.
ugly.