[Texmacs-dev] Optimizing assignations in TMSL

[David Allouche]

On Wednesday 15 May 2002 18:37, Joris van der Hoeven wrote:
> I was rather thinking about another scheme, similar to the one used
> in "bridge", but better optimized:
>
> 1. To each node of tmsl_rewriter (the source tree) you associate
>
>    a) A patch which contains the *inverse* of the environment change
>       corresponding to rewriting the source tree.
>
>    b) A hashset which contains all environment variables
>       on which the rewriting depends (this has not been done in
>       the bridge structure, but it will optimize rewriting a lot).
>
> 2. This structure is well compatible with the tree-structure for
>    most primitives. For instance for a concatenation,
>    the inverse patch for the concatenation is the "simplified"
>    inverse composite of the patches of its children.
>    The environment variables on which the rewriting depends
>    is the union of those on which the children depend.
>
>    In other words, when making a local modification,
>    you will only need to descend in the tree-structure
>    at those places where a real change occurred.
>    This is linear in time.

I have hard time understanding what you actually mean. If you explicited 
what you do with these data structures it would be much clearer to me. 
Also, I  would like if you specify time complexity with its dependant 
parameter. When you say "linear in time", do you mean linear(depth), 
linear(tree size), linear(nodes to update) or still something else? 

I am not sure I understand what you want to do with the inverse 
patch. If I guess right, that is someting useful when you use another 
object to accumulate state while traversing the rewriter hierarchy, as 
with the typesetter in bridge. I am not comfortable with this concept, 
and unless I find a good reason not to, I will try to avoid it.

Moreover, I am afraid that your hashset based update system may be 
problematic for several reasons. One reason would be the increased scope 
of local changes. If the environment depences of a given node change, 
then the change must be propagated to all parent nodes. Also, when a 
VALUE or ARG is removed each parent node would have to examine all of its 
children to know wether its dependence set has changed. I keep thinking 
that an observer based system would be better.

You may resent me for not "comparing thoroughly" both approaches, but I 
hardly can do so unless I am sure of what is your approach. You could 
tell me to read the code of brigde and edit_env, but it is hard for me to 
make the difference between typesetting and style in that code. Moreover, 
the tmsl_rewriter is much less constrained (because it is independant of 
rewriting) so I always think that code may have been designed with 
constraints wich are no longer applicable.

Do not misinterpret me, I am not complaining. I am just trying to improve 
our communication. I have noticed we seem to have very different ways to 
think, and since we are talking of complicated and subtle problems, it is 
easy to misunderstand one another.
-- 

                                  -- David --