Questions about SRFI-38

[Charles Turner]

Thanks for the response.

On 02/05/2011 02:20, Per Bothner wrote:
> The key is to use System#identityHashCode rather than Object#hashCode.
> For the hash-table use either java.util.IdentityHashMap or
> gnu.kawa.util.IdentityHashTable. 

Aha, thanks. I have a prototype now, though its not implemented as you 
suggested, nor is it tied in with the pretty printer, but at least I 
have a start.

> The basic logic is:
>
> writeObject(x, out, table) {
>   Info info = table.get(x);
>   if (info == null) {
>      info = newInfo(out, table);
>      table.put(info);
>      // The tricky part is here, because you might need to emit a #N=
>      // but you don't know that yet.  So you might have to back-patch
>      // in the output stream - which may change pretty-printer re-flow.
>      out.writePositionMarker(info);
>      out.writeObjectRecursive(x);
>   } else {
>      out.writeBackReference(info);
>   }
> }
>
> Some implementations
> basically solve the problem by essentially printing twice: The first time
> just to a dummy output which makes a note of shared structures.  I'm
> not really keen on that - it seems inefficient.  Worse: inconsistencies
> seem possible, either the data structure is mutated while it is being
> printed, or if there are side-effects in the formatting routines.

Thanks for the tips. I hadn't got so far w.r.t the pretty printer 
integration. Could you explain what you mean by the writeObjectRecursive 
method of the pretty printer? Is it a "this might be printed, or it 
might be replaced with print-circle notation, but here it is just in 
case" method?

Question about the inconsistencies, in my testing, I decided to mutate 
the list as I walked it, this leads to a pretty decent O(n) algorithm 
and IIUC, would reduce further object allocation in the pretty printer's 
data structures (having to mark positions and back references). While I 
don't fully understand how the pretty printer works yet, my current 
knowledge implies that with your suggestion, the algorithm would make a 
first pass through the list (or whatever) marking "interesting" objects 
in the pretty printer's buffer, and then the pretty printer would have 
to make a second pass, possibly resolving back references. That seems 
quite expensive, like you say, it may require shifting elements around 
in the pretty printer's buffer. I'm not really arguing here :-), my 
question is, what inconsistencies should I worry about  at write-time 
mutating a list?

Thanks once again for your time, much appreciated.

Charles.