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

Andre,

> 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.  


This will remain an unconfirmed statement (therefore, most probably
false) unless an example is provided -- a sample source xml document
and the solution that uses saxon:assign. Then people may be able to
provide a pure XSLT solution and compare the two solutions.


Cheers,
Dimitre Novatchev


On 6/18/05, Andre Cusson <ac@xxxxxxxxxxxxx> wrote:
> 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@xxxxxxxxxxxxx]
> > > Sent: 17 June 2005 06:40
> > > To: saxon-help@xxxxxxxxxxxxxxxxxxxxx
> > > 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@xxxxxxxxxxxxx> 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@xxxxxxxxxxxxx> 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@xxxxxxxxxxxxxxxxxxxxx
> > > > > > > >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@xxxxxxxxxxxxxxxxxxxxx
> > > > > > > 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@xxxxxxxxxxxxxxxxxxxxx
> > > > > >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@xxxxxxxxxxxxxxxxxxxxx
> > > > > 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@xxxxxxxxxxxxxxxxxxxxx
> > > >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@xxxxxxxxxxxxxxxxxxxxx
> > > 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@xxxxxxxxxxxxxxxxxxxxx
> >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@xxxxxxxxxxxxxxxxxxxxx
> https://lists.sourceforge.net/lists/listinfo/saxon-help
>
HS^�隊X���'���u����(���j̋�{�2(+jب�+kjנ������b��"��^����Z0F����l��ڊm~��j�Z�؜��"��+��b���mƬ�Ƨvj+xg�z����b�
��w�v� z۩��)y�_j�a����l��gr��i؝