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

[Shiro Kawai]

According to the note on 'map' in section 23.3.1, page 124
must the r6rs compliant system raise an exception in the
following code?

  (let ((x (list 1 2)))
    (set-cdr! (cdr x) x)   ;; x = #0=(1 2 . #0#)
    (map f some-list x))

This may be a kluge, but sometimes it is handy and I'd miss it
if R6RS won't allow it.

--shiro


From: Abdulaziz Ghuloum <aghuloum at cs.indiana.edu>
Subject: Re: [r6rs-discuss] [Formal] Requirement to detect circular lists
Date: Mon, 2 Oct 2006 05:11:36 -0400

> 
> On Oct 1, 2006, at 5:08 PM, AndrevanTonder wrote:
> 
> > Name        : Andre van Tonder
> > Email       : andre at het.brown.edu
> > Type        : defect
> > Priority    : minor
> > Component   : Mutable list arguments
> > Version     : 5.91
> > Pages       : 123-125
> > Dependencies: None
> >
> > Summary:
> > --------
> >
> > Requirement of cycle detection in list procedures
> > may be too onerous, potential performance problem.
> >
> > Description:
> > ------------
> >
> > The draft requires procedures such as length, and
> > various others, to detect and raise an exception
> > if passed a circular list.
> 
> > This may adversely affect performance globally
> > to accommodate an uncommon bug, in addition
> > to complicating the implementation of these
> > procedures rather significantly.
> 
> 1.  The claim of "adverse global effects on performance"
> needs to be supported.  Having used and implemented these
> procedures with full error detection under optimizing
> compilers, I wouldn't characterize the effects on
> performance as "adverse".  Additionally, if performance
> really matters in this case, you can either add a "fast"
> or "unsafe" declaration to your code or implement a
> version of these procedures that performs no circularity
> detection yourself.
> 
> 2.  The claim of circularity bugs being uncommon may be
> true, though there is no evidence of it.  I personally
> prefer getting an error when I make these bugs since
> they are, after all, bugs as you stated.
> 
> 3.  The claim that circularity detection complicates the
> implementation of these procedures "significantly" is no
> reason for dropping the requirement of raising an
> exception.  First, the hare-and-tortoise algorithm is by
> no means complicated compared to the other tasks that an
> implementation must perform.  Second, these procedures
> are implemented once, correctly, and very rarely need to
> be revised.  Third and most importantly, even if it were
> true that implementing these procedures is complicated,
> so what?  Making Scheme easy to implement is not a goal
> of R6RS as far as I can tell.
> 
> Aziz,,,
> 
> 
> _______________________________________________
> r6rs-discuss mailing list
> r6rs-discuss at lists.r6rs.org
> http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
>