Re: Lisp vs Scheme vs Python
Kirby, your teacher understood Lisp and Lisp vs Python very well. He didn't understand Scheme and why recursive programming matters. Scheme and S-expressions: your teacher was clueless in that regard. Scheme, macros and do: You don't need to teach about macros to use looping constructs. You can use the ones that every Scheme provides (do) and introduce new ones for your students, if you believe it's best. Of course it isn't :-). 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. Your basic functions in a program should match the data defs. The only way to match induction is to use recursion. The kind of recursion that you know (e.g. quicksort, fractals) has little to do with data. It's an algorithmic technique beyond basic programming. Loops are short-hands for linear recursions. 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. Read HtDP (http://www.htdp.org). -- Matthias
[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).
Wow. We're even getting polysyllabic pissing matches on the Edu list. Way cool. <big wink> --- Patrick K. O'Brien Orbtech "I am, therefore I think." -----Original Message----- From: edu-sig-admin@python.org [mailto:edu-sig-admin@python.org]On Behalf Of Tim Peters Sent: Sunday, May 27, 2001 2:44 PM To: edu-sig@python.org Subject: RE: [Edu-sig] Re: Lisp vs Scheme vs Python [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. <much more snipped>
That's it. Your basic functions in a program should match the data defs. The only way to match induction is to use recursion. The kind of recursion that you know (e.g. quicksort, fractals) has little to do with data. It's an algorithmic technique beyond basic programming.
So in these cases (quicksort and fractals) perhaps recursion is gratuitious, as it isn't justified by data defs. Certainly factorial (not fractals) is just as well implemented in Python with reduce(mul, range(1,n+1)) as with any recursive syntax.
Loops are short-hands for linear recursions. 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.
Read HtDP (http://www.htdp.org).
I'll check into it (have before but it's been some time -- very cool to have this book on the web). Another asset in the same category is: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-4.html -- also Scheme-heavy. On the other hand I don't think computer science should be too inward- looking. If my analogy is a conveyor belt, and/or things (objects) moving along through a channel (pipe), and each getting operations applied to it, then so be it. I don't require further theory to justify using this metaphor in a program. And in the cut'n paste from IDLE below, I vastly prefer loopit2. If theory says I should use loopit instead, then I say we should fix the theory.
def f(x): return x + 2 f(3) 5 mylist = range(15) def loopit(f,mylist): if len(mylist)==0: return [] return [f(mylist[0])] + loopit(f,mylist[1:])
loopit(f,mylist) [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] loopit(f,[]) [] loopit(f,[1]) [3] def loopit2(f,mylist): return map(f,mylist)
loopit2(f,mylist) [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] loopit2(f,[]) [] loopit2(f,[1]) [3]
Kirby
No recursion is not gratuitous with quicksort and fractals. It's necessary there. Eliminating it means you manage your own stack, and I bet you're not as good at that as Guido. _Teaching_ recursion first, followed by abstraction (of which iterators are just one simple part) is not inward looking. It is _empowering_ programmers and _empowering_ people who wish to learn to think systematically. Of course I prefer (map (lambda (x) (* x 2)) (build-list 10 identity)) over whatever goble-dee-gook the recursive defs look like. But I thought this list was about teaching, empowering people with programming, and using programming to empower people to think (the way stupid old math used to do). -- Matthias
At 12:18 PM 5/28/2001 -0500, Matthias Felleisen wrote:
No recursion is not gratuitous with quicksort and fractals. It's necessary there. Eliminating it means you manage your own stack, and I bet you're not as good at that as Guido.
Convenient with fractals, sure, but why necessary? What stack management? Just iterate by adding 1 and multiply the growing product until term = n. The model in mathematics, for fractals, is akin to SIGMA notation, except using the capital letter PI, which means multiply terms together vs. add them. So: n n! = PI j j=1 That's a "primitive definition" in a math textbook, and there's nothing recursive about it, any more than in: n tri(n) = SIGMA j j=1 i.e. the nth triangular number, also equal to n*(n+1)/2.
_Teaching_ recursion first, followed by abstraction (of which iterators are just one simple part) is not inward looking. It is _empowering_ programmers and _empowering_ people who wish to learn to think systematically.
If all you have is a hammer, everything looks like a nail. I just don't want recursion to be the hammer. We have a variety of tools, of which recursion is one. It should be taught -- not sure about first though. By the time students get to programming, they probably already have experience with iterative, non-recursive processing, so it's already too late to teach recursion before anything else.
Of course I prefer
(map (lambda (x) (* x 2)) (build-list 10 identity))
over whatever goble-dee-gook the recursive defs look like. But I thought this list was about teaching, empowering people with programming, and using programming to empower people to think (the way stupid old math used to do).
-- Matthias
Yes, map(lambda x: x*2, range(10)) also works in Python. So if you prefer it, would you teach students to write it this way? I've suspicious of curricula in which the most "formally correct" way to do something is out of sync with the practical way of doing it. I'm not a huge fan of the Bourbaki school of thought, either, for much the same reason. Kirby
Convenient with fractals, sure, but why necessary? What stack management? Just iterate by adding 1 and multiply the growing product until term = n.
The model in mathematics, for fractals, is akin to SIGMA notation, except using the capital letter PI, which means multiply terms together vs. add them. So:
Duh -- I wrote *fractal* and was thinking of *factorial* the whole time. Silly brain (knock knock -- wake up!). True enough, when I did my lsystems.py (not completely finished), recursion was key, e.g.: def iterate(n,axiom,rules): if n>0: axiom = produce(axiom,rules) print "Iteration count-down %s" % n return iterate(n-1,axiom,rules) else: return axiom So, re *factorial* (I should have said), there's no need to go the recursive route. Please make the appropriate substitutions. And now I understand what you meant by Guido and stack management -- yes, when using recursion, I rely on whatever language implementation to keep track of the process. Kirby
And now I understand what you meant by Guido and stack management -- yes, when using recursion, I rely on whatever language implementation to keep track of the process. :-) [I knew you'd see the mistakes of your way eventually. And you also understand that "subtitution" leads to vacuous claims.] Of course, if lambda were to bind variables properly, you could always teach continuation-passing style and get away with closures, rather than stacks. Well, that's for PPython (or Parenthesized Python to do). And once kids understand that, nothing stands in their wau of generating interactive CGI scripts from interactive programs. (Hey, why not turn IDLE into an interactive CGI script that way?) -- Matthias
At 01:40 PM 5/28/2001 -0500, Matthias Felleisen wrote:
And now I understand what you meant by Guido and stack management -- yes, when using recursion, I rely on whatever language implementation to keep track of the process.
:-) [I knew you'd see the mistakes of your way eventually. And you also understand that "subtitution" leads to vacuous claims.]
Yes, I see. It's so obvious to me now. Kirby
[Kirby Urner, to Matthias]
Yes, map(lambda x: x*2, range(10)) also works in Python.
So if you prefer it, would you teach students to write it this way?
I'm sure he does, but not at first: if you view lists as inductively defined recursive data structures (which he does), then you really need to teach what all those big words <wink> *mean* first. Then map is a simple application of those ideas, and students can implement it themselves with full confidence in what they're doing. Once they reach that stage, cool, just use "map" directly. Python views lists as sequences instead, and is more concerned about making operations transparent "at a glance" than in building them from the ground up. From that view, in current Python the preferred way to write the above is [x**2 for x in range(10)] a variant of set-builder notation borrowed from SETL via Haskell.
I've suspicious of curricula in which the most "formally correct" way to do something is out of sync with the practical way of doing it.
There's nothing formally suspect about "map" in Python or Scheme -- although, strictly speaking, Scheme's "map" doesn't define the order in which the function is applied, so there's a bunch of artificial complexity there catering to optimized implementations. Python doesn't have anything like that: every Python expression is exactly as slow as it looks <wink>.
[Matthias Felleisen]
No recursion is not gratuitous with quicksort and fractals. It's necessary there. Eliminating it means you manage your own stack, and I bet you're not as good at that as Guido.
Guido is quite fond of recursion -- the Python implementation is full of it (a statement you may agree with under an unintended reading <wink>).
participants (4)
-
Kirby Urner -
Matthias Felleisen -
Patrick K. O'Brien -
Tim Peters