python list handling and Lisp list handling

[Mark Tarver]

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.'

(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]

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.'

(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.

They are usually implemented as resizable arrays. In CPython great care
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

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]

Forgot to add: you might look athttp://norvig.com/python-lisp.html



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.

 

[Mark Tarver]

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.

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

 

[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.'

(fromhttp://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.

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]

This page says that Python lists are often flexible arrays

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- Hide quoted text -

- 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]

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]

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]

"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]

I think he meant to restrict the equivalence to
immutable conses.

 

[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.'
(fromhttp://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.

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- Hide quoted text -

- 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?

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

 

[james]

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;

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

 

[Dave Angel]

<div class="moz-text-flowed" style="font-family: -moz-fixed">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;

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

</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.

 

[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,

 

[namekuseijin]

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.