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

61–70 of 188 posts

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

#61

Post by dullcrisp »

gloria_mundi wrote: post #54
dullcrisp wrote: post #49

Earlier quoted context omitted.

I might have this wrong but I think if you want state and exceptions you probably want StateT (ExceptT e m a). The alternative would be to have state or exceptions, i.e. when you have an exception you no longer have state (which might be a legitimate type in some cases).

Remember that transformers are "inside-out", i.e. `StateT (ExceptT e m) a` is isomorphic to `m (Except e (State a))`. If we want to keep state if an exception occurs, you need a `m (State (Except e a))` which is `ExceptT e (StateT m) a`.

Yeah I could never keep this straight

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

#62

Post by narski »

nine_k wrote: post #55
narski wrote: post #29

I recently ran into this issue when trying to memoize a simple numerical sequence in Hoon (yes, that Hoon. I know, I know...). Let's use the fibonacci sequence as an example. Let's write it the classic, elegant way: f(n) = f(n-1) + f(n-2). Gorgeous. It's the sum of the two previous. With the caveat that f(n=0|1) = n. In Python: # fib for basic b's def fib(n): ## Base case if n == 0 or n == 1: return n return fib(n-1)…

The standard way to expel stated mutable state us to push it into function parameters and returned values. With Fibonacci numbers, you cab just compute two if them outright: def fib_(n: int) -> tuple[int, int]: if n == 0: return (1, 1) prev, this = fib_(n - 1) return (this, this + prev) def fib(n): return fib_(n)[0] Now there is no mutable state that survives between function calls, the performance is linear. With tr…

>The standard way to expel stated mutable state us to push it into function parameters and returned values.

This is precisely what I did in my Hoon solution :) However, I wasn't aware that this approach is the standard way, and I'm glad to have learned that! Thanks

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

#63

Post by throwaway81523 »

Ben Lippmeier's Disciplined Disciple Compiler (DDC), for his language later called Discus, was interesting. It was/is an experimental language that managed mutation through an effect typing system. In the intro to his thesis he talks about it some.

Discus language: http://discus-lang.org/

Thesis: https://benl.ouroborus.net/papers/2010-impure/lippmeier-impu...

The thesis is the more interesting of those two links IMHO. The intro is chapter 1 that starts at page 17 of the pdf. It has one of the better critiques of Haskell that I've seen, and explains why uncontrolled mutation is not the answer. Reference types ala ML aren't the answer either, in his view.

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

#64

Post by ChadNauseam »

armchairhacker wrote: post #32
ChadNauseam wrote: post #18

I enjoyed this article. As someone who has written too much haskell and ocaml, and now writes mostly Rust, I am biased but I think this problem is mostly solved by rust. (The author mentions rust in option 3, but I think underappreaciates it.) The author mentions linear types. This is a bit of a pet peeve of mine because, while very useful, linear types are not the concept that many people think they are and they are…

> IF a function expects a value with a linear type, can you pass an a value with an exponential type to it? The answer is that you can. Try this in linear haskell if you don't believe me. > Those familiar with rust will notice that this is not how rust works. If a function takes T, and you have &T, you just cannot call that function. (Ignore Clone for now.) I think this is wrong. An exponential type in Rust is a type…

> You can ignore `Clone`, but ignoring `Copy` destroys the premise, because without it Rust has no exponential types at all.

it somewhat strains the analogy because rust is implemented in a very elegant way (where references can be used multiple times because they implement Copy), but the analogy to exponentials in rust would be references. Just imagine clone and copy aren’t a thing, and that references have a special case that allow them to be used multiple times while owned values can be used at most once. The thing to note is that if you have an owned value, you can pass a reference to it to as many functions as you want (so long as those functions expect references). But if you have a reference, you can’t pass it to a function that expects an owned value unless the type provides you a way to make a copy.

You can imagine starting with this and then building up to rust in a nice way. You first implement passing an owned value as a move. Then first add types that can be used multiple times because they are still valid after a move. (the Copy trait.) And then you make references Copy since they meet that criteria.

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

#65

Post by Leftium »

> ...functional programming is mostly about avoiding mutation at all costs

Slightly different perspective from Grokking Simplicity[1]: functional programming is not about avoiding mutation because "mutation is bad." In fact, mutation is usually the desired result, but care must be taken because mutation depends on when and how many times it's called.

So good FP isn't about avoiding impure functions; instead it's about giving extra care to them. After all, the purpose of all software is to cause some type of mutation/effect (flip pixels on a screen, save bits to storage, send email, etc). Impure functions like these depend on the time they are called, so they are the most difficult to get right.

So Grokking Simplicity would probably say this:

1. Avoid pre-mature optimization. The overhead from FP is usually not significant, given the speed of today's computers. Also performance gains unlocked by FP may counter any performance losses.

2. If optimization via mutation is required, push it as far outside and as late as possible, keeping the "core" functionally pure and immutable.

This is similar to Functional Core, Imperative Shell[2]; and perhaps similar to options 1 or 2 from the article.

[1]: https://www.manning.com/books/grokking-simplicity

[2]: https://hw.leftium.com/#/item/18043058

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

#66

Post by nikhilsimha »

pornel wrote: post #8

> Rust's shared XOR mutable references […] makes linearity nearly useless or inevitably creates a parallel, incomplete universe of functions that also work on linear values. Yup. Rust can't abstract over mutability. For owned values, it defaults to exclusive ownership, and needs explicit Rc and clone() to share them. For references, in practice it requires making separate `foo()` and `foo_mut()` functions for each ty…

i personally like nim’s approach to memory management - implicitly refcounted, but exposes clean manual memory management when needed

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

#67

Post by initplus »

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…

It seems that way because it kind of is. The early days of functional research were equally focused on designing alternative computer architectures that were more suited to functional paradigms.

Now that hardware angle has not been very successful on the whole, and we are left with languages that end up feeling a bit out of place on the hardware we have today.

Another thing to note is that there is a lot of untapped potential in fb compilers. It’s suffering from underinvestment.

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

#68

Post by o11c »

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…

For GC-based inner languages it's mandatory to mention that inter-language cycles are nasty. Life is much easier in a world of explicit ownership!

I curate a list of what kinds of ownership people actually want: https://gist.github.com/o11c/dee52f11428b3d70914c4ed5652d43f...

It's been 6 years since I first posted it publicly, and neither I nor anyone giving suggestions has ever actually found a use for GC.

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

#69

Post by plorkyeran »

burntcaramel wrote: post #58
plorkyeran wrote: post #52

Earlier quoted context omitted.

In Swift you occasionally have to introduce a temporary local variable to avoid accidentally quadratic behavior, but I've never seen it require anything complicated or hard to explain.

Curious about an example of this in Swift? Is it a variable holding a collection like an Array?

A really simple example:

    class Foo {
        var foo = [Int]()
        var bar: [Int] {
            get {
                foo
            }
            set {
                foo = newValue
            }
        }
    }
    let obj = Foo()
Calling `obj.foo.append(i)` in a loop takes linear time, while `obj.bar.append(1)` is quadratic time. `obj.foo.append()` does a borrow operation resulting in there never being more than one reference at a time, while `obj.bar.append()` does a get followed by a set, meaning that there's always two references to the array and every append does a copy on write. `let bar = obj.bar; for i = 0..Usually of course your computed properties actually do something so this difference feels less surprising. Swift does offer the undocumented `_modify` property accessor to let computed operations do borrows, but making it an official feature is waiting for noncopyable types to be finalized.

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

#70

Post by zarzavat »

o11c wrote: post #68
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…

For GC-based inner languages it's mandatory to mention that inter-language cycles are nasty. Life is much easier in a world of explicit ownership! I curate a list of what kinds of ownership people actually want : https://gist.github.com/o11c/dee52f11428b3d70914c4ed5652d43f... It's been 6 years since I first posted it publicly, and neither I nor anyone giving suggestions has ever actually found a use for GC.

IME the utility of GC is not for structs but for closures. It’s very easy to cause cycles when freely using closures in non-GC languages.
Post reply on HN