1. 34

  2. 22

    If you want to be even more pedantic, only individual executions of a program can be fast or slow. There is no inherent speed to the program that exists in a meaningful way without tying it to specific measurable runs of the program.

    There goes the entire field of complexity theory I guess…

    Other than this gripe I guess I agree with the article, but the same thing can be said of any programming paradigm. Paradigms are just labels we give to programming languages to give a vague idea of the sorts of programs they lend themselves to expressing. They are (rarely) a strict guarantee on exactly what programs languages in a given paradigm allow you to express.

    1. 16

      Au contraire. You can analyze the computational complexity and decide which complexity class the program is in, and that’s extremely useful information a lot of the time, but it doesn’t tell you anything about the speed.

      Is an O(n log n) sorting algorithm faster than an O(n^2) sorting algorithm? That depends. You know that if you keep sorting larger and larger arrays, you will eventually find a point where the O(n^2) algorithm becomes slower than the O(n log n) sorting algorithm. We can talk about the complexity class of algorithms, but we can only talk about the speed of particular implementations on particular hardware.

      1. 17

        we can only talk about the speed of particular implementations on particular hardware.

        We can only talk about the speed of particular implementations on particular hardware running on particular data.

        1. 8

          z3 will sometimes intentionally increase the computational complexity of a particular strategy because it nevertheless makes some type of search more practically tractable. In the database field, trees are almost always preferred over hash maps, even for workloads targeting point queries without scans, because they are so much more straightforward to manage and so much more amenable to compression, despite bumping up to O(n log n) instead of O(1) theoretically. The list goes on and on. There’s no substitute for measuring real workloads on real hardware.

          1. 1

            Sounds fascinating! Is there further reading on this particular subject?

            1. 3

              I learned about this while watching this video by the creator of z3.

      2. 20

        Programming paradigms aren’t sets, they’re cognitive categories; meaning membership isn’t true or false, but rather a question of degree of closeness to the prototypical “center” of each category. Here’s a little thing I wrote about a week and a half ago on just this.

        1. 7

          [author of OP here]

          Thanks for sharing; I think your article is making the same point as mine in a way that uses a little more precise terminology. In particular I like this part:

          That’s my hope in writing this, that we can move away from the dull and fruitless search for the right conditions, or the right assignment to sets, and into the much more interesting conversations of comparing and contrasting, choice-for-choice, feature-for-feature.

          Both articles were motivated by a desire to move away from tedious “is X a Y or not?” arguments. I think there is an element of prescriptivist vs descriptivism as well; rather than trying to be the arbiter of how a specific term is defined, we can explore the landscape of how it is used to communicate.

        2. 15

          Joe Armstrong of Erlang fame used to posit that a truly FP lang will only keep your room warm.

          1. 14

            A nice side effect if I’ve ever seen any

            1. 1

              Good one!

          2. 9

            Functional programming does not have a single definition that’s easy to agree upon.

            I know that for most programmers, the term “functional programming” lacks meaning but there are large groups of programmers who DO use the term to mean just programming with (mathematical) functions. You can ask a question in these groups “is this functional?” and get a consistent response; it has meaning!

            I completely agree that there’s “no such thing as a functional programming language” because there’s only the question of “to what extent does this facilitate programming with functions?” and I don’t think we should draw a line at any particular point.

            1. 5

              This is why some folks in the PL community prefer to use the words “declarative” or “denotational” instead of functional when talking about what sets the languages apart at the semantic level.

              1. 4

                I believe it’s more helpful to think of it as a “spectrum of functionalness”

                Compulsory link to Van Roy’s taxonomy of programming paradigms, in which “functionalness” is but one of many axes along which programming paradigms can be judged: https://www.info.ucl.ac.be/~pvr/paradigmsDIAGRAMeng108.pdf

                Both the associated book “Concepts, Techniques, and Models of Computer Programming” and the paper “Programming Paradigms for Dummies: What Every Programmer Should Know” are recommended.

                1. 4

                  I’ve been making the same claim/argument as the author for some time. There are multiple styles of software design. Any language may or may not be conducive to a given style.

                  I think it might help us to keep this distinction (style vs. programming language) in mind.

                  Object oriented programming is a style. Let’s assume we can come to agreement on what things are required to call a software architecture “object oriented”. Then what does it mean to have an OOP language? What does calling, e.g., Java an “OOP language” mean? I would argue that it only means that Java was optimized for solving problems with a certain style of programming (what the creators would call OOP). It doesn’t necessarily mean that it’s impossible to do functional programming in Java (though it might be!).

                  So my point of view is that OOP and FP are, in fact, basically absolute terms. “Pure” if you will. But programming languages can have varying degrees of pragmatism, multi-paradigm features, etc.

                  1. 7

                    Functional programming is a tribe. It’s not a school of thought, but a school of behaviors and attitudes towards people.

                    1. 12

                      No, functional programming is a style of programming in which you prefer to write functions without side-effects, with an emphasis on immutability.

                      1. 5

                        For me the key difference is that when imperative, I feel like carver or stonecutter with regard to the data I work with. When functional, I feel like I’m growing the data from the inside.

                        1. 4

                          Is SQL functional then?

                          1. 3

                            I’ve always thought of SQL as declarative than imperative (or functional).

                            1. 1

                              It feels similar to me, yeah. Definitely much closer to LISPs and Haskell than to Python or C.

                              I realize it’s mostly about whether I think in expressions or statements.

                        2. 4

                          OK, I’ll bite :-) What do you mean with “Functional program is … [about] attitudes towards people”?

                          1. 3

                            Programming tribes operate by cultural values which emphasize treating people according to their style of writing code. The common pattern for these tribes is to indicate that code is good, bad, etc. according to certain abstract principles which are either nebulous, trivial, undefinable, or subjective; and then to use these judgements to establish social ranking and attitudinal norms.

                            Crucially, these opinions are almost entirely arbitrary. For an on-topic example, every “immutable” language has a mutable machine which implements its semantics by reifying the execution stacks implied by its internal logic, and every “mutable” language has an immutable denotational semantics given by its native type theory. This leads directly to e.g. the weasel words in a cousin comment, “an emphasis on immutability”, as if computer science were not already part of mathematics and mathematicians did not already regularly treat time as yet another varying parameter.

                            1. 3

                              I think there’s a lot of truth to this, and I agree with the sentiment, so take these as questions to explore your thoughts further…

                              and then to use these judgements to establish social ranking and attitudinal norms.

                              Absolutely. But I don’t think exclusively.

                              Crucially, these opinions are almost entirely arbitrary.

                              Did you mean to imply that arbitrary meant “without value” here? The words of our many natural languages too are arbitrary, and serve tribal goals, but the tribalism also serves to get a bunch of people on the same page to accomplish shit.

                              For an on-topic example, every “immutable” language has a mutable machine which implements its semantics by reifying the execution stacks implied by its internal logic, and every “mutable” language has an immutable denotational semantics given by its native type theory.

                              This feels like a technically correct but (at least partially) irrelevant fact to me. Is your argument that as a programmer you don’t experience a substantial difference between C and Haskell? People talk about having a functional or imperative “mindset” – tribal motivations aside, this does not strike me as an imaginary difference. In another answer puffnfresh made this empircal point:

                              there are large groups of programmers who DO use the term to mean just programming with (mathematical) functions. You can ask a question in these groups “is this functional?” and get a consistent response; it has meaning!

                              Forget the value argument, which language is better, etc. I’m just interested if you really think there is no difference in the experience of writing and reading those languages, or how you think about that.

                              1. 6

                                Did you mean to imply that arbitrary meant “without value” here?

                                I mean to say that any desired value can be assigned as a judgement. Imagine a video game: The representations displayed on-screen are simulacra designed to remind the player of various symbols which they know from outside the game, but the inner logic of the game is only aware of bits and basic arithmetic operations. This sort of disconnection is called a “ludic barrier”. Similarly, there is a cultural barrier which separates the intuition for how a language appears to operate from the actual native type theory which governs its computation. On one side of this barrier, “immutable” is an opinion rather than a fact, and that opinion is grounded in memes rather than in formal proof.

                                And yes, words are arbitrary in this sense, with the barrier being both ludic and cultural; this was Wittgenstein’s massive insight which led him to develop the discussion around language games.

                                This feels like a technically correct but (at least partially) irrelevant fact to me. Is your argument that as a programmer you don’t experience a substantial difference between C and Haskell?

                                No, my argument is that Haskellers tend to share a memeplex, an interlocking collection of memes which undergirds a culture. For example, Haskell has plenty of mutability (IO, ST, STM all offer mutable references) but the meme is that Haskell’s data is always immutable. This Haskell culture imagines itself as part of a larger tribe which affiliates with other functional-programming cultures.

                                Another strong example, which should be food for thought but is instead usually pearls before swine, is that we are not programming with functions and sets. We can only compute the effective things, and we need to pay attention to what we can and cannot realize on a computer. (There are generalizations of functions, like those offered by category theory and the category of sets (WP, nLab); we can use a function-like environment to talk about computable functions and partial functions.) The top comment thread was right to point out the implications for computational complexity theory.

                                I’m just interested if you really think there is no difference in the experience of writing and reading those languages, or how you think about that.

                                All Turing-complete programming languages are Just Another Programming Language to me. I agree that the experience of expressing oneself in each distinct language is different, and further that there may be overlap in language features which leads to overlap in experiences. But I’m not willing to actually sign on to the poor definitions of “experience” and “feature” which folks usually are imagining in these sorts of discussions; experience is too hard to talk about still, and features are usually oriented around marketing rather than around shared fragments of type theory.

                                Put another way, I think that programming language design is almost entirely about UX and ergonomics, and choice of computational models only matters to the degree that it eases or frustrates the programmer’s ability to emulate that model and predict how the computer will interpret their expressions.

                                1. 1


                              2. 1

                                …whereas you, on the other hand…

                                1. 3

                                  Whereas I am allied with mathematics and logic. I feel that all Turing-complete programming languages have something to teach us, but that no Turing-complete language is perfect for any particular task. (There are interesting esoteric languages which challenge this, like HQ9+.)

                                  It happens that, when we combine mathematics and anthropology, we prove that we are all quite closely related, and that tribalism is thus an unnecessary and outdated framework for how we should conduct ourselves. When we find tribal urges within ourselves, we need to also dig deep and find empathy which can let us overcome tribalism in favor of proper multiculturalism.

                                  1. 2

                                    That’s asking for too much. Tribalism is fine for now, we just need to elevate representatives that are not embarrassing, you know; cooler heads prevail - and all that… With time maybe we’ll be able to blur the lines a bit more.

                                    1. 3

                                      I really don’t think it is, and I actually think this tribalism is holding us back. Tribalism around programming language puts pressure on individuals to choose a style; are you in the “functional” camp or the “bare-metal” camp? And given how arbitrary these distinctions are, we instead end up spending cognitive load on trying to figure out which camp a language or a person is in, rather than trying to more effectively look at the aesthetic benefits and tradeoffs the language provides. With less tribalism, we can explore the aesthetic space of Turing-complete (and Turing-incomplete!) languages and freely mix features of whatever programming styles we like into a mix of aesthetics that we feel will elevate the practice of programming. Rather than bikeshedding about whether Prolog is functional, declarative, or OOP, we can instead spend time asking ourselves what happens if we invent completely new programming paradigms that hit our aesthetic preferences better.

                                      On this very site, if you look at the disowned posts (posts by deleted users who have chosen to hide their username on their post), there’s a markedly higher percentage of posts about Go and C in the disowned group. What this implies, to me, is that some aspect of the community here has driven away the people that like to talk about Go and C. This, to me, is a sad thing. Learning is a collaborative activity and our shared experiences and explorations help drive research and practice forward. By creating a fractious environment you end up driving away the very activity that helps elevate the aesthetic goals of programming.

                                    2. 2

                                      I like math. I like that you like math. I like that you know way more about math than me. I like to understand your point of view. I don’t like being flagged, but I’m going to risk digging myself a little deeper by drawing your attention to the following irony:

                                      1. Tribes establish common values and cultural norms.
                                      2. The way you use phrases like “weasel word,” “allied,” “unnecessary and outdated,” and “how we should conduct ourselves,” is normative.
                                      3. The way I was flagged as a troll in an invitation-only forum is normative.
                                      4. A tribe that has a shared opinion about programming language design is, by definition, also a school of thought. Dismissing it as not a real school of thought because you reject its opinion is normative.

                                      I understand that tribes do ugly things. But the notion that you or any human being is completely above tribalism is, to put it as gently as I can without drawing further ire, inaccurate. We just demonstrated that in this very thread. Furthermore, the fact that mathematics are capable of perfect internal consistency does not preclude mathematicians from normative, tribal behavior within their discipline.

                                      1. 2

                                        Just to be clear, I’m the one who downvoted you as “troll”, not Corbin. And I stand by my judgement: calling out Corbin for criticizing people’s tribal behaviours while still engaging in them is an appeal to hypocrisy. If being subject to tribal instincts made Corbin unfit to criticize tribal attitudes, then nobody in the world would ever be able to except psychopaths.

                                        It’s also the kind of comment that’s guaranteed to bring out a defensive response, which is the actual definition of trolling. And the resulting thread, with its defensive attitudes and STEMlords-arguing-about-the-humanities topic is basically guaranteed to be frustrating and boring.

                                        1. 2

                                          I appreciate your perspective. I might not be able to give it the respect that it deserves, but that is my personal failing. I did not feel that you were unfairly curt with your first post; you made an excellent point that speared the heart of a problem that undermines my entire position. Socrates would be proud.

                                          I might be doing some sort of moral philosophy here, but I certainly don’t mean to imply that I’m somehow unaffiliated; I actively produce an object-based functional programming language, I spent years in the Python and Haskell communities, and I am not immune to propaganda. Of course I am a problematic and flawed person with a limited and broken perspective, hobbled by my own experiences and words. That does not mean that my critiques are useless; it means that I am subject to my own critiques.

                                          For what it’s worth, I will never flag you. I will always use my words to explain why I disagree with you. Also, for what it’s worth, by opening up this thread, I got at least three new flags and became the sixth-most-flagged user, earning the pink banner; this is not my highest score, but it’s close.

                                    3. 1

                                      Interesting. So are you saying that it’s only folks that enjoy or explore the functional style of programming that are like this? Or are all styles of programming tribes that are about attitudes towards people?

                                      1. 3

                                        There’s at least a few more tribes that are easily recognizeable:

                                        • Object-oriented programming: Computation is about objects, which are combinations of state and behavior that send messages to each other. The goal of computation is to have a network of interacting objects.
                                        • Assembly/bare-metal programming: Computation is about digital logic. The goal of computation is to go as quickly as possible.
                                        • Esoteric language design: Computation is about the technical details that make languages Turing-complete. The goal of computation is to be artistically expressive and to ponder the nature of computation.
                                        • UML diagramming: Computation is about the high-level nebulous relationships between business concepts. The goal of computation is to execute business operations.
                                        • Type-driven design: Computation is about types. The goal of computation is to simplify type-theoretic expressions and verify type-based proofs.

                                        In all of these cases, I’ve seen the memes extend from judgment on code to judgment on people.

                                        This doesn’t happen with all programming styles. For example, Wang tiles or Conway’s Game of Life can be Turing-complete, and it’s easy enough to imagine a programming tribe which insists that computation is about shapes and that the goal of computation is to have aesthetically-pleasing memory layouts, but I’ve not yet seen people judging each other because of their attitudes towards such tiled languages.

                                        1. 2

                                          That’s a fascinating perspective. Over the years, I’ve certainly seen passion, but I wouldn’t reach the same stark conclusion “functional programming is about attitudes towards people” as you. Of course, you’re welcome to think that, but I don’t.

                                          1. 1

                                            I think the memes of life and wang tiles are similar to those of the esoteric programming languages, insofar as the goal is not practicality but the digging of turing tarpits largely for personal edification.

                                  2. 3

                                    I agree that the term “functional programming” is so vague as to be almost meaningless. But if I were to be as pedantic as this author, then I would also have to say that there is no single thing called “functional programming” as a style, and it doesn’t exist on a linear spectrum, there are multiple dimensions of variation. The Haskell style is not the only kind of pure functional programming you can point at. Many Haskell people do not seem to distinguish between pure functional programming and programming using category theory, a static type system and higher order types. But it is quite possible to have a dynamically typed pure functional language where the idioms are different from Haskell idioms.

                                    1. 1

                                      dynamically typed pure functional language where the idioms are different from Haskell idioms

                                      e.g. Nix

                                    2. 2

                                      “Haskell is a dynamically-typed, interpreted language.”

                                      1. 4

                                        Yeah “interpreted language” is another fun term that’s completely meaningless. But I feel like I’ve already ranted on this site enough about that one! (tl;dr: nearly every language in widespread use today is most commonly used with a compiler, but the “compiledness” is a property of the language implementation rather than the language itself.)

                                      2. 2

                                        Since we are discussing this topic I want to share this must-see Guy Steele talk: https://www.youtube.com/watch?v=dCuZkaaou0Q

                                        Computer Science Metanotation is where we prove the properties of all these languages so that we can debate how appropriate or trustworthy they are but we don’t really pay enough attention to the appropriateness or trustworthiness of that notation in the first place.

                                        All code should be under perpetual review, that is the only way to build confidence in its applicability.

                                        1. 2

                                          The term makes less sense as more languages are getting functions-as-values and such. But if you look at the history, it makes more sense:

                                          In FORTRAN, not all procedures are functions, there are also subroutines. Performance used to be a bigger concern, and in mathematics there is no mutation. Obviously this doesn’t necessarily perform well, so you reach a compromise: you avoid copy-pasting code, but you let them use memory allocated by the caller (instead of copying).

                                          So to a FORTRAN programmer, the term “functional programming” absolutely does makes sense. Even FORTRAN-like languages have functions-as-values now. That the term now refers to stuff like higher-order functions doesn’t really bother me. It is still reasonably clear compared to vague terms like “Industrie 4.0”, “AI”, “smart contracts” or “big data”.

                                          1. 1

                                            If languages cannot be “functional”, can they be “safe”?

                                            On the one hand, it can be argued that it’s not what programming languages do, it’s what they shepherd you to. Even in a safe language like Rust, you may still shot your foot by doing funny things like 1 & 2.

                                            On the other hand, it’s virtually impossible to write type/memory-incorrect programs in Rust if you don’t deliberately ask for trouble, so the corner cases above don’t really defeat the language’s safety. Ultimately, I can define a dialect of Rust by stripping all its unsafe parts, and that should be an absolutely safe language since you literally cannot write type/memory bugs with it.

                                            1. 1

                                              While I like reading articles like this that question fundamental thinking, I did wonder about the premise on which this one was based. Perhaps I’m seeing thing too superficially - but I can’t think of a language where you’re so constrained that you are compelled to program in a single specific style. Add to that the fact that styles are, perhaps by definition, not entirely strict (the author alludes to this from a functional perspective in the article, in fact) and it seems more sensible to think of languages as having-support-for one or more styles.

                                              An example that immediately comes to mind is support for first class functions. Not all languages have that, and those that do, along with support for other aspects of the functional paradigm, can - at least in my eyes, be called functional.

                                              1. 1

                                                Is C functional, then? Is shell?

                                                1. 2

                                                  Not a C programmer, but I do program in shell (POSIX / Bash) on occasion. And for that, the answer is no.

                                                  1. 1
                                                    plus1() { echo $(($1+1)); }
                                                    times2() { echo $(($1*2)); }
                                                    map() {
                                                    	while [ $# -gt 0 ]; do
                                                    		($f $1)
                                                    map plus1 1 2 5 6 # passes 'plus1' function to 'map'

                                                    It’s call-by-name, and there’s only a single scope (local is not posix!), but nevertheless passes a function as an argument to another function.

                                                    map times2 $(map plus1 1 2 5 6) # it even composes!
                                                    1. 2

                                                      To me support for first class functions is primarily about not only input but output of functions. I’m not sure how one would produce a function from another function.

                                                      1. 3

                                                        It’s an interesting question (as, somewhat more relevantly, is the question of what it means to ‘return’ a function). Here’s what looks (at least to me) a lot like a function returning a closure:

                                                        add() { echo $(($1+$2)); }
                                                        fbind() {
                                                        	bind_counter=$((bind_counter + 1))
                                                        	eval "bound$bind_counter() { $1 $2 \$@; }";
                                                        	return $bind_counter
                                                        fbind add 5
                                                        map bound$? 1 2 5 6   # using previous definition of 'map'

                                                        We can’t do anything like map $(fbind add 5) 1 2 5 6, because the parentheses delineate a subshell, which cannot affect its parent’s environment. So in practice it’s a lot less comfortable to do functional programming in shell. But I don’t think it’s a stretch to say that you can replicate most things you would expect of a dynamically typed functional language, just a little more verbosely.

                                                        1. 1

                                                          I love this; thanks for posting.

                                                          Incidentally, this is similar to the way that they added lexical scope to elisp using a macro before it was supported in a first-class way in the runtime itself; it used gensym and resulted in a really hideous macroexpansion, but it more or less got the job done!

                                                          1. 1

                                                            Fascinating - and food for thought. Thanks!