Type problem... possible design problem

Type problem... possible design problem

[chris.danx]

Hi,

What is the solution to the following problem?  There are two types of 
object in a scene graph, those that may have children and those may not. 
     A leaf may not have children.

For various reasons, I need to preserve the methods of internal nodes 
(non leaves).  I thought about something like this

type childNode = LeafNode of sgLeaf | IntNode of sgInternal
and
class sgLeaf
   = object(self)

     method draw () = ()

   end
and
class sgInternal
   = object(self)

     method addChild (child : childNode) = ()

     method getChildren () = ...

     method draw () = ()
   end

but this isn't legal O'Caml.  The following also doesn't work.

type childNode =
     LeafNode of <draw:unit -> unit; ..>
   | IntNode  of <draw:unit -> unit; addChild: childNode -> unit; ..>


I've not programmed in O'Caml for a while and am not yet fully 
comfortable with ocamls object system anyway, so I may be being silly. 
Can anyone shed some light on a solution to this?

Basically I need to be able to call addChild, etc for internal nodes if 
they're not leaves so I need to remember whether the type contains only 
draw or it also contains addChild, etc.  It will be clients that call 
operations like addChild, getChildren, ...

Perhaps this is the wrong solution entirely.

Thanks,
Chris

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

[Matt Gushee]

chris.danx wrote:

> type childNode = LeafNode of sgLeaf | IntNode of sgInternal
> and
> class sgLeaf
   .... etc. ...

> I've not programmed in O'Caml for a while and am not yet fully 
> comfortable with ocamls object system anyway, so I may be being silly. 
> Can anyone shed some light on a solution to this?

This seems to me like a good case for class types. How about something like:

class type leafType =
   object
     method draw : unit -> unit
   end

class type ['a] internalType =
   object
     method addChild : 'a -> unit
     method getChildren : unit -> 'a list
     method draw : unit -> unit
   end

type childNode =
     LeafNode of leafType
   | IntNode of childNode internalType

Then, of course, you'll need to define concrete classes that fit the 
class type signatures and/or coerce objects to those types.

I'm not sure this is the most elegant solution, but it is at least 
syntactically valid, and seems to do what you want.

--
Matt Gushee
Englewood, CO, USA

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

[Jon Harrop]

On Saturday 18 December 2004 00:42, chris.danx wrote:
> What is the solution to the following problem?  There are two types of
> object in a scene graph, those that may have children and those may not.
>      A leaf may not have children.

Could you redefine this as "There is one type of node in a scenegraph, which 
has an arbitrary number of children"? Leaf nodes are then nodes with zero 
children.

> I've not programmed in O'Caml for a while and am not yet fully
> comfortable with ocamls object system anyway, so I may be being silly.
> Can anyone shed some light on a solution to this?

Why are you using OO? Can you do what you want with modules and variant types 
more easily?

Cheers,
Jon.

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

[chris.danx]

Jon Harrop wrote:
> On Saturday 18 December 2004 00:42, chris.danx wrote:
> 
>>What is the solution to the following problem?  There are two types of
>>object in a scene graph, those that may have children and those may not.
>>     A leaf may not have children.
> 
> 
> Could you redefine this as "There is one type of node in a scenegraph, which 
> has an arbitrary number of children"? Leaf nodes are then nodes with zero 
> children.

I could.  The problem was that I wanted to enforce that leaf nodes are 
the only renderable objects and internal nodes are for grouping and 
state changes - lights, transformations, etc.


>>I've not programmed in O'Caml for a while and am not yet fully
>>comfortable with ocamls object system anyway, so I may be being silly.
>>Can anyone shed some light on a solution to this?
> 
> Why are you using OO? Can you do what you want with modules and variant types 
> more easily?

I was using OO because I want to extend the nodes available.  I suppose 
I can use closures.

My concern with variants is sharing subgraphs in graphs, will they be 
shared or copied?

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

[Richard Jones]

[-- Attachment #1: Type: text/plain, Size: 938 bytes --]

On Sat, Dec 18, 2004 at 02:28:09PM +0000, chris.danx wrote:
> My concern with variants is sharing subgraphs in graphs, will they be 
> shared or copied?

A tree structure like this should be stored shared:

  type 'a tree = Leaf of 'a | Node of 'a tree list

You can prove this; for instance:

# let n = ref 1;;
val n : int ref = {contents = 1}
# let t = Leaf n;;  
val t : int ref tree = Leaf {contents = 1}
# let tree = Node [t; t];;
val tree : int ref tree = Node [Leaf {contents = 1}; Leaf {contents = 1}]
# n := 2;;
- : unit = ()
# tree;;
- : int ref tree = Node [Leaf {contents = 2}; Leaf {contents = 2}]

Rich.

-- 
Richard Jones.  http://www.annexia.org/  http://www.j-london.com/
>>>   http://www.team-notepad.com/ - collaboration tools for teams   <<<
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
http://subjectlink.com/ - Lesson plans and source material for teachers

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

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

[Jon Harrop]

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.

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

[chris.danx]

Richard Jones wrote:
> On Sat, Dec 18, 2004 at 02:28:09PM +0000, chris.danx wrote:
> 
>>My concern with variants is sharing subgraphs in graphs, will they be 
>>shared or copied?
> 
> A tree structure like this should be stored shared:
> 
>   type 'a tree = Leaf of 'a | Node of 'a tree list
> 
> You can prove this; for instance:
> 
> # let n = ref 1;;
> val n : int ref = {contents = 1}
> # let t = Leaf n;;  
> val t : int ref tree = Leaf {contents = 1}
> # let tree = Node [t; t];;
> val tree : int ref tree = Node [Leaf {contents = 1}; Leaf {contents = 1}]
> # n := 2;;
> - : unit = ()
> # tree;;
> - : int ref tree = Node [Leaf {contents = 2}; Leaf {contents = 2}]

Hmm... this looks like it shows two subtrees hold the same reference but 
it does not to me look like it proves the structure is shared, only that 
references work as expected.

Perhaps I can use

type 'a sceneGraph = Leaf of 'a | IntNode of 'a * 'a sceneGraph list | 
SharedNode of 'a sceneGraph ref

to achieve what I want.

Chris

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

[skaller]

On Sun, 2004-12-19 at 01:28, chris.danx wrote:

> My concern with variants is sharing subgraphs in graphs, will they be 
> shared or copied?

It is up to you. Consider:

match ex with
| `A a -> `A a 
| (`B b ) as x -> x
| x -> x

In the first case, you're making a new object, by executing
the constructor `A. In the second and third you're not.
In all cases, the constructor argument is shared.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net