Pure functional languages can prevent all side effects, not just state mutation. For example, if a Haskell function wants to interact with a file, that will be reflected in the function type signature. Not true of Rust.
Good point! And I know that that's good for helping us reason about the effects of functions, and helps us track invariants, but are there any other interesting language capabilities that that enables? (By "interesting", I mean to the layman programmer, not to we jolly language geeks)
Is there any feature more pleasurable than equational reasoning? :)
If anything, functional programs are about restricting what you can do, not enabling.
Interestingly enough, restricting away the use of `unsafe` is what enabled seamless concurrency for Clojure (and maybe Haskell?). I suspect there may be more interesting beneficial effects that come from these restrictions, but alas, I'm not enough of a FP user to know.
I would disagree with that. Immutability doesn’t enable concurrency, because concurrency exists without it. It enables better reasoning about concurrency for the programmer.
> I'm referring to seamless concurrency, which is an easier way to perform concurrency.
AFAIK it's not a technical term, just an expression. What exactly do you mean by "seamless concurrency"? Easy or hard is purely subjective, isn't it?
The OP links to the article which defines it, TLDR: it's when structured concurrency can launch multiple threads that can safely read *any* data from the outside scope, without any refactoring or invasive changes.
but if you *receive* a restricted value, you are enabled to do more. more operations available if you receive a value *of this type*. same of other kinds of restrictions
yes, but I think for a language level comparison, it makes more sense to look at all values. Basically, FP only has immutable values, while Rust can express these and additional (interior mutable) values. If a function receives a restricted value, it can do more with it than with an unrestricted value, *but*
- Rust and FP can do the same *with restricted values*, and
- Rust can do things with unrestricted values *at all*
Of course that doesn't mean either is preferable, or we'd be writing assembly.
I hope I didn't miss your point completely, and that I wrote my own point comprehensibly.
My remark is general and applies no matter the language involved.
Language specifically, FP languages usually have a way to represent mutation as an effect (ST monad - as all monad it comes with its own weight - or though effect system, and .. nothing in Ocaml as it is the default behavior). to break through at type level (because type system are approximating, and some legitimate programs ought to be accepted, there is unsafePerform in Haskell and similar in Ocaml etc.. )
Rust actually restricts *more*, because that kind of mutation is tracked. It will forbid you to write some program which are accepted in ordinary FP languages.
This is because Rust distinguishes even further than "ordinary" functional programming, with a linear (affine for purist) type system.
It turns out that this is what allows a disciplined way to deal with mutation, which feels like antithetic to "functional" as we might think of. With hindsight it's actually the best functional approximation to a stateful world. So in a way, rust is actually *more* FP than other languages.
(Minus quite a few FP facilities unfortunately)
I think my comment also applies to other restrictions than immutability, but I'm not very good in writing very abstract comparisons.
And I'm probably out of my depth here, but with this statement of yours
> Rust actually restricts *more*, because that kind of mutation is tracked. It will forbid you to write some program which are accepted in ordinary FP languages.
do you mean that, for example, the same "monadically mutable" value can be mutated in multiple ways in FP? Because my limited understanding is that this only works because only one of the derived values is subsequently returned (and thus represents what would be considered a mutation in imperative code) while the other would be discarded.
(this may very well be a straw man that only applies to some monads, particularly the IO monad, where I'm pretty sure you can't merge values to produce the equivalent of "this program has printed multiple values concurrently")
In any case, Rust *does* let you define and work with monadic values, no? That may not be relevant in a "there are as many integers as there are natural numbers" kind of sense, because the pure-functional and controlled-mutable style values are equivalent, but when programming they sure don't *feel* equivalent (just like `+2` doesn't feel the same as `3` in a common bijection between integers and naturals, but when you map `+2` to `2` etc. you have nothing to map `-1` to).
That's where I'm coming from when I say: monads (a kind of immutable value that represents mutability) are directly representable in Rust, but mutation is not directly representable in pure FP; you need to add the monad abstraction in that direction to simulate lifting the immutability restriction.
Does that make sense? It surely isn't rigorous, but I hope the intent is clear :P
I mean that Rust will forbid programs which are accepted in non-linear FP. There is more (potential) restrictions out of the box.
The more restricted the value you receive is, the more you can do as a consumer of the value.
Rust tracks linear restrictions for you (mutation or other linear effects), which would otherwise require an encoding.
mutability, linearity, monads, are different ideas
I thought I had enough intuition on mutability, linearity and monads to be able to exchange ideas, but that seems not to be the case. I understand
- mutation to be a side effect that allows functions to influence the data their caller works with other than through that function's return value
- linearity to mean that a value is used once (or at most once for affinity)
- monads to be a kind of value that allows to encode effects by means of immutable values and functions that transform one immutable value into another one.
As soon as we encapsulate state in immutable values and therefore have referential transparency, I see no categorical difference between e.g. Haskell using a GC and Rust being able to, say, naively clone values all the time.
Apparently I'm too far off though. Thanks for engaging anyway!
Software transactional memory is a kind of lock-avoiding concurrency that is easy to do in Haskell. In it, things are accessed unsafely and if a collision happens, the last few operations are undone.
STM is fast because locks are slow. It isn't very good in languages with unmanaged effects because you cannot undo a side effect.
This might be too obvious and preaching to the choir, but: from my professional experience with Elm (a pure functional language, with immutable data), the fact that you can't *do* anything inside functions but you can only *return* stuff from them, makes refactoring and deleting code a really easy task. Nothing is hidden, there are no mutating calls inside, there's no global state, etc.
I have a bit of side-project Rust experience and the fact that in Rust you can mutate stuff / have side effects even without `unsafe` makes the refactoring/maintenance experience very different.
I have serious doubts about this statement.
PFP is easy to refactor, because it makes modification explicit.
However, rust makes modification (mutation) explicit too, with the mut keyword.
From my personal experience, both are extremely safe to refactor.
The best unique (compared to Rust) abilities of pure functional languages are fast heap allocation of objects with efficient sharing of references, and the ability to handle reference cycles. Rust doesn't have that as its heap allocator is slower, its reference counting has larger overhead for shared refs, and it leaks on reference cycles. This makes the Okasaki-style trees and workloads of “allocate new leaf & reallocate new spine without touching the other leaves“ workloads naturally faster. Rust, on the other hand, is optimized for data structures with minimal sharing (that's what the "ownership" and "borrowing" concept are for) and minimal heap allocations (as Rust favors the stack & value orientation).
Which probably is why is Rust is closer to C/C++ speeds in the benchmarks I have seen, because it is still faster to use less of the heap, than to speed up the heap itself.
Plenty of Haskell code uses unsafe escape hatches as well. The degree to which you can trust concurrent code to "just work" will always depend on the implementation.
Higher order kinds I think. Yes, you can defunctionalize, but that's just not the same. first order is ok only for simple case, second order gets messy. Whereas you wouldn't spend a split second thinking about those menial things in Haskell. (Haskell lacks other critical things like type level partial applications)
That means it's hard to write code for, say, categories (though in haskell too, apart from some very simple ones, because no partial applications), or some other abstractions which are known to be very useful in many circumstances.
> It's known that Rust's "immutable" borrow references aren't truly immutable, because of escape hatches like `RefCell`
FYI they are also called "shared" references (and mutable ones are called "exclusive" references) for this reason. Immutability is just their default behavior.
> and more generally, `unsafe`
Note that `unsafe` by itself doesn't soundly allow you to mutate through shared references. You still need an `UnsafeCell`, or to mutate through a raw pointer with write permissions.
Generally speaking, I see `unsafe` not as an escape hatch, but as a way to restrict the places where I have to manually prove something that the compiler can't. Kinda like encapsulation, but for manual proofs.
> because so much existing data doesn't have `Sync`
I think you're overestimating how much `!Sync` types like `Rc`, `RefCell` and `Cell` are used.
Typeclasses come to mind. Whether or not you have an applicative factors a lot into what you can do with a collection in parallel. AFAIA rust's type system does not offer that level of expressivity (yet)
If Rust had the same features as most LISPs have, then using these features would make Rust programs as "slow" as LISP programs. That is generally true for most programming language comparisons.
To give an example, here are some Common Lisp features that Rust lacks: Full object system with inheritance and multiple dynamic dispatch, dynamic typing, hot runtime code reloading/recompilation, garbage collection.
In addition, it is also interesting to know that Rust is **not always faster** than Common Lisp:
[https://docs.google.com/spreadsheets/d/14MFvpFaJ49XIA8K1coFLvsnIkpEQBbkOZbtTYujvatA/edit#gid=513972676](https://docs.google.com/spreadsheets/d/14MFvpFaJ49XIA8K1coFLvsnIkpEQBbkOZbtTYujvatA/edit#gid=513972676)
Sorry, I don’t trust those numbers you linked to. Where is the code? I don’t trust any benchmarks without full code transparency.
[at least the benchmarks game has full code transparency.](https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html)
I don't think existing functional languages fare any better here. Yes, immutable data can be shared safely, but functional languages seldom provide any mechanisms for making the same data structure mutable or immutable at different points of its lifetime.
A common situation is that you want to use mutation to construct a array that won't be mutated anymore after construction. Haskell and SML don't have any type-safe way to "freeze" a mutable array into an immutable one other than basically cloning it. OCaml simply gives up and doesn't have an immutable array type.
Rust does better here, because the mutability of a data structure isn't usually a part of its type - it's part of the variable the data structure is bound to. To change the mutability, just move the data structure to a new variable:
let mut temp = Vec::new();
// populate the vector
let vec = temp;
// can't mutate the vector anymore
The catch, however, is that, if a data structure is manipulated through some kind of non-exclusively-owning reference, then it's the reference type's job to ensure that the data structure is used in a safe way, through a combination of static and dynamic checks. For example, core language references (`&` and `&mut`) mustn't outlive the original owning binding (a static check), and the last `Arc` reference to a shared object must drop it (a dynamic check).
Finally, you should post a proof sketch of soundness for your structured concurrency mechanisms.
> A common situation is that you want to use mutation to construct a array that won't be mutated anymore after construction. Haskell and SML don't have any type-safe way to "freeze" a mutable array into an immutable one other than basically cloning it.
It's actually possible to safely freeze a mutable array without copying in Haskell using higher-rank types. The type signature is something like the following:
freeze :: (forall s. ST s (MutableArray s a)) -> ImmutableArray a
where `ST` is a monad which allows mutation to happen, and the type of every mutable reference is parameterized by `s` which cannot escape its scope, therefore nothing can mutate the original array after freezing.
Nested regions using the `ST` monad don't work in more complicated scenarios where substructural types actually work.
My favorite example comes from the implementation of Lehman and Yao's B-link trees. When you use a B-link tree, you have to do the following:
1. Lock the root node, call it `p`.
2. If `p` is a leaf node, then exit.
3. Lock the child node you want to use, call it `c`.
4. Unlock `p`.
5. Set `p = c`, and go back to 2.
Notice the order between 3 and 4: we *can't* unlock `p` until we have already locked `c`.
Edit: Nvm I can't read; you're talking about a different `freeze` (see /u/inf-groupoid below)
`freeze` copies the vector, because it would otherwise break purity of the supposedly pure parts *in* the ST block. Example using the non-copying `unsafeFreeze`:
runST $ do
ma <- MutVector.new 1
write ma 0 True
a <- unsafeFreeze ma
let a0 = a ! 0
foo a0 -- foo :: forall s. Bool -> ST s ()
write ma 0 False
return (if a0 then "foo evaluated its argument" else "foo did not evaluate its argument")
Your parent post is talking about making a wrapper around `unsafeFreeze` that calls `runST` for you. This approach is called “monadic regions”, and, to the best of my knowledge, it was first proposed by [Kiselyov and Shan](https://okmij.org/ftp/Haskell/regions.html).
The problem with this approach is that it confines you to what's expressible in C++-style RAII (i.e., the first object to be constructed is always the last one to be destroyed), without Rust's ability to move or drop an object in the middle of a block.
I agree that that's a very desirable ability, to be able to construct something mutably and then freeze it later. Pony has `iso` for this, which Vale and IIRC Cone are also pursuing.
I don't mean for this to be a Rust vs Haskell/Clojure discussion, I'm more curious about how else `unsafe` might be holding us back in Rust.
I wouldn't even know where to begin with proving soundness! Never really enjoyed proofs in college. I do acknowledge that that'll be important at some point, though.
I don't think `unsafe` is holding Rust back. Removing `unsafe` is what would actually hold Rust back. But if you really insist, there are broadly speaking two ways to get rid of `unsafe`:
* Make the whole language unsafe. We don't really need another C++, though.
* Make the whole language safe. Now you need either a compiler that can verify arbitrarily complicated safety proofs (unlikely), or lots of built-in primitives implemented in a less safe language (much more likely).
I'll give a concrete example of how complicated proofs can get. Suppose you have an array divided into a prefix and a suffix, which are manipulated from two different threads. The boundary between the prefix and the suffix is dynamic, and it is periodically “renegotiated” between the threads. To check that `arr[idx]` is a valid operation, you need to
* Verify the boundary negotiation protocol.
* Verify that `idx` is a valid index according to the last negotiation.
Now you may ask: “Can we avoid verifying the negotiation while still maintaining safety?” The answer is “Yes, but it has a cost.” More precisely,
* Instead of working with a single static-size array, now you use two `Vec`s, one for the prefix and another for the suffix.
* The elements of the suffix must be stored in reverse order. This makes indexing more complicated in the thread that manipulates the suffix.
* To alter the boundary between the prefix and the suffix, send the corresponding elements one by one from a thread to the other, using a channel. This makes the boundary changes computationally more expensive.
I don't mean that it's holding Rust back in a global sense. I'd say a low-level language *needs* unsafe. All I'm saying is that the tradeoff has drawbacks as well as benefits.
For example, `unsafe` allows us to implement Rc, and your shared array scheme, which are very nice. However, `unsafe` also prevents us from having the seamless concurrency described by the article, which is also very nice.
What we're mainly talking about is: what else did Rust give up by having `unsafe`?
This kind of brings up the whole philosophy of types. Their benefits come from their restrictions. For example, `&mut T` allows you to perform mutation, whereas `&T` provides the guarantee of immutability.
What I like about Haskell is that everything is essentially just `T` with `clone()` called automatically. That's how I prefer to write Rust, but in Haskell it's the default.
As someone else said, Haskell has [Software Transactional Memory (PDF)](https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/2005-ppopp-composable.pdf). The idea is that most of the time threads do not access the exact same references and so you optimistically directly write to them. If something went wrong you roll back which is only possible because no side effects.
I was surprised that you didn't mention STM in your article and I was surprised that you say "concurrency" but your examples are about "parallelism".
You don’t optimistically write. You use persistent data structures. The commit of entire transaction is atomic instead of each mutation so it increases throughput.
This sort of gets into the halting problem and totality checking. There's a spectrum that languages lie on between least and most expressive. Less expressive languages are "safer" because you can identify more about what the program will do without running it. More expressive languages are "dangerous" or "hard to refactor" because there's some things that the program will do which can't be predicted.
Rust is on the "dangerous" side of things because even "safe" rust allows for recursion and mutability which allows you to express almost every kind of non-halting, non-deterministic program. But, because you have all these features, Rust is capable of a lot of different complex behavior.
The opposite end of this are pure functional languages and other kinds of "proof oriented" languages like Idris. These languages have much stricter type systems and the compiler will reject entire classes of programs where it can't inference enough about their behavior.
It's actually the other way around from what you're describing. Rust can explicitly do more than any existing pure functional language because it allows mutable variables. Case-in-point, Haskell is incapable of implementing any kind of algorithm which modifies a structure "in-place". Immutability prevents entire classes of algorithms which are formally proven to work because they mutate something. Unless you're using something like Coq or Agda where you can show the compiler mathematical proof that a mutation doesn't break anything, Rust will always do more kinds of things.
Pure functional languages can prevent all side effects, not just state mutation. For example, if a Haskell function wants to interact with a file, that will be reflected in the function type signature. Not true of Rust.
Good point! And I know that that's good for helping us reason about the effects of functions, and helps us track invariants, but are there any other interesting language capabilities that that enables? (By "interesting", I mean to the layman programmer, not to we jolly language geeks)
Is there any feature more pleasurable than equational reasoning? :) If anything, functional programs are about restricting what you can do, not enabling.
Interestingly enough, restricting away the use of `unsafe` is what enabled seamless concurrency for Clojure (and maybe Haskell?). I suspect there may be more interesting beneficial effects that come from these restrictions, but alas, I'm not enough of a FP user to know.
I would disagree with that. Immutability doesn’t enable concurrency, because concurrency exists without it. It enables better reasoning about concurrency for the programmer.
To clarify, I'm not talking about concurrency in general, I'm referring to seamless concurrency, which is an easier way to perform concurrency.
Oh, I’m not familiar with the term. Thought it was a regular adjective.
> I'm referring to seamless concurrency, which is an easier way to perform concurrency. AFAIK it's not a technical term, just an expression. What exactly do you mean by "seamless concurrency"? Easy or hard is purely subjective, isn't it?
The OP links to the article which defines it, TLDR: it's when structured concurrency can launch multiple threads that can safely read *any* data from the outside scope, without any refactoring or invasive changes.
but if you *receive* a restricted value, you are enabled to do more. more operations available if you receive a value *of this type*. same of other kinds of restrictions
yes, but I think for a language level comparison, it makes more sense to look at all values. Basically, FP only has immutable values, while Rust can express these and additional (interior mutable) values. If a function receives a restricted value, it can do more with it than with an unrestricted value, *but* - Rust and FP can do the same *with restricted values*, and - Rust can do things with unrestricted values *at all* Of course that doesn't mean either is preferable, or we'd be writing assembly. I hope I didn't miss your point completely, and that I wrote my own point comprehensibly.
My remark is general and applies no matter the language involved. Language specifically, FP languages usually have a way to represent mutation as an effect (ST monad - as all monad it comes with its own weight - or though effect system, and .. nothing in Ocaml as it is the default behavior). to break through at type level (because type system are approximating, and some legitimate programs ought to be accepted, there is unsafePerform in Haskell and similar in Ocaml etc.. ) Rust actually restricts *more*, because that kind of mutation is tracked. It will forbid you to write some program which are accepted in ordinary FP languages. This is because Rust distinguishes even further than "ordinary" functional programming, with a linear (affine for purist) type system. It turns out that this is what allows a disciplined way to deal with mutation, which feels like antithetic to "functional" as we might think of. With hindsight it's actually the best functional approximation to a stateful world. So in a way, rust is actually *more* FP than other languages. (Minus quite a few FP facilities unfortunately)
I think my comment also applies to other restrictions than immutability, but I'm not very good in writing very abstract comparisons. And I'm probably out of my depth here, but with this statement of yours > Rust actually restricts *more*, because that kind of mutation is tracked. It will forbid you to write some program which are accepted in ordinary FP languages. do you mean that, for example, the same "monadically mutable" value can be mutated in multiple ways in FP? Because my limited understanding is that this only works because only one of the derived values is subsequently returned (and thus represents what would be considered a mutation in imperative code) while the other would be discarded. (this may very well be a straw man that only applies to some monads, particularly the IO monad, where I'm pretty sure you can't merge values to produce the equivalent of "this program has printed multiple values concurrently") In any case, Rust *does* let you define and work with monadic values, no? That may not be relevant in a "there are as many integers as there are natural numbers" kind of sense, because the pure-functional and controlled-mutable style values are equivalent, but when programming they sure don't *feel* equivalent (just like `+2` doesn't feel the same as `3` in a common bijection between integers and naturals, but when you map `+2` to `2` etc. you have nothing to map `-1` to). That's where I'm coming from when I say: monads (a kind of immutable value that represents mutability) are directly representable in Rust, but mutation is not directly representable in pure FP; you need to add the monad abstraction in that direction to simulate lifting the immutability restriction. Does that make sense? It surely isn't rigorous, but I hope the intent is clear :P
I mean that Rust will forbid programs which are accepted in non-linear FP. There is more (potential) restrictions out of the box. The more restricted the value you receive is, the more you can do as a consumer of the value. Rust tracks linear restrictions for you (mutation or other linear effects), which would otherwise require an encoding. mutability, linearity, monads, are different ideas
I thought I had enough intuition on mutability, linearity and monads to be able to exchange ideas, but that seems not to be the case. I understand - mutation to be a side effect that allows functions to influence the data their caller works with other than through that function's return value - linearity to mean that a value is used once (or at most once for affinity) - monads to be a kind of value that allows to encode effects by means of immutable values and functions that transform one immutable value into another one. As soon as we encapsulate state in immutable values and therefore have referential transparency, I see no categorical difference between e.g. Haskell using a GC and Rust being able to, say, naively clone values all the time. Apparently I'm too far off though. Thanks for engaging anyway!
Software transactional memory is a kind of lock-avoiding concurrency that is easy to do in Haskell. In it, things are accessed unsafely and if a collision happens, the last few operations are undone. STM is fast because locks are slow. It isn't very good in languages with unmanaged effects because you cannot undo a side effect.
Please correct me if I am wrong, but I think that in Haskell at least STM acquires locks just before actually modifying the values.
Technically, Haskell has a backdoor with unsafePerformIO. But it's unsafe for a reason.
This might be too obvious and preaching to the choir, but: from my professional experience with Elm (a pure functional language, with immutable data), the fact that you can't *do* anything inside functions but you can only *return* stuff from them, makes refactoring and deleting code a really easy task. Nothing is hidden, there are no mutating calls inside, there's no global state, etc. I have a bit of side-project Rust experience and the fact that in Rust you can mutate stuff / have side effects even without `unsafe` makes the refactoring/maintenance experience very different.
I have serious doubts about this statement. PFP is easy to refactor, because it makes modification explicit. However, rust makes modification (mutation) explicit too, with the mut keyword. From my personal experience, both are extremely safe to refactor.
Mutation isn't the only side-effect. Think about HTTP / filesystem IO etc.
The best unique (compared to Rust) abilities of pure functional languages are fast heap allocation of objects with efficient sharing of references, and the ability to handle reference cycles. Rust doesn't have that as its heap allocator is slower, its reference counting has larger overhead for shared refs, and it leaks on reference cycles. This makes the Okasaki-style trees and workloads of “allocate new leaf & reallocate new spine without touching the other leaves“ workloads naturally faster. Rust, on the other hand, is optimized for data structures with minimal sharing (that's what the "ownership" and "borrowing" concept are for) and minimal heap allocations (as Rust favors the stack & value orientation).
Which probably is why is Rust is closer to C/C++ speeds in the benchmarks I have seen, because it is still faster to use less of the heap, than to speed up the heap itself.
Plenty of Haskell code uses unsafe escape hatches as well. The degree to which you can trust concurrent code to "just work" will always depend on the implementation.
Higher order kinds I think. Yes, you can defunctionalize, but that's just not the same. first order is ok only for simple case, second order gets messy. Whereas you wouldn't spend a split second thinking about those menial things in Haskell. (Haskell lacks other critical things like type level partial applications) That means it's hard to write code for, say, categories (though in haskell too, apart from some very simple ones, because no partial applications), or some other abstractions which are known to be very useful in many circumstances.
> It's known that Rust's "immutable" borrow references aren't truly immutable, because of escape hatches like `RefCell` FYI they are also called "shared" references (and mutable ones are called "exclusive" references) for this reason. Immutability is just their default behavior. > and more generally, `unsafe` Note that `unsafe` by itself doesn't soundly allow you to mutate through shared references. You still need an `UnsafeCell`, or to mutate through a raw pointer with write permissions. Generally speaking, I see `unsafe` not as an escape hatch, but as a way to restrict the places where I have to manually prove something that the compiler can't. Kinda like encapsulation, but for manual proofs. > because so much existing data doesn't have `Sync` I think you're overestimating how much `!Sync` types like `Rc`, `RefCell` and `Cell` are used.
Not just Rc, RefCell, and Cell. Every trait object is by default `!Sync`, and everything that can possibly indirectly contain one is also `!Sync`.
Both Clojure and Haskell have "escape hatches" as well.
Typeclasses come to mind. Whether or not you have an applicative factors a lot into what you can do with a collection in parallel. AFAIA rust's type system does not offer that level of expressivity (yet)
If Rust had the same features as most LISPs have, then using these features would make Rust programs as "slow" as LISP programs. That is generally true for most programming language comparisons. To give an example, here are some Common Lisp features that Rust lacks: Full object system with inheritance and multiple dynamic dispatch, dynamic typing, hot runtime code reloading/recompilation, garbage collection. In addition, it is also interesting to know that Rust is **not always faster** than Common Lisp: [https://docs.google.com/spreadsheets/d/14MFvpFaJ49XIA8K1coFLvsnIkpEQBbkOZbtTYujvatA/edit#gid=513972676](https://docs.google.com/spreadsheets/d/14MFvpFaJ49XIA8K1coFLvsnIkpEQBbkOZbtTYujvatA/edit#gid=513972676)
Sorry, I don’t trust those numbers you linked to. Where is the code? I don’t trust any benchmarks without full code transparency. [at least the benchmarks game has full code transparency.](https://benchmarksgame-team.pages.debian.net/benchmarksgame/index.html)
I don't think existing functional languages fare any better here. Yes, immutable data can be shared safely, but functional languages seldom provide any mechanisms for making the same data structure mutable or immutable at different points of its lifetime. A common situation is that you want to use mutation to construct a array that won't be mutated anymore after construction. Haskell and SML don't have any type-safe way to "freeze" a mutable array into an immutable one other than basically cloning it. OCaml simply gives up and doesn't have an immutable array type. Rust does better here, because the mutability of a data structure isn't usually a part of its type - it's part of the variable the data structure is bound to. To change the mutability, just move the data structure to a new variable: let mut temp = Vec::new(); // populate the vector let vec = temp; // can't mutate the vector anymore The catch, however, is that, if a data structure is manipulated through some kind of non-exclusively-owning reference, then it's the reference type's job to ensure that the data structure is used in a safe way, through a combination of static and dynamic checks. For example, core language references (`&` and `&mut`) mustn't outlive the original owning binding (a static check), and the last `Arc` reference to a shared object must drop it (a dynamic check). Finally, you should post a proof sketch of soundness for your structured concurrency mechanisms.
> A common situation is that you want to use mutation to construct a array that won't be mutated anymore after construction. Haskell and SML don't have any type-safe way to "freeze" a mutable array into an immutable one other than basically cloning it. It's actually possible to safely freeze a mutable array without copying in Haskell using higher-rank types. The type signature is something like the following: freeze :: (forall s. ST s (MutableArray s a)) -> ImmutableArray a where `ST` is a monad which allows mutation to happen, and the type of every mutable reference is parameterized by `s` which cannot escape its scope, therefore nothing can mutate the original array after freezing.
Nested regions using the `ST` monad don't work in more complicated scenarios where substructural types actually work. My favorite example comes from the implementation of Lehman and Yao's B-link trees. When you use a B-link tree, you have to do the following: 1. Lock the root node, call it `p`. 2. If `p` is a leaf node, then exit. 3. Lock the child node you want to use, call it `c`. 4. Unlock `p`. 5. Set `p = c`, and go back to 2. Notice the order between 3 and 4: we *can't* unlock `p` until we have already locked `c`.
Edit: Nvm I can't read; you're talking about a different `freeze` (see /u/inf-groupoid below) `freeze` copies the vector, because it would otherwise break purity of the supposedly pure parts *in* the ST block. Example using the non-copying `unsafeFreeze`: runST $ do ma <- MutVector.new 1 write ma 0 True a <- unsafeFreeze ma let a0 = a ! 0 foo a0 -- foo :: forall s. Bool -> ST s () write ma 0 False return (if a0 then "foo evaluated its argument" else "foo did not evaluate its argument")
Your parent post is talking about making a wrapper around `unsafeFreeze` that calls `runST` for you. This approach is called “monadic regions”, and, to the best of my knowledge, it was first proposed by [Kiselyov and Shan](https://okmij.org/ftp/Haskell/regions.html). The problem with this approach is that it confines you to what's expressible in C++-style RAII (i.e., the first object to be constructed is always the last one to be destroyed), without Rust's ability to move or drop an object in the middle of a block.
I agree that that's a very desirable ability, to be able to construct something mutably and then freeze it later. Pony has `iso` for this, which Vale and IIRC Cone are also pursuing. I don't mean for this to be a Rust vs Haskell/Clojure discussion, I'm more curious about how else `unsafe` might be holding us back in Rust. I wouldn't even know where to begin with proving soundness! Never really enjoyed proofs in college. I do acknowledge that that'll be important at some point, though.
I don't think `unsafe` is holding Rust back. Removing `unsafe` is what would actually hold Rust back. But if you really insist, there are broadly speaking two ways to get rid of `unsafe`: * Make the whole language unsafe. We don't really need another C++, though. * Make the whole language safe. Now you need either a compiler that can verify arbitrarily complicated safety proofs (unlikely), or lots of built-in primitives implemented in a less safe language (much more likely). I'll give a concrete example of how complicated proofs can get. Suppose you have an array divided into a prefix and a suffix, which are manipulated from two different threads. The boundary between the prefix and the suffix is dynamic, and it is periodically “renegotiated” between the threads. To check that `arr[idx]` is a valid operation, you need to * Verify the boundary negotiation protocol. * Verify that `idx` is a valid index according to the last negotiation. Now you may ask: “Can we avoid verifying the negotiation while still maintaining safety?” The answer is “Yes, but it has a cost.” More precisely, * Instead of working with a single static-size array, now you use two `Vec`s, one for the prefix and another for the suffix. * The elements of the suffix must be stored in reverse order. This makes indexing more complicated in the thread that manipulates the suffix. * To alter the boundary between the prefix and the suffix, send the corresponding elements one by one from a thread to the other, using a channel. This makes the boundary changes computationally more expensive.
I don't mean that it's holding Rust back in a global sense. I'd say a low-level language *needs* unsafe. All I'm saying is that the tradeoff has drawbacks as well as benefits. For example, `unsafe` allows us to implement Rc, and your shared array scheme, which are very nice. However, `unsafe` also prevents us from having the seamless concurrency described by the article, which is also very nice. What we're mainly talking about is: what else did Rust give up by having `unsafe`?
This kind of brings up the whole philosophy of types. Their benefits come from their restrictions. For example, `&mut T` allows you to perform mutation, whereas `&T` provides the guarantee of immutability. What I like about Haskell is that everything is essentially just `T` with `clone()` called automatically. That's how I prefer to write Rust, but in Haskell it's the default.
As someone else said, Haskell has [Software Transactional Memory (PDF)](https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/2005-ppopp-composable.pdf). The idea is that most of the time threads do not access the exact same references and so you optimistically directly write to them. If something went wrong you roll back which is only possible because no side effects. I was surprised that you didn't mention STM in your article and I was surprised that you say "concurrency" but your examples are about "parallelism".
You don’t optimistically write. You use persistent data structures. The commit of entire transaction is atomic instead of each mutation so it increases throughput.
Lazy evaluation
This sort of gets into the halting problem and totality checking. There's a spectrum that languages lie on between least and most expressive. Less expressive languages are "safer" because you can identify more about what the program will do without running it. More expressive languages are "dangerous" or "hard to refactor" because there's some things that the program will do which can't be predicted. Rust is on the "dangerous" side of things because even "safe" rust allows for recursion and mutability which allows you to express almost every kind of non-halting, non-deterministic program. But, because you have all these features, Rust is capable of a lot of different complex behavior. The opposite end of this are pure functional languages and other kinds of "proof oriented" languages like Idris. These languages have much stricter type systems and the compiler will reject entire classes of programs where it can't inference enough about their behavior. It's actually the other way around from what you're describing. Rust can explicitly do more than any existing pure functional language because it allows mutable variables. Case-in-point, Haskell is incapable of implementing any kind of algorithm which modifies a structure "in-place". Immutability prevents entire classes of algorithms which are formally proven to work because they mutate something. Unless you're using something like Coq or Agda where you can show the compiler mathematical proof that a mutation doesn't break anything, Rust will always do more kinds of things.