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

[Tim Peters]

[Matthias Felleisen]
> Yes, finite maps and functions should be added to the constructors
> of the data definition list. Omitted by accident.

Ah -- great.  I proceeded to go off the deep end reading extreme
reductionist inclinations into the omission.  Happy to drop all that.

> But, on recursion vs iteration you don't seem to know much about Scheme:
>
>   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
>
>
> 1. Here is why this match that I am talking about matters:
>
>    datatype list = null | cons of int * list
>
>              ^                            |
>              |                            |
>              ------------------------------
>
>    I am using ML notation to spec a datatype, and the backpointer
>    shows the self-reference in the data definition.

Certainly *a* way to define a list of ints, and certainly the *natural* way
provided you're using ML (or thinking in Scheme).  Python is more from the
Algol line, where "a sequence" is taken as primitive in its own right (see,
e.g., C.A.R. Hoare's "Notes on data structuring").  A loop is the canonical
way to process objects of sequence types, just as first/rest recursion is
the canonical way to process a list in Scheme.  The program structure
matches the data structure in both, but since they view the data structure
differently the program structures differ too.  It's not the case that one
is unprincipled.

>    Now compare this to the function definition:
>
>    f(some_list) = (cond
>                    [(null? some_list) ...]
>                    [(cons? some_list) ... (first some_list) ...
> f(rest(some_list))])
>    ^                                                            |
>    |                                                            |
>    --------------------------------------------------------------
>
>    Number of function clauses: 2, because there are 2 clauses in
> the data def
>    Selectors in second clause: 2, because there are 2 fields in
> the data def
>    Recursion in the second clause: yes, because there is self-ref
> in the data def
>    Recursion on the second selector: yes, because ...
>
>    Now show me how to explain this with a for-loop.

A for loop isn't a natural way to process a list if you define a list
inductively; it's natural for sequences.  In a Haskell-ish type declaration
system for Python it would look more like

    datatype intseq = [int]

    def f(some_intseq):
        for element in some_intseq:
             do something with the int "element"


or
    datatype XXXseq = [XXX]

    def f(some_XXXseq):
        for element in some_XXXseq:
            do something with the XXX "element"

>    Now show me how to tell kids that all this generalizes to dd's
>    with 10 clauses and 22 self-refs?

It doesn't, of course -- then you're outside the realm of sequence types.
In the Algol line, such things are done via recursive datatypes (with or
without explicit pointers; "without" in Python), using either "magic values"
(like your "null" above) to terminate recursion, or a discriminated union.
The structure of a recursive program matches the structure of a recursive
datatype declaration closely there too, testing the special value or
discriminator to decide which case obtains, and recursing on the recursive
fields.  Wirth's classic "Algorithms + Data Structures = Programs" is a fine
text showing how to proceed systematically in such cases in Algol-like
languages.

> 2. Scheme abstracts uniformly with lambda (Python doesn't). So, of course
>    we teach that the same pattern for list-processing comes up over and
>    over again. And then we show how to abstract: using map and for-each.
>
>    From then on students understand that
>
>     (for-each (lambda (element) (display element) (newline))
> list-of-elements)
>
>    is perfectly okay.

How often do they use "map" instead by mistake <wink>?  I appreciate what
you're saying, but don't think that, e.g., Kirby's students will suffer
brain damage if they can write that

    for x in sequence:
        print x

their first hour.  You have to delay introducing lists in "How To Design
Programs" for a long time, because you need to introduce most of Scheme's
basic machinery first to be able to do anything interesting with them.

>    But, they also understand how to abstract for a data
>    def with 22 clauses and 10 self-references.

I expect you're exaggerating there, yes?  The difference bewteen one and two
is significant to a newcomer, no matter how clear it is to an expert.  But
once they grasp two, I'll buy that the leap to 1000 is relatively easy.  I
appreciate that an inductively defined list is the easiest way to *start*
this journey; in Python I'd do that by ignoring the built-in list type when
the time comes and building a new list type via a Pair (Cons, whatever)
class instead.

> 3. You write more stuff on reductionist view of programming. I didn't
>    advertise a reductionist view. I said that one teaches matching of
>    data defs and functions first, and then one moves on to abstractions.

I'm curious:  I first learned Lisp in 1970, before any "decent" curriculum
existed.  The intimate connection between data structure and program
structure is something I didn't see explicitly spelled out before Hoare's
essay (mentioned above), and I learned it in practice via Pascal (and,
indeed, from Wirth's book mentioned above).

It occurred to me at the time that I would have had a harder time learning
it in Lisp, because the Lisps I used didn't *have* a way to declare
structured types:  it was all pasted together by hand using fixed-size lists
to represent structures and defining layers of macros to make it
semi-readable.  Scheme and Python also lack ways to "spell types", and you
resorted to ML notation above while I resorted to Haskell.  Does this lack
get in the way?  Or would using ML (or Haskell -- *something* with a
carefully designed declaration system) to teach this approach have a real
advantage?

>    The reason is that students understand the why and learn to do
>    things on their own rather than copy patterns and play monkey
>    at the keyboard.

I expect that has more to do with the curriculum and the teacher than with
the language.

> Having said all that one can teach some of these things in Python of
> course. (If Python had abstracted in a uniform fashion, that would be
> easier of course.)

Python's notion of sequence is too useful to give up.  If you want an
inductively defined list, you can build one and pretend sequences didn't
exist.  I'm not entirely sure what lesson that would teach in the end,
though <wink>.

> Having said all that, I must admit that I don't think of R5RS but my own
> Scheme.

Or Schemes?  The language levels in DrScheme are a great idea!