Re: [Texmacs-dev] Using STL

[David Allouche]

On Tuesday 14 May 2002 19:13, Joris van der Hoeven wrote:
> On Tue, 14 May 2002, David Allouche wrote:
> >
> > As I said previously, I need a sorted associative container, and
> > there is no such thing in your classes.
> >
> > A sorted associative container is an associative container like your
> > hashmap, but additionnaly it provides an ordering based on a
> > comparison on the key. I need this to implement VALUE assignations in
> > TMSL efficiently.
>
> Can you explain this a little bit more? I am willing to implement this,
> but I would like to know what is the exact specification and
> what you would like to do with it.

I am thinking of imlementing the TMSL enviroment as a linked list of 
tmsl_env objects. Each object can be either a VAL environment (the top 
level, and environments created by WITH and APPLY) or a ARG environment 
(created by EXPAND).

ASSIGN will affect the innermost environment defining the name being 
assigned to.

To implement assignation efficiently we need a notification system. I 
define an interface with an abstract method notify_assign (I might use a 
concrete interface later, but at the moment I consider it abstract). When 
a tmsl_rewriter depends on a val variable, it invokes the method
ttree tmsl_env::get_val_attach(string, val_observer*, path ip) of its 
environment with 'this' as a val_observer (we need an uncounted pointer 
here), and the inverse path of the rewriter in the rewriter structure as 
ip.

When a val variable is ASSIGN'd, the containing environment sends a 
notify assign to all relevant attached val_observers. The relevant 
attached observers are those which:

  - are attached to the same name in the same tmsl_env
  - are after the ASSIGN
  - are before the next ASSIGN

After and before are defined by postorder tree traversal to account for 
constructs of the type (assign "x" (+ "x" "1")).

ASSIGN location are defined as the inverse path of the 
tmsl_assign_rewriter in the rewriter structure.

To implement that notification system, I define a tmsl_val_observer_group 
class, which records for a given value name in a given tmsl_environment 
the attached val_observer's, their locations and the locations of the 
ASSIGN statements (also as inverse paths in the rewriter hierarchy).

There I need sorted containers to get:
  - the location of the following ASSIGN
  - all the tmsl_val_observer between the modified ASSIGN and the next one

ASSIGN locations can be stored in a simple sorted set, but observers must 
be stored in a sorted associative container whose key is the observer's 
inverse path.

Since rewriters are recomputed in postorder (by recursive descent) there 
is no notification at initial rewriting. Partial rewritings after 
document modification may be optimized by using assign_notify to mark 
rewriters are dirty and use commit to reprocess dirty rewriters.

> > > I also would like you to avoid using too many new templated classes
> > > in your program, because this hugely increases the size of the
> > > executable. So please use the existing classes, like tree,
> > > array<int>, hashmap<string,tree> etc. whenever possible.
> >
> > I do, but I am not willing to write a new one if the STL already has
> > what I need.
>
> So I will take care of that.

I do not see what benefit you can expect from using a roll-it-yourself 
implementation. It will not significantly reduce the code size, it may 
introduce new bugs (any amount of new code may introduce new bugs), and 
will most likely not perform better than STL code.

But if you insist on it, and do not ask me to write or debug it, ok.

> OK. Please remind my remark on using NEW_TREES + tree for ttree.
> This will allow you to concentrate of the really essential stuff:
> the rewriters.

I have already written ttree. But If you want, I may merge the code with 
tree.

By the way, I have one important question about ttrees:
should the value of the inverse path used in hash equality comparisons 
and hash computation?

We might need to do so to use hashmaps to implement a rewriting cache. I 
have not really thought that issue out at the moment, though. 

I have already figured out that we must not consider the shared tail 
structure; though I use it to reduce the quadratic(depth) complexity 
induced by inverse path traversal to linear(depth)-best-case and 
quadratic(depth)-worse-case.
-- 

                                  -- David --