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

131–140 of 217 posts

Re: Two Vexing Problems in Functional Programming

#131

Post by galaxyLogic »

valcron1000 wrote: post #92
galaxyLogic wrote: post #50

Earlier quoted context omitted.

That is a very good question. The discussion often circles around pro- and against FP. Proponents of "pure FP" seem to suggest that it is the best solution for everything always. Is it? If not it would be nice to find discussion about when it is and when not and why? What is Haskell NOT the best solution for?

In my experience Haskell is a bad solution when you need fine control over memory usage and control flow. For those cases you should probably use something like C, C++ or Rust. For everything else I think is a viable option. The hard part is understanding how you should model your problem. I found that you could classify problems into two big groups: pipelines like compilers or web services where you get an input, do…

It took me some time to understand how Haskell performs its "magic" but now I think I do. Anybody please correct me if I'm still getting it wrong...

Haskell main program in essence runs a big loop until it decides the program should exit. In Haskell syntax the loop is coded as a call to a tail-recursive function, which on a real hardware of course needs to be translated to do iteration. At the end of each loop it sets the new calculated value of the new state to be used during the next loop.

Using tail-recursion optimization it looks like our whole program executes a single top-level function-call of a recursive function, that is how you code it in Haskell.

This is great but somehow it feels like a trick. It is actually still doing iteration and state mutation internally while running. You could program that in an imperative language writing a top-level loop and iterating over it and modifying the statefull variables at the end of each loop.

And what happens if you cannot write your program as tail-recursive function? What if the problem domain requires you to use general recursion, which can not be optimized away like tail-recursion can?

Re: Two Vexing Problems in Functional Programming

#132

Post by kortex »

Barrin92 wrote: post #69

Personally I never really understood the benefit of thinking in functional terms about things that are conceptually more naturally thought of as persistent objects. For example when the author picks "parents" or "children" or in general maybe any entity of any kind, I don't understand what functional thinking gets me. Sure instead of manipulating mutable objects I can think of every entity being 'one thing' at 'one m…

You are absolutely right that there are domains that are just inherently more stateful and not easily leant to a functional style. What I've found so far on my functional journey is that it can be handy to lean into this aspect of "punishing" certain problems. It kind of forces you to think more explicitly about mutation and when you actually want to invoke it. Thus you end up writing a lot in terms of transactions and hypotheticals - "if I get a POST /users request, what SQL queries do I emit?"

You have execution engines (a web framework and sql engine) that encap a block of pure function. There's no side effects (save maybe logging) whatsover inside your mini-program.

FP patterns like monads let you compose blocks of execution so you can have bigger mini-programs that are more ergonomic to write.

SQL query builders are (I think) a kind of Monad. You can compose selections, filters, groups, etc without ever executing, building up a big "what if" into a transaction. No side effects until you execute, it's pure data in data out. Which means for example you can write true unit tests without mutating a "real" db by composing transactions together.

FP falls apart when you have to reason about "nuts and bolts" of actual computation models, IO, network, time, RNGs, DMA, gpus, large data arrays. FP acolytes say "just let the computer/compiler do it" eg write in FP and compile to optimized imperative machine code, but someone still has to write drivers at the end of the day.

Re: Two Vexing Problems in Functional Programming

#133

Post by jayd16 »

js8 wrote: post #2

Not sure if the author will read this, but there is a simple answer to both problems. In functional programming, you typically do not manipulate state directly, instead you compose functions that manipulate that state, into more complex functions. (In Haskell, for example, this composition is often done through monads.) Eventually, you get a function that represents the whole program. This is somewhat dual to imperat…

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?

Re: Two Vexing Problems in Functional Programming

#134

Post by imtringued »

dehrmann wrote: post #44
nightski wrote: post #14

You should not approach problems in functional languages with imperative techniques. It's fitting a square peg in a round hole. The approaches & data structures aren't always the same. In my experience with FP you start with more of a top down approach in contrast to the bottom up approach discussed in the blog post. There are many good resources on this. I've referenced a few below. Of course there are many more. [1…

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

No, that's the easy part. Computation with FP is very easy. The problems start the moment you have to do persistence and communication. Those aren't part of any pure functional paradigm.

Re: Two Vexing Problems in Functional Programming

#135

Post by dahfizz »

nightski wrote: post #118
dahfizz wrote: post #106

Earlier quoted context omitted.

You're definitely stretching here. I could just as easily argue that "all of main memory" is the output of any function. Therefore every function is a pure function, and C is a function language. Using your definition, the concept of functional programming is meaningless. Main memory is state. Registers and cache are state. The entire purpose of the CPU is to mutate state.

No, I don't believe you could argue C is purely functional by framing memory as the output of the function because C doesn't treat it as such. Memory in C can be changed even if it is not listed in the inputs or outputs of the function. He's not really stretching the definition, that's just the lens through which FP looks at the world. Of course there is state. FP doesn't prohibit state, it just makes it explicit and…

> Memory in C can be changed even if it is not listed in the inputs or outputs of the function.

If we are going to nitpick syntax, nothing about `mov eax ebx` lists main memory as output. In fact, mov doesn't even have an 'output'.

If you want to model mov as a function with the implicit output of "all of main memory", then you can do the same with any arbitrary C function. If you can't make that leap for C, then you can't make that leap for assembly.

Re: Two Vexing Problems in Functional Programming

#136

Post by dahfizz »

mrkeen wrote: post #125
dahfizz wrote: post #109

Earlier quoted context omitted.

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?

I'm not sure what your point is. Yes, it is possible to build "functional" layers of abstraction on top of real hardware. The hardware itself is not "functional", that's why you need layers of abstraction.

Re: Two Vexing Problems in Functional Programming

#137

Post by mrkeen »

marcosdumay wrote: post #129
mrkeen wrote: post #122

Earlier quoted context omitted.

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?

I was referring to the ST monad which bts and travisathougies were talking about, not STM.

I mean that when you run ST code twice with the same input, you will get the same output. E.g., if I write (runST f) + (runST f), that's the same as 2 * (runST f), etc.

As for thinking, it means I don't use step-through debuggers ever, because I don't need the whole program to be in a certain state to watch what happens. I just grab the function, grab the input, and run it in isolation.

Re: Two Vexing Problems in Functional Programming

#138

Post by closeparen »

jayd16 wrote: post #133
js8 wrote: post #2

Not sure if the author will read this, but there is a simple answer to both problems. In functional programming, you typically do not manipulate state directly, instead you compose functions that manipulate that state, into more complex functions. (In Haskell, for example, this composition is often done through monads.) Eventually, you get a function that represents the whole program. This is somewhat dual to imperat…

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?

This is why Clojure’s big thing is to also, at the language level, emphasize copy-on-write data structures.

Re: Two Vexing Problems in Functional Programming

#139

Post by travisathougies »

marcosdumay wrote: post #129
mrkeen wrote: post #122

Earlier quoted context omitted.

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?

I think you should give the guy above the benefit of the doubt and restrict yourself to ST. IO and STM are different beasts, and still they're not imperative. The issue with IO and STM is global state. Mutation of global state can be done imperatively, as many imperative languages do. It can also be done functionally using monads to hide the affine types in a nice wrapper class in the absence of proper affine types or using proper affine type systems. Haskell choose the former. Other languages, like clean, choose the latter.

Same input -> same output is a nice property of referential integrity, which is a common thing we have in functional languages, but it is actually not due to the functional nature. Imperative languages can trivially be made to have this property by disallowing mutation of variables not in the immediate scope and restrict IO side effects (and maybe a few other straightforwards restrictions depending on the language in question).

With that out of the way. Same input -> same output holds for `orElse :: STM a -> STM a -> STM a`. However, you really have to expand out the types.

Here is the definition of STM (from https://hackage.haskell.org/package/base-4.15.0.0/docs/GHC-C...):

> newtype STM = STM (State# RealWorld -> (# State# RealWorld, a #))

So, `orElse` should behave the same as a function with this type:

> (State# RealWorld -> (# State# RealWorld, a #)) -> (State# RealWorld -> (# State# RealWorld, a #)) -> State# RealWorld -> (# State# RealWorld, a #)

Now, the definition of 'same input -> same output' is clear. Assuming the global state (State# RealWorld) is the same, then the output state will be the same. Actually, this is not a property of all languages, as most languages allow arbitrary side effects in any code. Haskell does not. This is the key property that makes STM easy in Haskell and difficult in other languages. Note that the 'State# RealWorld' is always handled linearly, so there is no possible way the same 'value' could be passed in twice. Again, hiding this behind a monad enforces that this value is handled linearly, since Haskell doesn't have linear types (or at least didn't when STM, ST, and IO were written).

Re: Two Vexing Problems in Functional Programming

#140

Post by chriswarbo »

dehrmann wrote: post #44
nightski wrote: post #14

You should not approach problems in functional languages with imperative techniques. It's fitting a square peg in a round hole. The approaches & data structures aren't always the same. In my experience with FP you start with more of a top down approach in contrast to the bottom up approach discussed in the blog post. There are many good resources on this. I've referenced a few below. Of course there are many more. [1…

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

I find this unconvincing. Electronic circuits are well described as a Cartesian Closed Category; and hence by lambda calculus (i.e. we can give semantics to functional programs by interpreting them as descriptions of circuits; as opposed to the "usual" interpretations of x86_64 machine code, or symbolic values, etc.)

Imperative systems are "fitting a square peg in a round hole" by introducing hacks like 'clock signals', 'pipeline flushes', etc.

Post reply on HN