for-each et al

[Andy Wingo <wingo@pobox.com>]

Hi,

I was looking at some profiles of the compiler in master, and
surprisingly for-each was fairly high in the list.  Probably for-each
should be inlined; but be that as it may, I thought I should take a look
inside for-each and see what the deal was.

The current boot-9 for-each for one list argument is this nastiness:

  (define for-each
    (case-lambda
      ((f l)
       (let for-each1 ((hare l) (tortoise l))
         (if (pair? hare)
             (begin
               (f (car hare))
               (let ((hare (cdr hare)))
                 (if (pair? hare)
                     (begin
                       (when (eq? tortoise hare)
                         (scm-error 'wrong-type-arg "for-each" "Circular list: ~S"
                                    (list l) #f))
                       (f (car hare))
                       (for-each1 (cdr hare) (cdr tortoise)))
                     (for-each1 hare tortoise))))
             (if (not (null? hare))
                 (scm-error 'wrong-type-arg "for-each" "Not a list: ~S"
                            (list l) #f)))))
      ...))

Terrible.  And it's slower than this:

  (lambda (f l)
    (unless (list? l)
      (scm-error 'wrong-type-arg "for-each" "Not a list: ~S" (list l) #f))
    (let for-each1 ((l l))
      (unless (null? l)
        (f (car l))
        (for-each1 (cdr l)))))

So, pop quiz: what's the difference between the two?

Yes, the first version would raise a "circular list" error instead of
"not a list" on a circular list -- not that anyone cares, I think.

Also, the boot-9 version calls the procedure on earlier elements of
non-lists, something that perhaps it should avoid.

But the real difference is in the handling of concurrent manipulation of
the list being traversed.  The boot-9 version is mostly tolerant of
concurrent manipulation (either by f or by another thread), as it
detects non-lists lazily.  In contrast if a list is concurrently made
circular, the check-then-iterate version will loop infinitely.
(Incidentally the generic multi-list variant of for-each is vulnerable
to this kind of bug.)

I invite you to check out this Matthew Flatt article from November 2007:

  http://blog.racket-lang.org/2007/11/getting-rid-of-set-car-and-set-cdr.html

Of course, there are different levels at which this problem can be
solved.  I think moving towards deprecation and removal of mutable pairs
is probably a good idea, though it's really complicated and not really
the point of this mail.  OTOH I think it's reasonable to ask for a
consensus opinion on this implementation of "for-each":

  (lambda (f l)
    (unless (list? l)
      (scm-error 'wrong-type-arg "for-each" "Not a list: ~S" (list l) #f))
    (let for-each1 ((l l))
      (unless (null? l)
        (f (car l))
        (for-each1 (cdr l)))))

Is this a reasonable implementation?  Are we OK with the possibility for
infinite-loops or exceptions accessing the car/cdr of what might not be
a pair?  Alternately if we change the test to pair? are we OK with the
possibility of the loop possibly ending silently before its time?  How
do we deal with this kind of bug -- what's our perspective?

My proposal would be that eventually, I don't know how, but Guile should
remove all use of mutable pairs in its own code.  There's not much
set-car!/set-cdr! in Scheme so it's not that big of a deal.  Therefore
in light of that long-term goal, we should write library code as if
pairs were immutable, and therefore the test-then-iterate example is
fine code.

WDYT?

Cheers,

Andy
-- 
http://wingolog.org/