Types of immutability
There are several types of immutability used or contemplated in Klink.
- Complete immutability
- Not much to be said.
- Pair immutability
- A pair that forever holds the same two objects, though those objects' contents may change.
- List immutability
- For instance, a list where you can change the contents, but not the number of elements.
- Recursive structural immutability
- An immutable tree of mutable non-pair objects.
- Administrative immutability
- Eg, what ports typically have. When you read or write to a port, it remains "the same thing" administratively.
Current status in Klink
Available in C, used in some places such as symbols and strings. AFAICT there's no way to specify its use or non-use in Kernel; some objects just have it because of what they are or how they are created.
Recursive structural immutability (Tree immutability)
No C flag for it. Like complete immutability, some objects just have it because of what type they are.
Non-recursive structural immutability?
If you read section 4.7.2 of the Kernel report (
you may notice that Pair immutability and List immutability are
actually extensions. So I figured I should at least advance a
rationale for them.
Is non-recursive immutability worth supporting? ISTM it's already strongly suggested by Kernel.
- Implied by an informal type
Some combiners take finite lists as
arguments; all applicatives require a finite list as argobject.
That distinguishes the finite list as at least an informal type.
There's a predicate for it,
finite-list?, but pairs that "are" finite lists can "become" other sorts of lists (dotted or circular), so it falls short of being a formal type. This seems like an irregularity to me. Structural immutability would solve it.
- Implied by implied algorithms
For some combiners (eg
reduce), any practical algorithm seems to require doing sub-operations on counted lists. That implies a structurally immutable list, because otherwise the count could theoretically become wrong; in practice it's saved from this by writing the algorithm carefully. So there are at least ephemeral, implied structurally immutable lists present.
- John once told me that he would eventually like to have vectors in Kernel. Vectors are optimized structurally immutable finite lists.
- Opportunity for optimization
- There's an opportunity for other optimizations where list immutability is used and recognized. In particular, caching a list's element count is often nice if one can be sure the list count won't change.
|Type of immutability||Pair||List||Tree|
|Special care needed|
|for shared objects?||No||Only own tail||Yes|
|Exists in Klink?||Yes||No||Yes|
|Exists in Kernel?||No||No||Yes|
|What might be mutable?||car, cdr||elements||leaves|