47

Let’s say fn(x) is a pure function that does something expensive, like returning a list of the prime factors of x.

And let’s say we make a memoized version of the same function called memoizedFn(x). It always returns the same result for a given input, but it maintains a private cache of previous results to improve performance.

Formally speaking, is memoizedFn(x) considered pure?

Or is there some other name or qualifying term used to refer to such a function in FP discussions? (i.e. a function with side effects that may affect the computational complexity of subsequent calls but that may not affect the return values.)

  • 24
    Maybe it is not pure for purists, but "pure enough" for pragmatic people ;-) – Doc Brown Aug 26 at 13:45
  • 2
    @DocBrown I agree, just wondering if there’s a more formal term for ‘pure enough’ – callum Aug 26 at 13:46
  • 13
    Executing a pure function will most likely modify the processor's instruction cache, branch predictors etc. But that's probably "pure enough" for purists as well - or you can forget about pure functions altogether. – gnasher729 Aug 26 at 15:08
  • 10
    @callum No, there is no formal definition of "pure enough". When arguing about purity and the semantic equivalence of two "referentially transparent" calls, you always have to state exactly which semantics you are going to apply. At some low level of implementation detail it will always break down and have different memory effects or timings. That's why you have to be pragmatic: what level of detail is useful for reasoning about your code? – Bergi Aug 26 at 22:57
  • 3
    Then for the sake of pragmatism, I'd say that the purity depends on whether or not you consider computation time to be part of the output. funcx(){sleep(cached_time--); return 0;} returns the same val every time, but will perform differently – Mars Aug 27 at 0:45
41

Yes. The memoized version of a pure function is also a pure function.

All that function purity cares about is the effect that input parameters on the return value of the function (passing the same input should always produce the same output) and any side effects relevant to global states (e.g. text to the terminal or UI or network). Computation time and extra memory usages is irrelevant to function purity.

Caches of a pure function is pretty much invisible to the program; a functional programming language is allowed to automatically optimise a pure function to a memoized version of the function if it can determine that it'll be beneficial to do so. In practice, automatically determining when memoization is beneficial is actually quite a difficult problem, but such optimisation would be valid.

19

Wikipedia defines a "Pure Function" as a function that has the following properties:

  • Its return value is the same for the same arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams from I/O devices).

  • Its evaluation has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or I/O streams).

In effect, a pure function returns the same output given the same input, and doesn't affect anything else outside of the function. For purposes of purity, it doesn't matter how the function computes its return value, so long as it returns the same output given the same input.

Functionally pure languages like Haskell routinely use memoization to speed up a function by caching its previously computed results.

  • 16
    I might miss something, but how are you going to keep cache without side effects? – val Aug 27 at 0:01
  • 1
    By keeping it inside the function. – Robert Harvey Aug 27 at 0:15
  • 4
    "no mutation of local static variable" seems to exclude local variables persistent between calls as well. – val Aug 27 at 0:29
  • 3
    This doesn't actually answer the question, even if you seem to imply that yes, it is pure. – Mars Aug 27 at 0:34
  • 6
    @val You’re correct: this condition needs to be relaxed a bit. The purely-functional memoization he refers to has no visible mutation of any static data. What happens is that the result is then computed and memoized the first time the function is called, and returns the same value whenever it’s called. Many languages have an idiom for that: a static const local variable in C++ (but not C), or a lazily-evaluated data structure in Haskell. There is one more condition you need: the initialization must be thread-safe. – Davislor Aug 27 at 14:24
7

Yes, memoized pure functions are commonly referred to as pure. This is especially common in languages like Haskell, in which memoized, lazily-evaluated, immutable results are a built-in feature.

There is one important caveat: the memoizing function must be thread-safe, or else you might get a race condition when two threads both try to call it.

One example of a computer scientist using the term “purely functional” this way is this blog post by Conal Elliott about automatic memoization:

Perhaps surprisingly, memoization can be implemented simply and purely functionally in a lazy functional language.

There are many examples in the peer-reviewed literature, and have been for decades. For example, this paper from 1995, “Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems,” uses very similar language in section 5.2 to describe what we would today call a pure function:

Memoization only works for true functions, not procedures. That is, if a function’s result is not completely and deterministically specified by its input parameters, using memoization will give incorrect results. The number of functions that can be memoized successfully will be increased by encouraging the use of a functional programming style throughout the system.

Some imperative languages have a similar idiom. For example, a static const variable in C++ is initialized only once, before its value is used, and never mutates.

3

It depends on how you do it.

Usually people want to memoize by mutating some sort of cache dictionary. This has all the problems associated with impure mutation, such as having to worry about concurrency, worrying about the cache growing too large, etc.

However, you can memoize without impure memory mutation. One example is in this answer, where I track the memoized values externally by means of a lengths argument.

In the link Robert Harvey provided, lazy evaluation is used to avoid side effects.

Another technique sometimes seen is to explicitly mark the memoization as an impure side effect in the context of an IO type, such as with cats-effect's memoize function.

This last one brings up the point that sometimes the goal is just encapsulating mutation rather than eliminating it. Most functional programmers consider it "pure enough" to make impurity explicit and encapsulated.

If you want a term to differentiate it from a truly pure function, I think it's sufficient to just say "memoized with a mutable dictionary." That lets people know how to use it safely.

  • I don't think any of the purer solution solves the above problems: While you lose any concurrency worries, you also lose any chance for two concurrently started calls like collatz(100) and collatz(200) to cooperate. And IIUIC, the problem with cache growing too large remains (though Haskell may have some nice tricks for this?). – maaartinus Aug 26 at 23:16
  • Note: IO is pure. All impure methods on IO and Cats are named unsafe. Async.memoize is also pure, so we don't have to settle for "pure enough" :) – Samuel Aug 27 at 4:33
2

Usually, a function that returns a list is not pure at all because it requires allocation of storage and can thereby fail (e.g. by throwing an exception, which is non-pure). A language that has value types and can represent a list as a bounded-size value type may not have this issue. For this reason, your example is probably not pure.

In general, if the memoization can be done in a manner that's failure-case free (e.g. by having statically allocated storage for memoized results, and internal synchronization to control access to them if the language admits threads), it's reasonable to consider such a function pure.

0

You can implement memoization without side-effects using the state monad.

[State monad] is basically a function S => (S, A), where S is the type that represents your state and A is the result the function produces - Cats State.

In your case the state would be the memoized value or nothing (i.e. Haskell Maybe or Scala Option[A]). If the memoized value is present it is returned as A, otherwise A is calculated and returned as both the transitioned state and the result.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.