[Edu-sig] Python for CS101

[John Zelle]

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.

> 
>>The discussion in the link above also shows that it's perfectly easy ---
>>and all too often likely --- for beginners to do silly things using
>>Python's lists too.  On Python-tutor, we often do get beginners who will
>>do things like list.pop(0), and not understand why it goes so slowly,
>>compared to doing list.pop().
> 

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.

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

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

> 
> Perhaps "imperfection" is a nicer term than "flaw". :-)
> 
> Toby
> 
> 
> _______________________________________________
> Edu-sig mailing list
> Edu-sig at python.org
> http://mail.python.org/mailman/listinfo/edu-sig
> 
> 

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