Well, simple to implement and useless optimization :)

After my previous post, "TreeView and Nonrecursion", I'd tried to ask the same topics in stackoverflow.com
(http://stackoverflow.com/questions/3630047/treeview-control-and-nonrecursion) and I got something new.

It is possible to recurse without using up the stack space. Optimizing compilers are able to accomplish certain types of recursion into efficient non-recursive loops, but the code has to be written into a tail recursion form.

Is there such a recursion optimization in FPC? If it is not enabled by default, how to enable it?

Hello FPC-Pascal,

Friday, September 3, 2010, 1:12:31 PM, you wrote:

BA> After my previous post, "TreeView and Nonrecursion", I'd tried to ask the same BA> topics in stackoverflow.com
BA> (http://stackoverflow.com/questions/3630047/treeview-control-and-nonrecursion) BA> and I got something new.
BA> It is possible to recurse without using up the stack space. Optimizing BA> compilers are able to accomplish certain types of recursion into efficient BA> non-recursive loops, but the code has to be written into a tail recursion form. BA> Is there such a recursion optimization in FPC? If it is not enabled by default, BA> how to enable it?

That kind of "optimization" to me only seems interesting in two possible situations, when calling functions is high costly or when there is a very limited stack amount (really, really small). From my point of view if you need more that 1MB of stack size I'm quite sure that you are doing something wrong, because around 65000 recursion levels looks not very good.

The recursion "optimization" is being done using regular RAM as a stack:

function Recursive(var a: integer): boolean;
begin
  if a=1000 then begin
    Result:=false;
    exit;
  end else begin
    inc(a);
    Result:=Recursive(a);
  end;
end;
Function Iterative(var a: integer): boolean;
var
  Stack: TStack;
  v: integer;
begin
  stack.Push(a);
  while true do begin
    v:=stack.pop;
    if v=1000 then begin
      Result:=true;
      a:=v;
      break;
    end else begin
      inc(v);
      Stack.push(v);
    end;
  end;
  stack.free;
end;

To me the first one looks more clear...

Thanks Jose, I agree with you. Since in my case I need less than 1MB of stack size, so there is no reason to use nonrecursive/iterative approach. Furthermore, recursion is more readable.

Thanks Jose for the code snippets. You introduce TStack that I'm not aware of.

First, just curious, have somebody here ever benchmark performance between native stack and regular RAM as a stack?

Second, does FPC understand "tail recursion"?

Hello FPC-Pascal,

Friday, September 3, 2010, 3:06:30 PM, you wrote:

BA> First, just curious, have somebody here ever benchmark performance between BA> native stack and regular RAM as a stack?

Stack is RAM, so the only difference is in the algorithm used.

Second, does FPC understand "tail recursion"?

Depends on version, do

fpc -i |grep -i tailrec

to find out more.

O Marco, I love you :-)

In our previous episode, Bihar Anwar said:

O Marco, I love you :-)

Better love Florian :-)

O.o

Ok... now I'm officially impressed.

Maybe it's time to reuse some of my OCaml knowledge from the 3rd term of my study :D

Regards,
Sven

On Sep 2010, at 20:32, José Mejuto wrote:

[ some stuff about recursion - at the bottom if you want to read it ]

This a misunderstanding of way recursion can be flattened into a loop. It's especially not useful because the transformed version still uses a stack, so it doesn't execute in constant space.

Consider the classic factorial function:

function fact ( i : integer ) : integer ;
begin
if i := 0 then
  fact := 1
else
  fact := i * fact ( i - 1 )
end ;

with initial call "fact ( <some-value> )"

For an actual parameter value "i" this requires O (i) space, because you need to create stack frame to hold the current value of "i" for use after calculating the value "factorial ( i - 1 )" and the return address of the calling routine, (which is actually the same in every stack frame except in the one created by the top-level call).

You can see this by writing a top-level-call and plugging in the definition until you hit the base-case:

fact ( 4 )
-> 4 * fact ( 3 )
-> 4 * ( 3 * fact ( 2 ) )
-> 4 * ( 3 * ( 2 * fact ( 1 ) ) )
-> 4 * ( 3 * ( 2 * ( 1 * fact ( 0 ) ) ) )
-> 4 * ( 3 * ( 2 * ( 1 * 1 ) ) )

None of the multiplications can be done until the final call of "fact", so all the values must be preserved until then.

Now consider this version:

function accfact ( f , i : integer ) ;
begin
if i = 0 then
  accfact := f
else
  accfact := accfact ( f * i , i - 1 )
end ;

with an initial call of "accfact ( 1 , <some-value> )"

This is the standard "accumulating parameter" technique. All the calculation is performed on the descent, no local variables need to be kept, and the return address can simply be the point following the top-level call. The new stackframe can overwrite the old one (or rather the new values for the actual parameters "f" and "i" can simply overwrite the old ones).

If you the previous trick of plugging the definition into a top-level call you immediately get:

accfact ( 1 , 4 )
-> accfact ( 1 * 4 , 3 )

and we can do the multiplication before making the recursive call. This is "tail recursion".

For trees it's a lot trickier to write the processing routines in this kind of tail-recursive form.

Suppose we have a data type "tree" that can be empty or hold a value (say an integer) plus two subtrees, either of which may of course be empty at any level. Without getting into the minutiae of data representation and pointer-twiddling, assume functions "value", "left" and "right" to return the value and the two subtrees respectively, and "isempty" to check if a tree is empty.

The obvious way to process all the integers in such a tree (perhaps by forming their sum) is:

function sum ( t : tree ) : integer ;
begin
if isempty ( t ) then
  sum := 0
else
  sum := value ( t ) + sum ( left ( t ) ) + sum ( right ( t ) )
end ;

For a tree with "n" nodes this executes in O (n) space.

The accumulating parameter version is a bit less intuitive than "accfact":

function accsum ( s : integer ; t : tree ) : integer ;
begin
if isempty ( t ) then
  accsum : = s
else
  accsum := accsum ( accsum ( s + value ( t ) , left ( t ) ) , right ( t ) )
end ;

with top-level call "accsum ( 0 , <some-tree> )"

Here we have double recursion, which for a tree of maximum depth "d" it can be executed in O (d) space. For a balanced tree of "n" nodes, this means O(log(n)) space, which is still a huge improvement on the original version.

The key to making this work invisibly is provide higher-order functions to hide the recursion. If necessary they can be hand-coded in assembler and the compiler need never do any optimisation.

i.e given a type "munge = function ( a , b : <some-type> ) : <some-type>"

we define:

function mungetree ( b : <some-type> ; m : munge ; t : <tree-containing-<some-type>-values> ) : <some-type> ;
begin
if isempty ( t ) then
  mungetree : = b
else
  mungetree := mungetree ( mungetree ( munge ( s , value ( t ) ) , left ( t ) ) , right ( t ) )
end ;

and depending on what <some-type> is, and the actual function we supply for "m" (with of course an appropriate base-case value for "b") we can traverse any tree in O(log(n)) space, irrespective of the type of values in the tree or the type of operation performed on them.

Or we could if Pascal had a proper polymorphic type system. But it ain't, it's too old-fashioned.

But it's nice to have.

In the lecture "Introduction of Computer Science 2" we had to learn functional programming with the programming language OCaml. There we used tail recursion a lot (and I always tried to write my functions in a tail recursive form) and it's nice to see/know that FPC can do that as well. :)

Btw: is this a CPU dependent optimization?

Regards,
Sven

Hello FPC-Pascal,

Saturday, September 4, 2010, 9:07:57 AM, you wrote:

RB> This a misunderstanding of way recursion can be flattened RB> into a loop. It's especially not useful because the transformed RB> version still uses a stack, so it doesn't execute in constant RB> space.

I know, but as far as I know it is the only way to get exactly the same functionality whichever the recursion function works (using a stack different than the default stack). If the recursion function is not the last function it can not be "optimized" in such way, moreover most of that "tail recursive" functions are easy to be rewritten as a while end loop.

Anyway I do not have any kind of degree in computer science or alike so I could be completly wrong :)

IIRC in the whole FPC source tree are two cases where this optimization is applied :)

Btw: is this a CPU dependent optimization?

No.