Re: python list handling and Lisp list handling
On Fri, Apr 24, 2009 at 10:19 AM, Mark Tarver dr.mtar...@ukonline.co.ukwrote: 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 When I first learned Python, I too was confused by the fact that Python lists are actually arrays (or vectors) under-the-hood, and it was some time before I learned that element access is fast (O(1)) but inserts, deletes, and taking a sublist are slow (O(n)). Much later, I went on to write a drop-in replacement type called the blist that has the same methods as a Python list, but has better asymptotic performance for many operations. That way I can write use the list in the most natural way without having to worry about accidentally hitting a O(n) method. http://pypi.python.org/pypi/blist/ -- Daniel Stutzbach, Ph.D. President, Stutzbach Enterprises, LLC http://stutzbachenterprises.com -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
On Apr 25, 4:34 am, Michele Simionato michele.simion...@gmail.com 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. ;) -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
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... -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
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*. 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
Steven D'Aprano st...@remove-this-cybersource.com.au writes: 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
On 25 Apr, 05:01, Carl Banks pavlovevide...@gmail.com wrote: On Apr 24, 8:19 am, Mark Tarver dr.mtar...@ukonline.co.uk 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
On Apr 25, 9:07 am, Mark Tarver dr.mtar...@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? 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
Mark Tarver dr.mtar...@ukonline.co.uk 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] -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
On Apr 25, 10:01 am, Paul Rubin http://phr...@nospam.invalid wrote: Mark Tarver dr.mtar...@ukonline.co.uk 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
On Apr 25, 12:07 am, Mark Tarver dr.mtar...@ukonline.co.uk wrote: On 25 Apr, 05:01, Carl Banks pavlovevide...@gmail.com wrote: On Apr 24, 8:19 am, Mark Tarver dr.mtar...@ukonline.co.uk 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
On Sat, 25 Apr 2009 08:07:19 +0100, Mark Tarver dr.mtar...@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'? -- Rhodri James *-* Wildebeeste Herder to the Masses -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
Mark Tarver dr.mtar...@ukonline.co.uk 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] -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
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 -- http://mail.python.org/mailman/listinfo/python-list
python list handling and Lisp list handling
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
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 at http://norvig.com/python-lisp.html Mark Tarver dr.mtar...@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. -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
Mark Tarver dr.mtar...@ukonline.co.uk 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
On 24 Apr, 17:19, Paul Rubin http://phr...@nospam.invalid wrote: 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 Mark Tarver dr.mtar...@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. Ah; so this def cons (x,y): return [x] + y is not accurate? Mark -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
Mark Tarver dr.mtar...@ukonline.co.uk 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
On 24 Apr, 19:54, Arnaud Delobelle arno...@googlemail.com wrote: Mark Tarver dr.mtar...@ukonline.co.uk 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
On Sat, 25 Apr 2009 00:32:26 +0100, Mark Tarver dr.mtar...@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 -- http://mail.python.org/mailman/listinfo/python-list
Re: python list handling and Lisp list handling
On Apr 24, 8:19 am, Mark Tarver dr.mtar...@ukonline.co.uk 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 -- http://mail.python.org/mailman/listinfo/python-list
