Previously
Klink is my standalone 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 nonpair 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 nonuse in Kernel; some objects just have it because of what they are or how they are created.
Recursive structural immutability (Tree immutability)
Supported via copyesimmutable
Administrative immutability
No C flag for it. Like complete immutability, some objects just have it because of what type they are.
Nonrecursive structural immutability?
If you read section 4.7.2 of the Kernel report (copyesimmutable
),
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 nonrecursive 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,
finitelist?
, 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 suboperations 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 
No comments:
Post a Comment