xml-dev - Re: The Power of Groves: VRML Description

[Eliot Kimber <drmacro@drmacro.com>]

Len Bullard wrote:
 
> For anyone, not just Steven.  Here is a very condensed expression of
> basic VRML.
> How is it expressed as a grove?

I'll take a late-night shot [I had started to say "quick", but clearly
it will not be quick--VRML is too sophisticated for a quick response].

This is a bit long because I've provided a good bit of tutorial
information on the property set definition syntax and methodology,
rather than just presenting a fully-formed result without comment.

---------------------------------
INTRODUCTION AND PROBLEM OVERVIEW

The basic design approach is to make each VRML construct type a grove
node
type (unless the construct can be fully represented by a simple string
or integer value). Simple-valued VRML properties become node properties.
VRML
properties that relate nodes become node-valued properties (properties
whose values are node lists). Structured properties become node
properties (just as you would use XML subelements to represent
structured fields for interchange).

The only real difficulty is matching the specific data types of
simple-valued VRML fields to the built-in property datatypes for groves.
Because we were only worried about representing SGML documents when we
designed the grove mechanism, we didn't build in a full range of
primitive types; in particular, there is no direct way to represent real
numbers. You can get around this just by defining a string
representation for reals or any other data type, just as you would to
use XML to represent the data for interchange.

Also, groves are a static data representation abstraction, not an object
modeling language, so there's no direct way to model methods--methods
would be part of an implementation applied to the groves for a
particular
data type. In the VRML case, the VRML specification can simply mandate a
set of methods that any conforming implementation must provide and can
define those methods in terms of operations on grove nodes and their
properties (which is what it effectively already does in the event and
scripting parts).  This part of the specification would be prose, but it
can be precisely formal with respect to the underlying data model.

One difficulty with talking about using groves to represent "VRML" is
that
VRML is not one thing, it is in fact several distinct facilities that
together define a complete environment for delivering interactive 3-D
virtual worlds. It has a source representation (the VRML "file"),
an "in-memory" representation (the result of applying processing to the
original source (the transformation hierarchy) and (I presume) other
ancilary resultant data structures), an event model (an abstraction of
processing through time), and a scripting model. It also defines
standardized presentation and processing semantics. Of these components,
groves are only directly applicable to the source and "in-memory"
representations. The other parts are processing applied to the groves
(including the construction of new groves from old groves).  

I observe at the outset that VRML makes *exactly the same mistake* that
SGML and XML make in that it starts by defining a source representation
syntax and not an abstract data model of which the syntax is a
representation. This will make doing the grove definition more difficult
because we first have to intuit the appropriate abstract data model.
That is, we have to take the route: syntax --> abstract data model -->
grove. Because I am not one of the VRML designers, I have no confidence
that any data model I might infer is correct, complete, or accurate. But
I'll take my best shot. I appologize in advance to the VRML design team
for any corruption I may perpetrate during this exercise.

-----------------------------------------------
DEFINING A VRML GROVE DATA MODEL (PROPERTY SET)

The formal definition of a notation-specific grove data model is a
"property set", defined through a "property set definition document",
the DTD for which is
defined in ISO/IEC 10744. It could be in SGML or XML syntax, it doesn't
matter. 

A property set is a *data* model, not an *object* model (roughly
equivalent to a UML model that only defines types and attributes, but no
methods, actions, or behaviors). Remember that the primary purpose of
groves is to provide a static data view suitable for doing reliable
addressing and transformation.

The syntax of a property set definition is pretty straight forward. For
each node class you have a "classdef" (class definition) element, which
defines the name of the class and some other meta-characteristics of the
class. Classdef elements then contain zero or more "propdef" (property
definition) elements, which define the properties of the node. Classes
and properties can be organized into "modules" (not used in this
discussion). 

Each construct has three names:
  - RCS name (rcsnm) (reference concrete syntax name). The RCS name is
eight
characters or less. This primarily to enable the use of class names as
SGML IDs.
  - Application name (appnm). The application name is the name you would
typically use in APIs. It is one or more blank-delimited tokens.
Grove-to-language-specific API bindings define how the tokens are mapped
to language-specific names (e.g., space goes to underscore, initial
capitalization, etc.). The GroveMinder product uses initial caps in its
Python API, for example. 
  - Full name. A fully-spelled out name that might be useful in
documentation, user interfaces, and so on. 

Each subsequent name defaults to the previous one if unspecified. 

I will discuss the remaining grove constructs as I get to them.

To be complete we need two property sets, one for VRML source documents
and one for VRML node sets that result from applying VRML semantics to
the source documents (that is, the result of implementing the event
model and scripting facilitites). I do most of the source property set
in this discussion. This can be defined pretty much by walking through
the syntax productions for the VRML syntax.

In looking at the VRML syntax, I see two ways to map that to groves. One
would be to have a separate node type for each built-in node type
defined
in VRML. The other would be to have a generic "vrmlnode" node type and
treat built-in and user-defined node types the same except that built-in
node types would not have explicit prototype definitions. The former
would provide the effect of an "early bound" API for accessing VRML
data, the latter would provide a simpler property set specification (one
node type rather than 56 (55 built-in plus proto)). Since it's late,
I'll take the latter approach.

-----------------------------
VRML Source File Property Set

First we start the property set definition document:

<?xml version="1.0"?>
<!DOCTYPE propset [
 <!NOTATION vrml97 SYSTEM
"http://www.vrml.org/technicalinfo/specifications/vrml97/index.htm" >
]>
<propset nsd="vrml97">
<desc>nsd is the "notation specification document", that is, the
definition of the data content notation this property set provides a
view of. In this case, the notation is "vrml97", which is defined by the
VRML 97 spec at the above URL. The property set DTD provides facilities
for tying parts of the property set definition document to specific
clauses in the notation
specification document. I will ignore these for this discussion,
although you would want to use them if this was part of a standard
(after all, VRML 97 is an ISO standard with easy-to-identify clauses).

Len says:

&gt; By VRML97 specification, VRML is a node language where nodes have
&gt; fields.  VRML is rootless.  A sceneGraph is a collection of VRML
&gt; nodes.  NOTE:  sceneGraph is not a named property

A grove must always have a single root node. This reflects the fact that
all data collections must have some kind of container. When modeling
information that has no inherent root, you define a "synthetic" node
type that serves to simply collect the nodes in the set, e.g.:
</desc>

<classdef appnm="scene" conprop="nodes">
<desc>A collection of VRML nodes that define a single "scene". 
The "conprop" (content property) attribute names the property of the
node that contains the "content" of the node. That is, if you ask for a
node's content, you will get back the value of the property named by the
"conprop" attribute. E.g.,:

>>> Python V1.5
> scene = construct_VRML_grove("myworld.wrl")
> con = scene.content()  # Get the "content" property.
> if con == scene.nodes:
      print "True"
True
>
</desc>
 
<propdef appnm="nodes" 
  datatype="nodelist"
  noderel="subnode"
  ac="vrmlnode"
>
<desc>The set of node instances defined by the VRML file.

The attribute "datatype" says what the data type for the property is.
This is one of the grove-specific data types: node, nodelist, nmndlist
(named node list), enum, char, string, strlist, integer, intlist,
boolean, compname (component name), or cnmlist (component name list).
The types node, nodelist, and nmndlist are "nodal" types, that is,
properties of these types contain one or more nodes. The other types are
"simple" values or lists of simple values.

A named node list is a node list that establishes a name space over the
nodes in the list such that each node in the list has a unique "name".
For example, in the XML property set, the "elements" property is a list
of all the
elements in a document that have a unique ID value. The notion of named
node list is a key grove concept because it enable generic name-based
addressing. This is essentially identical to a Python dictionary or
Visual Basic collection.

A property that is used as "name property" can have a simple value (a
string or integer) or it can be a node property. That means you can use
nodes as indexes in name spaces (just as you can in Python
dictionaries).

Any property of a node may be used as the "name" property in a given
node list as long as all the nodes of that type within the node list
exhibit a unique value for that property. It is up to the grove
constructor to enforce this rule (if the underlying data parser doesn't
already enforce it).

The "ac" (allowed classes) attribute defines what node types are allowed
in the value of this property. In this case, the single type "vrmlnode"
(because we are doing the simple "late-bound" approach).

The "noderel" (node relationship) attribute says what type of
relationship the nodes in the property value have to the node that
exhibits the property. "Subnode" means that the nodes will be "subnodes"
of this node. The node-to-subnode relationships defie a strict tree
within the grove (which is, more generally, a directed, possibly cyclic,
graph).
</desc>
</propdef>

<propdef appnm="prototypes"
  datatype="nmndlist"
  noderel="subnode"
  ac="protodef"
  acnmprop="ndtypeid"
>
<desc>The set of prototype definitions defined in this document.

The "acnmprop" (allowed class name property) attribute says, for each
type listed in the "ac" attribute, which property is used as the "name"
property in this named node list. In this case, nodes of type "protodef"
(prototype definition) have a property called "ndtypeid" (node type ID),
that is their unique node type name within the VRML file (or node, I'm
not sure what the scoping rules for prototype names are).
</desc>
</propdef>

<propdef appnm="routes"
  datatype="nmndlist"
  noderel="subnode"
  ac="route"
  acnmprop="routeid"
>
<desc>The definition of route among the node instances.

This can also be a named node list because route nodes have a required
ID property in the VRML syntax spec.
</desc>
</propdef>

<propdef appnm="named vrmlnodes"
  datatype="nmndlist"
  noderel="irefnode"
  ac="vrmlnode"
  acnmprop="nodeid"
>
<desc>An index (name space) of those nodes that are defined with unique
node IDs (e.g.:

DEF node0001 cone {}

This property captures the fact that some VRML nodes may have names. The
node relationship of "irefnode" (internal reference) means that the
nodes in the list exist in some other subnode property (the "nodes"
property of the scene node type) in the same grove, such that the value
of this property is a list of internal pointers to nodes (internal to
this grove). The other node relationship option is "urefnode":
unrestricted reference, which allows grove-to-grove pointers.

This property allows you to easily look up nodes by name, e.g., using
the GroveMinder Python API:

scene = construct_VRML_grove("myfile.wrl")
node = scene.namedVrmlnodes["node0001"]

<desc>
</classdef>

<classdef rcsnm="protodef" appnm="prototype definition">
<desc>A node prototype definition node.</desc>

<propdef rcsnm="ndtypeid" appnm="node type id"
  datatype="string"
>
<desc>The name for the type defined by this prototype definition. 

Note that the fact that this property is the "name" property of a named
node list (the "prototypes" property of the "scene" node class) imposes
a uniqueness constraint. Because the prototypes property is also a
subnode property (and, as we'll see) is the only subnode property that
allows protodef nodes, all protodef nodes in the grove must be listed in
that property. Therefore, all protodef nodes in the grove must have a
unique value for their ndtypeid properties. [NOTE: after writing the
above I realized that nodes can themselves contain prototype
definitions, so the above is not in fact true (prototype nodes can be in
one of several subnode properties, at least if my assumption about name
scoping is correct).]
</desc>
</propdef>

[I won't bother to define the details of prototype definitions--you can
probably figure it out from here.]

</classdef>

<classdef rcsnm="vrmlnode" appnm="vrml node" conprop="children">
<desc>A generic ("late bound") VRML node.
</desc>

<propdef appnm="children"
  datatype="nodelist"
  ac="node"
  noderel="subnode"
>
<desc>The hierarchical children of the node. 

Note that VRML's hierarchy maps directly to the subnode/content
hierarchy of groves.
</desc>
</propdef>

<propdef appnm="fields" 
  datatype="nmndlist"
  ac="ndfield simpfld"
  noderel="subnode"
  acnmprop="fieldnm fieldnm"
>
<desc>The set of fields for the node.

Note that in this late-bound representation we cannot map VRML node
fields to grove node properties because we don't know what they might be
for a given node (because of prototypes). Each field will therefore be
represented by a "field" node.
</desc>
</propdef>

<propdef appnm="routes"
  datatype="nmndlist"
  noderel="subnode"
  ac="route"
  acnmprop="routeid"
>
<desc>The definition of routes defined within this node.
</desc>
</propdef>

<propdef appnm="prototypes"
  datatype="nmndlist"
  noderel="subnode"
  ac="protodef"
  acnmprop="ndtypeid"
>
<desc>The set of prototype definitions defined in this node</desc>
<note>I'm not sure what the scoping rules for prototype names are in
VRML.
Will assume the are node scoped, not document scoped, but I could be
wrong.
If they are document scoped, make this an irefnode property that points
to nodes in the prototypes property on scene.
</note>
</propdef>

<propdef appnm="in events"
  datatype="strlist"
>
<desc>List of input event type names that this node accepts.</desc>
<note>If full set of event types is defined in VRML spec, no need to
make nodes out of events or event definitions. If users can define event
types, then we'd need to define event definition and event instance
nodes.</note>
</desc>
</propdef>

<propdef appnm="out events"
  datatype="strlist"
>
<desc>List of output event type names that this node emits.</desc>
</desc>
</propdef>
<!-- NOTE: may need more properties here to be complete for VRML nodes
-->
</classdef>

<classdef rcsnm="ndfield" appnm="node field" conprop="value">
<desc>Represents a single field whose value is a node list</desc>

<propdef appnm="field id"
  datatype="string"
>
<desc>Unique ID for this field within the node instance</desc>
</propdef>

<propdef appnm="field type"
  datatype="string"
>
<desc>VRML or user-defined field type name</desc>
</propdef>

<propdef appnm="value"
  datatype="nodelist"
  noderel="irefnode"
  ac="node"
>
<desc>The set of nodes that are the field value.

Note the assumption that the nodes are in the same scene grove. If this
assumption is not valid, change irefnode to urefnode for noderel.
</desc>
</propdef>

<!-- route node type skipped due to lateness of the hour. -->

<!-- I'm skipping the script part of nodes. It should be pretty obvious
how you'd do it by now. -->

</classdef>

<!-- More stuff would be needed for completeness, but not much more. -->
</propset>

----------------------------
CONCLUSIONS AND FURTHER WORK

This gives you a flavor of how a VRML source file could be grovified. A
more satisfying property set would probably provide a grove node type
for each VRML built-in type.

As for the transformation hierarchy, it's either just the same node
classes in a different organization or its similar node types, maybe
with additional properties or some properties removed because they
aren't relevant outside of the source file context. I have run out of
energy this PM (now AM) to pursue that, but Len should have the idea by
now.

The application of the event and scripting model to the grove approach
is an interesting discussion but I will leave that for another night.
The short version is: in the abstract grove processing model, each time
the world changes, you construct new groves to reflect the new world (of
course, in a real implementation, you wouldn't literally reconstruct
every node of every affected grove). That is, each set of groves
reflects a snapshot of the world at some instant in time. Every time you
turn the time crank, you get a new snapshot.

Messages can be modeled as groves which are themselves the input to
processors that construct new groves as a result of interpreting the
message groves.

Cheers,

E.