Re: [fpc-pascal] fpc isn't optimised for tail recursion, is it?
Le 12/06/2023 à 19:05, Steve Litt via fpc-pascal a écrit : Busted! I used Pascal 1984-1993 So I guess you are not familiar too with the "Result" variable which appeared with Delphi 1 in 1995 if I remember correctly. nextt:= num; can be written to as : Result:= num; https://www.freepascal.org/docs-html/ref/refse94.html I prefer Result because it reduces risks of confusion with recursive call and you can eventually take the address of Result with @Result (where @nextt would take the address of the function nextt), pass it by reference to another function ( e.g. FillChar( Result, SizeOf(Result), 0); ) , it behaves like a normal variable.___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] fpc isn't optimised for tail recursion, is it?
Steve,
If you're looking for equivalent to "return X", use "Exit" with a
parameter in Pascal: "Exit(X)".
It's just a shortcut for "Result := X; Exit;"
Regards,
Michalis
pon., 12 cze 2023 o 19:57 Steve Litt via fpc-pascal
napisał(a):
>
> Nikolay Nikolov via fpc-pascal said on Mon, 12 Jun 2023 09:15:17 +0300
>
> >On 6/12/23 04:44, Steve Litt via fpc-pascal wrote:
>
> [snip]
>
> >> So, subject to your guidance, I'm assuming FPC isn't optimized for
> >> tail recursion. Is my assumption an accurate one?
> >
> >FPC supports tail recursion optimization, it is enabled at -O2
> >optimization level for most CPUs, however your code isn't eligible for
> >that optimization, because there's extra code, after the recursive
> >invoke. If you change it like that:
> >
> >program recursion_hello;
> >
> >function nextt(num: int64): int64;
> >begin
> >writeln('Going deeper=> ', num);
> >nextt := num;
> >if (num > 0) then
> > begin
> > nextt(num - 1);
> > end;
> >end;
> >
> >begin
> > nextt(10);
> >end.
> >
> >And if you compile with -O2 it works, without segfaulting (tested with
> >FPC 3.2.2 on x86_64-linux).
>
> Thanks Nickolay,
>
> You're right about not assigning nextt below the call to nextt, and
> about the -O2 argument. After learning from you about -O2 and
> investigating further, I used {$OPTIMIZE tailrec}, which isn't quite the
> same thing, but it worked beautifully. {$OPTIMIZE on} also enables tail
> recursion and speeds things up about 10% of tailrec.
>
> Thanks for your help.
>
> SteveT
>
> Steve Litt
> Autumn 2022 featured book: Thriving in Tough Times
> http://www.troubleshooters.com/bookstore/thrive.htm
> ___
> fpc-pascal maillist - fpc-pascal@lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
___
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] fpc isn't optimised for tail recursion, is it?
Nikolay Nikolov via fpc-pascal said on Mon, 12 Jun 2023 09:15:17 +0300
>On 6/12/23 04:44, Steve Litt via fpc-pascal wrote:
[snip]
>> So, subject to your guidance, I'm assuming FPC isn't optimized for
>> tail recursion. Is my assumption an accurate one?
>
>FPC supports tail recursion optimization, it is enabled at -O2
>optimization level for most CPUs, however your code isn't eligible for
>that optimization, because there's extra code, after the recursive
>invoke. If you change it like that:
>
>program recursion_hello;
>
>function nextt(num: int64): int64;
> begin
> writeln('Going deeper=> ', num);
> nextt := num;
> if (num > 0) then
> begin
> nextt(num - 1);
> end;
> end;
>
>begin
> nextt(10);
>end.
>
>And if you compile with -O2 it works, without segfaulting (tested with
>FPC 3.2.2 on x86_64-linux).
Thanks Nickolay,
You're right about not assigning nextt below the call to nextt, and
about the -O2 argument. After learning from you about -O2 and
investigating further, I used {$OPTIMIZE tailrec}, which isn't quite the
same thing, but it worked beautifully. {$OPTIMIZE on} also enables tail
recursion and speeds things up about 10% of tailrec.
Thanks for your help.
SteveT
Steve Litt
Autumn 2022 featured book: Thriving in Tough Times
http://www.troubleshooters.com/bookstore/thrive.htm
___
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] fpc isn't optimised for tail recursion, is it?
Marco van de Voort via fpc-pascal said on Mon, 12 Jun 2023 09:12:22 +0200 >On 12-6-2023 08:15, Nikolay Nikolov via fpc-pascal wrote: > >Shouldn't the recursive call assign the result? > >> nextt(num - 1); > > >nextt:=nextt(num - 1); > > >if you don't use the result, the whole call may be optimized away? Thanks Marco, You're right, of course. I'm not using my function return. That being said, as far as I know, FPC can't optimize for tail recursion if I do use the function return in any way. So I didn't use the function return. Of course, you bring up a point of cleanness and style. If I don't use the function return, I should have made it a procedure instead of a function. Anyway, I learned from my forays into Guile that I don't yet have a good mental model of functional programming, hence my confusion. Thanks, SteveT Steve Litt Autumn 2022 featured book: Thriving in Tough Times http://www.troubleshooters.com/bookstore/thrive.htm ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] fpc isn't optimised for tail recursion, is it?
Jean SUZINEAU via fpc-pascal said on Mon, 12 Jun 2023 18:04:07 +0200 >According to you other posts, I won't be surprised that you think in a >C/C++ way. :-) Busted! I used Pascal 1984-1993, and C 1986-present with C++ (hate it) 1990-1998. So I long ago forgot the details of pascal, and program pretty much every language with a C accent. >This doesn't change anything in your last example, but particularly : > >nextt := num; > >doesn't behave like in C : > >return num; Busted again. I was thinking that nextt := num not only defined the return value, but actually executed the return. Because that's how the return statement works in C. I now know (remember actually) that the assignment doesn't trigger the return. Thanks, SteveT ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] fpc isn't optimised for tail recursion, is it?
According to you other posts, I won't be surprised that you think in a C/C++ way. This doesn't change anything in your last example, but particularly : nextt := num; doesn't behave like in C : return num; In pascal I think the equivalent would be : nextt := num; exit; ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] fpc isn't optimised for tail recursion, is it?
On 12-6-2023 08:15, Nikolay Nikolov via fpc-pascal wrote: Shouldn't the recursive call assign the result? nextt(num - 1); nextt:=nextt(num - 1); if you don't use the result, the whole call may be optimized away? ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] fpc isn't optimised for tail recursion, is it?
On 6/12/23 04:44, Steve Litt via fpc-pascal wrote:
Hi all,
Tail recursion is recursion in which absolutely nothing gets executed
after the return statement. Some programming languages, including
Guile, optimize for tail recursion such that tail recursive algorithms
don't use additional stack space as you pile up more and more levels of
recursion.
I did a typical non-tail recursion hello world program, and if I set
the "now-go-backward" number high enough, it segfaulted, I assume
because I ran it out of stack space with so many levels of recursion.
So, to see if FPC is optimized for tail recursion, I tested it with the
following program, which I think is tail-recursive.
===
program recursion_hello;
function nextt(num: int64): int64;
begin
writeln('Going deeper=> ', num);
if (num > 0) then
begin
nextt(num - 1);
end;
nextt := num;
end;
begin
nextt(10);
end.
===
As you can see, the return from function occurs at the very end of
function nextt(), which I believes makes my algorithm tail-recursive.
Running my program, I found it segfaulted pretty much the same as the
non-tail-recursive version.
I tried to look up all relevant compiler directives, finding {s-}
and {$stackspaces off}, which requires no local vars and no parameters
to not implement a stackspace for a fuunction. So I made the
"now-go-backward" number a global, and made the recursive function a
procedure, and still, I got the segfaulting.
So, subject to your guidance, I'm assuming FPC isn't optimized for tail
recursion. Is my assumption an accurate one?
FPC supports tail recursion optimization, it is enabled at -O2
optimization level for most CPUs, however your code isn't eligible for
that optimization, because there's extra code, after the recursive
invoke. If you change it like that:
program recursion_hello;
function nextt(num: int64): int64;
begin
writeln('Going deeper=> ', num);
nextt := num;
if (num > 0) then
begin
nextt(num - 1);
end;
end;
begin
nextt(10);
end.
And if you compile with -O2 it works, without segfaulting (tested with
FPC 3.2.2 on x86_64-linux).
Nikolay
Thanks,
SteveT
Steve Litt
Autumn 2022 featured book: Thriving in Tough Times
http://www.troubleshooters.com/bookstore/thrive.htm
___
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
___
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
[fpc-pascal] fpc isn't optimised for tail recursion, is it?
Hi all,
Tail recursion is recursion in which absolutely nothing gets executed
after the return statement. Some programming languages, including
Guile, optimize for tail recursion such that tail recursive algorithms
don't use additional stack space as you pile up more and more levels of
recursion.
I did a typical non-tail recursion hello world program, and if I set
the "now-go-backward" number high enough, it segfaulted, I assume
because I ran it out of stack space with so many levels of recursion.
So, to see if FPC is optimized for tail recursion, I tested it with the
following program, which I think is tail-recursive.
===
program recursion_hello;
function nextt(num: int64): int64;
begin
writeln('Going deeper=> ', num);
if (num > 0) then
begin
nextt(num - 1);
end;
nextt := num;
end;
begin
nextt(10);
end.
===
As you can see, the return from function occurs at the very end of
function nextt(), which I believes makes my algorithm tail-recursive.
Running my program, I found it segfaulted pretty much the same as the
non-tail-recursive version.
I tried to look up all relevant compiler directives, finding {s-}
and {$stackspaces off}, which requires no local vars and no parameters
to not implement a stackspace for a fuunction. So I made the
"now-go-backward" number a global, and made the recursive function a
procedure, and still, I got the segfaulting.
So, subject to your guidance, I'm assuming FPC isn't optimized for tail
recursion. Is my assumption an accurate one?
Thanks,
SteveT
Steve Litt
Autumn 2022 featured book: Thriving in Tough Times
http://www.troubleshooters.com/bookstore/thrive.htm
___
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
