Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Functional languages should be so much better at mutation than they are

cohost.org

Post reply on HN
Print view View original

81–90 of 188 posts

Re: Functional languages should be so much better at mutation than they are

#81

Post by derdi »

senorrib wrote: post #21
derdi wrote: post #16

Earlier quoted context omitted.

> Well, no, this is straight confusion between what’s expressed by the program and what’s compiled. The idiomatic code in Ocaml will end up generating machine code which is as performant than using mutable array. This cannot be true in general. There are machine code patterns for which arrays are faster than linked lists. The OCaml compiler, great as it is, won't turn linked list source code into array machine code.…

Well, it doesn't make the substance wrong. This paragraph rightly summarizes it: "The fact that most programming languages don’t give enough semantic information for their compiler to do a good job doesn’t mean it necessary has to be so. Functional programmers just trust that their compiler will properly optimize their code."

The substance of the statements I quoted was wrong. As I wrote elsewhere, I do agree with the broad statement that the combination of functional and imperative features in OCaml works just fine. But if the semantic information you give to the OCaml compiler is "linked list", it will use a linked list rather than a data structure that might be better for the task at hand.

Re: Functional languages should be so much better at mutation than they are

#82

Post by tome »

fire_lake wrote: post #79
ufo wrote: post #38

Earlier quoted context omitted.

One thing that many people miss is that Haskell's monadic style is a direct consequence of lazy evaluation. It all started because they thought lazyness was nice, and wanted to make a language that brought that front and center. But then they found out that they had to come up with a new way to do side-effects, because traditional side-effects don't work when the order of evaluation is unpredictable.

I think this is historically wrong. Monads didn’t land until later in Haskell, no?

I don't think GP is contradicting that.

Re: Functional languages should be so much better at mutation than they are

#83

Post by tome »

astrange wrote: post #60
runeblaze wrote: post #7

Earlier quoted context omitted.

I second the conclusion as (a brutal conclusion, but still) to stop using Haskell. Haskell allows imperative-like code but the ergonomics for day-to-day big-tech engineering is far from good. The state monad or lens are excellent tools to re-create a controlled imperative language in a vacuum, and is frankly impressive how much mutation we can conjure up from purity, but the error messages or the required understandi…

Haskell almost seems like it was intentionally designed to perform poorly on real computers, primarily because of space leaks and secondarily because the non-strict evaluation gets compiled into a lot of function pointer jumps, which branch predictors hate. I think it's funny that they make you write linked list code as a metaphor for generators, but it seems like it should be the other way round. (Also, it has excep…

> (Also, it has exceptions which are a bad language feature, and typed throws which are a worse one.)

Can you elaborate? You can't stop people simulating exceptions with sum types, and if you have exceptions, why wouldn't you want them to be typed?

Re: Functional languages should be so much better at mutation than they are

#84

Post by tome »

gloria_mundi wrote: post #31
tome wrote: post #27

I'm not convinced about the dismissal of option 2. I agree ST is clunky but not for the reasons given. It's clunky because it's impossible to mix with other effects. What if I want ST and exceptions, for example, and I want the presence of both to be tracked in the type signature? ST can't do that. But my effect system, Bluefin, can. In fact it can mix not only state references and exceptions, but arbitrary other eff…

Isn't mixing of effects exactly what monad transformers are for? AFAICT you want an `ExceptT e ST` for some exception type `e`. https://hackage.haskell.org/package/mtl-2.3.1/docs/Control-M...

Oh, I meant it's impossible to mix ST with actual exceptions as implemented in the RTS, rather than with ExceptT which simulates exceptions in pure code (like StateT simulates mutable state in pure code).

You're right, through a stroke of luck it's possible to use `ExceptT e ST r` and either handle the exception part first, to get `ST r`, or handle the ST part first to get `Either e r`, so in that sense you can "mix" exceptions and ST. That doesn't work for all transformers though. If you have `Stream (Of a) ST r` then you must consume the stream first. You can't run the ST part an get a pure stream `Stream (Of a) Identity r`. So in that sense ST can't be mixed with other effects. Bluefin does allow you to do that, though.

Re: Functional languages should be so much better at mutation than they are

#85

Post by ShroudedNight »

devbent wrote: post #77
tsimionescu wrote: post #76

Earlier quoted context omitted.

Almost all GCs used in practice today only scan the set of live objects, which in normal operation is much smaller than the entire heap. They also allow much more efficient allocation and de-allocation. The problems with GC are threefold, and why you might not want it in a systems language: 1. GC requires more memory than strictly necessary to be efficient (usually about 1.5x - 2x the amount you absolutely need). You…

People often forget that the runtime of free is not trivially calculatable! I've worked on tiny embedded systems (.net micro framework) where for a given usage pattern the GC was perfectly predictable, as it should be.

'Costly' doesn't seem to require that O(k) be non-constant:

http://www.gii.upv.es/tlsf/

Re: Functional languages should be so much better at mutation than they are

#86

Post by tome »

throw156754228 wrote: post #39
codebje wrote: post #35

Earlier quoted context omitted.

Yes, but transformers have a few drawbacks: the order of stacking alters behaviour, and you need to write n^2 instances for n transformers. Compare ExceptT e (StateT m a) and StateT (ExceptT e m a): if you just want your computation to have state and exceptions the difference shouldn’t matter.

Also their other well known problem: you lose the program state if an exception is thrown in the monad above.

Yeah, that's basically the same problem as `StateT s (ExceptT e m)` but for `StateT s m` where `m` throws exceptions.

Re: Functional languages should be so much better at mutation than they are

#87

Post by tome »

mrkeen wrote: post #33
tome wrote: post #27

I'm not convinced about the dismissal of option 2. I agree ST is clunky but not for the reasons given. It's clunky because it's impossible to mix with other effects. What if I want ST and exceptions, for example, and I want the presence of both to be tracked in the type signature? ST can't do that. But my effect system, Bluefin, can. In fact it can mix not only state references and exceptions, but arbitrary other eff…

Nice, first I'm hearing of bluefin - I'll be sure to check it out. As an aside, I watched an Alexis King stream (which I can't now find) in which she did a deep dive into effect systems and said something along the lines of: algebraic effect systems should not change their behaviour depending on nesting order e.g. Either > vs State >. Does bluefin have a particular philosophy about how to approach this?

I agree with Alexis. Bluefin approaches this by not actually having a nesting order. The effects that can be performed as specified as function arguments, so they can be freely reordered without changing behaviour. effectful, which was one of the inspirations for Bluefin, is similar but uses constraints instead of function arguments, which are even more free to reorder.

> I'll be sure to check it out

Great! If you have any questions or thoughts then feel free to file an issue on the repo (https://github.com/tomjaguarpaw/bluefin/issues/new).

Re: Functional languages should be so much better at mutation than they are

#88

Post by tome »

tsimionescu wrote: post #76
devit wrote: post #56

Earlier quoted context omitted.

You can, but it turns out that, as one may intuitively expect, a GC is never needed unless implementing a VM for a GC-based language or an API that required GC like fd passing on unix domain sockets, and those generally want an ad-hoc GC instead tailored to whatever you are implementing. Since it's not needed and it's massively worse than reference counting (assuming you only change reference counts when essential an…

Almost all GCs used in practice today only scan the set of live objects, which in normal operation is much smaller than the entire heap. They also allow much more efficient allocation and de-allocation. The problems with GC are threefold, and why you might not want it in a systems language: 1. GC requires more memory than strictly necessary to be efficient (usually about 1.5x - 2x the amount you absolutely need). You…

> You're basically trading runtime efficiency for memory.

What do you mean? Aren't GCs both less efficient at run time and use more memory?

Re: Functional languages should be so much better at mutation than they are

#89

Post by kaba0 »

devit wrote: post #56
Buttons840 wrote: post #45

Earlier quoted context omitted.

Aside: Could a Rust library provide an Rc interface but use a more sophisticated GC algorithm underneath?

You can, but it turns out that, as one may intuitively expect, a GC is never needed unless implementing a VM for a GC-based language or an API that required GC like fd passing on unix domain sockets, and those generally want an ad-hoc GC instead tailored to whatever you are implementing. Since it's not needed and it's massively worse than reference counting (assuming you only change reference counts when essential an…

> Since it's not needed and it's massively worse than reference counting

Lol, what? Maybe don’t go asserting stuff you clearly know little about. Reference counting is a fine tradeoff for manual memory-managed languages, but it is absolutely smoked out of the water by a tracing GC on most counts. It’s almost like JVM, V8, etc engineers know a thing about the topic and don’t have RC for a good reason.

Tracing GC doesn’t burden the mutator threads with additional work, almost everything can be done in parallel, resulting in vastly better throughput. Imagine dropping the last reference to a huge graph, one can actually observe it when exiting a c++ program, it might hang for a few seconds before returning control to you, as all the destructors are recursively called, serially, on the program thread, literally pointer by pointer jumping across the heap, the very thing you are so afraid of. And I didn’t even get to the atomic part, bumping a number up or down with synchronization between CPUs is literally the slowest operation you can do on a modern machine. Tracing GCs elegantly avoid all these problems at the price of some memory overhead. None of these GC algorithms (yes, RC is a GC) is a silver bullet, but let’s not joke ourselves.

Re: Functional languages should be so much better at mutation than they are

#90

Post by kaba0 »

tome wrote: post #88
tsimionescu wrote: post #76

Earlier quoted context omitted.

Almost all GCs used in practice today only scan the set of live objects, which in normal operation is much smaller than the entire heap. They also allow much more efficient allocation and de-allocation. The problems with GC are threefold, and why you might not want it in a systems language: 1. GC requires more memory than strictly necessary to be efficient (usually about 1.5x - 2x the amount you absolutely need). You…

> You're basically trading runtime efficiency for memory. What do you mean? Aren't GCs both less efficient at run time and use more memory?

They are massively faster (as in, has better throughput) than ref counting. See my previous comment for more details.
Post reply on HN