Re: for-each et al

[Andy Wingo <wingo@pobox.com>]

On Sun 02 Mar 2014 22:27, ludo@gnu.org (Ludovic Courtès) writes:

> Welcome back to email.  ;-)

Thank you :)  This makes my first round-trip ;)

>>   (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?
>
> I think an important difference you didn’t mention is that ‘list?’ does
> its list traversal in C.

That's true.  Let's call the above version for-each*.  Then we have
for-each**, which is the same except it calls list*, which is:

(define (list*? l)
  (let lp ((hare l) (tortoise l))
    (or (null? hare)
        (and (pair? hare)
             (let ((hare (cdr hare)))
               (or (null? hare)
                   (and (pair? hare)
                        (not (eq? tortoise hare))
                        (lp (cdr hare) (cdr tortoise)))))))))

Then we have:

  scheme@(guile-user)> (define l (iota 100000000))
  scheme@(guile-user)> ,time (for-each** (lambda (x) x) l)
  ;; 3.228201s real time, 3.223919s run time.  0.000000s spent in GC.
  scheme@(guile-user)> ,time (for-each* (lambda (x) x) l)
  ;; 2.356612s real time, 2.353496s run time.  0.000000s spent in GC.
  scheme@(guile-user)> ,time (for-each (lambda (x) x) l)
  ;; 3.142366s real time, 3.126806s run time.  0.000000s spent in GC.

So the overhead of traversing the list twice is negligible in the worst
case, and probably we still gain once the compiler gets better.

>>   (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)))))

> I’m OK with this implementation.  I’ve never found myself iterating over
> a list and modifying it concurrently.

Yeah it's something that no one in their right mind does.  But still we
should have some kind of statement about what we guarantee -- currently
the code is resilient to concurrent mutation, and we'd be relaxing that.

> I’m all in favor of immutable pairs.  However, I expect that a lot of
> code out there relies on it.
>
> Moving set-car! and set-cdr! to a different module like in R6 may be a
> good first (or second) step.

Brainstorming possibilities:

  * Deprecate set-car!/set-cdr! (replacement would be mutable cells in
    the car/cdr; currently called variables, but could be called boxes)

  * Introducing a #!lang facility, and having programs with #!lang make
    immutable pairs

  * ?

It's completely possible to remove mutable pair usage in Guile, but
what's not clear is how to migrate our users.  I assume that we would
want to make Guile's core operations only operate on immutable pairs;
how big would the mutable pair libraries have to be?

Could we forsake R6RS/R7RS and only do immutable pairs?  (I would be OK
with that.  In that case R5RS would run in its own environment.)

Dunno, just some thoughts.  Deprecating set-car!/set-cdr! would be an
easy first step, if we planned to make further steps.

Andy
-- 
http://wingolog.org/