5 ms·

I don't get the immutable data structures thing though. If I have a vector of 1 billion numbers and I need to sort it it'll be unfeasible to make a copy every t

I don't get the immutable data structures thing though. If I have a vector of 1 billion numbers and I need to sort it it'll be unfeasible to make a copy every time I swap elements. RAM isn't infinite either. So, deep down in the guts of the language's libraries there must be mutable operations. Which kind of defeats the whole point. I don't get point of functional programming. Machines don't work that way.

tmountain 7y ago
The implementations of immutable data structures in most concurrency aware functional languages are smarter than that. Take Clojure as an example: "All of the Clojure collections are immutable and persistent. In particular, the Clojure collections support efficient creation of 'modified' versions, by utilizing structural sharing, and make all of their performance bound guarantees for persistent use." https://hypirion.com/musings/understanding-persistent-vector-pt-1 https://hypirion.com/musings/understanding-persistent-vector...
moring 7y ago
IMHO the advantages of functional programming is often looked for in examples that are too small for them to exist. There is no advantage in sorting a billion numbers the functional way. There is an advantage to gain, though, when the unsorted numbers are used for other purposes besides sorting. Then, functional programming demands that the output of sorting is written to a new 1-billion array instead of "in place", so other clients can consume the same array in parallel without being disturbed by the sorting. > So, deep down in the guts of the language's libraries there must be mutable operations. Which kind of defeats the whole point. It doesn't defeat the point if the abstraction doesn't leak. If a pure functional language offers sorting as a pure primitive, then language-wise it doesn't matter that it actually mutates memory internally. The problem with "mostly" pure functional languages is that the abstraction leaks enough to make it useless.
- clarry 7y ago
  > The problem with "mostly" pure functional languages is that the abstraction leaks enough to make it useless. Does this make e.g. erlang useless? Processes have mutable dictionaries and you can perform I/O anywhere in your functions..
growse 7y ago
>I don't get point of functional programming. Machines don't work that way. FP is useful because it provides an abstracted model that is pretty easy to reason about. It doesn't matter how it gets implemented, that's the point of the abstraction. We don't write programs for machines to understand. We write programs for humans to understand.
- sorokod 7y ago
  That works if an abstraction doesn't leak. Since we are not quite there yet, could you explain in broad terms how a large collection is sorted while maintaining performance and immutability.
  - throwaway17_17 7y ago
    The simplest way, but which essentially dodged the question, is to utilize a language with uniqueness types. Where the data structure may only exist in a single place and there can be no aliasing. Then any operation on the data structure occurs and can be done ‘in place’ returning the new unique data structure. This is similar (but not identical) to linear and affine type systems, of which Idris is the only language I know of that actually implements such a type system. Also, along the same lines, it is certainly possible to craft types in some FP languages which allow for this same logic to be captured, mostly via some monad construct.
    - steveklabnik 7y ago
      Rust has an affine type system, and https://docs.rs/im/14.3.0/im/ https://docs.rs/im/14.3.0/im/ implements this https://docs.rs/im/14.3.0/im/#in-place-mutation https://docs.rs/im/14.3.0/im/#in-place-mutation
      - throwaway17_17 7y ago
        This reply is late, so if you don’t see it or care I don’t blame you. To start, I am aware of Rust and left it out of the above comment purposefully. While Rust does indeed make many ‘functional programming’ idioms available and, some would say, is basically an impure, eager functional language, I don’t tend to view Rust as a language featuring persistent, immutable data structures. I certainly don’t think that is a negative characterization, just how I see things. I find that one of the defining features of the functional programming ‘persistent’ data structure is the structural sharing that is all too frequent in most of the mainline FP languages (Haskell, ML, Clojure, etc.). Rudy’s focus on low level/systems level programming is much more likely to use standard imperative data structures without the sharing and deep pointer chasing style seemingly inherent in FP implementations. I have had a few spirited web-discussions with people about the claim that Rust has an affine type system. I don’t think that stance is accurate, from a type theoretic stance. I subscribe to the theoretical standpoint that Rust has a standard non-substructural type systems with constraints placed on types that meet a mutability predicate. I think that those constraints are better described as a uniqueness constraint per instance of a type. But the sequent calculus presentations for Rust (especially concerning mutable data) would look very similar and act very similar as well. So really it’s much ado about nothing, just fun to talk about. Sorry for the wall of text, and rambling about type theory. Stay safe.
chapium 7y ago
Not defending fp but if memory is a limitation why not create a sortable index and leave the data alone?
ImprobableTruth 7y ago
The key idea is that there are functional data structures that only require you to copy a small part and reuse a lot of the old. For example, if you have a binary tree and you want to swap out the root value, you create a new root node that simply uses the existing children. >So, deep down in the guts of the language's libraries there must be mutable operations. Which kind of defeats the whole point. Why does it defeat the point? If you can guarantee that the mutability doesn't leak (there are ways to do this), it behaves just like a pure implementation.
pjmlp 7y ago
No machine works like the high level languages, including C. Many believe the portable Assembler story and aren't aware that ISO C is defined in terms of an abstract machine. The abstraction level that functional programming allows for, all the way back to Lisp, is to take advantage of the underlying hardware without being forced to hand code lowlevel details. Something written in ML like language could be running on 70's, 80's, NUMA architectures, GPGPU, whatever, without changing one single line of code. Naturally we are not speaking about the same runtime implementation. Whereas a language like C, requires a bunch of dialects to actually make use of the low level details, only exposed via Assembly and not part of ISO C.
- jstimpfle 7y ago
  Yeah but those "low level details" are not portable between computer architectures, so why not stop whining. And you can actually USE these low level details if you really want, with very low friction (if you are willing to lock down to specific architectures). Are you STILL whining? C level (or Pascal if you're masochistic) is still a very nice abstraction, and for a lot of people it's everything they care about 99% of the time, to get all the control they need, while simultaneously ensuring they're not wasting any time fighting pointless language features that are mutually incompatible. In the end everybody's using whatever they like. https://twitter.com/fabynou/status/1242517783092400129 https://twitter.com/fabynou/status/1242517783092400129
  - pjmlp 7y ago
    As long as people are lyabble for the security exploits they produce I am all for it, hammer them hard with lawsuits.
    - jstimpfle 7y ago
      Sorry, but that's a rough shifting of goalposts. The statement that I argued against clearly was "C is not low level". You might not have noticed that you shifted, because you have an agenda.
unlinked_dll 7y ago
Mutability is an access pattern and not an underlying data layout. In fact, some structures that lend themselves to immutability represent the hardware better. Take your vector of a billion elements. It probably is too big for L1/L2 cache. Is it actually a billion things next to each other in memory? Not at all. If you used something like a radix balanced balanced tree to represent your vector, you get amortized O(1) access and mutation can be implemented using copy on write at individual leaves of the tree. And your abstraction is much friendlier with the cache, because it reflects how the hardware works much better than a simple vector. In practice, immutable data structures can be much more performant at scale than pretty much anything. They're not just convenient for soundness. Trivial data structures like vectors are really only useful when you're talking hundreds to the low thousands of elements, at which point who cares how much memory they take up?
kyllo 7y ago
Functional programming builds immutable semantics as an abstraction on top of mutable semantics. This abstraction layer includes internal optimizations that elide unnecessary copying, such as persistent data structures and "list fusion." When you're processing a list, the compiler can optimize away intermediate sublists. If you "copy" a list or sublist in Haskell, you don't actually get a copy, you get a new pointer to the same physical data, which is safe because it's immutable and garbage collected. A key premise of functional programming is that the constraints of immutable semantics free the compiler up to do all sorts of performance optimizations, and the compiler can apply those optimizations much faster than a human developer can. Also, when you really need a vector that you can mutate in place, you can still do that. Haskell has a mutable vector type. It's not the default idiom, but if you needed to sort a billion numbers in place, this is what you would use. Note all the function names prefixed with "unsafe": https://hackage.haskell.org/package/vector-0.12.1.2/docs/Data-Vector-Mutable.html https://hackage.haskell.org/package/vector-0.12.1.2/docs/Dat...

tmountain 7y ago

The implementations of immutable data structures in most concurrency aware functional languages are smarter than that. Take Clojure as an example: "All of the Clojure collections are immutable and persistent. In particular, the Clojure collections support efficient creation of 'modified' versions, by utilizing structural sharing, and make all of their performance bound guarantees for persistent use." https://hypirion.com/musings/understanding-persistent-vector-pt-1 https://hypirion.com/musings/understanding-persistent-vector...

moring 7y ago

IMHO the advantages of functional programming is often looked for in examples that are too small for them to exist. There is no advantage in sorting a billion numbers the functional way. There is an advantage to gain, though, when the unsorted numbers are used for other purposes besides sorting. Then, functional programming demands that the output of sorting is written to a new 1-billion array instead of "in place", so other clients can consume the same array in parallel without being disturbed by the sorting. > So, deep down in the guts of the language's libraries there must be mutable operations. Which kind of defeats the whole point. It doesn't defeat the point if the abstraction doesn't leak. If a pure functional language offers sorting as a pure primitive, then language-wise it doesn't matter that it actually mutates memory internally. The problem with "mostly" pure functional languages is that the abstraction leaks enough to make it useless.

clarry 7y ago
> The problem with "mostly" pure functional languages is that the abstraction leaks enough to make it useless. Does this make e.g. erlang useless? Processes have mutable dictionaries and you can perform I/O anywhere in your functions..

growse 7y ago

>I don't get point of functional programming. Machines don't work that way. FP is useful because it provides an abstracted model that is pretty easy to reason about. It doesn't matter how it gets implemented, that's the point of the abstraction. We don't write programs for machines to understand. We write programs for humans to understand.

sorokod 7y ago
That works if an abstraction doesn't leak. Since we are not quite there yet, could you explain in broad terms how a large collection is sorted while maintaining performance and immutability.
- throwaway17_17 7y ago
  The simplest way, but which essentially dodged the question, is to utilize a language with uniqueness types. Where the data structure may only exist in a single place and there can be no aliasing. Then any operation on the data structure occurs and can be done ‘in place’ returning the new unique data structure. This is similar (but not identical) to linear and affine type systems, of which Idris is the only language I know of that actually implements such a type system. Also, along the same lines, it is certainly possible to craft types in some FP languages which allow for this same logic to be captured, mostly via some monad construct.
  - steveklabnik 7y ago
    Rust has an affine type system, and https://docs.rs/im/14.3.0/im/ https://docs.rs/im/14.3.0/im/ implements this https://docs.rs/im/14.3.0/im/#in-place-mutation https://docs.rs/im/14.3.0/im/#in-place-mutation
    - throwaway17_17 7y ago
      This reply is late, so if you don’t see it or care I don’t blame you. To start, I am aware of Rust and left it out of the above comment purposefully. While Rust does indeed make many ‘functional programming’ idioms available and, some would say, is basically an impure, eager functional language, I don’t tend to view Rust as a language featuring persistent, immutable data structures. I certainly don’t think that is a negative characterization, just how I see things. I find that one of the defining features of the functional programming ‘persistent’ data structure is the structural sharing that is all too frequent in most of the mainline FP languages (Haskell, ML, Clojure, etc.). Rudy’s focus on low level/systems level programming is much more likely to use standard imperative data structures without the sharing and deep pointer chasing style seemingly inherent in FP implementations. I have had a few spirited web-discussions with people about the claim that Rust has an affine type system. I don’t think that stance is accurate, from a type theoretic stance. I subscribe to the theoretical standpoint that Rust has a standard non-substructural type systems with constraints placed on types that meet a mutability predicate. I think that those constraints are better described as a uniqueness constraint per instance of a type. But the sequent calculus presentations for Rust (especially concerning mutable data) would look very similar and act very similar as well. So really it’s much ado about nothing, just fun to talk about. Sorry for the wall of text, and rambling about type theory. Stay safe.

chapium 7y ago

Not defending fp but if memory is a limitation why not create a sortable index and leave the data alone?

ImprobableTruth 7y ago

The key idea is that there are functional data structures that only require you to copy a small part and reuse a lot of the old. For example, if you have a binary tree and you want to swap out the root value, you create a new root node that simply uses the existing children. >So, deep down in the guts of the language's libraries there must be mutable operations. Which kind of defeats the whole point. Why does it defeat the point? If you can guarantee that the mutability doesn't leak (there are ways to do this), it behaves just like a pure implementation.

pjmlp 7y ago

No machine works like the high level languages, including C. Many believe the portable Assembler story and aren't aware that ISO C is defined in terms of an abstract machine. The abstraction level that functional programming allows for, all the way back to Lisp, is to take advantage of the underlying hardware without being forced to hand code lowlevel details. Something written in ML like language could be running on 70's, 80's, NUMA architectures, GPGPU, whatever, without changing one single line of code. Naturally we are not speaking about the same runtime implementation. Whereas a language like C, requires a bunch of dialects to actually make use of the low level details, only exposed via Assembly and not part of ISO C.

jstimpfle 7y ago
Yeah but those "low level details" are not portable between computer architectures, so why not stop whining. And you can actually USE these low level details if you really want, with very low friction (if you are willing to lock down to specific architectures). Are you STILL whining? C level (or Pascal if you're masochistic) is still a very nice abstraction, and for a lot of people it's everything they care about 99% of the time, to get all the control they need, while simultaneously ensuring they're not wasting any time fighting pointless language features that are mutually incompatible. In the end everybody's using whatever they like. https://twitter.com/fabynou/status/1242517783092400129 https://twitter.com/fabynou/status/1242517783092400129
- pjmlp 7y ago
  As long as people are lyabble for the security exploits they produce I am all for it, hammer them hard with lawsuits.
  - jstimpfle 7y ago
    Sorry, but that's a rough shifting of goalposts. The statement that I argued against clearly was "C is not low level". You might not have noticed that you shifted, because you have an agenda.

unlinked_dll 7y ago

Mutability is an access pattern and not an underlying data layout. In fact, some structures that lend themselves to immutability represent the hardware better. Take your vector of a billion elements. It probably is too big for L1/L2 cache. Is it actually a billion things next to each other in memory? Not at all. If you used something like a radix balanced balanced tree to represent your vector, you get amortized O(1) access and mutation can be implemented using copy on write at individual leaves of the tree. And your abstraction is much friendlier with the cache, because it reflects how the hardware works much better than a simple vector. In practice, immutable data structures can be much more performant at scale than pretty much anything. They're not just convenient for soundness. Trivial data structures like vectors are really only useful when you're talking hundreds to the low thousands of elements, at which point who cares how much memory they take up?

kyllo 7y ago

Functional programming builds immutable semantics as an abstraction on top of mutable semantics. This abstraction layer includes internal optimizations that elide unnecessary copying, such as persistent data structures and "list fusion." When you're processing a list, the compiler can optimize away intermediate sublists. If you "copy" a list or sublist in Haskell, you don't actually get a copy, you get a new pointer to the same physical data, which is safe because it's immutable and garbage collected. A key premise of functional programming is that the constraints of immutable semantics free the compiler up to do all sorts of performance optimizations, and the compiler can apply those optimizations much faster than a human developer can. Also, when you really need a vector that you can mutate in place, you can still do that. Haskell has a mutable vector type. It's not the default idiom, but if you needed to sort a billion numbers in place, this is what you would use. Note all the function names prefixed with "unsafe": https://hackage.haskell.org/package/vector-0.12.1.2/docs/Data-Vector-Mutable.html https://hackage.haskell.org/package/vector-0.12.1.2/docs/Dat...