7 ms·

Functional programming with immutable state cannot possibly win in the general case. There are two truths that ensure the dominance of imperative software: 1.

by dolni 4y ago

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.

kaba0 4y ago
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.
mholyland 4y ago
Are you considering the speed of persistent data structures, that have the same big-O as their mutable counterparts? [0] 0. https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure
- Avshalom 4y ago
  Algorithmic complexity isn't the same as speed.
  - mholyland 4y ago
    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.
pjmlp 4y ago
1. Mainstream FP languages have modules and OOP support as well. 2. Immutable structures aren't immutable at the runtime level, https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure
jjtheblunt 4y ago
> 2. Copying memory ... 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.
miloignis 4y ago
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. So it seems we can have out cake and eat it too! [0] - https://www.microsoft.com/en-us/research/uploads/prod/2021/11/flreuse-tr-v1.pdf https://www.microsoft.com/en-us/research/uploads/prod/2021/1...
- pyuser583 4y ago
  Koka-lang and Roc-lang? What are those?
  - miloignis 4y ago
    https://koka-lang.github.io/koka/doc/index.html https://koka-lang.github.io/koka/doc/index.html https://www.roc-lang.org/ https://www.roc-lang.org/ 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.
    - tomcam 4y ago
      90% sure these are Malaysian soft drinks
- nyanpasu64 4y ago
  Does Perceus differ substantially from using https://lib.rs/crates/im 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)?
WkndTriathlete 4y ago
> Copying memory around to enable to facilitate these immutable structures is SLOW. "Optics". No one writing serious FP code copies memory around willy-nilly.
- Koshkin 4y ago
  No, but the compiler may do it for you.
  - riku_iki 4y ago
    why it would copy and not be passing immutable data by reference?
valbaca 4y ago
> 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)
dustingetz 4y ago
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
GuB-42 4y ago
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.
- anon_d 4y ago
  I don't think this is accurate at all. 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".
  - deltaonenine 4y ago
    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.
anon_d 4y ago
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.
- gnulinux 4y ago
  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.
  - anon_d 4y ago
    > 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.
  - ParetoOptimal 4y ago
    > 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.
naasking 4y ago
> 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.
- jayd16 4y ago
  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.
  - christophilus 4y ago
    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.
    - yencabulator 4y ago
      I'd argue that means Clojure lets you use paradigms other than FP. FP is still FP.
- gurjeet 4y ago
  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.
throwamon 4y ago
Clojure
gnulinux 4y ago
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.
- Beltalowda 4y ago
  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.
  - klodolph 4y ago
    > ...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.
ebingdom 4y ago
This is a really uninformed opinion. I'm disappointed that it's currently the top comment. You really think functional programmers don't build composite types?
- deltaonenine 4y ago
  It's like listening to a flat earth advocate.
charlieflowers 4y ago
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.
mbrodersen 4y ago
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.
phillipcarter 4y ago
This comment is a fine example of what it's like to have strong opinions about something you've never used.
ch4s3 4y ago
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.
- yencabulator 4y ago
  Those copy-on-write linked data structures, with the implied pointer chasing, have a cost. That's what the parent is talking about...
  - ch4s3 4y ago
    A lot of languages, like Erlang/BEAM, use pointers under the hood and aren't necessarily copying anything.
deltaonenine 4y ago
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.
- Akronymus 4y ago
  > 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.
  - deltaonenine 4y ago
    just pass a const reference. It's immutable anyway.
    - Akronymus 4y ago
      Unless that ref holds a mutable reference. C++ doesnt make it easy at all to have something be truly immutable.
      - deltaonenine 4y ago
xigoi 4y ago
Check out HVM, an experiment to make copying immutable data really fast: https://github.com/Kindelia/HVM https://github.com/Kindelia/HVM

by dolni 4y ago

kaba0 4y ago

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.

mholyland 4y ago

Are you considering the speed of persistent data structures, that have the same big-O as their mutable counterparts? [0] 0. https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure

Avshalom 4y ago
Algorithmic complexity isn't the same as speed.
- mholyland 4y ago
  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.

pjmlp 4y ago

1. Mainstream FP languages have modules and OOP support as well. 2. Immutable structures aren't immutable at the runtime level, https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure

jjtheblunt 4y ago

> 2. Copying memory ... 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.

miloignis 4y ago

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. So it seems we can have out cake and eat it too! [0] - https://www.microsoft.com/en-us/research/uploads/prod/2021/11/flreuse-tr-v1.pdf https://www.microsoft.com/en-us/research/uploads/prod/2021/1...

pyuser583 4y ago
Koka-lang and Roc-lang? What are those?
- miloignis 4y ago
  https://koka-lang.github.io/koka/doc/index.html https://koka-lang.github.io/koka/doc/index.html https://www.roc-lang.org/ https://www.roc-lang.org/ 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.
  - tomcam 4y ago
    90% sure these are Malaysian soft drinks
nyanpasu64 4y ago
Does Perceus differ substantially from using https://lib.rs/crates/im 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)?

WkndTriathlete 4y ago

> Copying memory around to enable to facilitate these immutable structures is SLOW. "Optics". No one writing serious FP code copies memory around willy-nilly.

Koshkin 4y ago
No, but the compiler may do it for you.
- riku_iki 4y ago
  why it would copy and not be passing immutable data by reference?

valbaca 4y ago

> 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)

dustingetz 4y ago

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

GuB-42 4y ago

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.

anon_d 4y ago
I don't think this is accurate at all. 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".
- deltaonenine 4y ago
  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.

anon_d 4y ago

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.

gnulinux 4y ago
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.
- anon_d 4y ago
  > 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.
- ParetoOptimal 4y ago
  > 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.

naasking 4y ago

> 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.

jayd16 4y ago
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.
- christophilus 4y ago
  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.
  - yencabulator 4y ago
    I'd argue that means Clojure lets you use paradigms other than FP. FP is still FP.
gurjeet 4y ago
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.

throwamon 4y ago

Clojure

gnulinux 4y ago

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.

Beltalowda 4y ago
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.
- klodolph 4y ago
  > ...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.

ebingdom 4y ago

This is a really uninformed opinion. I'm disappointed that it's currently the top comment. You really think functional programmers don't build composite types?

deltaonenine 4y ago
It's like listening to a flat earth advocate.

charlieflowers 4y ago

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.

mbrodersen 4y ago

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.

phillipcarter 4y ago

This comment is a fine example of what it's like to have strong opinions about something you've never used.

ch4s3 4y ago

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.

yencabulator 4y ago
Those copy-on-write linked data structures, with the implied pointer chasing, have a cost. That's what the parent is talking about...
- ch4s3 4y ago
  A lot of languages, like Erlang/BEAM, use pointers under the hood and aren't necessarily copying anything.

deltaonenine 4y ago

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.

Akronymus 4y ago
> 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.
- deltaonenine 4y ago
  just pass a const reference. It's immutable anyway.
  - Akronymus 4y ago
    Unless that ref holds a mutable reference. C++ doesnt make it easy at all to have something be truly immutable.
    - deltaonenine 4y ago

xigoi 4y ago

Check out HVM, an experiment to make copying immutable data really fast: https://github.com/Kindelia/HVM https://github.com/Kindelia/HVM