Hi everyone,

With some blessing from Florian on the concept, I've set up a Wiki page discussing the design proposals for the support of pure functions, as well as some explanation on what they actually are.
wiki.freepascal.org/Pure_functions
I hope it proves useful to explain what I'm doing. How do the proposals look so far, Florian?

Gareth aka. Kit

As far as I know, keywords are often used (e.g. "constexpr" in C++).  My reasons are explained in the Wiki topic, but it boils down to compiler performance.  If every function is assumed to be pure, then the compiler has to check each time if that is actually the case, and with a large project with many hundreds of functions and thousands of calls, this will quickly get prohibitively slow.  Generally, most functions will not be pure, especially given the tight restrictions required (for example, object methods can't be pure because it's impossible to determine the value of Self at compile-time, although this may be something for future research if the method only sets internal fields).

Also, it won't break existing code.  For example, this will compile without any problems (although the word 'virtual' might appear highlighted):

 function TestClass.Test: Integer; virtual;
 var
   virtual: Integer;
 begin  virtual := x + 1;  Result := virtual * virtual;
 end;

Due to the design of the Pascal language, procedure directives can share names with identifiers without problems.
Gareth

On Sun 08/07/18 17:11 , "R0b0t1" sent:

J. Gareth Moreton wrote

Hi everyone, With some blessing from Florian on the concept, I've set up a Wiki page discussing the design proposals for the support of pure functions, as

well

look

so far, Florian? Gareth aka. Kit

This is usually done without a keyword. Why add a keyword?

If a keyword must be used, I'd appreciate if they weren't taken from the English language. Doing so is liable to make older code that uses variables of the reserved word's name incompilable.

Cheers,
R0b0t1

What Florian said. Only particular functions can be pure, and even if they are marked as such, the compiler has to make sure they are fulfil a strict set of criteria that requires a degree of data flow analysis, and this can quickly take far too long to complete, especially if the function contains a loop of some kind.

It is a slightly tricky design, because I want to make sure a programmer can't write something that will crash the compiler (which is why I mention the Ackermann Function as a test case).
Anything that dereferences a pointer or accesses a dynamic array (which, internally, is a pointer to something on the heap) cannot be pure, and this covers the vast majority of the functions, but depending on how the function is written, it may not be apparent until the compiler has analysed the majority of the compiled nodes.
Just note... though strictly speaking, only functions can be pure, I haven't explicitly forbidden procedures from being pure, because if they have out parameters, then as long as they fulfil all the other criteria, they can be considered a function with multiple return values.  Note that the presence of a var parameter instantly makes a function impure on account that the argument is, by definition, not constant.

Gareth

On Sun 08/07/18 17:59 , Florian Klämpfl sent:

Why a preprocessor switch for something which applies to a particular function?

This is usually done without a keyword. Why add a keyword?

If a keyword must be used, I'd appreciate if they weren't taken from the English language. Doing so is liable to make older code that uses variables of the reserved word's name incompilable.

Cheers,
R0b0t1

It also feels safer and more intuitive for the programmer.  If you're writing code such as "const Partitions = log2(Length(StaticList));" (assuming Length(StaticList) evaluates to a constant value), then defining log2 as a pure function shows you know what you're doing, because otherwise it might seem random and arbitrary in that you can assign some functions to constants, but not others.  And if the pure function in question is actually impure, then you get both a warning and an error... first the warning that the function is impure, and then an error because you're assigning a function result to a constant, and the two appearing side-by-side will quickly inform the programmer what's going on. It's also the reason behind my choice of the pure keyword... ease-of-use and intuitiveness.

Gareth

On Sun 08/07/18 18:01 , Florian Klämpfl sent:

Dmitry Boyarintsev wrote

On Sun, Jul 8, 2018 at 11:20 AM, J. Gareth Moreton wrote: As far as I know, keywords are often used (e.g. "constexpr" in C++). 

My reasons are explained in the Wiki topic,

but it boils down to compiler performance. How about adding a new modeswitch instead PUREFUNCTIONS? The mode switch would treat any "function" as pure function (and should

check the code for "purity").

beneficial:

From the compiler performance perspective, the purity of a function

needs to be checked only when evaluating constant

expressions (according to the wiki article) Thus the actual use of a function in a constant expression should act as

the proposed "pure" keyword.

No. Because pure is part of the function header and tells users "you can use this function with constant arguments in
constant expressions and this won't change without notification". If the compiler determines by itself if a function is
pure or not, it might even depend on the compiler version if a function is detected as pure or not.

On Jul 8, 2018, at 8:50 AM, J. Gareth Moreton wrote: With some blessing from Florian on the concept, I've set up a Wiki page discussing the design proposals for the support of pure functions, as well as some explanation on what they actually are.

What are the performance benefits? It sounds like this is a proposal for a compiler optimization which we can explicitly opt in to, but what exactly is the optimization?

If nothing else I like the idea as a way to enforce a function is not accessing global state. Kind of like const for functions.

Regards,
Ryan Joseph

It's sort of the other way around.  The lack of the directive implies the function is impure, and so the compiler won't bother with any kind of purity check.  The presence of "pure" slows down the compiler, but possibly producing much more efficient code.  Because pure functions will be rare, it seems only right to mark the functions that definitely fulfil the criteria (or so the programmer thinks), rather letting the compiler attempt to find the pure functions itself, when upwards of 99% of them will be impure.

It also simplifies things for the programmer as far as constant assignment is concerned, otherwise it might appear random and arbitrary in that some functions can be assigned to constants, but not others, while throwing a warning if a function is marked pure but actually isn't helps to inform the programmer that they might have made a mistake.

Gareth

On Sun 08/07/18 18:33 , (Marco van de Voort) sent: In our previous episode, Florian Kl?mpfl said:

> > It doesn't explain why you chose for a modifier rather than

preprocessor

> switch. Why a preprocessor switch for something which applies to a particular

function?

Maybe. But this kind of stuff will be rare, and is only an hint to speed up
parsing. I think having a directive is a bit too much honor.

Maybe it is time for an attribute system?

On Sun, Jul 8, 2018 at 11:20 AM, J. Gareth Moreton <

How about adding a new modeswitch instead PUREFUNCTIONS? The mode switch would treat any "function" as pure function (and should check the code for "purity").

While at the same time would allow "procedures" to return values:
procedure Random(l: LongInt):LongInt;

However, not having an extra modeswitch or new keywords would be beneficial:

From the compiler performance perspective, the purity of a function needs

to be checked only when evaluating constant expressions (according to the wiki article)
Thus the actual use of a function in a constant expression should act as the proposed "pure" keyword.

thanks,
Dmitry

In our previous episode, J. Gareth Moreton said:

wiki.freepascal.org/Pure_functions I hope it proves useful to explain what I'm doing. How do the proposals look so far, Florian?

It doesn't explain why you chose for a modifier rather than preprocessor switch.

On Jul 8, 2018, at 10:55 AM, Marco van de Voort wrote: It doesn't explain why you chose for a modifier rather than preprocessor switch.

Performance aside I think it’s useful to mark a function as “pure” so you can guarantee it’s not messing with global state. I’m sure I could have used that at some point over the years.

Regards,
Ryan Joseph

Why a preprocessor switch for something which applies to a particular function?

No. Because pure is part of the function header and tells users "you can use this function with constant arguments in constant expressions and this won't change without notification". If the compiler determines by itself if a function is pure or not, it might even depend on the compiler version if a function is detected as pure or not.

The concept of pure functions is that it allows for their evaluation at compile time for constant arguments.  In your example, function purity wouldn't play into it because x, I assume, is a variable whose value is unknown at compile time.  However, advanced data flow analysis might be able to spot that x hasn't changed, and marking 'sin' as pure would indeed be an advantage because the first call's result can be stored for later use, and the second function call removed, knowing it won't cause side-effects.
I would say that that is currently beyond the scope of the proposal, but given that I've been working on a deep optimizer with the intention of optimising code where div and mod are used together with the same arguments (in this case, the pure 'function' is the div operator), that is definitely something I would like to come back to - thanks for the idea!

Gareth
On Sun 08/07/18 19:00 , Martin sent: On 08/07/2018 16:50, J. Gareth Moreton wrote:
Hi everyone,

With some blessing from Florian on the concept, I've set up a Wiki page discussing the design proposals for the support of pure functions, as well as some explanation on what they actually are.
wiki.freepascal.org/Pure_functions
I hope it proves useful to explain what I'm doing. How do the proposals look so far, Florian?

I seem to be missing a part of the feature (or did I misunderstand (part of)  the side?

It is all about the compiler evaluating pure functions at compile time, and placing the result as a constant in the code. (Or at least that's how I read it).
That's all fine.

 But what about re-using  := sin(x);
 If x is unknown this can not be computed at compile time.
 But
   if sin(x) > y then b := sin(x);

Knowing that sin is pure AND knowing that x did not change, means only one call is needed.
Is that also planed?

At the same time, I would argue that, really, the programmer should code something like this:
c := sin(x);if c > y then b := c;

There probably isn't any harm in supporting such optimisation though.

Gareth

On Sun 08/07/18 18:19 , "J. Gareth Moreton"
sent:
The concept of pure functions is that it allows for their evaluation at compile time for constant arguments.  In your example, function purity wouldn't play into it because x, I assume, is a variable whose value is unknown at compile time.  However, advanced data flow analysis might be able to spot that x hasn't changed, and marking 'sin' as pure would indeed be an advantage because the first call's result can be stored for later use, and the second function call removed, knowing it won't cause side-effects.
I would say that that is currently beyond the scope of the proposal, but given that I've been working on a deep optimizer with the intention of optimising code where div and mod are used together with the same arguments (in this case, the pure 'function' is the div operator), that is definitely something I would like to come back to - thanks for the idea!

Gareth
On Sun 08/07/18 19:00 , Martin sent: On 08/07/2018 16:50, J. Gareth Moreton wrote:
Hi everyone,

With some blessing from Florian on the concept, I've set up a Wiki page discussing the design proposals for the support of pure functions, as well as some explanation on what they actually are.
wiki.freepascal.org/Pure_functions
I hope it proves useful to explain what I'm doing. How do the proposals look so far, Florian?

I seem to be missing a part of the feature (or did I misunderstand (part of)  the side?

It is all about the compiler evaluating pure functions at compile time, and placing the result as a constant in the code. (Or at least that's how I read it).
That's all fine.

 But what about re-using  := sin(x);
 If x is unknown this can not be computed at compile time.
 But
   if sin(x) > y then b := sin(x);

Knowing that sin is pure AND knowing that x did not change, means only one call is needed.
Is that also planed?

In our previous episode, Florian Kl?mpfl said:

Maybe. But this kind of stuff will be rare, and is only an hint to speed up parsing. I think having a directive is a bit too much honor.

Maybe it is time for an attribute system?

I seem to be missing a part of the feature (or did I misunderstand (part of)  the side?

It is all about the compiler evaluating pure functions at compile time, and placing the result as a constant in the code. (Or at least that's how I read it).
That's all fine.

But what about re-using  := sin(x);
If x is unknown this can not be computed at compile time.
But
   if sin(x) > y then b := sin(x);

Knowing that sin is pure AND knowing that x did not change, means only one call is needed.
Is that also planed?

Talking about this.... Maybe it is worth to also detect if an inpure function is side effect free (e.g. random() ).
if sin(globalvar) > foo() then b := sin(globalvar);

If foo is side-effect free, then the optimization can still be done. (even if foo is not pure).
And since side-effect free is anyway part of being pure, you are going to write those checks anyway. It may be worth organizing the checks, so that side-effect free can be detected on its own too.

This also allows more optimization around full bool eval or short cut bool eval.
   if true or foo() then
Full bool eval will call foo, despite it will never change the result. This is needed for various reasons:
- side effects
- security (cryptography etc)

In case of the former, a mode switch could be introduced to shortcut bool eval only for side effect free expressions. (though that is very specific, and may not be wanted)

In any case knowing that a function is side effect free will later help with data flow analysis.

Isn't it similar to "overload" keyword?
delphi mode required "overload" keyword for functions, while for objfpc mode, it's up to the compiler.

(and yes, there were some issues with the compiler failing to determine what overload function to call from version to version)

thanks,
Dmitry

No. It marks a function as usable in constant expressions (like sin/ln whatever).

There were some other comments touching on reasons for or against a keyword, and I apologize for not speaking to them precisely. But, this is why I would like to avoid a keyword - it is redundant.

As noted only certain statements are constant. If marked so the compiler must verify they are constant anyway. So, what makes more sense is determining the constexprness of an expression by analyzing each subexpression. If an expression is made of only constant expressions it too is constant.

The information *must* already be there. It would be best to not introduce another keyword and to keep the user from worrying about it.

Cheers,
R0b0t1

That's my fault for using the wrong
terminology in that case - feel free to
fix it.

And yes, the directive tells the compiler
that the programmer intends for this
function to be pure. It still requires
effort by the compiler to determine if
it's eligible, because the only way to
figure out if it is, and to actually
calculate the values, is to emulate the
pre-compiled nodes, and this will be
relatively expensive to perform.

Gareth

P.S. Determining if a function has side-
effects or not, to aid data flow analysis,
itself requires data flow analysis.

On Sun 08/07/18 22:43 , "Thorsten Engler"
sent:

touching on

reasons for or against a > keyword, and I apologize for not

speaking to

them precisely. But, > this is why I would like to avoid a

keyword - it

is redundant. People keep talking about keywords. As

shown in the examples, pure is not a

keyword. It's a context-sensitive

directive. This is already wrongly stated

in the proposal itself (so people can be

excused for picking up on the use

of the term "keyword" in the proposal)

and it should be fixed (in

the proposal). And it's not redundant. You are telling

the compiler: I want this function

to be pure. Please tell me if I made a

mistake.

People keep talking about keywords. As shown in the examples, pure is not a keyword. It's a context-sensitive directive. This is already wrongly stated in the proposal itself (so people can be excused for picking up on the use of the term "keyword" in the proposal) and it should be fixed (in the proposal).

And it's not redundant. You are telling the compiler: I want this function to be pure. Please tell me if I made a mistake.

Cheers,
Thorsten

If I put a function call into a constant expression, doesn't it already tell the compiler "I want this function to be pure. Please tell me if I made a mistake"?

thanks,
Dmitry

I've fixed the reference in the Wiki - it now calls "pure" a directive, not a keyword.

I predict that evaluating the purity of a function to be an expensive operation and something that should be avoided where possible, especially when compiling something large like Lazarus or the compiler itself.

In the Wiki, I mention the use of the Ackermann Function as an extreme test case for the compiler to see if it spots that it will take too long to evaluate, or maybe even manage some optimizations by remembering some partial results (the Wikipedia article states that the Ackermann Function is a good case for testing a compiler's ability to optimise recursion).  Using a timeout is too unreliable and random, so it will have to be some kind of node count and stack depth limit... I'm pondering about 4,096 and 64 respectively, but these can be changed based on empirical tests.  A node count limit will also allow the compiler to break out if you try to be malicious by writing a pure function with an infinite loop.

Originally I thought about using PascalScript to test a function for purity, but Florian turned this down due to portability issues, licensing issues and the fact that there are bugs present (it sometimes still compiles even if the script is missing essential semicolons).  I hope that one can interpret the pre-compiled nodes with relative efficiency, since this will be a cross-platform solution.

Florian spoke about different compiler versions, and the more I think of it, I believe this will be an iterated development.  For example, initially I will try to get it to work with ordinal and floating-point types, while strings and record types will come later, especially the former since they are dynamic memory objects and might be a bit tricky to work with.  Who knows... maybe they aren't that bad in practice. As a side-note, it might also be possible to make assembler routines pure (e.g. the Int and Frac functions if they weren't internal compiler procedures), but this will require a different kind of interpretation that I consider low-priority for now, especially as it will have to be different for each platform.  I might still research this as part of my work on my deep optimizer.

Gareth

On Mon 09/07/18 00:18 , "Thorsten Engler" sent:

Maybe you don’t understand what “determine the purity of a function” means?

It means that every time any function is called, the compiler has to try to execute the function at compile time (by working through the nodes like an interpreter) until it hits a point that is non-deterministic. This can potentially take forever (the halting problem is real!), so the only thing limiting it is basically some form of timeout (defined as either time spend or nodes traverse).

If you are talking about always considering every function as pure until proven otherwise, you are talking about slowing down the compiler by orders of magnitude.

And, once more, NOT A KEYWORD. It will not conflict with the use of the word “pure” in any existing code. And it will not conflict with any further uses of the word pure in any other context. It’s a context-sensitive directive, and the only context in which it can occur (and is checked for) is one in which arbitrary identifiers can NOT occur.

From: fpc-devel On Behalf Of Dmitry Boyarintsev
Sent: Monday, 9 July 2018 09:00
To: FPC developers' list
Subject: Re: [fpc-devel] Pure function Wiki page

On Sun, Jul 8, 2018 at 6:47 PM, Thorsten Engler wrote:

You are thinking about something like:

 const
  x = FunctionCall(42);

In which case, yes, the compiler could possibly see that as in implicit “check if that function is pure”.

But “constant expressions” can also be something like:

If FunctionCall(42) > 0 then

In which case you don’t want the compiler to have to test every single expression in your program to see if it is composed (all the way down) of pure functions.

Maybe a different approach should be taken?

Determine how much performance impact is made to determine the purity of a function. and then consider adding a new directive and a keyword.

thanks,

Dmitry _______________________________________________

You are thinking about something like:

const
  x = FunctionCall(42);

In which case, yes, the compiler could possibly see that as in implicit “check if that function is pure”.

But “constant expressions” can also be something like:

If FunctionCall(42) > 0 then

In which case you don’t want the compiler to have to test every single expression in your program to see if it is composed (all the way down) of pure functions.

For that, the pure; directive is essential, telling the compiler that it should try to evaluate that function at compile time (if called with only constant parameters).

And keeping this in mind, even for the first case (in an explicit const declaration) the compiler would only be marking the directly referenced function as “possibly pure”, but if that function internally calls other functions (which aren’t explicitly marked as pure) it would fail right away.

The problem with determining if a function is pure or not is not just limited to looking for references to external memory and the like, but also has to take into account that the function might contain an infinite loop, for example, and this is difficult because there is no general-purpose algorithm for finding out if a given program (or a group of functions) will finish or continue running forever.  See "Turing's halting problem": https://en.wikipedia.org/wiki/Halting_problem
As mentioned before, the other reason is semantics.  It might potentially confuse the programmer if "const x = FunctionCall(42);" is seemingly allowed for some arbitrary functions, but not others.  By clearly defining valid functions as pure, it makes it clear to the programmer what can be specified, and also aids in debugging because the compiler will throw a warning if the function is question is actually impure, for example (and then the actual error for trying to assign a function result to a constant).

Gareth

On Mon 09/07/18 00:00 , Dmitry Boyarintsev sent:
On Sun, Jul 8, 2018 at 6:47 PM, Thorsten Engler wrote:

You are thinking about something like:

const
  x = FunctionCall(42);

In which case, yes, the compiler could possibly see that as in implicit “check if that function is pure”.

But “constant expressions” can also be something like:

If FunctionCall(42) > 0 then

In which case you don’t want the compiler to have to test every single expression in your program to see if it is composed (all the way down) of pure functions.
Maybe a different approach should be taken?Determine how much performance impact is made to determine the purity of a function. and then consider adding a new directive and a keyword.
thanks,
Dmitry _______________________________________________

Maybe a different approach should be taken?
Determine how much performance impact is made to determine the purity of a function. and then consider adding a new directive and a keyword.

thanks,
Dmitry

Maybe you don’t understand what “determine the purity of a function” means?

It means that every time any function is called, the compiler has to try to execute the function at compile time (by working through the nodes like an interpreter) until it hits a point that is non-deterministic. This can potentially take forever (the halting problem is real!), so the only thing limiting it is basically some form of timeout (defined as either time spend or nodes traverse).

If you are talking about always considering every function as pure until proven otherwise, you are talking about slowing down the compiler by orders of magnitude.

And, once more, NOT A KEYWORD. It will not conflict with the use of the word “pure” in any existing code. And it will not conflict with any further uses of the word pure in any other context. It’s a context-sensitive directive, and the only context in which it can occur (and is checked for) is one in which arbitrary identifiers can NOT occur.

If I had to give a realistic example of a pure function in such a conditional expression, how about?

"if (decay_constant * time_elapsed) >= ln(2) then ..."

This is a formula related to radioactive decay - if the condition is true, then over half of the original sample has decayed (i.e. time_elapsed is greater than the sample's half-life).

Yes, if any parameters are variables, then the function is not evaluated.  My intention is that the purity of a function is only determined when it comes to evaluating it in an expression, but because of how complex functions can become, the "pure" directive hints to the compiler that the given function is pure and it should attempt the laborous task of evaluating it, rather than the opposite approach of attempting to evaluate all functions with constant actual parameters and potentially increasing the compilation time by several orders of magnitude (don't forget it might be attempting to do the same thing with system functions if the project is undergoing a full build).

Gareth

On Mon 09/07/18 01:21 , Dmitry Boyarintsev sent:
On Sun, Jul 8, 2018 at 7:18 PM, Thorsten Engler wrote:

Maybe you don’t understand what “determine the purity of a function” means?

It means that every time any function is called, the compiler has to try to execute the function at compile time (by working through the nodes like an interpreter) until it hits a point that is non-deterministic. This can potentially take forever (the halting problem is real!), so the only thing limiting it is basically some form of timeout (defined as either time spend or nodes traverse).

If you are talking about always considering every function as pure until proven otherwise, you are talking about slowing down the compiler by orders of magnitude.
I'm taking about considering every function that's **used to calculate a constant expression** as a pure function (not just every function).  (how many of:If FunctionCall(42) > 0 then
vsIf FunctionCall(x) > 0 then
is out there?)
Naturally, if a parameters of pure function are variable of any kind, the evaluation cannot be done in compile time anyway.
So, if a function (even if it's a pure function) is not used for constant expression valuation, there's no point in the actual "determination of purity" (in it's full meaning).
The compiler knows if a function potentially impure w/o the actual evaluation or interpretation, solely based on what data it's using.   Even if you deal with functions marked by a developer as "pure", the problem of full determination of purity remains.  thanks,Dmitry

I'm taking about considering every function that's **used to calculate a constant expression** as a pure function (not just every function). (how many of:
If FunctionCall(42) > 0 then
vs
If FunctionCall(x) > 0 then
is out there?)

Naturally, if a parameters of pure function are variable of any kind, the evaluation cannot be done in compile time anyway.

So, if a function (even if it's a pure function) is not used for constant expression valuation, there's no point in the actual "determination of purity" (in it's full meaning).

The compiler knows if a function potentially impure w/o the actual evaluation or interpretation, solely based on what data it's using.

Even if you deal with functions marked by a developer as "pure", the problem of full determination of purity remains.

thanks,
Dmitry

Loop unrolling is still a little bit shaky in places for Free Pascal, but if it can be sorted, then its combination with pure functions will offer even more performance enhancements. Granted, it may conflict slightly with vectorization.

"There were some time testing done with C++ language vs others, where C++ would beat anyone due to such optimization."

Challenge accepted!  Truthfully though, it's nothing to do with the language, but how clever the compiler is.  It just so happens that C++ gained the most attention.

Gareth

That's something for future research.  Initially I just want to get pure Pascal procedures working, and that's the most important since it's cross-platform.  Analysing assembler routines will require a different kind of interpretation, and it will likely involve only allowing a certain subset of opcodes and dropping out if it spots a memory operand that doesn't point to the local stack (unless it's a LEA instruction). For the first iteration, specifying 'pure' on a pure assembler routine will probably just throw a warning and ignore the directive, much like what currently happens with 'inline'.  I can see the use of pure, pure assembler routines (that's going to get confusing very quickly!) because of operations such as x86's ROR and BSR that don't have direct Pascal equivalents.

Gareth

On Mon 09/07/18 03:07 , "Dmitry Boyarintsev"
sent:

On Sun, Jul 8, 2018 at 8:15 PM, J. Gareth Moreton wrote: Yes, if any parameters are variables, then the function is not evaluated.  My intention is that the purity of a function is only determined when it comes to evaluating it in an expression, but because of how complex functions can become, the "pure" directive hints to the compiler that the given function is pure and it should attempt the laborous task of evaluating it, rather than the opposite approach of attempting to evaluate all functions with constant actual parameters and potentially increasing the compilation time by several orders of magnitude (don't forget it might be attempting to do the same thing with system functions if the project is undergoing a full build).
 if FPC assembler reader powerful enough to analyze and trust assembler functions marked as pure?
thanks,Dmitry

Thinking about it some more, this might also interact with loop unrolling.

e.g.:

for i := 0 to 9 do
  x := x * SomeFunc(i);

If the loop is being unrolled, what looks like a non-const expression becomes a const expression. So if SomeFunc is marked as pure, the compiler might be able to omit the call completely.

There were some time testing done with C++ language vs others, where C++ would beat anyone due to such optimization.

thanks,
Dmitry

I've only really researched and improved the peephole optimizer, which is the assembler stage.  I'm not sure how much optimisation is done at earlier stages, but I do know that care is taken in deciding the best implementation of a case block, for example, evaluating factors such as how many separate branches there are.
As it currently stands, pure function evaluation would be at the pre-compilation stage, where Pascal code is converted into platform-independent nodes.
Gareth

On Mon 09/07/18 03:33 , "R0b0t1" sent:
n Sun, Jul 8, 2018 at 9:07 PM, Dmitry Boyarintsev

evaluated.

> My intention is that the purity of a function is only determined when

it

> comes to evaluating it in an expression, but because of how complex > functions can become, the "pure" directive hints to the compiler that

the

> given function is pure and it should attempt the laborous task of

evaluating

> it, rather than the opposite approach of attempting to evaluate all > functions with constant actual parameters and potentially increasing

the

> compilation time by several orders of magnitude (don't forget it might

be

At which stages is optimization done? GCC's backend optimizes each step in compilation (as I am aware), i.e. GENERIC -> GIMPLE -> RTL -> assembly. Many optimizations work best or are only possible at a certain stage.

The various representations are also what makes analysis efficient. Most optimization passes do not happen on assembly.

On Sun, Jul 8, 2018 at 8:15 PM, J. Gareth Moreton <

if FPC assembler reader powerful enough to analyze and trust assembler functions marked as pure?

thanks,
Dmitry

n Sun, Jul 8, 2018 at 9:07 PM, Dmitry Boyarintsev

At which stages is optimization done? GCC's backend optimizes each step in compilation (as I am aware), i.e. GENERIC -> GIMPLE -> RTL -> assembly. Many optimizations work best or are only possible at a certain stage.

The various representations are also what makes analysis efficient. Most optimization passes do not happen on assembly.

Ryan Joseph schrieb am Mo., 9. Juli 2018,
08:45:

It would allow you to declare constants that use those functions with the compiler evaluating them at compile time.
Also the compiler might be able to optimize such functions better especially if they're inlined. *shrugs*

Regards,
Sven

Besides being able to assign the function
result to constants, the main benefit is
that, for constant inputs, the result is
deterministic and so the compiler can
calculate this beforehand and replace a
function call with an assignment. For
example, if tan was a regular function, x
:= tan(Pi / 2) might look like this in
assembly:

MOVAPD XMM0, Pi
DIVSD XMM0, TwoConstant
CALL tan ; Result is now in XMM0, which is
1

It won't be exactly that, but you get the
idea. If tan is defined as a pure
function, then the result can be pre-
calculated and the entire block changed to
a simple assignment:

MOVAPD XMM0, OneConstant ; value of tan(Pi
/ 2)

It doesn't take a genius to know that that
is faster by several orders of magnitude.

More subtly, if it turns out that the
function is never called with variable
arguments, the entire function can be
removed from the compiled binary, reducing
its size.

Gareth aka. Kit

On Mon 09/07/18 10:25 , Sven Barth via
fpc-devel
sent:

Ryan Joseph schrieb am Mo., 9. Juli

2018, 08:45:

> On Jul 8, 2018, at 8:50 AM, J. Gareth

Moreton wrote

> > With some blessing from Florian on the

concept, I've set up a Wiki page

discussing the design proposals for the

support of pure functions, as well

as some explanation on what they

actually are.

> What are the performance benefits? It

sounds like this is a proposal for a

compiler optimization which we can

explicitly opt in to, but what exactly

is the optimization? If nothing else I like the idea as a way

to enforce a function is not

accessing global state. Kind of like

const for functions.

It would allow you to declare constants

that use those functions with the

compiler evaluating them at compile

time. Also the compiler might be able

to optimize such functions better

especially if they're inlined. *shrugs*

Regards,  Sven 

I meant to say tan(Pi / 4) in that
example. Sorry. Trying to assign tan(Pi /
2) to something will probably cause an
error, or at the very least be an
interesting test case, because the result
is undefined.

Gareth aka. Kit

On Mon 09/07/18 12:00 , "J. Gareth
Moreton" sent:

Besides being able to assign the

function

x

is

the

to

tan(Pi

that

is faster by several orders of

magnitude.

reducing

Gareth

the

concept, I've set up a Wiki page > discussing the design proposals for

the

way

constants

__________________________________________

http://secureweb.fast.net.uk/parse.php?

I suppose the language I should have used was "reserved word." After having been explained that the token would only have special meaning in function declarations I feel a bit better, but would the highlighter also be context sensitive? The IDE has a habit of bolding valid identifiers for I think this very reason, and it is rather annoying. The supported dialects of Object Pascal is quite cluttered.

That can in part be attributed to the existence of Delphi mode...

I don't want to oppose all progress and think this is a worthwhile optimization, I would just ask that partially aesthetic issues like this be considered.

Cheers,
R0b0t1

On Jul 9, 2018, at 3:25 AM, Sven Barth via fpc-devel wrote: It would allow you to declare constants that use those functions with the compiler evaluating them at compile time.

That’s a double win then. Very good idea this is.

Regards,
Ryan Joseph

Just one question: doesn't all this new stuff introduce another kind of mess during cross-compiling?

E.g. some complex nested const.expr. "sin(cos(0.12345))" evaluated by the compiler on x64 (double precision) is not the same as if it would be evaluated by the compiled program itself running on some x32 (float80), or some future float128 alikes..

Either the compiler itself must eventually become fully softfloat-based??

Admittedly I have slightly selfish reasons for my proposed improvements. I like to play around with mathematical programming where loops can run for several days or weeks, so even the slimmest of savings adds up to a lot of saved time... and I love Object Pascal! Granted I can use assembly language for the most critical of code, something that 64-bit Visual C++ makes extremely difficult (plus there are always portability issues), but the more you can use a high-level language, the better.

Ideally, any mathematical function should be eligible for being pure, which is why I listed factorial as a goal. There will always be exceptions, of course, but that seems like a good benchmark.

Gareth aka. Kit

On Mon 09/07/18 15:39 , Ryan Joseph sent:

The intention is to perform the analysis of pure functions at the pre-compilation stage where all the Pascal code is transmuted into nodes, which are platform-independent and also have the advantage of not requiring total rebuilding of a project, since it is these nodes that are stored in PPU files. It may turn out that that is more difficult in practice, but that's the current theory.

Everything will be programmed in Pascal... no platform-specific assembly language (and I think that is a global rule with the Free Pascal Compiler because of cross compilation). I admit I'm not sure what will happen if you try to use floating-point numbers that the platform simply does not support, in which case, ANY program that uses them might run into problems. If floats are however emulated by the Free Pascal Compiler in these cases, then the same will happen when pre-calculating the functions.

Just for some extra fun - this is a video that shows the Ackermann Function being run on a relatively modern computer, and hence the importance of being able to catch functions that will take too long to compute (but which are still nonetheless "decidable"). https://www.youtube.com/watch?v=i7sm9dzFtEI&t=9m30s - I've done some calculations by hand, and shown that storing and recalling partial results to the Ackermann Function does reduce the amount of recursion required (e.g. when calculating A(3,2), it comes across 7 results from the function with smaller arguments that it can reuse later that can significantly cut down the processing requird), but there are still cases that are too ridiculous to work out, not least because the answer will cause an overflow (e.g. the result of A(4,2) has almost 20,000 decimal digits and, naïvely, takes longer than the age of the Universe to compute).

Gareth aka. Kit

On Mon 09/07/18 18:36 , "Thorsten Engler" sent:

How would that be any different from floating point consts currently that are defined with an expression involving calculations?

Yes, preferable float128 based. However, nobody volunteered so far do so.

sorry for this off-topic post but are you aware that your messages are not threading into the topic under discussion? every one of your posts looks like a separate thread and there's nothing to link it to the message you are actually responding to... looking at them, there's no references line(s) in your headers...

On Mon 09/07/18 20:53 , sent:

I saw this too. Unfortunately I use a webmail system and I fear there's little I can do about it. I'll try a few things to see if they work, but at the moment I'm not too hopeful. Sorry for it being so confusing.

I'm actually a bit surprised that this topic has caused such a huge discussion!

Gareth aka. Kit

On Mon 09/07/18 22:39 , "Bart" sent:

I'm aware that it can be calculated in less than that time, otherwise we wouldn't know what the answer was. But if done naïvely without algebraic shortcuts (e.g. A(1,n) = n + 2, A(2,n) = 2n + 3 and A(3,n) = 2^(n+3) - 3), then it does take that long. It's also something I doubt the compiler will be able to work out on the fly.

Gareth

J. Gareth Moreton wrote

out, not least because the answer will cause an overflow (e.g. the result of A(4,2) has almost 20,000 decimal digits and, naïvely, takes longer than the age of the Universe to compute).

Ackerman(4,2) = (2^65536) - 3 (it's explained int the follow up video), you can calculate that in less time than the age of the universe ....

Bart

Intermediate results may fall out of the compiler range capabilities, or introduce lost of precision in generated constant (e.g. Win64->Win32 cross-compiler is able to do only double-precision calculations, however the resulting program is fully float80-capable).
(Hopefully compiling will just fail with over/underflow, but I cannot check this right now).

In any case, I see no other but softfloat solution, as Florian already mention, and this would be a big performance impact, I suspect.. :(

Compile-time evaluation will always be a
performance hit for the compiler
unfortunately, even for the simplest of
algorithms, which is why I feel that only
those functions that the programmer says
are pure should be evaluated. If anyone
has ideas for performance enhancements
though, feel free to contribute to the
last section in the Wiki topic. Due to
cross compilation though, assembly
language can only be used in internal
functions available to the programmer
(e.g. the Frac function). The compiler
itself must be pure Pascal.

I primarily work with win64, as that's my
development platform, and the plan is to
have the emulator hopefully use hardware
floating point where available, but you
are right in that cross-compilation will
be quite the monster to debug!

float128 does sound like a good solution
overall. I'm not sure where to begin with
that though, or even what to call it for
Pascal, since "float128" is distinctly C-
like! It could be something to put on my
list of possible research projects!

Gareth aka. Kit

On Wed 11/07/18 12:12 , Max Nazhalov via
fpc-devel
sent:

Tue, 10 Jul 2018 03:36:01 +1000 Thorsten

new

precision) is

not the same as if it would >> be evaluated by the compiled program

itself

running on some x32 >> (float80), or some future float128

alikes..

> How would that be any different from

floating

point consts > currently that are defined with an

expression

involving calculations? Intermediate results may fall out of the

compiler range capabilities,

or introduce lost of precision in

generated constant (e.g. Win64->Win32

cross-compiler is able to do only

double-precision calculations, however

the resulting program is fully float80-

capable).

(Hopefully compiling will just fail with

over/underflow, but I cannot

softfloat solution, as Florian already

mention, and this would be a big

performance impact, I suspect.. :(

J. Gareth Moreton schrieb am Mi., 11. Juli
2018, 15:13:

The RTL has the ufloat128 unit which would then be used by the compiler.

Regards,
Sven

Thanks - I'll take a look to see if it's usable. Otherwise, any float128 type would probably be called "Quadruple" if we're going by the naming convention used in Object Pascal and Visual Basic, for example.

Gareth

On Wed 11/07/18 17:54 , "Sven Barth" sent: