[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Scheme's DO construct
There are two things to be said in defense of Scheme's DO:
1. Unlike most general purpose iteration constructs, DO is useful
for functional programming.
2. DO is the only general purpose iteration construct in Scheme
that doesn't force you to think up a name (such as LOOP) for
the loop.
This is a long message, but the two points above are the gist of it.
It seems to me that Andy has missed the first point entirely, considering
his remarks that:
I have no prima facie objection to the use of iterative constructs,
and in particular, none to supporting iteration in Scheme. Indeed, I
think that it is often very effective to think procedurally and
iteratively rather than functionally and recursively. (I understand
these are apples and oranges, but the styles are usually associated
with each other.)
...
I have performed the following informal experiment. I had one or
two of the people working with me who were true devotees of LOOP
and DO go back and recode fairly large (5000-15000 lines) LISP programs,
ripping out LOOP and DO and putting in DOLIST, DOTIMES, and mapping
functions. I should say that they did it "kicking and screaming," not
because of the work involved but because they so loved all the features
that LOOP offered.
LOOP is indefensible, but Andy is mistaken to lump DO with LOOP.
If by "mapping functions" Andy here means the standard Scheme mapping
functions, then MAP is the only functional alternative to DO that Andy
offered his people. MAP isn't general enough to replace DO, and DOLIST,
DOTIMES, and FOR-EACH are completely useless for functional programming.
Thus it seems that in the name of style Andy was coercing his people to
convert functional programs that use DO into non-functional programs.
It seems to me that if we truly want to discourage people from writing
functional programs, a more effective way to do it would be to change
Scheme so people can't program in the functional style until they master
a set of arbitrarily chosen rules for inserting tokens like #' and FUNCALL
into their programs.
Let's consider the functional alternatives to DO using a simple example.
The example is not too simple; it cannot easily be written using Scheme's
standard mapping procedures. (Aside: In the example, SEQUENCE is a
procedure, not a special form, so this is not portable Scheme code.
The name SEQUENCE was meaningful to my audience, so I used it anyway.
As I recall the discussion at Brandeis, SEQUENCE as a special form was
supposed to disappear over time so we could use the name for such higher
purposes, and I was very disappointed that the recent vote was phrased
as a referendum on dropping BEGIN rather than on dropping SEQUENCE.)
The example is:
(define find-word-break
(lambda (x k2)
(do ((x x (rest x)))
((or (empty? x) (not (break? (first x))))
(do ((x x (rest x))
(word '() (concat word (sequence (first x)))))
((or (empty? x) (break? (first x)))
(k2 word x)))))))
The most straightforward elimination of DO yields:
(define find-word-break
(lambda (x k2)
(letrec ((loop1
(lambda (x)
(if (or (empty? x) (not (break? (first x))))
(letrec ((loop2
(lambda (x word)
(if (or (empty? x) (break? (first x)))
(k2 word x)
(loop2 (rest x)
(concat word
(sequence (first x))))))))
(loop2 x '()))
(loop1 (rest x))))))
(loop1 x))))
This code is rather forbidding, so I would probably define loop1 and loop2
in a single LETREC. That works in this case but would not work if a
variable introduced by the outer DO were free within the inner DO.
REC or NAMED-LAMBDA would improve the code a little.
Can Scheme do better? I could instead use named LET, which would have
the advantage of moving the initialization expression for each loop
variable into proximity with its binding, and would make some of the
LAMBDAs invisible:
(define find-word-break
(lambda (x k2)
(let loop1
((x x))
(if (or (empty? x) (not (break? (first x))))
(let loop2
((x x)
(word '()))
(if (or (empty? x) (break? (first x)))
(k2 word x)
(loop2 (rest x)
(concat word (sequence (first x))))))
(loop1 (rest x))))))
This version still has two disadvantages: (1) I had to think about (or avoid
thinking about!) the names LOOP1 and LOOP2; and (2) it is hard to find the
new bindings for the loop variables. The way to overcome these disadvantages
is to invent a new special form that moves the expressions that compute the
new values for the loop variables next to their bindings (Dick Gabriel has
already pointed out the value of doing this) and to suppress the names of
the loops; in other words, to invent DO.
Having invented DO, we still have to decide on its syntax. The syntax of
Scheme's DO is less than optimal for functional programming primarily
because it is designed to support an additional feature: you can insert
non-functional statements to be executed every time around the loop.
Because Scheme is not a purely functional language, this is a reasonable
feature to support; even I use it on occasion. Unless we can come up with
a significantly better syntax, we might as well enjoy the advantages of
Lisp tradition and compatibility, while fixing any randomness (as we did
by flushing the implicit binding of RETURN and by using binding instead of
assignment for the loop variables).
I could go on and talk about why functional loops such as the ones you
write using tail recursion or DO are easier to understand than imperative
loops such as the ones you write using DOTIMES, DOLIST, FOR-EACH, or
Andy's straw FOR, VARYING, REPEAT, or WHILE, but I don't think it's
necessary for this audience.
Peace, William Clinger