Re: More on Function Purity

Ville Oikarinen schrieb:
On Wed, 16 May 2007, Al wrote:

variable int V = GetTimeOfDay(); // runtime
... So, I would assume that a function *cannot* be pure if it:

* Reads from V; and/or

The code as a whole is not pure, because it uses a mutable variable. But
it's the variable itself (and the code that writes to it) that's impure,
not the function. The function just reads the variable, ignoring the fact
that it *could* be written, too. (Actually, writing to V only once in the
code could justify the whole code to be called pure, but at least the
function is pure.)

If you make V immutable, the code becomes pure functional *without changes
to the function*; therefore the function cannot be impure.

Actually, the function still is impure.
If fn() accesses V, and V is updated asynchronously, then
2*fn()
is semantically different from
fn()+fn()
and this at least breaks the "equational reasoning" kind of purity (and probably other definitions of purity, too).

In my book, purity is not a local property. It's a property of a function and the context it's executing in: guarantees about (im)mutability come into play, for example.

In this concrete case, V and any functions accessing it are impure, simply because V may be updated at any time.


If the updates are synchronous, anything that makes use of purity arguments (equational reasoning, compiler transforms, whatever) would have to be confined so that it does not span an evaluation step that updates V.
If the language syntactically or lexically identifies "islands of purity" between updates, then you can do equational reasoning within these islands, and the function is pure within them. If the language does not, then you'll have to do some kind of whole-system analysis to make sure that V isn't updated in the function or any functions called from it. (This can be a challenge, e.g. if the function in question is a HOF: executing a submitted function may update V, so you need dataflow analysis to determine that none of the functions submitted as parameters will ever update V - note that this kind of analysis is undecidable, so assuming that a function is impure if it accesses an impure variable is just a reasonable conservative approximation.)

(Although I find it somehow inconvenient to talk about pure functionality
using imperative code.)

In non-imperative code, it's difficult to have impure code in the first place, so you don't get to write impure examples.

I think the compile time/runtime evaluation question is not relevant here: a program that contains only expressions evaluatable at compile time is
not useful: you don't need to publish the program; the result it evaluates
to is enough :)

Compile-time evaluation cannot continue as soon as inputs are involved.
If the functions are pure, what you get after compile-time evaluation is a function that needs an input for the next reduction step.

Regards,
Jo
.

Relevant Pages

  • Re: More on Function Purity
    ... I would assume that a function *cannot* be pure if it: ... therefore the function cannot be impure. ... probably other definitions of purity, ... purity is not a local property. ...
    (comp.lang.functional)
  • Re: 3n+1 path records >18?
    ... All 0are pure, all 2are impure. ... So, for ANY number mod 18, we always know purity status for 16 ... But that wouldn't be a record, since the path record of 15 ...
    (sci.math)
  • Re: Pure Communism Has Never Been Tried
    ... we would have to weed out the bad people so that pure communism could ... We need purity. ... Of course the selection process for shipment to Earth was imperfect, and a few people who should not have been sent, were sent... ...
    (rec.games.go)
  • 3n+5 pures and impures!
    ... You stated that they be impure. ... tree in a hypothetical counter example would have ... to be pure wheather it be the smallest odd integer, ... sequential seed search where seed determines ...
    (sci.math)
  • Re: The Collatz discrete primes!
    ... an odd pure will trigger a counter example ... connected with this counter example has to be pure ... "Non-trivial" would be a tree rooted at the ... they are impure with respect to ...
    (sci.math)
Loading