[r6rs-discuss] [Formal] Requirement to detect circular lists - benchmarks

[AndrevanTonder]

On Mon, 2 Oct 2006, AndrevanTonder wrote:

> Amazingly, the r6rs cycle-checking version is consistently faster by
> about 10%.  I would imagine the reason for this is that the loop is unrolled 
> with respect to the r5rs version.

Correction:  I really should have compared the r6rs version with a similarly 
unrolled version of the r5rs version (below).  Upon doing this, I find that the 
r5rs and r6rs times are indistinguishable in Stalin.  This agrees with Kent 
Dybvig's experience in Chez.

So my formal comment based on performance was unfounded.

(not to deny that there may still be other issues, as Shiro Kawai's map example 
illustrated).

Andre

;; unrolled r5rs length:

(define length-regular
    (lambda (clist)
      (define length-0
        (lambda (clist acc)
          (if (null? clist)
              acc
              (let ((acc (+ 1 acc)) (clist (cdr clist)))
                (if (null? clist)
                    acc
                    (length-0 (cdr clist) (+ 1 acc)))))))
      (length-0 clist 0)))

;; unrolled r6rs length:

(define length-circ
    (lambda (clist)
      (define length-0
        (lambda (clist tortoise acc)
          (if (null? clist)
              acc
              (let ((acc (+ 1 acc)) (clist (cdr clist)))
                (if (eq? clist tortoise)
                    (error "Circular list"))
                (if (null? clist)
                    acc
                    (length-0 (cdr clist) (cdr tortoise) (+ 1 acc)))))))
      (length-0 clist clist 0)))