Teaching : Python, Scheme, Java...

[Alex Martelli]

<posted & mailed>

Jean-Paul Roy wrote:

> Hi, snakes,
> 
> I'm teaching Scheme in our Univ. to 2nd year students. The cursus is now:
> - Java in 1st year
> - Scheme in 2nd year
> - Java, C++... in 3rd year and above (+ some Scheme to build an
> interpreter).

OK.  I might suggest adding some more-rigorously-functional language
to just Scheme (O'CAML has the advantage, for you, of being French and
having excellent French books about it...), but overall the picture
seems not bad.


> Now, is it a good move to swap from Java to Python in 1st year ? Some of

Yes, I think it WOULD be a good move, in general -- *however*, in terms
of the overall plan of study, I would then be a bit concerned if the
students were ONLY exposed to dynamically typed languages (Python first
year, Scheme second year) and never to statically typed ones until "the
third year and above".  Adding (perhaps some subset of) O'CAML would be
very good for this concern, too, because it would show students a *GOOD*
static typing scheme [not *EXCELLENT* -- that's reserved for Haskell!-) --
but, seriously, pretty good indeed, and heads and shoulders above the
kludgey typesystems of both Java and C++].

> us find Java a bit heavy for algorithmics. The probable discussion will
> be about:

Yes, Java IS indeed quite heavy for algorithmics -- Python "gets out
of your way", when you're teaching algorithms and data structures, in
a way Java never will.


> - Python is bad : no static types (it's ok for me)

It's perfectly OK *in general* that Python's typing is dynamic, just
as it's perfectly OK for Scheme, *BUT* you should consider the need
to expose students to SOME kind of static typing, preferably within
the first 2 years.  Doing it with a good, mathematically consistent
model such as ML's (any version -- O'CAML is a bit complicated by a
lot of twists and additions, but still the underlying model is quite
sound) or Haskell's is didactically VERY preferable to doing it with
the kludgey approaches of Java and the like, of course.

> - Pyhton is bad : recursion limit (I am astonished at that one)

Yeah, one spot where implementation and pragmatical issues have
taken priority over didactical and theoretical ones.  I suspect you
could use _Stackless_ Python and free yourself from the recursion
limit, if you could accept the limitation of running on Intel and
Intel-compatible CPU's only, but I don't know it for a fact.

> - Python is bad : tail recursion is not iterative (also astonished at
> that, I can understand with an interpreter, but compiler ?)

Implementation detail -- nobody's ever cared deeply about it.  I'm
sure a patch to _optionally_ deal with that would be well-received
(*optionally* because you want to be able to have the full stack
trace, normally, when a chain of calls including tail calls ends
up propagating an exception -- so, optimizing tail recursion would
need an explicit renunciation to see a complete stack trace in
such cases, and might be triggered by -O or some other dedicated
switch on the Python commandline, for example).

> - Python is bad : we are obliged to use message passing paradigm to add
> an element to a list (it's ok for me but some of us get angry with
> objects for beginners)

I'm sorry, but I just don't see this one.  E.g.:

onelist = [1, 2, 3]
anotherone = onelist + [4]

yes, the "+" operator, "under the covers", *IS* calling the
__add__ method of object onelist, but, why is that a problem?
If you want to modify the onelist in place,

onelist += [4]

does it (internally by calling __iadd__ on onelist, but,
again, why would that be a problem???).

Sure, calling onelist.append is more idiomatic, but if you don't
want to teach that right at the start, where's the problem with
onelist+=[...] or just onelist+[item] ...?  Perhaps I'm missign
something obvious -- I _would_ like you to clarify, thanks!

> - Python is bad : where are classical arrays ? Does:
>      from array import array
>   actually imports contiguous arrays ? How can they stay contiguous if
>   they support adding an element ? Is the access only O(1) amortized ?
>   Comes from : wanting to play with big arrays of bitmap images.

Python's so-called lists are actually "contiguous arrays" (of any
arbitrary objects, natch).  They stay contiguous when you add
elements by having a carefully tailored overallocation strategy
(and, in the case of .insert, ALSO shifting in memory all the
items that follow the insertion point -- and similarly for slice
assignments), and reallocating when necessary.  So, yes, appending
is amortized O(1) [inserting or deleting at an arbitrary point is O(N), 
and _accessing_ anylist[index] is "hard" O(1), not just amortized).

The type array.array is used for *homogeneous* arrays -- contiguous
arrays (just like builtin lists) where all items of one array are of 
the same primitive type (numbers or characters).  As for the type's
overallocation strategy, that may vary by release [as it did for
lists - they didn't have .append as O(1) amortized a few releases
ago, since they did only bounded overallocation back then] -- if
such implementation details are crucial to your didactical purposes,
they can be studied in the Python sources (and I'll be glad to help
you with that, if needed).  But I doubt you want to introduce the
array.array type to beginners -- it's really a memory optimization
for some common special cases, that's all!


> Aside from that points, a personal question as a Schemer who reads the
> Python primer:
> - how do you ask if a list is empty ? Is the following ok ?
>       if L == [] :

It works, though it's not idiomatic.  Other alternatives:

    if len(L) == 0: print 'L is empty'

    if not len(L): print 'L is empty'

    if not L: print 'L is empty'

the latter is idiomatic: any container is false IFF it's empty, so,
the boolean 'not' operator does all you need.

> - how do you ask if the list has only one element, with time 0(1) ? The
>   Scheme/Lisp analog is (null? (cdr L))

    if len(L) == 1: print 'L has exactly 1 element'

is the only construct that would come to most pythonistas' minds (and
yes, it's O(1)).  Other approaches you'd probably only see in some
kinds of "obfuscated Python" -- somebody trying hard to be clever --
and they might e.g. exploit slicing:

    if not L[1:2]: print 'L has 0 or 1 elements'

Slicing can be handy because it's tolerant of indices out of bounds
(differently from indexing, which raises exceptions when you index
out of bounds!).  But it makes no sense to "get too cute about it";
when you're interested in the length of L, len(L) is the way to go.

> - more generally, is the length of a list a builtin ? Is the L[k] access
>   time O(1) with a list ? Probably not. And with a tuple ?

len is a built-in function.  len(L) is O(1) for any list L, and len(T)
is O(1) for any tuple T.  Indexing, L[k] and T[k], are also both O(1).


> Sorry for so many questions and your time.

The root of half of your problems is the strange use of the term
"list" in Python -- QUITE different from most uses of the same term
in all of CS and programming literature -- so it's WE, the Python
community, who should be apologizing to you for wasting some of
your time with it.  It's too late of course to eradicate the Python
use of the term "list" (the word 'list' itself is the name of the
built-in type, among other considerations) but at least the tutorial
should definitely mention it up front that a 'list' is really a
(potentially heterogeneous) vector (able to grow and shrink, but
contiguous in memory at all times -- this is somewhat more than an
implementation detail, as it governs the O()-behavior of many of
the aspects of Python lists...).


> But thanks a lot, I guess that Python is a good guy :-)

You're welcome!!!  And, yes, you'll do your students a world of
good if you can teach them Python as their first language -- it
can give them a very useful tool that will help them in a lot of
ways throughout their careers, both conceptually and practically
(e.g., when they later get around to studying sockets, or Java
libraries, etc, etc, being able to play interactively with them
with Python [or Jython -- same language, but implemented on top
of a JVM] will perhaps ease their learning enormously).


Alex