Chapter 7 page 111 Using setf to put extra stuff into first parameter to build circular list

[farmkitteh]

Hi,  I'm hoping someone will help me to understand the example on page 111.  Here's the code and REPL feedback:

> (defparameter foo '(1 2 3))

FOO

> (setf (cdddr foo)  foo)

#1=(1 2 3 . #1#)

I'm afraid that there is more than one thing that I don't understand.  When I look at it, I review in my mind that defparameter defines global variables.  Global variables should have earmuffs *globvar* but don't have to.  Is foo a global variable in this case?  cdddr to me means that I would look at a list and slice off the first item three times.  In other words, if I have a list like this:  (cat dog thingy fourthItem)  I would end up with fourthItem in a list once I've cdr'ed it 3 times.  If a list has only three items like foo above (i 2 3), would I end up with 3 in the final list?  Or an empty list?  I think it would be 3 in this case but I'm not sure. When there is a setf operation to reassign a variable, what would I be reassigning to what here?  

Finally, what does the notation #1=(1 2 3 . #1#) mean?  #' is shorthand for function I believe but what does the hash mean here?

Thanks in advance.  Just when I feel like I'm going along fine understanding LoL, I run in to cases loike page 51 in Chapter 4 and now this.

[farmkitteh]

Hello again,

If there's a chapter later in the book that would help me understand this example better, please let me know.  Or if there's another reference that you could point me to, I'd really appreciate it.  After I get through understanding this code, I'm on to Chapter 8 and the Wumpus.  Thanks!

[farmkitteh]

When googling for Lisp circular lists I found this:

#1=(#1#) is a cons-cell that contains itself

So now my question is:  How does the cdddr foo work in this example?  I have to lead the discussion for our book club tonight and I'm hoping to be able to explain this code snippet in detail.  the rest of the chapter I understand.  Thanks in advance for your help!

[farmkitteh]

On page 74 of David S. Touretzky's Book: "Common Lisp:  A Gentle Intrioduction to Symbolic Computation", 

(David S. Touretzsky is at Carnegie Mellon University), I found this:

2.18 CIRCULAR LISTS

Dotted lists may look a bit strange, but even stranger structures are possible.

For example, here is a circular list:

A B C

If the computer tried to display this list in printed form, one of several

things might happen, depending on the setting of certain printer parameters

that will be discussed later. The computer could go into an infinite loop.  Or it

might try to print part of the list, using ellipsis (three dots), as in:

(A B C A B C A B ...)

This way of writing the list is incorrect, because it suggests that the list

contains more than ten elements, when in fact it contains only three.

Common Lisp does provide a completely correct way to print circular

structures, using something called ‘‘sharp-equal notation,’’ based on the #

(sharp-sign) character.  Essentially, to write circular structures we need a way

to assign a label to a cons cell so we can refer back to it later.  (For example, in

the circular list above, the CDR of the third cons cell refers back to the first

cell.) We will use integers for labels, and the notation #n= to label an object.

We’ll write #n# to refer to the object later on in the expression.  The list above

is therefore written this way:

#1=(A B C . #1#)

EXERCISE

2.36. Prove by contradiction that this list cannot be constructed using just

CONS. Hint: Think about the order in which the cells are created.

An even more deviant structure is the one below, in which the CAR of a

cons cell points directly back to the cell itself.HAPTER 2 Lists 75

A

If the computer tried to print this structure, it might end up printing an infinite

series of left parentheses.  But if the printer is instructed to use sharp-equal

notation, the list would print this way:

#1=(#1# . A)

> '#1='(1 2 3 . #1#)

(1 2 3 1 2 3 1 2 3 1 ...)

So I guess this: 

> (defparameter foo '(1 2 3))

FOO

> (setf (cdddr foo)  foo)

#1=(1 2 3 . #1#)

means that the cdr of the third cons cell (3 in our case, the right cell of the cons) points back to itself.  I think I sorta get it.

Did everybody else just grok this easily?  If so, how did you know about the sharp-equal notation?

Thanks.

-The kitteh from the farm

[Munawar Cheema]

I did not grok this easily and found thus thread useful

[Mauricio]

I´m not sure if I´m arriving too late to the discussion, but reaading the original post and browsing the additional post here aof re my inputs on how you can understand the code:

1) Any time you declare a variable usising using defparameter at the top level (outside any let or defun form) you are creating a global variable, wether it has earmuffs or not. As you say earmuffs are just a convention, is like putting + signs around constant names, just makes it easy for somebody reading the code to understand what they are, but are not required.

2) CDR looks at the second field of a cons cell, CAR looks at the first, a list is made up of cons cells, so in this case using CAR will give you an atom (because is a flat not a list of lists), CDR in the other hand will give you a list, So if your list is ´(1 2 3), CAR is 1 and CDR is ´(2 3).

(CDDDR ´(1 2 3)) is equivalent to (CDR (CDR (CDR '(1 2 3)), that means the second element of the last cons cell, in this case a NIL, the last cons cell a proper list always point to nil. 

 ______      ______      ______

|   |  |    |   |  |    |   |  |

| 1 | -+--->| 2 | -+--->| 3 | -+---> NIL

|___|__|    |___|__|    |___|__|

 
Now, what the example is doing, is giving a name to this list, which really is giving a pointer (lets represent it with an arrow too) to the first cons cell, the one containing the 1.

 foo

  |

 _V____      ______      ______

|   |  |    |   |  |    |   |  |

| 1 | -+--->| 2 | -+--->| 3 | -+---> NIL

|___|__|    |___|__|    |___|__|

So whte the code says really, is get that lass arrow, and instead of pointing it to NIL, point it to where foo is pointing.

 foo------------------------------+

  |                               |

 _V____      ______      ______   |

|   |  |    |   |  |    |   |  |  |

| 1 | -+--->| 2 | -+--->| 3 | -+--+

|___|__|    |___|__|    |___|__|

Can you see the circular list there?, So now, when you ask the REPL to print foo, it will star following all those  arrows until it finds a NIL, but there is no NIL anymore, so it would have to print (1 2 3 1 2 3 1 2 3 ...  (until hell freezes over or your computer dies). But that will make the REPL stay in an infinite loop and die, so the notation #1=(1 2 3 . #1#) was invented to avoid that, and to convey the information I drew in the diagram above. With a little imaggination you can see that what it is telling you is that the list is represented by #1 and the las CDR in the last cons cell is pointing to the #1, thus faithfully representing the circular reference.

I don´t remember if Land of Lisp mentions this but the way the REPL represents a cons cell is '( a . b ), you can see this by typing something like

(cons 1 2)

in the REPL, and if you type (cons 1 nil) you will see that you get a list with just one element, so any cons cell that has the CDR pointing to NIL is represented as a list by the REPL, neat!!, so the list we created at the beggining is really (cons 1 (cons 2 (cons 3 nil))) which is a cons with it's second element (know as CDR) being another cons cell, which in turn has a CDR which is a third cons cell which finally has a CDR that point to nil, 

Hope this helps!!

[Munawar Cheema]

yes it does and thanks Mauricio