Two Vexing Problems in Functional Programming • Hacker News Board

Re: Two Vexing Problems in Functional Programming

#61

Post by TuringTest » Fri, Apr 01, 2022, 5:21 PM UTC

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.

> 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 inmutable, monotonic sequence of all the states that the CPU goes through over time; or maybe, if you know enough PL theory, as a chain of rewritings of a program-long expression that is updated, one term at a time, when each expression is replaced by the result of a function as it consumes its input parameters.

And no viewpoint is inherently better than the other (except that the functional version can be analyzed in a natural way with mathematical tools, which is often difficult with the imperative description).

Re: Two Vexing Problems in Functional Programming

#62

Post by otikik » Fri, Apr 01, 2022, 5:22 PM UTC

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.

Re: Two Vexing Problems in Functional Programming

#63

Post by setr » Fri, Apr 01, 2022, 5:22 PM UTC

jerf wrote: post #28

ImprobableTruth wrote: post #26

Earlier quoted context omitted.

I don't really see how this relates to the article. The author specifically mentions that he also encountered these problems in Racket (a functional programming language). Anyway: >I do not understand why so many of you are so vigorously adamant that you're going to program in the intersection of functional programming languages and imperative programming languages Because it actually works pretty well? The vast majo…

I'm not talking about using it when it's helpful. I do it myself all the time. I'm talking about forcing it in when it hurts specifically . It occurs to me that I may have accidentally answered myself at the end, when I referred to the concept of union vs. intersection. When you bring in helpful angles on your current paradigm from light cast by other paradigms, that's helpful. You're expanding your working set of op…

I’m pretty sure half the purpose of the article is to resolve the ambiguity: does it hurt because the paradigm is inelegant for this problem, or because I don’t know how to make it elegant?

Just stopping anytime you struggle is precisely how you learn nothing at all

Re: Two Vexing Problems in Functional Programming

#64

Post by munificent » Fri, Apr 01, 2022, 5:23 PM UTC

ChadNauseam wrote: post #39

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…

> 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. A bit more detail. In Haskell this is implemented very elegantly with list fusion. If you write map (\x -> x+1) myli…

> 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 code (though with better static checking, which might be nice).

Re: Two Vexing Problems in Functional Programming

#65

Post by bckr » Fri, Apr 01, 2022, 5:23 PM UTC

Jtsummers wrote: post #40

exdsq wrote: post #33

Earlier quoted context omitted.

Thanks for these links, commenting to find them later.

If you select the timestamp of a comment (also when you reply to it) you can favorite it. This is much cleaner than leaving scattered "to find them later" comments around this site (in fact, I'm pretty sure it was added precisely to avoid those kinds of comments). You can also favorite submissions themselves. Favorites can be found in your profile.

you can click the timestamp and just keep the URL somewhere, like your browser's bookmarks

Re: Two Vexing Problems in Functional Programming

#66

Post by UncleMeat » Fri, Apr 01, 2022, 5:24 PM UTC

dgreensp wrote: post #21

These problems have lots of other well-known solutions. For large objects: Persistent data structures with path-copying. Batching small mutations (and using mutation internally in a way that doesn’t leak out). Using the type system somehow to distinguish cases where copying is not necessary (experimental in certain new languages). Structuring your program around a “data store” that is mutable. For the “references” pr…

Persistent data structures exist and work very well but they still remain way slower than alternatives that don't support persistence. This is especially bad if you want the data structure to be shared across multiple threads. Just iterating over a tree now requires taking and releasing oodles of locks. Add in the GC overhead and you've got a meaningful problem.

Yes, you aren't constructing an entirely new 30k byte array on each mutation. But you are still adding a lot of overhead to your program.

Re: Two Vexing Problems in Functional Programming

#67

Post by ImprobableTruth » Fri, Apr 01, 2022, 5:24 PM UTC

jerf wrote: post #28

ImprobableTruth wrote: post #26

Earlier quoted context omitted.

I don't really see how this relates to the article. The author specifically mentions that he also encountered these problems in Racket (a functional programming language). Anyway: >I do not understand why so many of you are so vigorously adamant that you're going to program in the intersection of functional programming languages and imperative programming languages Because it actually works pretty well? The vast majo…

I'm not talking about using it when it's helpful. I do it myself all the time. I'm talking about forcing it in when it hurts specifically . It occurs to me that I may have accidentally answered myself at the end, when I referred to the concept of union vs. intersection. When you bring in helpful angles on your current paradigm from light cast by other paradigms, that's helpful. You're expanding your working set of op…

Sure, it's best to work with rather than against the language, but for most languages support of functional programming is not binary, just like with OOP.

I'm pretty sure most of the complaints are generally of the "This FP thing would work well here, but the language is unfortunately not quite there" nature rather than "I will try to implement profunctor optics in C no matter the cost" square peg in round hole crazyness.

>when you force lots of maps & filters in a language that can't do fusion and function calls are kind of expensive

I think that's perfect example to show that it's really about degrees, because fusion is really a Haskell thing. Sure, it's a nice-to-have, but it's definitely not essential to functional programming.

And when people want sum types (which aren't even really FP, ALGOL had them first!), it's often because the idiomatic alternative just kind of sucks for what they're doing. Trying to "implement" sum types in a language without support is nonsensical, but complaints about lacking them are pretty understandable I think.

Re: Two Vexing Problems in Functional Programming

#68

Post by WkndTriathlete » Fri, Apr 01, 2022, 5:28 PM UTC

charcircuit wrote: post #30

skybrian wrote: post #7

This article explains the problems pretty well, but they are old problems and functional programmers have various solutions that the author seems unaware of. I'm not a Haskell programmer but I do know about monads and have heard of lenses.

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.

Re: Two Vexing Problems in Functional Programming

#69

Post by Barrin92 » Fri, Apr 01, 2022, 5:30 PM UTC

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 moment in time' and I do a gazillion state transitions that all return new things and I have never mutated anything, but not only is that bad from a performance standpoint, I never understood how that's clearer or easier, it just seems like a tortured metaphor.

Monads and other functional tools are being brought up in this thread as well but I always had the same problem. Sure, I can stuff my operations into a box, say it's the "state box" and then everything is neat but for what purpose? I still remember when I was in university I rewrote a tetris clone I had made into Haskell. It took a lot of time and weird error messages, but at the end of the day translating all my imperative or object like procedures into functional paradigms didn't make the program any easier to understand.

The places where I think functional programming is natural is for something like accounting, data processing or version control systems. Where I really do want to think of every state as its own, immutable little world, where keeping track of changes pays off, and so on. In a lot of domains it to me seems ill-suited.

Re: Two Vexing Problems in Functional Programming

#70

Post by TuringTest » Fri, Apr 01, 2022, 5:33 PM UTC

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…

travisathougies is not alone on that. Every one of us functional programmers worth their salt will consider a sequence of transformations from one state to the next as a functional program, as long as there are no side effects outside the current function that may transform state in ways that aren't declared in the types of the input and return values (which would break the referential transparency).

Functional Reactive programming (i.e. combining functions over streams of mutating objects) is essentially that, and it's a pure functional paradigm, quite popular in front-end web development (and I hear it's even creeping its way into the back-end).