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

[John Cowan <cowan@x>]

John Boyle scripsit:

> I might define some kind of binary tree structure, where each node
> has a pointer to its parent--or to the root of the tree.  I would
> characterize this as a very finite graph, and would not consider a
> tree with two equal?  nodes added to it as the same as a tree with
> only one node.

Well, sure.  But then you are using pairs to define a different data
structure from the ordinary binary tree/graph.  After all, you don't
expect `equal?` applied to two a-lists to return whether or not they
equal *as a-lists*; you'd need an entirely different predicate for that.

> > That's a non-conformant implementation of R7RS `write`, which is
> > required to use labels only in the presence of cycles, not in the
> > presence of structure-sharing.
> 
> Hah.  Do you mean to say that an implementation should detect the *exact*
> amount of datum-labeling that is necessary to represent a list without
> infinite loops, and do no more than that?  

No, I mean that it should report no more labels than necessary.
It would be all right, for example, for #1=(a . #1#) to be 
reported as #1=(a a a a a . #1#), which has more datums than
necessary.

The point of separating `write` and `write-shared` is to avoid shipping
labels to a Scheme system that does not understand them, unless there is
no way to avoid them.  So `write` introduces labels in the presence of
loops, but not when there are none.  In the current head of the draft,
it's undefined whether in the presence of a loop shared structure is
reported or not, but in my personal view the intention is better served
if it is not.

> The obvious thing to do is just to indiscriminately use write-shared for
> the whole structure once a single cycle has been found; this is what Racket
> does, and I would be amazed if an implementation did anything else.

Ikarus/Vicare does not:

> (define x '(x))
> (define y `(,y ,y))  ;shared structure
> (set-cdr! (cdr y) y) ;loop
> y
#0=((x) (x) . #0#)

> - Specify merely that "write" must produce something that, when read
> back in, will be equal? to the results of "write-shared".

I think that's equivalent to what the draft now says:

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.

> I imagine "read" will remain simple (will not, for example, read "(1
> 1 1 . #0=(1 . #0#))" into a single cons cell--basically, it assumes
> the output was made by "write-shared").

Yes.

> By the way, when hash-tables are specified, will it be possible to
> make a hash-table with an arbitrary equality predicate?

I have no idea.  Why don't you join WG2 when it awakens from hibernation,
and get a say?  WG2 members don't have to work on every package, just
the ones that interest them.

-- 
If you have ever wondered if you are in hell,         John Cowan
it has been said, then you are on a well-traveled     http://www.ccil.org/~cowan
road of spiritual inquiry.  If you are absolutely     cowan@x
sure you are in hell, however, then you must be
on the Cross Bronx Expressway.          --Alan Feuer, NYTimes, 2002-09-20

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