From: Larry Evans (cppljevans_at_[hidden])
Date: 2004-02-29 07:50:34
On 02/28/2004 06:29 PM, Brian McNamara wrote:
> On Sat, Feb 28, 2004 at 09:38:26AM -0600, Larry Evans wrote:
>>OK, YAT (Yet Another Thing), the tree<B> virtual functions
>>must be able to treat their children in the tree as tree<B>
> Ok, now I think I understand what you want.
> As a result, an expression like "x+y" ends up being represented by a
> data structure that looks something like this:
> Expr tree TExpr tree
> + <----------------- .
> / \ / \
> / \ / \
> x_ y_ int int
> |\ |\_____________/_____/
> where the tree on the right contains only the "added data" as well as
> pointers to the corresponding nodes of the original tree.
YES! This is exactly what I want, expressed "most directly" AFAICT,
this looks like the homomorphism or isomorphism diagrams I vaguely
remember from category theory. The mostly horizonal lines represent
the data mappings and the mostly diagonaly lines represent the
function mappings. This much more clearly represents what I
However, this implementation has a disadvantage. For example, The
tree -> first isomorphism, implemented by the regexp_first_constructor
:: new_from_nilable, would have to create, for the regexp_tree_alt ->
regexp_first_alt mapping a list<regexp_first_top*> as superclass of
regexp_first_alt corresponding to the list<regexp_tree_top*>
superclass of regexp_tree_alt. This duplicates the list
overhead. OTOH, the way it's currently coded may be represented as:
Expr tree TExpr tree
+ <----------------> .
x_ y_ _int _int
|\ |\ /| /|
\ \___________/ /
where <---> represents two pointers, one the inverse of the other. At
first, it looks like the number of pointers added by the isomorphism
in the 2nd diagram exceeds that of the 1st (6 vs.5); however, the list
overhead, I think, would tip the balance in the other direction at the
cost, of course, of less speed for accessing the TExpr children. It's
a trade-off, which I'll have to think on some more.
Thanks for helping me clarify my thinking :) .
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk