> This is exactly the kind of problem that functional programming was supposed to help us avoid!
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.
Commutative functions are scarce. You can rely on having transitive functions, but not commutative ones and frankly, there aren't that many useful commutative functions possible.
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.
>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.*
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".
If the code is commutative, then this that statement is true.
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.
>If the code is commutative, then this that statement is true.
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?
Yes, thank you, I wrote this comment and then saw your other comment. Below that comment I explained why I think your interpretation of what those people are claiming is mistaken. Mind you, not a case of No True Scotsman: I'm saying they aren't arguing what you say they are arguing; at worst they are being unclear, but they are certainly arguing something very different!
Are you sure we are talking about the same "functional programming"? Consider a function that parses a number from a string, and a function that doubles a number. How could anybody expect the order of these applications to not matter?
Some people just oversell it, or don't think of the whole spectrum of commutativeness scenarios when they write about FP. I give several examples of that, lower in this thread, with links.
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.
I don't think anybody ever meant to imply that pure functions can be composed in any order. That's the confusion here. "Pure functions can be run in any order" only means that they don't have side effects so one call doesn't impact another, but nobody ever meant or (hopefully) understood that to mean that the inputs and outputs of pure functions could be composed in any order. I don't even know what kind of confusion could lead to such an idea.
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.
Your statement may be mistaken. The order in which pure functions are applied matters often, but not necessarily. You can think of a few trivial algebraic examples where order matters.
Note that the parent said "if their inputs don't change".
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:
I don't see why your comment is not simply additive to mine. Both our statements are true, and are related to the general discussion. Your statement relates to the most "pleasingly parallel" situations. Mine refers to problem composability.
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.
> Only the latter (that the order where 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 in which pure functions are evaluated doesn't matter (except with respect to nontermination). You are claiming people say that the order they are applied doesn't matter - this is a bit ambiguous. The example above is changing what the functions are applied to - everyone agrees that this matter (outside some well structured exceptions).
Or any other order, and we will converge to the same result: [20, 40, 60]. If a language has the Church-Rosser property (AKA being "confluent"), then we're guaranteed that if we reach a result (i.e. if we don't get stuck in an infinite loop) then we get the same result, regardless of evaluation order.
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 ";":
If the "print" procedure has side-effects, we get different results depending on which order we evaluate the calls in, hence the language would be non-confluent and we would have to be very careful that parallelism doesn't break the functionality.
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")
If we eventually choose to execute this "AST", all of the side-effects will still occur in the same order, even if we've evaluated a bunch of things inside it, since evaluating a compound statement like 'a; b' cannot change the order of the parts, in the same way that evaluating a list '[x, y]' cannot change the order of its elements. Treating side-effecting statements as pieces of data in this way lets us blur the lines between interpreters, compilers and "eval", and is similar to what Haskell's "IO" type does.
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))
This turns one statement value into another with equivalent behaviour, but better performance (e.g. fewer system calls, etc.). Haskell's GHC compiler allows these sorts of rules, although they're applied at compile-time rather than run-time. There are also languages based around rewriting expressions at run-time, like Pure and Maude, for which all of these arguments also apply.
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:
"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/...
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...
I think you're being disingenuous. Those articles aren't claiming what you say they are claiming. Their wording may be imprecise (I agree with you on that), but nobody is claiming that FP makes all chains of transformations magically commutative.
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.
>I think you're being disingenuous. Those articles aren't claiming what you say they are claiming. Their wording may be imprecise (I agree with you on that), but nobody is claiming that FP makes all chains of transformations magically commutative.
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.
I don't follow you. When people say "you can run these functions in any order" (or "in parallel"), how do you interpret this to also imply "...regardless of their input"?
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?
>Why does it matter if they say "run" instead of "evaluate"? What's the difference, in your opinion?
"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.
You're mistaking order of evaluating separate functions, from function composition. So if I have two pure functions, f and g, that take and return immutable values (thus having no side effects) I can go:
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.
It's clear that you know what is actually meant by "order doesn't matter".
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.
>However, I find the idea that FP advocates have been ambiguous in using this phrase to be preposterous.
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).
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.