Yes mathematically composability is part of it. That's because math functions return the same type. Its easy to express the 'state' of a function as the value of the operation.
There's a wider idea of idempotency in computing - that state changes in general respond to operations. Repeating the same function more than once (because the network stuttered or the sender resent the message) and arriving at the same state is a common example.
I got that, my point is that such composability is rarely better than good old OOP with encapsulation. Enumerating all possible state transitions on object interface leads to better design than procedural programming (and composable operations are procedural programming).
I'm not sure that they are. You just need to model the concept of state as the function's input/output, as functional programmers are eager to do :)
If we start in state x, then apply operation f, the resulting state is f(x). If we apply operation f again, we'll be in state f(f(x)). If f is idempotent, then state f(x) and state f(f(x)) are identical.
All this is saying is you can't compose behaviors because we insist on having only one whole state, and only one concept of what 'next' state is.
If you can have state with sub-states and 'next' operator that is respective to what sub-state we want to address then this example is easily composable.
But then of course you might want to have substates interact with each other so it complicates further. It just looks like multithreaded programming.
Plenty of state -- even mutable state -- is essential complexity. Think of an IDE where a user is typing out code: the state is changing all the time. Pure functional programming has a hard time walking the line between "avoiding" mutable state, and "ignoring" mutable state. If you insist on functional purity, you're already admitting defeat in the face of essential mutable state. The walls of functional (and especially reactive) programming are too high -- they currently don't play very well with their Turing and von Neumann neighbors.
Functional programming is only "mathematically pure" because we already have math for it. You can make mutating state "mathematically pure" too, if you just invent new math for it. For example, you can pair state with a "generation" variable and define mutating functions as returning the new state with generation + 1; now all your functions are pure again. That's not all it takes, and it's not easy! But it shows how narrow-minded the current idea of "purity" is.
I think it's much more common to talk about idempotence in programming w.r.t. state and state transitions. With immutable data, this approaches the mathematical definition:
(= (remove-el set 1) (remove-el (remove-el set 1) 1))
With network protocols, state machines, and mutable data, idempotence helps ensure consistent state without the fixed-point-ness.
I wonder if there is an entirely different way to reason about computation, other than mutable state, which coincides with our intuitions based on everyday experience of the physical world; and immutable state, which coincides with the powerful and abstract approach of our mathematics.
Alas, mutable and immutable would appear to cover all the cases.
Idempotence is usually used when talking about effectful code. Modeling the state as part of the input/output seems to run counter to that purpose, because that's how you create a pure model of an effectful program. It's useful to talk about idempotence when running the function zero times is different than running it once, which is hard to do in that framing. As you say, "on the same input" is difficult to reconcile if the state is part of the input.
If we consider the state to be part of the input, then it's easier to say that when f(x) = y, then f(y) = y as well. In other words, f(f(x)) = f(x). Which, as it just so happens, is literally the mathematical definition of idempotence which the programming concept is based on.
In any case, this still gets to the same overall conclusion: the point is to arrive at a specific destination, not to move towards it. That shift of perspective is helpful in framing problems towards an idempotent solution.
Not to mention idempotent code is trivially memoized, allowing you to skip computations you couldn't previously reason about. A function that produces a value is always comparable to another value — a function that modifies some state requires that you have a way to observe that the world changed in order to skip doing it again.
that's assignment AND reassignment. Mutable state is fundamental to how computers work no matter how hard the fans of the current fad of functional programming try to deny it.
Yes, that was actually my point. State is essentially function composition. Thus I'm arguing for avoiding dependencies between conceptually independently compositions.
Idempotence is a desirable property of systems whereby repeating an action has no effect. Mathematically, an operator is idempotent if f(f(x)) = f(x).
Idempotence is handy because it implies that one can retry safely if one isn't sure whether something succeeded or failed. Not sure if your file was saved? Save again! If it was indeed saved, the file continues to be saved. If the file was not saved, it is now. Yay.
I would kill for such descriptions of every system I work with.
Code that does I/O has a lot of interplay that's hard to replicate and impossible to cover entirely. The physical world is nothing but shared mutable state.
I completely agree. I like how most responses to your rant hone in on the fact that it's a simple syntactic change, but utterly fail to get the point that composition of stateless functions a la Joy is totally magical, and opens up a whole world of possibilities that mutating, unchainable, uncomposable methods cannot.
For starters, and given that this is a thread about scientific computing, having stateless functions that mirror mathematical ones gives you robust, efficient approaches for parallelism and optimization that are completely lost (or horribly intractable) once you start boxing numeric types just so some OOPhead can put a dot after them.
I was trying to respond specifically to didibus's obvious misunderstanding: they thought an increment function might be designed to be idempotent. That doesn't make any sense, whether you know the CS meaning of idempotence or not.
One significant issue here is the question of a priori vs. a posteriori properties. When thinking algebraically about software, it's often a case of defining things in an a priori way in order to get the right laws to apply to operations. Idempotence is one such law.
The other angle on this is the a posteriori angle, where you note that something behaves a certain way and use an appropriate word to describe that behaviour.
My reading of didibus's comment was that it was basically about imperative programming, and that there was some confusion around the situations in which the concept of idempotence applies (incrementing a variable isn't one of them).
I think you are trying to introduce the State monad and the technique of modelling a stateful program by chaining pure functions. That's fine, but it does introduce a level of complication that is not implied by a straightforward comparison of memoized functional vs. idempotent imperative code.
Not quite. The computer you're referring to has one state before an event, and another state afterwards.
Modeling those as two distinct, immutable states provides enormous benefits over modeling it as a single state that "mutates". Doing this eliminates a large class of serious bugs.
The reason for these benefits is that far from trying to "escape the reality that the known universe and everything that happens within it is stateful," functional programming uses a more rigorous model of state that better reflects the relationships between states over time.
Isn’t that just axiomatic? Of course anything you can do with a class you can do with a function + state. The prose is to make that pattern more natural for humans to program and use.
Yeah, you’re absolutely right that there is always some situation where some amount of shared mutable state is necessary, but there’s still a lot of fat to trim in most cases.
There's a wider idea of idempotency in computing - that state changes in general respond to operations. Repeating the same function more than once (because the network stuttered or the sender resent the message) and arriving at the same state is a common example.
reply