[Edu-sig] Re: Lisp vs Scheme vs Python

[Tim Peters]

[Matthias Felleisen]
> ...
> Recursion:
>  Read up on data types and how to specify them. Mathematically
>  speaking (and that's what you want to do), there are
>
>   basic sets
>   subsets
>   unions
>   products
>   inductive definitions
>   (co-inductive definitions).
>
>  That's it.

I'd add finite maps to the list, aka associative arrays ("dictionaries" in
Python).  Viewing a finite map as a subset of the product of the key and
value sets isn't particularly illuminating, and especially not in a
programming context.  You can object that it's not "primitive", but then
neither are products:  in set theory products are defined in terms of
ordered pairs, where ordered pairs are in turn defined in terms of unordered
sets, the ordered pair (a, b) being (by definition) the set {{a}, {a, b}}.
Since products are frequent in practice, that reduction is too tedious to
endure every time, so we agree to pretend products are primitive in order to
get on with life.  Finite maps are also useful enough to merit
(pseudo)primitive status.

> Your basic functions in a program should match the data defs.  The
> only way to match induction is to use recursion.

No argument, but I'll add that most lists in Python programs are better
viewed as elements of product sets; e.g., if you've got a list of 5 names of
things to buy at the store, I expect most non-Scheme programmers view that
as being an element of the String**5 product space; *from* that view,
indexing via ordinal position is natural, while traversing via recursion is
as strained as viewing products as nested sets.  They're both theoretically
sound views (unless you want to disown products <wink>).

> ...
>  Loops are short-hands for linear recursions.

Ya, and integer literals "are" short-hands for lambda compositions too.
Demonstrating that a thing can be defined in terms of something more
primitive doesn't make the case that the latter view is "more correct".  Why
not use a combinator-based language and give up the pesky concept of
variable names too?  If theoretical minimalism is a goal, a language like
Joy makes Scheme look positively bloated with gratuitous pragmatic
compromises:

    http://www.latrobe.edu.au/www/philosophy/phimvt/j00syn.html

Now I happen to like gratuitous pragmatic compromises, and would much rather
program in Scheme than in Joy.  But if you want to cut to the heart of
CompSci without "irrelevant" concerns about practicality or transparency
getting in the way, Joy looks like a better bet (fewer primitive concepts:
no vrbls, no formal parameters, no block structure, no iteration, and even
lists "are" programs).

>  But because there is an infinite way of doing linear mutual
>  recursions among data defs, you can't get away with a finite
>  number of looping constructs -- if you want to match data defs
>  and program defs. You need recursion.

Heartily agreed.  Where Python parts company is in believing that *all*
iteration is better expressed via recursion, and in particular iteration
over lists.  The notion that

    for element in list:
        do something with element

is hard to explain in theory or practice doesn't hold water; OTOH, Python
has no looping construct anywhere close to the complexity of Scheme's "do"
macro (if you think iteration confuses students, it could be simply because
you're teaching it via Scheme's bloated macro version!  "for" in Python is
tied to sequences, not arbitrarily large collections of initialization and
rebinding and termination expressions).