#'equal compare true compared to (list 7 1) but false when compared to '(7 1), why?

Question

SBCL 1.3.1

In summary, a is a list, '(7), b is set to the same list via setq. A value is appended to b. List c is set to the expected result after the append, i.e. '(7 1). a is then compared to c and correctly compares true. However, when a is compared via (equal a '(7 1)), it compares false.

My guess is that the compiler has not seen the append, as it was done on b, and has optimized away the compare to constant with the incorrect result. If so, what options are there to tip off the compiler. Can a be marked as special somehow? Or, apart from style issues related to destructive programming, is there something else going on here?

    (defun test-0 ()
      (let ((a '(7))
            b
            (c '(7 1)))
        (setq b a)
        (setf (cdr b) (cons 1 '()))
        (pprint (list a b c))

        (values (equal c a) (equal '(7 1) a) (equal (list 7 1) a) c a)))


    * (test-0)

    ((7 1) (7 1) (7 1))
    T
    NIL  <== ??
    T
    (7 1)
    (7 1)

Here is the transcript as it is loaded and run in an empty environment. The file is a copy and paste of the code above. One can see that there are no error messages. It is interesting to see here that the results are different.

§sbcl> sbcl
This is SBCL 1.3.1.debian, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
* (load "src/test-0")

T
* (test-0)

((7 1) (7 1) (7 1))
NIL
NIL
T
(7 1)
(7 1)
*

You should avoid using quoted lists when binding values to variable. Those always tend to cause strange behaviour when modified (just replace them with `(list ...)` and the code should work). — jkiiski, Jan 19 '16 at 14:05
yes that fixes it, and it makes perfect sense that quoted lists would be constants and not available to be modified. If you want that as an 'answer' add it and I'll mark it. — , Jan 19 '16 at 14:29
@user244488 That's an appropriate answer for "what should I do in order to avoid this", but it doesn't explain the behavior that you're getting. The modification *does* happen, in fact (though that's undefined behavior); the behavior is that the equality test is getting optimized away. I've added an answer with some more details. — Joshua Taylor, Jan 19 '16 at 14:39
I think that you have found an issue with the SBCL compiler, that should be reported to the maintainers. Here is another SBCL session that shows another problem with the compiler: `* (defvar a '(7)) A * (defvar c '(7 1)) C * (rplacd a '(1)) (7 1) * (equal a c) T * (let* ((a '(7)) (c '(7 1))) (rplacd a '(1)) (equal a c)) T `. Of course one could always says that undefined consequences can lead to any behaviour. But I think there should be some logic inside all this madness... :) — Renzo, Jan 19 '16 at 15:27
@Renzo There *is* some logic here. The code included literal data. The compiler used that literal data to optimize away a comparison. That's a pretty reasonable thing for a compiler to do. I think the only real improvement that could happen here is that SBCL could be more aggressive about issuing the warning about modifying literal data, if it could have been detected in this case. In you example, there might be some check that only does that optimization when applied to local variables; who knows? — Joshua Taylor, Jan 19 '16 at 15:35
@JoshuaTaylor, but in my example the last expression is identical to your first example. So, why the compiler treat it differently? Only because the are two global variables with the same name? It seems that the optimizer has a behaviour that depends from something that does not concern the code that must be optimized (two different global variables that happen to have the same name that two local variables). — Renzo, Jan 19 '16 at 15:42
@Renzo Your last example *isn't* equivalent to mine. Since you're done an earlier **defvar**, you've made **a** and **c** globally declared special. That means that those bindings with **let\*** are *special* bindings. Maybe SBCL doesn't do that optimization in that case. As a slightly different case, suppose that instead of returning the value of `(equal a c)` you'd returned `(lambda () (equal a c))`. SBCL definitely couldn't do the optimization, since the values of `a` and `c` can't be known until that function is called. — Joshua Taylor, Jan 19 '16 at 15:47
Of course you are right, the examples are different, but `a` and `b` inside `(let* ((a '(7)) (c '(7 1))) (rplacd a '(1)) (equal a c))` are local variables, and the compiler should treat them not using any information on global variables with the same name (that could have completely different types and values). — Renzo, Jan 19 '16 at 15:54
@Renzo They're *not* "local" variables; they're not *lexically* scoped. They're *special* (i.e., dynamically scoped), so non-local changes could modify them. That's probably enough for the compiler to skip the optimization. E.g., after `(defvar a 10) (defun change-a () (setf a 12))`, `(let ((a 13)) (change-a) a)` is 12, not 13. Since that kind of non-local change can happen to special variables, it makes sense that SBCL wouldn't perform the optimization in your code, since the variables *aren't* just "local" variables. — Joshua Taylor, Jan 19 '16 at 16:44
@JoshuaTaylor thanks very much for the clarification. I got it wrong. — Renzo, Jan 19 '16 at 19:25

score 5 · Answer 1 · answered Jan 19 '16 at 14:10

5

Quoted lists are "literals", modifying them (as you do in (setf (cdr b) ...)) leads to undefined consequences. Any outcome from test-0 would be valid, e.g., formatting your hard disk and blowing up your house.

Replace '(7) with (list 7) and you should get what you expect.

PS. Please format your code properly.

answered Jan 19 '16 at 14:10

sds

58,617
29
161
278

5

I just have to say, as it really happened, as you posted this the neighbor came by and said she smelled something burning and was concerned. – Jan 19 '16 at 15:30

score 4 · Accepted Answer · edited May 23 '17 at 12:31

As sds says, you're modifying literal data, and the short answer is "don't do that." Modifying literal data is undefined behavior and "anything" can happen. That said, usually the results are relatively predictable (e.g., see Unexpected persistence of data), and this case is a bit surprising. It appears that what's happening is that SBCL optimizes the call (equal …) when it "knows" that the values should be different (since they're different literals).

Since this is kind of unexpected, I think it's worth looking into. We can isolate this down to letting a and c be literal lists, and then modifying a to make it an equal value:

CL-USER> (let* ((a '(7))
                (c '(7 1)))
           (rplacd a '(1))
           (equal a c))
; in: LET* ((A '(7)) (C '(7 1)))
;     (RPLACD A '(1))
; --> LET PROGN SETF 
; ==>
;   (SB-KERNEL:%RPLACD #:N-X0 '(1))
; 
; caught WARNING:
;   Destructive function SB-KERNEL:%RPLACD called on constant data.
;   See also:
;     The ANSI Standard, Special Operator QUOTE
;     The ANSI Standard, Section 3.2.2.3
; 
; compilation unit finished
;   caught 1 WARNING condition
NIL

Now let's take a look at the compiled code that expression gets turned into:

CL-USER> (disassemble (lambda ()
                        (let* ((a '(7))
                               (c '(7 1)))
                          (rplacd a '(1))
                          (equal a c))))

; disassembly for (LAMBDA ())
; Size: 60 bytes. Origin: #x10062874D4
; 4D4:       488D5C24F0       LEA RBX, [RSP-16]               ; no-arg-parsing entry point
; 4D9:       4883EC18         SUB RSP, 24
; 4DD:       488B158CFFFFFF   MOV RDX, [RIP-116]              ; '(7)
; 4E4:       488B3D8DFFFFFF   MOV RDI, [RIP-115]              ; '(1)
; 4EB:       488B058EFFFFFF   MOV RAX, [RIP-114]              ; #<FDEFINITION for SB-KERNEL:%RPLACD>
; 4F2:       B904000000       MOV ECX, 4
; 4F7:       48892B           MOV [RBX], RBP
; 4FA:       488BEB           MOV RBP, RBX
; 4FD:       FF5009           CALL QWORD PTR [RAX+9]
; 500:       BA17001020       MOV EDX, 537919511
; 505:       488BE5           MOV RSP, RBP
; 508:       F8               CLC
; 509:       5D               POP RBP
; 50A:       C3               RET
; 50B:       CC0A             BREAK 10                        ; error trap
; 50D:       02               BYTE #X02
; 50E:       19               BYTE #X19                       ; INVALID-ARG-COUNT-ERROR
; 50F:       9A               BYTE #X9A                       ; RCX

Now, you can see where there's a function call to rplacd, but you don't see one for equal. I think that what's happening here is that the compiler knows that equal will return false when (7) and (7 1) are compared, and hard codes it.

One way to test this might be to parameterize the test so that the compiler can't optimize it. Sure enough:

(defun maybe (test)
  (let* ((a '(7))
         (c '(7 1)))
    (rplacd a '(1))
    (funcall test a c)))

With this, you get the results you might have expected. Now a and c are equal, but not eq:

CL-USER> (maybe 'equal)
T

CL-USER> (maybe 'eq)
NIL

Another way to test this would be to make a call to copy-list and compare a copy of a with c (assuming that SBCL won't optimize the call to copy-list away to produce a copy of a's original value):

CL-USER> (let* ((a '(7))
                (c '(7 1)))
           (rplacd a '(1))
           (values (equal a c)
                   (equal (copy-list a) c)))
; ...
NIL    ; (equal a c)
T      ; (equal (copy-list a) c)

Josh, thanks that really ties it together. That error would have been helpful, but apparently the compiler did do some optimization so it didn't happen. That is interesting. — , Jan 19 '16 at 14:40
What error would have been helpful? When you compiled your code, you should have gotten a similar diagnostic message. When I run your code, I get a similar message. — Joshua Taylor, Jan 19 '16 at 14:48
BTW, thank you for the assembly code example. Been a while since I've read much x86 code, but I followed that - largely due to your comments as I had no idea the address for rplacd (or perhaps you surmise that from the order). The test that I quoted in the original post, test-0, compiles without any noise. — , Jan 19 '16 at 15:00
@user244488 I didn't add the comments into the output from **disassemble**; those are provided by SBCL. :) — Joshua Taylor, Jan 19 '16 at 15:03
The original code doesn't give that warning because of the `(setq b a)`. If you leave out the `b`-variable, you'll get a warning. — jkiiski, Jan 19 '16 at 15:07
@jkiiski I guess I wasn't running OP's exact code. My mistake. I get the behavior you're describing. — Joshua Taylor, Jan 19 '16 at 15:10
I've add the load and run transcript verbatim from a fresh run of sbcl at the bottom of the post. And of course, the result is different. However, there is no error given. — , Jan 19 '16 at 15:32
@user244488 Yes, as I replied to jkiiski, I was mistaken. I must not have been loading your exact code. When I run your exact code, I don't get the warning. — Joshua Taylor, Jan 19 '16 at 15:36

#'equal compare true compared to (list 7 1) but false when compared to '(7 1), why?

2 Answers2