[stringtemplate-interest] Understanding template recursion

[Terence Parr]

On May 24, 2007, at 9:11 AM, Trevor Strohman wrote:

>
>>> I do understand why recurse(x) works the way it does, now.  Terrence
>>> has this version:
>>> 	recurse(x) ::= "<x><rest(x):recurse()>"
>>> on a presentation slide about recursion, although it's really just a
>>> single level of recursion, not tail recursion (which I was  
>>> expecting).
>>
>> Hi gang. that is tail recursion isn't it?  rest(x) will get smaller
>> and smaller until it's null i nwhich case recurse() won't be applied
>> again.
>
> Here's how I understand the evaluation:
> 	Step 1: output <x>
> 	Step 2: evaluate <rest(x):recurse()>
> 		2a: recurse evaluated with x[1] as the argument
> 		2b: recurse evaluated with x[2] as the argument
> 		2c: recurse evaluated with x[3] as the argument...

rest returns all but the first element.  So it return 1..3, 2..3, 3

> That doesn't seem like tail recursion to me, since the stack depth  
> seems like it's two no matter how long x is.

well, it's recursive and on the tail. ;)  It does matter how long it  
is, btw, right?

That IF below is redundant.

Ter
> Contrast with:
>
> recurse2(x) ::= "<if(x)><x><recurse2(rest(x))><endif>"
> 	Step 1: output <x>
> 	Step 2: evaluate "<recurse2(rest(x))>"
> 		Step 2a: output <x[1:]>   (using Python array notation)
> 		Step 2b: evaluate "<recurse2(x[2:])>"
> 			Step 3a: output <x[2:]>
> 			Step 3b: evaluate "<recurse2(x[3:])>"
> 				...
>
>