Item — HN Reader

> A pure function only looks at the parameters passed in to it, and all it does is return one or more computed values based on the parameters. It has no logical side effects. This is an abstraction of course; every function has side effects at the CPU level, and most at the heap level, but the abstraction is still valuable.

Rereading this for the umpteenth time, this is the paragraph which sticks out to me this time around, and a point which I think most people miss, specifically the latter part about “pure” functions consuming CPU and memory.

The reality is that there is no such thing as a “pure” function, insofar as execution of that function costs something. Certain functional programmers corrupted this idea to somehow mean pure functions are free; that these functions can be executed one to infinity times and the result is the same.

For instance, this idea taken to an extreme has resulted in the current situation with React.js, where most React applications pathologically over-execute the “pure” rendering functions which we use to define components, resulting in degraded performance, increased GC pressure, and a lack of understanding of how our code executes.

Just because you can call a pure function many times doesn’t mean you should.

5 comments

> Certain functional programmers corrupted this idea to somehow mean pure functions are free; that these functions can be executed one to infinity times and the result is the same.

I think you are conflating two things and attacking a strawperson. As someone who is very involved in the functional programming community, I've never heard anyone say that pure functions are "free", and if this has been said it's certainly not the majority perspective. The fact that a function gives you the same result given the same arguments is not meant to be some kind of encouragement to redundantly call a function many times. It's meant to give you a tool to better reason about the program logically. You don't have to worry about _when_ a pure function is called, because it doesn't depend on hidden state that may change over time, and it doesn't change anything about its environment.

In a sense, I think you seem to have been given the _opposite_ idea (not necessarily saying it was your misunderstanding vs. someone else poorly communicating to you); the fact that a function always gives you consistent results means that you never have to invoke it multiple times. In some sense, this viewpoint recognizes the cost of function execution even more than the zeitgeist.

I’m assuming the “free” part is referring to referential transparency. I may have wildly misunderstood that and they may be even more mislead. But when referential transparency is assured, one of the promises of FP is that repeated calls to expensive functions can be optimized. Like I said in my sibling comment, the important part of that promise is can. If a runtime or compiler is able to flag a pure function as expensive, it can automatically memoize it (of course then trading memory space for computation time).

> The fact that a function gives you the same result given the same arguments is not meant to be some kind of encouragement to redundantly call a function many times.

All pure functions are by definition idempotent, and this quality is often celebrated as yet another point of merit. What is the point of highlighting this quality if functional programmers do not expect to over-execute them?

> It's meant to give you a tool to better reason about the program logically. You don't have to worry about _when_ a pure function is called…

If you say you don’t have to worry about when a function is called, the implication is that you don’t have to worry about how many times that function has been called. Functional programmers tend to belittle this sort of reasoning, and yet this sort of reasoning continues to be necessary when evaluating long-running, interactive programs for correctness.

This downplaying of executional reasoning is precisely why even if using pure functions on their own doesn’t encourage overexecution, the systems which functional programmers build typically do. We see this most clearly in discussions of reactivity, the fetishization of spreadsheets as programming model. Discrete events are tranformed into discrete outputs in a many-to-many relationship and yet functional programmers continue to think it’s not important to reason about the code which executed in between, the when and how much, just because it’s a composition of pure functions.

// stateful impl

class foo{ enum current_operator;

    init() { current_operator = ADD }

    evalOp(int a, int b){
        if (current_operator == ADD) return a + b;
        else if (current_operator == MULTIPLY) return a * b;
    }

    setOp(enum op){ current_operator = op; }

}

// pure impl

class bar{

    evalOp(enum op, int a, int b){

        if (op == ADD) return a + b;
        else if (op == MULTIPLY) return a * b;
    }

}

In the first case, evalOp is not pure since one has no idea on what is the current_operator set as. In the second case it is pure since the operator is part of the input.

Purity refers to reproducibility, as in no matter what else is going on, that function will always behave the same. You can have pure functions in OOP based languages, but in practice devs just default to managing state and having weird behavior depending on outside state of a given function.

As a side note, and since you mention runtime performance cost: if you implement a dummy generic cache layer and you have pure functions you will have an easier time than having stateful impls. In this case, that cache layer must have the ability to introspect into foo, but in bar that cache layer just keeps track of input and that's it.

Tangential:

Pure impl v2:

  class foo {
  public:
    //enum is a keyword, so let's call it _enum
    const _enum current_operator;
    foo(_enum co) : current_operator(co) { }
  // ... evalOp() as in your stateful impl example ...
  };

  //Example use:
  Reduce(foo{ADD}, 1, 2, 3, 4, 5, 6);

Point being, functional purity doesn't necessarily mean only functions taking all their inputs as arguments. It means no mutable state. In the above example, the class foo essentially represents a partially applied evalOp(). If you have multiple, related functions working on similar sets of parameters, you could put them in such a class with const members to create what is essentially a package of partially applied functions.

Pureness also makes it easier to remove calls to a function. If f is a pure function, then I know that if x, y or z doesn't change, then I never need to call f(x, y, z) again.

(Idempotence means f(f(x)) = f(x), whereas purity means f(x) = f(x).)

All pure functions are idempotent but not all idempotent functions are pure. It has nothing to do with the domain/range of the function.

You are correct in that there is a definition of idempotence that agrees with you, but you are wrong to correct the parent comment, because the most common mathematical definition of idempotence of functions agrees with them (and not you).

There are multiple definitions of idempotence, used even within computer science, and neither of you seem to be aware of the definition used by the other. The common mathematical definition of an idempotent function is that f(f(x)) = f(x) for all x. But in computer science there is another common definition which involves side effects not being repeated (that is, `f(); f();` is the same as `f();`).

> But in computer science there is another common definition which involves side effects not being repeated (that is, `f(); f();` is the same as `f();`).

where have you ever seen that definition ?!

> in imperative programming, a subroutine with side effects is idempotent if the system state remains the same after one or several calls

https://en.wikipedia.org/wiki/Idempotence#Computer_science_m...

It’s used commonly when working with unreliable communication (e.g. networking). For example, if you make a request but you don’t get a response, either the request or the response might have failed to send. It’s convenient if you don’t need to determine which case occurred; idempotent functions free you from worrying about whether the requested action was carried out.

> Certain functional programmers corrupted this idea to somehow mean pure functions are free; that these functions can be executed one to infinity times and the result is the same.

I'd be very curious to read someone claiming anything of this sort. One benefit (with respect to the CPU) of pure functions is that they can be cached because you know you'll get the same result for each call (of course, this impacts memory), which you can't guarantee with impure functions. But that's a tradeoff of memory for time. I've never seen anyone claim there's no cost to a pure function.

When we say “pure functions are free” out loud, of course it seems categorically false, and I don’t think anyone has ever credibly argued for this claim. And yet I think it is an implicit assumption of a lot of functional programming development, specifically that which attempts to build “referentially transparent” systems on top of an imperative, impure systems and languages, rather than starting with a new language from scratch.

My example of React.js is the pinnacle of this, all features like hooks, contexts, and concurrent mode only make sense when they estimate the cost of re-executing pure functions to be free, or at least negligible, and yet real-world experience indicates this is definitely not the case.

> One benefit (with respect to the CPU) of pure functions is that they can be cached because you know you'll get the same result for each call (of course, this impacts memory), which you can't guarantee with impure functions. But that's a tradeoff of memory for time.

In my personal experience, I’ve become pretty skeptical of trading memory for execution time. Especially in garbage-collected languages, what you save in execution time you lose in GC pauses, so the end result is you get neither.

Caching is and will continue to be a core building block of performance in current sw (and hw) systems. And it's a boon when you have a tool to fix one of the two hard problems[1].

[1] The famous quote: "There are only two hard things in Computer Science: cache invalidation and naming things." (attributed to Phil Karlton)

> Especially in garbage-collected languages, what you save in execution time you lose in GC pauses, so the end result is you get neither.

This only applies to GC languages that lack language features support for value types, stack allocation or native heap support.

There are some wildly imaginative benefits of FP sold in words by some advocates, oftentimes imagining what could be in a runtime or compiler based on the maths of what’s promised by the practice. It’s easy to imagine that if an expensive function call always produces the same results it can be optimized to a single call, after which all further calls are free (a memory access). It’s easy to then overstate or imply that calling a pure function guarantees that kind of optimization even if it doesn’t.

You are right of course, that this is not always implemented. I'd add though, that an impure implementation would never allow for such an optimization. The rest is the job of compiler developers. Of course you need to keep an eye on runtime execution cost as well. That is part of your job.

> One benefit (with respect to the CPU) of pure functions is that they can be cached

Only if the input space is very small. If your function takes as input two booleans and a string you know is an ID from a relatively static and small set of IDs, memoization is the way to go. If your function takes in two arbitrary floats, trying to memoize anything will only make your program run slower and leak memory.

Permanent memoization is not your only option.

Caching the result of common inputs and discarding not-recently-used results can be useful on functions with huge - but nonuniformly distributed - input and output spaces. At the extreme, you might have procedural image or texture generation - perhaps the postprocessing of another image or texture, for example. Impurity is a great way to end up with serious cache invalidation bugs when untracked inputs are changed, and purity a great way to avoid them.

Well, caching is a thing that shouldn't be done "just because" but after some analysis that says it's worth it. And as MaulingMonkey said, a cache doesn't need to keep everything, just enough things to improve performance. And if the cache is costing you performance versus recomputation, then don't do it. I mean, just like anything else in life, if it hurts don't do it. If it costs you performance in a way that you care about, use an alternative.

The "free" part you're describing is called referential transparency. What it means is that a pure function, called with the same parameters, always returning the same results without side-effect, can be substituted with its return value as an assignment (or as part of an expression).

The most important part of that explanation is can. The idea behind certain properties of FP, this being one of the most important ones, is that you are able to describe the results you want (somewhat declarative, moreso than imperative languages, less so than logic programming) and let the "compiler" or the "runtime" determine how that's delivered, without knowing or caring how it's executed. The problem with that is that the "compiler" or the "runtime" has to actually do the optimization, and if it doesn't, you're... executing unoptimized code!

Taking your React example, if it had appropriate heuristics, it could noop a ton of work and devs wouldn't have to even think about optimizing really simple good hygiene patterns. But it doesn't even look at your source code, it has no idea what weird stateful complex mess you're calling into, and it just assumes the worst.

If you’re interested in a language which does claim to optimize pure functions, take a look at Koka (https://koka-lang.github.io/koka/doc/index.html), a research language from Microsoft. It doesn’t implement any control flow besides conditionals and pattern matching; everything else is implemented with higher-order functions, and a cool syntax which allows trailing callback parameters to look like a block of code makes it look almost imperative. Additionally, they have a complex effect tracking system which tracks not only if a function is pure, but also things like if it might be non-terminating or throw errors. Somehow this is used to transform functional code into code which is about as fast as the imperative equivalent.

Ultimately, I think reasoning about function effects in such a fine-grained way probably won’t catch on, but it’s a great example of what you can do when you design compiler up. However, the original article, and most in production functional systems, are about attempting to carve out a functional system from imperative parts. The result is like you said, we’re executing unoptimized code.

This is why (the keyword) pure in D (mentioned in the article) asserts that the function does the same thing for the same input - not necessarily the same output. Side effects are still reasonably possible, just not launching the missiles.

Strong purity can be checked by having immutable arguments.

A true pure function combined with persistent immutable data structures (Immutable.js, Clojure, Scala, et al) can be memoized and re-executed practically for free (in very short constant time).

P.S. In React for example, in almost all cases the amount of memory dedicated to holding immutable data is typically tiny for modern hardware. So it almost always makes sense to trade memory for faster execution.