Re: Re: lookup-table thoughts (was Re: matching multip

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