Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Two Vexing Problems in Functional Programming

matthewbutterick.com

Post reply on HN
Print view View original

201–210 of 217 posts

Re: Two Vexing Problems in Functional Programming

#201

Post by TuringTest »

whimsicalism wrote: post #198
TuringTest wrote: post #170

Earlier quoted context omitted.

How do you define "imperative" in a way that precludes a functional description of your definition? I'd say that if you're able to do that, you'd have found a contradiction in Turing completeness and win you a Turing award. Also, this: https://news.ycombinator.com/item?id=30883863

Just because every program in C is also expressable in Haskell does not mean that C is Haskell or that C is a functional programming language. The same is true of CPUs, which at their base level execute instructions line-by-line to move and load things in and out of stateful registers as well as doing simple mathematics. Not going to keep arguing, as I can see from your other comments that you are going to try to hol…

> It does not imply that all distinctions between the semantics of languages and the structure of hardware thus are collapsed. It means that you can write an equivalent program using different semantics or different hardware.

No, it means that every computable program or device can be described through functional semantics, and therefore that very same program running on that same hardware can be described mathematically with them (not an 'equivalent' program, but the same program with the same runtime behaviour, just described in low level with a different format).

That's a core principle of computer science that predates computers themselves, and people arguing about the benefits of the imperative style tend to be unaware of this fact, making their arguments look weak.

Re: Two Vexing Problems in Functional Programming

#202

Post by AtNightWeCode »

TuringTest wrote: post #91
AtNightWeCode wrote: post #41

Have not got the time to read this but. Let me guess. Another programmer in a functional programming language realizing that the state is all over the place and gets copied around but still is so importantly immutable.

That, and the comments in this thread reminding us that you have powerful tools in pure functional languages to represent state and handle those pesky side effects causing the bugs that plague imperative programmers' nightmares.

Nothing prevents you from doing pure functions in other langs. Fact is that it is standard today. The imperative programming model and the core problem with functional programming is much the same. The only difference is that you have a copy of the state in functional programming. The “real” state is still all over the place. That is why any sane business avoids functional langs except for areas were functional langs shine.

Re: Two Vexing Problems in Functional Programming

#203

Post by mirceal »

dahfizz wrote: post #152
mirceal wrote: post #144

Earlier quoted context omitted.

that’s the point. more complex circuits are made from simple circuits. principle still applies. if you think about it, most problems with writing code stem from state management.

> more complex circuits are made from simple circuits. principle still applies. And humans are made out of carbon, but you are never going to understand human emotion by studying carbon atoms really hard. Assembly is the interface to the hardware. Assembly is imperitive. The abstraction that assembly exposes is a machine with global, mutable state. That's the way the hardware works.

> And humans are made out of carbon, but you are never going to understand human emotion by studying carbon atoms really hard.

here is the problem with that line of reasoning: human emotion is difficult to define, highly subjective. it does not mean anything unless you are human and try to understand the emotions.

also, you probably need to focus more on K and Na ions and electrons if you are going down the emotional rabbit hole. Carbon is interesting, but apart from providing the skeleton for various things like dna, proteins etc i think it’s not where you’d start

Re: Two Vexing Problems in Functional Programming

#204

Post by harperlee »

closeparen wrote: post #168
mumblemumble wrote: post #150

Earlier quoted context omitted.

But Clojure also has a habit of implementing core functionality that needs to be fast in imperative Java. The thing about copy-on-write is that it's only a good solution when writes are infrequent. My sense is that Clojure largely deals with this by simply not targeting business domains where frequent writes to mutable data structures are particularly necessary. Which hints at my own opinion on how to deal with this…

All programming paradigms are at some level implemented in terms of assembly.

Yes, but paradigms can be different enough that an intelligent compiler fails to find the same optimal assembly for two solutions for the same problem. Thus the paradigm in which you express the solution matters. Otherwise we would just need to express the problem, and a trivial solution, and the compiler would work the rest (the idea behind declarative programming!)

Re: Two Vexing Problems in Functional Programming

#205

Post by kkfx »

The real issue, IMVHO, about functional programming is that's more suited for a development model modern society do not follow.

That's not much an FP issue but an actual IT issue, since modern development for modern business reasons produce monsters and solutions waiting for problems. That's also hard to teach and probably the reason functional programming is seen as "superior but not for the real world by many.

Re: Two Vexing Problems in Functional Programming

#206

Post by TuringTest »

AtNightWeCode wrote: post #202
TuringTest wrote: post #91

Earlier quoted context omitted.

That, and the comments in this thread reminding us that you have powerful tools in pure functional languages to represent state and handle those pesky side effects causing the bugs that plague imperative programmers' nightmares.

Nothing prevents you from doing pure functions in other langs. Fact is that it is standard today. The imperative programming model and the core problem with functional programming is much the same. The only difference is that you have a copy of the state in functional programming. The “real” state is still all over the place. That is why any sane business avoids functional langs except for areas were functional langs…

> The only difference is that you have a copy of the state in functional programming. The “real” state is still all over the place.

Not necessarily. You can have a reference to state, with no need to copy it; and a single structure containing all of the 'real' program state in one place, neatly referenced from a central point; destroying (i.e. liberating) the old values no longer being used. Same as you would do in an imperative garbage-collected program.

Imperative programs have state all over the place because they sweep it under the carpet of the runtime engine instead of fully embracing it and referencing it at all times, but doing this doesn't make state any more 'real'.

> That is why any sane business avoids functional langs except for areas were functional langs shine.

Yeah, probably. The problem is that sane business should also be avoiding imperative programs except for areas where they shine (namely complex world simulations and low-level access to embedded devices and OS modules), and they aren't doing because of industry inertia.

The mutable cell is one of the most advanced, complex and dangerous features of programming languages, and yet we introduce them to students on their very first lessons on their first week, without even a warning, making them think that using them all over the place is just how things should be done. Many junior developers will never learn to properly handle state other than 'don't use global variables'. This is not the proper way to run an engineering industry.

Thankfully, the industry is finally catching up to functional ways of handling state where it makes more sense, specially in networked asynchronous computation (the web and the cloud), where imperative code for asynchronous coordination is a nightmare; it's one of the areas where functional and agent-based state management shines, seeing updates in the form of promises and streams, not as mutable cells that may be changed at any time by anyone with access to them

Re: Two Vexing Problems in Functional Programming

#207

Post by zrkrlc »

throwaway81523 wrote: post #184
jayd16 wrote: post #133

Earlier quoted context omitted.

That's fine from a philosophical sense, but doesn't it make consecutive reads extremely heavy? You're throwing away the efficiency of in place updates at the language level, no?

> That's fine from a philosophical sense, but doesn't it make consecutive reads extremely heavy? You're throwing away the efficiency of in place updates at the language level, no? You use special data structures to deal with that. There's a great book about them, "Purely Functional Data Structures", by Jeff Okasaki. You generally don't get O(1) update like for traditional arrays, but you can usually get O(log n), lik…

Minor nitpick, but it's actually *Chris Okasaki

Re: Two Vexing Problems in Functional Programming

#208

Post by charcircuit »

WkndTriathlete wrote: post #68
charcircuit wrote: post #30

Earlier quoted context omitted.

Lenses don't help. They just make copying and updating large data structures cleaner to write. They don't solve the performance problem of copying everything.

Incorrect. Optics implementations can ensure updating a node in a large balanced tree is O(log n) instead of O(n), trivially, and I'm sure there are sufficiently clever collections with optics that would enable much better performance than the trivial optimizations I can think of. The same holds true for large structure updates.

Not all data structures are a large balanced tree and a O(1) update is going to be faster than O(log n) updates. There is still going to be a significant performance hit from having to recreate a whole node instead of just updating a single value. While yes you can say large data structures are like a big node of a tree, having to copy all of the different records from the old one to a new one is going to be considerably slower than just modifying a single record.

It does help, but it's still going to be significantly slower than just modifying a single record in a data structure. It is a still a problem that will be slowing down your program.

Re: Two Vexing Problems in Functional Programming

#209

Post by fulafel »

tomp wrote: post #121
nlitened wrote: post #120

Earlier quoted context omitted.

> you want to modify a list - how do you know if the inner list changed or not You know for sure that inner list did _not_ change, because it is immutable. Someone else might have a reference to an updated hashtable with an updated inner list, but the one you hold will never change—isn’t that the whole idea of immutable data structures?

No, I mean "update" in the persistent sense - create a new list, with some (or none) elements changed/added/removed. e.g. say you have a method remove_all_in_values that takes an int x and a hashmap of list of int, and returns a new hashmap of list of int, with x removed from each element of the hashmap. Obviously you'd use something like List.filter for the inner operation, but most functional programming languages…

In FP I think composability and interchangeability of these higher order functions help, in case the supplied filter did not work like you want: You could write your own filter function variant that guarantees to return the same list if the predicate function returned true for each element.
Post reply on HN