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

On 6/18/05, Andre Cusson <ac@xxxxxxxxxxxxx> wrote:
> Hi,
> 
> We seem to be on different planets.

  Definitely.

> 
> 
> >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.
> 
> I have no problem finding the paths between nodes, this is trivial, without
> assign.
> 
> It would be nice if instead you had a solution for the problem at stake,

No problem at stake has been defined; where is:

     - the source xml to be transformed.

     - the wanted properties of the transformation.

    - the wanted result

If in addition the problem is that a pure XSLT solution is
"inefficient", then the alleged more efficient solution must be
provided so that it would be possible to compare it to pure XSLT
solutions people will put forward.



> but I have not seen any.

I have not seen any problem defined as described above.


> 
> Maybe you do not understand, or maybe I was not clear enough.
> 
> But when you write:
>  > 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.
> I understand that you are accusing me of misinforming people

  Until now people have seen only some unsupported statements that a
problem exists.

>  and my feeling
> now is that you do not have a solution and you do not want anyone to know.


Andre,

I asked you more than once to provide a definition of the problem -- a
concrete source xml, the desired properties of the transformation and
the desired result; also the "efficient" solution which uses
saxon:assign.

You obviously are not able provide such problem definition that will
prove your claims.

Then it is logically to conclude that this problem simply does not exist.

It is high time to either stop the rhetoric or provide concrete
example of your claims.

I am deeply disappointed that what looked promising to provide a new
challenging problem turned out to be just words.

Anyway, if you ever really happen to have a definition of a problem
that you want to be solved in pure XSLT, I would be happy to give it a
try.


Thanks,
Dimitre


> 
> Fine, no problem.
> 
> Cheers,
> Andre
> 
> 
> 
> 
> 
> At 20:16 2005-06-17, you wrote:
> >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@xxxxxxxxxxxxx> 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@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_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
>