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

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=click