This is the mail archive of the kawa@sourceware.org mailing list for the Kawa project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Questions about SRFI-38


On 05/01/2011 05:41 PM, Charles Turner wrote:
My strategy so far has been to extend DisplayFormat with a formatter
that looks for shared structures (SSDisplayFormat). Instead of changing
Scheme's write directly, I thought seperating the concerns would be
wise. The kawa.lib.ports write can always be changed to write/ss later,
if a permanent change is wanted.

I'm just overriding writeList for now (testing). I have another class,
SharedStructure, which takes a list (for the time being) in its
constructor. I'm using a HashMap--which might have to be changed for
sync reasons--to keep track of the elements in the list. The first value
into the hash is the current list, i.e. the reference to current list
before traversing in. I need to map some sort of reference to this list
to some other entity which I won't go into right now. This is where I'm
getting stuck.

If I try and stuff a self-referential list into the hash, I just get a
stack overflow error because Java is too eager it seems (better than the
current behaviour though, at least it stops fairly quickly :-)). I can't
acquire the hash code of the starting list for the same reason. My use
case is a dotted pair whose car points to itself. Please may someone
advise me on how to approach this? Sorry that I haven't made more of a
dent in the problem.

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. The latter has the advantage that it can
be customized to reduce object allocation. (Or at least AbstractHashTable can be:
You can store the needed date directly in the Map.Entry. I.eâ the Info type
below would be combined with the HashNode interface.)


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);
  }
}

I.e. the idea is the output buffer is a mix of text as well as
PositionMarker and BackReference objects.  Note that when pretty-printing
you also have a mix of text and begin-group/end-group token, as well
as special breakable spaces.  These concepts are related, hence my
idea to enhance the data structures used by the pretty-printer.

Preferably, you'd like the #N= key to increase numerically for forwards
output order.  So the dumb and ugly solution to always emit those keys.
The hard part is only emitting them when needed.  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.

So the solution is when you're done with the write, you go through
output buffer, checking each PositionMarker.  If there is a back-reference
to it, you emit #N= (for the next consecutive N); otherwise you ignore it.
For each BackReference you emit #N# where N is the number allocated for
the PositionMarker.
--
	--Per Bothner
per@bothner.com   http://per.bothner.com/


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]