No, no it isn't. Just like you wouldn't expect 2 * 3 + 8 to suddenly return 22 when you intend it to, you shouldn't expect the order in which you apply functions to not matter.
When you pass around a changing state object to every step of your program, you are effectively doing normal imperative programming with global-ish state.
If the functions aren't commutative, function order definitely matters!
Yes, ordering matters, but if you cannot force ordering by protocol or by the types used, then the result is going to be non-deterministic by definition, which means it's not referentially transparent.
Only the latter (that the order that pure functions are applied doesn't matter) has been touted forever as a benefit of functional programming, and what supposedly makes it "trivially parallelizable".
Functions that return the same values when given the same arguments are substantially easier to reason about than functions that return values that depend on both the arguments passed in and some state somewhere else in the system.
Additionally, functions that don't modify their arguments are relatively easy to parallelize. (Due in part to the fact that it's really easy to figure out locking in a share-nothing system.)
Anyway. I'm no scholar, but I'm pretty sure that no knowledgable FP proponent has ever seriously said "FP lets you call your pure functions in any order whatsoever and get the same end result, every time.". Perhaps I'm misunderstanding your statement?
The order pure functions are applied in doesn't matter if their inputs don't change. Here, the inputs do change. The result of handleCollisions is a different state than the state you pass into it, so you should expect a different result when passing it to another function.
Pure functions are trivially parallelizable because they don't depend on non-local state. The moment you know what arguments you are passing to them, you can run them in whatever parallel or non-parallel fashion you like.
Every function that uses and returns a modified version of a single object can not be parallelized, since every single function in the pipeline depends on the result of the previous one. Here, for example, you don't know what the argument you are passing to processInput looks like until you've run handleCollisions.
f(a) = a + 3
f(b) = 2b
f(a).f(b) can have different results vs f(b).f(a)
fun f(a) = a + 3
fun g(b) = 2b
val x = f(2)
val y = g(3)
val y = g(3)
val x = f(2)
This was the post right before the one we're talking about:
>No, no it isn't. Just like you wouldn't expect 2 3 + 8 to suddenly return 22 when you intend it to, you shouldn't expect the order in which you apply functions to not matter.*
A reasonable interpretation of the text and the one that follows is that some claims have been made that functional programming provides benefits of commutativity, and that people are disappointed to find no such benefit.
In general in this thread, some people are following the root comment in using "order in which functions are applied" to refer to what you mean - applying one function to the output of another, or vice-versa. Of course this affects the correctness of the result (and possibly also the well-typed-ness of the program).
Other people, like the author of your parent comment, are using "order in which functions are applied" to mean "order in which functions evaluated", which indeed does not for the correctness of pure functions (except possibly with respect to nontermination).
Working with f(x) = x + 3 and g(x) = 2 x, the expression f(g(7)) can be evaluated inside-out or outside-in:
f(g(7)) = f(2*7) = 2 * 7 + 3
f(g(7)) = g(7) + 3 = 2 * 7 + 3
Edited to add: per https://news.ycombinator.com/item?id=11396816, that should be "coldtea's incorrect accusations against now-specified FP proponents".
But functional programming isn't going to make a non-commutative problem magically commutative.
All code has inherently serial parts (eg because of dependency chains). These cannot be magically made parallel (although, especially with immutable data, it may be possible to apply parallelism techniques like pipelining). However, the parts that are independent can be trivially parallelizable. Immutable state and functional programming make it easier to tease this out, but it doesn't automatically eliminate dependencies or allow them to be evaluated in arbitrary order.
Actually my statement is true whether code is commutative or not -- since my statement wasn't that "pure functions can run at any order" but rather "people has been claiming often that pure functions can run at any order".
What they claiming can be right or wrong (depending on the commutative nature of the functions in their code), but that people indeed claim it is true (and can be quantifiably verified)...
Barring people who are new to FP and reading through a tutorial, who can make erroneous claims out of lack of understanding (just like people learning OOP also make mistaken claims about it), I don't see how anyone using FP can make that claim. It's evident that you cannot arbitrarily change the order in a series of transformations unless they are commutative. I mean, this is already the case with maths! Who would claim it isn't with FP?
I have posted several examples lower in this very thread.
For example, consider the expression:
myList = map(double, [10, 20, 30])
myList = [double(10), double(20), double(30)]
myList = [20, double(20), double(30)]
myList = [20, 40, double(30)]
myList = [20, 40, 60]
myList = [double(10), double(20), 60]
myList = [double(10), 40, 60]
myList = [20, 40, 60]
To see the link to parallelism, imagine that the above list is much larger, and rather than just doubling a number we're doing some expensive calculation. In a non-confluent language, we'd have to specifically designate the tasks which can be performed in parallel, e.g. creating a job queue or the like, to avoid race conditions and out-of-order side-effects. In a confluent language, everything can be evaluated in parallel without affecting the result; the only thing we have to care about is performance (the overhead of parallelising small tasks far exceeds the gains) and data dependencies (if X uses the result of Y, there's no point starting X until Y has finished; and it's better to run both on the same machine, to minimise network usage).
Now instead of a list of numbers separated by ",", imagine we have a list of statements separated by ";":
myProcedure = print(reverse(" olleh")); print(concat("wo", "rld"))
On the other hand, we could approach these statements from a higher level view: we can think of each statement as a perfectly normal piece of data, e.g. as if it were a node in some AST. In which case, the ";" separator is just a pure function for combining two statements (pieces of data) into one statement (piece of data). In this setting, we can regain confluence, and hence evaluate in any way we like, e.g. we can reduce the inner expressions to:
myProcedure = print("hello "); print("world")
In a non-confluent language we couldn't evaluate parts of the second statement in general, e.g. because "concat" might depend on effects from "reverse" or the first call to "print", hence there is less opportunity for aggressive optimisation, and without a distinction between pure and impure code (like we have above between functions and 'statement data'), there's no way in general to know which parts can be evaluated in parallel.
In fact, confluence isn't limited to function application (AKA "beta reduction"); we can add all sorts of program transformation rules to our language whilst remaining confluent (although such rule-adding mechanisms can be used to break confluence, this is usually considered user-error). For example, we might have a rule like the following:
print(x); print(y) --> print(concat(x, y))
I'm not saying that order doesn't matter with pure functions (which is wrong).
I'm saying that the notion that "order doesn't matter" (without qualifications) has been touted as a benefit of pure functions and FP -- and indeed it has. Wrongly, but it has -- and that's an impression many people get from reading such "introductions to FP".
In fact, the author of the original post we're discussing makes the exact same observation: that order was supposed to "not matter", but he shows how it does.
And if you want some more example of what I said, here's a very lazily collected sample, I just used "pure function" and "any order" etc. in Google:
"A pure function is also robust. Its order of execution doesn’t have any impact on the system.". -- http://www.nicoespeon.com/en/2015/01/pure-functions-javascri...
"Finally, and here's the coup de grâce, we can run any pure function in parallel since it does not need access to shared memory and it cannot, by definition, have a race condition due to some side effect". -- https://drboolean.gitbooks.io/mostly-adequate-guide/content/...
"Another consequence is that it doesn't matter in what order functions are evaluated — since they can't affect each other, you can do them in any order that's convenient". -- http://stackoverflow.com/questions/4382223/pure-functional-l...
"Pure functions may be run in any order, so it's more easy to parallelize their execution". --http://leonardo-m.livejournal.com/99194.html?page=1
"Pure functions can be evaluated in any order, the result is always the same. Therefore, pure functions calls can be run in parallel". -- https://medium.com/@yannickdot/functional-programming-101-6b...
Note how all examples don't bother to give any qualifications for input data dependencies between some of your pure functions and race conditions based on them...
What do newcomers to FP learn from those?
You know what these people mean when they say pure functions may be evaluated in any order: that as long as they have the same input, the result will be the same. But in contrast, the "magical commutativity" property doesn't mean the functions get called with the same input! Or, to say the same in other words, you cannot change a function and expect your program to be the same, and we know that h1 = f . g and h2 = g . f are, in the general case, NOT the same function! In fact, one of the two might not even compile!
At best you could argue the explanations you linked to are incomplete or unclear. But it's dishonest to say they claim you can order the functions in any way, regardless of their input -- which is what TFA was having problems with.
But I didn't say they do [say the latter].
Only that they sidestep the issue -- often confusing application with evaluation (using them interchangeably, or e.g. using the imprecise "run in any order" instead of evaluate).
Very few of those article mention commutativeness, the distinction between evaluation and application, data dependencies, etc. And even those ment
ioning "order of evaluation" forgetting to clarify that is not the same as application, and confusing the matters more by adding that we can "easily run them all in parallel" (giving newcomers the impression that the order of application doesn't matter at all).
>At best you could argue the explanations you linked to are incomplete or unclear. But it's dishonest to say they claim you can order the functions in any way, regardless of their input -- which is what TFA was having problems with.
TFA author had those problems (or, more precisely, had the idea that they shouldn't exist) because he was influenced by such articles -- coming to believe that FP was "supposed to free us" from ordering issues.
You say that "it's dishonest to say they claim you can order the functions in any way, regardless of their input", but that's just what this statement implies:
"A pure function is also robust. Its order of execution doesn’t have any impact on the system."
Potential issues with input not mentioned at all, as if they don't exist.
Or this:
"Pure functions can be evaluated in any order, the result is always the same. Therefore, pure functions calls can be run in parallel"
Here they indeed write "evaluation", but the "can be run in parallel" sans qualifications, muddies the waters.
Why does it matter if they say "run" instead of "evaluate"? What's the difference, in your opinion?
Do people really have trouble with the (universal, not FP-specific) notion that the input to a function matters?
Do we both agree that FP/immutability doesn't promise what the author of the article thinks it promises, and that people (regardless of about how clearly they say it) do not claim it does?
"Evaluation" solely implies passing an actual value and getting the result from a function. Taken in isolation, each evaluation (of pure functions) is independent from whether 10 or 200 other happened before or after -- it depends only on the input it gets.
Saying "run" on the other hand can be conflated to mean running a pure function in the course of a program's execution, and there the order or execution can matter with regards to the overall program's behavior, e.g. when it affects the derived input of a subsequent function.
>Do people really have trouble with the (universal, not FP-specific) notion that the input to a function matters?
Yes, people do expect pure functions will free them from race conditions for example -- only to discover that they still exist, as the author did, at a higher conceptual level.
Heck, if we are to discuss the original article, isn't it a given that such people as its author do exist and have the same confusion?
Or does the author seem like some totally ignorant programmer that is not representative of more people (and that we'd expect him/her to get it all wrong)? It doesn't come out that way to me.
a = f(x)
b = g(y)
or:
b = g(y)
a = f(x)
And the order does not matter. Because each function cannot effect the other. This is what these quotes are talking about. That independence. There's no outside state mutated in one evaluation affecting the other evaluation.
What you're talking about is function composition. That it f(g(x)) vs g(f(x)). And as many others have said on these threads, the order of the functions when composing two functions together like this is only unimportant if the functions themselves are commutative.
However, I find the idea that FP advocates have been ambiguous in using this phrase to be preposterous. In none of the examples you cite does the other say "order doesn't matter" without qualification. In every example you cite, the author explicitly says that order of evaluation/execution doesn't matter. That is an unambiguously correct statement.
That being said, it is still possible to be unambiguously correct and still regularly confuse people. Rhetorical style and knowing your audience go a long way towards avoiding that sort of confusion. However even when you write with clarity, there will still be some who will misinterpret - this cannot be helped.
I recognize this is merely my personal experience, but even as an average programmer who was haphazardly exploring the concepts of FP, I don't think I ever misunderstood what was meant by "order doesn't matter". If it turns out that many/most people were confused, then I will consider myself lucky in having found some good introductory material. Otherwise, I'm inclined to think that this is one of those blindingly obvious things, and that people who fell into this confusion - while by no means stupid - were simply exercising poor reading comprehension when they came across that phrase.
And yet the author of the original article, writes:
>It turns out that our purely functional rendering code is sensitive to ordering in non-obvious ways. The first time I encountered this kind of bug, it felt strangely familiar – it’s something that often occurs in imperative programs.
And notes:
>This is exactly the kind of problem that functional programming was supposed to help us avoid!
[empasis mine]
That the author felt that way is a failure from those intro to FP blog posts/articles that failed to make such things clear.
>In none of the examples you cite does the other say "order doesn't matter" without qualification.
They all fail to mention that those functions can have data dependencies from one another, and that we can't easily parallelize "any" of them as they claim.
None of the articles mentions anything about the commutativity of the calculations (or even the very term commutative itself).
And it's exactly the same thing that the author of the original article discusses -- that order was supposed not to matter, but it does.