LOOP type declaration issue

[Nikodemus Siivola]

Reported by Stas Boukarev on sbcl-devel.

(loop for i from most-negative-fixnum to most-positive-fixnum
      count i))

expands into

(BLOCK NIL
  (LET ((I MOST-NEGATIVE-FIXNUM))
    (DECLARE (TYPE (AND REAL NUMBER) I))
    (LET ((#:LOOP-SUM-899 0))
      (DECLARE (TYPE FIXNUM #:LOOP-SUM-899))
      (SB-LOOP::LOOP-BODY NIL
                          (NIL NIL
                           (WHEN (> I '536870911) (GO SB-LOOP::END-LOOP)) NIL)
                          ((WHEN I (SETQ #:LOOP-SUM-899 (1+ #:LOOP-SUM-899))))
                          (NIL (SB-LOOP::LOOP-REALLY-DESETQ I (1+ I))
                           (WHEN (> I '536870911) (GO SB-LOOP::END-LOOP)) NIL)
                          ((RETURN-FROM NIL #:LOOP-SUM-899))))))

Where counter has type FIXNUM even though the count becomes a bignum.

Note also the (AND REAL NUMBER) declaration for I: smarter placement of the termination test would allow a FIXNUM declaration there.

[Nikodemus Siivola (nikodemus)]

CLHS says about LOOP COUNT:

"The count construct counts the number of times that the supplied form returns true. The argument var accumulates the number of occurrences; if var is supplied, loop does not return the final count automatically. The var argument is bound as if by the construct with to a zero of the appropriate type. Subsequent values (including any necessary coercions) are computed as if by the function 1+. If into var is used, a type can be supplied for var with the type-spec argument; the consequences are unspecified if a nonnumeric type is supplied. If there is no into variable, the optional type-spec argument applies to the internal variable that is keeping the count. The default type is implementation-dependent; but it must be a supertype of type fixnum."

So FIXNUM appears to be a legal assumption, actually. Suboptimal, but legal.

[Eugene Ossintsev (eugoss-deactivatedaccount)]

By the way, in Clozure CL 1.4 it's also FIXNUM.

(BLOCK NIL
  (LET ((I MOST-NEGATIVE-FIXNUM))
    (DECLARE (TYPE NUMBER I))
    (LET ((#:LOOP-SUM-0 0))
      (DECLARE (TYPE FIXNUM #:LOOP-SUM-0))
      (ANSI-LOOP::LOOP-BODY NIL
                            (NIL NIL NIL NIL)
                            ((WHEN I (SETQ #:LOOP-SUM-0 (1+ #:LOOP-SUM-0))))
                            (NIL (ANSI-LOOP::LOOP-REALLY-DESETQ I (1+ I))
                                 (WHEN (> I '1152921504606846975)
                                   (GO ANSI-LOOP::END-LOOP))
                                 NIL)
                            ((RETURN-FROM NIL #:LOOP-SUM-0))))))

[Michał "phoe" Herda (phoe-krk)]

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

(declaim (optimize (safety 0)))

(lambda ()
  (loop for x of-type fixnum
        from (1- most-positive-fixnum) to most-positive-fixnum
        do (progn)
        finally (print x)))

(compile nil *)

(funcall *)

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

The above loops even though it is conforming ANSI CL.

[Swapneil Singh (swapneils)]

Just running the above loop directly in the REPL without any declaimations also fails (SBCL 2.4.3, but I don't see any recent commits that would change this).

(loop for x of-type fixnum
      from (1- most-positive-fixnum) to most-positive-fixnum
      do (progn)
      finally (print x))
=> ; Debugger entered on #<TYPE-ERROR expected-type: FIXNUM datum: 4611686018427387904>

The code is macroexpanded to:
(BLOCK NIL
  (LET ((X (1- MOST-POSITIVE-FIXNUM)))
    (DECLARE (IGNORABLE X)
             (TYPE (AND REAL FIXNUM) X))
    (TAGBODY
     SB-LOOP::NEXT-LOOP
      (WHEN (> X '4611686018427387903) (GO SB-LOOP::END-LOOP))
      (PROGN)
      (SB-LOOP::LOOP-DESETQ X (1+ X))
      (GO SB-LOOP::NEXT-LOOP)
     SB-LOOP::END-LOOP
      (PRINT X))))

Which is incorrect as X gets incremented past the end value.

It may be better to duplicate the short-circuit check, once *before* the NEXT-LOOP tag and again at the end of the loop body. Desired macroexpansion:
(BLOCK NIL
  (LET ((X (1- MOST-POSITIVE-FIXNUM)))
    (DECLARE (IGNORABLE X)
             (TYPE (AND REAL FIXNUM) X))
    (TAGBODY
     (WHEN (> X '4611686018427387903) (GO SB-LOOP::END-LOOP))
     SB-LOOP::NEXT-LOOP
      (PROGN)
      (SB-LOOP::LOOP-DESETQ X (1+ X))
      (WHEN (>= X '4611686018427387903) (GO SB-LOOP::END-LOOP))
      (GO SB-LOOP::NEXT-LOOP)
     SB-LOOP::END-LOOP
      (PRINT X))))

That would require some refactoring in `loop.lisp`, however, as it doesn't look like the master sequencer (where the END-LOOP check is defined) can specify multiple tests for a single loop form (nor the position of the test in the loop form, but given `loop-hack-iteration` has multiple test positions I assume those are specified somewhere else that I'm missing).

[Swapneil Singh (swapneils)]

No, given the position of the loop body that doesn't work.

`(>= X end-value)` could be replaced with `(>= X <end-value minus step/1>)`, though, in which case the following macroexpansion gives the correct behavior.

(BLOCK NIL
  (LET ((X (1- MOST-POSITIVE-FIXNUM)))
    (DECLARE (IGNORABLE X)
             (TYPE (AND REAL FIXNUM) X))
    (TAGBODY
     (WHEN (> X '4611686018427387903) (GO SB-LOOP::END-LOOP))
     SB-LOOP::NEXT-LOOP
      (PROGN)
      (WHEN (> X '4611686018427387902) (GO SB-LOOP::END-LOOP))
      (SB-LOOP::LOOP-DESETQ X (1+ X))
      (GO SB-LOOP::NEXT-LOOP)
     SB-LOOP::END-LOOP
      (PRINT X))))