I record here some ideas that I gleaned from hardware pointer designs. The time was about 1963 when CTSS was first running and Multics was being designed and described. I attended a series of Multics lectures by Bob Graham at MIT where I learned a few new pointer patterns. The notion of a pointer was then only a few years old.
I don’t know where I first recognized the pattern but it may well have been a page table entry with a bit which would invalidate stores via the entry. The notion in this context was to replace the idea of a read-only page, with the idea of a page table entry that provided only read access. More generally the idea was to include attributes in pointers and move attribute markers forwards or backwards in a directed graph of pointers at design time. I recall that previous to that insight I had seen pointers as an isolated ‘discovery’ of an immutable idea. The flexibility pattern of including attributes in pointers, and moving attribute markers forwards and backwards suddenly generated a whole new family of pointer ideas.
In an entirely different context I have used a bit in a pointer to indicate that the floating point number eventually retrieved via this indirection should have its sign changed. Depending on pointer type the effects of these bits would accumulate. Certain data structures became much smaller and efficient with this hack. Incidentally it is also a general reason not to preclude stealing a few bits from a physical pointer.
Another instance of this is the red segment node in the Keykos memory tree logic. Since there was no room in the node to mark it as red we moved the indication that it was red into the pointer (capability) thereto. This meant that we had to understand the ramifications of a node reader interpreting the ‘color’ differently from that intended by the writer. This turned out not to be a problem. It was easier to allow this case than to prevent it. Years earlier some computer designers had thought it necessary to mark each word in memory as either an instruction, or data operand. Perhaps it was von Neumann who pointed out that this was unnecessary.
The notion of using the secure hash of an immutable datum as its name was a short step from this. A hardware pointer both points to and names the datum; the hash just names. A person’s name helps find the person only with the help of auxiliary information such as a phone book.
Someone from a three letter agency asked me in 1961 whether I could think of any use of a crypto system with a different enciphering key than deciphering key. I recall saying no. This is a marker in my mind that I had no concept then of even the problem, let alone the solution provided public key cryptography. I suppose I learned of the problem, and solution, in Gardner’s 1978 Scientific American RSA article. Among other things this allowed naming things with their public key. The thing named was whatever could access the corresponding private key. I think this is the central insight of SPKI. This is my variation of the insight which treats the normal name as entirely incidental to the claimed attributes of the named thing.