why the change is in place for the list with elisp?

Question

I have a question about elisp. For example:

(setq trees '(maple oak pine birch))
      -> (maple oak pine birch)
(setcdr (nthcdr 2 trees) nil)
      -> nil
trees
      -> (maple oak pine)

I thought (nthcdr 2 trees) returns a new list - (pine birch) and put the list into the setcdr expression, which should not change the value of trees. Could anyone explain it to me?

score 4 · Accepted Answer · edited May 23 '17 at 10:32

4

If you read the documentation string for nthcdr, you'll see that it just returns a pointer to the "nth" "cdr" - which is a pointer into the original list. So you're modifying the original list.

Doc string:

Take cdr N times on LIST, return the result.

Edit Wow, "pointer" seems to stir up confusion. Yes, Lisp has pointers.

Just look at the box diagrams used to explain list structure in lisp (here's Emacs's documentation on that very thing):

     --- ---      --- ---      --- ---
    |   |   |--> |   |   |--> |   |   |--> nil
     --- ---      --- ---      --- ---
      |            |            |
      |            |            |
       --> rose     --> violet   --> buttercup

Look at all those arrows, they almost look like they're .... pointing to things. When you take the cdr of a list, you get what the 2nd box refers to (aka "points" to), be it an atom, a string, or another cons cell. Heck, check it out on Wikipedia's entry for CAR and CDR.

If it feels better to call it a reference, use that terminology.

cdr certainly does NOT return a copy of what it refers to, which is what was confusing RNAer.

edited May 23 '17 at 10:32

Community

1
1

answered Feb 06 '13 at 06:35

Trey Jackson

73,529
11
197
229

Would you mind to point out the doc where it says *nthcdr* returns a *pointer* to the nth cdr? – Déjà vu Feb 06 '13 at 07:53
There is no such thing as a *pointer* in Lisp. However, `cdr` and `nthcdr` returns a *cons-cell* (which is what lists are built of), it is the *same* const cell which originally was part of the list. If you destructively modify it, that change will be reflected in the original list. – Lindydancer Feb 06 '13 at 09:46
@Lindydancer Sure, you don't have raw pointers, but saying that you return a cons cell often evokes images of a *copy* of something. And in reality, you're getting the pointer - just like the box diagrams show, it's really not that scary. – Trey Jackson Feb 06 '13 at 15:08
@ring0 What is the value of the `cdr` of a cons cell? It's a pointer (aka reference to the next element in the list). Look at the box diagrams, that's exactly what is drawn. – Trey Jackson Feb 06 '13 at 15:11
The reason why I objected is that whenever one start talking about *pointers*, the next question is always "so, how to I take the *address of* something". Well, in lisp, you can't... – Lindydancer Feb 06 '13 at 15:23

Chris Barrett · Answer 2 · 2013-02-06T10:38:08.337

R: "Look, in the sky! The Lambda Signal! A citizen is in trouble Lambda Man!"

LM: "I see it! And I've got just the box art they need."

In Lisps, lists are singly-linked data structures, comprised of elements called cons cells. Each of these cells is a structure that consists of

a pointer to a value
a pointer to the next cell

These are called the car and cdr respectively for historical reasons. Here's the traditional box art representing a 3-element list:

Structure:    (car . cdr -)--->(car . cdr -)--->(car . cdr)
                |                |                |      |
                v                v                v      v
Values:         1                2                3     nil

The car and cdr functions allow you to work with lists from this low level of abstraction, and return the values of the respective cells. Thus, car returns the 'value' of the cell, and cdr dereferences to the remainder of the list. nthcdr is a generalisation on top of cdr for convenience.

The value returned by cdr is a reference to a raw data structure, which is mutable at this level. If you change the value of a cons-cell's cdr, you are changing the underlying structure of the list.

Given:

 let A = '(1 2)    ~= (1 . -)-->(2 . nil)

 let B = '(3 4)    ~= (3 . -)-->(4 . nil)

Setting the cdr of (cdr A) to B will destructively concatenate A and B such that A is now the structure below:

 A                   B     
 (1 . -)-->(2 . -)-->(3 . -)-->(4 . nil)

As we've shown, a nil value in a cell's cdr represents the end of the list - there's nothing more that can be traversed. If we set the cdr of A to nil, we lobotomise the list, such that A is now

A                  
(1 . nil)  <- [Not pointing to anything - the rest of the list shall go wanting]

This is pretty much what you've done - you've mutated the underlying data structures using low-level functions. :) By setting one of the cell's cdrs to nil, you've trimmed the end off your list.

One rule of thumb is that functions containing `car` or `cdr` in their name are often lower-level and destructive in elisp. — Chris Barrett, Feb 06 '13 at 10:47

score 0 · Answer 3 · answered Feb 06 '13 at 10:24

0

This is called 'mutation'. And is present everywhere apart from Haskell.

There are functions that mutate the data structures and functions that duplicate it.

answered Feb 06 '13 at 10:24

alinsoar

15,386
4
57
74

why the change is in place for the list with elisp?

3 Answers3