Re: [Scheme-reports] Cycle detection problems: #442, #338, "equal?"

[Alex Shinn <alexshinn@x>]

Hi David,

On Wed, Aug 29, 2012 at 9:12 PM, David A. Wheeler <dwheeler@x> wrote:
>
> First, trac #338 has the display procedure "generate loops like write", but it appears to me that the later resolution in #442 means that the resolution of #338 started with a false premise.  After all, the write procedure no longer generates "loops like write", as was assumed by #338 vote.  So #338 needs revisiting.

Incorrect, as John pointed out `write' does generate loops in the
presence of cycles, and for more clarification the ticket was also
restricted to cycles to begin with.  There is no ambiguity here.

> Second, trac #442's resolution imposes a large overhead that is completely unnecessary to meet the stated goal (termination).  The comments in #442 make it clear that for ordinary "write", the primary thing some people cared about was termination in the presence of cycles.

Your comment is overly long so I'll summarize.  You
believe that allowing write to first output many megabytes
or gigabytes of garbage before detecting a cycle and
raising an exception could be done more efficiently than
detecting the cycle when it first occurs.  I'm not convinced
of this - the output itself has an arbitrarily large overhead
either on the runtime (for string/in-memory ports) or the
OS (for files).  If you set the recursion threshold too
low it's no different from checking for cycles initially,
if too high it's an easy way to explode a lot of memory
or disk.

Furthermore detecting cycles (in advance or on the fly)
can be done with a eq-hash-table with O(n) time and
O(d) space, where d <= n is the length of the longest
cycle.  Thus asymptotically it could be argued this is
faster than your proposal.

I'm also uncomfortable with `write' raising exceptions
where it never did before.

And if you want speed you can use `write-simple'.

> In addition, there seems to be a major gap in the definition of "equal?" involving cycles.  It currently says, "Even if its arguments are circular data structures, equal? must always terminate."  That additional sentence adds a MAJOR new performance and implementation cost on "equal?" compared to R5RS.

No it does not, this can be done essentially for free,
see http://www.r6rs.org/r6rs-editors/2006-February/000969.html

-- 
Alex

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports