Asp Forum - SICP's description of pointers

chong.franklin

2/1/2016 7:01:00 AM

This quote is from
SICP
that I think is talking about pointers/references in programming languages.

"As we have seen, pairs provide a primitive "glue" that we can use to construct compound data objects. Figure 2.2 shows a standard way to visualize a pair--in this case, the pair formed by (cons 1 2). In this representation, which is called box-and-pointer notation, each object is shown as a pointer to a box. The box for a primitive object contains a representation of the object. For example, the box for a number contains a numeral. The box for a pair is actually a double box, the left part containing (a pointer to) the car of the pair and the right part containing the cdr."

In this case the book is talking about pairs (E.G. (cons 1 2)) and how they are represented. However we can also use pairs to construct a list like this:

(cons 1 (cons 2 '()))

Though box-and-pointer-notation is just a notation and useless, I think this looks a lot like a linked list. As I understand it, a linked list is a data
structure that contains a value and a pointer to another linked list. Having said that I think cons can be constructed like a linked list. I'm confused
by:

"The box for a pair is actually a double box, the left part containing (a pointer to) the car of the pair and the right part containing the cdr."

I originally thought the pointer should be on cdr because that would be the next list if we were constructing a list through pairs.

I think this might be a different kind of pointer all together. What exactly does a pointer mean in this case? The only pointer I know is pointers used in c. Does SICP even mention anything about c pointers?

12 Answers

Piotr Chamera

2/1/2016 9:29:00 AM

W dniu 2016-02-01 o 08:01, franklin pisze:
> This quote is from SICP that I think is talking about
> pointers/references in programming languages..
>
> "As we have seen, pairs provide a primitive "glue" that we can use to
> construct compound data objects. Figure 2.2 shows a standard way to
> visualize a pair--in this case, the pair formed by (cons 1 2). In
> this representation, which is called box-and-pointer notation, each
> object is shown as a pointer to a box. The box for a primitive object
> contains a representation of the object. For example, the box for a
> number contains a numeral. The box for a pair is actually a double
> box, the left part containing (a pointer to) the car of the pair and
> the right part containing the cdr."
>
> In this case the book is talking about pairs (E.G. (cons 1 2)) and
> how they are represented. However we can also use pairs to construct
> a list like this:
>
> (cons 1 (cons 2 '()))
>
> Though box-and-pointer-notation is just a notation and useless, I
> think this looks a lot like a linked list. As I understand it, a
> linked list is a data structure that contains a value and a pointer
> to another linked list. Having said that I think cons can be
> constructed like a linked list. I'm confused by:
>
> "The box for a pair is actually a double box, the left part
> containing (a pointer to) the car of the pair and the right part
> containing the cdr."
>
> I originally thought the pointer should be on cdr because that would
> be the next list if we were constructing a list through pairs.

Cons is general data structure with two identical slots.
You can build other data structures with it, like above mentioned linked
list, but also tree, and others. For example such a tree:

(cons (cons 2 3)
(cons (cons 4 "abc")
'xyz))

or list alike structure like this (cons (cons '() 1) 2)

Both slots in cons are identical and both can hold reference to any
other object inside. Objects 1, 2, "abc", 'xyz and conses above are
probably stored elsewhere, not in cons itself ? cons only holds
references (pointers) to them.

> I think this might be a different kind of pointer all together. What
> exactly does a pointer mean in this case? The only pointer I know is
> pointers used in c. Does SICP even mention anything about c
> pointers?

cons is something like structure with two void pointers C:

struct cons {
void *car;
void *cdr;
};

You can build anything with this...

chong.franklin

2/1/2016 9:55:00 AM

On Monday, February 1, 2016 at 5:29:09 PM UTC+8, Piotr Chamera wrote:
> W dniu 2016-02-01 o 08:01, franklin pisze:
> > This quote is from SICP that I think is talking about
> > pointers/references in programming languages..
> >
> > "As we have seen, pairs provide a primitive "glue" that we can use to
> > construct compound data objects. Figure 2.2 shows a standard way to
> > visualize a pair--in this case, the pair formed by (cons 1 2). In
> > this representation, which is called box-and-pointer notation, each
> > object is shown as a pointer to a box. The box for a primitive object
> > contains a representation of the object. For example, the box for a
> > number contains a numeral. The box for a pair is actually a double
> > box, the left part containing (a pointer to) the car of the pair and
> > the right part containing the cdr."
> >
> > In this case the book is talking about pairs (E.G. (cons 1 2)) and
> > how they are represented. However we can also use pairs to construct
> > a list like this:
> >
> > (cons 1 (cons 2 '()))
> >
> > Though box-and-pointer-notation is just a notation and useless, I
> > think this looks a lot like a linked list. As I understand it, a
> > linked list is a data structure that contains a value and a pointer
> > to another linked list. Having said that I think cons can be
> > constructed like a linked list. I'm confused by:
> >
> > "The box for a pair is actually a double box, the left part
> > containing (a pointer to) the car of the pair and the right part
> > containing the cdr."
> >
> > I originally thought the pointer should be on cdr because that would
> > be the next list if we were constructing a list through pairs.
>
> Cons is general data structure with two identical slots.
> You can build other data structures with it, like above mentioned linked
> list, but also tree, and others. For example such a tree:
>
> (cons (cons 2 3)
> (cons (cons 4 "abc")
> 'xyz))
>
> or list alike structure like this (cons (cons '() 1) 2)
>
> Both slots in cons are identical and both can hold reference to any
> other object inside. Objects 1, 2, "abc", 'xyz and conses above are
> probably stored elsewhere, not in cons itself - cons only holds
> references (pointers) to them.
>
> > I think this might be a different kind of pointer all together. What
> > exactly does a pointer mean in this case? The only pointer I know is
> > pointers used in c. Does SICP even mention anything about c
> > pointers?
>
> cons is something like structure with two void pointers C:
>
> struct cons {
> void *car;
> void *cdr;
> };
>
> You can build anything with this...

Thanks. This got me interested. I haven't read the whole thing, will SICP talk about pointers in later chapters?

chong.franklin

2/1/2016 10:03:00 AM

On Monday, February 1, 2016 at 5:29:09 PM UTC+8, Piotr Chamera wrote:
> W dniu 2016-02-01 o 08:01, franklin pisze:
> > This quote is from SICP that I think is talking about
> > pointers/references in programming languages..
> >
> > "As we have seen, pairs provide a primitive "glue" that we can use to
> > construct compound data objects. Figure 2.2 shows a standard way to
> > visualize a pair--in this case, the pair formed by (cons 1 2). In
> > this representation, which is called box-and-pointer notation, each
> > object is shown as a pointer to a box. The box for a primitive object
> > contains a representation of the object. For example, the box for a
> > number contains a numeral. The box for a pair is actually a double
> > box, the left part containing (a pointer to) the car of the pair and
> > the right part containing the cdr."
> >
> > In this case the book is talking about pairs (E.G. (cons 1 2)) and
> > how they are represented. However we can also use pairs to construct
> > a list like this:
> >
> > (cons 1 (cons 2 '()))
> >
> > Though box-and-pointer-notation is just a notation and useless, I
> > think this looks a lot like a linked list. As I understand it, a
> > linked list is a data structure that contains a value and a pointer
> > to another linked list. Having said that I think cons can be
> > constructed like a linked list. I'm confused by:
> >
> > "The box for a pair is actually a double box, the left part
> > containing (a pointer to) the car of the pair and the right part
> > containing the cdr."
> >
> > I originally thought the pointer should be on cdr because that would
> > be the next list if we were constructing a list through pairs.
>
> Cons is general data structure with two identical slots.
> You can build other data structures with it, like above mentioned linked
> list, but also tree, and others. For example such a tree:
>
> (cons (cons 2 3)
> (cons (cons 4 "abc")
> 'xyz))
>
> or list alike structure like this (cons (cons '() 1) 2)
>
> Both slots in cons are identical and both can hold reference to any
> other object inside. Objects 1, 2, "abc", 'xyz and conses above are
> probably stored elsewhere, not in cons itself - cons only holds
> references (pointers) to them.
>
> > I think this might be a different kind of pointer all together. What
> > exactly does a pointer mean in this case? The only pointer I know is
> > pointers used in c. Does SICP even mention anything about c
> > pointers?
>
> cons is something like structure with two void pointers C:
>
> struct cons {
> void *car;
> void *cdr;
> };
>
> You can build anything with this...

Thanks. I got interested in pointers. I haven't read the whole thing. will SICP talk about pointers or the concept of indirection in later chapters?

Jussi Piitulainen

2/1/2016 10:08:00 AM

franklin writes:

> On Monday, February 1, 2016 at 5:29:09 PM UTC+8, Piotr Chamera wrote:
>> W dniu 2016-02-01 o 08:01, franklin pisze:
>> > This quote is from SICP that I think is talking about
>> > pointers/references in programming languages..
>> >
>> > "As we have seen, pairs provide a primitive "glue" that we can use to
>> > construct compound data objects. Figure 2.2 shows a standard way to
>> > visualize a pair--in this case, the pair formed by (cons 1 2). In
>> > this representation, which is called box-and-pointer notation, each
>> > object is shown as a pointer to a box. The box for a primitive object
>> > contains a representation of the object. For example, the box for a
>> > number contains a numeral. The box for a pair is actually a double
>> > box, the left part containing (a pointer to) the car of the pair and
>> > the right part containing the cdr."
>> >
>> > In this case the book is talking about pairs (E.G. (cons 1 2)) and
>> > how they are represented. However we can also use pairs to construct
>> > a list like this:
>> >
>> > (cons 1 (cons 2 '()))
>> >
>> > Though box-and-pointer-notation is just a notation and useless, I
>> > think this looks a lot like a linked list. As I understand it, a
>> > linked list is a data structure that contains a value and a pointer
>> > to another linked list. Having said that I think cons can be
>> > constructed like a linked list. I'm confused by:
>> >
>> > "The box for a pair is actually a double box, the left part
>> > containing (a pointer to) the car of the pair and the right part
>> > containing the cdr."
>> >
>> > I originally thought the pointer should be on cdr because that would
>> > be the next list if we were constructing a list through pairs.
>>
>> Cons is general data structure with two identical slots.
>> You can build other data structures with it, like above mentioned linked
>> list, but also tree, and others. For example such a tree:
>>
>> (cons (cons 2 3)
>> (cons (cons 4 "abc")
>> 'xyz))
>>
>> or list alike structure like this (cons (cons '() 1) 2)
>>
>> Both slots in cons are identical and both can hold reference to any
>> other object inside. Objects 1, 2, "abc", 'xyz and conses above are
>> probably stored elsewhere, not in cons itself - cons only holds
>> references (pointers) to them.
>>
>> > I think this might be a different kind of pointer all together. What
>> > exactly does a pointer mean in this case? The only pointer I know is
>> > pointers used in c. Does SICP even mention anything about c
>> > pointers?
>>
>> cons is something like structure with two void pointers C:
>>
>> struct cons {
>> void *car;
>> void *cdr;
>> };
>>
>> You can build anything with this...
>
> Thanks. This got me interested. I haven't read the whole thing, will
> SICP talk about pointers in later chapters?

Yes.

chong.franklin

2/1/2016 10:17:00 AM

On Monday, February 1, 2016 at 6:08:08 PM UTC+8, Jussi Piitulainen wrote:
> franklin writes:
>
> > On Monday, February 1, 2016 at 5:29:09 PM UTC+8, Piotr Chamera wrote:
> >> W dniu 2016-02-01 o 08:01, franklin pisze:
> >> > This quote is from SICP that I think is talking about
> >> > pointers/references in programming languages..
> >> >
> >> > "As we have seen, pairs provide a primitive "glue" that we can use to
> >> > construct compound data objects. Figure 2.2 shows a standard way to
> >> > visualize a pair--in this case, the pair formed by (cons 1 2). In
> >> > this representation, which is called box-and-pointer notation, each
> >> > object is shown as a pointer to a box. The box for a primitive object
> >> > contains a representation of the object. For example, the box for a
> >> > number contains a numeral. The box for a pair is actually a double
> >> > box, the left part containing (a pointer to) the car of the pair and
> >> > the right part containing the cdr."
> >> >
> >> > In this case the book is talking about pairs (E.G. (cons 1 2)) and
> >> > how they are represented. However we can also use pairs to construct
> >> > a list like this:
> >> >
> >> > (cons 1 (cons 2 '()))
> >> >
> >> > Though box-and-pointer-notation is just a notation and useless, I
> >> > think this looks a lot like a linked list. As I understand it, a
> >> > linked list is a data structure that contains a value and a pointer
> >> > to another linked list. Having said that I think cons can be
> >> > constructed like a linked list. I'm confused by:
> >> >
> >> > "The box for a pair is actually a double box, the left part
> >> > containing (a pointer to) the car of the pair and the right part
> >> > containing the cdr."
> >> >
> >> > I originally thought the pointer should be on cdr because that would
> >> > be the next list if we were constructing a list through pairs.
> >>
> >> Cons is general data structure with two identical slots.
> >> You can build other data structures with it, like above mentioned linked
> >> list, but also tree, and others. For example such a tree:
> >>
> >> (cons (cons 2 3)
> >> (cons (cons 4 "abc")
> >> 'xyz))
> >>
> >> or list alike structure like this (cons (cons '() 1) 2)
> >>
> >> Both slots in cons are identical and both can hold reference to any
> >> other object inside. Objects 1, 2, "abc", 'xyz and conses above are
> >> probably stored elsewhere, not in cons itself - cons only holds
> >> references (pointers) to them.
> >>
> >> > I think this might be a different kind of pointer all together. What
> >> > exactly does a pointer mean in this case? The only pointer I know is
> >> > pointers used in c. Does SICP even mention anything about c
> >> > pointers?
> >>
> >> cons is something like structure with two void pointers C:
> >>
> >> struct cons {
> >> void *car;
> >> void *cdr;
> >> };
> >>
> >> You can build anything with this...
> >
> > Thanks. This got me interested. I haven't read the whole thing, will
> > SICP talk about pointers in later chapters?
>
> Yes.

Cool! What section?

Piotr Chamera

2/1/2016 10:18:00 AM

W dniu 2016-02-01 o 10:54, franklin pisze:
> I haven't read the whole thing, will SICP talk about pointers in
> later chapters?

Maybe chapter 3.3 will be interesting.
But I recommed studying whole book ? it is eye-opening lecture.

chong.franklin

2/1/2016 10:22:00 AM

On Monday, February 1, 2016 at 6:18:34 PM UTC+8, Piotr Chamera wrote:
> W dniu 2016-02-01 o 10:54, franklin pisze:
> > I haven't read the whole thing, will SICP talk about pointers in
> > later chapters?
>
> Maybe chapter 3.3 will be interesting.
> But I recommed studying whole book - it is eye-opening lecture.

Yes, I certainly will read the whole book. But you say chapter 3.3 is about pointers?

chong.franklin

2/1/2016 10:23:00 AM

Norbert_Paul

2/1/2016 10:24:00 AM

Piotr Chamera wrote:
> W dniu 2016-02-01 o 08:01, franklin pisze:
>> I think this might be a different kind of pointer all together. What
>> exactly does a pointer mean in this case? The only pointer I know is
>> pointers used in c. Does SICP even mention anything about c
>> pointers?
>
> cons is something like structure with two void pointers C:
>
> struct cons {
> void *car;
> void *cdr;
> };
>
> You can build anything with this...

Yes, but note that this is only one possibility.
For example muLISP87 made something like

UINT16 cars[maximal_number_of_conses]; // offsets to DS register
UINT16 cdrs[maximal_number_of_conses]; // offsets to ES register

such that

(car_aux x) and (cdr_aux x)

, which are merely CAR and CDR without any error checking, could be written
for muLISP87 in assembly like

car_aux: mov si,[bp] ; argument 1 is passed in bp
mov di,ds:[si] ; return value in di
ret

cdr_aux: mov si,[bp]
mov di,es:[si]
ret

or, in C,:

UINT16 car_aux(UINT16 x) { return cars[x]; }
UINT16 cdr_aux(UINT16 x) { return cdrs[x]; }

The word "pointer" in SICP and the boxes are only illustrative.
You should also google "cdr-coding" to get a feeling for the difference
between the illustrative "two pointers" concept and the alternative
implementations of a cons, which are permitted by its specification.

Norbert

chong.franklin

2/1/2016 10:31:00 AM

On Monday, February 1, 2016 at 6:23:47 PM UTC+8, Norbert_Paul wrote:
> Piotr Chamera wrote:
> > W dniu 2016-02-01 o 08:01, franklin pisze:
> >> I think this might be a different kind of pointer all together. What
> >> exactly does a pointer mean in this case? The only pointer I know is
> >> pointers used in c. Does SICP even mention anything about c
> >> pointers?
> >
> > cons is something like structure with two void pointers C:
> >
> > struct cons {
> > void *car;
> > void *cdr;
> > };
> >
> > You can build anything with this...
>
> Yes, but note that this is only one possibility.
> For example muLISP87 made something like
>
> UINT16 cars[maximal_number_of_conses]; // offsets to DS register
> UINT16 cdrs[maximal_number_of_conses]; // offsets to ES register
>
> such that
>
> (car_aux x) and (cdr_aux x)
>
> , which are merely CAR and CDR without any error checking, could be written
> for muLISP87 in assembly like
>
> car_aux: mov si,[bp] ; argument 1 is passed in bp
> mov di,ds:[si] ; return value in di
> ret
>
> cdr_aux: mov si,[bp]
> mov di,es:[si]
> ret
>
> or, in C,:
>
> UINT16 car_aux(UINT16 x) { return cars[x]; }
> UINT16 cdr_aux(UINT16 x) { return cdrs[x]; }
>
> The word "pointer" in SICP and the boxes are only illustrative.
> You should also google "cdr-coding" to get a feeling for the difference
> between the illustrative "two pointers" concept and the alternative
> implementations of a cons, which are permitted by its specification.
>
> Norbert

I see. What about in chapter 3, will there be about c pointers?

comp.lang.lisp

SICP's description of pointers

chong.franklin

Piotr Chamera

chong.franklin

chong.franklin

Jussi Piitulainen

chong.franklin

Piotr Chamera

chong.franklin

chong.franklin

Norbert_Paul

chong.franklin

x Login to ForumsZone