python list handling and Lisp list handling

Discussion in 'Python' started by Mark Tarver, Apr 24, 2009.

  1. Mark Tarver

    Mark Tarver Guest

    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
     
    Mark Tarver, Apr 24, 2009
    #1
    1. Advertising

  2. Mark Tarver

    MRAB Guest

    Mark Tarver wrote:
    > 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.
     
    MRAB, Apr 24, 2009
    #2
    1. Advertising

  3. Mark Tarver

    Paul Rubin Guest

    Mark Tarver <> writes:
    > 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, Apr 24, 2009
    #3
  4. Mark Tarver

    Paul Rubin Guest

    Mark Tarver <> writes:
    > 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 <> 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.
     
    Paul Rubin, Apr 24, 2009
    #4
  5. Mark Tarver

    Mark Tarver Guest

    On 24 Apr, 17:19, Paul Rubin <http://> wrote:
    > Mark Tarver <> 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
    >
    > Mark Tarver <> 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.


    Ah; so this

    def cons (x,y):
    return [x] + y

    is not accurate?

    Mark
     
    Mark Tarver, Apr 24, 2009
    #5
  6. Mark Tarver <> writes:
    > 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
     
    Arnaud Delobelle, Apr 24, 2009
    #6
  7. Mark Tarver

    Mark Tarver Guest

    On 24 Apr, 19:54, Arnaud Delobelle <> wrote:
    > Mark Tarver <> writes:
    > > 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


    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
     
    Mark Tarver, Apr 25, 2009
    #7
  8. Mark Tarver

    Carl Banks Guest

    On Apr 24, 8:19 am, Mark Tarver <> wrote:
    > 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
     
    Carl Banks, Apr 25, 2009
    #8
  9. Mark Tarver

    Mark Tarver Guest

    On 25 Apr, 05:01, Carl Banks <> wrote:
    > On Apr 24, 8:19 am, Mark Tarver <> wrote:
    >
    >
    >
    >
    >
    > > 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?

    Mark
     
    Mark Tarver, Apr 25, 2009
    #9
  10. Mark Tarver

    Mark Tarver Guest

    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
     
    Mark Tarver, Apr 25, 2009
    #10
  11. On Apr 25, 9:07 am, Mark Tarver <> 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?
    >
    > 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
     
    Michele Simionato, Apr 25, 2009
    #11
  12. Mark Tarver

    Paul Rubin Guest

    Mark Tarver <> writes:
    > "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]
     
    Paul Rubin, Apr 25, 2009
    #12
  13. On Apr 25, 10:01 am, Paul Rubin <http://> wrote:
    > Mark Tarver <> writes:
    > > "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.
     
    Michele Simionato, Apr 25, 2009
    #13
  14. Mark Tarver

    Carl Banks Guest

    On Apr 25, 12:07 am, Mark Tarver <> wrote:
    > On 25 Apr, 05:01, Carl Banks <> wrote:
    >
    >
    >
    > > On Apr 24, 8:19 am, Mark Tarver <> wrote:

    >
    > > > 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
     
    Carl Banks, Apr 25, 2009
    #14
  15. Mark Tarver

    Guest

    how to suspend program and save state data in python or IDLE?

    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
     
    , Apr 25, 2009
    #15
  16. Mark Tarver

    Chris Rebert Guest

    Re: how to suspend program and save state data in python or IDLE?

    On Sat, Apr 25, 2009 at 3:18 PM, <> wrote:
    > 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
     
    Chris Rebert, Apr 25, 2009
    #16
  17. Mark Tarver

    Dave Angel Guest

    Re: how to suspend program and save state data in python or IDLE?

    wrote:
    > <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.
     
    Dave Angel, Apr 26, 2009
    #17
  18. Mark Tarver

    Mark Wooding Guest

    Mark Tarver <> writes:

    > 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]
     
    Mark Wooding, Apr 26, 2009
    #18
  19. 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,


    --
    Steven
     
    Steven D'Aprano, Apr 26, 2009
    #19
  20. Mark Tarver

    namekuseijin Guest

    On Apr 25, 4:34 am, Michele Simionato <>
    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, Apr 26, 2009
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ekzept
    Replies:
    0
    Views:
    386
    ekzept
    Aug 10, 2007
  2. nanothermite911fbibustards
    Replies:
    0
    Views:
    388
    nanothermite911fbibustards
    Jun 16, 2010
  3. nanothermite911fbibustards
    Replies:
    0
    Views:
    328
    nanothermite911fbibustards
    Jun 16, 2010
  4. Xah Lee
    Replies:
    10
    Views:
    367
    Xah Lee
    Mar 2, 2012
  5. Xah Lee
    Replies:
    5
    Views:
    772
Loading...

Share This Page