Formal comment #45 (defect)

last-element behavior of for-each
Reported by:	Per Bothner

Component:	other
Version:	5.91

The specification of for-each (in R5RS as well as R6RS) has a weird
asymmetry in that the result value is the result of calling the
function on the last elements. Furthermore, it is required to
tail-call the function on the last element.

The problem is that this specification makes it more difficult to
optimize for-each. If we didn't have this requirement a compiler could
transform (for-each proc list) into:

  (do ((p list (cdr p)))
    (if (not (null? p))
       (let ((x (car p)))
          (proc x))))

(Notice the unspecified else clause.) 

The key point is that this transformation further allows the compiler
to inline proc. If the last tail call to proc must be a tail-call,
then the inlining gets ugly. I think you'd need two copies of the call
to proc: one for each iteration except the last, and then a final
tail-call. The former can be inlined, but the latter cannot be,
Duplicate copies is bad: it leads to code bloat, more difficulties for
a debugger in setting breakpoints, etc.

Now presumably an even-more-sophisticated compiler would figure out
when it is safe to use a non-tail-call for the final element. But that
requires global analysis. If we get rid of the weird last-element
semantics even a fairly simple compiler can do this optimization.

In addition to hurting optimization the asymmetry in the specification
is inelegant, in my opinion.

I propose that the return value of for-each be "the unspecified value"
[pending resolution of this issue], and the requirement for special
handling of the last element be removed.

RESPONSE:

Although several R5RS-conformant compilers generate inline
code for calls to for-each, this inlining would become less
likely for the draft R6RS semantics of for-each.  The main
problem is that for-each must raise an exception if any of
its list arguments is not a list; that can be detected by a
call to list?, however.  The formal comment points out a
secondary problem.

There is little benefit to requiring for-each to perform a
tail-call for its last call.  The R5RS did not require it,
and the R6RS should not require it either.

The comment proposes that for-each be required to return
the unspecified value.  There is little benefit to that.
The R5RS did not specify the value returned by for-each,
and the R6RS should not specify it either.