🚀 go-pugleaf

ergo@netcom.com (Isaac Rabinovitch) writes:
>This raises two questions:  First, Why does your book (*Computer Science 
>Logo Style*) spend so much time on make and on "instruction sequence"
>programs?

Well, Logo is sort of a compromise in this regard.  Functional programming
is great for computing the values of functions, as in the GCD example.
For something like turtle graphics, or an interactive question-and-answer
program, sequential programming seems more natural.

CSLS emphasizes sequential programming more heavily than I might have liked
because it's pretty hard to write interesting functional programs until you
have either recursion or higher-order functions like MAP.  That's why the
examples in the early chapters are more sequential.  These days, when I
teach a Logo class using my book as a text, I generally introduce the
higher-order functions as black boxes right from the beginning, and that
lets me show interesting functional examples earlier.  (Of course, this
approach makes students confront the function-as-data issue sooner.)  I'm
thinking about a second edition, based on Berkeley Logo, and if I do that
it'll take advantage of the fact that MAP and FILTER and so on are provided
as primitives.

[Also, to be entirely honest, I wrote volume 1 before I'd read Abelson and
Sussman, so I only partly understood the True Religion.]

>  Second, how do you justify the abolition of assignment and
>iteration to someone who is used to using them?  I don't mean the
>fancy doctrines about denotational elegance and all that.  Few
>programmers are interested in that stuff, assuming they can understand
>it.  What are the *practical* advantages?

Well, it's hard to answer a question if you rule out the answer in advance.
I don't see such a sharp line between "practical advantages" and "fancy
doctrines" as you do.  Certainly there is *no* advantage to functional
programming from the point of view of machine efficiency.  The difference
is entirely in the mind of the programmer, and so it's hard to justify
without making reference to the functional metaphor ("doctrine").  Logo
isn't purely functional and doesn't make an all-or-nothing principle of
this, but it's clear to me that some hard problems become easy problems
if you think about them in terms of recursive functions.

One of my standard anecdotes about this comes from a data structures class
that I taught a few years ago, in C, to students who had taken the Abelson
and Sussman (Scheme) course.  They were given the following midterm problem:

	Write a function that takes three arguments: a binary search tree
	and two numbers (called low and high).  The function should return
	a sequential linked list containing those numbers from the tree
	that are in the range low < x < high.  Your program should not
	examine any tree nodes if it can be deduced from already-seen nodes
	that they can't be part of the result.

What we were looking for was the C equivalent of this Logo function:

	to range :tree :low :high
	if empty.tree? :tree [op []]
	if (root.node :tree) < :low [op range (right.branch :tree) :low :high]
	if (root.node :tree) > :high [op range (left.branch :tree) :low :high]
	op (se range (left.branch :tree) :low :high
	       root.node :tree
	       range (right.branch :tree) :low :high)
	end

Hardly anyone got this question right, because they all tried to solve it
iteratively.  Even the ones who used recursion ignored the return value in
the recursive call, and tried to use global variables to keep track of
their position in the tree.  So in class the next day I said "okay, write
this in Scheme" and many of them were able to do that.  Why not in C?  Because
they had the attitude that Real Men don't use recursive functions in C
programs.

>Incidentally, you probably should make it clear that you're talking
>about a specific kind of recursion, namely tail recursion.  Most C
>programmers will look at your Euclid's example, scratch their heads,
>and say, "Gee, that's OK if you can set aside a meg for the stack.
>These list guys sure don't know how to program in the real world...."

No, I'm not especially interested in tail recursion.  If a problem
(such as the GCD one) happens to be naturally iterative, so that its
recursive solution happens to be tail recursive, then we get runtime
efficiency as an added bonus.  But as a teacher I couldn't care less
about efficiency.  If I am teaching students about the factorial function
I would much rather have them write the natural, understandable

	to fact :n
	if :n=0 [output 1]
	output :n * fact (:n-1)
	end

than the tail recursive but incomprehensible

	to fact :n
	output fact.helper :n 1
	end

	to fact.helper :n :result
	if :n=0 [output :result]
	output fact.helper :n-1 :result*:n
	end

By the way, Euclid's algorithm converges quite quickly for most inputs, so
even an implementation that doesn't support tail recursion elimination is
hardly likely to require a meg of stack!