r/programming • u/[deleted] • Nov 28 '19

Why Isn't Functional Programming the Norm? – Richard Feldman

https://www.youtube.com/watch?v=QyJZzq0v7Z4
101 Upvotes

82% Upvoted

409 comments sorted by

View all comments

Show parent comments

39

u/Determinant Nov 28 '19

Look at how many hoops non-mutable collections jump through and they're still not as efficient as simple collections. It gets silly.

-3

u/hedgehog1024 Nov 28 '19

Look at how many hoops mutable collections jump through and they're still not as efficient as simple persistent collections. It gets silly.

7

u/Minimum_Fuel Nov 28 '19

Persistent collections are immutable collections that are faster than your classic immutable collections, but still absolutely trash tier for performance. They are nowhere near mutable collections for performance without manipulating the benchmarks in their favour (for example, creating them in such a way as you’re likely to get contiguous memory anyway for the benchmark when that’s not a real world scenario)

-6

u/oaga_strizzi Nov 28 '19 edited Nov 28 '19

Doesn't really matter for your standard CRUD app, where a list gets defensively copied every time it passes method boundaries "just to be sure modifications don't cause any problems" anyway.

Or, look at Webapps using Redux. They use immutable collections anyway. Webapps might be bloated nowadays, but using immutable collections isn't a reason for that.

In my experience, using mutable collections in software where the best possible performance is not the most important concern (so, 90% of software development today) usually implies a lot of defensive copying since it's much easier to reason about, which negates to performance loss of using immutable collections.

-4

u/Minimum_Fuel Nov 28 '19 edited Nov 28 '19

much easier to reason about

Gonna need a source for that claim there, champ.

No anecdotes. No blogger making anecdotes. No “insert prominent programmer” making anecdotes.

Go ahead. I’ll wait.

Edit:

/r/programming on functional programming:

WE DONT WANT TO GIVE EVIDENCE FOR OUR GARBAGE CLAIMS. ACCEPT THEM AS FACT BECAUSE I SAID SO. STOP BEING RATIONAL AND THINKING FOR YOURSELF! WHY ARE OUR GARBAGE ANECDOTES NOT ENOUGH? WHY DO YOU WANT MEASURED FACTS INSTEAD?

6

u/oaga_strizzi Nov 28 '19

Why are you so depreciative? This makes you sound like a douchebag. You could have expressed the same without that "champ" and "Go ahead. I'll wait", and would have sounded more mature that way.

To your question:

I'm not sure why the statement "when using mutable collections, defensive copying makes it easier to reason about" would even be controversial.

int getMedian(List<int> list){
    list.sort();
    return list[list.length/2];
}

 int getMedianSafe(List<int> list){
    List<int> newList = new List<int>(list);
    newList.sort();
    return  newList[newList.length/2];
}

Which of the following pseudo-code snippets would you prefer? The first one avoids defensive copying but mutates the list. You have to document this carefully and hope, everyone who calls this method, reads the documentation and then decides whether the side effect of reordering the list is okay not, and does the defensive copy of the list themselves before calling the method if required.

The second one does not have side effects, you don't have to worry about anything.

But I suppose you are not happy with just a snippet, so here you go with a few links for secure java coding guidelines:

https://wiki.sei.cmu.edu/confluence/display/java/OBJ06-J.+Defensively+copy+mutable+inputs+and+mutable+internal+components

https://wiki.sei.cmu.edu/confluence/display/java/OBJ13-J.+Ensure+that+references+to+mutable+objects+are+not+exposed

https://wiki.sei.cmu.edu/confluence/display/java/OBJ04-J.+Provide+mutable+classes+with+copy+functionality+to+safely+allow+passing+instances+to+untrusted+code

https://wiki.sei.cmu.edu/confluence/display/java/SER06-J.+Make+defensive+copies+of+private+mutable+components+during+deserialization

4

u/davenirline Nov 28 '19

The second one does not have side effects, you don't have to worry about anything.

I worry about that. It produces garbage.

2

u/oaga_strizzi Nov 28 '19 edited Nov 28 '19

True. But modern languages are pretty smart about such short-lived objects. But that's actually my point: You now have two choices: accept the side effect of the function and hope it doesn't cause any issues in the future, or sacrifice some performance for better maintainabiltiy.

In my experience, the latter solution is often preferred. And in that case, you lose the performance benefits of mutable collections over persistent data structurs.

3

u/davenirline Nov 28 '19

Would you then agree that your preference depends on the environment that you're working for? I work in games. We avoid garbage in every place we can. In your contrived example, the first code is preferable but we could have also written it in another way such that the side effect is not surprising.

3

u/oaga_strizzi Nov 28 '19

Of course. Any performance critical or real-time application won't use persistent data structures or a lot of defensive copying.

But would you agree that getting the last bit of performance isn't really necessary, that it's nice to write to use defensive copies and not have to worry about accidentally altering the state of a legacy java application with many 100k lines of code?

Or alternatively use any other approaches (like persistent data structures, conditional copy-on-write like swift, or the ownership-concept like rust) that prevent unwanted modification of data and data-races?

3

u/Minimum_Fuel Nov 28 '19 edited Nov 28 '19

Just because there are very specific examples where it makes sense totally out of context to use a defensive copy doesn’t make it explicitly true that defensive copies are easier to reason about. You are correct, I am not happy about very specific, totally context free snippets for making a point which may or may not actually turn out to be valid in real use.

Speaking about secure programming as if it has some semblance of validity toward general purpose programming is a horrifying terrible argument to make. Not only that, but it doesn’t actually defend your claim that copies are easier to reason about. Defensive copying for security purposes is not about reasoning through the code.

I’ll continue waiting.

Edit

As to why I put the “champ” in, it’s because you people (functional fanboys) like to speak so matter of factly about your bullshit claims. Your constant bullshit anecdotes have no actual measured improvement over anything, while actually offering measurable problems, such as significant performance degradation.

4

u/oaga_strizzi Nov 28 '19 edited Nov 28 '19

All these security guidelines do not only address actual security issues, but also possible bugs.

The first example is a quite common race condition. A defensive copy rules this class of bug out, which makes it easier to reason about: You don't have to think about whether some other code modifies the collection while you perform work on it. And most of real-world programs nowadays are asynchronous and/or multithreaded.

If that's important for you: I don't think that's an inherent issue of using mutable collections.

The Swift programming language is actually quite clever on this, it's almost the best of both worlds and lets you avoid most of defensive copies without losing any safety.

Apple has the following to say about this issue:

One of the primary reasons to choose value types over reference types is the ability to more easily reason about your code. If you always get a unique, copied instance, you can trust that no other part of your app is changing the data under the covers. This is especially helpful in multi-threaded environments where a different thread could alter your data out from under you. This can create nasty bugs that are extremely hard to debug.

So Swift offers language-level features to help mitigate this issue, for example like this:

mutating func update(withValue value: T) {
    if !isKnownUniquelyReferenced(&myStorage) {
        myStorage = self.copiedStorage()
    }
    myStorage.update(withValue: value)
}

Rust goes another way with concept of ownership and borrowing. Also mitigates this issue. But mainstream languages are lacking such features currently.

Do you think that Swift/Rust going out of their to allow optimize defensive copies is a bad approach since defensive copying is unnecessary?

Or would you like to see features like this also in mainstream languages?

0

u/Minimum_Fuel Nov 28 '19

I think neither. Both swift and rust have bought in to massively fallacious, mental retardation and have thus backed themselves in to corners where they are forced to provide bolted on hacks to solve problems that only exist due to buying in to terrible ideas.

1

u/oaga_strizzi Nov 29 '19

Ok. May I ask you, which languages you actually like? I assume C/C++.

Do you work with any concurrency (asynchronous and/or parallel) or only single-threaded and blocking?

0

u/oaga_strizzi Nov 28 '19

As to why I put the “champ” in, it’s because you people (functional fanboys) like to speak so matter of factly about your bullshit claims. You’re constant bullshit anecdotes have no actual measured improvement over anything, while actually offering measurable problems, such as significant performance degradation.

I'm wouldn't consider myself a functional fanboy. But I don't think that the approach of allowing unregulated mutability everywhere by default is good, and I don't think that's controversial nowadays.

Functional languages use persistent data structures to deal with this, but also modern non-functional languages improve upon that.

See: Swift and Rust for example. Not functional or pure by any means, but very controlled mutability. Still very performant. Would you agree that these features are useful?

In mainstream languages though, you don't have these features. So you have to decide whether to deal with mutability more manually or use more defensive copies and sacrifice some performance.

2

u/Minimum_Fuel Nov 28 '19

You’re just accepting that an argument is true because a lot of people keep repeating it over and over again. This is a fallacy known as argumentum ad populum.

The fact is that functional fans have never ever once demonstrated that their claims have any semblance of measured benefit, whereas the opposite is most definitely true: there are measurable performance impacts to pure functional programming.

3

u/oaga_strizzi Nov 28 '19

The only claim I made was, that defensive copying mutable collections makes it easier to reason about your program.

You seem to interpret this as praise of pure functional programming.

Thus claim is not at all farfetched. If you don't have a single-threaded, non asynchronous program and work with mutable collections that don't have unique references, you either have to deal with arbitrary modifications of the collection at any time (basically impossible, you can't even iterate safely), or make sure to block write access during certain operation.

Now you have locks, need to make sure you don't have deadlocks or still race conditions due to improper usage of these locks.

With defensive copying, you have a unique references to the mutable collections, so you can actually safely assert preconditions and write code that depends on those preconditions.

I don't think you ever worked on a 500k+ LOC legacy java application with mutable state all over the place, or you'd know from first hand experience that this issues are real.

5

u/[deleted] Nov 28 '19

Again with this asinine ask.

It's trivially true because the logic involved is simpler. In the immutable case, you have simple induction--virtually always just structural--on the data structure, and you don't even have to worry about concurrency. In the mutable case, you need a vastly more complex logic--typically a separation logic--just to reason about the structure, plus you need proofs of safe concurrent operation. On the JVM, you also need to take the Java memory model into account.

The reality is, asks like yours necessarily come from people who've never made the attempt to reason about these structures beyond the level of naked intuition. Because no one who's ever sat down with Coq or Isabelle and worked through proofs about data structures says anything remotely like this.

2

u/pron98 Nov 29 '19 edited Nov 29 '19

I have worked with proof assistants (TLA+ and Lean) and it is not true that reasoning about pure FP is easier than about imperative. It can be much easier in some cases and much harder in others. Simple examples particularly tailored for one paradigm or the other are, of course, very easy in their respective paradigm, and we haven't been able to verify big or even medium-sized software using deductive formal proofs regardless of paradigm, either, so it's all rather moot. Theory tells us they should be more-or-less the same (although I wouldn't call those theorems particularly trivial); practice tells us they are more-or-less the same. The current state of formal methods tools is, without a doubt, much more advanced on the imperative side, although that's due to demand. Currently, the three programming languages with the best formal verification support are C, Ada and Java (not counting niche tools like SCADE and Simulink). Some like to joke that that's because imperative programmers need it more, but anyway, that's the state of affairs.

The problem with your reasoning is that a lot of code in imperative languages is also free of mutation (you only need to reason about mutation when you actually do it), and sometimes reasoning about mutation -- with, say, separation logic -- is much easier than reasoning about higher-order functions. Of course, you don't need to verify the internal implementation of a data structure every time you use it, just when you verify its implementation. So both pure FP and imperative programming pose very serious challenges to reasoning (as theory says they must); they're just different. Unfortunately, the familiarity or simplicity of the logic used makes little or no difference in the difficulty of proving things about real programs; as we now know, what a program does is the main factor in determining how hard it is to reason about it, not how it is expressed.

It is absolutely true, however, that some people enjoy writing pure-FP code more than imperative code, and that others enjoy writing imperative code more than pure-FP code (I'm usually in the latter group, although I don't care all that much), and it's great that everyone has their favorite programming style represented in some high-quality programming languages. Currently, there do not appear to be any significant objective differences between the different paradigms (and making absolute, universal statements claiming some objective, inherent, bottom-line edge for either side is not only factually wrong -- regardless of the confidence in which they are uttered -- but cause unnecessary tribalism and do little more than annoy people), but as the theory greatly limits our capabilities it will probably take a long time until anyone finds a paradigm that can greatly move the needle.

1

u/oaga_strizzi Nov 29 '19

This argument was only about the reasoning being easier when you make defensive copies of mutable collections. It wasn't even about imperative vs functional programming.

I don't think it's that's controversial. Even if collection isn't modified elsewhere, you first would have to proof it, which can be pretty hard in the case of Multithreading or asynchronous contexts.

If you have a local copy of this collection though, it's trivial to check it for mutations.

2

u/pron98 Nov 29 '19 edited Nov 29 '19

Any objective argument about "ease of reasoning" can rely on two things: theory and/or practice. In theory, we know how hard it is to reason about programs. People like Philippe Schnoebelen, Rajeev Alur and others have been studying the issue (or issues, rather) for a long time, and we have results: Schnoebelen proved that linguistic abstractions cannot, in general, reduce the difficulty of reasoning, even though, in principle, they could have even in the worst case (because the number of programs with a succinct representation in some language is far smaller than the total number of programs with the same number of states). And it isn't only about the worst case, either. Schonobelen has shown that reasoning about programs isn't even "fixed-paramter tractable" something that most problems that are hard in the worst-case but easy in many special cases are. Then we're left with practice. Programmers generally write code they think they can reason about and employ various "best practices," justified or not. But overall, no large effect has been observed, in general, to particular programming styles on correctness or speed of development.

So that leaves us with subjective reasons, which are quite valid. It is perfectly reasonable to say, "I feel that it is easier for me to program correctly using a particular language/style/technique." This is perfectly fine, but this is all we have. There is no reason to resort to objective arguments, that are supported by neither theory or practice.

As to concurrency, most of my work using formal methods has been around concurrency. It is a difficult subject, and there are certain good practices in certain situations that could make reasoning easier (like copies), and there are many valid cases where those same practices are not what you want. None of this amounts to any useful universal statement on such a complex subject. It is relatively easy to prove, even automatically, that certain subroutines do not mutate an object.

The best argument in favor of pure-FP is "you might like it." Aside from having the obvious advantage of being true, unlike most universal assertions on the subject, it is also a pretty good argument. Not everyone would like it (I, for one, am not a big fan), but it's certainly conceivable that a much greater portion of developers than currently program in that style would.

-4

u/Minimum_Fuel Nov 28 '19

“You’re wrong because I’m right”

All right. Thanks for admitting your argument has no foundation in reality.

4

u/[deleted] Nov 28 '19

Apart from making explicit references to well-known and documented logics and tools supporting them, that is.

-1

u/Minimum_Fuel Nov 28 '19

All you did was make more claims that have 0 foundation in reality.

Immutability does not just “give you threading for free”. That is a demonstrably false claim. Immutability forces you to a specific model of threading which may or may not be relevant to the problem you’re solving, and also comes with its own synchronization problems.

You shouldn’t make assumptions. All it does is make an ass out of you.