[fpc-devel] Compile time functions

[J. Gareth Moreton]

On Sun 22/07/18 14:57 , Martok 
listbox at martoks-place.de sent:
> Am 22.07.2018 um 06:03 schrieb 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.

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.
> 
> 
> > 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".
> 
> 
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.

> 
> > 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.

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.

> 
> 
> > 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
> 
> 

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