Re: [Caml-list] Type problem... possible design problem

[Jon Harrop <jon@jdh30.plus.com>]

Ah yes, it's coming back to me now. I asked about this on the mailing list 
almost a year ago because I didn't understand it then. I don't completely 
understand it now but I can tell you what I learned. :-)

My original scenegraph implementation was written without objects. I wanted to 
be able to extend the functionality without touching the original code so I 
converted the whole thing to using objects instead. Basically, I found that 
neither approach solves all of the problems and I ended up converting the 
code back to non-OO because I decided this was the better of the two.

There are two ways you'll want to extend the functionality provided by your 
scenegraph library:

1. Add new types of node (e.g. a "glyph leaf node" to represent a character).
2. Add new functions which act over scenegraphs or node (e.g. a 
"render_selected" function for a graphical editor).

If you choose OO then you can easily create a new node class type which 
inherits from the base node class type. However, I couldn't figure out how to 
define new functions which act over arbitrary node types as the necessary 
functionality was rarely provided by the objects' interface, requiring me to 
create a whole new bunch of objects each time I needed a new function.

If you choose non-OO then you can add new node constructors by reusing the old 
constructors but you'll have to add a little extra code to every new function 
which resorts to the equivalent existing function.

I defined the type of a node in the scene graph to be the variant type over 
the types of metadata held in leaves ('a), loners ('b) and groups ('c) (a 
loner is a node with one child, such as a transformation):

type ('a, 'b, 'c) generic_node =
    GenericLeaf of 'a
  | GenericLoner of 'b * ('a, 'b, 'c) generic_node
  | GenericGroup of 'c * ('a, 'b, 'c) generic_node list

You can reuse this definition when adding new node types by supplementing the 
variant type used as 'a, 'b or 'c with an extra constructor. Your new 
function can then call the old function for the old contructor(s), thus 
reusing the old code.

For example, I've then done:

type basic_leaf =
    ContourObject of ContourObject.t

type basic_loner =
    Transform of mat
  | Text of string * string

type basic_group =
    Group of Bound.t cache

type basic_node = (basic_leaf,
     basic_loner,
     basic_group) generic_node

So basic_node is now a simple scenegraph which implements contour objects at 
the leaves, transforms and text as loners, and groups. A type of scenegraph 
which implements additional stuff (which I've done for the vector graphics 
editor) can either be defined similarly to the above (copying most of the 
code) or by referring back to the code above (which requires the same amount 
of code in this case and is less readable).

However, functions which traverse the scenegraph can now be written 
straightforwardly.

Of course, this looks like a tree and not a graph. I chose to implement the 
graphness by using "thin" metadata in the above variant types. In order to 
reuse a subgraph, the metadata contains a reference to a reference to a 
scenegraph, which can then be shared between nodes in the root scenegraph. 
This satisfies my design criteria but may not satisfy yours.

In summary, I decided that users will not be adding layer upon layer of new 
node types and, consequently, the benefits associated with using variant 
types over OO outweighed the costs.

I'd like to know if polymorphic variants would offer an improvement because 
they might be able to let you extend the variant type and resort to 
previously defined functions for the previously defined subset of the 
polymorphic variant's constructors. I can't see how they can but I've got a 
paper on extensible programming using polymorphic variants by someone 
(Jacques, no doubt ;-) which I have yet to absorb.

As OCaml is a functional language, data tends to be magically shared (see 
"referential transparency") so you don't need to worry about this as long as 
you build each subgraph once and place it in two different parts of the 
scenegraph, it will be shared and not copied. Just don't build it twice.

I'm very interested to hear what people have to say about this...

HTH.

Cheers,
Jon.