The big challenge is how do you maintain those guarantees while having a language that product engineers would want to write in.
You can decide to not allow mutability in your language but developers need to think about code in a very very different way than what they do now. It’s also going to be challenging to convert/translate existing codebases and patterns to it.
So we decided to allow both mutability and immutability. But it poses very interesting challenges. For example in the standard library, what is the type of x.map(y -> z). Which pieces are mutable or immutable. If you are not precise enough in your type system, then you are going to type it as “i don’t know (readonly)” or “mutable” but then you can’t pass the result of this to a memoized function, so you lost the point of the language.
The other interesting aspect is that the backend relies on the fact that the invariant are true in order to output optimized code and garbage collector.
So we cannot “cheat” like many gradual typed languages like Hack, TypeScript, C# where they can just say, actually this type is wrong but i’m just going to ignore it and it’ll throw an exception at runtime if the programmer got it wrong. It would segfault in Skip case.
For Skip to have to know that the actual instance is immutable, and that no one has a reference to a mutable version of that instance. If the inputs/outputs change after the memoization, we cannot guarantee the correctness of the reactivity/cache-invalidation. Thus for memoizing the inputs/outputs to a function, we need to know that the object, and any of its fields, will never be modified. In other words, we need to know if the object is transitively immutable. In order to get this sort of analysis, you need the type system to provide the information, and it is not enough to have a simple local analysis.
[[This was written by Todd Nowacki but his new HN account has been flagged as commenting too fast...]]
PS: Whatever, it pleases me that somebody has finally come to the idea of a heavily-memoized language that would still support mutable imperative parts and tried implementing it. I've been thinking "why the eck there is no language that would memoize pure functions automatically" for so many years already (but I've always been dismising the idea of building it myself as I lack sufficient background in computer science to build a compiler that would produce reasonably fast programs so it would be impractical to invest time). The only language I've found easy to add automatic memoization to is Python.
PPS: That's a pity Todd Nowacki has been flagged, HN should really learn to distinguish between garbage fast commenters and qualified resourceful writers.
> but can't an object be considered immutable when all its fields are immutable and all its member functions (but the constructor perhaps) are pure?
How exactly do you expect to track this accurately without integrating it into the type system? It's not an issue of whether or not the field itself is assignable, but whether or not the type that it points to is mutable. This becomes much more difficult to determine when generics are involved. This sort of type level knowledge for generics would make it hard to staple onto an existing type system. Even if you did, you would likely end up with a lot of code duplication as you would need two forms of types, immutable and mutable, e.g. `ImmVector` and `MutVector`, `ImmMap` and `MutMap`, `ImmMyObject` and `MutMyObject`, etc. To make this more ergonomic, Skip has a mode based mutability model, where the mutability is determined not at the class declaration, but rather at the type annotation/object instantiation. So we would then have `Vector` and `mutable Vector`, two modes of the same class.
You can read more here: http://skiplang.com/blog/2018/04/10/understanding-mutability...
Ideally, in a OO language, what I want is to be able author a single class, but then "overload on immutable", so to speak. So there are some class members that are shared for both implementations, and then there are some that are only there when the object is mutable, or is immutable (in the most extreme case, there are no shared data members or method implementations at all, and only the API is common).
That would imply that a class definition effectively implicitly defines a trait derived from the common members - e.g. "Vector", having operations such as "size" or "[index]" - and then two distinct classes, e.g. "mutable Vector" and "immutable Vector", both implementing the trait, and providing some extra APIs where that makes sense.
This would be helped a lot by a full decoupling of classes from types, as some modern (and not so modern - e.g. OCaml is practically a golden standard here) languages do.
struct Foo {
A bar(); // If the instance is non-const.
A bar() const; // If the instance is const.
};
Of course this is C++ so it's up to you to make sure that all the types contained in your object are also immutable when they're const-ed (e.g. avoid pointers). And the mutable keyword is a backdoor.Or perhaps you wanted to be able to change the representation (e.g. member variables) of your type based on whether it's mutable or not? Although in that case I'd probably go with an interface.
As far as changing representation, that's exactly what I meant by "class members" (and why it doesn't say "class methods"). An immutable map should have a different internal representation from a mutable map, for example, to permit for efficient copy-with-update. But logically, they're both maps. C++ punts on this problem - a map is a map, and the only thing that "const" does is make its data immutable, which in practice means that immutable containers aren't used much because there's no way to do copy-with-update (e.g. given a const std::list, you can't efficiently create a new const std::list with an item prepended, like you can in Lisp or ML - you have to create a whole const std::list, copying all items from the original one).
Languages that tried to tackle this basically just came up with a pattern where you just write two completely different classes, that have a common pattern in the name by convention (like Map and ImmutableMap), and implement a common interface/trait. But there's no link between those two classes other than convention, and the common interface has to be authored manually, even though it can be derived entirely from the two classes in practice.
So, what I'm proposing is basically a better way to write Map and ImmutableMap in a way that would 1) make it clear that those are semantically related, even though they're distinct in implementation, and 2) automatically derive the common trait. So when I write a function, I can say "takes a Map", and that's a trait that covers both "mutable Map" and "immutable Map" - automatically!
The hashmap version of immutable maps are really useful for the "builder pattern". This is very common in product code. You create a mutable local map by slicing the inputs in many ways and freeze it at the end. We have an optimization that makes freeze a no-op if we can prove that there are no references to the variable that escape (it's true in many cases). We often talked about doing a compaction step at this point but haven't played with it.
The tree version of immutable maps are really useful when you are mutating (hmmm...) it after it escapes the function.
The problem is that the two have a very different API and complexity trade-offs. We haven't found a way to unify the two APIs and have the compiler able to pick one or the other transparently behind the scenes.
Also, one thing the language tries to have is predictable performance. Having a different complexity based on whether an optimization is kicking in or not is something that bit us many many many times on the dynamic languages we're working on (Hack, JavaScript, Python) that it is something we're trying to avoid with Skip.
val buf = scala.collection.mutable.ArrayBuffer.empty[Int]
buf += 1
is perfectly valid. You can't reassign buf to another object, but you can change the underlying object. Making something "truly" immutable when that's allowed is tricky. Apache Spark (built on top of Scala) goes a long way to try and achieve this, and is able to do a number of optimizations as a result, but IIRC there are still significant cases it isn't able to resolve.The other approach is to do deep copies but it’s very expensive in practice.
Kinda like C++'s const, except that's actually "readonly" (which is also handy to have!), while what we really need is "immutable". Or rather make immutable the default, and then "readonly" and "mutable" have to be explicit everywhere.
I wholeheartedly disagree. Scala is among the most difficult languages to master. From experience, a successful compilation do not shield you from bugs and runtime exceptions. NullPointerException being my favourite, as a reminder that lots of libraries are built on top of Java's ecosystem, and thus plagued with the same curse.
And even if you're toying with pure Scala code, without any dependencies, it's still possible to end up in a state where the given traceback would be absolutely useless and full of (Anonymous) calls. Good luck with that.
also just shared it here https://news.ycombinator.com/item?id=18080598 if you have comments
I am quite frankly speechless that anyone could hold this opinion.
If a non-trivial program runs as expected on the first try I get really suspicious.
When you want to memoize a function, then we move all the arguments to the intern heap which makes structurally equal values have the same pointer. Then we can figure out quickly if two immutable values are equal.
We have an intern() function that lets you move a value to the intern heap manually. We are also thinking about adding a field for objects such that once it is interned somewhere, if you intern it again, it's a no-op and we use the pointer in the object. This would avoid accidentally increasing the complexity of an algorithm by repeatedly interning the same value.
Why don't you just use the functools.lru_cache decorator in the standard library?
By the way it seems very sad to me that the majority of imperative and hybrid (functional×imperative) languages lack syntax for immutable variables: in just so many cases I introduce a variable to store an intermediate result of an operation an don't mean to re-assign it ever after, it's nice of a developer to define this intention explicitly and of a compiler to raise an error when the variable is re-assigned accidentally - this simple feature is among the reasons why Scala programs usually are comparably easy to debug and run as expected as soon as they get compiled successfully.