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

161–170 of 217 posts

Re: Two Vexing Problems in Functional Programming

#161

Post by Sinidir »

karmakaze wrote: post #83
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…

I was thinking along the same lines. Is an "atom" in Clojure like STM where the structure/reference is changed in a highly controlled manner?

atoms are containers that require no coordination so its a simple Compare and swap. There are Refs that require transactions and change of multiple Refs is coordinated in these transactions. WIth that Clojure has an implementation of Software Transaction Memory.

Re: Two Vexing Problems in Functional Programming

#162

Post by valcron1000 »

galaxyLogic wrote: post #131
valcron1000 wrote: post #92

Earlier quoted context omitted.

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

What you are trying to describe is not Haskell the language but an implementation, and right now the de facto implementation is GHC. I really can't talk about how GHC works internally, but when it comes to the language you need to think your program as a value, just like `5` or `[1,2,3]` or `{ "name": "susan" }`. That is, effects are values, you compose those effects, and, your program being some kind of effect, is also a value. That's the reason behind `main :: IO ()`: your program is an `IO value`.

When it comes to "executing" your program, a runtime (like GHC's runtime) takes your program which is a value and actually performs the requested actions, dealing with mutation, loops, jumps, etc. This is a hack just as much as any other language dealing with variables instead of the stack, heap or registries directly.

In case you're interested, this idea of using some kind of interpreter which loops over your program and performs mutations and side effects is very popular in Scala: libraries like Cats and ZIO do this, allowing you to effectively get Haskell's IO. As far as I know, tail-recursion is not really needed for this, but when implemented on the runtime it allows the end user to write loops using recursion without blowing up the stack.

Re: Two Vexing Problems in Functional Programming

#163

Post by saeranv »

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?

Yes, although I suppose even in languages where this isn't mitigated (i.e. Clojure example below), you can offset that inefficiency with the parallelism enabled by functional programming.

Re: Two Vexing Problems in Functional Programming

#166

Post by [deleted] »

Sinidir wrote: post #155
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…

Creation of new versions of datastructures are done in log32(N) time in clojure. The performance even for frequent updates is fine.

[deleted]

Re: Two Vexing Problems in Functional Programming

#167

Post by TuringTest »

kortex wrote: post #127
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…

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…

> Just because you could shoehorn reality into a physical model, does not make it equally valid.

Hey, physicists do it all the time. Having mathematical representations of how things work in the real world often turn out to give you complex devices that you wouldn't get by intuition alone. Thanks to doing it, we have Special Relativity and Schrodinger equations, that bring you advantages as GPS and insanely-high-speed networks.

There's nothing wrong with modelling interrupts and mutable state as static mathematical entities a.k.a. functions; and if you think it is, you don't know enough about functional programming - in fact, doing it allows for advanced tactics like automatic verification and very high scale generation of electronic devices.

Those less degrees of indirection may make it simple to build some kinds of programs; but they also introduce complexity in modelling the possible states of the system when you allow for arbitrary, unchecked side effects. So no, that representation is not inherently better - only most suited for some tasks than others; but the converse is also true for functional models of computation. If you think it is always better, it's because you're not taking all possible scenarios and utilities into account.

(Besides, as I already said elsewhere, "computers are mutable state" is not incompatible with functional representation; as mutable state can be represented with it). It seems that you're confusing mutable, wich is a property of computational devices, with 'imperative' which is a style of writing source code and defining relations between statements in your written program.

> Literally the exact opposite of functional, IO registers are the epitome of global mutable state.

Yup, you definitively don't know what functional programming is if you think you can't have global mutable state in it. In fact, every top-level Haskell program is defined as a global mutable IO monad...

Re: Two Vexing Problems in Functional Programming

#168

Post by closeparen »

mumblemumble wrote: post #150
closeparen wrote: post #138

Earlier quoted context omitted.

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

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.

Re: Two Vexing Problems in Functional Programming

#169

Post by TuringTest »

dahfizz wrote: post #158
nightski wrote: post #153

Earlier quoted context omitted.

It's not syntax, it is semantics. There is a lot to programming language theory/design and this is all formalized. C does not have the semantics you are describing in the formal specifications (C99, etc..). Could they have developed a version of C with these semantics? Possibly. Rust was a step in that direction with it's borrow checker.

Yes, and my whole point is that assembly does not have those semantics either. The computer is an imperative machine.

The computer is not an imperative machine. It's a physical machine that you describe with an imperative representation in your mind. Can you tell the difference, or are you unaware of the map-territory distinction going on?

Functional programmers are simply choosing to use a different style of map, but we both represent the same reality.

Re: Two Vexing Problems in Functional Programming

#170

Post by TuringTest »

whimsicalism wrote: post #99
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…

Not really arguable, IMO. Just because both lambda calculus and assembly are Turing complete does not mean that CPU architecture isn't clearly imperative.

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

Post reply on HN