Re: [PATCH] Avoid `SCM_VALIDATE_LIST ()'

[Clinton Ebadi]

Han-Wen Nienhuys <address@hidden> writes:

> Neil Jerram escreveu:
>> 2008/9/2 Han-Wen Nienhuys <address@hidden>:
>>> If you are doing memq? for something you already know to
>>> somewhere in front of the list [...]
>> 
>> Why would you do that?  In two senses:
>> 
>> 1. I know memq gives you the tail of the list, but I usually use its
>> result only as a true/false value Why would run use memq like that in
>> a situation where you already know that it will give you true?
>> 
>> 2. It feels unusual to me to have a long list, but in which certain
>> kinds of values are known always to be near the front.  That sounds
>> like something that should really be represented as two (or more)
>> separate lists.
>> 
>> Have you observed this (the current usage of SCM_VALIDATE_LIST) as a
>> performance problem in practice?
>
> No, but it feels strange to me that a function whose intrinsic function
> does not require O(n) behavior, does require it in all cases.
>
> However, I find Mikael's argument that it complicates programming a lot 
> persuasive.

How about something like (obviously better and in C):

(define (detect-cycle lst fn)
  (let ((get-hare (lambda (lst)
                    (if (and (pair? lst) (pair? (cdr lst)))
                        (cddr lst)
                        #f)))
        (get-tortoise (lambda (lst)
                        (if (pair? lst)
                            (cdr lst)
                            (error "End of list hit")))))
    (let detect ((tortoise lst)
                 (hare (get-hare lst)))
      (fn tortoise)
      (cond ((eq? tortoise hare)
             (error "cycle detected"))
            (else (detect (get-tortoise tortoise)
                          (get-hare hare)))))))

;;; example

(define (cyclic-memq x lst)
  ;; Obviously a real version would want to catch an exception here
  ;; and return the proper value
  (detect-cycle lst (lambda (sublist)
                      (if (eq? (car sublist) x)
                          (error "x found")))))

In C the only burden would be defining one-use helper functions and a
struct (or perhaps just a Scheme list since there would be at most one
or two values each faked closure would need) for storing any data they
would need. It would be a tad bit ugly, but would neatly (as neatly as
can be done in C at least) allow every list traversing primitive
function to avoid cycles (and still work on cyclic lists where the
item was actually there) without traversing the entire list.

The question then becomes whether the overhead of a bunch of indirect
function calls would be an issue. Asymptotically this wouldn't matter
(but neither does potentially traversing the entire list twice except
that now your best and worst case are both N), but in reality with
average list length and all...

Perhaps a macro could be used instead (is it possible to pass entire
blocks of code to a macro using something like CYCLE_DETECTING({
.... code ... }) in C?). It would be a very hairy macro, but would
again give every list traversal primitive the ability to avoid
spinning on cyclic lists or dying at the end of improper lists without
having a separate implementation of the tortoise and hare algorithm in
every function.

-- 
          Who will tend the garden when the snake swallows the light?          
         Who will eat the decay when the worms have lost their sight?          
           Who will rape the weak when there's nothing left to gain?           
             Who will till the soil of these barren black remains?