Two cons point to same memory when mapping over array in Common Lisp

Question

I have the following function:

(defun transform-matrix (matrix)
   (let ((res (map 'vector
                   (lambda (x)
                       (map 'vector
                            (lambda (ix)
                                (if ix
                                    '(t 0) ; --> Problem happens here
                                    0))
                            x))
                   matrix)))
    res))

This function will accept a 2d matrix, in which each element can either be t or nil. Then it will transform t -> '(t 0) and nil -> 0.

The result array has one problem is every (t 0) cons now point to the same memory location. For example if i save the result array in res variable and do this:

(eq (aref (aref res 0) 0)
    (aref (aref res 1) 1))

*Assume that res[0][0] and res[1][1] is the '(t, 0) nodes.

This will result in T. But do like this is result in nil:

(eq '(t 0) '(t 0))

Can i ask what happen with the transform-matrix that make created cons to point to the same memory location.

I test these codes on SBCL 2.0.0 Windows 64 Bit.

Thank you.

Answer 1

One way to see the problem here is to change your function to this:

(defun transform-matrix (matrix)
  (let ((non-nil-value '(t 0))
        (nil-value 0))
    (map 'vector
         (lambda (x)
           (map 'vector
                (lambda (ix)
                  (if ix non-nil-value nil-value))
                x))
         matrix)))

It should be clear that this code is functionally identical: both functions have a single occurrence of '(t 0): this one just gives it a name.

But now let's gut this function and consider this:

(defun ts ()
  (let ((non-nil-value '(t 0)))
    (eq non-nil-value non-nil-value)))

Well, certainly I would expect the result of calling this function to be t.

And that's why every element in your resulting nested vectors which isn't 0 is the same: because you only ever constructed one object.

If you want all of the objects in the returned value to be different objects (ie not to be identical), you need to construct a new object each time, for instance by:

(defun transform-matrix (matrix)
  (let ((non-nil-template '(t 0)))
    (map 'vector
         (lambda (x)
           (map 'vector
                (lambda (ix)
                  (if ix (copy-list non-nil-template) 0))
                x))
         matrix)))

This will ensure that each non-zero element of the resulting object

• is distinct;
• can safely be mutated.

Neither of these were previously true.

For the case of (eq '(t 0) '(t 0)) you might expect that this must return nil. That is (I think definitely) the case in interpreted code. But for compiled code the answer is not so clear. At least for the file compiler, it's fairly clear that in fact this may return t. Section 3.2.4.4 of the spec says, in part

If two literal objects appearing in the source code for a single file processed with the file compiler are the identical, the corresponding objects in the compiled code must also be the identical. With the exception of symbols and packages, any two literal objects in code being processed by the file compiler may be coalesced if and only if they are similar; if they are either both symbols or both packages, they may only be coalesced if and only if they are identical.

And in (eq '(t 0) '(t 0)), there are two literal lists, which are similar, and which therefore may be coalesced by the file compiler.

As a general rule, if you want a mutable object, or an object which you need to be certain is not identical to any other object, you should construct it explicitly: it is never safe (or even legal) to mutate literal objects, and the rules on which objects can be coalesced are complex enough that it is generally just safer to construct the objects so you know what is happening.

---

As an aside is there a reason you are using nested vectors rather than a two-dimensional matrix?

Answer 2

Just to add to TFB:

Lisp does not copy its arguments in a function call. It passes references to it:

(let ((a '(1 2)))          ; A is a reference to (1 2)
  (foo a)                  ; calls FOO and the same (1 2) will be 
                           ; accessible via a new reference inside FOO
  (setf (aref array 0) a)
  (setf (aref array 1) a)  ; this will make the array at 0 and 1
                           ;  reference the same list
)

If i use the quote version '(t 0) twice in the REPL i still can get two different cons.

That's because in the REPL you would need to enter '(t 0) twice and make sure that the Reader (the R in REPL) constructs new lists, which it usually does:

CL-USER > (eq (read) (read))
(0 1) (0 1)
NIL

Now the REPL reader:

CL-USER 6 > '(1 2)
(1 2)                     ; result

CL-USER 7 > '(1 2)
(1 2)

CL-USER 8 > (eq * **)     ; comparing previous results
NIL

Each call to READ conses a fresh new lists.

Side note: There are actually also more advanced REPL readers, where one can reference already existing lists, like in the REPL of the McCLIM listener.

Answer 3

Firstly, note that your transform-matrix function contains exactly one instance of the '(t 0) syntax, whereas the expression you're testing at the REPL contains two instances: (eq '(t 0) '(t 0)).

Because that expression has two instances, it is is possible that those will be different objects. In fact, the Lisp implementation would have to go out of its way to turn them into one object, and it is something that is allowed.

The (t 0) syntax is a piece of the program's source code. A program can apply the quote operator (for which the ' character is a shorthand) to a piece of its syntax to use that syntax as a literal. A given literal is one object; multiple evaluations of the same quote yield the same object.

When Lisp is naively interpreted, the interpreter recursively walks the original list-based source code. The implementation of the quote operator simply returns the piece of code that is being walked as a value.

When Lisp is compiled, the list-based source code is transformed to something else, such as native machine language for the CPU to execute directly. In the transformed image, the source code is gone. Yet, the compiler has to recognize the quote special form and translate it somehow. To do that, it has to take the piece of source code structure enclosed by quote and embed that object in the compiled image, so that it's somehow available to the compiled code: i.e. that quoted part of the source is not gone, but is propagated into the translation. For instance, the compiled image may be accompanied by a static vector dedicated for storing literals. Whenever the compiler process a quote expression like '(t 0), it allocates the next available slot in that vector, like position 47 or whatever, and stick the object (t 0) into that slot. The compiled version of '(t 0) code will then access that slot 47 in the literal data vector, and it will do that every time it is executed, retrieving the same object each time, just like the interpreted version of the program retrieveds the same piece of its own source code each time.

When compiling literals, the compiler may also search through the vector and de-duplicate it. Instead of allocating the next available index, like 47, it might scan through the literals and discover that index 13 already has a (t 0). Then it generates code to access index 13. Therefore, the compiled version of (eq '(t 0) '(t 0)) may well yield true.

Now, the way your question is framed, there is no evidence that there is an actual problem from all of the slots sharing a single instance of (t 0).

You need these objects to be different if you ever change the 0 value to something else by mutation. However, even that issue can be solved without actually making the objects different up-front. So that is to say, we can keep all the (t 0) entries objects pointing to the same object, and if we want to change some of them to, say, (t 3), we can allocate a whole new object at that time, rather that doing (set (cadr entry) 3). Moreover, maybe we can make all the (t 3) entries point to a single (t 3), like we did with (t 0).

It is impossible to say that changing '(t 0) to (list t 0) is the best approach to fix the problem, assuming there even is a problem.