Recent

Author Topic: Tail recursion vs tail call elimination  (Read 652 times)

raoul

  • New member
  • *
  • Posts: 5
Tail recursion vs tail call elimination
« on: August 20, 2022, 12:08:48 pm »
Hi,

I'm writing an interpreter. The docs mention that tail recursion is available in free pascal. Is tail call elimination also done? i.e. if the last statement in a function calls another function through a function pointer, is this optimized to a jump?

I'm asking because this would make free pascal suitable for direct threaded interpreters without resorting to trampolining (slow) or assembly (non portable).

I am in the process of writing a test for that using mutually recursive functions, but I wondered if someone had more info?

Thx!

MarkMLl

  • Hero Member
  • *****
  • Posts: 5598
Re: Tail recursion vs tail call elimination
« Reply #1 on: August 20, 2022, 12:33:05 pm »
Welcome to the forum, interesting project :-)

I'd strongly recommend testing it, irrespective of development tool... and always retesting it as part of your build procedure.

Subject to any comments from @PascalDragon and the other core developers, I have reservations as to the extent that any transfer of control can be reliably optimised through a function pointer unless that is explicitly marked as being a constant, i.e. resolved at link time and subsequently immutable.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 10404
  • FPC developer.
Re: Tail recursion vs tail call elimination
« Reply #2 on: August 20, 2022, 01:05:02 pm »
There is an optimization switch (from https://www.freepascal.org/docs-html/prog/progsu58.html):

Quote from: 'from docs"
TAILREC
    change tail recursion to regular while

raoul

  • New member
  • *
  • Posts: 5
Re: Tail recursion vs tail call elimination
« Reply #3 on: August 20, 2022, 01:37:17 pm »
There is an optimization switch (from https://www.freepascal.org/docs-html/prog/progsu58.html):

Quote from: 'from docs"
TAILREC
    change tail recursion to regular while

Thanks, yes I am aware of the switch. My question boils down to whether this optimization is only for self recursion (caller & callee are the same function) or is also done in the general case (caller & callee are different functions) ?
« Last Edit: August 20, 2022, 01:39:20 pm by raoul »

raoul

  • New member
  • *
  • Posts: 5
Re: Tail recursion vs tail call elimination
« Reply #4 on: August 20, 2022, 03:42:30 pm »
Well, apparently tail call elimination is not done in the general case, barring changes since then. Close, but no cigar! I'll have to find some other way to make my interpreter fast. [: very sad emoji]

Then you should try to compile that code with the optimization. Because this is a tail recursion. The question is if the compiler detects this over two functions

No, it won't. The optimization only handles calls to the same routine.

However, for me TAILREC does not seem to kick in even in the trivial case. The following program still triggers a stack overflow exception (for all conditions -O0 to -O3, even when adding -Ootailrec). Can someone tell me why? Am I using compiler directives wrong? (Linux Debian testing ; Lazarus 2.2.0+dfsg1-6 ; Free Pascal Compiler version 3.2.2+dfsg-11 [2022/05/26] for x86_64)

Code: Pascal  [Select][+][-]
  1. program tailrec;
  2.  
  3. {$mode ObjFPC}{$H+}{$OPTIMIZATION TAILREC}
  4.  
  5. uses sysutils;
  6.  
  7. function Recursive(var Level : NativeUInt) : NativeUInt;
  8. begin
  9.   Level := Level + 1;
  10.   Result := Recursive(Level)
  11. end;
  12.  
  13. var
  14.   i: NativeUInt;
  15.   k: NativeUInt;
  16.  
  17. begin
  18.   i := 0;
  19.   try
  20.     k := Recursive(i);
  21.     WriteLn('Should never be executed, infinite loop.');
  22.   except
  23.      on E: EStackOverflow do
  24.        WriteLn('Stack overflow; recursion frame: ' + IntToStr(i));
  25.   end;
  26. end.
  27.  
« Last Edit: August 20, 2022, 04:16:40 pm by raoul »

MarkMLl

  • Hero Member
  • *****
  • Posts: 5598
Re: Tail recursion vs tail call elimination
« Reply #5 on: August 20, 2022, 04:06:22 pm »
Try doing it without that parameter or result. The parameter is probably being passed on the stack, hence the eventual crash.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

raoul

  • New member
  • *
  • Posts: 5
Re: Tail recursion vs tail call elimination
« Reply #6 on: August 20, 2022, 04:14:58 pm »
Try doing it without that parameter or result. The parameter is probably being passed on the stack, hence the eventual crash.

MarkMLl

Indeed, this was the cause of the crash. Thanks!

MarkMLl

  • Hero Member
  • *****
  • Posts: 5598
Re: Tail recursion vs tail call elimination
« Reply #7 on: August 20, 2022, 06:19:01 pm »
It might be that the problem is the var parameter. If it were a pointer (possibly a const pointer) it might be passed in a register.

However I really feel that at this point you ought to be inspecting the assembler code that the compiler's generating.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

PascalDragon

  • Hero Member
  • *****
  • Posts: 4765
  • Compiler Developer
Re: Tail recursion vs tail call elimination
« Reply #8 on: August 20, 2022, 11:18:10 pm »
There is an optimization switch (from https://www.freepascal.org/docs-html/prog/progsu58.html):

Quote from: 'from docs"
TAILREC
    change tail recursion to regular while

Thanks, yes I am aware of the switch. My question boils down to whether this optimization is only for self recursion (caller & callee are the same function) or is also done in the general case (caller & callee are different functions) ?

This is only for self recursion.

It might be that the problem is the var parameter. If it were a pointer (possibly a const pointer) it might be passed in a register.

In main var-parameters are supported as well, at least as long as they aren't copyback parameters (which might be the case on the Aarch64 ABI depending on the type).

However I really feel that at this point you ought to be inspecting the assembler code that the compiler's generating.

It's indeed always best to check whether the compiler indeed replaces the call by a jump, especially when one relies on the tail recursion.

raoul

  • New member
  • *
  • Posts: 5
Re: Tail recursion vs tail call elimination
« Reply #9 on: August 21, 2022, 02:14:28 am »
Thanks for chiming in!
May I ask if support for tail calls is expected to be expanded in the future (i.e. full tail call elimination) ?

PascalDragon

  • Hero Member
  • *****
  • Posts: 4765
  • Compiler Developer
Re: Tail recursion vs tail call elimination
« Reply #10 on: August 21, 2022, 04:25:01 pm »
May I ask if support for tail calls is expected to be expanded in the future (i.e. full tail call elimination) ?

No one is working on this and as far as I know no one is even interested in this. If you want this you need to implement it yourself.

 

TinyPortal © 2005-2018