Understanding Cons cell notation

[speech impediment]

Hello, I am using Touretzky's Common Lisp book to teach myself Lisp. I don't know if it is Lisp or the book, but learning Lisp isn't too hard and I am giddy. The only programming experience I have is a failed college BASIC class about 9 years ago. So I guess you can consider me as a guinea pig of an experiment for whether Lisp is a suitable first language to learn.

Anyhoo, the cons cell notation in Touretzky's book is now puzzling me after finishing 6 chapters. It is the squiggly wavy pointer for functions. I shall refer to chapter 2.9. The input to REST is pointing this way: REST --> THE BIG BOPPER. However, the result: REST --> BIG BOPPER also points in the same direction. Should not the notation for the input point the other way? Like so: REST <-- THE BIG BOPPER ??

I understand that all pointers point in one direction, so it's hard to wrap my head around input and output since Lisp works on the basis of pointers. Can anyone elaborate further about this?

[Paul Donnelly]

If we're looking at the same example, it works as follows.

"input to REST" and "Result of REST" are both pointers — that is, values which indicate some specific object. In the first diagram, "Input to REST" is pointing to the cons whose car is "THE". In the second, "Result of REST" is pointing to the cons whose car is "BIG". Think of a pointer as an address that gets passed around. If we have:

1 Memory Lane: A cons containing THE and another cons.
2 Memory Lane: A cons containing BIG and another cons.
3 Memory Lane: A cons containing BOPPER and NIL.

What actually get passed around are these addresses, and each cons (and symbol, and other object) stays where it always was. So "Input to REST" is "1 Mem. Ln.", and "Result of REST" is "2 Mem. Ln.". The zigzag arrow depicts this graphically. Rest was given the first address, it examined the cons and returned the second address. The arrows aren't showing the flow of data, rather the structure of the data at particular moments in time.

Clearer?

In languages like C, pointers are variables which hold literal memory addresses, and a programmer has to explicitly look up the data a pointer points to to get at it. In Lisp, pointers are all implicit, partly because who cares where in memory objects actually lie, and partly because attempting to use that knowledge would likely end poorly, since the garbage collector could rearrange all our objects at any time, maintaining only the structure of who points to whom.

[speech impediment]

The arrows aren't showing the flow of data, rather the structure of the data at particular moments in time.

Clearer?

Yes, that pretty much explains why I was confused. When there is talk of input and result (output), I think of flow of data and not data structure itself. Appreciate the time you spent explaining this. Thank you.