[catlifeonmars]

Isn’t it possible (at least in theory) to make mutability an implementation detail of the compiler/runtime? Rust’s borrow checker approaches this, but the abstraction leaky or nonexistent. Additionally, many high performance computing applications (e.g. Tensorflow) abstract away expensive mutable operations, so at least in theory, it should be possible to isolate mutability to small segments of code where mutability is opt-in.

[retrac]

Yes, Haskell as a pure functional language does this too. A naive copy-by-value handling of lists will usually end up in the same order of magnitude for performance as mutate-in-place linked lists in C. The compiler can track those immutable values and just mutate them in place, when it can guarantee that's a safe operation. The vast majority of the time, you can get away with just copying a pointer or renaming, not the whole variable.

The caveat is that, in my experience, it's a fair bit harder to reason about performance, as the execution model is even more abstracted away from the hardware than even something like the C model is (which is no longer a good fit either, in this era of speculative execution and multi-level caches.)

[msla]

> The caveat is that, in my experience, it's a fair bit harder to reason about performance, as the execution model is even more abstracted away from the hardware than even something like the C model is (which is no longer a good fit either, in this era of speculative execution and multi-level caches.)

One solution is to have a tool developed and distributed along with the compiler (so it can never fall out of sync with the compiler, that's why) annotate the code with notes about performance.

[heavenlyblue]

I think if performance is part of the requirements of your code, then performance must be a part of your type signature.

For example, a tail-recursive function needs to have it’s type as tail-recursive.

[openfuture]

This is where linear types and in general quantitative type theory comes into play. Also eagerness / laziness annotations.

Tail recursion is not necessary to annotate imo, but I guess the compiler/linter could maybe complain if it finds recursion it can't do a tail call optimisation for. These kinds of warnings are similar to mutable languages warning about things that are probably bad but sometimes necessary.

[heavenlyblue]

It’s neccessary to annotate tail recursion because you are making it clear to the compiler that your initial assumption about the performance of this function is that it will not explode the stack.

The reason it must be made explicit is because when somebody else comes later on to change that function they may miss the fact that it doesn’t explode only because it’s tail-recursive.

You could of course document the requirement - but why document if you can make it a compiler option? “I don’t want this to compile unless I get the behaviour I expect from it”.

Also as far as I am aware C-style functions can not be tail-recursive because they can not clean up the stack after themselves, thus you can’t support tail-recursion across FFI.

[nyanpasu64]

Rust's im[1] and rpds[2] crates are refcounted pointers to immutable data structures, but support mutable operations on &mut instances. When an instance is cloned, it merely creates another pointer. When an instance is modified, it uses Arc::make_mut() to only clone each tree node if it has other users. This approach has runtime overhead, but makes nested updates (foo[0][0].attr = 1) as simple as mutable structures.

This somewhat resembles immer.js (uses a proxy around an immutable structure which records updates). Contrast this approach to Clojure transients (whose children don't magically become transient), and whatever Haskell does (https://news.ycombinator.com/item?id=24740384).

[1]: https://docs.rs/im/

[2]: https://docs.rs/rpds/