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

Hi Andre,

> On the other hand, I am surprised that the information provided and the
> problem description is not sufficient yet, that is more then I had when I
> figured it out in the first place.

The information provided is not at all convincing that a pure XSLT
solution does not exist or that an XSLT solution will be significantly
less efficient than one using saxon:assign.


Be informed that there exist pure XSLT solutions to the problem of
finding a path between two nodes of a multigraph -- I have my own
solutions and wouldn't be surprised if other people have developed
theirs.

I would be glad to demonstrate such a solution on a sample graph,
provided by anyone interested.

> Re-designing and re-writing the code
> will not be trivial and if you want to do it we could always try to workout
> agreements, but there is no money.

I am not interested in being hired to work on this or in getting money.

What I just want is that people are not misinformed about the alleged
impossibility (or inefficiency) of solving this problem in a pure
functional (without modification of values of variables) way.

Unfortunately, from this thread until now it seems that you cannot
stand up to the challenge and provide a concrete example of the
problem that would support your statements.


Thanks,
Dimitre

On 6/18/05, Andre Cusson <ac-ncSKzJSyWVNl57MIdRCFDg@xxxxxxxxxxxxxxxx> wrote:
> Hi Dimitre,
> 
> Our application has over 25K lines of XSLT, apart from the Java code
> working with it.  There are about 15 man/years of development from
> experienced developers with an average of over 20 years experience each, in
> the field.  By the way every one of them dislikes assign but all agree that
> it is the best available solution.  Re-designing and re-writing the code
> will not be trivial and if you want to do it we could always try to workout
> agreements, but there is no money.
> 
> If our code and design are "wrong" because they are based on assign and if,
> as I understand it, an assign-based design is what you are trying to avoid,
> our code implementing our (faulty) design is probably not the best place to
> start.
> 
> On the other hand, I am surprised that the information provided and the
> problem description is not sufficient yet, that is more then I had when I
> figured it out in the first place.  Also, if XSLT has the proper constructs
> for this, it should be easy to work out an acceptable solution, shouldn't
> it ?  Isn't there a design pattern for avoiding circular references in a
> circular net in a high-performance Web context ?
> 
> My feeling is that, rather than trying to patch the current design, the
> best thing to do is to start back from the specs and work out a design
> approach that meets the requirements and does not use assign.
> 
> I tried to provide the specs and requirements and I would be happy to
> provide further support there, as well as to try to work out an alternate
> solution with whoever is interested.
> 
> If we come-up with a better solution, we will undertake retro-fitting it to
> our application but if no one can provide a better solution, please allow
> me to believe that XSLT would be lacking without assign.
> 
> Thank you.
> 
> Cheers,
> Andre
> 
> 
> 
> 
> 
> At 17:30 2005-06-17, you wrote:
> >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-ncSKzJSyWVNl57MIdRCFDg@xxxxxxxxxxxxxxxx> 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-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_idt77&alloc_id492&op=click