RE: Template recursion, StackOverflowError, saxon:while a nd variable assignability

Hi Ed  and Dimitre,

Each node in the network is really a tree, as each "database model" record 
is itself a document.
The network is not usually a complete network but could be and two adjacent 
nodes can have multiple arcs between them.

The "database" contents change constantly, based on update requests, 
sometimes fast, sometime slow.
Not all requests are for update but in any case (ie. read or read/write), 
the network analysis has to be performed as inside and outside conditions 
can change.

Triggered by a request passing it request parameter nodeset specifying the 
required processing conditions, source, targets, etc., used throughout the 
traversal, the analysis currently does a single pass forward traversal of 
the required paths without any back axis access.  Also, a node is never 
processed twice.

Currently, as the traversal progresses nothing is changed in the network 
but some information is accumulated in a variable, using assign, and the 
traversal process further refers to this variable as it 
progresses.  Currently the "analysis" model variable is a single string and 
referral to it uses regular expressions.

Replacing the "analysis" string variable, with a dynamically evolving key() 
may work, It would probably be larger, more elaborate, and possibly slower, 
but the key() structure would also have to be assignable ...

As for Dimitre's quoted solution, it is interesting, and granted, it does 
not get tangled in a loop, but the sample graph used has no loops and it 
only has a single arc between adjacent nodes.  But the main issues here are 
related to performance and memory as the network has to be traversed 
multiple times (ex: building the key structure) and the keys would have to 
hold all the nodes in the "database" and many of them multiple 
times.  Then, the whole structure has to be processed recursively and nodes 
have to be copied again.  My feeling is that we are orders of magnitude 
slower than the current solution and memory is going to burst.  Also, if 
the request is read-only, and most requests are, we have copied most of the 
nodes for nothing.

We need to improve performance, not slow it down, as it can never be fast 
enough.  Same with memory usage. And here, we are still talking of a 
simplified problem.

For now at least, I maintain that assign is indispensable to the problem 
solution and that since this problem should be relatively common and that 
there is bound to be more like this, that XSLT would be lacking without 
assign, implying that assign should be considered as a standard "extension" 
and complement to the language.  Yet, I think that assign should be avoided 
and used exclusively when it is by far the best approach to solving a problem.

This reminds me a lot of the goto statement in a language like Pascal: 
counter-architectural but indispensable for processing recursive structures 
without using recursion, for example, in cases where the level of recursion 
would burst the memory/stack

We have been working on this for a while, about 3 decades for me, and I 
would be very happy to find or learn a better solution, but it has to be 
both: better and a solution, before we can drop the old.

Thank you for your interest and consideration.
Regards,
Andre



At 05:07 2005-06-17, you wrote:
> Hi Andre
>
> Am I right in saying your problem _could_ be equivalent to the following
>
> You have two input models.
>         - your large database model
>         - your problem goal
> You perform a side-effect free analysis to compute
>         - a goal-specific change request model
> The change request model then controls an update of the database model?
>
> This is typical of many graph analysis problems, and it is often
> convenient for a non-side-effect free analysis to leave marks
> and other temporaries within the source database model. This avoids
> any allocation/location issues for the working memory.
>
> Analysis
> --------
>
> A possible solution within XSLT is to maintain the marks in an
> analysis model that accompanies and references the database model.
> You are then dependent on efficient key() functionality to
> navigate randomly from database model to analysis model.
> Separating the read-only and read-write functionality will have
> considerable advantages in resolving re-entrancy issues.
>
> A possible extension to XSLT might be to support a form of
> node extension, so that each output document node could comprise
> the 'copied' input node plus the appended working extension. This
> could avoid the performance limitations of key().
>
> Update
> ------
>
> The controlled update of the large model in response to a change
> request model is a straightforward challenge for Michael and other
> XSLT compiler implementers. The compiler should recognise that,
> subject to minimal constraints, an in-place update can be performed.
>
> Perhaps XSLT could have a keyword that indicates that this is the
> programmers intent, so that the compiler can explain why the intent
> is not fulfilled.
>
>         Regards
>
>                 Ed Willink
>
> > -----Original Message-----
> > From: Andre Cusson [mailto:ac-ncSKzJSyWVNl57MIdRCFDg@xxxxxxxxxxxxxxxx]
> > Sent: 17 June 2005 06:40
> > To: saxon-help-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@xxxxxxxxxxxxxxxx
> > Subject: Re: [saxon] Template recursion, StackOverflowError,
> > saxon:while
> > a nd variable assignability
> >
> >
> > Hi Dimitre,
> >
> > The graph is a (generic) capacity network (multi-digraph) and
> > one of the
> > tasks, for example, is to follow every path between node A
> > and node B,
> > weighting the arcs and processing, while not getting tangled
> > in a loop,
> > very quickly, very often, on possibly huge graphs, all in XSLT.  No
> > (significant) heuristics are currently used, only plain
> > crunching, and
> > saxon:assign.  Of course, as paths are traversed and
> > processed, some may be
> > found to be uninteresting at the time and further processing
> > of that path
> > is skipped, for now.
> >
> > How would you do it in XSLT, without using saxon:assign ?
> >
> > Thank you,
> > Andre
> >
> >
> >
> > It happens that I already have this done :o)  -- more than an year ago
> > >I implemented in XSLT some generic graph (multigraph) operations like
> > >Eulerisation and the street sweeper / NY postman algorithm.
> > >
> > >
> > >Of course, full graph traversal is NP-complete (regardless if assign
> > >is used or not), so with deep graphs one would inevitably try some
> > >euristics.
> > >
> > >
> > >Cheers,
> > >Dimitre Novatchev.
> >
> >
> >
> > At 00:28 2005-06-17, you wrote:
> > On 6/17/05, Andre Cusson <ac-ncSKzJSyWVNl57MIdRCFDg@xxxxxxxxxxxxxxxx> wrote:
> >  > Hi,
> >  >
> >  > Simple?
> >  > How would you avoid getting stuck in a circular loop while
> > processing a
> >  > general directional graph with XSLT, without using assign ?
> >  >
> >  > Thank you
> >  > Andre
> >
> >
> >
> > > >
> > > >
> > > > At 23:31 2005-06-16, you wrote:
> > > > >So how about an (simple, please) example?
> > > > >
> > > > >Maybe someone will come up with comparable efficient
> > solution without
> > > > >using saxon:assign?
> > > > >
> > > > >
> > > > >Cheers,
> > > > >Dimitre Novatchev
> > > > >
> > > > >On 6/17/05, Andre Cusson <ac-ncSKzJSyWVNl57MIdRCFDg@xxxxxxxxxxxxxxxx> 
> wrote:
> > > > > > Hi,
> > > > > >
> > > > > > Definitely a graph and one of the issues is dealing
> > with circular
> > > > > > references, in a strained performance environment.
> > > > > > It has been working fine for a few years already and
> > uses assign.
> > > > > >
> > > > > > Andre
> > > > > >
> > > > > >
> > > > > >
> > > > > > At 11:40 2005-06-16, you wrote:
> > > > > > >Hi Andre
> > > > > > >
> > > > > > >...
> > > > > > > > by a graph processing
> > > > > > >...
> > > > > > >
> > > > > > >Do you really mean graph or tree?
> > > > > > >
> > > > > > >For a tree-structured problem one can envisage a very simple
> > > transform,
> > > > > > >that declaratively takes in the entire data-base
> > plus a change request
> > > > > > >and returns the updated database. If the change
> > request applies
> > > > > > >to some low level branches, then multiple changes
> > can be safely
> > > > > > >executed in parallel on multiple processors. The
> > XSLT compiler
> > > > > > >needs to recognise the tunneling down to the
> > branches idiom to
> > > > > > >identify that the transform has a very controlled
> > change domain
> > > > > > >within which an assign rather than copy can be performed.
> > > > > > >
> > > > > > >It then 'just' requires the XSLT compiler to manage
> > the on-demand
> > > > > > >re-distribution of data nodes to processors, so that
> > you run one
> > > > > > >massively parallel XSLT session rather than one per process.
> > > > > > >
> > > > > > >If your problem is really a graph, then there must
> > be significant
> > > > > > >issues with determining the extent of the change, and more
> > > significantly
> > > > > > >ensuring that the concurrent execution of 'assign'-optimised
> > > transforms
> > > > > > >is deterministic. I don't think that XSLT as it
> > stands, will allow
> > > for the
> > > > > > >real life indeterminism that you currently have. You
> > don't mind which
> > > > > > >record is updated first, just so long as the updates
> > are consistent.
> > > > > > >But achieving this consistency probably means that
> > you already have
> > > > > > >a policy that constrains the potential graph
> > anarchy, and this could
> > > > > > >be exploited by XSLT to do what you do manually.
> > > > > > >
> > > > > > >         Regards
> > > > > > >
> > > > > > >                 Ed Willink
> > > > > > >
> > > > > > >
> > > > > > >-------------------------------------------------------
> > > > > > >SF.Net email is sponsored by: Discover Easy Linux
> > Migration Strategies
> > > > > > >from IBM. Find simple to follow Roadmaps,
> > straightforward articles,
> > > > > > >informative Webcasts and more! Get everything you
> > need to get up to
> > > > > > >speed, fast.
> > http://ads.osdn.com/?ad_id=7477&alloc_id=16492&op=click
> > > > > > >_______________________________________________
> > > > > > >saxon-help mailing list
> > > > > > >saxon-help-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@xxxxxxxxxxxxxxxx
> > > > > > >https://lists.sourceforge.net/lists/listinfo/saxon-help
> > > > > >
> > > > > >
> > > > > >
> > > > > > -------------------------------------------------------
> > > > > > SF.Net email is sponsored by: Discover Easy Linux
> > Migration Strategies
> > > > > > from IBM. Find simple to follow Roadmaps,
> > straightforward articles,
> > > > > > informative Webcasts and more! Get everything you
> > need to get up to
> > > > > > speed, fast.
> > http://ads.osdn.com/?ad_id=7477&alloc_id=16492&op=click
> > > > > > _______________________________________________
> > > > > > saxon-help mailing list
> > > > > > saxon-help-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@xxxxxxxxxxxxxxxx
> > > > > > https://lists.sourceforge.net/lists/listinfo/saxon-help
> > > > > >
> > > > >
> > > > >
> > > > >-------------------------------------------------------
> > > > >SF.Net email is sponsored by: Discover Easy Linux
> > Migration Strategies
> > > > >from IBM. Find simple to follow Roadmaps,
> > straightforward articles,
> > > > >informative Webcasts and more! Get everything you need
> > to get up to
> > > > >speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&opÌk
> > > > >_______________________________________________
> > > > >saxon-help mailing list
> > > > >saxon-help-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@xxxxxxxxxxxxxxxx
> > > > >https://lists.sourceforge.net/lists/listinfo/saxon-help
> > > >
> > > >
> > > >
> > > > -------------------------------------------------------
> > > > SF.Net email is sponsored by: Discover Easy Linux
> > Migration Strategies
> > > > from IBM. Find simple to follow Roadmaps, straightforward
> > articles,
> > > > informative Webcasts and more! Get everything you need to
> > get up to
> > > > speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&opclick
> > > > _______________________________________________
> > > > saxon-help mailing list
> > > > saxon-help-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@xxxxxxxxxxxxxxxx
> > > > https://lists.sourceforge.net/lists/listinfo/saxon-help
> > > >
> > >
> > >
> > >-------------------------------------------------------
> > >SF.Net email is sponsored by: Discover Easy Linux Migration
> > Strategies
> > >from IBM. Find simple to follow Roadmaps, straightforward articles,
> > >informative Webcasts and more! Get everything you need to get up to
> > >speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&opÌk
> > >_______________________________________________
> > >saxon-help mailing list
> > >saxon-help-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@xxxxxxxxxxxxxxxx
> > >https://lists.sourceforge.net/lists/listinfo/saxon-help
> >
> >
> >
> > -------------------------------------------------------
> > SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
> > from IBM. Find simple to follow Roadmaps, straightforward articles,
> > informative Webcasts and more! Get everything you need to get up to
> > speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&op=click
> > _______________________________________________
> > saxon-help mailing list
> > saxon-help-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@xxxxxxxxxxxxxxxx
> > https://lists.sourceforge.net/lists/listinfo/saxon-help
> >
>
>
> -------------------------------------------------------
> SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
> from IBM. Find simple to follow Roadmaps, straightforward articles,
> informative Webcasts and more! Get everything you need to get up to
> speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&opÌk
> _______________________________________________
> saxon-help mailing list
> saxon-help-5NWGOfrQmneRv+LV9MX5uipxlwaOVQ5f@xxxxxxxxxxxxxxxx
> https://lists.sourceforge.net/lists/listinfo/saxon-help



-------------------------------------------------------
SF.Net email is sponsored by: Discover Easy Linux Migration Strategies
from IBM. Find simple to follow Roadmaps, straightforward articles,
informative Webcasts and more! Get everything you need to get up to
speed, fast. http://ads.osdn.com/?ad_idt77&alloc_id492&op=click