In a fit of frustration I turn to this group for aid.
Please note this is a HOMEWORK question, as such I please do not
directly address the problem. That would be cheating and I don't want
that.
However feel free to address the concepts of the problem. Thats why I'm
posting.
The problem relates to Cons Cell representation of a list ((A B)(A B)).
My prof argues that there are 3 possible Cons Cell representations of
this list. I disagree. He wants us to show the code as to how to create
the list so let me explain my view.
First, I can only think of one Cons Cell rep. for (A B), that of
[ | ] ----> [ | nil ]
| |
A B
The complete list naturally follows with two Cons Cells whose CAR points
to the above representation.
Any sort of creation I can think of leads to this list.
(setq x (cons 'a '(b)))
(list x x)
Even using Append which duplicates the first argument should result in
the same Cons Cell structure...
If someone has some idea that can help me in this quest for the correct
answer I would appreciate it. Again, no answers to the problem. Thats my
job.
My newsfeed is slow and clunky, please CC all replies to my address
(Remove the 'nospamplease')
Edward
In article <·················@nospamplease.uleth.ca>,
pollej <······@nospamplease.uleth.ca> wrote:
>In a fit of frustration I turn to this group for aid.
>
>Please note this is a HOMEWORK question, as such I please do not
>directly address the problem. That would be cheating and I don't want
>that.
Thank you! If all people who posted homework problems followed your lead,
we would have no problem.
>However feel free to address the concepts of the problem. Thats why I'm
>posting.
>
>The problem relates to Cons Cell representation of a list ((A B)(A B)).
>My prof argues that there are 3 possible Cons Cell representations of
>this list. I disagree. He wants us to show the code as to how to create
>the list so let me explain my view.
>
>First, I can only think of one Cons Cell rep. for (A B), that of
>
>[ | ] ----> [ | nil ]
> | |
> A B
Pleas refrain from using TAB or variable-space fonts in your postings.
Your diagram doesn't line up properly on my screen. But I think I know
what you meant.
>The complete list naturally follows with two Cons Cells whose CAR points
>to the above representation.
>
>Any sort of creation I can think of leads to this list.
>(setq x (cons 'a '(b)))
>(list x x)
>
>Even using Append which duplicates the first argument should result in
>the same Cons Cell structure...
>
>If someone has some idea that can help me in this quest for the correct
>answer I would appreciate it. Again, no answers to the problem. Thats my
>job.
I find it difficult to give hints on this without actually giving out the
answers, but I'll try.
In your case you're sharing the same second-level list. But what would
happen if you just shared part of that list, or if you created a new list
of A and B? Since the printed representation doesn't tell you how much
sharing is going on (unless you turn on *PRINT-CIRCLE*) these are possible
ways to produce a list structure that prints as ((A B) (A B)). In fact,
take a look at the structure that's created if you actually type in
(setq y '((a b)(a b)))
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
In article <···················@burlma1-snr2>,
Barry Margolin <······@bbnplanet.com> wrote:
(...)
> In your case you're sharing the same second-level list.
(...)
Couldn't help noting how the concept of sameness pops up even in
such innocent-looking problems in an (apparently) introductory
Lisp course.
From the point of view of an observer with restricted
capabilities, i.e. armed only with EQUAL, there is but one
cons cell representation that produces ((A B) (A B)) as
printed representation. Observers that also have EQL at
their disposal, however, are able to distinguish between the
three different cases on encountering them.
Note that if the three cases are L1, L2, L3, I _don't_ mean
that the observer would just do (EQUAL Li Lj) or (EQL Li Lj).
(Assuming a setting where the observer is given a number of
lists that all print the same and the question is, `How many
different cons cell representations are there?')
Also note that from the point of view of a `microscope-enabled'
observer who has access to the bit strings stored in the cons
cells there are many many more than 3 representations because
cons cells at different machine addresses would be
distinguishable.
So this is a problem with non-trivial instructive value.
Once I gave some students two problems: write COUNT-CONSES, which
would return the `straightforward' cons count for a list, and
COUNT-ACTUAL-CONSES, which would not count identical conses twice.
The latter turned out to be rather more difficult than the former,
more than I expected. (This was a Lisp-only 1-semester course,
elective, only for the few students who were supposed to be really
interested.)
Good luck,
Vassil.
P.S. It is a Good Thing when homework-related questions are
announced as such and posted in this way.
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
From: Tim Bradshaw
Subject: Re: Cons Cell Representation---`sameness' again
Date:
Message-ID: <nkj3e2eja4s.fsf@tfeb.org>
Vassil Nikolov <········@poboxes.com> writes:
> Also note that from the point of view of a `microscope-enabled'
> observer who has access to the bit strings stored in the cons
> cells there are many many more than 3 representations because
> cons cells at different machine addresses would be
> distinguishable.
But that observer is really working outside Lisp, because those
notions of identity are not preserved from moment to moment (the GC
may move things). It's a bit like quantum mechanics where you end up
with an exploded brain if you start asking too closely whether two
electrons are different, or indeed if there actually *is* more than
one electron (it has been suggested there isn't).
--tim
In article <···············@tfeb.org>,
Tim Bradshaw <···@tfeb.org> wrote:
> Vassil Nikolov <········@poboxes.com> writes:
>
> > Also note that from the point of view of a `microscope-enabled'
> > observer who has access to the bit strings stored in the cons
> > cells there are many many more than 3 representations because
> > cons cells at different machine addresses would be
> > distinguishable.
>
> But that observer is really working outside Lisp,
Oh, yes, but I wanted to show that there is another world outside
the Lisp world, confusing though this may be...
<uselessly-philosophical-assignments-for-readers-with-free-time>
(1) The garbage collector does see the bit strings. Is it working
outside the Lisp world? If yes, why? If no, why not?
(2) Is a (fairly hypothetical) Lisp programmer examining a core dump
from a Lisp program working outside the Lisp world?
(I reckon with all those homework writers seeking help in
comp.lang.lisp I shouldn't be flamed too much for giving out
assignments here...)
</uselessly-...>
> because those
> notions of identity are not preserved from moment to moment (the GC
> may move things). It's a bit like quantum mechanics where you end up
> with an exploded brain if you start asking too closely whether two
> electrons are different, or indeed if there actually *is* more than
> one electron (it has been suggested there isn't).
If you ask me, there is not even one [1, 2].
[1] Poe, E. A. `A Dream within a Dream.'
[2] Carroll, L. _Through the Looking-Glass_, Ch. 4.
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
In article <············@nnrp1.dejanews.com>,
Vassil Nikolov <········@poboxes.com> wrote:
>In article <···················@burlma1-snr2>,
> Barry Margolin <······@bbnplanet.com> wrote:
>(...)
>> In your case you're sharing the same second-level list.
>(...)
>
>Couldn't help noting how the concept of sameness pops up even in
>such innocent-looking problems in an (apparently) introductory
>Lisp course.
>
>From the point of view of an observer with restricted
>capabilities, i.e. armed only with EQUAL, there is but one
>cons cell representation that produces ((A B) (A B)) as
>printed representation. Observers that also have EQL at
>their disposal, however, are able to distinguish between the
>three different cases on encountering them.
Since the original posting had a box-and-pointers diagram, it seemed clear
to me that object identity was an important factor in the problem.
>Note that if the three cases are L1, L2, L3, I _don't_ mean
>that the observer would just do (EQUAL Li Lj) or (EQL Li Lj).
>(Assuming a setting where the observer is given a number of
>lists that all print the same and the question is, `How many
>different cons cell representations are there?')
>
>Also note that from the point of view of a `microscope-enabled'
>observer who has access to the bit strings stored in the cons
>cells there are many many more than 3 representations because
>cons cells at different machine addresses would be
>distinguishable.
Again, since it was presented in the constext of a box-and-pointer diagram,
not machine language, it seemed clear that the only issue in the problem is
the relationship between the pieces of the list in the abstract, not
low-level machine issues.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
In article <···················@burlma1-snr2>,
Barry Margolin <······@bbnplanet.com> wrote:
> In article <············@nnrp1.dejanews.com>,
> Vassil Nikolov <········@poboxes.com> wrote:
(...)
> >From the point of view of an observer with restricted
> >capabilities, i.e. armed only with EQUAL,
(...)
> >Observers that also have EQL
(...)
> Since the original posting had a box-and-pointers diagram, it seemed clear
> to me that object identity was an important factor in the problem.
Yes, in the original problem, definitely.
(...)
> >Also note that from the point of view of a `microscope-enabled'
> >observer who has access to the bit strings
(...)
> Again, since it was presented in the constext of a box-and-pointer diagram,
> not machine language, it seemed clear that the only issue in the problem is
> the relationship between the pieces of the list in the abstract, not
> low-level machine issues.
Yes, in the original problem, definitely.
Perhaps I should have made it explicit that I was not trying to
redefine the problem that brought about the original posting, just
to offer more ways one could look at it and at other problems of
a similar, analogous, or related nature.
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
In article <············@nnrp1.dejanews.com> Vassil Nikolov <········@poboxes.com> writes:
Observers that also have EQL at
their disposal, however, are able to distinguish between the
three different cases on encountering them.
Also, if you are allowed to change the conses with rplaca and rplacd
(or with setf if you want to be more modern, I suppose), you can get
by without eql.
--
Pertti Kellom\"aki, Tampere Univ. of Technology, Software Systems Lab
From: Erik Naggum
Subject: Re: Cons Cell Representation---`sameness' again
Date:
Message-ID: <3132456355962317@naggum.no>
* Vassil Nikolov <········@poboxes.com>
| Also note that from the point of view of a `microscope-enabled' observer
| who has access to the bit strings stored in the cons cells there are many
| many more than 3 representations because cons cells at different machine
| addresses would be distinguishable.
in what way is EQ not microscope-enabled, and how could you get more than
three different representations of a _single_ list like this, unless you
compare a cons cell from one list's representation and a cons cell from
_another_ list's representation, but that seems a rather silly argument
and not dependent on "bit strings" at all. what did I miss?
#:Erik
In article <················@naggum.no>,
Erik Naggum <····@naggum.no> wrote:
> * Vassil Nikolov <········@poboxes.com>
> | Also note that from the point of view of a `microscope-enabled' observer
> | who has access to the bit strings stored in the cons cells there are many
> | many more than 3 representations because cons cells at different machine
> | addresses would be distinguishable.
>
> in what way is EQ not microscope-enabled, and how could you get more than
> three different representations of a _single_ list like this, unless you
> compare a cons cell from one list's representation and a cons cell from
> _another_ list's representation, but that seems a rather silly argument
> and not dependent on "bit strings" at all. what did I miss?
What I had in mind was this. From the point of view of the `EQ
observer' two different evaluations of the form (LIST '(A B) '(A B))
return indistinguishable cons cell configurations (see note 1)
while the `bit-string observer' would distuinguish them by virtue
of observing different bit strings in the memory cells (see note 2).
Of course, this isn't a rigourous definition of the capabilities
of the two observers. For example, it carries the implicit assumption
that the bit-string observer doesn't `care about' the meaning of the
bit-strings (which is a non-rigourous formulation again).
Note 1: `indistinguishable cons cell configurations' must not be
taken to mean identical cons cells, of course. This is used here
in the sense that ((A B) (A B)), ((A . #1=(B)) (A . #1#)), and
(#1=(A B) #1#) are the three cons cell configurations for the
printed representation "((A B) (A B))" (with :PRINT-CIRCLE NIL)
that are distinguishable by the EQ observer but indistinguishable
by the EQUAL observer.
Note 2: unless the first list is garbage-collected immediately
after it is examined and then the exact same memory locations are
used for the second one.
For a rigiourous definition one approach would be to define in
a formal way the classes of equivalence for these types of
observers. Do I have to do it in full?
I am not going to argue if a bit-string observer is useful or
not. For me the point of this exercise is to gain some insight
into the nature of objects, references, sharing of structure,
and underlying machine representation as well as the `points of
view' of, say, Lisp programs, the Lisp processor (e.g. when it
decides if it can coalesce two constants or not), the CPU, etc.
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
In article <················@naggum.no>, Erik Naggum <····@naggum.no> wrote:
>* Vassil Nikolov <········@poboxes.com>
>| Also note that from the point of view of a `microscope-enabled' observer
>| who has access to the bit strings stored in the cons cells there are many
>| many more than 3 representations because cons cells at different machine
>| addresses would be distinguishable.
>
> in what way is EQ not microscope-enabled, and how could you get more than
> three different representations of a _single_ list like this, unless you
> compare a cons cell from one list's representation and a cons cell from
> _another_ list's representation, but that seems a rather silly argument
> and not dependent on "bit strings" at all. what did I miss?
If the microscope operates at the machine level, addresses become apparent.
At that level, an object is not really the "same" before and after a
copying GC, because its address has changed. They're two different
machine-level objects that happen to represent the same Lisp object at
different times.
Vassil has made it clear in other posts that he was answering a different
question than what was originally posed, I suspect to encourage this
meta-level discussion about sameness.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
In article <···················@burlma1-snr2>,
Barry Margolin <······@bbnplanet.com> wrote:
(...)
> Vassil has made it clear in other posts that he was answering a different
> question than what was originally posed, I suspect to encourage this
> meta-level discussion about sameness.
Yes, indeed. I want to encourage everything that helps me---perhaps
others too---to understand better what `object-oriented' means,^1
and sameness is well-known to be a key concept in this respect.
___________________________________________________________________
^1 I know people (I don't have in mind posters in comp.lang.lisp)
who might respond, with the invention of <someone's favourite OO
language> the issue is closed...
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
From: Erik Naggum
Subject: Re: Cons Cell Representation---`sameness' again
Date:
Message-ID: <3132518309719035@naggum.no>
* Barry Margolin <······@bbnplanet.com>
| If the microscope operates at the machine level, addresses become
| apparent. At that level, an object is not really the "same" before and
| after a copying GC, because its address has changed. They're two
| different machine-level objects that happen to represent the same Lisp
| object at different times.
if you can retain a pre-GC pointer to an object past the GC, you have a
reportable GC bug or a violation of the sanity of the system. I'm not
sure this helps anyone understand anything at all. so, I still think I'm
missing something, or that this is just a waste of time.
| Vassil has made it clear in other posts that he was answering a different
| question than what was originally posed, I suspect to encourage this
| meta-level discussion about sameness.
we might as well discuss sameness of objects before and after a page of
virtual memory has been paged out and then in again at different physical
machine addresses. again, I'm not sure there is enlightenment to be
found anywhere along this path.
#:Erik
In article <················@naggum.no>, Erik Naggum <····@naggum.no> wrote:
> if you can retain a pre-GC pointer to an object past the GC, you have a
> reportable GC bug or a violation of the sanity of the system. I'm not
> sure this helps anyone understand anything at all. so, I still think I'm
> missing something, or that this is just a waste of time.
You've never heard of a machine-level debugger? Get yourself a Lisp
Machine and type (si:ddt). I also recall low-level functions that would
return the address that a locative refers to, as an integer.
Or if you have a foreign function interface, the foreign language may be
able to convert the address of a Lisp object that you pass to an integer,
and return that integer.
This is what was meant by a machine-level microscope. It's operating below
the level of the Lisp language, looking at the hardware representations.
I agree that this is not really a very useful level to mention in this
thread.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Erik Naggum
Subject: Re: Cons Cell Representation---`sameness' again
Date:
Message-ID: <3132551629497789@naggum.no>
* Barry Margolin <······@bbnplanet.com>
| You've never heard of a machine-level debugger? Get yourself a Lisp
| Machine and type (si:ddt). I also recall low-level functions that would
| return the address that a locative refers to, as an integer.
yes, of course I have heard of them, I just find it wholly irrelevant to
a discussion of object sameness, which I tried really hard to show with
the virtual memory page example, which goes below visible machine address
to physical machine address.
| Or if you have a foreign function interface, the foreign language may be
| able to convert the address of a Lisp object that you pass to an integer,
| and return that integer.
yep, that's the violation of the sanity of the system.
| This is what was meant by a machine-level microscope. It's operating
| below the level of the Lisp language, looking at the hardware
| representations.
but, but, this microscope has memory and shows you what was before in a
way that is entirely artificial. I mean, copying GC is just like paging
the same data in at a different physical memory location.
in effect, this "argument" drops an important context: instead of saying
"the bit strings" it should say "the bit strings at time T1" and "the bit
strings at time T2". but that would make the silliness explicit...
| I agree that this is not really a very useful level to mention in this
| thread.
whew! :)
#:Erik
In article <················@naggum.no>, Erik Naggum <····@naggum.no> wrote:
> but, but, this microscope has memory and shows you what was before in a
> way that is entirely artificial. I mean, copying GC is just like paging
> the same data in at a different physical memory location.
I think the memory belongs to the operator of the microscope.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
pollej <······@nospamplease.uleth.ca> writes:
[...]
> The problem relates to Cons Cell representation of a list ((A B)(A B)).
> My prof argues that there are 3 possible Cons Cell representations of
> this list. I disagree. He wants us to show the code as to how to create
> the list so let me explain my view.
[...]
The trick here is to remember that, while the symbols in the above lists
are shared -- because all symbols are interned, the boxes that connect them
may or may not be shared -- because they're allocated from the heap.
pollej <······@nospamplease.uleth.ca> writes:
>
> In a fit of frustration I turn to this group for aid.
>
> The problem relates to Cons Cell representation of a list ((A B)(A B)).
> My prof argues that there are 3 possible Cons Cell representations of
> this list. I disagree. He wants us to show the code as to how to create
> the list so let me explain my view.
OK, the first two were not too hard, but the third took me a couple of
minutes of thought, although it is of the same variety as the problem in
general.
> First, I can only think of one Cons Cell rep. for (A B), that of
>
> [ | ] ----> [ | nil ]
> | |
> A B
OK.
> The complete list naturally follows with two Cons Cells whose CAR points
> to the above representation.
This step is not quite true.
> Any sort of creation I can think of leads to this list.
> (setq x (cons 'a '(b)))
> (list x x)
OK.
> Even using Append which duplicates the first argument should result in
> the same Cons Cell structure...
Why? This is the crux of the argument, and the point of your
instructor's exercise. Thinking about duplication versus non
duplication of the argument is the key to the solution.
>
> Edward
>
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
As an additional hint: What is the minimum and maximum number of cons
cells to represent ((A B) (A B)) ?
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu