Tail Calls

From The Oxygene Language Wiki

This is a Language topic
Feel free to add your notes to this topic below.

From the May 2010 release onwards, support will be provided for tail calls. Tail calls are exit statements followed by a call to a function. When the option is enabled, it will, instead of calling the method, set the parameters and jump to the target method.

{$TAILCALL ON}

function TestTail(i: Integer): Integer;
begin
  if i > 10000000 then exit i;
  exit TestTail(i+1);
end;
{$TAILCALL OFF}
 
TestTail(0);

Calling the above function will not trigger a stack overflow, but instead act as a loop. This is a pattern often seen in functional programming languages.

Requirements for tail calls:

• Method result or lack thereof has to match exactly (no casts)
• var/out parameters are not allowed
• Must be prefixed by 'exit'; assigning to result does not emit tail calls
• Exit is not allowed from within try/finally or try/except

The default mode for tail calls is specified in the configuration properties of the project options (set to off unless explicitly checked). {$TAILCALL ON} can be used to turn it on, OFF to turn it off, and DEFAULT to set it back to the value specified in the project options.

Tail calls were added to make it easier to support writing solutions to math problems in Delphi Prism. This optimization is also often used by functional programming languages. The advantage of this is, that the recursive call gets transformed into a loop, thereby reducing the amount of stack space required for this operation.

{$TAILCALL ON}

method Factorial(x, acc: Decimal): Decimal;
begin
  if x <= 1 then exit acc;
  exit Factorial(x -1, acc * x);
end;


{$TAILCALL OFF}

method Factorial(x: Decimal): Decimal;
begin
  exit Factorial(x, 1);
end;
 

Factorial(20); 
// 20 * 19 * 18 * 17 * 16 * 15 * 14 * 13 * 12 * 
// 11 * 10 * 9 * 8 * 7 *6 * 5 * 4 * 3 * 2 * 1 = 2432902008176640000

Were you to write this without the use of tail calls, it would look like:

method Factorial2(x: Decimal): Decimal;
begin
  var acc: Decimal:= 1;
  loop begin
    if x <= 1 then exit acc;
    acc := acc * x;
    x := x -1;
  end;
end;

Tail calls are also supported between different methods.

See Also

• Exit (keyword)
• Understanding Tail Recursion

Area: Oxygene Language
Compiler version: Oxygene 5

Language Glossary — Keywords — Types — FAQ — How To