Wanted: Warn when a LAMBDA capturing the binding of an iteration variable escapes the dynamic extent of the iteration that introduced it

Bug #775712 reported by Jean-Philippe Paradis on 2011-05-02
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Wishlist
Unassigned

Bug Description

I believe these 4 pieces of code should result in a compile-time WARNING, because their effect is specified to be implementation-dependent and won't do what one probably wants across all implementations.

(mapcar #'funcall
        (let (list)
          (dolist (i '(0 1 2) (nreverse list))
            (push (lambda () i) list))))
;; This is the result we probably wanted, but another implementation can return something else!
;; This is a portability hazard. I have tons and tons of old code that does this.
;; Some SBCL internals might rely on DOLIST's fresh binding, so maybe the WARNING should be disabled in SBCL's implementation code?
=> (0 1 2)

(mapcar #'funcall
        (let (list)
          (dotimes (i 3 (nreverse list))
            (push (lambda () i) list))))
;; One might seriously waste hours searching for the bug in a real coding scenario
;; if he wasn't aware that a fresh binding is not necessarily created on each new iteration.
;; I know I did, some time ago! Even more puzzling because DOLIST just happens to have the intended effect on SBCL.
=> (3 3 3)

(mapcar #'funcall
        (loop for i below 3
              collect (lambda () i)))
=> (3 3 3)

(let (previous list)
  (dotimes (i 3 (progn (push (funcall previous) list)
                       (nreverse list)))
    (when previous
      (push (funcall previous) list))
    (setf previous (lambda () i))))
;; Notice the nice off-by-one...
;; This code is much less likely to get written, but it illustrates that the problem is when the LAMBDA capturing the iteration variable escapes the iteration where it was introduced, not just when it escapes the iteration construct entirely.
=> (1 2 3)

So, a warning a bit like this would be nice:

"WARNING: Lambda #<FUNCTION (LAMBDA #) {AB13235}> captures the binding of iteration variable I and escapes the dynamic extent of the DOLIST iteration that introduced it. The standard specifies that:

"It is implementation-dependent whether DOLIST establishes a new binding of var on each iteration or whether it establishes a binding for var once at the beginning and then assigns it on any subsequent iterations."

See http://www.lispworks.com/documentation/HyperSpec/Body/m_dolist.htm"

Jean-Philippe Paradis <email address hidden> writes:

> I believe these 4 pieces of code should result in a compile-time
> WARNING, because their effect is specified to be implementation-
> dependent and won't do what one probably wants across all
> implementations.

I don't. I think there's value for sbcl to distinguish some unportable
code scenarios, but "implementation-dependent" is a long, long way away
From "undefined consequences", which is what has normally triggered a
compile-time WARNING. Consider: what if you actually /want/ to write
this code? How do you tell the system "yes, I know what I'm doing?".
(This is in contrast with the "undefined consequences" situation, where
there is no way in fact that the writer of code causing undefined
consequences really knows what they are doing).

Christophe

I support Christophe in this discussion. Also, look at this macroexpansion, there is no DOLIST when it comes to the places in the compiler where such analysis is possible:

* (macroexpand '(dolist (i '(0 1 2) (nreverse list))
                              (push (lambda () i) list)))

(BLOCK NIL
  (LET ((#:N-LIST597 '(0 1 2)))
    (TAGBODY
     #:START598
      (UNLESS (ENDP #:N-LIST597)
        (LET* ((#:TMP599 (TRULY-THE (MEMBER 2 1 0) (CAR #:N-LIST597)))
               (I #:TMP599))
          (SETQ #:N-LIST597 (CDR #:N-LIST597))
          (TAGBODY (PUSH (LAMBDA () I) LIST)))
        (GO #:START598))))
  (LET ((I NIL))
    I
    (NREVERSE LIST)))

At this moment, DOLIST context is lost, so the compiler cannot warn you about it. The alternative solution is to describe this somewhere in the manual (to show the behavior of this code in SBCL).

> "implementation-dependent" is a long, long way away from "undefined consequences"

Actually, I think in this case, it's a short, short way away from it. Consider this:

Did SBCL, as a project, go out of its way to define this behavior and document it, and is it ready to support the current behavior "in perpetuity"? Did it carefully analyse the situation and decide: "Yes, the correct thing to do is definitely to provide a fresh binding for each iteration of DOLIST, and reuse the same binding for all iteratinos of DOTIMES and LOOP!" ?

Or is the current behavior a mere implementation detail that wasn't explicitly considered and is subject to change? In my view, "This is implementation-defined behavior which this implementation doesn't explicitly define" is about the same thing as "This is undefined behavior."

And it's possible (and allowed) for behaviors specified as undefined to be defined by implementations, so the difference between undefined and implementation-defined is somewhat "philosophical".

> At this moment, DOLIST context is lost, so the compiler cannot warn you about it.

What about something like this?

(BLOCK NIL
  (LET ((#:N-LIST597 '(0 1 2)))
    (TAGBODY
       #:START598
       (UNLESS (ENDP #:N-LIST597)
         (LET* ((#:TMP599 (TRULY-THE (MEMBER 2 1 0) (CAR #:N-LIST597)))
                (I #:TMP599))
           ;; Hypothetical new declaration type
           (DECLARE (ITERATION-VARIABLE DOLIST I))
           (SETQ #:N-LIST597 (CDR #:N-LIST597))
           (TAGBODY (PUSH (LAMBDA () I) LIST)))
         (GO #:START598))))
  (LET ((I NIL))
    (DECLARE (ITERATION-VARIABLE DOLIST I))
    I
    (NREVERSE LIST)))

The fact that it comes from a DOLIST doesn't necessarily have to be recorded, but you get the point. The fact that the required contextual information is *currently* lost doesn't seem like a problem to me at all!

The idea with the declarations is smart, so let us suppose that there are no technical difficulties in generating such warnings (however, I estimate the implementation to be quite complex). But should we really warn? Implementation-dependent stuff is defined in CLHS like this:

"implementation-dependent adj. describing a behavior or aspect of Common Lisp which has been deliberately left unspecified, that might be defined in some conforming implementations but not in others, and whose details may differ between implementations. A conforming implementation is encouraged (but not required) to document its treatment of each item in this specification which is marked implementation-dependent, although in some cases such documentation might simply identify the item as ``undefined.''

So, CLHS asks us to document this, not to warn about this. I still think that the best way is to update the manual, or tweak DOLIST to handle the binding in another way. However, we may ask developers on sbcl-devel to give their opinions, and in case people support this, some patch is likely to come. Feel free to write such a mail.

Anyway, thank you for reporting this and other issues, it really helps us to make SBCL better!

Best Regards,
Roman

Nikodemus Siivola (nikodemus) wrote :

"Would be nice", but definitely not a priority.

I suspect the best way to approach this would be (declare (warn-on-closure x)) or similar.

At the same time, I do wonder if it's really worthwhile not to introduce those bindings for iteration variables by default. Might just be the easiest thing all around.

Changed in sbcl:
importance: Undecided → Wishlist
status: New → Triaged
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers