[Edu-sig] Edu-sig Digest, Vol 22, Issue 9

Danny Yoo dyoo at hkn.eecs.berkeley.edu
Tue May 10 03:26:29 CEST 2005

On Mon, 9 May 2005, Toby Donaldson wrote:

> > 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.
> :-) You must know something about my programs that I don't!

Hi Toby,

I have a bad feeling this is straying away even more from the educational
aspect of this thread, but let me take one more detour.  I think that
you're arguing that linked structure is irrelevent to Python programmers,
and that students should not learn about it.  Does that sound right, or
would you limit the argument simply to linear linked lists?

As a concrete example of linked lists in Python, take a critical look at
the implementation of xml.dom.pulldom.  The implementation depends on a
working understanding of linked lists, even though the code itself goes
out of its way to avoid using the word "linked list".  In particular, we
should pay attention to the handling of the 'firstEvent' and 'lastEvent'

I've never quite understood why that code there uses arrays, when it's
obvious that what the code is really trying to do is create linked
structure.  But I think I can argue well that the readability of the code
is damaged because the code is just sticking with the array abstraction
when it's inappropriate.  For example:

    rc = self.pulldom.firstEvent[1][0]
    self.pulldom.firstEvent[1] = self.pulldom.firstEvent[1][1]

is really, in essence, linked list operations disguised as array

It should be clear that linked structure is important: anytime we work
with structured data, we're almost certainly using linked data structures.
Anytime we use XML, we are certainly using linked structure.

Ok, detour over, I hope.

> What I am saying is that, for the case of a queue and similar utility
> data structures and algorithms that can be frequently used in many
> different programs, *I* am *not* happy with anything less than the best
> possible performance that can be achieved on the machine (not the
> *language*, the *machine*) I run it on. *I* do not want my machine
> wasting *any* time on useless overhead.

If absolute machine performance was our primary concern, we should
certainly avoid Python like the plague.  Every attribute access in Python
is a run-time hashtable lookup.  Every method call involves significant
run-time type checks to make sure we're running a program in a safe
manner.  That late-binding flexibility is NOT for free, and does incur
significant performance cost.

But if we really care about using a programming environment that is
dedicated to help programmers, then we have a different criteria for
goodness than absolute machine performance.  And if we're talking about a
language that we intend to use to teach programming, then we might have a
different goalset than a professional programmer.

I think this thread is just trying to bring up the point that "performance
at all cost"  is not the goal: it's human understanding.  We are trying to
teach students how to write readable programs for human beings: it's only
accidental that we have a machine that can actualize those programs into

Looking back at the original post on this:


it really sounds like we're talking about an introduction course that is
meant as a gateway class, so that people come out of it prepared to tackle
the other core CS classes.  I don't expect people will come out it saying
"Now I'm a professional programmer", because, frankly, they won't be. But
they'll have a basis for learning real ideas.

> My point is that if a language *only* allows for an inefficient
> implementation of something (or makes it too difficult to achieve), then
> it is flawed. Having to write an assembly language module or use some
> other special tool is fine, but I would prefer the language to do it
> itself.

Darn it;  I really don't want to contribute heat to the Lisp vs. Python
subthread, because it's not truly core, not important to what we're
talking about.  Perhaps you were just saying your statement as a
hypothetical, about any general language, but I think you mean Lisp in
particular, so I have to rebutt again and make sure there is no confusion.

You should know that the serious, extant Lisps --- Common Lisp and Scheme
--- have native support for vectors.

;;;;;; (mzscheme)
> (define words (vector "hello" "world" "this" "is" "a" "test"))
> (vector-ref words 3)

This is not a linked list, but is a real, fixed-size array structure, with
constant-time access to any arbitrary element.

I think the core questions are: is Python an appropriate language for
teaching introductory programming?  Is there support that can we provide
to make that teaching relevant and exciting to students?

Of course I think Python's a fine language; it has a familiar syntax, and
excellent runtime support.  I do think that its Standard Library and
orbiting third-party modules have matured enough that its applications to
the real world are immediately apparant.

> Anyways, this is all getting pretty far a field from Python education.

Slightly.  *grin*

But we have to teach each other before we can hope to teach others.  For
us to be truth tellers, with authenticity, we have to be right about our
facts.  And if we see an untrue assertion, we have to stand up and say
that it's wrong.

More information about the Edu-sig mailing list