Thinking about Immutability in Klink

Previously

Klink is my stand-alone implementation of Kernel by John Shutt.

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

Complete immutability

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.

Pair immutability

This is the default in Klink. To get mutable pairs, use mcons instead of cons. I was persuaded of this by Getting rid of set-car! and set-cdr! and Racket, also here.

List immutability

No way to have a pair whose car is mutable but whose cdr recursively isn't.

Recursive structural immutability (Tree immutability)

Supported via copy-es-immutable

Administrative 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 (copy-es-immutable), 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.

Vectors

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.

Comparison table

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