[fpc-devel] Pure function Wiki page

[J. Gareth Moreton]

 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" thorsten.engler at 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-devel at 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:
------
[1] mailto:thorsten.engler at gmx.net
[2] mailto:fpc-devel at lists.freepascal.org
[3] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20180708/7614c16d/attachment.html>