[Edu-sig] Python for CS101

[John Zelle]

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

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

This _is_ a simple implementation of an indefinitely long queue. A 
linked list with head and tail pointers is the classic way of solving 
this problem. You seem to have some bias against linked structures. They 
are not inherently more complicated than arrays, just different.

>
<snipped here>
> 
> 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.
> 
> 

Ah, the key here is that you are restricting yourself to a fixed size 
queue. Arguably a circular array is the best solution. However, it is 
not necessarily a trivial implementation. As anyone who has actually 
implemented this will tell you, one has to be very careful about how 
full and empty conditions are handled. It's not hard, but it is subtle. 
I've seen many flawed queue implementations.


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

I can't agree with this statement. There are many situations where a 
linked structure us the _right_ implementation of a particular 
abstraction. If you want an indefinitely large queue in Python with 
constant time operations, then a linked list is probably the best way to 
do it. Furthermore, it is very easy to implement this in Python. Using 
linked lists for this in no way illustrates any flaw in Python.

The reason you may not have seen linked lists in Python is that the 
built-in continguous implementation is so good. Still, there are cases 
where reference-based linked structures are a good thing: ordered 
structures with constant time insertion, graphs, trees, sparse matricies 
(perhaps), etc. Sometimes, the linked list is entirely hidden in the 
logic of the problem. I once did a backtracking solution to n queens in 
Python and discovered only after the fact that I had actually built a 
linked list.

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

True enough. I was only saying that your arguments seemed to be 
inconsistent. Not claiming that Common Lisp had necessarily taken this 
approach.

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

No. The operations that are efficient on a fixed size array are the same 
operations that are efficient on Python lists. For example, your 
fixed-sized (circular) queue can easily be implemented using a Python 
list. I think we agree that the "right" thing in this case is that 
programmers should be aware of what the Python list does and, when 
necessary, be able to optimize their code to use efficient operations.

The important thing to keep in mind is that it is not a design flaw 
simply that a language makes it easy to write inefficient programs. This 
is ususally the sign of a higher-level language. It becomes easier to 
write an inefficient program simply because it is easier to write 
programs period. Again, the queue example shows this. It is absolutely 
trivial to implement using append and pop(0). If O(n) efficiency is good 
enough for the problem at hand, what's wrong with that?

--John


-- 
John M. Zelle, Ph.D.             Wartburg College
Professor of Computer Science    Waverly, IA
john.zelle at wartburg.edu          (319) 352-8360