Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I have question regarding pure functions. According to the Wikipedia page one of the requisites for a pure function is :
Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices.
Now what does this really mean. Or rather how can i make a side effect which is not semantically observable?
A semantics of a program is a model of its behavior which, like any scientific model, ignores aspects that you don't want to study.
An extremely detailed model of the execution of a program would model the physical behavior of the computer that executes it, including the execution time, power consumption, electromagnetic radiation, etc. Such aspects are very rarely taken into account because they are very rarely relevant. Nonetheless they do matter sometimes: a useful model of an airplane autopilot needs to include runtime information, a useful model of a credit card's security needs to include electromagnetic radiation, ...
In typical semantics, side effects such as timing and power consumption are ignored. Even if in a mundane setting where you type an expression at a Haskell interpreter prompt, the printing of the result is a side effect (if you try to print out an infinite object, it matters). If the Haskell interpreter runs out of memory, this is also an observable side effect in a “real-world” model, but not in an idealized model of Haskell that effectively allows unbounded computations.
An observable side effect is one which is modeled in the semantics. In typical models of programming languages, memory consumption is not modeled, so a computation that requires 1TB of storage can be pure, even though if you try to run it on your PC it would observably fail.
Another kind of non-observable side effect is one that is internal to the function. This is, I think, what most semanticists would think of when talking about non-observable side effects. Consider a computation that uses mutable data internally, but does not share this mutable data with any other part of the program. For example, a list sorting function which builds an array with the same elements as the list, sorts the array in place, and returns a list containing the elements as the array in their final order: a semantic model of subexpressions of this function exhibits side effects (modifications of the array), but the function itself has no external side effect, so it is pure.
For a more subtle example, consider a function that writes some data to a temporary file and cleans up after itself. In a semantics where there is always enough room for temporary files and programs do not share temporary files, the function has no side effect; the temporary file acts as extra memory used by the function. In a semantics which takes filesystem full conditions into account, the function has a side effect — it may fail due to external circumstances. In a semantics that allows the machine to crash, the function has a side effect: if there is a crash during the execution of the function, the temporary file may be left behind. In a semantics that allows concurrently executed programs to see and maybe modify the temporary file, the function has a side effect.
