[fpc-devel] A call to help test pure functions

[J. Gareth Moreton]

Hi everyone,

This has been something that's been in development for some time now, 
and I invite other Free Pascal users and developers to test the new 
feature... pure functions.  Its closest equivalent in C++ would be 
"constexpr".

A pure function has no side-effects - it doesn't affect the machine 
state outside of its scope.  More broadly, it is analogous to a 
mathematical function, so for a given input(s), will always return the 
same output.  The idea is that if a function is marked as pure, and 
confirmed to be by the compiler, then in certain situations, its result 
can be computed at compile time and the call replaced with the 
calculated result as a literal.  I've attached two examples showing pure 
functions in action, one that unrolls a for-loop, and one that handles 
recursion.  As the examples imply, to mark as a function as pure, simply 
use the new "pure" directive.  By default, subroutines are not 
considered pure because, while the compiler would easily be able to 
defermine if a function is actually pure or not, this would cause 
significant slowdown to the compilation process.

You can access my repository here: 
https://gitlab.com/CuriousKit/optimisations/-/tree/pure?ref_type=heads

Note that pure functions are subtly different to inline functions, and 
while there is a lot of overlap, they have different use cases.  Some 
pure functions can theoretically be extremely complex and would not be 
something you'd want to inline, but is guaranteed to produce a 
deterministic result for a given input.  A theoretical example would be 
a hash function (although my pure functions do not support pointers 
because the data they point to is not deterministic until you 
dereference it). Similarly, a small inline function that accesses a 
global variable (e.g. to read or modify a reference count) cannot be a 
pure function because the compiler has no way of knowing what that 
variable will be set to at compile time.

Currently there's no support to assign the result of a pure function to 
a constant, although I intend to find a means to support it one day.  
Additionally, procedures with "out" parameters unfortunately tend to not 
be evaluated correctly and will error out (the compiler might consider 
them impure even though they actually are.  If the "out" parameter is 
passed into another function through a call, even if it's to another 
pure function or itself (recursion), the parameter is considered 
"escaped" and so can't be optimised.  So far I haven't worked out how to 
get around this because the load nodes are marked as "address taken" as 
well as the definition of the formal parameter itself.  Temporarily 
modifying these definitions during pure function analysis is somewhat 
dangerous and error-prone.  I'll solve this eventually though.

One of my current goals is to make "IntToStr", which calls "Str" 
internally, a pure function.  One might question the point of this, 
since who in their right mind would write something like "Output := 
IntToStr(5);"  The reasul is that another pure function (one that may 
generate a string for a notification message, for example) may call 
IntToStr with an actual parameter that's a variable, but said variable 
is deterministic within the function and so would be replaced with an 
integer literal by the time "IntToStr" is evaluated.  If "IntToStr" can 
be successfully made a pure function, then that can be considered a 
milestone and other similar functions can follow.

Other possibilities:

for N := 1 to 10 do
   Y := N * SomePureFunc(X);

Here, X is an unknown local variable.  However, if it is not modified 
within the for-loop, SomePureFunc(X) will always return the same value 
(if it is actually a pure function), so the compiler could theoretically 
optimise it to the equivalent code:

Z := SomePureFunc(X);
for N := 1 to 10 do
   Y := N * Z;

This could be achieved through the tempcreate / tempref / tempdelete 
nodes that are often used when expanding inline functions.

Any suggestions, requests, bug reports or, heck, even a merge request, 
please send them my way!

Yours faithfully,

J. Gareth "Kit" Moreton
-------------- next part --------------
program pure1a;
{$MODE OBJFPC}
{$COPERATORS ON}

function Factorial(N: Cardinal): Cardinal; pure;
  var
    X: Integer;
  begin
    Result := 1;
    for X := N downto 2 do
      Result *= X;
  end;

begin
  WriteLn(Factorial(5));
end.
-------------- next part --------------
program pure1b;
{$MODE OBJFPC}

function Factorial(N: Cardinal): Cardinal; pure;
  begin
    if N < 2 then
	  Result := 1
	else
      Result := N * Factorial(N - 1);
  end;
  
begin
  WriteLn(Factorial(5));
end.