Hacker News Reader

Comment by jimbokun | Hacker News Reader

> Is concurrency really easier in functional languages

You can use the same approaches in non-functional languages. You can only use immutable data structures, and pure functions everywhere. Then you get the same benefits of easier reasoning about concurrent execution, as you get from a functional programming language.

So the point of using an actual functional language, is that the compiler pushes you very strongly towards programming this way. It's kind of like using a language with built in garbage collection. You could implement a garbage collector in C, and use it everywhere in your program where you allocate and release memory. But having it build into the language frees you up from having to think about it very much.

View on HN

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.

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

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.

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

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

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.

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.

Rust has an affine type system, and https://docs.rs/im/14.3.0/im/ implements this https://docs.rs/im/14.3.0/im/#in-place-mutation

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.

> That works if an abstraction doesn't leak.

It seems like you're saying that abstractions are worthless unless they're perfect, which is obviously not true.

> Since we are not quite there yet, could you explain in broad terms how a large collection is sorted while maintaining performance and immutability.

What do you mean by "maintaining performance"? Relative to what? Who's asking for the sorted collection? How are they going to access it? What are the resource constraints? Give me a real-world example.

Don't get me wrong, I'm not saying that FP is the answer to everything. It's a useful tool, and part of being good at software development is knowing what tools to use and when.

No need for a real-world example or an exact definition of performance or efficiency, just make up something sensible.

How can efficient sorting be implemented with immutable data structures? Genuinly curious.

Here is a worked example of how to implement radix sort using only immutable data-parallel operations: https://futhark-lang.org/examples/radix-sort.html

There will of course be "impure" writes at the machine level, but at the language level, the abstraction doesn't leak.

> We don't write programs for machines to understand. We write programs for humans to understand.

True, but that program ends up executing on a machine. You normally want that program to execute as efficiently as possible. 'Efficiency' can be measured several ways... time to complete, resources required, financial cost.

A case in point is our company switched from using Cassandra (JVM based) to ScyllaDB (a C++ clone of Cassandra). Query latencies were the same if not faster, and we needed fewer nodes to handle the same load. All because the language used has some mechanical sympathy for the CPU it's going to run on, and no GC.

I see Scala is somewhat the defacto language used for 'big data' stuff. I have no idea why. I reckon if some bean counter translated that choice into $$$ things would change.

> True, but that program ends up executing on a machine. You normally want that program to execute as efficiently as possible. 'Efficiency' can be measured several ways... time to complete, resources required, financial cost.

No, you normally want that program to execute efficiently enough to do its required job. Abstractions are often necessarily costly, but that's ok because their value is greater than their cost. Otherwise, you'd just throw all the abstractions away and use assembler.

> Query latencies were the same if not faster, and we needed fewer nodes to handle the same load. All because the language used has some mechanical sympathy for the CPU it's going to run on.

It seems like there's a whole load of reasons why it might have been more efficient on ScyllaDB that are unrelated to what language it was written in. Maybe the software design fit your requirements better? Maybe it was just better implemented? Maybe it was easier to configure for your load? Etc. etc. Programs aren't magically "more efficient" because they're written in C.

> No, you normally want that program to execute efficiently enough to do its required job

but... the "required job" is to go as fast as possible - in two ways :

1/ You must go faster than your competitors. Else people will switch, your software will get bad reviews, etc.

2/ you must go fast enough for anything that people will throw at you. And, in many cases, people can throw arbitrarily large problems to your program, and telling them "sorry but it will take 1 hour to process your 2TB dataset" just won't cut it at all. And even when you manage to cut it, then people come at you like "now can this run on a raspberry pi?"

Take for instance image processing software, audio or multimedia software... they will never be fast enough, and there is always an use case where getting a 1% perf improvement will allow a project to make instead of break (especially when working with uncompromising artists).

> but... the "required job" is to go as fast as possible - in two ways :

This is sometimes true, but hardly ever. Most software is not image/audio processing software. Most software is not even interacted with directly by humans. Most software exists as a component as part of a larger system, the performance of which is typically determined by a small fraction of that system. In other words, most software is not on the critical path.

Even if you're on the critical path, the performance requirements could be of the form "Here's some data, I need an answer in an hour". If your current system spends 2 minutes computing and delivering the result, why spend time and money making it faster? Just because you're on the critical path for you, doesn't mean you're on the client's critical path.

This is the whole point of performance engineering - identifying which bits are important and then figuring out how to optimise those. Optimising everything to run as fast as possible is a waste of time and effort - worse, it often degrades the overall system by making previously easy-to-understand components more complex and more difficult to reason about. See the whole "Worse is better" thing.

If you're on the critical performance path, go nuts. Throw away the abstractions and take it down to the metal. If you're not? Why bother?

Perhaps the 'I need answer in a hour' is currently acceptable because that's how long people are used to waiting for the answer. If they knew that you could get that answer in 2 minute do you not think they'd ask for that instead?

Like I mentioned previously, Scala's use in Big Data is perplexing. I reckon Cloud providers are making an absolute mint from design / language inefficiencies.

> the performance requirements could be of the form "Here's some data, I need an answer in an hour"

I have never been in the case where the answer to the question "when" wasn't "as fast as physically possible".

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

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.

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.

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

As long as people are lyabble for the security exploits they produce I am all for it, hammer them hard with lawsuits.

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.

I have always been quite clear about it, it is even part of my profile.

But please let's stay focused and keep discussing specific points. When changing topic, we can make a new subthread.

Fair enough.

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?

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

Reply on news.ycombinator.com