W3C home > Mailing lists > Public > w3c-sgml-wg@w3.org > December 1996

Re: clink/ilink direction (Was: anchor awareness)

From: David G. Durand <dgd@cs.bu.edu>
Date: Sat, 28 Dec 1996 16:02:48 -0500
Message-Id: <v02130501aeeb34b7d695@[]>
To: w3c-sgml-wg@www10.w3.org
At 4:11 PM 12/27/96, W. Eliot Kimber wrote:
>At 05:04 PM 12/27/96 -0500, David G. Durand wrote:
>>    A "grove" is just a new name for what everyone else in the world calls
>>a "parse tree".
>Not exactly correct: groves are a new name for what everyone else in the
>world calls a direct graph data structure.  It happens that one obvious
>application of directed graphs is the representation of parse trees, but
>that's not the only thing groves are used for.  Groves are useful because
>the provide the following features on top of the basic directed graph of
>nodes concept:

trees are directed graphs. Are you saying that groves can include cyles of
nodes (ie node that are their own ancestors), or multiple inheritance
(directed _acyclic graphs_)? If not, groves are part of that subset of
directed graphs known as trees, and you are spreading more smoke into the
air, instead of shedding light on the issues.

>1. Optimization for the representation of parsed SGML documents and things
>   more or less like SGML documents.

viz, trees.

>2. A clear and convenient semantic distinction between "content" nodes and
>   other nodes (thus the notion that a single grove contains multiple
>   distinct "content trees", thus "grove").

Rooted forest? (just interested in mapping HyTime's creative terms into
standard math/CS terminology) Actually this sentence means very little to
me, except that it seems to reflect the fact that SGML processors need
access to so-called "insignificant" information, so that we need to label
all nodes with a significant/insignificant flag.

>3. Provides a standardized abstraction mechanism divorced from the
>   implementation issues.

Ah, kind of like a parse tree. In fact, exactly like.

>Thus, in the XML discussion, groves are useful because they are more
>complete than ESIS for discussing processing the results of parsing and
>they provide a common, implementation-independent data structure for
>discussing location addressing.

ESIS is certainly incomplete. I assume that this refers to point 2 (more
complete than ESIS). And implementation independence just means that there
is a defined data model.

>We can't do either coherently without some sort of common abstraction.
>Groves exist. Ergo, why not use groves in our discussions?

My inclination agaist groves stems from:
   1. The complexity of groves (reflecting the complexity of full SGML parsing).
   2. The unique terminology of HyTime, which does not correspond with
standard terms for standard entities.
   3. The fact that I have not yet seen anything in XML that would not fit
usefully in a standard parse tree model, so I fail to see the avantage of
adopting a new, relatively-unknown, highly-complex solution to a simple

>Now we could avoid parse trees by using byte offsets, but
>>given that addressing bytes in markup does not usually make sense, we will
>>need to have the parse tree anyway -- that's what structural addressing is
>>founded on. As far as I can tell, the details of groves are irrelevant to
>>XML, unless we decide that we have to explain how XML linking can be
>>treated as HyTime linking.
>I don't think they're irrelevant because I don't think you can discuss
>location addressing in an open environment without something like groves.
>We had to invent groves to solve exactly that problem in trying to
>rationalize DSSSL and HyTime.  XML will have the same problem and will need
>the same solution.

XML will need parse trees (probably the same as groves, unless you give me
unexpected answers to my queries).Groves are (over?)-designed to accomodate
the many complexities of SGML parsing that XML has eliminated. This means
that the details of groves are probably not all that relevant. We may need
look to them for inspiration, and possibly compatibility, but I doubt we
will need to look deeper, unless we have to hack the grove notion for
compatibility with the linking semantics of XML as thoroughly as we hacked
SGML for compatibility with the syntax of XML).

   -- David

I am not a number. I am an undefined character.
David Durand              dgd@cs.bu.edu  \  david@dynamicDiagrams.com
Boston University Computer Science        \  Sr. Analyst
http://www.cs.bu.edu/students/grads/dgd/   \  Dynamic Diagrams
--------------------------------------------\  http://dynamicDiagrams.com/
MAPA: mapping for the WWW                    \__________________________
Received on Saturday, 28 December 1996 15:57:56 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:25:21 UTC