loop macro could be improved

[William Cushing]

This is problematic:

(loop for i of-type (integer 0 (1- N)) from (1- N) downto 0 do <anything>)

I imagine with the right declarations in place the compiler would issue appropriate warnings; with (safety 0), the code compiles into an infinite loop.

I believe that the issue is that the loop macro expands into < rather than <= for the termination test (at least when counting down --- I didn't investigate the opposite direction), so the type needed for the index is (integer (- end 1) start) rather than the arguably more correct (integer end start). With (safety 0), the type declaration is believed, which in this case leads to unsigned/modular arithmetic being used, and the loop can't be exited --- but only because the macro writer presumed signed arithmetic, or more generally, that a value less than the terminal value is representable within the same type.

Note that one important reason to be writing a loop that counts down is because one suspects that the machine can check for equality with zero more efficiently than equality with any other constant. (...Or because one doesn't want to finish off by calling reverse.) That is, it'd be kindof nice to get this particular corner case --- counting down to zero --- of loop to expand the "right" way.

-----------------------

Another problematic loop expansion:

(loop for i from 1 to 2 nconcing '(a b)) ; diverges

Note that neither of the following three fails:

(loop for i from 1 to 2 appending '(a b)) ; -> (A B A B), as expected
(loop for i from 1 to 2 nconcing `(,i ,i)) ; -> (1 1 2 2), as expected
(let ((x (list 'a 'b))) (nconc x x)) ; -> #1=(A B . #1#), as expected
(loop for i from 1 to 2 nconcing (list 'a 'b)) ; -> (A B A B), as expected

It isn't enough for one part of the structure to be variable:

(loop for i from 1 to 2 nconcing `(,i (b))) ; diverges

It *is* enough if the tail is variable:

(loop for i from 1 to 3 nconcing `((b) ,i)) ; works fine

...but that behavior is extremely fragile:

(loop for i from 1 to 2 nconcing `(,(if i 'a nil) ,(car (cons 'b nil)))) ; -> (A B A B), as expected, ...but...
(loop for i from 1 to 2 nconcing `(,(if i 'a nil) . ,(cons 'b nil))) ; diverges, not *at all* as expected....

Of course appending works just fine:

(loop for i from 1 to 2 appending `(,(if i 'a nil) . ,(cons 'b nil))) ; -> (A B A B), as expected
(loop for i from 1 to 2 appending `(,(if i 'a nil) ,(car (cons 'b nil)))) ; -> (A B A B), as expected

Instead of using car/cons, one can also use "if" to build the tail --- the results are again extremely fragile for nconcing.

This test case is perhaps the most interesting:

(let ((x '(a b))) (nconc x x)) ; -> #1=(A B . #1#), as expected,

...but with a compiler warning (nconc called with constant data) and a reference to the ANSI spec.

-----------------------

I suppose all the cool kids use iterate, not loop. Perhaps iterate doesn't fail in the above ways.

------------------------

$ sbcl --version
SBCL 1.1.13

$ uname -a
Linux ubuntu 3.5.0-44-generic #67-Ubuntu SMP Tue Nov 12 19:36:14 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux

(:CLOS :QUICKLISP :SB-BSD-SOCKETS-ADDRINFO :ASDF3 :ASDF2 :ASDF :OS-UNIX
 :NON-BASE-CHARS-EXIST-P :ASDF-UNICODE :ALIEN-CALLBACKS :ANSI-CL
 :ASH-RIGHT-VOPS :C-STACK-IS-CONTROL-STACK :COMMON-LISP :COMPARE-AND-SWAP-VOPS
 :COMPLEX-FLOAT-VOPS :CYCLE-COUNTER :ELF :FLOAT-EQL-VOPS :GENCGC
 :IEEE-FLOATING-POINT :INLINE-CONSTANTS :LARGEFILE :LINKAGE-TABLE :LINUX
 :LITTLE-ENDIAN :MEMORY-BARRIER-VOPS :MULTIPLY-HIGH-VOPS :OS-PROVIDES-BLKSIZE-T
 :OS-PROVIDES-DLADDR :OS-PROVIDES-DLOPEN :OS-PROVIDES-GETPROTOBY-R
 :OS-PROVIDES-POLL :OS-PROVIDES-PUTWC :OS-PROVIDES-SUSECONDS-T
 :PACKAGE-LOCAL-NICKNAMES :RAW-INSTANCE-INIT-VOPS :SB-DOC :SB-EVAL :SB-FUTEX
 :SB-LDB :SB-PACKAGE-LOCKS :SB-SIMD-PACK :SB-SOURCE-LOCATIONS :SB-TEST
 :SB-THREAD :SB-UNICODE :SBCL :STACK-ALLOCATABLE-CLOSURES
 :STACK-ALLOCATABLE-FIXED-OBJECTS :STACK-ALLOCATABLE-LISTS
 :STACK-ALLOCATABLE-VECTORS :STACK-GROWS-DOWNWARD-NOT-UPWARD :UNIX
 :UNWIND-TO-FRAME-AND-CALL-VOP :X86-64)

[Douglas Katzman (dougk)]

None of the examples constitute incorrect, nor even undesirable behavior, if (safety 0) is to have any benefit.

In (integer 0 (1- n)), assuming that (1- n) is metasyntax, and not syntax for an exclusive upper bound, the declaration is subtly incorrect.
LOOP's downto clause is explained by CLHS saying:
 "the loop terminates when the variable 'var' passes the value of 'form2'"

Fix N to 5 for the sake of concreteness. Your example is like the following (incorrect) DO form:
 (do ((i 5 (1- i)))
        ((< i 0))
  (declare ((integer 0 5) i))
  (print i))

Safe code will tell you that -1 isn't an (INTEGER 0 5) but unsafe code will never terminate.
The type of I should have been (INTEGER -1 5) because the step form has to bump the iteration variable beyond the lower bound.

"fragility" of the nconc examples has to do with illegal modification of quoted constants.
The compiler detects the improper usage (nconc '(a b) '(a b)) but the LOOP usage is equally illegal, though nontrivial to detect and warn about.

(loop ... nconcing `(,i (b))) is illegal for the same reason.
The backquoted expression `(,i (b)) is the equivalent of (cons i '((b))) [or in some alternative implementation of backquote, perhaps it is construed as (list i '(b)) but not in SBCL's backquote]
It is the cdr of '((b)) that nconc is not allowed to mutate.