1
$\begingroup$

I asked: What prevents Java from having immutable primitive arrays? a while back and got an answer: Because immutable primitive arrays would typically require checking some immutable flag every time a write attempt is made, slowing down performance.

But I just thought, variables and references themselves can be made read-only (final). Yet they do not have a immutable flag associated with them (as far as I know), rather, they are checked at compile time. Would having a similar mechanism for immutable arrays be possible?

For example, a mutable array reference could be converted to an immutable one but not vice versa, and thus any attempt made to write to an immutable array could be rejected at compile time, similar to other final items? Or are there edge cases that would make that not work out somehow?

While this is technically having immutable views to arrays rather than actual immutable arrays themselves, is there any difference in practice between a 'true' immutable array and an array created as an immutable view, so no non-immutable view exists? Either way, the array cannot and will not be modified.

$\endgroup$
11
  • 4
    $\begingroup$ Nothing seems to prevent a Java-like language from having immutable arrays. The mechanism for enforcing this at compile-time would be the type system. Is that the answer that you're looking for, or is there some reason you doubt that having separate types for immutable arrays would be a good solution? $\endgroup$
    – kaya3
    Nov 24, 2023 at 23:25
  • $\begingroup$ “a mutable array reference could be converted to an immutable one but not vice versa, and thus any attempt made to write to an immutable array could be rejected at compile time” seems to be proposing read-only references to arrays, not immutable arrays; which one are you meaning to ask about? $\endgroup$
    – Michael Homer
    Nov 25, 2023 at 0:02
  • $\begingroup$ @MichaelHomer What is the difference between the 2 in practice? $\endgroup$
    – CPlus
    Nov 25, 2023 at 0:03
  • 1
    $\begingroup$ I believe java implementations already need a runtime check when writing to an array: suppose B <: A, C <: A, and I cast a B[] to an A[] and try to write a C into it; this errors at runtime. It seems quite likely to me that it would be possible to extend this mechanism to support readonly arrays with no additional performance cost. $\endgroup$
    – Moonchild
    Nov 25, 2023 at 0:30
  • 1
    $\begingroup$ Furthermore, a good compiler will be able to elide the overhead of the runtime check in many cases. $\endgroup$
    – Moonchild
    Nov 25, 2023 at 0:32

3 Answers 3

2
$\begingroup$

There is nothing stopping a Java-like language from having statically-enforced immutable arrays. These would be of a different type to the existing mutable arrays. Freshly-constructed array literals can trivially be treated as immutable array constructors of this type, and the compiler will know which references have that type so that no mutation operations will be permitted, and no casts to anything but another immutable array type can be performed.

On this level, there’s no issue with using the existing static type system to back that. Java specifically does make its primitive arrays visibly special via their interactions with overloading, variadic methods, and erasure, and a new array type would be incompatible with those, but this isn’t a broader issue.

The more you’re happy to prohibit statically, the easier this is, and the more you can reuse the baseline primitive mutable arrays and implement the semantics purely in the compiler. Prohibiting all cast and assignment operations, and making the immutable type unassignable to mutable array types, is sufficient. If you want to hold them in erased generic storage locations, for example, you need to implement a distinct runtime type as well, but if you disallow that you can probably get away without it.


Your proposal that

a mutable array reference could be converted to an immutable one but not vice versa

works only for unique linear or affine array references; otherwise, it would still be possible to mutate the array via a pre-existing reference, just not through the new one. Unique references would be an additional new concept for Java, though a number of research languages that are broadly Java-like have general linear, affine, immutable, or read-only references already, and would get all this for free.

If only source-level literal immutable arrays are required, you don’t need this conversion at all. A method on the mutable array type that produces a new immutable array with the same contents covers many uses for it also.

A read-only array type, which could contain either a mutable or immutable array, would likely be useful. This would be a purely static construct, with no difference in the storage type, and it’s possible that this is more what you’re thinking of given the example. You couldn’t mutate an array through one of these references, but you could observe changes made through aliases.


It’s also worth noting that C#, perhaps the most Java-like language, has immutable “arrays” in the System.Collections.Immutable.ImmutableArray<T> struct. These have some runtime support and are accessed identically once created, but are not quite as primitive as base arrays and don’t have their compiler support.

$\endgroup$
0
$\begingroup$

To have immutable arrays that are statically checked for immutability in a statically typed language, the immutability needs to be part of the array's type. That requires syntax at least; not insurmountable - we can take inspiration from C++, and imagine e.g. final int[] foo vs. int final[] foo (the latter meaning that the array itself is immutable, and that it can be replaced, but only by another immutable array).

But do keep in mind that this fundamentally makes the immutability a property of the variable, not the object it holds. The point of static typing, and thus static checking, is to examine the statically available information; and the objects don't exist until runtime.

Converting references would probably not be desirable. Of course it would defeat the purpose to be able to treat an immutable array as if it were immutable. But binding a mutable array to an "immutable array" type variable is also not that useful; while that could help the programmer avoid certain kinds of unintended mutations, it would not allow for any additional reasoning about the code (i.e. "the array's elements will not change within this scope") as long as anyone else could have a reference to the same array object.

$\endgroup$
1
  • 2
    $\begingroup$ In Typescript, the distinction is readonly x: number[]; vs. x: readonly number[];. Typescript allows converting T[] to readonly T[] but not vice versa, which means that readonly T[] is more like a read-only view of an array, rather than necessarily an immutable array. To ensure true immutability you need no cross-assignability in either direction. $\endgroup$
    – kaya3
    Nov 26, 2023 at 20:42
0
$\begingroup$

Nothing about the overall design of Java would preclude support for an immutable array type. Having the underlying virtual machine "understand" a type that includes support for "real" immutability, however, could make things more efficient than would be possible under the JVM.

A good starting basis would be a type of reference that could identify any of four kinds of arrays:

  1. Arrays which may be read or written, but may only be accessed on the thread where they are created.

  2. Arrays which may only be read, but may be accessed on any thread.

  3. Arrays which may be read or written, but only on the thread where it is created.

  4. Arrays which may be read or written on any thread.

An array instance of the first type could be safely converted to any of the others (but only on the thread which created it), but any conversion would be "permanent". Because only one thread would be able to do anything with an array instance prior to its conversion to some other type, there would be no way conversion could create any kind of race condition.

From this, one could add a family of reference-to-array types which could identify various subsets of the above.

  • Reference to any array
  • Reference to any array that's readable on the current thread
  • Reference to any array that's readable and writable by the current thread
  • Reference to any array that was created by the current thread
  • Reference to an array of type #1 that was created by the current thread
  • Reference to any array that's readable on any thread
  • Reference to any array that's readable and writable on any thread
  • Reference to any array that's immutable (and thus readable by any thread)

Conversions to more general reference types could be performed without need for run-time checks, while conversions to more specific types would require runtime checks. Additionally, operations that load a reference of a type that's limited to working with the current thread would need to validate that the object in question is associated from the correct thread unless the container from being which it is loaded is already bound to the current thread. I'm not sure how best to syntactically distinguish among the different array types, or between references that encapsulate array contents versus those that identify arrays "owned" by other objects, but semantics are more important than syntax.

A common weakness in many "Popsicle immutability" designs is that race conditions may arise if a thread tries to write an object as it is being frozen. Requiring that the thread that created an object must either freeze it or permanently prevent it from being frozen before any other thread can do anything with it would eliminate that race condition.

Additionally, it may be useful for each array to hold a "reference to array known to be equal" field which is initially empty, and would only be relevant on arrays that end up being "frozen". If two immutable arrays are compared and found to be equal, and the VM defined a "seniority" characteristic for references, the junior array could have a reference to the senior array stored here and then, at the next GC cycle, any existing references to the junior array could be replaced with references to the senior one (allowing the junior array to be collected).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .