Discussion:
Pure function Wiki page
(too old to reply)
J. Gareth Moreton
2018-07-08 14:50:03 UTC
Permalink
Raw Message
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
R0b0t1
2018-07-08 16:11:37 UTC
Permalink
Raw Message
On Sun, Jul 8, 2018 at 9:50 AM, J. Gareth Moreton
Post by J. Gareth Moreton
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
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
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.free
J. Gareth Moreton
2018-07-08 15:20:17 UTC
Permalink
Raw Message
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" ***@gmail.com sent:
On Sun, Jul 8, 2018 at 9:50 AM, J. Gareth Moreton
Post by J. Gareth Moreton
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
Post by J. Gareth Moreton
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
Post by J. Gareth Moreton
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
Dmitry Boyarintsev
2018-07-08 16:53:47 UTC
Permalink
Raw Message
On Sun, Jul 8, 2018 at 11:20 AM, J. Gareth Moreton <
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").

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
Florian Klämpfl
2018-07-08 17:01:05 UTC
Permalink
Raw Message
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").
procedure Random(l: LongInt):LongInt;
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.
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fp
Dmitry Boyarintsev
2018-07-08 19:11:17 UTC
Permalink
Raw Message
Post by Florian Klämpfl
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.
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
Marco van de Voort
2018-07-08 16:55:35 UTC
Permalink
Raw Message
Post by J. Gareth Moreton
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.
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/
Florian Klämpfl
2018-07-08 16:59:19 UTC
Permalink
Raw Message
Post by Marco van de Voort
Post by J. Gareth Moreton
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.
Why a preprocessor switch for something which applies to a particular function?
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fp
Ryan Joseph
2018-07-08 16:58:11 UTC
Permalink
Raw Message
Post by Marco van de Voort
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

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.
J. Gareth Moreton
2018-07-08 16:06:47 UTC
Permalink
Raw Message
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
Post by Marco van de Voort
Post by J. Gareth Moreton
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.
Why a preprocessor switch for something which applies to a particular
function?
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org [1]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[2]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel



Links:
------
[1] mailto:fpc-***@lists.freepascal.org
[2] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
J. Gareth Moreton
2018-07-08 16:15:12 UTC
Permalink
Raw Message
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
Post by J. Gareth Moreton
As far as I know, keywords are often used (e.g. "constexpr" in C++). 
My reasons are explained in the Wiki topic,
Post by J. Gareth Moreton
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").
Post by J. Gareth Moreton
procedure Random(l: LongInt):LongInt;
However, not having an extra modeswitch or new keywords would be
From the compiler performance perspective, the purity of a function
needs to be checked only when evaluating constant
Post by J. Gareth Moreton
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.
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org [1]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[2]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel



Links:
------
[1] mailto:fpc-***@lists.freepascal.org
[2] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Marco van de Voort
2018-07-08 17:33:31 UTC
Permalink
Raw Message
Post by Florian Klämpfl
Post by Marco van de Voort
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?
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-deve
Florian Klämpfl
2018-07-08 19:41:51 UTC
Permalink
Raw Message
Post by Marco van de Voort
Post by Florian Klämpfl
Post by Marco van de Voort
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.
No. It marks a function as usable in constant expressions (like sin/ln whatever).
Post by Marco van de Voort
I think having a directive is a bit too much honor.
Maybe it is time for an attribute system?
_______________________________________________
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepasc
R0b0t1
2018-07-08 21:22:06 UTC
Permalink
Raw Message
Post by Marco van de Voort
Post by Florian Klämpfl
Post by Marco van de Voort
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?
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
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-de
Thorsten Engler
2018-07-08 21:43:44 UTC
Permalink
Raw Message
-----Original Message-----
R0b0t1
Sent: Monday, 9 July 2018 07:22
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.
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

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://l
Dmitry Boyarintsev
2018-07-08 22:38:47 UTC
Permalink
Raw Message
Post by Thorsten Engler
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.
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
Thorsten Engler
2018-07-08 22:47:49 UTC
Permalink
Raw Message
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.



From: fpc-devel <fpc-devel-***@lists.freepascal.org> On Behalf Of Dmitry Boyarintsev
Sent: Monday, 9 July 2018 08:39
To: FPC developers' list <fpc-***@lists.freepascal.org>
Subject: Re: [fpc-devel] Pure function Wiki page



On Sun, Jul 8, 2018 at 5:43 PM, Thorsten Engler <***@gmx.net <mailto:***@gmx.net> > wrote:

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.



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
Dmitry Boyarintsev
2018-07-08 23:00:13 UTC
Permalink
Raw Message
Post by Thorsten Engler
const
x = FunctionCall(42);
In which case, yes, the compiler could possibly see that as in implicit
“check if that function is pure”.
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
Thorsten Engler
2018-07-08 23:18:20 UTC
Permalink
Raw Message
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 <fpc-devel-***@lists.freepascal.org> On Behalf Of Dmitry Boyarintsev
Sent: Monday, 9 July 2018 09:00
To: FPC developers' list <fpc-***@lists.freepascal.org>
Subject: Re: [fpc-devel] Pure function Wiki page



On Sun, Jul 8, 2018 at 6:47 PM, Thorsten Engler <***@gmx.net <mailto:***@gmx.net> > 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
Dmitry Boyarintsev
2018-07-09 00:21:14 UTC
Permalink
Raw Message
Post by Thorsten Engler
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
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
R0b0t1
2018-07-09 14:22:57 UTC
Permalink
Raw Message
Post by Thorsten Engler
-----Original Message-----
R0b0t1
Sent: Monday, 9 July 2018 07:22
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.
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.
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
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.
J. Gareth Moreton
2018-07-08 16:41:55 UTC
Permalink
Raw Message
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
Post by Florian Klämpfl
Post by Marco van de Voort
It doesn't explain why you chose for a modifier rather than
preprocessor
Post by Florian Klämpfl
Post by Marco van de Voort
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?
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org [1]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[2]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel



Links:
------
[1] mailto:fpc-***@lists.freepascal.org
[2] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Martin
2018-07-08 18:00:17 UTC
Permalink
Raw Message
Post by J. Gareth Moreton
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 results at runtime.

   b := 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?
J. Gareth Moreton
2018-07-08 17:19:43 UTC
Permalink
Raw Message
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 ***@mfriebe.de 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 results at runtime.
 
   b := 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?

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



Links:
------
[1] mailto:fpc-***@lists.freepascal.org
[2] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
J. Gareth Moreton
2018-07-08 17:22:42 UTC
Permalink
Raw Message
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" ***@moreton-family.com
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 ***@mfriebe.de 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 results at runtime.
 
   b := 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?

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

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



Links:
Martin
2018-07-08 18:52:02 UTC
Permalink
Raw Message
Post by J. Gareth Moreton
At the same time, I would argue that, really, the programmer should
c := sin(x);
if c > y then b := c;
There probably isn't any harm in supporting such optimisation though.
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.

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc
J. Gareth Moreton
2018-07-08 21:22:20 UTC
Permalink
Raw Message
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"
Post by R0b0t1
-----Original Message-----
From: fpc-devel On Behalf Of
R0b0t1
Sent: Monday, 9 July 2018 07:22
There were some other comments
touching on
Post by R0b0t1
reasons for or against a
keyword, and I apologize for not
speaking to
Post by R0b0t1
them precisely. But,
this is why I would like to avoid a
keyword - it
Post by R0b0t1
is redundant.
People keep talking about keywords. As
shown in the examples, pure is not a
Post by R0b0t1
keyword. It's a context-sensitive
directive. This is already wrongly stated
Post by R0b0t1
in the proposal itself (so people can be
excused for picking up on the use
Post by R0b0t1
of the term "keyword" in the proposal)
and it should be fixed (in
Post by R0b0t1
the proposal).
And it's not redundant. You are telling
the compiler: I want this function
Post by R0b0t1
to be pure. Please tell me if I made a
mistake.
Post by R0b0t1
Cheers,
Thorsten
__________________________________________
_____
Post by R0b0t1
fpc-devel maillist - fpc-
http://lists.freepascal.org/cgi-
bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mail
J. Gareth Moreton
2018-07-08 22:43:30 UTC
Permalink
Raw Message
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" ***@gmx.net 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 _______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org [2]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[3]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel



Links:
J. Gareth Moreton
2018-07-08 22:49:10 UTC
Permalink
Raw Message
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 ***@gmail.com 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 _______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org [2]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[3]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel



Links:
J. Gareth Moreton
2018-07-09 00:15:21 UTC
Permalink
Raw Message
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 ***@gmail.com 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
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org [2]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[3]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel



Links:
Thorsten Engler
2018-07-09 01:47:51 UTC
Permalink
Raw Message
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.



From: fpc-devel <fpc-devel-***@lists.freepascal.org> On Behalf Of J. Gareth Moreton
Sent: Monday, 9 July 2018 10:15
To: FPC developers' list <fpc-***@lists.freepascal.org>
Subject: Re: [fpc-devel] Pure function Wiki page



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 ***@gmail.com <mailto:***@gmail.com> sent:

On Sun, Jul 8, 2018 at 7:18 PM, Thorsten Engler <***@gmx.net <mailto:***@gmx.net> > 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

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



_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org <mailto:fpc-***@lists.freepascal.org>
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
Dmitry Boyarintsev
2018-07-09 01:54:32 UTC
Permalink
Raw Message
Post by Thorsten Engler
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
Dmitry Boyarintsev
2018-07-09 02:07:46 UTC
Permalink
Raw Message
Post by Thorsten Engler
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
R0b0t1
2018-07-09 02:33:12 UTC
Permalink
Raw Message
n Sun, Jul 8, 2018 at 9:07 PM, Dmitry Boyarintsev
On Sun, Jul 8, 2018 at 8:15 PM, J. Gareth Moreton
Post by Thorsten Engler
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?
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.
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/l
J. Gareth Moreton
2018-07-09 01:05:56 UTC
Permalink
Raw Message
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
J. Gareth Moreton
2018-07-09 01:33:10 UTC
Permalink
Raw Message
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" ***@gmail.com
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
J. Gareth Moreton
2018-07-09 02:00:47 UTC
Permalink
Raw Message
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" ***@gmail.com sent:
n Sun, Jul 8, 2018 at 9:07 PM, Dmitry Boyarintsev
On Sun, Jul 8, 2018 at 8:15 PM, J. Gareth Moreton
Post by J. Gareth Moreton
Yes, if any parameters are variables, then the function is not
evaluated.
Post by J. Gareth Moreton
My intention is that the purity of a function is only determined when
it
Post by J. Gareth Moreton
comes to evaluating it in an expression, but because of how complex
functions can become, the "pure" directive hints to the compiler that
the
Post by J. Gareth Moreton
given function is pure and it should attempt the laborous task of
evaluating
Post by J. Gareth Moreton
it, rather than the opposite approach of attempting to evaluate all
functions with constant actual parameters and potentially increasing
the
Post by J. Gareth Moreton
compilation time by several orders of magnitude (don't forget it might
be
Post by J. Gareth Moreton
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?
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
2018-07-08 16:27:30 UTC
Permalink
Raw Message
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

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/
Sven Barth via fpc-devel
2018-07-09 09:25:35 UTC
Permalink
Raw Message
Post by J. Gareth Moreton
Post by J. Gareth Moreton
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
Ryan Joseph
2018-07-09 14:39:51 UTC
Permalink
Raw Message
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

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-d
J. Gareth Moreton
2018-07-09 11:00:53 UTC
Permalink
Raw Message
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
Ryan Joseph schrieb am Mo., 9. Juli
On Jul 8, 2018, at 8:50 AM, J. Gareth
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 
__________________________________________
_____
fpc-devel maillist - fpc-
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
J. Gareth Moreton
2018-07-09 11:11:36 UTC
Permalink
Raw Message
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
Post by J. Gareth Moreton
Besides being able to assign the
function
Post by J. Gareth Moreton
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
Post by J. Gareth Moreton
:= tan(Pi / 2) might look like this in
MOVAPD XMM0, Pi
DIVSD XMM0, TwoConstant
CALL tan ; Result is now in XMM0, which
is
Post by J. Gareth Moreton
1
It won't be exactly that, but you get
the
Post by J. Gareth Moreton
idea. If tan is defined as a pure
function, then the result can be pre-
calculated and the entire block changed
to
Post by J. Gareth Moreton
MOVAPD XMM0, OneConstant ; value of
tan(Pi
Post by J. Gareth Moreton
/ 2)
It doesn't take a genius to know that
that
Post by J. Gareth Moreton
is faster by several orders of
magnitude.
Post by J. Gareth Moreton
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
Post by J. Gareth Moreton
its size.
Gareth aka. Kit
On Mon 09/07/18 10:25 , Sven Barth via
Ryan Joseph schrieb am Mo., 9. Juli
On Jul 8, 2018, at 8:50 AM, J.
Gareth
Post by J. Gareth Moreton
With some blessing from Florian on
the
Post by J. Gareth Moreton
concept, I've set up a Wiki page
discussing the design proposals for
the
Post by J. Gareth Moreton
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
Post by J. Gareth Moreton
to enforce a function is not
accessing global state. Kind of like
const for functions.
It would allow you to declare
constants
Post by J. Gareth Moreton
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 
__________________________________________
Post by J. Gareth Moreton
_____
fpc-devel maillist - fpc-
de
http://lists.freepascal.org/cgi-
bin/mailman/listinfo/fpc-devel [1]
------
[1]
http://secureweb.fast.net.uk/parse.php?
Post by J. Gareth Moreton
redirect=http://lists.freepascal.org
/cgi-bin/mailman/listinfo/fpc-devel
__________________________________________
_____
Post by J. Gareth Moreton
fpc-devel maillist - fpc-
http://lists.freepascal.org/cgi-
bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://list
Max Nazhalov via fpc-devel
2018-07-09 16:24:57 UTC
Permalink
Raw Message
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??
--
WBR,
Max

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org
Thorsten Engler
2018-07-09 17:36:01 UTC
Permalink
Raw Message
-----Original Message-----
Max Nazhalov via fpc-devel
Sent: Tuesday, 10 July 2018 02:25
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..
How would that be any different from floating point consts currently that are defined with an expression involving calculations?

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi
Florian Klaempfl
2018-07-09 18:07:39 UTC
Permalink
Raw Message
Post by Max Nazhalov via fpc-devel
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??
Yes, preferable float128 based. However, nobody volunteered so far do so.
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-de
J. Gareth Moreton
2018-07-09 16:30:18 UTC
Permalink
Raw Message
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 Jul 9, 2018, at 3:25 AM, Sven Barth via
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
_______________________________________________
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailm
w***@windstream.net
2018-07-09 19:53:53 UTC
Permalink
Raw Message
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...
--
NOTE: No off-list assistance is given without prior approval.
*Please keep mailing list traffic on the list unless*
*a signed and pre-paid contract is in effect with us.*
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://l
J. Gareth Moreton
2018-07-09 16:59:24 UTC
Permalink
Raw Message
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").
-
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
Post by Max Nazhalov via fpc-devel
-----Original Message-----
From: fpc-devel On Behalf Of
Max Nazhalov via fpc-devel
Sent: Tuesday, 10 July 2018 02:25
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..
How would that be any different from floating point consts currently that
are defined with an expression involving calculations?
_______________________________________________
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mai
Bart
2018-07-09 21:39:09 UTC
Permalink
Raw Message
On Mon, Jul 9, 2018 at 6:59 PM, J. Gareth Moreton
Post by J. Gareth Moreton
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
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mail
J. Gareth Moreton
2018-07-09 21:16:50 UTC
Permalink
Raw Message
Post by w***@windstream.net
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...
--
NOTE: No off-list assistance is given without prior approval.
*Please keep mailing list traffic on the list unless*
*a signed and pre-paid contract is in effect with us.*
_______________________________________________
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
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
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mai
J. Gareth Moreton
2018-07-09 21:17:35 UTC
Permalink
Raw Message
Post by Bart
On Mon, Jul 9, 2018 at 6:59 PM, J. Gareth Moreton
<gar
Post by J. Gareth Moreton
out, not least because the answer will cause an
overflow (e.g. the result of
Post by J. Gareth Moreton
A(4,2) has almost 20,000 decimal digits and,
naïvely, takes longer than the age
Post by J. Gareth Moreton
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
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
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/
Max Nazhalov via fpc-devel
2018-07-11 11:12:40 UTC
Permalink
Raw Message
Post by Thorsten Engler
-----Original Message-----
Max Nazhalov via fpc-devel
Sent: Tuesday, 10 July 2018 02:25
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..
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
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.. :(
--
Best regards,
Max mailto:***@mail.ru

_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://l
J. Gareth Moreton
2018-07-11 12:12:31 UTC
Permalink
Raw Message
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
Tue, 10 Jul 2018 03:36:01 +1000 Thorsten
Post by Thorsten Engler
-----Original Message-----
From: fpc-devel On Behalf Of
Max Nazhalov via fpc-devel
Sent: Tuesday, 10 July 2018 02:25
Just one question: doesn't all this
new
stuff introduce another kind
Post by Thorsten Engler
of mess during cross-compiling?
E.g. some complex nested const.expr.
"sin(cos(0.12345))" evaluated by
Post by Thorsten Engler
the compiler on x64 (double
precision) is
not the same as if it would
Post by Thorsten Engler
be evaluated by the compiled program
itself
running on some x32
Post by Thorsten Engler
(float80), or some future float128
alikes..
Post by Thorsten Engler
How would that be any different from
floating
point consts
Post by Thorsten Engler
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
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.. :(
--
Best regards,
Max stein_no
__________________________________________
_____
fpc-devel maillist - fpc-
http://lists.freepascal.org/cgi-
bin/mailman/listinfo/fpc-devel
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-b
Sven Barth via fpc-devel
2018-07-11 16:54:00 UTC
Permalink
Raw Message
Post by J. Gareth Moreton
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!
The RTL has the ufloat128 unit which would then be used by the compiler.

Regards,
Sven
J. Gareth Moreton
2018-07-11 17:32:25 UTC
Permalink
Raw Message
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
Post by J. Gareth Moreton
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!
The RTL has the ufloat128 unit which would then be used by the compiler. 
Regards, Sven 
_______________________________________________
fpc-devel maillist - fpc-***@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailma

Loading...