[stringtemplate-interest] Understanding template recursion

[John Snyders]

Hi Trevor,

recurse(x) ::= "<x><rest(x):recurse()>"

In this case on the first call x is the whole list so "abcd" is output. 
then it loops over the rest of x calling recurse with the x being the 
current item it. It is the same as recurse(x=it).
When I try this I get "abcdbcd"
For me this is behaving as you and I would expect. I don't know why it 
doesn't work for you. We may have different versions of ST.

recurse2(x) ::= "<x><recurse2(rest(x))>"

I think what might be happening here is infinite recursion. The typical 
pattern for recursion is to have a test for the case that is going to 
stop the recursion. You might intend something like this (I just happen 
to use $$ rather than <>)

recurse2(x) ::= "$x$ $if(x)$$recurse2(rest(x))$$endif$"

Sadly this does not do what I expect. The first time it should output 
"abcd" because x is items. Now it calls recurse2 with the rest of x 
which is [ b, c, d ] and that is what should be output next "bcd" Now it 
recurses again with [ c, d ] and should output "cd" and again resulting 
in "d" at which point rest is null and the if would be false. So the 
total output I expect is "abcd bcd cd d "

What I get is "abcd bcd "

The reason I believe has to do with how ST uses iterators. On the first 
recursive call to recurse2(rest(x)) rest(x) returns an iterator and not 
a new list that is a slice of the old list. Now on the recursive call x 
is an iterator and as soon as you use it once it is used up. The next 
recursive call rest(x) returns null because x was used up in $x$.

This is a very serious bug and I thought I had reported it before in 
some way but now I can't find it in the archives.
A very simple way to see this bug is with the following
useItTwice(x) ::= <<
once : $x;separator=", "$
twice: $x;separator=", "$
 >>
test() ::= <<
$useItTwice(items)$
$useItTwice(rest(items))$
 >>
With your definition of items calling
$useItTwice(items)$
$useItTwice(rest(items))$
it should print
once : a, b, c, d
twice: a, b, c, d
once : b, c, d
twice: b, c, d

but it prints
once : a, b, c, d
twice: a, b, c, d
once : b, c, d
twice:

Iterators should never be passed to templates. This bug will prevent you 
from doing anything interesting with recursive templates.

P.S. I went to umass Amherst back in the 80's.

-John

Trevor Strohman wrote:
> I'm having trouble understanding recursion in templates.
>
> Suppose I have a list called "items" that contains Strings: "a", "b",  
> "c", "d", and these two templates:
> recurse(x) ::= "<x><rest(x):recurse()>"
> recurse2(x) ::= "<x><recurse2(rest(x))>"
>
> I expect <recurse(items)> to become:
> 	abcdcdd
> and <recurse2(items)> to become:
> 	abcd
>
> However, <recurse(items)> becomes "abcd" and <recurse2(items)> throws  
> an Exception.  What am I misunderstanding?
>
> Also, I notice that functions first, last and rest don't seem to be  
> first-class citizens in the language.  These expressions throw  
> exceptions:
> 	<if(first(rest(items))>
> 	<first(items).isEnabled>
> This has been a problem for me this afternoon.  I feel like I must be  
> misunderstanding the right way to approach recursive template  
> invocation.
>
> Trevor
>
> _______________________________________________
> stringtemplate-interest mailing list
> stringtemplate-interest at antlr.org
> http://www.antlr.org:8080/mailman/listinfo/stringtemplate-interest
>
>