5 ms·

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). Fo

by 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...
  - tomp 8y ago
    Are different modes implemented differently? E.g. an immutable (but extensible) Map should be implemented as a tree, whereas mutable maps are best implemented using arrays.
    - tnowacki 8y ago
      No. The modes are there so that you don't need to completely switch what you are doing and do a fully copy when you need to memoize; it does not switch the underlying implementation.
    - vjeux 8y ago
      This is something that was a big source of discussions in the team. The state we're in so far is that we have two different classes for those two use cases. 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.
  - int_19h 8y ago
    I think integrating this sort of thing into the type system is long overdue. 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.

by vjeux 8y ago

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...
- tomp 8y ago
  Are different modes implemented differently? E.g. an immutable (but extensible) Map should be implemented as a tree, whereas mutable maps are best implemented using arrays.
  - tnowacki 8y ago
    No. The modes are there so that you don't need to completely switch what you are doing and do a fully copy when you need to memoize; it does not switch the underlying implementation.
  - vjeux 8y ago
    This is something that was a big source of discussions in the team. The state we're in so far is that we have two different classes for those two use cases. 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.
- int_19h 8y ago
  I think integrating this sort of thing into the type system is long overdue. 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.