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

[John Cowan <cowan@x>]

David A. Wheeler scripsit:

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

That's #388, and you are misquoting it.  It says "generate labels
like `write` [as of the previous draft], or loop like `write-simple`".
The vote was to have it generate labels.  The editors interpret this to
mean "generate labels only for cycles in the data structure", as
`write` does under the resolution of #442.

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

I think that's correct.

> However, the resolution of #442 (write+simple+shared) seems to forbid a
> "suspicious counter" implementation.

I don't see it.  As long as the result is correct, it doesn't have to
be the most compact possible approach.

> The current resolution of #442 still requires labels when there's
> a cycle, even though it seems unlikely that the user actually wants
> (or cares) about labels. If the user wanted labels, the user would
> have called write-shared.

Not necessarily; that ignores the distinction between `write` and
`write-shared` as resolved by #442.  `Write` always produces a finite
and rereadable answer, but not necessarily a most-precise answer.
`Write-shared` allows the reconstruction of the exact degree of sharing.

In particular, (write `(,a ,a)), where a is bound to the pair (b . c),
prints ((b . c) (b . c)) with `write`, whereas `write-shared` will print
(#1=(b . c) #1#).  (Currently, the `write` procedures of Kawa, SISC,
Chibi, Scheme 7, and Owl Lisp print the latter; all other Schemes in
my test suite print the former.)

> 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.  But what, exactly, is that procedure
> supposed to do if a cycle is detected?  Return #f?  Throw something?

I think it's been generally accepted that it means what R6RS means: the
procedure returns true iff "the (possibly infinite) unfoldings of its
arguments into regular trees are equal as ordered trees."  In particular,
that means that #1=(a b . #1#) and #1=(a b a b . #1#) are the same in
the sense of `equal?`.  If necessary, I will add this wording to R7RS,
but I'd rather have clearer wording if anyone has some on tap.

> This additional requirement imposes a major new performance
> cost, but the spec doesn't even promise to do something if it happens.

I agree, and we need new language.

> * In "equal?", change "Even if its arguments are circular data
> structures, equal? must always terminate" to "Even if its arguments
> are circular data structures, equal? must always terminate; equal? must
> return #f if it terminates due to a cycle."

-1; see above.

> * "write" should specifically say: "Shared structure is not represented
> using datum labels (see write-shared)."

The draft 7 text reads:

# If \var{obj} contains cycles which would cause an infinite loop using
# the normal written representation, then at least the objects that form
# part of the cycle must be represented using datum labels as described
# in section~\ref{labelsection}.  Datum labels must not be used if there
# are no cycles.

> * Both "write" and "display" should say: "This procedure must always
> terminate; if a circular data structure is detected, a condition
> is raised."

-1; see above.

> In general, I like how R7RS is shaping up; this seems to be a sore spot
> in an otherwise really promising spec.  I especially can't wait for a
> library and exception system that might actually *PORT* across Schemes.

In my more dysthymic moments, I feel that everyone will look at R7RS,
say "It's absolutely stellar, except for...", with a different except-for
for each person, and the whole thing will go down with a great big crash.

-- 
John Cowan            http://www.ccil.org/~cowan     cowan@x
Uneasy lies the head that wears the Editor's hat! --Eddie Foirbeis Climo

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