[antlr-interest] On trees and JavaBeans, part 2: tree creation

[Loring Craymer]

Scott--

Take a step back and do a closer analysis.  You're missing the point.

> -----Original Message-----
> From: Scott Stanchfield [mailto:scott at javadude.com]
> Sent: Tuesday, April 19, 2005 8:09 PM
> To: 'Loring Craymer'; antlr-interest at antlr.org
> Subject: RE: [antlr-interest] On trees and JavaBeans, part 2: tree
> creation
> 
> First, I don't know if you realize that the Carrier model you propose is
> *exactly* what TreeNodes are in Swing.

Not true.  Data objects are not accessible from TreeNodes; instead data
objects must implement the TreeNode interface.  You have to typecast a
TreeNode before you can get at the associated data.

It is because of this simple difference that all of the navigation
capabilities you want can be provided at essentially no cost.

> 
> Swing allows you to do exactly what you're saying, *but* gives the option
> of
> replacing the entire tree model yourself. This is TreeModel.
> 
> As usual, *I'm asking for an option* and getting shot down because y'all
> don't happen to need it in the little boxes you're living in. Think
> bigger!

Wrong!  You've got your blinders on and are chasing windmills as a result.
Complexity for complexity's sake is not good design.  The Carrier/Payload
model provides all of the capability that you are campaigning for.

> 
> (Give me the *option* of not having to type the damned parens for + and
> *!!!!!!!!!!!)
> 
> I'll write up an example so you can really see it in a few mins...
> 
> 
> > Separating data and navigation interfaces is key to
> > supporting any sort of transformation--to transform, you need
> > to rewrap a data package with navigation information.
> 
> This is *exactly* what the ASTModel I'm proposing does.
> 
> Think about it this way

Been there; done that.  You are worrying many of the right issues, but you
are arguing for an alternative access model, not improved capabilities.

> 1) We have some "tree data". The data can be in *any* tree form you like,
> but we'll assume there are no cycles to avoid that argument for now
> 
> 2) We want to parse the data using an antlr tree parser
> 
> 3) Antlr needs to determine
>    a) the token type of a node
>    b) the children of a node
>    Note that Antlr really doesn't need to know the *class* of the
>    node as long as it can get this data.
> 
> 4) We provide a mapping layer between Antlr and the data that interprets
> Antlr's requests by looking at the real tree data and returning it.
> 
> 5) Suppose antlr needs to create or modify nodes
> 
> 6) we provide another mapping layer that interprets antlrs requests
> (create,
> add/remove kids) by manipulating the real data
> 
> Perfect separation. Only ONE extra object needed to do the job instead of
> n
> extra objects.
> 
> With a big tree, the overhead of carriers is significant.


You are still missing the point of having a payload interface.  Payloads
will normally persist through a complete transformation sequence, and should
almost limit object creation/destruction to Carriers during transformation
passes.  That means that they save on garbage collection overhead for
heterogeneous trees, at least, and reduce the cost of copying data from one
pass to the next to setting a reference.  The only case where carriers add
overhead is where you have a single pass for tree construction.

 

> 
> > Swing's JTree is mis-designed because the navigation class
> > (JTree.DynamicUtilTreeNode) is referenced from the data
> > container, not the other way around.
> 
> Huh? Which Swing are you talking about? What do you mean by "navigation
> referenced from the data container"? It's not. The navigation data
> (TreeModel) is separate from the data, and is only called from the Jtree
> (the presentation). The real data doesn't call the tree model.

No.  The data container implements TreeNode; TreeModel just provides an
access model which hides that ugly fact.

> 
> 
> Swing has a brilliant design for the tree that gives great model
> separation
> from the UI.
> 
> JTree
>   |  calls
>   |
>   V
> TreeModel
>   |  calls
>   |
>   V
> Your real data

Which implements the TreeNode interface ...

> Think of TreeModel as a controller for the actual data, which is the real
> model. All access to the data from the UI goes through the tree model. The
> real data doesn't (and shouldn't) even know the TreeModel exists.
> 

Yes, there is a complex access structure just because the navigation
interface is bound to the data.  Despite that, there is a point for having
TreeModels--they provide a place to attach and detach listeners to the tree.

> 
> > There are two navigation
> > paradigms:  you can either use a Cursor object to navigate
> > (in which case, the options are assigning an object to the
> > cursor, moving the cursor to one of the siblings or children
> > of the assigned object, returning a sibling/child of the
> > assigned object, or adding a child/sibling) or a Carrier.
> 
> You're thinking in a box and missing a better option. The ASTModel option
> is
> a complete separation of cursor and navigation.
> Take the Jtree example.
> 
> Jtree asks the TreeModel for the root node, and holds that root node. This
> is the "current node", or cursor.
> 
> Jtree renders the current node
> 
> Jtree asks the TreeModel to tell it the # of children, and asks for each
> in
> turn. As it asks for each, they are the cursor. It renders them.
> 
> This is a really flexible and less expensive solution.

No--it is a solution that provides the required complexity for the problem
that it solves.  At the lowest level, TreeNodes are quite analogous to ASTs
and have all of the associated warts.  TreeNodes, however, tend to be
persistent, while AST nodes have to be copied during each transformation
pass.  ANTLR trees have different associated costs than Swing trees.

> 
> > [example snipped]
> > That may look like a lot of overhead to create Carriers
> > willy-nilly, but in practice it probably is not--the creation
> > and destruction of Carriers is just a recycling which the
> > garbage collector will do as efficiently as one can do
> > manually or nearly so--when walking, Carriers are the only
> > dynamic element.
> 
> The trouble is there are extra objects to collect. More objects == more

You miss the point.  There is less manipulation of data pointers with
Payloads implemented as objects distinct from Carriers when doing
significant manipulations.  Objects created and destroyed are homogeneous,
which places less stress on the garbage collector resulting in faster
creation times and fewer compactions.  And, for platforms that do not have
efficient garbage collectors, releasing Carriers back to a CarrierFactory is
possible.

> frequent/longer collection == slower app. In the ASTModel example, there

Not if the garbage collector is reasonably well optimized.  Take a look back
at the recent posts on ASTPair recycling in C# and you'll see what I mean.

> is
> *one* ASTModel.

... and many ASTNodes, which makes it necessary to copy data fields during
tree transformations, and that costs in terms of performance.  You cannot
avoid costs associated with navigation; however, you can minimize the cost
of maintaining AST data across transformation passes.

For that matter, you can allow ASTs which implement both the Carrier and
Payload interfaces for single pass language processors.  Don't confuse
interfaces with classes--logical and physical structures can be quite
different.

--Loring

> > Really, it is all just a matter of which access pattern you
> > are using, and the key abstraction is to separate out data
> > from navigation.
> 
> Later,
> -- Scott
> 
> 
>