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

111–120 of 217 posts

Re: Two Vexing Problems in Functional Programming

#111

Post by agumonkey »

ChadNauseam wrote: post #85
vnorilo wrote: post #49

Earlier quoted context omitted.

Not sure there's any benefit in using the state monad for an interpreter. My first thought is to model a cycle of the interpreter as a function of old state into new state. I guess the state monad could be used to thread the state dataflow through the interpreter, but it would not make the copy-big-buffer any more efficient. Code using the state monad is still pure and uses immutable data. Now if you have to use a mu…

Writing efficient interpreters in a functional style is not easy. I write interpreters in OCaml for a living and we had to switch to a mutation-heavy style for performance and memory usage reasons. It can be done though. When you think about it, any dependently typed language has to have an interpreter inside it, because you can put function applications inside a type and the typechecker will probably need to evaluat…

Isn't there a way to derive efficient/in-place interpretation from pure total recursive functions ?

reading lisp in small pieces, the author migrates interpreters from naive recursive eval to bytecode. It felt there was an underlying model to extract.

Re: Two Vexing Problems in Functional Programming

#112

Post by dahfizz »

mirceal wrote: post #107
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…

immutability is amazing. you can make assumptions about the data that you have received, it's friendly to caching, it's friendly to crashes, it's very easy to reason about. it's even more amazing when you enter a territory of multithreading/multi processor.

But the real world is mutable. The authors example of a GUI program is a good one: the user wants to change the state of the program, and expects the new state to be reflected in the GUI. You can model this in fp, but it feels like I'm standing on my head. The user wants to modify a glyph, and the program should modify that glyph. It's the simplest way of modeling what is happening.

Re: Two Vexing Problems in Functional Programming

#113

Post by voxl »

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…

Ah yes, monadic programming, liked by no one but championed by those who probably have never really had to do it.

OCaml does state without monads the way it does for a reason, because working with monads is a massive headache.

Re: Two Vexing Problems in Functional Programming

#114

Post by lostcolony »

dboreham wrote: post #42
ljloisnflwef wrote: post #19

Earlier quoted context omitted.

There's genuinely good things that came from FP that creeped into popular languages: * Algebraic data types * Pattern matching (with exhaustiveness) * Lambdas / Closures * Type inference

I don't believe it's true that algebraic data types "came from" FP. The name did, but the concept has existed since before high level languages existed. Actually before computers existed since it's in Type Theory. And before that it's in ordinary human thinking for thousands of years.

As a usable programming construct though it did.

I mean, Lambdas came from the Lambda calculus which predates FP. Type inferencing was also formulated as part of typed Lambda calculus. Pattern matching definitely came about prior to FP; SNOBOL (and its predecessor COMIT) is probably the first language that really made it 'a thing'.

Very few things FP uses came from FP; they came from underlying Math and CS, and are themselves specific formulations and implementations that fit within the context of broader well understood concepts.

Re: Two Vexing Problems in Functional Programming

#116

Post by parksy »

Tangential but what is the most successful and most complex example of a fully FP-based application where I can view the source-code today? I feel like I still don't quite grasp the essence of the conflict between FP and whatever it seems to be opposing. I also feel like I use what a lot of FP people claim as FP in my day-to-day.

I think if I can see some code beyond the old map/reduce toy examples it might click. Not wanting to be confrontational, and I know that this forum isn't here specifically to educate me personally, I just genuinely have had problems understanding what FP is "supposed" to be that any good programmer doesn't already do when possible, regardless of language or whatever.

I'm sure it will click and I'll look dumb but yeah. Isn't loose coupling and strong coherence kind of covering this already? Is it just down to doing map/reduce/filter to avoid mutating some variable and instead get a new set of results? Is mutation the charm?

I genuinely really feel I'm missing out on something important here because I have older views on programming, I've struggled to get a good explanation. Do I have to go back to school again? I'm not against that but yeah. I'm sorry if this sounds ignorant, but I kind of am.

Re: Two Vexing Problems in Functional Programming

#117

Post by gavinray »

The Koka research language has something it calls "FBIP" (Functional, but in-place)

Where you write functional/immutable methods and the compiler deterministically can convert it to in-place mutating operations for performance:

https://koka-lang.github.io/koka/doc/book.html#sec-fbip

  "With Perceus reuse analysis we can write algorithms that dynamically adapt to use in-place mutation when possible (and use copying when used persistently). Importantly, you can rely on this optimization happening, e.g. see the match patterns and pair them to same-sized constructors in each branch."

  "This style of programming leads to a new paradigm that we call FBIP: “functional but in place”. Just like tail-call optimization lets us describe loops in terms of regular function calls, reuse analysis lets us describe in-place mutating imperative algorithms in a purely functional way (and get persistence as well)."

Re: Two Vexing Problems in Functional Programming

#118

Post by nightski »

dahfizz wrote: post #106
TuringTest wrote: post #61

Earlier quoted context omitted.

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

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 referentially transparent. But this is in the semantics, not the execution model of the program.

Re: Two Vexing Problems in Functional Programming

#119

Post by mrkeen »

tomp wrote: post #95
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 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.

> how do you know if the inner list changed or not

This is a vital question that virtually every programming language overlooks.

If you are using a mainstream language, you do not know if they were modified.

If you use a language which has a type system to segregate mutable operations from immutable operations, then you know if they were modified.

> They work in the small, but don't truly scale.

Go even bigger then. Work with the kind of data that won't fit in memory. Put your data on disk - you can't insert into the middle of a 1GB+ file.

Re: Two Vexing Problems in Functional Programming

#120

Post by nlitened »

tomp wrote: post #95
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 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?

Post reply on HN