Functional programming with immutable state cannot possibly win in the general case.
There are two truths that ensure the dominance of imperative software:
1. At some level of software complexity, programmers MUST start to organize data into composite objects. They have to do this because working outside of well-defined problem domains is a recipe for buggy software and spaghetti code.
2. Copying memory around to enable to facilitate these immutable structures is SLOW.
> At some level of software complexity, programmers MUST start to organize data into composite objects.
I don't understand this point. All functional programming languages have algebraic data types and records, which are composite types. If this is not a "composite object", you'll have to clarify what you mean.
> Copying memory around to enable to facilitate these immutable structures is SLOW.
Slower than what and in what context? Append-only logs in relational databases are immutable data structures, and they enable multiversion concurrency control, which is faster and more scalable than locking when there's lots of contention.
Unqualified claims like "immutable data structures are slow" is just wrong.
> I don't understand this point. All functional programming languages have algebraic data types and records, which are composite types. If this is not a "composite object", you'll have to clarify what you mean.
I think they meant data structures, not data types. Things like lists of records that each contain further records.
All data structures have types. EVEN lists of records that each contain further records. A type or a data structure is an orthogonal concept to FP, because types exist in imperative programming and data structures also exist in FP.
Note: the log (aka write-ahead-log) in Postgres, and its ilk, enables the D(urability) of ACID. MVCC in Postgres is implemented by storing the visibility info of each row in the row-header (search: xmin, xmax).
Some commercial RDBMSs do use their logs for MVCC, though.
Why have immutable data structures not taken over in the general case if it's a strict improvement? Sometimes they're good and sometimes there not. The issue is functional programming needs them to be used in every case.
Personally I'm of the opinion that purity is impossible so if a paradigm needs purity it's going to be an uphill battle.
FP doesn’t require their use in every case. For example, Clojure allows mutation as an optimization. But for the normal path, immutable data structures are just fine and help avoid a whole host of bugs.
Ah, but you don't always have to copy memory around to facilitate immutable datastructures. Koka lang and Roc lang are at the forefront of a functional-but-in-place (FBIP) style of memory management that use hyper-fast ref-counting and if a function owns the sole reference to a datastructure can mutably modify it instead of deallocating & reallocating.
The most recent Perceus reference counting paper, implemented in Koka, had Koka's functional and persistent Red-Black tree 10% faster than the handwritten C++ version (std::map) [0], and the Roc language has a purely functional quicksort version competitive with standard imperative languages.
Does Perceus differ substantially from using https://lib.rs/crates/im and writing code which looks identical to imperative code, but cloning is faster and mutations are slower (and copy internal structures as necessary)?
It does the same mutate-if-unique optimization as im, but it does so automatically and more broadly as a part of its optimized reference counting. Perceus can go beyond what im can do by re-using allocations between static types - one of their examples involves doing a tree traversal with O(1) extra space by using a zipper which gets optimized by Perceus into a Morris traversal - and the programmer doesn't have to do anything special to get the benefit! (of course, writing code in such a way that you know it will be optimized has performance benefits if you do know how it works) This sets up this wonderful situation where you can write easier-to-maintain and easier-to-verify-correct algorithms that get optimized into very efficient versions that would be hard to write by hand even in a mutable/imperative language.
Their papers and online docs are very good, I highly recommend them for more information!
Both working on making functional programming practical and very fast. Koka is more of a research language, also developing Algebraic Effects and making them practical, which is very cool.
Functional programming doesn't actually compete with imperative programming.
In practice, functional programming is a way of organizing imperative programs. Kind of like how OO is a way of organizing imperative programs.
Almost all applications written in Haskell use the IO monad quite a bit, for example. Large Haskell projects generally use a lot of C libraries, and sometimes even directly include C code for performance sensitive bits.
I think part of the problem is no implementation has an exciting story about writing the "shell" part in a different language. I love love love writing purely functional code. Probably my favorite thing to do. But what a lot people who also like functional programming are missing is writing imperative code in functional languages almost invariably sucks. At the end of the day we all have to write the "shell" part of our Haskell programs, and my programs always end up in a horrific mess of IO, State and other monads.
> writing imperative code in functional languages almost invariably sucks.
I don't agree at all!
Haskell is extremely pleasant for imperative programming.
There's a learning curve for sure, but you get a lot in return. (STM is one small example). I would much rather write imperative Haskell than Python.
It does gets messy when you start writing really low level code (direct pointer manipulation, etc). And it sucks for small scripts (too much project boilerplate, small standard library). But those are the only real pain-points.
> At the end of the day we all have to write the "shell" part of our Haskell programs, and my programs always end up in a horrific mess of IO, State and other monads.
You can very successfully keep nearly all IO at the edges and do the heavy lifting in pure functions if you make it a goal.
The biggest problem I have with functional programming is debugging.
On imperative code, execution is easy to follow. Instructions go one after the others, loops loop, function calls and local variables go on the stack, globals are always visible. Optimization aside, what you code is what the computer runs. You often have a debugger to step through your code, or some logging facilities, even if it is just a printf.
On functional programs, the idea is usually that you manipulate stuff, but you don't know what you manipulate. You apply a functions to functions making other functions until you end up with the function that turns the input of your program into the output of your program. Then you let the compiler do its magic, it is actually really good at that and not slow. But then you end up with something that doesn't look at all like what your wrote (computers are imperative), and if, in the end, the result is wrong, good luck finding where. The debugger will give you the state of the program in a program that has no state, and logging is a side effect in a program without side effects.
Functional programming is not bad, I love pure functions, but in the end, I think it is just a tool. A solution to a set of problems, but not enough to stand by its own for most projects. And it is evident from most modern programming languages. Most of them have some functional paradigms, and could likely be used to write pure functional code, but is better suited as something to use just when you need it.
Debugging in a strict FP language is pretty much exactly like debugging in an imperative language. Debugging in a lazy FP language requires somewhat different approaches, but still does not have the problems you are implying here.
> In the end, the result is wrong, good luck finding where.
This is not true. If this was true, nobody would be able to build significant things in FP languages.
> Optimization aside, what you code is what the
computer runs.
> But then you end up with something that doesn't
look at all like what your wrote.
No, you can trace code down through the compiler
transformations and generally understand what
is going on at each level of abstraction.
Compilers for imperative languages are just as
"magical".
I like FP but debuggers fail with FP because debuggers are imperative tools. There's a definite miss match in both UI and concept. It's not the fault of FP itself, it's more the fault that we haven't come up with such an interface yet.
If you want an FP debugger the interface has to be able to step by step evaluate an expression. Since FP is just a giant expression, how is it evaluated step by step? Break points will be different and stepping through it will be different as well.
Take for example:
(1 + 2) * 3 + 2
Stepping through it with a debugger would look like this (imagine the expression transforming at each step):
(1 + 2) * 3 + 2
(3) * 3 + 2
9 + 2
11
A break point would look like this (square brackets indicate a GUI marker)
(1 + 2) + [(4 * 6)] + 1
A run until breakpoint will evaluate to this:
(3) + [(4 * 6)] + 1
That's it. Debugging FP is about stepping through expressions. Debugging Imperative programming is about stepping through statements. And the unique thing about "stepping" through an expression is that the expression is getting reduced (aka changing) at every step.
You need a complete UI overhaul for FP to work. This tends to be harder in terms of building a UI, because text by nature is a one to one mapping to procedural instructions as text Lines are equivalent to instructions. However for FP everything can basically be on one line, so text doesn't really fit and thus you actually need a more dynamic UI for a proper FP debugger.
> On imperative code, execution is easy to follow. Instructions go one after the others, loops loop, function calls and local variables go on the stack, globals are always visible. Optimization aside, what you code is what the computer runs. You often have a debugger to step through your code, or some logging facilities, even if it is just a printf.
I think you're doing something wrong.
Because your experience should be exactly the opposite. Imperative programming by distributing its state can only really be understood in context. You need to understand that instruction one after another, just like you said. You need to understand globals and the overall state.
In functional programming you understand code without context. Everything is local. There's nothing to trace.
> Then you let the compiler do its magic, it is actually really good at that and not slow. But then you end up with something that doesn't look at all like what your wrote (computers are imperative), and if, in the end, the result is wrong, good luck finding where
What does the compiler have to do with anything here?
You can print out whatever state you want, your debugger can provide you with whatever local state you want. There's nothing obscure or mysterious about functional code compared to imperative code. It's just a matter of not distributing your state widely.
This isn't my experience at all. Imperative code with side effects is harrowing to debug because it may do different things depending on what execution path got you there.
Pure functions are easy to debug. Run it, check the result against expectations. Step in if necessary.
I think this comes down to experience. My favorite programming language is Agda and I have a lot experience writing code in Haskell and Lisp variants. I personally also find it trickier to debug in functional languages. I believe this comes down to how you debug: I am comfortable using a debugger for debugging but I simply find it easier to debug using prints (for context switching reasons) but this is not always an option in a purely functional context without any IO. This does push me out of my comfort zone sometimes, and I would say it's accurate that I debug much faster in imperative languages. Even though I write better and safer code in functional languages (and even though I like them better).
>I love pure functions, but in the end, I think it is just a tool. A solution to a set of problems,
I'm tired of seeing this analogy everywhere. Everyone knows it, there's nothing new here. When we talk about things like FP or OOP, the real opinions live at the extremes. Where one tool is definitively better than another tool or where some tools are complete garbage.
Saying that everything is a tool for different things or it's all apples and oranges says nothing about anything.
Well written compilers for functional programming language do not copy immutable data. I recommend searching for “Immutable Data Structures” to see how you can implement very high performance immutable data structures. Haskell and Closure (for example) does this and Haskell is faster than most imperative languages out there. I recommend learning more about this subject.
Immutable data structures often don’t copy a lot of data around. Immutable linked lists have tail references from each head. If something falls out of scope it gets collected by the garbage collector. Also if you don’t share memory between processes, you can free that memory once a process terminates, which may seem orthogonal but it’s a core principle in Erlang.
FP maps perfectly to networked applications that integrate more than one machine (i.e. client/server, APIs, and larger distributed systems). networked applications arguably IS the “general case”; it’s the platform specific stuff which is getting paved over by data/function abstractions
True. My use of the word "speed" is incorrect, or at least imprecise.
The parent comment claimed that immutable data structures are slow, because you would have to copy them around, an O(N) operation.
I wanted to know if they considered that operations on immutable structures can be done without copying, and have the same algorithmic complexity as the mutable data structures, if they used persistent data structures.
Others already argued against your point, but I want to point out that (2) is simply wrong. You can have mutability in functional programming -- not in general, but there are cases where this can be expressed. For example, in a very simple example:
a = [1, 2, 3]
b = a.append(4) // append: list->int->list
// Rest of the code never refers to a, but refers to b
In this code, you can prove that it's safe to move a's memory into b and thus append operation can be done without copying a. I'm not implying this is easy to implement, but it's clear that this is not a fundamental issue in functional programming, rather a deficiency in its current implementations.
Right, but FP has been around for quite some time, and given that none of the current implementations actually solve this issue right now I think it is a valid critique of FP because it's simple what current FP implementations are limited to.
Maybe a "sufficiently advanced compiler" in the future will solve this, but it's not at all clear such a thing can be created in a way that's practical right now.
> Right, but FP has been around for quite some time, and given that none of the current implementations actually solve this issue right now I think it is a valid critique of FP because it's simple what current FP implementations are limited to.
No idea what you mean.
Mutable state is not a problem in Haskell. You can have high performance libraries that provide mutable APIs that are safe to use. You can have code that looks more imperative if you want. If you really want to go nuts you can use linear types and solve such problems in a completely general way.
> Maybe a "sufficiently advanced compiler" in the future will solve this, but it's not at all clear such a thing can be created in a way that's practical right now.
There's no need for any advanced compiler. We have all of this today.
> ...and given that none of the current implementations actually solve this issue right now...
This has been possible in Haskell for a long, long time. A ton of languages do something very similar with strings (Python, JavaScript, etc.) Strings are immutable in both Python and JavaScript, but rather than using a "StringBuilder" class like in C# or Java, the compiler and runtime will optimize certain pure functional operations (like string concatenation) into a mutable operation on a buffer. If you are not aware of this optimization, you might find yourself benchmarking some simple string operations and be completely shocked at how fast they are. (There are a couple questions on Stack Overflow where people are confused about why their Python code is faster than their C++ code when benchmarked.)
I think the term "sufficiently advanced compiler" does a bit of a disservice. People have used that phrase a lot, not only when talking about high-level languages but also when talking about things like ISAs. It turns out that people are bad at predicting what kinds of optimizations compilers will be able to do in the future.
The other reason I don't like the phrase "sufficiently advanced compiler" is because these optimizations are often tied to something other than the compiler. They may come from advances in library implementations, advances in programming languages, or advances in language runtimes.
Take a look at how Haskell does it. You have array implementations with a pure interface but impure implementation. You have a system called "stream fusion" which lets the compiler take array operations that logically produce arrays as values, and transform these into simple operations that loop over the array. Stream fusion is a feature that doesn't really require a "sufficiently advanced compiler", but rather some relatively simple compiler features (all things considered, "simple" is relative) and the ability to annotate library functions with transformations that improve the generated code at the library functions' call sites.
I think of stream fusion as more of a "let's write good libraries" feature, and less of a "compiler magic" feature.
Then take a look at how Python does it. When you concatenate strings, the library code can check that the left-hand argument has no other references, and modify it in-place. All the compiler has to do is make sure that variables are killed as soon as possible, which is a very ordinary thing for compilers to do. It's not magic, there are ways to break this optimization from happening, but it does work.
Have you seen the AWS go sdk? It basically builds linked lists (no locality) of everything and marshals to and from json over and over like it's free. I mean there's no thought whatsoever to making efficient use of memory, getting locality for improved performance, etc.
And if you think about it, most things using the aws sdk are network i/o bound anyway, which is probably why they burn ram and generate garbage like it's free.
So immutable data structures (especially persistent ones) aren't a problem at all in many domains.
Copying is an implementation detail, it doesn’t have much to do with FP in itself. If anything, due to the compiler knowing that variables can’t change, it can optimize away copies much much more aggressively than a “traditional” PL.
2. Copying memory around to enable to facilitate these immutable structures is SLOW.
This is categorically wrong. You actually don't know what you're talking about.
In an functional programming language, because everything is immutable, the compiler just MOVES everything around. There is ZERO copying in a functional programming language. In fact there's no explicit command for it either. There is zero reason for you to copy a variable that is immutable so there's no copy() function.
What you're referring to is more of what happens when someone is writing functional code in a language that's not functional.
> 1. At some level of software complexity, programmers MUST start to organize data into composite objects. They have to do this because working outside of well-defined problem domains is a recipe for buggy software and spaghetti code.
Right. and FP provides NO way to composite objects
> 2. Copying memory around to enable to facilitate these immutable structures is SLOW.
Who says you have to (multiple others have pointed to resources)
the entire point of some of the immutable structures is hidden in their implementations, such that they are fast exactly because they do NOT copy unnecessarily. the side effect gets called "functional", so there's a strange reversal of importance of (kinda misleading) buzzwords at play here.
There are two truths that ensure the dominance of imperative software:
1. At some level of software complexity, programmers MUST start to organize data into composite objects. They have to do this because working outside of well-defined problem domains is a recipe for buggy software and spaghetti code.
2. Copying memory around to enable to facilitate these immutable structures is SLOW.