I have suggested elsewhere that Keykos nodes might be compared with control block of classic software technology.
Nodes can point to other nodes and even hold data grudgingly.
I wonder aloud here which pointer like things may be profitably be replaced by capabilities.
I learned of a surprising data structure in a lecture on Multics.
It was the KST: Known Segment Table.
An address space was composed of segments and a segment might belong to several spaces, each at some particular address within that space.
There was one KST entry for each membership of a segment in an address space.
The KST entry had 5 words, two bilateral pointers to other KST entries for this segment in other spaces,
two bilateral pointers to other KST entries for other segments within this space, the virtual address within this space at which this segment is accessed.
I had learned of linked lists only a few years earlier.
This was the first structure I had seen where you could navigate to data from different directions.
It was sort of like an array element belonging to two arrays at once.
Relational data base systems
have just one important piece of magic, I think.
They abstract away the difference of A’s designating B’s, and B’s designating A’s.
You can write code that is oblivious to this otherwise vital distinction.
A predecessor to this technology was CODASYL which was a proposed language in which to express algorithms for navigating thru a data base with pointers.
A companion language was specified in which to describe such pointers.
The suggestion was that a relational data base could be accessed by a language, such as SQL, in which you could express those tasks for which CODASYL had been invented.
This would require a great deal of additional software technology, however.
Programs for such tasks would be oblivious to data base reorganizations that introduced new pointers and removed others.
I think that the promise was credible enough to win mind-share and I wonder what fraction of that promise has been fulfilled.
Certainly a great deal of it has been.
If you take the field values by which you can jump from one table to another as unprotected data, then these data bases do not provide the advantages of protected names which is at the heart of capability theory.
One gedankin experiment imagines field values that cannot be typed.
One must thereby invent a way for the first table entry with such a value to arise.
A capability arises just as an object is created.
A field value in a table may be invented when there is not yet, or never will be something that it refers to.
This is a strength and weakness in RDBS.
Is this merely a design pattern for doubly linked lists?
Does it have a useful analog in the world of immutable structures?