<p>I asked: <a href="https://softwareengineering.stackexchange.com/q/445737/404182">What prevents Java from having immutable primitive arrays?</a> 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.</p>
<p>But I just thought, variables and references themselves can be made read-only (<code>final</code>). 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?</p>
<p>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 <code>final</code> items? Or are there edge cases that would make that not work out somehow?</p>
<p>While this is technically having immutable views to arrays rather than actual immutable arrays themselves, is there any difference in practice between a <em>'true'</em> 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.</p>

<arrays><java><immutable><runtime-performance>
Is there any way a Java-like language could implement immutable primitive arrays without incurring performance penalties?
CC BY-SA 4.0
2023-11-24T23:25:02.647Z
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?
kaya3
CC BY-SA 4.0
2023-11-25T00:02:53.570Z
“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?
Michael Homer
CC BY-SA 4.0
2023-11-25T00:03:40.520Z
@MichaelHomer What is the difference between the 2 in practice?
CPlus
CC BY-SA 4.0
2023-11-25T00:16:57.233Z
@harold Yes, but suppose an array was created as read only. Then there would be no mutable views to the array, so the array would be behaviorally indistinguishable from just an immutable array, right?
CPlus
CC BY-SA 4.0
2023-11-25T00:28:00.157Z
There can be other properties than types.  Those other properties go to mutability, many other things.  These are hard to shoehorn into a type system since mutable x and immutable x are not necessarily related in a type system / subtyping friendly way.  So,. types are just one property, while there are others.
Erik Eidt
CC BY-SA 4.0
2023-11-25T00:30:06.963Z
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.
Moonchild
CC BY-SA 4.0
2023-11-25T00:32:07.213Z
Furthermore, a good compiler will be able to elide the overhead of the runtime check in many cases.
Moonchild
CC BY-SA 4.0
2023-11-25T03:07:17.077Z
I think the main issue is if the language runs on the JVM and it compiles to a JVM array, then it can be modified by other JVM code via reflection. Otherwise, I believe OCaml has stand-ins for most of Java's features (including objects) and it has truly-immutable lists.
tarzh
CC BY-SA 4.0
2023-11-25T03:17:14.473Z
Another caveat is if the array is technically mutable, but doing so would violate the language's rules. In C++ you can have `const` arrays which aren't "supposed" to be modified (if the object was declared as `const`, doing so is UB), but you can `const_cast` them. In Java, not a primitive, but there are classes like `ImmutableList` internally store an array but don't expose any way to modify it.
tarzh
CC BY-SA 4.0
2023-11-28T13:34:28.780Z
@tarzh Fun fact: `System` has [public static final PrintStream out](https://docs.oracle.com/javase/8/docs/api/java/lang/System.html#out) and an accompanying [public static void setOut(PrintStream out)](https://docs.oracle.com/javase/8/docs/api/java/lang/System.html#setOut-java.io.PrintStream-).
tevemadar
<p>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.</p>
<p>On this level, there’s no issue with using the existing static type system to back that. <em>Java</em> 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.</p>
<p>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.</p>
<hr />
<p>Your proposal that</p>
<blockquote>
<p>a mutable array reference could be converted to an immutable one but not vice versa</p>
</blockquote>
<p>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.</p>
<p>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 <em>new</em> immutable array with the same contents covers many uses for it also.</p>
<p>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.</p>
<hr />
<p>It’s also worth noting that C#, perhaps the <em>most</em> Java-like language, has immutable “arrays” in the System.Collections.Immutable.ImmutableArray&lt;T&gt; 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.</p>

CC BY-SA 4.0
2023-11-25T04:02:46.083Z
2023-11-25T04:02:46.083Z
Michael Homer
<p>Nothing about the overall design of Java would preclude support for an immutable array type.  Having the underlying virtual machine &quot;understand&quot; a type that includes support for &quot;real&quot; immutability, however, could make things more efficient than would be possible under the JVM.</p>
<p>A good starting basis would be a type of reference that could identify any of four kinds of arrays:</p>
<ol>
<li><p>Arrays which may be read or written, but may only be accessed on the thread where they are created.</p>
</li>
<li><p>Arrays which may only be read, but may be accessed on any thread.</p>
</li>
<li><p>Arrays which may be read or written, but only on the thread where it is created.</p>
</li>
<li><p>Arrays which may be read or written on any thread.</p>
</li>
</ol>
<p>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 &quot;permanent&quot;.  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.</p>
<p>From this, one could add a family of reference-to-array types which could identify various subsets of the above.</p>
<ul>
<li>Reference to any array</li>
<li>Reference to any array that's readable on the current thread</li>
<li>Reference to any array that's readable and writable by the current thread</li>
<li>Reference to any array that was created by the current thread</li>
<li>Reference to an array of type #1 that was created by the current thread</li>
<li>Reference to any array that's readable on any thread</li>
<li>Reference to any array that's readable and writable on any thread</li>
<li>Reference to any array that's immutable (and thus readable by any thread)</li>
</ul>
<p>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 &quot;owned&quot; by other objects, but semantics are more important than syntax.</p>
<p>A common weakness in many &quot;Popsicle immutability&quot; 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.</p>
<p>Additionally, it may be useful for each array to hold a &quot;reference to array known to be equal&quot; field which is initially empty, and would only be relevant on arrays that end up being &quot;frozen&quot;.  If two immutable arrays are compared and found to be equal, and the VM defined a &quot;seniority&quot; 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).</p>

CC BY-SA 4.0
2023-11-28T17:32:24.087Z
2023-11-28T17:32:24.087Z
supercat
<p>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. <code>final int[] foo</code> vs. <code>int final[] foo</code> (the latter meaning that the array itself is immutable, and that it can be replaced, but only by another immutable array).</p>
<p>But do keep in mind that this fundamentally makes the immutability a property of <em>the variable, not</em> 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.</p>
<p>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 &quot;immutable array&quot; 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. &quot;the array's elements will not change within this scope&quot;) as long as anyone else could have a reference to the same array object.</p>

CC BY-SA 4.0
2023-11-26T20:29:11.703Z
2023-11-26T20:29:11.703Z
Karl Knechtel
CC BY-SA 4.0
2023-11-26T20:42:13.767Z
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.
kaya3
# Is there any way a Java-like language could implement immutable primitive arrays without incurring performance penalties?
Posted by: username_0 on 2023-11-24
I asked: [What prevents Java from having immutable primitive arrays?](https://softwareengineering.stackexchange.com/q/445737/404182) 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.
**Tags:** arrays java immutable runtime-performance
> **Comments:**
> **username_1**: 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?  
> **username_2**: “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?  
> **username_0**: @MichaelHomer What is the difference between the 2 in practice?  
> **username_0**: @harold Yes, but suppose an array was created as read only. Then there would be no mutable views to the array, so the array would be behaviorally indistinguishable from just an immutable array, right?  
> **username_3**: There can be other properties than types.  Those other properties go to mutability, many other things.  These are hard to shoehorn into a type system since mutable x and immutable x are not necessarily related in a type system / subtyping friendly way.  So,. types are just one property, while there are others.  
> **username_4**: 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.  
> **username_4**: Furthermore, a good compiler will be able to elide the overhead of the runtime check in many cases.  
> **username_5**: I think the main issue is if the language runs on the JVM and it compiles to a JVM array, then it can be modified by other JVM code via reflection. Otherwise, I believe OCaml has stand-ins for most of Java's features (including objects) and it has truly-immutable lists.  
> **username_5**: Another caveat is if the array is technically mutable, but doing so would violate the language's rules. In C++ you can have `const` arrays which aren't "supposed" to be modified (if the object was declared as `const`, doing so is UB), but you can `const_cast` them. In Java, not a primitive, but there are classes like `ImmutableList` internally store an array but don't expose any way to modify it.  
> **username_6**: @tarzh Fun fact: `System` has [public static final PrintStream out](https://docs.oracle.com/javase/8/docs/api/java/lang/System.html#out) and an accompanying [public static void setOut(PrintStream out)](https://docs.oracle.com/javase/8/docs/api/java/lang/System.html#setOut-java.io.PrintStream-).  
---
## 3 answers
### Answer by username_2 on 2023-11-25. Score: 2
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 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.
---
### Answer by username_7 on 2023-11-28. Score: 0
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).
---
### Answer by username_8 on 2023-11-26. Score: 0
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.
> **Comments:**
> **username_1** (2023-11-26): 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.  
---
