On Mon, Feb 18, 2008 at 08:43:38PM -0800, Chuck Esterbrook wrote:
On Feb 18, 2008 8:14 PM, David Brown <[EMAIL PROTECTED]> wrote:
Another example is that Python lists can't represent circular data
structures, which Scheme/lisp lists can. In other words, you can't
implement set-cdr! without using cons cells.
Your other comments seem correct, but can you expand on this last
part? Python lists hold references and can refer to themselves:
Which is quite different than what I'm referring to.
from pprint import pprint
t = [1, 2]
t = [t, t]
pprint(t)
[[1, 2], [1, 2]]
t[0] is t[1]
True
t[1] is t
False
t[1] = t
t[1] is t
True
pprint(t)
[[1, 2], <Recursion on list with id=405832>]
Well that wasn't a minimal session to demonstrate the concept, but
nonetheless we end up with a list t that is effectively [[1, 2], t]
Which is very different than (1 2 1 2 1 2 1 2 ...). You have a two element
list, the first element is a list of two elements and the second element
points back.
The result in lisp is an infinite list, not a tree with recursion.
Lisp also allows pointers to arbitrary cons cells, meaning that various
entities can hold references to conses other than the one at the beginning
of the list. This is _very_ important to doing some lisp manipulation.
When I take the 'cdr' of a list, I have a pointer to the second element of
the list. You can't do this in Python. Chris's implementation of cdr
would probably end up constructing another list, which would be very
different behavior, especially if that list is cyclic (meaning it wouldn't
terminate).
Did you mean something else by circular or did you mean that LISP had
a more elegant way of constructing the cycle? (or something else...)
Yes, it can really construct a cycle. Your python list is not a cycle,
it's a tree with a pointer back to the top. Yes, it's cyclic, but not an
unending list. In other words, you can construct lists in python that are
infinitely deep, but not infinitely wide. Cons cells can do both.
Another way to think of it. A python list is an arbitrary-length tuple.
An element of that tuple could refer to the tuple itself, but the
individual pieces can't be referred to.
A cons cell contains just a car and and cdr. When representing a true
list, the car will be the item, and the cdr will be the next pointer.
These interiors of lists can be shared, not just the list as a whole.
Dave
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
