David Durand asserted that a grove" is just a new name for what everyone else in the world calls "parse tree", and others (Eliot Kimber, James Clark, Joe English) sought to nuance that characterization. . .
From email@example.com Sat Dec 28 23:23:14 1996 Date: Sun, 29 Dec 1996 12:16:52 +0700 To: firstname.lastname@example.org (David G. Durand) From: James Clark <email@example.com> Subject: Re: clink/ilink direction (Was: anchor awareness) Cc: firstname.lastname@example.org At 16:02 28/12/96 -0500, David G. Durand wrote: >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. Groves are directed graphs (not acyclic), but they can also be considered as trees. More precisely: - A subset of the edges are distinguished as representing "origin-to-subnode" relationships. If you delete all edges other than these, then the graph becomes a single tree. - A subset of the "origin-to-subnode" edges are distinguished as representing parent-child relationships. If you delete all edges other than these, then the graph becomes a set of disjoint trees: one of these trees is the normal ESIS-like element structure tree; each attribute assignment (name plus value) is also its own tree. James ---------------------------------------------- From email@example.com Sun Dec 29 21:25:35 1996 To: firstname.lastname@example.org Subject: Re: clink/ilink direction (Was: anchor awareness) Date: Sun, 29 Dec 1996 19:13:39 -0800 From: Joe English <email@example.com> firstname.lastname@example.org (David G. Durand) wrote: > W. Eliot Kimber: > >David G. Durand: > >> 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. [...] > > 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_)? Sort of. Groves are like trees in that every node with the exception of a unique root node has a single parent. However, nodes in a grove also have a collection of named properties, whose values can be either "plain data" or a list of references to other nodes. Nodal properties (those whose value is a list of nodes) are classified as either "subnode properties" or "reference node properties"; every node except for the root is a member of a subnode property of exactly one other node in the grove (i.e., its parent), but there are no restrictions on reference node properties. If you consider only the subnode properties, you have a tree; if you consider the reference node properties as well, you have a directed (possibly cyclic) graph. Further, non-leaf nodes have a single distinguished subnode property designated as the "content property"; if you consider only the content properties you get the "principal tree" of the grove. For example in the SGML grove plan, attribute nodes are subnodes of element nodes, but they are not part of the principal tree. > >3. Provides a standardized abstraction mechanism divorced from the > > implementation issues. > > Ah, kind of like a parse tree. In fact, exactly like. A grove is nothing like a parse tree in the sense of the term with which I am familiar (a representation of a derivation of a string of terminals with respect to a grammar); they're more like an abstract syntax tree (i.e., a representation of the information derived from the parse tree) augmented with cross-references between nodes. > My inclination agaist groves stems from: > 1. The complexity of groves (reflecting the complexity of full SGML parsin > g). The grove data structure taken by itself is really quite simple and elegant. The SGML property set is horrendously complex, but if you only consider the "important" parts (e.g., ESIS plus a few extra properties that got left out) groves are very useful. (Cost 2 uses a grove-like data structure for its internal representation, so I can attest to their utility.) --Joe English email@example.com