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

121–130 of 217 posts

Re: Two Vexing Problems in Functional Programming

#121

Post by tomp »

nlitened wrote: post #120
tomp wrote: post #95

Earlier quoted context omitted.

Persistent data structures are very hard. It's basically impossible to cleanly combine them. E.g. if you have an immutable hashtable that contains immutable lists, and you want to modify a list - how do you know if the inner list changed or not (you don't want to be creating new hashtables if the elements don't change). They work in the small, but don't truly scale.

> 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 give you no indication whether the result of filter is the same list (i.e. element is not present) or a new list (i.e. some elements were removed).

So how do you know if you create a new hashtable or return the old one? One solution is complex, the other is wasteful.

Re: Two Vexing Problems in Functional Programming

#122

Post by mrkeen »

marcosdumay wrote: post #46
travisathougies wrote: post #22

Earlier quoted context omitted.

ST is not 'imperative'. The monadic interface can look imperative sure, but then you can also use Applicative and friends and that's back to being functional. Of course, I prefer to think of what you call 'imperative' programming as function composition where >>= is the reverse of the 'normal' composition operator. Indeed, sequential imperative commands and function composition are isomorphic.

Hum... You declare an state and go modifying it with an action after another. Looks quite imperative to me. The fact that it returns an interpreter instead of values is meaningless if it doesn't change the way you think about the program. If you personally prefers to read it as the declaration of a program that given an state modifies it step by step, you can claim it's functional. But you are alone on that, the lang…

The benefit is same-input -> same-output.

Re: Two Vexing Problems in Functional Programming

#123

Post by mrkeen »

dkarl wrote: post #77

> Indeed, Perlis’s quip gestures toward the ulti­mate tension within all program­ming languages: how to connect the gossamer realm of human ideas to the grubby reality of a computing machine. Arguably the whole point of program­ming languages is to insu­late us from those details, and allow us to express ourselves natu­rally. But the farther we drift from reality of the machine, the less effi­ciently we can use its r…

Agree with most, especially that C-style for-loops used to be the most natural thing.

I'm more pessimistic about:

> It has only been in the last 10-20 years that the majority of working software engineers have fully recognized the difficulty of managing shared mutable state

I suspect that the number of practicing programmers who don't worry about shared mutable state is growing much faster than the number who do worry. To quote Uncle Bob: "the industry as a whole will remain dominated by novices, and exist in a state of perpetual immaturity"

Re: Two Vexing Problems in Functional Programming

#124

Post by tromp »

dllthomas wrote: post #81
zodiac wrote: post #38

Earlier quoted context omitted.

Got it. I'm familiar with persistent data structures but I was more curious as to the "Haskell approach" of doing the same problem (which, I assume, doesn't use persistent data structures per se). Follow-up question: if you wanted to implement the interpreter (as in the author's article) in idiomatic Haskell, would using the State monad be one solution? (I assume that's what you meant by "compose functions that manip…

Translating naively, in Haskell I might use https://hackage.haskell.org/package/containers-0.6.5.1/docs/... , which does use sharing to reduce copying.

A simple Brankfuck interpreter in Haskell using state monads may be found at https://tromp.github.io/cl/Binary_lambda_calculus.html#Brain...

Re: Two Vexing Problems in Functional Programming

#125

Post by mrkeen »

dahfizz wrote: post #109
mirceal wrote: post #104

> To be clear, there’s nothing inher­ently supe­rior about func­tional program­ming. (Despite the fact that these self-contained func­tions are also known as pure func­tions.) It is not the way computers work at a hard­ware level. Hah. Weird way of approaching it but okay. Here's the thing: it is exactly how computers work at hardware level. If you look at an electronic circuit you and a program written in a function…

That works for simple circuits. Actual computers have oodles of state - we usually call it "main memory". Assembly is a language that can only do one thing: mutate this state.

But it's a pain to write out assembly, so we go via LLVM and SSA.

In SSA, rather than modelling your program using 16 mutable registers (imperative folk love talking about "the real world" or "real computer"), we use an infinite number of immutable registers.

Infinite registers won't fit in a computer (we only have 16), and not being able to overwrite registers must kill performance right?

Re: Two Vexing Problems in Functional Programming

#126

Post by munificent »

ChadNauseam wrote: post #82
munificent wrote: post #64

Earlier quoted context omitted.

> The solution the Haskell community finds promising is to be able to give a tag to value, like a type only not quite, that says "I promise to use this value exactly once". If you use it twice or zero times, the compiler will yell at you. I suspect the contortions required to fit your code into that affine type style will likely lead to code that is just as hard to understand and maintain as the equivalent imperative…

It's surprisingly convenient when you get used to it. A very large proportion of values are only used once, so if a function only uses a value once you can mark it as being linear in that argument and get the relevant guarantees for very little mental overhead. You can still pass any value you want to the function, the only restriction is that the function must consume the value exactly once. It's tricky to write per…

Interesting! This reminds of me of what it feels like to write const-correct code in C++.

Re: Two Vexing Problems in Functional Programming

#127

Post by kortex »

TuringTest wrote: post #61
dehrmann wrote: post #44

Earlier quoted context omitted.

> You should not approach problems in functional languages with imperative techniques. It's fitting a square peg in a round hole. This might be part of the problem with FP. Every popular CPU architecture is imperative.

> Every popular CPU architecture is imperative. That's arguable, given that every (deterministic) imperative computation can be expressed as a pure functional program. "Imperative" is more of a viewpoint that the developer is using to understand the behavior of the computer, rather than a property of the machine itself. A pure functional analysis will describe a computation on that "imperative" architecture as an inm…

Nope, unless you do some serious contortions and basically say that the universe is a lambda calculus that operates on each moment in time to produce a new view of reality.

Computers that do anything useful have all manner of I/O. Highly oversimplified in modern architecture, but you can think of I/O as a bunch of memory cells that are DMA'd by external forces. Literally the exact opposite of functional, IO registers are the epitome of global mutable state. Then you have interrupts and the CPU operates in response to these events.

The viewpoint of "computers are mutable state" is inherently better because of parsimony - it requires less degrees of indirection to explain what is happening. Just because you could shoehorn reality into a physical model, does not make it equally valid. You basically need to break it down to the Schrodinger equation level to have a purely functional model when even idealized gates are involved because propagation delay impacts things like how fast you can DMA.

Re: Two Vexing Problems in Functional Programming

#128

Post by otikik »

NyxWulf wrote: post #72
otikik wrote: post #62

Naming things, and cache invalidation :). Now seriously: while reading this, and especially the first problem, my head was shouting "immutable data structures! immutable data structures!". The author surely must have encountered IDSs during their 10-year tenure with Lisp. I'm curious about why they thought they would not fit the bill for the problems they are writing about.

Did you read the article? The entire discussion was on the tension between immutable data structures and cognitive complexity on one side, and machine performance and mutability on the other side.

First, if I sounded snarky I apologize. I assure you it was not my intention.

Secondly, I did read the article. If they are allocating a big chunk of memory and copying it over every single time they are making a change, they are not using immutable data structures. Ok, technically speaking, they might be. But they are using the worst implementation possible as a base to make conclusions from. That'd be like looking at the C language and concluding that strong types are not good, because of all the limitations C has.

Re: Two Vexing Problems in Functional Programming

#129

Post by marcosdumay »

mrkeen wrote: post #122
marcosdumay wrote: post #46

Earlier quoted context omitted.

Hum... You declare an state and go modifying it with an action after another. Looks quite imperative to me. The fact that it returns an interpreter instead of values is meaningless if it doesn't change the way you think about the program. If you personally prefers to read it as the declaration of a program that given an state modifies it step by step, you can claim it's functional. But you are alone on that, the lang…

The benefit is same-input -> same-output.

Ok, let's get specific.

Here is an STM function: orElse :: STM a -> STM a -> STM a

It returns the first argument if there isn't any synchronicity problem, or the second if some other execution line conflicts with the first.

What exactly do you mean by "same input -> same output" and how exactly does a programmer thinks about that function on this way when composing it into an STM interpreter?

Re: Two Vexing Problems in Functional Programming

#130

Post by mrkeen »

sfvisser wrote: post #20

> Functional program­ming, however, suggests we should create and destroy these struc­tures willy-nilly. It really saddens me that some people completely miss the point of what FP is about. How did this happen?

Two reasons:

1) Uncle Bob's "perpetual state of immaturity" [1]

2) Non-FP languages and "hybrid" languages do a bad enough job of FP to stop people from seeking out more. E.g.

FP lang: Doesn't have null. Uses Maybe in the rare cases its useful. The benefit is not having null. Imp lang: Keeps null. Adds Optional so now there's two ways not to have a value.

FP lang: Functions are lambdas are first class. Imp lang: Separate Function object. Lambdas can't throw checked exceptions or update variables in the method's scope.

FP lang: Understands when mutation can and cannot happen. Can share data and fuse code efficiently. Imp lang: Cannot assume underlying data doesn't change. Programmer needs to make defensive copies.

FP lang: map (+1) [1,2,3] Imp lang: Arrays.asList(1,2,3).stream().map(x -> x + 1).collect(Collectors.toList())

If I grew up with the kind of FP that made it into mainstream languages I'd probably be against it too.

[1] https://blog.cleancoder.com/uncle-bob/2014/06/20/MyLawn.html

Post reply on HN