Re: for-each et al

[ludo@gnu.org (Ludovic Courtès)]

Andy Wingo <wingo@pobox.com> skribis:

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

[...]

>> 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.

Yes.

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

Right.  R5 and R6 don’t say anything about that, but yes, we can add a
statement in the manual and NEWS to that effect.

I think the for-each change would be for 2.2, right?

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

SRFI-111 boxes.

We should check a few existing packages and usage patterns before.

For instance, I suspect SCM_SETCAR/SCM_SETCDR are actually more
widespread than their Scheme counterparts, and probably much harder to
avoid.  What can we do with them?

Another issue: what about elisp?  It needs mutable pairs, but we don’t
want to have it use a disjoint type.

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

Not really fan of the idea.  :-)

Thanks,
Ludo’.