[Edu-sig] Python for CS101

[Toby Donaldson]

On 5/6/05 8:47 PM, "John Zelle" <john.zelle at wartburg.edu> wrote:

> 
> 
> Toby Donaldson wrote:
>>>> For instance, to write an efficient queue data structure (where adding
>>>> and removing form the queue are always constant-time operations) in
>>>> LISP/Scheme requires using arrays.
>>> 
>>> Hi Toby,
>>> 
>>> I don't think this is a valid criticism.  If the point of using a queue is
>>> to teach how to write an efficient data structure, is the target audience
>>> really going to be beginners?  Do beginners care about efficiency, to the
>>> exclusion of all else?
>> 
>> 
>> If beginners don't care about the efficiency of queues, then they need to
>> learn otherwise. Performance is certainly not the only thing, but it was one
>> of the most important things, especially for an object that is going to be
>> re-used again and again.
>> 
>> 
>>> What you said is also technically wrong: there are efficent ways to
>>> implement queues with pure list structures.  See:
>>> 
>>>   http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/210459
>>> 
>>> which is basically a translation of a Lisp-friendly queue class.
>> 
>> 
>> Indeed, this is a neat trick for implementing queues with stacks.
>> 
>> However, it's not the best implementation for simple fixed capacity queues
>> where each add/remove operation is required to finish in constant time (as
>> opposed to amortized constant time). I don't know any way to achieve that in
>> LISP using only lists.
>> 
> 
> For the record, it's very easy in LISP to implement a Queue using a
> cons-pair with car pointing to the front of a linked list and cdr
> pointing to the back. Using such a structure, constant time enqueue and
> dequeue is trivial without arrays or amortized analysis. LISP allows one
> to easily build any linked structure you'd like. There is no restriction
> to a linear list with only a head (car) pointer.
> 
> Of course implementing something like a queue which has state
> (side-effects) is not pure functional programming, but real LISP
> programmers don't worry too much about that.

Thanks for pointing this out; I did a bit of searching on the web and found
an implementation of what you are referring to. I'd never seen this before.
I guess I should know better than to doubt what's possible in Common LISP.
:-) Here's the code:

(defun enqueue (obj queue)
  "Enqueue an object. Return the queue."
  (if (cdr queue)
      (setf (cdr (cdr queue)) (list obj)
            (cdr queue) (cdr (cdr queue)))
    (setf (cdr queue) (list obj)
          (car queue) (cdr queue)))
  queue)


(defun dequeue (queue)
  "Dequeue an object. Return the object queued."
  (when (cdr queue)
    (prog1
        (caar queue)
      (if (eq (cdr queue)
              (car queue))
          (setf (car queue) nil
                (cdr queue) nil))
      (setf (car queue) (cdr (car queue))))))

Again, I think it is still an example of a design flaw in LISP because it
violates the precept "simple things should be done simply".
 
> Interestingly, I recently needed a queue in Python and timed some
> alternatives. For run-of-the-mill work, the naive use of a list using
> append and pop(0) actually faired quite well for modest Q sizes.
> 
> In any case, it is important at some point for Python suers to learn and
> understand the implications of Pythons continguous allocation. It's
> probably not crucial that the first queue they write be the most
> efficient one. Remember, premature optimization is the root of much evil.

I agree that optimization should come last, if at all.

One could argue that in, say, C, the simple way to implement a fixed-sized
queue is as a circular array. If you believe that, then I would suggest that
is an example of good design: the simple solution to a simple problem is
also the most efficient.

>> 
>>> Abstractions always leak.  But I wouldn't say that Python is flawed
>>> because it makes it easy to do list.pop(0), nor would I say Lisp is flawed
>>> because it makes it easy to use linked lists.
>> 
>> 
>> True. I would agree with this statement. The flaw in LISP is the fact that
>> it requires *both* the use of lists and arrays to implement certain
>> elementary algorithms in the best way, and that the lists and arrays have
>> different interfaces.
> 
> Sometimes a linked structure us the right one, sometimes a contiguous
> structure is better. Having both in LISP hardly seems like a design
> flaw. Python does not provide a built-in linked structure, but you can
> easily implement one yourself. Some would argue the lack of a built-in
> linked list is the flaw.

If one uses linked lists, then it is a flaw in Python. Personally, I have
never needed a linked list in Python.

> If your argument is that both kinds of structures should have exactly
> the same interface, that adds to the beginner's confusiuon over
> efficiency that you argued above. By only providing the operations that
> are efficient for the particular structure, LISP helps the novice
> programmer use the more appropriate structure for a given task.

Interesting argument. Although in Common LISP the "nth" function retrieves
list items in linear time, so inefficient list operations are provided.

Do you think Python would be a better language for beginners if a fixed-size
array data type was added to it that had a different interface than the
current dynamic lists?

Toby

> I don't think this is a particularly compelling argument for Python over
> LISP.