Subject: Re: [xsl] Re: lookup-table thoughts (was Re: matching multiple times, outputting once? From: Tom Myers <tommy@xxxxxxxxxxxxxx> Date: Wed, 07 Nov 2001 11:08:01 -0500 |
I'd said > >... I'm thinking of a functional-programming pattern > > > > accum(f,[],base) = base > > accum(f,[hd]+tail,base) = f(hd,accum(f,tail,base)); > > > > (the sum of a sequence S is accum(add,S,0); the product is > > accum(multiply,S,1); ... and Jeni T. replied with >The one "problem" with this template (and the same was true of Mike's >and Dimitre's) is that it's not tail recursive... And the exposition following was indeed instructive (yes, I have your book on order) but I'm not convinced of the tail-recursion point itself; the trouble is that the "f" in this accum is a constructor. Consider... hmm....I'll switch syntax a bit, consider a range function R such that R(1,5) = [1,2,3,4,5] which I compute via R(L,H) = if(L > H) then [] else cons(L,R(L+1,H)); or else via the tail-recursive accumulator usage R(L,H) = Ra(L,H,[]); Ra(L,H,S) = if(L > H) then S else Ra(L,H-1,cons(H,S)); And similarly I want a SumRange function SR such that SR(1,5) = 1+2+3+4+5 which I compute via SR(L,H) = if(L > H) then 0 else L+SR(L+1,H); or else via the tail-recursive accumulator usage SR(L,H) = SRa(L,H,0); SRa(L,H,A) = if(L > H) then A else SRa(L,H-1,H+A); I think I claim that this is pretty close to the way you're making my "accum" (or Mike's or Dimitre's) tail-recursive, yes? And I also claim that making SR tail-recursive has the properties you claim (it makes an O(N) time, O(N) space problem into an O(N) time, O(1) space problem if you compile it with GCC, for example; I didn't know Saxon did tail-recursion until last week, and haven't tried that). Effectively the generated code concludes with "Call SR; RET;" and this is equiv to "Goto SR". (Should I expand on that, or allude to continuation-passing? Nahh...) However, I think making R tail-recursive is a success only if the "cons" is constant-time. In your response, you wrote > <xsl:with-param name="base"> > <xsl:element name="{$hdvalue}"> > <xsl:copy-of select="$base" /> > </xsl:element> > </xsl:with-param> and if copy-of actually makes a copy, taking O(N) time and space, I think you've actually replaced an O(N)time, O(N) stack, O(N) max space, O(N) total space construction with one using, umm, umm, O(N^2) time, O(1) stack, O(N) max space, O(N^2) total space. Do you see why I'm thinking that? <xsl:copy-of select="$base" />, as $base grows, takes more and more time (and space). btw, My "total space" vs. "max space" assumes that the previous copy is then garbage-collectible. Granted, the space issue may win if the stack-space limit is distinct from, and less than, the max space limit (experiment suggests that this is true in Xalan), but the time definitely doesn't...unless the processor avoids unnecessary copies, and does a "copy-of" in constant time and space. Does it? Is copy-of a misnomer, in which case I've misunderstood the way result-tree formation is supposed to go? Or could it use refcounts to notice that only one copy is requested and that it already has that one, so use a pointer instead? I should perhaps mention that my original R =...cons(L,R(L+1,H)), like the "accum" template I was trying to generalize from, is "tail-recursive modulo cons"; there was a paper of that (approx) title by (approx) Friedman & Wise in the (approx) late 70s, pointing out essentially that it is perfectly possible, indeed straightforward in a graph-reduction engine, to get tree output without stacking the top of the tree to wait for the bottom. For them the point was that this was the way to generate lazy infinite lists, but if Saxon does tail-recursion modulo cons then I think that I think that the accumulation I proposed would not accumulate stack space; nor would Mike or Dimitre's. Mike, if you've read this far...comments? Dimitre, Haskell does that, doesn't it? It's been so long since I read anything about Haskell...I am going to respond to Dimitre's post, which I found extremely thought-provoking, but meanwhile I need to do some JDBC, SAX, and DOM. sigh. Tom Myers XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: [xsl] reliability of MSXML, Michael Kay | Thread | Re: [xsl] Re: lookup-table thoughts, Jeni Tennison |
Re: [xsl] Re: Re: Re: lookup-table , Dimitre Novatchev | Date | Re: [xsl] IE6 xml direct browsing, Michael Beddow |
Month |