python list handling and Lisp list handling
Mark Tarver
http://www.brpreiss.com/books/opus7/html/page82.html
but also says that their representation is implementation dependent.
As far as I see this should mean that element access in Python should
run in constant time. Now if so this is a boon, because generally
'A list is a sequence of elements, but it is not a single primitive
object; it is made of cons cells, one cell per element. Finding the
nth element requires looking through n cons cells, so elements farther
from the beginning of the list take longer to access. But it is
possible to add elements to the list, or remove elements.'
(from http://www.chemie.fu-berlin.de/chemnet/use/info/elisp/elisp_7.html)
But are Python lists also indistinguishable from conventional
Lisplists for list processing. For example, can I modify a Python
list non-destructively? Are they equivalent to Lisp lists. Can CAR
and CDR in Lisp be thought of as
def car (x):
return x[0]
def cdr (x):
return x[1:]
The idea of a list in which elements can be accessed in constant time
is novel to me.
Mark
MRAB
has been taken to make appending average to constant time; however,
inserting requires the later elements to be shifted up.
In the way they are normally used they are fast.
There are also queues and deques for when you want efficient queue or
deque behaviour.
Paul Rubin
> But are Python lists also indistinguishable from conventional
> Lisplists for list processing. For example, can I modify a Python
> list non-destructively? Are they equivalent to Lisp lists. Can CAR
> and CDR in Lisp be thought of as
Python lists are vectors that automatically resize. You can append to
the end in amortized constant time in the obvious way (i.e. the
implementation allocates some extra space for expansion, and copies to
an even bigger area if you run out of expansion room). You can insert
and delete in the middle in linear time. This isn't as bad as it
sounds because the Python interpreter is pretty slow, but the list
insertion/deletion primitives are in C and are fast.
Paul Rubin
> But are Python lists also indistinguishable from conventional
> Lisplists for list processing.
Forgot to add: you might look at http://norvig.com/python-lisp.html
Mark Tarver <dr.mt...@ukonline.co.uk> writes:
> But are Python lists also indistinguishable from conventional
> Lisplists for list processing.
They are very different. There is nothing like cons or nconc.
You can't convert two lists to a single longer list with nconc,
etc.
Mark Tarver
> Mark Tarver <dr.mtar...@ukonline.co.uk> writes:
> > But are Python lists also indistinguishable from conventional
> > Lisplists for list processing.
>
> Forgot to add: you might look athttp://norvig.com/python-lisp.html
>
> > But are Python lists also indistinguishable from conventional
> > Lisplists for list processing.
>
> They are very different. There is nothing like cons or nconc.
> You can't convert two lists to a single longer list with nconc,
> etc.
Ah; so this
def cons (x,y):
return [x] + y
is not accurate?
Mark
Arnaud Delobelle
> Ah; so this
>
> def cons (x,y):
> return [x] + y
>
> is not accurate?
Depends what you mean by accurate!
in lisp, if you do:
(setq a '(1 2))
(setq b (cons 0 a))
(rplaca a 3)
Then
a is now (3 2)
b is now (0 3 2)
In Python, if you do:
a = [1, 2]
b = cons(0, a) # with your definition of cons
a[0] = 3
Then
a is now [3, 2]
b is now [0, 1, 2]
So in this respect, it is not accurate. But that's because Python lists
are vectors not conses.
--
Arnaud
Mark Tarver
Thanks for that.
OK; I think I get it. RPLACA and RPLACD are part of the id of Common
Lisp which I rarely contemplate. However what it seems to be is that
the difference is this. Lisp operates a destructive operation like
RPLACA in such a way that RPLACA on a global G not only changes G, but
all globals that reference G. Python on the other hand has a
destructive operation a[0] = .... which acts a bit like RPLACA but
whose change is local to the global changed. I take it that this is
because Python essentially copies the list, creating a brand new
vector rather than playing with pointers. Is that more or less it?
Which brings me to my next question. Assuming that we ban the use of
destructive operations like a[0] = ... Lisp's RPLACA and all the
rest. Assuming the following Python encodings, and ignoring questions
of performance, would Python and Lisp lists then be observationally
indistinguishable? i.e. would these then be fair encodings?
def car (x):
return x[0]
def cdr (x):
return x[1:]
def cons (x,y):
return [x] + y
Mark
Rhodri James
<dr.mt...@ukonline.co.uk> wrote:
> OK; I think I get it. RPLACA and RPLACD are part of the id of Common
> Lisp which I rarely contemplate. However what it seems to be is that
> the difference is this. Lisp operates a destructive operation like
> RPLACA in such a way that RPLACA on a global G not only changes G, but
> all globals that reference G. Python on the other hand has a
> destructive operation a[0] = .... which acts a bit like RPLACA but
> whose change is local to the global changed. I take it that this is
> because Python essentially copies the list, creating a brand new
> vector rather than playing with pointers. Is that more or less it?
In the specific case of list concatenation, Python copies the lists
being concatenated. For other list operations this is not necessarily
true. What is different is the concept of "all globals that
reference G". For example:
>>> a = [1, 2, 3]
>>> b = a
>>> a[0] = 0
>>> print b
[0, 2, 3]
> Which brings me to my next question. Assuming that we ban the use of
> destructive operations like a[0] = ... Lisp's RPLACA and all the
> rest. Assuming the following Python encodings, and ignoring questions
> of performance, would Python and Lisp lists then be observationally
> indistinguishable? i.e. would these then be fair encodings?
>
> def car (x):
> return x[0]
>
> def cdr (x):
> return x[1:]
>
> def cons (x,y):
> return [x] + y
I'm not sure you get a useful language by banning the destructive
operations. In particular, list slicing is another copy operation,
so you're going to run into exactly the same set of problems.
--
Rhodri James *-* Wildebeeste Herder to the Masses
Carl Banks
> This page says that Python lists are often flexible arrays
>
> http://www.brpreiss.com/books/opus7/html/page82.html
>
> but also says that their representation is implementation dependent.
> As far as I see this should mean that element access in Python should
> run in constant time. Now if so this is a boon, because generally
>
> 'A list is a sequence of elements, but it is not a single primitive
> object; it is made of cons cells, one cell per element. Finding the
> nth element requires looking through n cons cells, so elements farther
> from the beginning of the list take longer to access. But it is
> possible to add elements to the list, or remove elements.'
>
>
> But are Python lists also indistinguishable from conventional
> Lisplists for list processing. For example, can I modify a Python
> list non-destructively? Are they equivalent to Lisp lists. Can CAR
> and CDR in Lisp be thought of as
>
> def car (x):
> return x[0]
>
> def cdr (x):
> return x[1:]
>
> The idea of a list in which elements can be accessed in constant time
> is novel to me.
That's because Python lists aren't lists.
It might be an interesting exercise to compare Python lists and Lisp
lists, but you should do it under the understanding that they are not
analogous types. (A Python list is analogous to a Lisp vector.) The
two objects have almost no similarity in typical their manner of use;
even the way you iterate through them is different.
You could, as you've tried to do here, operate on Python lists the
same way you operate on Lisp lists, but you'd just be doing things the
hard way. Whatever you're trying to do with cons, car, and cdr,
chances are Python has a high-level way to do it built in that
performs a lot better.
Then again, Lispers seem to like to reimplement high-level operations
from low-level primitives every time they need it. So if you liked
doing that you might not mind doing a lot of extra work using your
homebrew cons, car, and cdr.
Carl Banks
Mark Tarver
>
> - Show quoted text -
OK; I guess the answer to the question
"Assuming the following Python encodings, and ignoring questions
of performance, would Python and Lisp lists then be observationally
indistinguishable? i.e. would these then be fair encodings?"
is a 'yes'. Any disagreement?
Mark
Mark Tarver
> reference G". For example:
>
> >>> a = [1, 2, 3]
> >>> b = a
> >>> a[0] = 0
> >>> print b
>
> [0, 2, 3]
I see that Python had an id too ;).
Mark
Michele Simionato
> OK; I guess the answer to the question
>
> "Assuming the following Python encodings, and ignoring questions
> of performance, would Python and Lisp lists then be observationally
> indistinguishable? i.e. would these then be fair encodings?"
>
> is a 'yes'. Any disagreement?
>
> Mark
No disagreement here. Since I know that you are trying
to generate Python code automatically from Qi/Lisp code,
I would like to suggest you to target Python 3.0,
which has some feature you may like. For instance,
there is a weak form of pattern matching built-in:
>>> head, *tail = [1,2,3] # Python 3.0 only!
>>> head
1
>>> tail
[2, 3]
Michele Simionato
Paul Rubin
> "Assuming the following Python encodings, and ignoring questions
> of performance, would Python and Lisp lists then be observationally
> indistinguishable? i.e. would these then be fair encodings?"
> is a 'yes'. Any disagreement?
I don't think it is equivalent:
Python 2.4.4 (#1, Oct 23 2006, 13:58:00)
[GCC 4.1.1 20061011 (Red Hat 4.1.1-30)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> a = [1,2,3]
>>> b = [4,5,6]
>>> a[1:] = b # the idea is to simulate (setf (cdr a) b)
>>> print a
[1, 4, 5, 6]
>>> b[0] = 9 # (setf (car b) 9)
>>> print a
[1, 4, 5, 6] # would expect [1,9,5,6]
Michele Simionato
I think he meant to restrict the equivalence to
immutable conses.
Carl Banks
In Python
cdr([]) == []
And I'd think that'd be an exception in Lisp depending on variants and
such. That's the only difference I can think of.
Carl Banks
ja...@biosci.utexas.edu
student project, and i have a couple of questions.
1) how can i suspend program execution for brief periods either in
python or through IDLE;
and 2) is there a way to save state data so that if i have to quit
running a program in a student computer lab, i can write the state of
the program and all intermediate data to -- say -- a usb drive, then
read in the state data later so the program can pick up where it left
off?
thanks,
james
Chris Rebert
> hi! i'm running computationally-intensive python programs for a student
> project, and i have a couple of questions.
>
> 1) how can i suspend program execution for brief periods either in python or
> through IDLE;
Ctrl+Z on Unix shells will stop program execution and return you to
the shell. The command `fg 1` will resume execution.
>
> and 2) is there a way to save state data so that if i have to quit running a
> program in a student computer lab, i can write the state of the program and
> all intermediate data to -- say -- a usb drive, then read in the state data
> later so the program can pick up where it left off?
http://docs.python.org/library/pickle.html
Cheers,
Chris
--
I have a blog:
http://blog.rebertia.com
Dave Angel
> <div class="moz-text-flowed" style="font-family: -moz-fixed">hi! i'm
> project, and i have a couple of questions.
>
> 1) how can i suspend program execution for brief periods either in
> python or through IDLE;
>
> running a program in a student computer lab, i can write the state of
> the program and all intermediate data to -- say -- a usb drive, then
> read in the state data later so the program can pick up where it left
> off?
>
> james
>
> </div>
>
1a) A program can suspend itself, with a call to sleep(). While it's
sleeping, it uses very little CPU time. Similarly, if it's waiting for
console input, or in an idle loop (for a GUI app).
1b) If the program is running from an IDE, such as Komodo, then you can
set a breakpoint, and pause it, while examining values and stack
information. I'm not familiar with IDLE, so I don't know if it has
similar abilities.
2) As far as I know, there's no standardized to preserve the entire
state of any process. However, if you write a program with this in
mind, you could preserve the state of your variables with pickle.
Preserving the state of the local variables in functions currently
executing is another story, however. I don't know of any standard way
of dumping the execution frames.
When writing a GUI program, it's sometimes necessary to break up a long
computation, so that the GUI doesn't freeze. The same techniques could
be used here.
Rhodri James
<dr.mt...@ukonline.co.uk> wrote:
> OK; I guess the answer to the question
>
> "Assuming the following Python encodings, and ignoring questions
> of performance, would Python and Lisp lists then be observationally
> indistinguishable? i.e. would these then be fair encodings?"
>
> is a 'yes'. Any disagreement?
I'm probably being rather thick, but aren't you saying here
"Assuming that the answer to this question is 'yes', is the
answer to this question 'yes'?"
Mark Wooding
> But are Python lists also indistinguishable from conventional
> Lisplists for list processing.
>
> For example, can I modify a Python list non-destructively?
No.
> Are they equivalent to Lisp lists. Can CAR and CDR in Lisp be thought
> of as
>
> def car (x):
> return x[0]
>
> def cdr (x):
> return x[1:]
Not in the presence of side-effects, no.
The slice-extration operation on lists constructs a copy of the
original, and mutating the original doesn't affect the copy. Here's a
simple example.
[Load your definitions...]
In [1]: def car (x): return x[0]
...:
In [2]: def cdr (x): return x[1:]
...:
[Python] [Common Lisp]
In [3]: a = [1, 2, 3, 4] CL-USER> (setf a (list 1 2 3 4))
(1 2 3 4)
In [4]: b = cdr(a) CL-USER> (setf b (cdr a))
(2 3 4)
In [5]: a[2] = 'banana' CL-USER> (setf (third a) "banana")
"banana"
In [6]: a CL-USER> a
Out[6]: [1, 2, 'banana', 4] (1 2 "banana" 4)
In [7]: b CL-USER> b
Out[7]: [2, 3, 4] ! (2 "banana" 4)
Also, note:
In [8]: b is cdr(a) CL-USER> (eq b (cdr a))
Out[8]: False ! T
Your Python `cdr' operation conses. Until you create it explicitly,
there is no Python value corresponding to `all but the first element of
this list'.
But, apart from the performance and sharing characteristics, they're the
same. I think those are pretty big differences, though.
-- [mdw]
Steven D'Aprano
> That's because Python lists aren't lists.
Surely you meant to say that Lisp lists aren't lists?
It-all-depends-on-how-you-define-lists-ly y'rs,
--
Steven
namekuseijin
wrote:
> which has some feature you may like. For instance,
> there is a weak form of pattern matching built-in:
>
> >>> head, *tail = [1,2,3] # Python 3.0 only!
> >>> head
> 1
> >>> tail
>
> [2, 3]
Good seeing yet another long time Perl feature finally brought in. ;)
namekuseijin
Yeah, the List Processing language got it all wrong by not going with
arrays like Python...
Steven D'Aprano
Well, Lisp was invented in 1958, before anyone knew how to program *wink*.
Seriously though, linked lists are not the only sort of list. That was my
point: first define what is a list, and then we can debate what is or
isn't a list. Even within linked lists, there are various different
types, all with their own strengths and weaknesses: singly-linked lists,
doubly-linked lists, circular lists, open lists, xor-lists, lists with or
without sentinels, lists with internal and external storage, unrolled
linked lists, and combinations of all of the above.
--
Steven
J Kenneth King
> On Sat, 25 Apr 2009 23:51:18 -0700, namekuseijin wrote:
>
>> On Apr 26, 1:31 am, Steven D'Aprano <st...@REMOVE-THIS-
>> cybersource.com.au> wrote:
>>> On Fri, 24 Apr 2009 21:01:10 -0700, Carl Banks wrote:
>>> > That's because Python lists aren't lists.
>>>
>>> Surely you meant to say that Lisp lists aren't lists?
>>>
>>> It-all-depends-on-how-you-define-lists-ly y'rs,
>>
>> Yeah, the List Processing language got it all wrong by not going with
>> arrays like Python...
>
> Well, Lisp was invented in 1958, before anyone knew how to program *wink*.
And 50+ years of development hasn't taught them anything. :p
Guess you don't know anything about programming unless you're new...
> Seriously though, linked lists are not the only sort of list. That was my
> point: first define what is a list, and then we can debate what is or
> isn't a list. Even within linked lists, there are various different
> types, all with their own strengths and weaknesses: singly-linked lists,
> doubly-linked lists, circular lists, open lists, xor-lists, lists with or
> without sentinels, lists with internal and external storage, unrolled
> linked lists, and combinations of all of the above.
And any sufficiently powerful language would allow the programmer to
adapt to any type they needed. ;)
Interesting topic though.