1. 9
  1.  

  2. 6

    <strike>Sorry, nope.</strike> No. Functional programming gives primacy to value transformations as the means to express computation, and for this style to work, the language must have interesting (nontrivial) observational equivalences between expressions. (Note that purity, in the Haskell sense, is a sufficient but by no means necessary condition.) For example, in ML, the functions fn (x: int) => x + x and fn x => 2 * x are indistinguishable from the other, and so are the lists [1,2,3] and rev (rev [1,2,3]). Their C# counterparts could be distinguished by object identity. Very few languages support functional programming reasonably well.

    1. 6

      I don’t see how the fact that there exists a means to distinguish values by object identity in a given language makes it impossible to program in a functional style in that language. This is also a bit idiosyncratic as a litmus test for functional programming (not that FP has any shortage of idiosyncratic litmus tests).

      1. 3

        Functional programming imposes restrictions on otherwise imperative programming, in the hope that programs that satisfy this restriction are easier to manipulate as mathematical objects, both formally and informally. This restriction comes with an expressiveness price. For example, FP limits the kinds of nondeterminism that can be expressed in a program, because the lambda calculus is Church-Rosser: if you evaluate a lambda term twice, and both times arrive at an answer (normal form), then both times you arrive at the same answer.

        A general-purpose programming language can’t be purely functional only. For example, Haskell has IO actions, and which are executed, not evaluated. However, a programming language can make it easier to implement parts of a program in a functional style, and integrate them with other parts implemented in a more traditional imperative style. For this to work, you need a guarantee that the imperative parts won’t compromise the abstractions that the functional parts depend on. Pervasive object identities compromise the irrelevance of the choice between multiple representations of the same value.

        1. 5

          The traditional solution in these kinds of mixed languages (Lisp, for example) is that if you don’t want to compare objects by object identity, you compare them according to a different kind of identity, which is why there are several kinds of equality predicates in Lisp. It’s an unusual argument (although not unheard of) to argue that the existence of an equality predicate that you don’t want to use makes the language impossible to program in a functional style.

          In any case, my broader point is that this isn’t some kind of new issue, and how “functional” various choices make a language has dozens of definitions. I don’t think the fact that you personally prefer one idiosyncratic definition of this decades-old contested term justifies starting a comment with an arrogant, dismissive “Sorry, nope”.

          1. 2

            Common Lisp isn’t a “mixed” language. It’s object-oriented, and the real notion of equality is physical object equality (eq), period. Everything else is just a convenience. For example, equal tells you something about the state of two objects, not whether the objects are really the same.

            Removing eq from the language doesn’t make the problem go away. Even if eq didn’t exist, you can provide evidence that two supposedly equal objects are actually physically distinct by mutating just one of them.

            I apologize for the “Sorry, nope.”

            1. 6

              I don’t think you can have a historically coherent definition of the term “functional programming” that doesn’t include Lisp, which was the first widely researched and used language considered to support a functional style of programming. Until roughly the late 80s / early 90s, when other more-strictly-functional languages eclipsed it, it was even often seen as the canonical FP language, though of course not everyone agreed (in “Lisp” here I’m including Scheme, which probably had a larger FP-oriented community than Common Lisp did). From 1982 to 1994, for example, one of the main academic FP conferences was named “ACM Symposium on Lisp and Functional Programming”. It published work situated in a variety of languages (including the ML family and Haskell), but Lisp had a dominant position. Once Lisp began waning, in 1996 that conference merged with another one to become the International Conference on Functional Programming (ICFP), today’s biggest FP conference.

              Now certainly you can say “the definition of FP has shifted over time”, but I think it’s not so much shifted as become a family-resemblance term with a dozen or so definitions, like “object-oriented”. Yes, there are Kay disciples who will claim that there is one true definition of OO (and Java isn’t OO), but they haven’t really won out.

              1. 7

                I don’t think you can have a historically coherent definition of the term “functional programming” that doesn’t include Lisp, which was the first widely researched and used language considered to support a functional style of programming.

                The risk of asking to include Lisp at all costs is that you’re making functional programming impossible to distinguish from object-oriented programming. Citing a researcher on and proponent of object-object oriented programming:

                An object is a first-class, dynamically dispatched behavior. A behavior is a collection of named operations that can be invoked by clients where the operations may share additional hidden details. Dynamic dispatch means that different objects can implement the same operation name(s) in different ways, so the specific operation to be invoked must come from the object identified in the client’s request. First class means that objects have the same capabilities as other kinds of values, including being passed to operations or returned as the result of an operation.

                First-class procedures are thus objects with a single operation.


                Until roughly the late 80s / early 90s, when other more-strictly-functional languages eclipsed it, it was even often seen as the canonical FP language, though of course not everyone agreed (in “Lisp” here I’m including Scheme, which probably had a larger FP-oriented community than Common Lisp did).

                Yes, it is an observed social phenomenon that the Scheme community has traditionally appreciated programming in a functional style. (It is also an observed social phenomenon that some C++ programmers appreciate programming in a functional style, and other C++ programmers call the former “crazy”.) However, from a purely technical point of view, there is no well-defined functional subset of Scheme that can safely interact with imperative Scheme programs, without compromising the abstractions defined in the functional subset.


                Now certainly you can say “the definition of FP has shifted over time”, but I think it’s not so much shifted as become a family-resemblance term with a dozen or so definitions, like “object-oriented”. Yes, there are Kay disciples who will claim that there is one true definition of OO (and Java isn’t OO), but they haven’t really won out.

                I don’t understand the defensive reaction when I say that such and such language doesn’t support functional programming very well. I’m not saying “it’s useless” or “you can’t write clean code in it”. I’m just saying “it isn’t terribly convenient to program in a functional style in it”. And that’s fine - no single language can support all styles and do it well.

                I suspect that the defensive attitude comes from the “trendiness” of functional programming in certain very vocal circles, and the subsequent rush of language designers to add “functional features” to their languages. This is dangerously reminiscent of what happened to object-orientation since the 80’s. Alas, this causes more harm than good (as this very thread shows), and, in any case, it can’t possibly work: what is needed isn’t “more features”, but rather “more restrictions on what existing features can do” and even “less features”.

                1. 2

                  Thanks, I found this reply helpful / clarifying, and largely agree.

      2. 4

        I have never seen this definition before and am inclined to believe that it is one you made up, rather than what is commonly meant by the term.

        Do you have any citations that this is what is commonly implied by the term “functional programming”?

        1. 3

          It should support both computation by evaluation and computation by execution. Evaluation is a smooth generalization of high school- and university-level mathematics, and is defined in terms of standard mathematical concepts such as tuples, functions, numbers, and so forth. Variables are given meaning by substitution, and evaluation consists of simplifying expressions. Execution is the action of a program on another agent or data structure conceived of as existing independently of the program itself. The data lives “over there” and the program “over here” diddles that data. Assignables (my word for what in imperative languges are wrongly called variables) are given meaning by get and put operations (fetch and store), not by substitution. Execution consists of performing these operations.

          Source

          1. 3

            Your most contentious claim, namely that object identity disallows computation by evaluation by its existence, is neither mentioned nor supported by Dr. Harper’s article.

            1. 1

              I didn’t claim that object identities disallow computation by evaluation. However, when object identities are pervasively involved in all calculations, the values you are manipulating are the object identities themsevles, not the standard mathematical concepts Dr. Harper talks about. For example, when you evaluate twice the Lisp expression (list 1 2 3), you get two different results: the identities of two different cons cells. Languages that support functional programming avoid this unfortunate situation by natively treating many common mathematical constructions (tuples, lists, trees, etc.) as values.

              1. 3

                I fail to see the practical implications of this. As long as you agree by convention to not compare function types by reference identity, what impediment do you have to programming in a functional style?

                Your example of creating two lists doesn’t paint a clear picture for C#, since most complex object types define structural comparisons that would be used in most cases.

                1. 2

                  As long as you agree by convention to not compare function types by reference identity, what impediment do you have to programming in a functional style?

                  Conventions come in two kinds: enforced (statically or dynamically) and broken.

                  Your example of creating two lists doesn’t paint a clear picture for C#, since most complex object types define structural comparisons that would be used in most cases.

                  As I stated before, it doesn’t suffice to have the right equality predicate. Equal objects must actually be indistinguishable.

                  1. 2

                    Conventions come in two kinds: enforced (statically or dynamically) and broken

                    Up to you if you want to take such a hard line. My experience is that value is not a step function.

        2. 3

          So ML has some way of determining whether two algorithms implement the same function? That would be an enormous advance.

          1. 10

            For reference this is actually impossible by Rice’s theorem (which, in extreme brief, states that you can’t always tell what an algorithm will do). It’s actually strikingly easy to prove by reduction to the halting problem, and it’s my favorite result in computer science, because it’s both very general and simple and elegant to prove.

            1. 2

              No. Function equality is undecidable in ML. “Being equal” doesn’t imply “can algorithmically be determined to be equal”.

              1. 2

                I fail to understand how stating a long-known mathematical fact is being a troll. The existence of the notion of equality doesn’t imply that it has to be algorithmically decidable. For example:

                • Function equality in general is undecidable.
                • Real number equality is undecidable.
                • Observational equality of programs is undecidable.

                Could the downvoter please explain?

                1. 1

                  So what does: “ For example, in ML, the functions fn (x: int) => x + x and fn x => 2 * x are indistinguishable from the other, ” mean then?

                  if f x = x+x and g x = x*x were “indistinguishable”, I’d assume the compiler could optimize h(g 5, f 5) by reusing g 5

                  1. 4

                    Two expressions being indistinguishable means replacing one with the other in any larger program doesn’t alter the meaning of the larger program.

                    1. 2

                      Ok. So, similarly, “In C, the expressions (x+x) and 2*x are indistinguishable”? In fact, optimizing compilers will replace the multiply with a shift.

                      1. 1

                        Yep. The expressions x+x and 2*x by themselves are indistinguishable in C. However, if you define

                        int foo(int a, int b) { return a + b; }
                        int bar(int a, int b) { return a + b; }
                        

                        Then foo and bar, as function pointers, are not indistinguishable.

                        1. 1

                          But since ML is unable to determine whether two algorithms implement the same map, what is the actual difference? ML cannot replace f with g and actually treat them as “indistinguishable” unless it can determine that they are equal as functions which is impossible in general and exceptionally difficult even for restricted cases. So it appears that your claim means nothing at all.

                          1. 5

                            Function equality being undecidable means that there’s no algorithm for testing whether two arbitrary functions are equal. That’s why, if you write the expression (fn x => x + x) = (fn x => 2 * x), you get a type error: the type int -> int isn’t an eqtype.

                            However, an optimizing compiler doesn’t need to decide whether two arbitrary expressions are equal. It is sufficient to have an algorithm with three possible results: “equal”, “not equal” and “don’t know”. Only when the algorithm returns “equal”, can the compiler use this equality to optimize your program.

                            1. 1

                              So they are distinguishable. Which was my point. ML is a programming language and as such is subject to the same limitations that dog all languages in which algorithms are definable.

                              1. 4

                                No, that is wrong: fn x => x + x and fn x => 2 * x are not distinguishable. Both denote the same mathematical function - provably so, even!

                                1. 4

                                  ML cannot replace f with g and actually treat them as “indistinguishable” unless it can determine that they are equal as functions which is impossible in general and exceptionally difficult even for restricted cases.

                                  Your argument here is from the perspective of the compiler making optimizations. All equivalence says is that the optimization is valid, it doesn’t say anything about the feasibility of implementing the optimization. Furthermore there are reasons to care about equivalences beyond optimization.

                                  1. 1

                                    My point was simply that ML “functional” nature does nothing to make this difficult problem magically go away.

                                    1. 3

                                      If you make a plan that depends on your ability to make unicorns appear out of nowhere, you know that the plan is fundamentally flawed and can’t be carried out, right? The situation is very similar here: Algorithmically deciding whether two arbitrary functions are equal is known to be impossible, so you better don’t try in the first place.

                                      However, it’s possible to implement a procedure that, given two expressions (that is, syntax trees), answers either (0) “they’re surely equal” or (1) “they might or might not be equal”. For one, a procedure that always answers (1) meets the specification! We’re interested in procedures that sometimes answer (0), though, of course.