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 think they meant data structures, not data types. Things like lists of records that each contain further records.
type 'a list = Nil | Cons of 'aAll 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.
Some commercial RDBMSs do use their logs for MVCC, though.
Personally I'm of the opinion that purity is impossible so if a paradigm needs purity it's going to be an uphill battle.
So it seems we can have out cake and eat it too!
[0] - https://www.microsoft.com/en-us/research/uploads/prod/2021/1...
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.
You really think functional programmers don't build composite types?
2. Immutable structures aren't immutable at the runtime level, https://en.wikipedia.org/wiki/Persistent_data_structure
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 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.
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.
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".
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
(1 + 2) * 3 + 2
(3) * 3 + 2
9 + 2
11
(1 + 2) + [(4 * 6)] + 1
(3) + [(4 * 6)] + 1
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.
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.
The problem is people don't trust it's really local even though it is.
Pure functions are easy to debug. Run it, check the result against expectations. Step in if necessary.
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.
"Optics". No one writing serious FP code copies memory around willy-nilly.
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.
a = [1, 2, 3]
b = a.append(4) // append: list->int->list
// Rest of the code never refers to a, but refers to b
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.
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.
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.
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.
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.
And even then, there is the question of whethwr it is a deep or shallow copy on receiving or write.
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.
The link(s) the others shared is a great article.
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.