Re: [Caml-list] Extensible graphs

[Jon Harrop <jdh30@cam.ac.uk>]

First of all, thank you very much for taking the time to reply!

My context is a graphics library. Since posting, I have created a simple 
implementation of the extensible graph using the polymorphic approach. The 
graph is actually over three types ('a, 'b and 'c, for example ;-) and 
contains leaves, "loners" and groups. Leaves have no children and metadata of 
type 'a, loners have a single child and metadata of type 'b and groups 
contain a list of children and metadata of type 'c.

Currently, I am thinking that, in my particular application, it may be 
satisfactory to just have extensible "loners" and keep leaves and groups 
specialised. I am not yet sure though, so I'm keeping everything generic for 
now.

In order to maximise code reuse, I have factored out a number of algorithms: 
iter (equivalent to List.iter), map (almost equivalent to List.map) and apply 
(like "iter" but only applying the functions on a route through the graph 
specified by an "iterator"). I have implemented these algorithms such that 
they are given four functions which get applied to the leaves, loners, groups 
and elements within groups respectively. I have then created slightly more 
specialised versions of these functions such as "render" which transparently 
performs necessary graphics state changes whilst doing an "iter".

I am now in the process of writing code which uses this generic graph 
representation to create a graph with new types of "loner" characterised by 
different metadata and replacement functions, based upon the generic "iter", 
"map" and "apply". This new code is actually for an editor. It creates a new 
"loner" type for a font glyph and an example of a new function is 
"render_selected" which renders a suitable overlay for when the user has 
selected something.

The main, current ugliness with the code is the rather large types which it 
produces, e.g.:

    val generic_render :
	RenderData.t -> 
	  (RenderData.t -> ('leaf, 'loner, 'group) generic_node -> bool) ->
	    (RenderData.t -> 'leaf -> unit) ->
	      (RenderData.t -> 'loner -> (unit->unit) -> unit) ->
		(RenderData.t -> 'group -> (unit->unit) -> unit) ->
		  (RenderData.t -> int -> ('leaf, 'loner, 'group) generic_node -> 
(unit->unit) -> unit) ->
		    ('leaf, 'loner, 'group) generic_node -> unit

Although this is quite daunting, I haven't had _that_ many problems, but it 
can make bug hunting a little more interesting... ;)

On Wednesday 31 March 2004 10:11 am, Diego Olivier Fernandez Pons wrote:
> Bonjour,

Bonjour!

> I have read a few of your web pages and you seem to be an "imperative
> programmer" more used to languages such as C++ or Java rather than
> functional ones like ML or Haskell.

I certainly am, although I was taught a little ML in my first year as an 
undergrad, so I know a tiny bit of basic theory.

> What do you mean by "new node types" ?

I wish to supply a basic graph type which can contain, say (pedagogical 
example), two types of node which represent triangles and squares 
respectively, but I want a user to be able to create a new graph type which 
also includes pentagon nodes. Obviously, I want them to be able to reuse the 
existing code as efficiently as possible.

> If the "node type" requires specific accessors (i.e. if it is a
> module) then you should try functorial graphs.

What do you mean by a "specific accessor"? Do you mean the equivalent of a 
member function required for a class by an abstract base class?

If so then yes, I do, but I also want the set of required functions to be 
extensible (e.g. the addition of "render_selected" in my editor). I believe 
this requirement makes object orientation (ocaml classes?) unsuitable.

> You will find an example of functorial graph library in OCamlGraph
> (see the Hump, data structures section) even if in this case it is the
> whole graph data structure which is abstracted from the (functorial)
> graph algorithms.

Just reading about it, this may be a good way to reduce the size of those 
types. I could encapsulate a generic graph in a functor which is defined over 
the functions which the generic functions such as "iter" apply as they go. 
The only problem is that, I think, the user is likely to want to create 
several different specialisations of "iter", each of which applies a 
different set of functions for the leaves, groups etc., in which case this 
won't work.

What about just encapsulating the iter function itself in a functor, rather 
than the type of the whole graph?

> > type leaf = A | B | C
> > type node =
> >
> >     | Leaf of leaf
> >     | FunkyGroup of node list
> >     | Group of node list
>
> In the example you give, the "node" is not a node of the graph but
> a node of the underlying tree that represents the graph : are you
> really sure you need that ?

I think I see what you mean. Is this not fixed by my now using:

type ('a, 'b, 'c) node =
  Leaf of 'a
| Loner of 'b * node
| Group of 'c * node list

This may be a confusion caused by my using the word "graph" to refer to what 
is commonly known as the "scene graph" in graphics which is, in this case, 
just a tree. There are some cool things which could potentially be done by 
using a scene graph which is not just a tree but I won't go into these now.

> The main problem here is the pattern-matching since the predefined
> functions (like count_leaves) based on it do not work any more.

Ok, I think that is fixed by my implementation which just ignores the metadata 
if it is only after leaf-/group-ness.

> Possible work-around are :
>
> i) pattern-matching simulation via functors

Ok.

> ii) polymorphic variants
>
> In the previous case, the problem was "inside a constructor"
>   N (l, v, r) against N (l, v, r, _)
>
> If you only need to add patterns, then polymorphic variants could be
> what you are looking for. The Caml manual gives a few examples of the
> use of variants.

Ok, I'll check that out too, thanks.

[Objects]
> you use the object layer to downcast to a common subtype.

Which makes adding new node types easy, but I couldn't figure out how to add 
new member functions. I tried multiple inheritance (with an extra ABC) but 
couldn't get it to work.

> > Is factoring out as much code as possible the best I can do, or is
> > there a better way to approach this problem ?
>
> It would be easier if you gave us a more detailled example. Anyway, in
> my opinion you should first try simple solutions (polymorphic data
> structures).

I hope my more detailed explanation has clarified some points.

Cheers,
Jon.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners