CVS difference for ai05s/ai05-0136-1.txt

Differences between 1.5 and version 1.6
Log of other versions for file ai05s/ai05-0136-1.txt

--- ai05s/ai05-0136-1.txt	2009/06/08 05:46:57	1.5
+++ ai05s/ai05-0136-1.txt	2009/06/09 05:27:09	1.6
@@ -3002,3 +3002,60 @@
+From: Randy Brukardt
+Date: Monday, June 8, 2009  1:07 PM
+[Answering some private mail from Matt:]
+> Well, I confess to not knowing what "bottom-up tree construction is" 
+> (unless we're talking about a B-tree).  I also assumed that Splice and 
+> Move would be appropriate mechanisms for moving trees and subtrees 
+> across tree containers.
+It's the way trees are constructed when using a bottom-up parser - first
+you create the leaves, then the operation connecting the leaves, and so on.
+I have difficulty even imagining another way to create a tree when parsing;
+too many years using LALR(1) parsers I guess. (I realize that grasping how
+bottom-up parsers work is really hard unless you've been using them in
+practice for a while -- I think that is why our compiler-construction course
+required using them.)
+> > (It seems silly to have to create a special object solely for the 
+> > purpose of making a copy of some nodes, especially bad in a bounded 
+> > container type, where it would cause an extra set of copying.)
+> Well, that's where we disagree -- creating a separate (tree) object to 
+> hold (sub)trees you intend to splice onto another tree is *exactly* 
+> what you want.
+It's way too expensive, especially for bounded forms. And it's not how you
+think of subtrees as you are creating them if done without using a container,
+why should they be different here? We're probably going to have to agree to
+disagree on this one.
+> Concern about efficiency of a bounded form is also misplaced. 
+>  It's better to optimize the design around the common case, which is 
+> an unbounded form.  We already accept that Move, Splice, etc is going 
+> to require a copy for other bounded forms, so I see no reason to treat 
+> a tree container any differently.
+For most (paying) Ada customers, the bounded form is the only one they'll
+be able to use. (Why do you think that we have so much pressure to define
+For lists, the use of Move and Splice are going to be very rare. I can't
+recall ever having tried to insert something into the middle of a normal list
+(priority queues are not a list!). Indeed, I think Splice is one of the
+operations that will commonly be ignored as people will consider it "exotic"
+and forget about it in favor of more familiar operations. (At least half
+of the operations in Ada.Strings.Unbounded qualify like that; I don't even
+try to use them because the effort to figure out whether one applies and how
+to call it if it does.) For a tree, however, pretty much the only operation
+that you are going to use (other than Insert) is a Splice_Subtree, since it
+is the only way to do any sort of tree construction or transformation. It
+is simply unacceptable to make tree construction impossibly expensive by
+forcing copying everything at every step.

Questions? Ask the ACAA Technical Agent