<p>An idea I had for one of my languages recently was this: function purity makes it easier to do certain optimizations. However, the language I'm designing is an impure imperative language that has an implicit purity checker. The model of purity is pretty restrictive, as in <a href="https://languagedesign.stackexchange.com/a/1033/45">this answer</a>. That's fine because purity is implicit, and not exposed to the end user. When the language manages to catalog the pure functions, it can then apply stuff like constant folding, compile-time memoization, and loop hoisting with those functions. Are there any downsides to my idea?</p>
<p>Bonus question: do any languages actually do this?</p>

<implementation><optimization><pure-functions>
What are the downsides, if any, of using implicit function purity in an impure language?
<p>Even if purity is only used for optimisations, users may still rely on those optimisations such that it's an unacceptable performance regression if the same code ceases to be optimisable. There is also the reverse case, where the correctness of a library function depends on a user-provided callback function being pure, where it's better for everyone involved if this is a checked part of the API.</p>
<p>If users will rely on a function being pure (either for correctness or performance), then purity is a part of a library's API. Having it be explicit (e.g. with different keywords for pure functions vs. impure procedures) makes this fact obvious to readers, allows it to be included in generated documentation, and allows the compiler to detect when a promise of purity is broken. If such promises only exist in documentation comments then they can't be checked.</p>
<hr />
<p>The same issue about purity being part of the API also affects dynamic linking. Suppose module A makes a call to a function from module B within a loop. If the function happens to be pure (as an implementation detail), then module A may be compiled with the function call hoisted out of the loop, but still dynamically linked to module B.</p>
<p>If module B is changed so that the function is no longer pure, then module A must be recompiled or its behaviour will be incorrect, even though the function's signature in module B didn't change ─ that is, it's harder for the author of module B to know whether a change will break code which depends on it.</p>
<p>While this issue could be addressed by compiling module A without the assumption that the dynamically-linked function is pure, addressing it by making purity explicit allows for your performance optimisations to be applied across modules.</p>
<hr />
<p>There is also a minor issue of compiler performance: it is faster to check only functions labelled as pure, rather than infer for all functions whether they are pure.</p>

CC BY-SA 4.0
2023-06-20T16:10:26.987Z
2023-06-20T16:10:26.987Z
kaya3
CC BY-SA 4.0
2023-06-20T17:48:14.487Z
Hrm, I thought my plan was bulletproof... this is what this site exists for lol
Seggan
CC BY-SA 4.0
2023-06-20T18:06:03.973Z
@Seggan I mean, it's still a decent plan, and all of the points raised in this answer can be accepted as limitations (or perhaps addressed in other ways, e.g. by doing these optimisations in a JIT instead of AOT) if that's how you want your language to work.
kaya3
CC BY-SA 4.0
2023-06-20T18:44:28.190Z
@Seggan you could address this point by adding an optional way to signify purity. Then the compiler could complain if it cannot prove purity for an explicitly marked function
abel1502
<p>rather than tracking purity, you may want to track at a more granular level. Julia added an effects system in 1.8 that has been very nice for compile and runtime performance. it tracks a number of properties:</p>
<ol>
<li>consistency (can other functions mess with you)</li>
<li>effect free (can you mess with data seen by others)</li>
<li>nothrow (might you throw an exception)</li>
<li>termination.</li>
</ol>
<p>this separation is important because (for example) dead code does not need to be consistent to be removed (but it does need to be nothrow), while computer time memoization is fine with code that throws but requires code to probably terminate.</p>

CC BY-SA 4.0
2023-07-18T04:48:36.300Z
2023-07-18T04:48:36.300Z
Oscar Smith
<p>In many cases, what may be more useful than specifying that a function is pure, may be a means of indicating that if a program's inputs will cause a certain function to be invoked with certain values, a compiler's generated code may, at the compiler's leisure, call the function with those values any number of times it sees fit, whenever it sees fit, except that timing of such calls might be limited by certain sequencing directives.</p>
<p>Note that any function which is free of outside side effects would naturally satisfy this criterion, but the criterion also applies to many functions which are not pure, but could benefit from the same optimizations as pure functions.</p>
<p>While it might be useful for compilers to recognize functions that can be easily proven to be pure, I think it would in general be better to have programs specify which functions specify the earlier-mentioned criterion regarding sequencing.  If treating a function as &quot;pure&quot; would result in a compiler performing optimizations that swap the order in which two log entries get generated, but both orderings would be equally acceptable, a compiler could easily perform the optimizations if it was <em>told</em> that such reordering was acceptable, but could not be expected to accurately know when such orderings would be acceptable,</p>

CC BY-SA 4.0
2023-07-16T18:05:21.240Z
2023-07-16T18:05:21.240Z
supercat
CC BY-SA 4.0
2023-07-17T01:57:04.450Z
Log entries are a side effect; therefore the example is moot, as pure functions cannot log
Seggan
CC BY-SA 4.0
2023-07-17T15:02:19.167Z
@Seggan-OnStrike: If one draws a three-way partition: "Functions with side effects that are necessary for correctness; those without any side effects that are relevant to application correctness; those without any side-effects whatsoever", I would view the second category as being useful more often than the third.  If one is e.g. trying to identify performance problems, being able to tell how often an "essentially pure" function is called may be a necessary part of that.  Having to mark a function as impure in order to add logging would defeat the whole purpose of profiling.
supercat
# What are the downsides, if any, of using implicit function purity in an impure language?
Posted by: username_0 on 2023-06-20
An idea I had for one of my languages recently was this: function purity makes it easier to do certain optimizations. However, the language I'm designing is an impure imperative language that has an implicit purity checker. The model of purity is pretty restrictive, as in [this answer](https://languagedesign.stackexchange.com/a/1033/45). That's fine because purity is implicit, and not exposed to the end user. When the language manages to catalog the pure functions, it can then apply stuff like constant folding, compile-time memoization, and loop hoisting with those functions. Are there any downsides to my idea?

Bonus question: do any languages actually do this?
**Tags:** implementation optimization pure-functions
---
## 3 answers
### Answer by username_1 on 2023-06-20. Score: 6
Even if purity is only used for optimisations, users may still rely on those optimisations such that it's an unacceptable performance regression if the same code ceases to be optimisable. There is also the reverse case, where the correctness of a library function depends on a user-provided callback function being pure, where it's better for everyone involved if this is a checked part of the API.

If users will rely on a function being pure (either for correctness or performance), then purity is a part of a library's API. Having it be explicit (e.g. with different keywords for pure functions vs. impure procedures) makes this fact obvious to readers, allows it to be included in generated documentation, and allows the compiler to detect when a promise of purity is broken. If such promises only exist in documentation comments then they can't be checked.

---

The same issue about purity being part of the API also affects dynamic linking. Suppose module A makes a call to a function from module B within a loop. If the function happens to be pure (as an implementation detail), then module A may be compiled with the function call hoisted out of the loop, but still dynamically linked to module B.

If module B is changed so that the function is no longer pure, then module A must be recompiled or its behaviour will be incorrect, even though the function's signature in module B didn't change ─ that is, it's harder for the author of module B to know whether a change will break code which depends on it.

While this issue could be addressed by compiling module A without the assumption that the dynamically-linked function is pure, addressing it by making purity explicit allows for your performance optimisations to be applied across modules.

---

There is also a minor issue of compiler performance: it is faster to check only functions labelled as pure, rather than infer for all functions whether they are pure.
> **Comments:**
> **username_0** (2023-06-20): Hrm, I thought my plan was bulletproof... this is what this site exists for lol  
> **username_1** (2023-06-20): @Seggan I mean, it's still a decent plan, and all of the points raised in this answer can be accepted as limitations (or perhaps addressed in other ways, e.g. by doing these optimisations in a JIT instead of AOT) if that's how you want your language to work.  
> **username_2** (2023-06-20): @Seggan you could address this point by adding an optional way to signify purity. Then the compiler could complain if it cannot prove purity for an explicitly marked function  
---
### Answer by username_4 on 2023-07-16. Score: 3
In many cases, what may be more useful than specifying that a function is pure, may be a means of indicating that if a program's inputs will cause a certain function to be invoked with certain values, a compiler's generated code may, at the compiler's leisure, call the function with those values any number of times it sees fit, whenever it sees fit, except that timing of such calls might be limited by certain sequencing directives.

Note that any function which is free of outside side effects would naturally satisfy this criterion, but the criterion also applies to many functions which are not pure, but could benefit from the same optimizations as pure functions.

While it might be useful for compilers to recognize functions that can be easily proven to be pure, I think it would in general be better to have programs specify which functions specify the earlier-mentioned criterion regarding sequencing. If treating a function as "pure" would result in a compiler performing optimizations that swap the order in which two log entries get generated, but both orderings would be equally acceptable, a compiler could easily perform the optimizations if it was *told* that such reordering was acceptable, but could not be expected to accurately know when such orderings would be acceptable,
> **Comments:**
> **username_0** (2023-07-17): Log entries are a side effect; therefore the example is moot, as pure functions cannot log  
> **username_4** (2023-07-17): @Seggan-OnStrike: If one draws a three-way partition: "Functions with side effects that are necessary for correctness; those without any side effects that are relevant to application correctness; those without any side-effects whatsoever", I would view the second category as being useful more often than the third.  If one is e.g. trying to identify performance problems, being able to tell how often an "essentially pure" function is called may be a necessary part of that.  Having to mark a function as impure in order to add logging would defeat the whole purpose of profiling.  
---
### Answer by username_3 on 2023-07-18. Score: 2
rather than tracking purity, you may want to track at a more granular level. Julia added an effects system in 1.8 that has been very nice for compile and runtime performance. it tracks a number of properties:

1. consistency (can other functions mess with you)
2. effect free (can you mess with data seen by others)
3. nothrow (might you throw an exception)
4. termination.

this separation is important because (for example) dead code does not need to be consistent to be removed (but it does need to be nothrow), while computer time memoization is fine with code that throws but requires code to probably terminate.
---
