On Thu, 5 Jan 2006, Michael Sperber wrote:

> Andre van Tonder <xxxxxx@now.het.brown.edu> writes:
>
>>   so it would have to be eqv?-cyclic, but the spec does not
>>   guarantee that
>>
>>    (let ((f (lambda () (construct ...))))
>>      (eqv? (f) (f))) => #f
>>
>>   for /immutable/ records, which I think would be required for
>>   such cyclic graphs.
>
> I'm not sure what exactly you mean here---do you mean that
> EQV?-*distinctness* would be required to traverse the graph in finite
> time?

In the absence of the above guarantee, I see no way of
constructing distinct nodes with the same content.

>> - I would not like to artificially declare an immutable record as
>>   mutable just so I can use it in a cyclic graph.
>
> That's a very good point (one that Richard Kelsey had also reminded me
> of earlier).  The problem is, of course, that mutability happens at
> the type level rather than the object level.  (A general problem with
> this class of record systems---too much stuff happens at the type
> level.)

> That unboxing should be supported at *some* level language seems quite
> clear to me, as this enables setting up certain kinds of abstraction
> barriers.  That it should happen at the level of records is less clear
> to me, but we don't have any other place currently.

Understood.  Is there a good reason to conflate eq?-behaviour with
field mutability, though.

To me field mutability seems to be an unnatural way of declaring eq?-
behaviour.  It seems arbitrary to me to have to
choose an arbitrary field in an immutable structure and make it mutable
just so that I can use it in a graph.  Which field do I choose, and
won't this confuse the reader of the program?

Also, how would one make a graph, with a specified shape, with nodes
belonging to a variant type, each variant declared as a record with
no fields, without further boxing?

Conceivably, an extra property in the record declaration could
specify or override the behaviour under equivalence.  Maybe
something like

   (boxed)

which would guarantee that a record remain boxed, even if it is
immutable.

Cheers
Andre