Discussion:
Compile time functions
(too old to reply)
Martok
2018-07-20 21:19:34 UTC
Permalink
Hi all,

inspired by Kit's concept for pure functions, I had a deeper look at what inline
functions (and more importantly, the nodes involved in expanding them) can do.
Let me share my proof-of-concept (which may very well become a
'poof-of-concept'...). You can find my current working branch here
<https://github.com/martok/freepascal/compare/master...dev_inlining>.

Instead of marking a function as 'pure' at declaration, I took another way: make
normal inlining firstpass flexible enough that any "accidentally" pure function
can be collapsed at the call site.
As an extension, I then propose a new intrinsic:

function ConstExpr(X: AnyType): AnyType;
If the expression X can be reduced to a constant, the node simplifies to
that constant.
Otherwise, fail compilation with E3203 Illegal Expression.

ConstExpr is basically pass-through for most expressions, but it allows us to
"call" functions /at parse time/, as long as these functions are pure and the
arguments are constant at the point of declaration.

Let me illustrate with an example:

program tinline3;

  function sinc(x: Real): Real; inline;
  begin
    if X = 0 then
      Result:= 1
    else
      Result:= sin(x) / x;
  end;

const
  s1 = constexpr(sinc(0.3));
  s2 = constexpr(sinc(0));
var
  u, v: Real;
begin
  u:= s1;
  u:= s2;
end.

This gets processed into the node tree (right at parse time):

*******************************************************************************
after parsing
$main; Register;
*******************************************************************************
(blockn, resultdef = $void = "untyped", pos = (16,1), loc = LOC_INVALID,
expectloc = LOC_INVALID, flags = [], cmplx = 4
   (statementn, resultdef = <nil>, pos = (17,9), loc = LOC_INVALID,
expectloc = LOC_INVALID, flags = [], cmplx = 4
      (assignn, resultdef = $void = "untyped", pos = (17,3), loc =
LOC_INVALID, expectloc = LOC_INVALID, flags = [], cmplx = 2
         (loadn, resultdef = Real = "Double", pos = (17,3), loc =
LOC_INVALID, expectloc = LOC_INVALID, flags = [nf_write], cmplx = 1
            nil
            symbol = U
         )
         (realconstn, resultdef = Real = "Double", pos = (17,7), loc =
LOC_INVALID, expectloc = LOC_INVALID, flags = [], cmplx = 2
            value =  9.85067355537798561294E-0001
         )
      )

   )
   (statementn, resultdef = <nil>, pos = (18,9), loc = LOC_INVALID,
expectloc = LOC_INVALID, flags = [], cmplx = 2
      (assignn, resultdef = $void = "untyped", pos = (18,3), loc =
LOC_INVALID, expectloc = LOC_INVALID, flags = [], cmplx = 2
         (loadn, resultdef = Real = "Double", pos = (18,3), loc =
LOC_INVALID, expectloc = LOC_INVALID, flags = [nf_write], cmplx = 1
            nil
            symbol = U
         )
         (realconstn, resultdef = Real = "Double", pos = (18,7), loc =
LOC_INVALID, expectloc = LOC_INVALID, flags = [], cmplx = 2
            value =  1.00000000000000000000E+0000
         )
      )

   )
)

As you can see, the expressions have been simplified into (the correct)
constants of type Double (Real for x86 is Double). Intermediate type conversions
(including potential loss of FP-precision) are handled correctly (there's a
sneaky int(0)<>real in the example).
This is already really useful for the most common application of macros with
parameters in C: calculating constants (like #define _IOC(inout,group,num,len)
(inout | ((len & IOCPARM_MASK) << 16) | ((group) << 8) | (num))).

There are currently a few issues:

1. I extended the const propagation optimisation pass a bit. It had
restrictions on inlinen and realconstn that probably had a reason, but I
can't see it...
2. calln now does an automatic internal optconstpropagate pass when inlining.
This is to carry refs to constant temps a bit further down. That might in
fact be problematic because it could increase code size with multiple loads
and should probably not be done in general. But for this PoC, that was the
simplest way.
3. procs can only be inlined if their body has been fully parsed before the
call. This is actually kind of a problem because it limits usefulness for
the C-style constant-macro application.
4. The tricky part (same goes for pure functions) is actually finding out if
parameters of an inlined function are constants. optconstpropagate can track
that after the fact, but at that point the fun is already over. The best
solution I could think of is running some very primitive DFA along while
parsing, so that the firstpass can refer to that. Basically, if a symbol is
known to be constant, loads of it could be treated as constants of its
stored value for the purposes of simplify(). This is of course limited to
only local symbols, but still doesn't seem very practical...

So, it's far from perfect, but shows that there is some potential for
metaprogramming without the need for much new complexity (numstat is +59-5 at
the time of writing this). I suspect there is quite a lot that could be gained
from better constant propagation in general: most nodes can already simplify
themselves efficiently, but only if they know the arguments are constant.

What do you think?

Regards,
Martok
Sven Barth via fpc-devel
2018-07-21 00:08:45 UTC
Permalink
Post by Martok
What do you think?
The main problem is that not all functions that would be eligible for your
approach are also declared as inline thus their node trees would not be
stored inside the PPU and thus you could not work with them.
Additional benefit of the "pure" modifier: the compiler can check once the
method has been parsed whether it's pure or not and can thus error out in
the latter case.

Regards,
Sven
R0b0t1
2018-07-21 03:11:38 UTC
Permalink
On Fri, Jul 20, 2018 at 7:08 PM, Sven Barth via fpc-devel
Post by Sven Barth via fpc-devel
Post by Martok
What do you think?
The main problem is that not all functions that would be eligible for your
approach are also declared as inline thus their node trees would not be
stored inside the PPU and thus you could not work with them.
Additional benefit of the "pure" modifier: the compiler can check once the
method has been parsed whether it's pure or not and can thus error out in
the latter case.
How does the existing constprop optimization relate to the pure
modifier? I apologize if this was already covered.
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/l
Martok
2018-07-21 15:11:40 UTC
Permalink
Post by Sven Barth via fpc-devel
The main problem is that not all functions that would be eligible for your
approach are also declared as inline thus their node trees would not be stored
inside the PPU and thus you could not work with them.
I'm not sure I understand. Isn't the same true, with a new feature? The full
node tree must be available, which basically means "has inlineinfo". Doesn't it?
Post by Sven Barth via fpc-devel
Additional benefit of the "pure" modifier: the compiler can check once the
method has been parsed whether it's pure or not and can thus error out in the
latter case.
That is true, it is a more explicit declaration of intent.
Maybe the codegen of pure can simply be implemented as generating inline info,
but always replacing the calls with the simplified version. If it is already
known that a function is pure, what I did with constexpr() would basically be
guaranteed to work.
--
Regards,
Martok

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/
Sven Barth via fpc-devel
2018-07-21 17:51:33 UTC
Permalink
Post by Martok
Post by Sven Barth via fpc-devel
The main problem is that not all functions that would be eligible for
your
Post by Sven Barth via fpc-devel
approach are also declared as inline thus their node trees would not be
stored
Post by Sven Barth via fpc-devel
inside the PPU and thus you could not work with them.
I'm not sure I understand. Isn't the same true, with a new feature? The full
node tree must be available, which basically means "has inlineinfo". Doesn't it?
Correct.
Post by Martok
Post by Sven Barth via fpc-devel
Additional benefit of the "pure" modifier: the compiler can check once
the
Post by Sven Barth via fpc-devel
method has been parsed whether it's pure or not and can thus error out
in the
Post by Sven Barth via fpc-devel
latter case.
That is true, it is a more explicit declaration of intent.
Maybe the codegen of pure can simply be implemented as generating inline info,
but always replacing the calls with the simplified version. If it is already
known that a function is pure, what I did with constexpr() would basically be
guaranteed to work.
Pure functions would still have an ordinary generated body as there is no
reason that their address shouldn't be able to be taken (otherwise one
needs to declare wrappers for them). Other than that I personally favor the
explicit declaration of intent for such functions without the need for a
ConstExpr intrinsic.

Regards,
Sven
J. Gareth Moreton
2018-07-22 04:03:13 UTC
Permalink
An interesting read. If you can collapse an inline function into a single
assignment in most situations, then brilliant! Definitely keep that optimisation in.

While there are many similarities and prerequisites between an inline function
and a pure function, and many simple mathematical functions could easily carry
both modifiers, they are not exactly the same. Pure functions cannot be
evaluated at compile time if one of the arguments is a variable (or at the very
least, not deterministic), but it might be inlined, while a function with
recursion can't be reliably inlined, but might still be pure (e.g. factorial,
assuming you don't rewrite it to use a for-loop), and not all recursive functions
can be rewritten to use simpler loops (e.g. the infamous Ackermann function). It
is true though... proper constant propagation would cover most situations, even
when an inline function calls another inline function such as Max, although there
might still be issues in exceptional conditions (e.g. division by zero or trying
to calculate tan(pi/2), for example).

The other point with a "pure" modifier is that, assuming the compiler determines
that the function is indeed pure, it would permit their assignment to a constant.
True, you could replace the constant with the function call whenever it appears,
but that's not exactly good coding practice. And that's sort of the other reason
for the "pure" modifier. If you release a library of functions that a
third-party then looks at, with no background knowledge of its inner workings,
the appearance of the "pure" modifier would quickly clue them in in regards to
the functions' intent.

The final issue is that while a function might be pure, you might not want to
inline it because of its complexity, especially if it's called multiple times
with variable arguments. The simplest example I can think of is the two-argument
binomial coefficient:

function Binomial(n, r: Cardinal): Cardinal; pure;
begin
if (r > n) then
Result := 0
else if (r = n) then
Result := 1 { Faster than calculating the factorials }
else
Result := Factorial(n) div (Factorial(r) * Factorial(n - r));
end;

The alternative versions either require recursion, or for exceptionally large
values of n and r, calculating the integral that defines the gamma function.

Gareth aka. Kit
Post by Martok
Post by Sven Barth via fpc-devel
The main problem is that not all functions that would be eligible for
your
Post by Sven Barth via fpc-devel
approach are also declared as inline thus their node trees would not be
stored
Post by Sven Barth via fpc-devel
inside the PPU and thus you could not work with them.
I'm not sure I understand. Isn't the same true, with a new feature? The
full
node tree must be available, which basically means "has inlineinfo".
Doesn't it?
Correct. 
Post by Sven Barth via fpc-devel
Additional benefit of the "pure" modifier: the compiler can check once
the
Post by Sven Barth via fpc-devel
method has been parsed whether it's pure or not and can thus error out
in the
Post by Sven Barth via fpc-devel
latter case.
That is true, it is a more explicit declaration of intent.
Maybe the codegen of pure can simply be implemented as generating inline
info,
but always replacing the calls with the simplified version. If it is
already
known that a function is pure, what I did with constexpr() would basically
be
guaranteed to work.
Pure functions would still have an ordinary generated body as there is no
reason that their address shouldn't be able to be taken (otherwise one
needs to declare wrappers for them). Other than that I personally favor the
explicit declaration of intent for such functions without the need for a
ConstExpr intrinsic. 
Regards, Sven  _______________________________________________
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel [1]
------
[1]
http://secureweb.fast.net.uk/parse.php?redirect=http://lists.freepascal.org
/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinf
Martok
2018-07-22 13:57:59 UTC
Permalink
Post by J. Gareth Moreton
Pure functions cannot be
evaluated at compile time if one of the arguments is a variable (or at the very
least, not deterministic)
Do you have an idea how to prove that yet? The way I see it now, this is the
only hard issue, every other component is already present somewhere in some form.
Post by J. Gareth Moreton
although there
might still be issues in exceptional conditions (e.g. division by zero or trying
to calculate tan(pi/2), for example).
Good point - what should happen in that case?
const
x = Pi / 0;
begin
writeln(x);
end.
That writes "+Inf".
Post by J. Gareth Moreton
The other point with a "pure" modifier is that, assuming the compiler determines
that the function is indeed pure, it would permit their assignment to a constant.
So: on processing a call to a pure function,
if arguments are constant, emit (interpreted) result of function
otherwise, emit regular call
?
What would error/warning cases be? I'd want to avoid a situation like that with
the insightful, but unfixable and thus spammy "06058_N_Call to subroutine "$1"
marked as inline is not inlined" message.
Post by J. Gareth Moreton
The final issue is that while a function might be pure, you might not want to
inline it because of its complexity, especially if it's called multiple times
with variable arguments.
That is very true. Should the "interpretation complexity" be limited, or should
the compiler keep going and maybe run into a stack overflow?
--
Regards,
Martok


_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://l
J. Gareth Moreton
2018-07-22 04:15:05 UTC
Permalink
Sorry for that mess of a formatting on the code sample, Here is a much
nicer version!
function Binomial(n, r: Cardinal): Cardinal; pure;begin
  if (r > n) then
    Result := 0
  else if (r = n) then
    Result := 1 { Faster than calculating the factorials }
  else
    Result := Factorial(n) div (Factorial(r) * Factorial(n - r));
end;

Gareth aka. Kit

On Sun 22/07/18 05:03 , "J. Gareth Moreton" ***@moreton-family.com
sent:
An interesting read. If you can collapse an inline function into a single
assignment in most situations, then brilliant! Definitely keep that
optimisation in.

While there are many similarities and prerequisites between an inline
function
and a pure function, and many simple mathematical functions could easily
carry
both modifiers, they are not exactly the same. Pure functions cannot be
evaluated at compile time if one of the arguments is a variable (or at the
very
least, not deterministic), but it might be inlined, while a function with
recursion can't be reliably inlined, but might still be pure (e.g.
factorial,
assuming you don't rewrite it to use a for-loop), and not all recursive
functions
can be rewritten to use simpler loops (e.g. the infamous Ackermann
function). It
is true though... proper constant propagation would cover most situations,
even
when an inline function calls another inline function such as Max,
although there
might still be issues in exceptional conditions (e.g. division by zero or
trying
to calculate tan(pi/2), for example).

The other point with a "pure" modifier is that, assuming the compiler
determines
that the function is indeed pure, it would permit their assignment to a
constant.
True, you could replace the constant with the function call whenever it
appears,
but that's not exactly good coding practice. And that's sort of the other
reason
for the "pure" modifier. If you release a library of functions that a
third-party then looks at, with no background knowledge of its inner
workings,
the appearance of the "pure" modifier would quickly clue them in in
regards to
the functions' intent.

The final issue is that while a function might be pure, you might not want
to
inline it because of its complexity, especially if it's called multiple
times
with variable arguments. The simplest example I can think of is the
two-argument
binomial coefficient:

function Binomial(n, r: Cardinal): Cardinal; pure;
begin
if (r > n) then
Result := 0
else if (r = n) then
Result := 1 { Faster than calculating the factorials }
else
Result := Factorial(n) div (Factorial(r) * Factorial(n - r));
end;

The alternative versions either require recursion, or for exceptionally
large
values of n and r, calculating the integral that defines the gamma
function.

Gareth aka. Kit

On Sat 21/07/18 18:51 , Sven Barth via fpc-devel
Post by Martok
Post by Sven Barth via fpc-devel
The main problem is that not all functions that would be eligible for
your
Post by Sven Barth via fpc-devel
approach are also declared as inline thus their node trees would not
be
Post by Martok
stored
Post by Sven Barth via fpc-devel
inside the PPU and thus you could not work with them.
I'm not sure I understand. Isn't the same true, with a new feature? The
full
node tree must be available, which basically means "has inlineinfo".
Doesn't it?
Correct. 
Post by Sven Barth via fpc-devel
Additional benefit of the "pure" modifier: the compiler can check once
the
Post by Sven Barth via fpc-devel
method has been parsed whether it's pure or not and can thus error out
in the
Post by Sven Barth via fpc-devel
latter case.
That is true, it is a more explicit declaration of intent.
Maybe the codegen of pure can simply be implemented as generating inline
info,
but always replacing the calls with the simplified version. If it is
already
known that a function is pure, what I did with constexpr() would
basically
Post by Martok
be
guaranteed to work.
Pure functions would still have an ordinary generated body as there is
no
Post by Martok
reason that their address shouldn't be able to be taken (otherwise one
needs to declare wrappers for them). Other than that I personally favor
the
Post by Martok
explicit declaration of intent for such functions without the need for a
ConstExpr intrinsic. 
Regards, Sven  _______________________________________________
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[3]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel [1]
Post by Martok
------
[1]
http://secureweb.fast.net.uk/parse.php%3Fredirect%3Dhttp://lists.freepascal.org
[4]">http://secureweb.fast.net.uk/parse.php?redirect=http://lists.freepascal.org
[5]
Post by Martok
/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org [6]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[7]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel



Links:
------
[1] mailto:fpc-***@lists.freepascal.org
[2] mailto:fpc-***@lists.freepascal.org
[3] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[4]
http://secureweb.fast.net.uk/parse.php%3Fredirect%3Dhttp://lists.freepascal.org
[5] http://lists.freepascal.org
[6] mailto:fpc-***@lists.freepascal.org
[7] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
J. Gareth Moreton
2018-07-22 04:56:45 UTC
Permalink
To follow up on this, even if you rewrote the function to use a
multiplicative formula (faster to compute overall):

function Binomial(n, r: Cardinal): Cardinal; pure;var  c: Cardinal;
begin
  for (r > n) then
    Result := 0
  else
    begin
      Result := 1;
      if n r then
        begin
          Inc(n); { Only "n + 1" appears in the formula }
          for c := 1 to r do           
            Result := (Result * (n - c)) div c; { Make sure the
multiplication is evaluated first }

        end;
    end;
end;

I'm not saying it's impossible, but that's certainly slightly harder to
propagate a constant through that, even with manual programmer
optimisations like with Inc(n).

Gareth aka. Kit

On Sun 22/07/18 05:15 , "J. Gareth Moreton" ***@moreton-family.com
sent:
Sorry for that mess of a formatting on the code sample, Here is a much
nicer version!
function Binomial(n, r: Cardinal): Cardinal; pure;begin
  if (r > n) then
    Result := 0
  else if (r = n) then
    Result := 1 { Faster than calculating the factorials }
  else
    Result := Factorial(n) div (Factorial(r) * Factorial(n - r));
end;

Gareth aka. Kit

On Sun 22/07/18 05:03 , "J. Gareth Moreton" ***@moreton-family.com
sent:
An interesting read. If you can collapse an inline function into a single
assignment in most situations, then brilliant! Definitely keep that
optimisation in.

While there are many similarities and prerequisites between an inline
function
and a pure function, and many simple mathematical functions could easily
carry
both modifiers, they are not exactly the same. Pure functions cannot be
evaluated at compile time if one of the arguments is a variable (or at the
very
least, not deterministic), but it might be inlined, while a function with
recursion can't be reliably inlined, but might still be pure (e.g.
factorial,
assuming you don't rewrite it to use a for-loop), and not all recursive
functions
can be rewritten to use simpler loops (e.g. the infamous Ackermann
function). It
is true though... proper constant propagation would cover most situations,
even
when an inline function calls another inline function such as Max,
although there
might still be issues in exceptional conditions (e.g. division by zero or
trying
to calculate tan(pi/2), for example).

The other point with a "pure" modifier is that, assuming the compiler
determines
that the function is indeed pure, it would permit their assignment to a
constant.
True, you could replace the constant with the function call whenever it
appears,
but that's not exactly good coding practice. And that's sort of the other
reason
for the "pure" modifier. If you release a library of functions that a
third-party then looks at, with no background knowledge of its inner
workings,
the appearance of the "pure" modifier would quickly clue them in in
regards to
the functions' intent.

The final issue is that while a function might be pure, you might not want
to
inline it because of its complexity, especially if it's called multiple
times
with variable arguments. The simplest example I can think of is the
two-argument
binomial coefficient:

function Binomial(n, r: Cardinal): Cardinal; pure;
begin
if (r > n) then
Result := 0
else if (r = n) then
Result := 1 { Faster than calculating the factorials }
else
Result := Factorial(n) div (Factorial(r) * Factorial(n - r));
end;

The alternative versions either require recursion, or for exceptionally
large
values of n and r, calculating the integral that defines the gamma
function.

Gareth aka. Kit

On Sat 21/07/18 18:51 , Sven Barth via fpc-devel
Post by Martok
Post by Sven Barth via fpc-devel
The main problem is that not all functions that would be eligible for
your
Post by Sven Barth via fpc-devel
approach are also declared as inline thus their node trees would not
be
Post by Martok
stored
Post by Sven Barth via fpc-devel
inside the PPU and thus you could not work with them.
I'm not sure I understand. Isn't the same true, with a new feature? The
full
node tree must be available, which basically means "has inlineinfo".
Doesn't it?
Correct. 
Post by Sven Barth via fpc-devel
Additional benefit of the "pure" modifier: the compiler can check once
the
Post by Sven Barth via fpc-devel
method has been parsed whether it's pure or not and can thus error out
in the
Post by Sven Barth via fpc-devel
latter case.
That is true, it is a more explicit declaration of intent.
Maybe the codegen of pure can simply be implemented as generating inline
info,
but always replacing the calls with the simplified version. If it is
already
known that a function is pure, what I did with constexpr() would
basically
Post by Martok
be
guaranteed to work.
Pure functions would still have an ordinary generated body as there is
no
Post by Martok
reason that their address shouldn't be able to be taken (otherwise one
needs to declare wrappers for them). Other than that I personally favor
the
Post by Martok
explicit declaration of intent for such functions without the need for a
ConstExpr intrinsic. 
Regards, Sven  _______________________________________________
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[3]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel [1]
Post by Martok
------
[1]
http://secureweb.fast.net.uk/parse.php?redirect=http://lists.freepascal.org
[5]
Post by Martok
/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org [6]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[7]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org [8]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[9]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel



Links:
------
[1] mailto:fpc-***@lists.freepascal.org
[2] mailto:fpc-***@lists.freepascal.org
[3] http://secureweb.fast.net.uk/ http:=
[4] http://lists.freepascal.org
[5] http://lists.freepascal.org
[6] mailto:fpc-***@lists.freepascal.org
[7] http://secureweb.fast.net.uk/ http:=
[8] mailto:fpc-***@lists.freepascal.org
[9] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
J. Gareth Moreton
2018-07-22 16:05:19 UTC
Permalink
On Sun 22/07/18 14:57 , Martok
Am 22.07.2018 um 06:03 schrieb J. Gareth
Post by J. Gareth Moreton
Pure functions cannot be
evaluated at compile time if one of
the
arguments is a variable (or at the very
Post by J. Gareth Moreton
least, not deterministic)
Do you have an idea how to prove that
yet? The way I see it now, this is
the
only hard issue, every other component
is already present somewhere in some
form.
This one is quite simple really. If what
you are passing into the function is
neither a constant nor a literal number,
then it is called like a regular function
with no hint or warning. If all the actual
parameters are constant, then the compiler
will attempt to evaluate it there and then
and replace the call with the result.
Post by J. Gareth Moreton
although there
might still be issues in exceptional
conditions
(e.g. division by zero or trying
Post by J. Gareth Moreton
to calculate tan(pi/2), for example).
Good point - what should happen in that
case?
const
x = Pi / 0;
begin
writeln(x);
end.
That writes "+Inf".
For integer division and explicit raise
statements, I plan to return a compile-
time error. With floating point, I'm
considering returning the relevant special
representations, since there are
constructs such as "const NaN = 0.0 /
0.0;", which in the mathematical sense is
a pure function. I'm not certain what
tan(Pi/2) returns, but going by the
identity tan = sin/cos, it would be +inf.
Post by J. Gareth Moreton
The other point with a "pure" modifier
is that, assuming the compiler
determines
Post by J. Gareth Moreton
that the function is indeed pure, it
would
permit their assignment to a constant.
So: on processing a call to a pure
function,
if arguments are constant, emit
(interpreted) result of function
otherwise, emit regular call
?
What would error/warning cases be? I'd
want to avoid a situation like that
with
the insightful, but unfixable and thus
spammy "06058_N_Call to
subroutine "$1"
marked as inline is not inlined"
message.

My plan with pure functions is that if the
compiler spots something that makes the
function impure, it returns a warning and
sets a flag to say it's ineligible, so it
won't attempt any further compile-time
evaluation. Unlike inline, which has
fairly arbitrary restrictions, the
definition of a pure function is fairly
concise and easy to understand. Triggering
the warning is usually the sign of a bug,
either in the function itself or has no
business being marked as pure (because it
reads from a file, for example). The
compiler might spot the function's
impurity during node construction or
during evaluation (the latter would
generally only happen if it suspects an
infinite loop and the like).

For the constant assignment, it will
return the error that is already thrown if
you try to assign a function result to a
constant. If the compiler only notices the
function's impurity while attempting to
evaluate the result for this assignment,
it will first throw the warning, then the
error.
Post by J. Gareth Moreton
The final issue is that while a
function might
be pure, you might not want to
Post by J. Gareth Moreton
inline it because of its complexity,
especially
if it's called multiple times
Post by J. Gareth Moreton
with variable arguments.
That is very true. Should the
"interpretation complexity" be
limited, or should
the compiler keep going and maybe run
into a stack overflow?
--
Regards,
Martok
This is actually why I keep bringing up
the Ackermann function as a test case, to
see how the compiler responds to extreme
situations, because there is no general
solution to determine if a function
actually completes (Turing's halting
problem)... then again, Ackermann's
function actually does complete - it just
takes a prohibitively long time for large
inputs.

To get around this, I'm considering a
limit of 4096 nodes that the compiler will
step through, and a stack depth limit of
64, before deciding that it's an infinite
loop or otherwise too complex to be pure,
and mark it as ineligible (and to stop the
compiler from crashing or taking longer
than the age of the Universe to build the
project). This would otherwise be the only
arbitrary restriction on pure functions
that can't easily be fixed, but you would
have to try quite hard to trigger it and
is more likely a bug such as an actual
infinite loop.

Thanks for the questions, Martok.

Gareth aka. Kit
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fp

Loading...