4 ms·

The problem that the language is trying to solve is essentially building safe caches. Once a value is in the cache it cannot be changed from inside the program

by vjeux 8y ago

The problem that the language is trying to solve is essentially building safe caches. Once a value is in the cache it cannot be changed from inside the program (the solution we opted for is to make it deeply immutable) and externally (if it depends on some external data, we need to invalidate the cache when it changes). 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.

qwerty456127 8y ago
It feels like I didn't really get it given your explanation as I still can't understand why doesn't Scala (as a language, I know its actual compiler doesn't handle memoization on itself and won't remember the exact type in many cases (see "type erasure") actually) suit these needs?
- vjeux 8y ago
  This goes far beyond having a local variables being assigned (assuming you mean the local being assigned and not mutating the object assigned to the local). 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...]]
  - qwerty456127 8y ago
    I understand this, 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? And isn't this what C# structs (and Scala case classes although both can be equipped with mutable fields and impure methods if the developer wants but this isn't a recommended pattern) are meant to be? If this doesn't solve the problem then what is the solution proposed? 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.
    - tnowacki 8y ago
      I got unflagged! > 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.html http://skiplang.com/blog/2018/04/10/understanding-mutability...
- SatvikBeri 8y ago
  As an example in Scala, consider: 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.
  - qwerty456127 8y ago
    I know this (and even use this occasionally), that's why there are whole separate families of collections in Scala - mutable and immutable collections. And I think it is possible for the compiler to figure out if a type (e.g. a collection type) is mutable or not given its source code and even if it isn't it probably can be made possible by introducing some sort of special annotations to class definitions.

by vjeux 8y ago

qwerty456127 8y ago

It feels like I didn't really get it given your explanation as I still can't understand why doesn't Scala (as a language, I know its actual compiler doesn't handle memoization on itself and won't remember the exact type in many cases (see "type erasure") actually) suit these needs?

vjeux 8y ago
This goes far beyond having a local variables being assigned (assuming you mean the local being assigned and not mutating the object assigned to the local). 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...]]
- qwerty456127 8y ago
  I understand this, 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? And isn't this what C# structs (and Scala case classes although both can be equipped with mutable fields and impure methods if the developer wants but this isn't a recommended pattern) are meant to be? If this doesn't solve the problem then what is the solution proposed? 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.
  - tnowacki 8y ago
    I got unflagged! > 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.html http://skiplang.com/blog/2018/04/10/understanding-mutability...
SatvikBeri 8y ago
As an example in Scala, consider: 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.
- qwerty456127 8y ago
  I know this (and even use this occasionally), that's why there are whole separate families of collections in Scala - mutable and immutable collections. And I think it is possible for the compiler to figure out if a type (e.g. a collection type) is mutable or not given its source code and even if it isn't it probably can be made possible by introducing some sort of special annotations to class definitions.