3

I want to understand the implications of append's property that "All arguments except the last one are copied, so none of the arguments is altered." (from the Elisp manual)

Say I have a list mylist (the order of its elements is irrelevant),

(setq mylist '(a b))

First, I want to add a couple of elements to it. Using append I can do

(setq mylist
      (append mylist '(c d)))

or

(setq mylist
      (append '(c d) mylist))

If I understand right, the resulting list is

mylist
|
|     --- ---      --- ---      --- ---      --- ---
 --> |   |   |--> |   |   |--> |   |   |--> |   |   |--> nil
      --- ---      --- ---      --- ---      --- ---
       |            |            |            |
       |            |            |            |
        --> a        --> b        --> c        --> d

in the first case and

mylist
|
|     --- ---      --- ---      --- ---      --- ---
 --> |   |   |--> |   |   |--> |   |   |--> |   |   |--> nil
      --- ---      --- ---      --- ---      --- ---
       |            |            |            |
       |            |            |            |
        --> c        --> d        --> a        --> b

in the second case. Both settings leave nothing else in memory, right?

Second, I want to concatenate mylist and another-list (again invariant wrt to the order of its elements),

(setq another-list '(0 1))

(I'll use the first value of mylist). I can do

(setq another-list
      (append mylist another-list))

or

(setq another-list
      (append another-list mylist))

In my reasoning the first setting yields

another-list
|
|     --- ---      --- ---      --- ---      --- ---      --- ---      --- ---
 --> |   |   |--> |   |   |--> |   |   |--> |   |   |--> |   |   |--> |   |   |--> nil
      --- ---      --- ---      --- ---      --- ---      --- ---      --- ---
       |            |            |            |            |            |
       |            |            |            |            |            |
        --> a        --> b        --> c        --> d        --> 0        --> 1

while mylist still resides unaltered somewhere in memory. The second setting yields

another-list              mylist
|                           |
|     --- ---      --- ---   -> --- ---      --- ---      --- ---      --- ---
 --> |   |   |--> |   |   |--> |   |   |--> |   |   |--> |   |   |--> |   |   |--> nil
      --- ---      --- ---      --- ---      --- ---      --- ---      --- ---
       |            |            |            |            |            |
       |            |            |            |            |            |
        --> 0        --> 1        --> a        --> b        --> c        --> d

which is all the code I've used has put in memory, which is to say that compared with the first setting of another-list I've spared one copy of mylist. Is this right?

Last thing, when Emacs evaluates (append mylist '(c d)) and (append '(c d) mylist), what do they look like in memory? Can you show it with a cons cells diagram?

4

That's pretty much it, but keep in mind that there is always more going on. For example, the source code that you type in is also read into a bunch of cons cells. This is true whether you're typing at the repl, or be reading from a source file. (Reading byte-compiled code will have a somewhat different result, but with identical semantics.)

Thus, after the very first (setq mylist '(a b)), you'll have this in memory:

┌─┬─┐  ┌─┬─┐    ┌─┬─┐
│╷│╶┼─→│╷│╶┼───→│╷│/│
└┼┴─┘  └┼┴─┘    └┼┴─┘
 └→setq └→mylist │ ┌─┬─┐   ┌─┬─┐
                 └→│╷│╶┼──→│╷│/│
                   └┼┴─┘   └┼┴─┘
                    └→quote │ ┌─┬─┐  ┌─┬─┐
                            └→│╷│╶┼─→│╷│/│
mylist───────────────────────→└┼┴─┘  └┼┴─┘
                               └→a    └→b

mylist is pointing to part of the source code, rather than to a new list.

Then, after running (setq mylist (append mylist '(c d))) you'll have the above plus this:

┌─┬─┐  ┌─┬─┐    ┌─┬─┐
│╷│╶┼─→│╷│╶┼───→│╷│/│
└┼┴─┘  └┼┴─┘    └┼┴─┘
 └→setq └→mylist │ ┌─┬─┐     ┌─┬─┐    ┌─┬─┐
                 └→│╷│╶┼────→│ │╶┼───→│╷│/│
                   └┼┴─┘     └┼┴─┘    └┼┴─┘
                    └→append  └→mylist │
                                       │ ┌─┬─┐   ┌─┬─┐
                                       └→│╷│╶┼──→│╷│/│
                                         └┼┴─┘   └┼┴─┘
                                          └→quote │ ┌─┬─┐  ┌─┬─┐
        ┌─┬─┐  ┌─┬─┐                              └→│╷│╶┼─→│╷│/│
mylist─→│╷│╶┼─→│╷│╶┼───────────────────────────────→└┼┴─┘  └┼┴─┘
        └┼┴─┘  └┼┴─┘                                 └→c    └→d
         └→a    └→b

That is, mylist is now pointing to a list whose first two conses are new, but whose other conses are not.

This is why you never want to call setcar, setcdr, nconc, or any other function that modifies a value in place on any value that came directly from the reader; they will happily modify source code that you will want to run again.

12
  • 1
    Yes, specifically it's that part of the lisp interpreter which converts text into cons cells. You can invoke directly it by calling the read function, or indirectly by calling load or require, typing at a repl, M-:, etc, etc.
    – db48x
    Jan 20 at 12:57
  • 1
    @ArchStanton Everything comes from the reader, including (list 1 2). The difference is that each time (list 1 2) is evaluated, a fresh list object is created, whereas each time the constant '(1 2) is evaluated, the same list object might be returned. Passing the latter as a non-last argument to nconc would modify the same list object globally, which means your program would exhibit different (undefined) behaviour each time it is run. Constant literals are effectively part of the program source itself, and thus should be copied before being modified destructively.
    – Basil
    Jan 20 at 13:52
  • 2
    The lisp reader takes text (the lisp code that you see in your text editor) and turns it all into lisp objects (which is what actually gets evaluated). Typically the textual code is read once and the resulting objects may be eval'd repeatedly. When something is quoted -- e.g. '(1 2) -- evaluating that form returns the object that the reader established (in this case a list which had the value (1 2) at the time it was read but, like any other list, is subject to manipulation, and so may not longer have that same value at a later evaluation.
    – phils
    Jan 20 at 21:53
  • 1
    No, I made a mistake and conflated evaluation with reading. The reader does not resolve variable names, so it produces a structure with just the symbol mylist in it. The evaluator sees the symbol and looks up the value for that symbol in the environment. The evaluator doesn't change the structure produced by the reader though, so there's never a link between them.
    – db48x
    Jan 22 at 17:43
  • 1
    Also, (append '(c d) mylist) looks exactly like (append mylist '(a b)) which I already showed, but obviously the arguments are in the opposite order.
    – db48x
    Jan 22 at 17:45
4

I think it's useful to contrast how append and nconc behave in this regard.

The way nconc concatenates its arguments is by modifying the end of each argument to point to the next argument. It does so "destructively", meaning it modifies its arguments in-place, without first making a copy.

Here's an example. N.B.: instead of using quoted constant lists like '(1 2) I am using list to allocate fresh list objects that are safe to modify; see (info "(elisp) Mutability").

(setq a (list 1 2))
(setq b (list 3 4))
(setq c (nconc a b))

Here's the resulting box diagram:

a, c                        b
|                           |
|     --- ---      --- ---   -> --- ---      --- ---
 --> |   |   |--> |   |   |--> |   |   |--> |   |   |--> nil
      --- ---      --- ---      --- ---      --- ---
       |            |            |            |
       |            |            |            |
        --> 1        --> 2        --> 3        --> 4

What happened is a was traversed until its final cdr, which was modified in place to point to b. As a result, a and c are both equal and eq now, but the new a is no longer equal to the old a.

By contrast, b was the last argument to nconc and thus the final tail of the concatenated list, so it wasn't even traversed, let alone modified. In fact, the final tail doesn't even have to be a list; whatever it is is just slapped onto the end of the result as the final cdr:

(nconc (list 1 2) 3) ;; => (1 2 . 3)

The way append concatenates its arguments is practically the same, except it makes a copy before modifying any argument (it also accepts sequences that aren't lists, but that's irrelevant here). Using the same example as before, here's the resulting box diagram:

a
|
|     --- ---      --- ---
 --> |   |   |--> |   |   |--> nil
      --- ---      --- ---
       |            |
       |            |
        --> 1        --> 2

c                           b
|                           |
|     --- ---      --- ---   -> --- ---      --- ---
 --> |   |   |--> |   |   |--> |   |   |--> |   |   |--> nil
      --- ---      --- ---      --- ---      --- ---
       |            |            |            |
       |            |            |            |
        --> 1        --> 2        --> 3        --> 4

What happened is a was copied, the copy's final cdr was modified in place to point to b, and the result was assigned to c. As a result, a and b are still equal and eq to their previous selves, and a is neither equal nor eq to c.

Again, the final tail need not be a list, because it won't be traversed or copied:

(append (list 1 2) 3) ;; => (1 2 . 3)

Back to your question:

Both settings leave nothing else in memory, right?

Apart from objects that are no longer referred to and might eventually be garbage-collected, such as the original value of mylist of '(a b). See also db48x's answer.

which is to say that compared with the first setting of another-list I've spared one copy of mylist. Is this right?

Yes, as was the case with b in my example above.

Last thing, when Emacs evaluates (append mylist '(c d)) and (append '(c d) mylist), what do they look like in memory? Can you show it with a cons cells diagram?

I think db48x's answer has already covered that.

HTH.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.