The Object Model: A Historical Perspective

IBM Research Report RC 10809
October 1984

Larry Koved

IBM Research Division
Thomas J. Watson Research Center
P.O. Box 218
Yorktown Heights, New York 10598

Abstract

The object model is an abstraction mechanism useful for understanding the design and implementation of systems. The notion of objects and object manipulation is pervasive throughout computer science literature. When applied to computing systems, there are two main areas of discussion: hardware support for the protection of objects, and language abstraction mechanisms which support object oriented concepts.

Objects in a computer system are either passive or active. Passive objects are program variables or databases. Active objects are instantiated programs and procedures which act upon and transform passive objects.

This paper will discuss the history of protection and abstraction with respect to the object model. The first half concentrates on hardware and computing systems, and their protection mechanisms. The second half discusses the evolution of various forms of abstraction in programming languages.

Preface

At this point, the paper is incomplete. There are other papers of importance which will be either included when I finish this paper, or will be listed as related reading material. I plan to add sections on APL, CLU (Liskov, et. al.), Alphard (Shaw, et. al.), and SIMULA (Nygaard, Dahl, et. al.). I hope to complete this survey in early 1985. In the meanwhile, I would like to solicit comments and suggestions. In particular, any suggestions on additional systems, both hardware and software, to include in this paper would be greatly appreciated.

Deliberate omissions include CAL, ADA, and COBOL. I felt that these did not significantly further the understanding of object oriented systems because of their similarity to systems already described in this paper.

I can be contacted primarily through my userid at IBM, or the University of Maryland. My e-mail addresses are:

Within IBM: Larry Koved/Watson/IBM

Internet:   koved@us.ibm.com

Larry Koved

September 7, 1984

Contents

Abstract
Preface
What is the Object Model?

Hardware, Systems, and Protection Mechanisms
Conclusion
Appendix
Footnotes
References

What is the Object Model?

The object model is an abstraction mechanism useful for understanding the design and implementation of systems. The notion of objects and object manipulation is pervasive throughout computer science literature. Objects are either passive or active. Passive objects are program variables or databases. Active objects are instantiated programs and procedures which act upon and transform passive objects. Carefully designed programs and procedures maintain the invariant properties of the passive objects. Hence, the active objects preserve the invariant properties of the passive objects. Preservation of the invariant properties of passive objects is a requirement for the construction of provably correct and reliable systems.

The notion of passive and active objects is a tool for developing concepts about protection and abstraction within computer systems. When applied to computing systems, there are two main areas of discussion: hardware support for the protection of objects, and languages which support object oriented concepts. The first component is the protection mechanisms used to prevent unauthorized or unintended access to and modification of objects. The emphasis is on the general methods for accessing and protecting objects stored in computers. The evolution of hardware protection mechanisms is discussed with respect to the ways in which the mechanisms support or fail to support the object model.1 The second component is the abstraction mechanism which hides the details of the representation and implementation of systems.

Protection and Security

Protection mechanisms constrain the ways in which information is shared or resources are accessed and modified. The concepts of rights and domains are major issues in the implementation of protection mechanisms. A right, or a capability, is a permission to gain access to an object. Typical rights include read, write, and execute permission. File systems typically use rights to determine the types of operations a user is allowed to perform on a file system object. A domain is an instantiation of a program or procedure with a set of rights associated with it. A domain for a given user may permit read/write access to the user's own directory of files, but only read access to another's directory. A procedure in one domain may invoke a procedure in a different domain to perform functions on behalf of the caller. In some circumstances the called procedure may execute in a restricted domain and have fewer rights than the caller. Conversely, amplification may be used to give the called procedure additional rights which the caller did not possess. An example of amplification is an application program requesting the operating system to perform a privileged operation.

Security policies dictate the ways in which users and processes are permitted to access and manipulate objects. Protection mechanisms attempt to enforce the security policies by regulating how domains acquire, disseminate, and retract rights.

A motivation for protection mechanisms is the principal of least privilege.. This principle states that a domain should only have the minimum number of privileges necessary to perform its function. An implication of this principle is that domains and objects manipulated by the domains should be relatively small. Therefore, the protection mechanisms should support small objects and efficient domain switching.

A topic closely related to object model and protection is the construction and verification of secure systems. Provably secure operating systems usually take the approach of writing a small, verifiable, operating system kernel. This kernel provides the basic services necessary for secure operation of the system. It is usually divided into smaller routines which provide abstract functions and are individually validated. Languages have been designed for the purpose of writing and proving security properties of operating systems. Details of this approach to operating system development can be found in [MILL76] [POPE77] [CHEH81] [WULF76].

Abstraction

Abstraction is fundamental to the object model and appears to be vital in proving properties of programs and systems. In addition, abstraction played an important part in the development of programming languages as they evolved in the 1970's [JENS74] [WIRT83] [LISK75] [GOLD83].

Instantiations of data types are passive objects. An object's representation is based upon a set of primitives supported by the language or the machine, and other defined abstract data types. A limited set of procedures are defined to access and manipulate instantiations of an abstract data type. These procedures are aware of the object's representation and must maintain the object's invariant properties. Before and after a procedure manipulates a passive object, the object's invariant properties are true, although during the operation on an object they may be temporarily false [JONE79] [HOAR69] [HOWA76] [OWIC76]. Procedures which desire to use an abstract object must use call the procedures which define the data type.

The advantages of using abstract data types and a set of procedures to manipulate the instances of the abstract data type are numerous. Programs can be decomposed into successively simpler pieces. Each piece has well defined inputs and outputs which aid in system development and maintenance. Should the representation of an object change, only the small set of procedures using the object's representation need to be modified. The remainder of the system need not be aware of the changes because they are not dependent upon the object's representation and implementation. Use of a limited number of procedures to manipulate objects supports the concept of information hiding.

Both the programming languages and hardware protection mechanisms to support the object model have developed in parallel since the early 1960's. First, the development of computer hardware and systems will be viewed, primarily with respect to protection mechanisms.

Hardware, Systems, and Protection Mechanisms

During the past 25 years, protection mechanisms in computer hardware have developed considerably. The earliest machines provided little or no protection of computing resources such as memory, I/O devices, and information. Therefore, various hardware and software mechanisms have been created to address these issues. Many implementations of the computer protection mechanisms can be viewed as memory protection and control over privileged instructions.2

Non-Segment Machines

Unprotected Machines model

Early computers had unprotected linear address spaces into which the users loaded their programs. There were no operating systems, so these programs essentially controlled the entire machine, including the I/O devices.

Current philosophy considers self modifying code to be a poor programming practice. However, in order to implement certain types of instructions, such as branching and indexing, some machines required code to be self modifying. (examples ?) A vestige of this programming style is the IBM System/370 Execute instruction [IBM80].

Because of the lack of hardware protection mechanisms and the necessity to have self modifying code, these early machines clearly do not fit into the object model. It is disturbing to note that many of the current microcomputers have similarities to these early machines, and lack protection mechanisms.

Protected Operating System model

Early protection mechanisms grew out of the desire to assist the user by providing I/O routines, compilers, and operating systems. The early operating systems assisted the user in loading and executing programs. The protection model was a simple one in which a processor status bit was used to distinguish between the user and the privileged (supervisor) mode. Primary (core) memory was divided into two regions: user and operating system. User programs could run in the user address space and execute most instructions. The operating system had control over both the user and operating system address spaces, plus the use of privileged instructions (I/O instructions, set CPU clock, etc.). While this simple mechanism protected the operating system and other resources (i.e. I/O devices) from malicious or accidental damage, many of the problems of an unprotected system still remained. A user program or the operating system could still modify its own code. However, an application program bug could accidentally destroy the program and user data during execution. An operating system bug could destroy portions of itself and/or the user address space. In addition, this simple protection mechanism was inadequate to support protection for multiprocessing.

Multiprocessing Systems model

Multiprocessing systems maintain the privileged mode mechanisms for the operating system, and additional hardware features are added to protect user processes from one another. One simple mechanism employed is the lock and key. Memory is divided into relatively small units, called pages or frames, and typically contain 512 to 4096 bytes each. Each memory unit is associated with several bits that comprised the lock. These bits are divided into two categories: several bits to match against the key, and several bits to describe access capabilities such as read, write and execute. In turn, the operating system assigns a key (typically 2-4 bits) to each user process by placing the key's value in the process' status word. When a user program tries to access a word in memory, the key is compared with the lock to see if they match. If so, processing continues as long as the access is consistent with the capabilities found in the lock. If the lock and key do not match, or an operation is attempted for which the process is not given the capability, a protection interrupt occurs.

There are numerous flaws in this protection model, including all of the shortcomings of the simple Protected Operating System model. Privileged mode is an exception to the lock and key protection mechanism. Whenever the operating system receives control, it is indiscriminately permitted access to all of storage, regardless of the lock values. Sharing of information between user processes is difficult because they have different lock and key values. A solution to the problem is to change the lock values of the shared memory units whenever the processor is allocated to a different user process. This method for protection and sharing of information is scarcely better than the Protected Operating System model.

The sharing problem can be solved by adding bits to the locks and keys. Multiple keys could be associated with each process, enabling the possibility that any of the desired sharing and protection schemes could be accommodated. However, for non-trivial mixtures of procedures, assignment of lock and key values becomes a difficult combinatorial problem which would consume large amounts of computing resources to solve. Non-static environments would be difficult to manage because the addition of a single new process could invalidate a protection scheme for a previously calculated distribution of locks and keys. Therefore, an allocation method would require a less then perfect protection regime to make the locks and keys practical [NEED72].

Many variations of the lock and key scheme have been used for protection and resource sharing. Paged virtual memory solves some of the problems, although other problems arise including naming (addressing) issues for shared resources [FABR74].

The three memory models just described fail to fit into the object model for several reasons. Each of these models is predicated upon large, word oriented, linear address spaces. If a program or process so chooses, it can divide its address space into smaller logical units, although there is rarely hardware support for small objects. Whenever a hardware or software interrupt occurs, the operating system (or the user program in the case of the Unprotected Machines model) receives control and has unrestricted control to all of the computing system resources. Large unprotected linear address spaces and unrestricted access to all of the computing system resources clearly violates the principal of least privilege..

Segment Machines

Burroughs

One of the earliest machines with hardware support for small memory objects (segments) and capabilities is the Burroughs B5000 [BURR61], B5700 and B6700 machines [ORGA73]. The Burroughs machines are designed to directly support the hierarchically organized block structured languages such as Algol. As such, they are well suited to accommodate the hierarchical scoping rules of the language while also providing hardware protection mechanisms and methods for sharing objects.

The B6700 is built specifically to use variable length segments for program code and data. Block structured languages specify that procedure definitions may be nested within other procedures, and the scoping rules for identifiers are organized in a hierarchical fashion. Each procedure, or block of code, is placed in a separate segment. Instead of a conventional instruction pointer, a set of registers is used, denoted by the tuple (ip,EP). The ip (instruction pointer) is used to reference the instruction in the current code segment while the EP (environment pointer) is a set of 32 pointers, called display registers, to the active data blocks. The ip is the register set (i,j,k) -- i is 0 or 1 to indicate whether the currently referenced code segment is in the stack trunk (system routines) or segment dictionary (active user routines); j is the offset in the stack trunk or segment dictionary where the base address of the current segment can be found; k is the offset of the instruction in the current segment. Display register D0 points to the stack trunk, and D1 points to the segment dictionary. Display registers D2 through D31 point to the suspended and active procedures' stack segments. A block of code may be invoked by the ENTER instruction, and execution always starts at the beginning of the block -- there is only one entry point per block.

For example, the main program starts and is referenced by D2. The program invokes procedure A, defined in the main program, and register D3 points to its block. Procedure B, defined in procedure A, is called and is referenced by D4. Procedure C is defined in the main program, and is called by procedure B. Information about the current block level (level 3) is pushed onto the stack, and D3 then is set to point to the block for procedure C. At this point, D2 points to the main procedure and D3 points to procedure C, so variables in procedure C and the main program are accessible. But, D4 becomes inaccessible because the machine knows that the program is running at block level 2. Variables in procedures A and B are inaccessible, and are protected from accidental or malicious use. It should be noted that all system functions begin running at block level 1 (D2), so the only variables accessible to the system functions are those passed as parameters.

Interrupts are handled in the same way as procedure calls. When an asynchronous interrupt is received, status information -- current block number and a backward chain reference -- is pushed onto the stack. A system procedure is called with two arguments indicating the source of the interrupt. The system interrupt handling routines conform to the same rules as user programs, so these routines operate in a restricted domain. When a synchronous interrupt is received (i.e. arithmetic overflow, invalid segment offset), the same mechanism is used. Unlike the previous protection models, the interrupt handling routines have a limited number of resources which they may manipulate, thereby reducing the chance of accidental damage to a user's application or the system. After the interrupt processing is completed, normal block exits (procedure returns) are performed and processing resumes.

Arrays are typically placed in segments separate from other variables because the hardware can automatically perform bounds checking on subscripts to ensure that illegal references are not made. A single dimension array allows immediate retrieval of data by using an (i,j) pair, where i is a segment number, and j is an offset into the segment. A two dimensional array is constructed by having the first array serve as an indirection vector to many single dimension arrays. The same method can be applied to higher dimension arrays. The advantage of this method is that protection and error detection is automatically provided by the hardware, and all of the segments need not be in memory at the same time. The disadvantage is the performance penalty of indirect addressing. This penalty can be alleviated by "linearizing" the array and forsaking subscript error detection and increasing the working set size.

All of the above functions are hardware supported via the use of tagged memory. Each word contains 51 bits, of which 48 are data, descriptor, or special control words, and a three bit encoded tag. Data words are single and double precision floating point numbers. Descriptor words distinguish code from data, indicate whether the segment is in memory, the segment's length, and its absolute address. Special control words include information placed in the stack for block activation and return, process scheduling, stack management, and indirect address referencing. Any attempt to perform an improper operation on a word, such as addition on a descriptor word, will result in a protection interrupt.

The Burroughs machines support many of the features that are desirable for the object model, yet it has several disadvantages. They support only a limited number of primitive data objects (floating point numbers), and all other types must be simulated. Simulating the other necessary data types increases the cost of using them. The hierarchical structure of the machine violates the principal of least privilege.. If a procedure or a program needs a specific privilege or data to perform its function, then all of its ancestors must have access to the privileges or data even though the ancestors may not need them. No mechanisms are provided for permanent (disk) storage of references to objects outside either the active program or the operating system. The only method for naming objects is through relative referencing via the segment dictionary. To be able to store references, the system would need to have a global naming mechanism whereby each object in the system has a unique name. The use of global names would eliminate the requirement of having a hierarchical system, but would increase the number of bits needed to address an object.

Cambridge CAP Computer

The Cambridge CAP Computer [NEED72] [WILK79] [HERB78] is another segment oriented machine that, unlike the Burroughs machines, uses non-hierarchical capability based addressing and protection. Each code segment has a capability list associated with it. As control passes from procedure to procedure, the list of capabilities, and therefore the protection domain, associated with the active process changes. If the calling procedure has the necessary capability for invoking the called procedure, the ENTER instruction transfers control to the new procedure and the machine's capability registers are completely changed. The called procedure has its own list of capabilities which may be completely different from the caller's. Because there is no hierarchical dependency for obtaining capabilities, no distinction is needed between user programs and operating system procedures. This lack of distinction is sometimes referred to as an open operating system [LAMP73].

Access to segments is made via several levels of indirection. The system has a Master Resource List (MRL) containing the absolute address of all segments in memory. Each process has a Process Resource List (PRL) containing references to the MRL for all segments which are addressable by the process. Each program reference to a segment contains three elements: the number of the PRL, the entry number in the PRL to use (segment number), and the segment offset. Each memory reference is handled by the capability unit which uses the address to locate a capability, perform segment bounds checking and access rights validation.

The CAP computer has the same advantages as the Burroughs machines, but privileges and data need not be organized hierarchically. However, the CAP design does have have several drawbacks because of some specific aspects of its implementation. Due to the hierarchical naming structure, sharing of procedure segments requires that procedure capabilities be passed along hierarchically. The system is also designed to minimize the amount of work it does for garbage collection. Within a process, capabilities may be freely copied because the reference counting mechanism for garbage collection is only concerned with the number of processes referencing a segment -- when a process is destroyed, all references to an object within a process are destroyed. Passing capabilities between processes is harder because the bookkeeping becomes more complex. Retraction of capabilities is also difficult because there is no central authority to track their dissemination, and segment numbers are reused. Therefore, the owner of an object can not retract capabilities, nor destroy the object as long as there is an outstanding reference to the object. If an object is destroyed which has an outstanding reference to it, an unintended reference to a new object with the same segment number can cause disastrous results. Procedure call argument validation is problematic because the addressed object must be accessible by the called procedure, even though it may not be accessible by the caller. Passing data structures which span multiple segments may not be feasible, especially if the called procedure does not have all of the capabilities for the segments referenced by the data structures. CAP does not have tagged memory, so separate segments are necessary to isolate data from capabilities. Finally, no mechanisms are provided to seal and unseal3 abstract data type objects.

Multics

The Multics system [SCHR72] [ORGA72] is another architecture based upon the use of segments and descriptors. The descriptors forming the process' capabilities are maintained in an array called the descriptor segment. Each physical processor in a Multics machine contains the absolute address of the descriptor segment in the descriptor base register (DBR). A program memory reference, of the form (segment,offset) is translated into an absolute address by using the segment number as an index into the descriptor segment. The offset is added to the absolute address portion of the capability, yielding an absolute address of the data object. To attach a segment to a process, the supervisor checks the access control lists associated with each segment to see if the user is authorized to use the segment, and the capabilities that the user is to receive for the segment.

Protection in Multics is organized hierarchically in rings, sometimes referred to as spheres of protection [DENN66]. In Multics, there are eight rings with the lowest numbered ring accorded the greatest number of rights. Thus, each successively higher numbered ring is granted fewer rights. Each capability in the descriptor segment contains fields called brackets that indicate the highest ring number (upper bound) for which a segment capability (i.e. read, write, execute privileges) is granted. For example, read and write capabilities may be granted for procedures at level 0-3, while procedures at levels 4-5 are restricted to read-only use, and levels 7-8 are denied access. A flag in the descriptor can be set to deny all ring levels a particular access right. For example, if a shared segment has the flags set for both the read and write privileges, the segment is execute mode only, regardless of the ring number. Execute access may also be upper bounded by the bracket number.

The protection problems in the Multics system are primarily due to its hierarchical protection structure. Upward transfers of control to higher ring numbers can only decrease capabilities, so no restrictions are necessary. However, argument validation becomes a problem if the called procedure is at a higher ring number, and the arguments become inaccessible. Either hardware or software is needed to ensure that the arguments will be accessible. Software assistance is required to ensure proper protection when the ring number is reset following a return from a higher numbered ring to a lower numbered ring. Precautions are necessary so that a returning procedure does not give its caller a lower ring number than when the caller made the original call. Downward transfers of control (to a lower ring number) requires explicit privilege in the called procedure's descriptor. The descriptor contains the highest ring number that the calling procedure may have to be able to call the lower ring numbered procedure. This mechanism acts as a restriction for limiting access to privileged procedures. The lower ring number remains in effect until the procedure either calls a procedure at a different ring number, or it returns to its caller. Because of the limited number of rings and the hierarchical protection mechanism, almost all procedures will be over privileged. This violates the principal of least privilege.. Also, no mechanisms are provided for sealing and unsealing objects.

The use of descriptors in Multics leads to the problem of retracting capabilities. Immediate retraction of a capability requires maintenance of lists of pointers to descriptors allocated to processes. In fact, this method is used. The lists could be eliminated if a look-up is performed on a single list to verify a process's right to access a resource each time it is used. This concept, described by Dennis and Van Horn [DENN66], is called capability lists, or c-lists.

Hydra

One of the objectives of the Hydra system [WULF75] [WULF74] is to provide protection mechanisms that are separate from the protection policies [LEVI75]. The mechanisms are provided permit any number of protection policies to be implemented by writing different policy modules [JONE73]. As in the CAP system, segment capabilities are organized in a non-hierarchical fashion, and use global addresses in descriptor segments like Multics. These two aspects eliminate many of the protection problems associated with the Burroughs, CAP and Multics computers. Hydra provides a rich set of primitive types, including procedures, processes, semaphore, and abstract data types with their associated procedures to manipulate them. The capabilities for a data type include generic operations (i.e., read, write) which can be applied to all types, and auxiliary rights which are type dependent. All objects are 2-tuples of the form where the two parts are maintained in separate segments.4 The representation of an object is hidden (sealed), through the use of capabilities, so that only a limited number of modules are permitted to manipulate each type. To extract from or store into an object, a procedure calls one of these modules, passing a capability for the object. The module uses rights amplification [JONE73] to enable access to (unseal) the internal representation of the object.

The protection domain of a procedure is defined by its c-list and the arguments passed to it. If one of its capabilities is to access another object, then

the actual protection domain extends to all objects reachable via some capability path rooted in the [procedure]. Access to such objects is limited though, by the rights in the capabilities along the path.5
Therefore, an object is accessible if there is a sequence of c-list entries leading from the instantiation of the procedure to the object.

When an procedure is called, the rights passed by the caller and a template defined by the procedure are used to determine the set of rights an instantiation of the procedure will have. Each formal argument in a procedure has a template specifing the object type and/or the necessary rights (i.e., read, write, execute) an object must have when it is passed as an argument in a procedure call. If the type is incorrect, or the rights passed are insufficient, the procedure is not entered, and an error is returned to the caller; otherwise, sealed objects are unsealed through rights amplification and the procedure is executed.

When a call is made, the status of the calling procedure, including references to its c-list and protection domain, are pushed onto the stack. Returning from a procedure call pops the caller's status off the stack and restores the protection domain. The stack is a protected object, so when a procedure returns control to its caller, the protection domain is correctly restored.

Hydra provides a solution for the mutual suspicion problem.6 The called routine can be restricted to only the objects passed as parameters because capabilities are not necessarily inherited from the caller. The called procedure can protect private objects by sealing them with capabilities.

Copying of capabilities can be controlled through a copying right. Each capability has a flag indicating whether the procedure is allowed to copy the capability. If not, the procedure is unable to retain the capability for later use, or pass it along to another procedure or user. Selective revocation can be performed by passing a capability to an alias for the object. If permission is to be revoked, removing the alias breaks the path to the object without destroying the object. Removing the alias only revokes the privileges of those processes using the alias to access the object. Processes with a capability for the object itself, or a different alias, for the same object are not affected. However, immediate revocation can lead to the disruption of a process. If a process is disrupted while updating an object, the invariant of other objects may not be true when the procedure is exits. To prevent disruption, freezing is used so that its contents can no longer be modified. Freezing allows the procedure to clean up gracefully by restoring the invariant properties of other objects it was manipulating.

Hydra does have several disadvantages. Domain switching is very expensive due to its lack of special hardware for handling capabilities. Therefore, objects tend to be large so domain switching overhead is not excessive. All functions requiring the use of capabilities must be done by the kernel, including searching for an object being referenced in a data structure. Loading and storing data in objects referenced by capabilities must be done by the kernel, as well as creating and copying objects. If hardware were available, the performance of Hydra would most likely improve and objects could be much smaller.

IBM System/38

The principles behind the IBM System/38 [DAHL78] [PINN78] [BERS78] [HOFF78] [HOUD81] are for the most part the same as Hydra. The most significant difference between these two systems is that the System/38 implements the handling of capabilities in hardware. Primitive objects include process objects, abstract I/O devices, and communication ports between processes. The microcode provides a high level programming interface to the programmer and masks any hardware dependencies. The microcode also provides generic computation instructions, such as addition and subtraction. All necessary conversions between data types and data of varying lengths are performed automatically. Primitive objects may be aggregated to form sealed objects, and operators may be defined to manipulate the representation of these objects. New objects are created and initialized by the microcode.

The IBM System/38 uses tagged memory with 32 bit words plus a flag bit to indicate whether or not the word is a pointer, and a 7 bit error correction code (ECC). The pointer flag may be manipulated only by the hardware. Any improper manipulation of a pointer will turn off the flag and subsequent attempts to use the word as a pointer will result in an error condition. Objects are referenced by 64 bit descriptors, of which 32 bits are used for defining the global name of an object in a single level store. In a single level store, every object both in primary memory and secondary memory is accessible through the use of a unique global name. The processor or operating system performs automatic management of primary and secondary storage. Running processes are given the illusion that all objects are always available in primary memory. Whenever a process references an object not in primary memory, the object is automatically retrieved from secondary storage, and this retrieval process is transparent to the running process.

Each process has a "user profile"7 which defines its protection domain. The protection domain can be changed by invoking a procedure which operates under a different user profile. When a procedure is invoked, it can pass capabilities for an object, and rights may be restricted as well.

Active objects in the system, such as processes, the scheduler in the microcode and I/O devices, can communicate by sending messages via ports. The message passing mechanism and the use of a high level interface enables hardware and software resources to remain relatively implementation independent.8 Another advantage of message passing is that the system is queue driven so commands to system resources can be "stacked".

The System/38 provides a rich set of primitive operations. Implicit and explicit locking of objects is provided. A large number of database manipulation operators, such as file sharing, record format definition and mapping with access mechanisms, updating, addition and deletions are implemented in microcode [DAHL78].

Some of the drawbacks of the System/38 are that there is no automatic garbage collection, and the programming languages for the machine are not "object oriented". Rather, the software provided is oriented towards the business community which uses FORTRAN and COBOL.

Intel 432

The Intel 432 [ZEIG81] [RATT80] has the same basic philosophy as the IBM System/38.. The Intel 432 uses a high level programming interface, protection domains and sealed objects. Like Hydra, context activation objects are pushed onto the stack when a procedure call is made, and popped off upon returning thereby restoring the protection domain. Message passing is used for interprocess communication, scheduling policies, I/O devices and other processor resources, in a manner similar to the System/38.. If a process requests to be scheduled for execution in a multiprocessor configuration, the microcode schedules the process for the next available processor -- known as transparent multiprocessing [ZEIG81]. No changes need be made to the software, even if processing units are added. Unlike the System/38., the Intel 432 implementers chose not to place all of the system provided functions in the hardware, such as database management.

Sward

Sward, a descendant of Hydra and IBM System/38., contains some of the best features of its ancestors [MYER80]. Sward is a capability based machine, organized as a single level store using unique 88 bit capabilities in a tagged memory architecture. Each capability contains a 4 bit tag, a 4 bit access code and an 80 bit unique system-wide logical address. The access bits are rights for read, write and destroy privileges. The last bit indicates whether a datum is undefined, or a capability may be copied -- the two uses of a word (addressing and data) are mutually exclusive. Capabilities may be passed from procedure to procedure. A unique solution to the retraction problem introduced in Sward is an operation called CHANGE-LOGICAL-ADDRESS which changes the address rather than copying the object and destroying the original. There are five basic object types: modules, data, ports (abstract devices), activation records, and virtual processors. Procedure calls are hierarchical, with pushing of activation records onto the stack and popping them off on return. Error handling is controlled through hierarchical error recover; that is, errors in a procedure may be trapped by one of the calling procedures.

The major emphasis of Sward is to "install barriers to minimize the effects of software errors, but the primary emphasis is on semantic checking during program execution."9 This goal is achieved through using a capability based architecture, high level instructions, and message passing.

Some notable drawbacks in the design should be noted. No mechanisms are provided to seal objects. Any procedure given a capability for a data object may erroneously or maliciously manipulate its contents without knowing the representation of the object. Objects may be either implicitly or explicitly destroyed. Implicit destruction of an object is automatically performed by the system when there are no more references to the object. When an object is not marked for implicit destruction, the "owner" must explicitly destroy the object. If all references to an object are subsequently lost, the object becomes inaccessible, and remains permanently inaccessible due to the garbage collection mechanism used.

Smalltalk-80

Smalltalk-80 is a single user virtual machine predicated on the use of sealed objects [KRAS81]. The virtual machine is a program10 containing storage management routines, an instruction interpreter, and subroutines to perform primitive operations. Storage for objects is allocated and managed by the virtual machine.'s storage management routines, and are referenced by 15 bit system-wide identifiers. Objects remain sealed because the virtual machine interpreter inspects the type of the object, finds the methods11 permitted to manipulate the object, and determines which, if any, of the methods is to be invoked. If an object does not recognize a message sent to it, then the requested operation fails and the caller is notified.

The Smalltalk-80 virtual machine contains a primary pointer to the current (active) context. This pointer references an object called the MethodContext (procedure activation record) with nine fields. The first two fields are the object length, and the object type (MethodContext). The remaining seven fields are pointers (or indexes) to other objects needed during execution of a method:
Receiver The object to be manipulated by the active method.
Stack An object to be used as the local stack.
Stack Pointer The current position (index) in the stack.
Method An object containing the method bytecodes (machine instructions), literals, and other information necessary to manipulate an object of the class.12
Current Bytecode The current position (index) in the list of the method bytecodes.
Temporaries An object containing temporary local variables used by the method.
Caller A pointer to the MethodContext (procedure activation record) of the calling method.

The only information a method has at its disposal is restricted to the arguments it receives, any global variables associated with the object's class, and resources global to all Smalltalk-80 processes.

Smalltalk-80 contains a rich set of primitive object types because everything within Smalltalk-80 is an object and is treated as such. Primitives include a variety of integers types, floating point numbers, fractions, arrays, characters, strings, pointers, process management, semaphores, and boolean objects. These objects are directly manipulated by the interpreter. All other objects, including MethodContexts, are constructed from these primitives.

Smalltalk-80 takes two approaches to the management of resources. Some resources are under the complete control of the virtual machine., such as memory management. Methods and the interpreter are allowed to request that objects be created and accessed, but garbage collection and management of the objects' locations are inaccessible. Memory can be considered a sealed object. Other resources, such as process scheduling and I/O scheduling, have their mechanisms built into the virtual machine., but interfaces are provided to allow policies to be implemented and changed by the user. This separation of policy from mechanisms is similar to the approach taken by Hydra.

The main advantages of Smalltalk-80 is its use of sealed objects and program semantics. While these do not provide sufficient protection mechanisms, one can argue that Smalltalk-80 is a single user environment and many of the protection mechanisms are not necessary. There is also a lack of mechanisms for restricting access to global resources and the retraction of capabilities. The problem of mutually suspicious programs is partially solved by the use of message passing which is call-by-value rather than call-by-reference. If used properly,13 message passing can solve the mutual suspicion problem because invocation of a method can not modify the arguments.

Hardware and Systems - Discussion

The discussion about hardware to support the object model has primarily dealt with protection mechanisms and how these mechanisms support the principal of least privilege.. The first three memory models do not provide adequate mechanisms to support small data objects. The privileged mode of operation bypasses all security because it indiscriminately permits access to all system resources. The lock and key mechanism is not able to support arbitrary forms of sharing due to the limitations on the number of bits in the keys. Addressing and naming problems associated with the sharing in paged virtual memory systems compound the complexity of using the lock and key mechanism. Thus, these mechanisms do not provide adequate protection and methods for sharing of information.

Machines using segmented memory solve some of the protection problems. Segments are defined to be the same size as the objects themselves. Attempts to access memory outside the bounds of a segment are impossible. In addition, rights or privileges are given to a process, thereby defining the ways in which the process may use the object. The object's type (i.e., program or data) may define the permissible operations.

A major issue when using segmented memory is how are rights to be associated with processes and procedures. One approach is to have a hierarchical structure whereby some levels of the hierarchy have greater rights and privileges, or have access to global data. Use of a hierarchy in this way violates the principal of least privilege because some procedures and/or processes have rights and privileges which they do not need or should not have. A non-hierarchical approach is to assign a set of capabilities to each procedure or module. When a procedure is called, additional rights and capabilities may be passed. The procedure is able to determine, through the use of templates, whether or not it has the necessary capabilities to perform its function. Rights amplification allows the procedure to unseal objects. Access to an object's representation is restricted to those procedures which define the abstract object and its manipulation. The non-hierarchical method approaches the practical limit of achieving the principal of least privilege because only the capabilities necessary to perform the requested operation are passed to the procedure instantiations.

Mechanisms must be available to pass and restrict rights and capabilities between procedures and processes. The simplest method is to pass them as arguments in procedure calls. However, indiscriminate dissemination of rights and capabilities violates security policies and the principal of least privilege.. Therefore, the caller must have the ability to restrict the ways in which the object may be manipulated, and may also be able to indicate that the capability may not be copied or saved. Prohibiting the copying of a capability restricts the flow of information, and is a partial solution to the confinement problem.

The retraction problem can be solved through several mechanisms. Lists can be maintained of all disseminated capabilities. Lists are most practical when descriptors are maintained in segments separate from other data and require the system kernel to transfer rights to other procedures and processes. Aliasing is another mechanism which permits flexibility in selective revocation. The alias can be deleted without affecting the original object or the object's other aliases. Another approach is to change the name of the object so all references to the original name become invalid. If name changing is not available, the object can be copied and the original deleted. An alternative to retraction is freezing, whereby any further modification of an object are prohibited, but the procedure or process is still permitted to use the object's other capabilities.

Two divergent trends are developing in computer hardware. One trend is to develop high level programming interfaces which hide the resource interfaces for I/O devices, memory, and processors.14 The other trend is to build very fast and simple processors (RISC15 machines), and use compilers to hide the details of the machine. Smalltalk-80 is a virtual machine written as a program which could be implemented on such a processor. It appears that both approaches are being taken in the development of these systems. At this time, there appears to be no clear advantage for either approach.

Programming Languages

The programming language.s examined in this section fall into two categories. The procedure-oriented languages are those with which most people are familiar. A typical program in a procedure-oriented language consists of a main program and possibly calls to subprograms - procedures and functions. Data is shared by subprograms through several techniques, including passing parameters in the subprogram invocation. The basic view is that there is data, and procedures which manipulate data.

The other type of programming language.s is the object-oriented, message-passing languages which view data as contained objects. Each object contains the information, its representation, and defines the types of manipulation that may be performed upon the object. The implication is that objects are strongly typed, regardless of whether or not the object's identifiers have a type. The identifiers are merely temporal means for accessing an object. To perform an operation upon an object, a message which specifies the manipulation and operands is sent to the object, not to a procedure. The object determines whether or not it recognizes the message type. If it does, the operation is performed, and an object may be returned. If the message is not recognized, the sender is informed.

Each object is an instance of a type, frequently referred to as a class16 [BIRT66]. The class defines the instance variables, methods17 which manipulate an object, and the temporary variables which are used by instantiations of a method. Some object-oriented language.s permit the declaration of class variables which are shared by objects of the class in which they are defined.

Inheritance is an important concept in object-oriented language.s. A class may specify that it inherits properties from one or more other classes. The properties include methods, class and instance variables. Multiple inheritance, or the ability to inherit properties from two or more classes and its semantics, is an area of current research.

The programming language.s discussed herein fall into one or both of the categories. Modula-2 and Ada, while both procedure-oriented languages, contain syntax and semantics which are similar to message passing. Thus, there is no distinct dichotomy.

Procedure-Oriented Languages

FORTRAN

FORTRAN provides an interesting and important historical reference when discussing the object-model. Its origins date to the mid-1950's when high level languages were not in wide use. FORTRAN is the first high level language to become widely used. A goal of the language is to provide a mapping of the statements into an efficient run-time representation. Because of this, the syntax and semantics of the language are constrained, and the run-time environment is machine dependent. Code, scalar and array variables are all defined and bound at compile-time, so the run-time structure is fixed. There are no run-time storage management mechanisms. The only parts of a FORTRAN program that vary during execution are the scalars and array variables.

A program consists of a main program, and may call upon functions and procedures. All variables are either implicitly or explicitly declared with a type. Information is passed between the subprograms by either parameters or COMMON blocks. Variables local to subprograms18 retain their values between invocations, similar to PL/1 static variables or ALGOL-60 own variables. Arguments passed in subprogram calls are call-by-reference.

COMMON blocks are a means for sharing storage between two or more subprograms. Variables in the COMMON blocks are mapped directly to memory locations and no type checking is done between subprograms. The mapping of a variable to a particular location in one program need not be the same type as a variable mapped to the same location in a different subprogram. This mechanism provides a quick method for reusing storage, performing type conversion, and aliasing. The EQUIVALENCE statement provides the same storage sharing mechanism as the COMMON block, but does so for variables in the same subprogram.

FORTRAN provides the primitive data types integer, real, double precision, complex and logical (boolean), which typically map directly into their machine representations. Characters and strings are defined by Hollerith constants which may be stored in any of the primitive data types. Arrays of any of the primitive types may be defined with up to three dimensions. Run-time array descriptors are not used; there is no bounds checking. By definition, arrays are stored in column major order. This knowledge is important when creating aliases via EQUIVALENCE or COMMON declarations.

FORTRAN represents an early attempt at creating a language which provides abstraction mechanisms above the machine assembly language level. Subprograms, primitive data types, iteration statement, conditional statements and other constructs provide a means for constructing large systems. Without a doubt, FORTRAN has been a success.

Yet, FORTRAN violates many of the principles of the object model. The lack of type checking on subprogram calls can lead to unexpected and incorrect results. COMMON blocks and EQUIVALENCEs do not enforce type checking. Sharing may be defined in arbitrary ways, so unexpected side effects may occur. To create complex methods of sharing information, the user must be aware of how the compiler allocates storage. The use of COMMON blocks violates the principle of least privilege because any subprogram has access to all information defined in the block. Information stored in a COMMON block may inadvertently or deliberately be modified or destroyed. There are no mechanisms for protecting these shared memory locations. Call-by-reference always permits the called subprogram to modify a caller's variable. Some versions of FORTRAN have call-by-value which prevents such side effects.

FORTRAN is limited to five primitive data types and subprogram calls; no means are provided for creating abstract data types or structuring data into objects other than arrays. Hence, FORTRAN is very limited in the types of abstraction which it can directly support. The language is described here because of its historical significance, but clearly does not fit into the object model because it is weak in both protection and abstraction mechanisms.

ALGOL-60

ALGOL-60 is another historically important language because it is the first block-structured language. The block structure defines the scoping rules for identifiers. Another unique feature of the language is its use of call-by-name. ALGOL-60 supports three data types: real, integer, and boolean. Data type conversion is done implicitly either at compile-time or run-time. Once an identifier is declared within a block, it may be referenced by statements in the block and statements contained in nested blocks. Blocks may be nested hierarchically within existing blocks. Naming is defined hierarchically and the search for binding a name to an object beings at the symbol table for the current block and will recursively search the tables of each of its surrounding blocks. The search is terminated when the first occurrence of the identifier is found.

Subprograms must be declared before they are used. When a subprogram is called, an activation record is created for the block containing the subprogram. By default, storage is dynamically allocated on each invocation and released at block termination. This prevents residual values of previous invocations from being used. The exception is own variables which allow a subprogram to have space statically allocated for variables which are to remain intact between invocations.

ALGOL-60 is important because of its strong influence on language design. Its hierarchical block structure has interesting properties which can be exploited by a programmer. Within a block, all identifiers declared in the block or its surrounding blocks are accessible. In a block, an identifier that is defined in an outer block may be redefined by declaring it as a local identifier. This protects the identifier in the outer blocks from inadvertent misuse or destruction. But, it has the disadvantage that the identifier in the outer block becomes completely inaccessible for further use until the block which redefined the identifier exits. Call-by-name can have unexpected results if the identifier has been redefined and is no longer the desired target of the operation.

From the point of view of the principal of least privilege., hierarchical naming permits access to more information than is necessary. Because of the ability to access identifiers in outer blocks, subprograms and blocks of code are able to cause unexpected side effects. Statement labels have the same scoping rules as variable identifiers. A GOTO statement can cause a transfer of control out of a block, or out of a subprogram. Proving the correctness of programs which use GOTOs is difficult.

Hierarchically organized systems do not adequately protect information because sharing must be done through the hierarchy. Many procedures and functions must be over-privileged in order to pass information or capabilities. The outer blocks have access to all information needed by the inner blocks, which could lead to side effects.

ALGOL-60 provides roughly the same abstraction mechanisms as FORTRAN.. In addition, arrays may be allocated at run-time by parameterizing the upper and lower bounds, although the number of dimensions is fixed. Variables are limited to integer, real and boolean types. No mechanisms are provided to create abstract data types or records.

Pascal and Modula-2

Pascal and Modula-2 [JENS74] [WIRT83] are descendents of ALGOL-60 and block structured languages. For purposes of this discussion, Modula-2 will be considered a superset of Pascal, so attention will be focused on Modula-2. These languages are procedure oriented and contain a rich set of data types which may be combined to form new types. The language also contains provisions for separate module compilation and mechanisms to hide information within modules.

Modula-2 is a language which hides most of the hardware dependencies from the programmer. The primitive data types include INTEGER, CARDINAL, REAL, CHAR, which have the usual meanings.19 Enumeration, SET, subrange, ARRAY, RECORD, POINTER, and PROCEDURE types are extensions of the TYPE construct. Constant declarations plus the primitive and type extensions permit a wide range of objects to be created.20

The declaration of subprograms is very similar to ALGOL-60.. Procedures and functions may be declared within subprograms. Pascal and Modula-2 require that constants, variables, types, and subprograms be declared before the first block of code in the main program or subprogram. Therefore, variables may not be declared local to a nested block. In most other respects, the scoping rules for identifiers remain the same.

The MODULE construct is a means for providing abstract data types and functions.21 Each MODULE consists of 2 declarations; the definition part and the implementation part. The definition part consists of: a list of imported items which are identifiers found in other MODULEs; the list of exported items which are identifiers that are made visible outside the scope of the MODULE; and a list of declarations which are identified or used by the items listed in the export list (See Modula-2 - Definition Module).


Figure: Modula-2 - Definition Module

DEFINITION MODULE identifier;
< import-list >
< export-list >
< declarations >
END identifier.

The DEFINITION MODULE with the import and export lists form a library of programs and procedures. The optional import list is of the form

FROM name IMPORT identifiers.
The name is a MODULE from which the identifiers and their attributes are to be retrieved. The export list is required and has the form
EXPORT <QUALIFIED> identifiers.
The identifiers list indicates the declarations which may be imported by other MODULEs. Only those in the list are made public. The remainder of the identifiers in the module are private and are used by the module implementation. The QUALIFIED part is optional. If it is not included, only the MODULE may be imported. When an entire MODULE is imported, all of the identifiers in the export list are imported.

The MODULE construct can be used in a variety of ways. Constants, variables and data structures can be defined in a MODULE so they can be shared among many other modules. Protected procedures can be written so that only the external interface will be available, and not the representation of its data structures. Abstract data types can be created by exporting the type and operations on the type. The representation and implementation details remain hidden in the MODULE. Objects created using abstract data types are protected and may not be manipulated by procedures and operations other than those defined in the types' MODULE.

The IMPLEMENTATION MODULE consists of the MODULE name, an optional import list, declarations, and subprograms that comprise the MODULE (See Modula-2 - Implementation Module).


Figure: Modula-2 - Implementation Module
<IMPLEMENTATION> MODULE identifier;
< import-list >
< declarations  and subprograms >
END identifier.

MODULEs may be declared within other MODULEs, and are called LOCAL MODULEs. They are similar in most respects to subprograms. The primary difference is in the scoping rules for identifiers. An identifier may be access after the end of a MODULE if it is passed in the MODULE's export list. Also, any identifiers accessible in the block surrounding the MODULE's definition are not accessible inside the MODULE unless the MODULE explicitly imports them (See Modula-2 - Local Modules22).


Figure: Modula-2 - Local Modules
MODULE W;
   VAR a:CARDINAL;

   MODULE X;
      EXPORT b;
      VAR b:CARDINAL;
      (* only b is visible here *)
   END X;

   MODULE Y;
      EXPORT c;
      VAR c:CARDINAL;
      (* only c is visible here *)
   END Y;

   MODULE Z;
      IMPORT b,c;
      (* b,c visible here *)
   END Z;

   (* a,b,c visible here *)
END W

Because of its block structured architecture, Pascal and Modula-2 suffers from the same hierarchical naming and sharing mechanisms as ALGOL-60.. Particularly in Pascal, there is little protection of information because all information must be passed via hierarchically defined structures. In Modula-2, the MODULE construct permits non-hierarchical methods of sharing information. But, one drawback is that shared variables and data structures can not be explicitly write protected. Procedures which share these objects may accidentally or deliberately modify them, causing unexpected side effects. A major problem area is dangling references. The crux of the problem is due to the user being responsible for managing dynamically allocated objects using the NEW and DISPOSE functions. References may remain to objects which no longer exist.

Pascal and Modula-2 contain many constructs which are invaluable abstraction aids. The languages define an adequate set of primitive types. A large number of extensions to the primitive types permit an unbounded number of object representations to be constructed. Both primitive types and defined abstract types can be allocated statically at compile-time, or dynamically at run-time. This permits great flexibility in creating and maintaining complex data structures.

Modula-2 permits subprograms to have arrays declared with upper bounds unspecified at compile-time. At run-time, the parameters passed to the subprogram can be used to define the number of elements in the array. This permits subprograms to be defined in such a way that the parameters can define the representation at run-time rather than being predefined and fixed.

The MODULE construct facilitates sharing and protection. MODULEs can specify shared constants, variables, data structures, and protected abstract data types with their operations. The protection and abstraction mechanisms are the features which are the most desirable with respect to the object model. Although Pascal and Modula-2 have their faults, and there are means for subverting the protection and abstraction mechanisms, these languages are an improvement over their predecessors.

Object-Oriented Languages

Smalltalk-80

Smalltalk-80 [XERO81] [GOLD83] is an object-oriented language based upon the use of message passing. Each expression that is evaluated results in a message being sent to a receiver. The receiver is an object which evaluates the message selector to determine whether or not there is a method to evaluate the expression. Messages fall into three categories: unary, binary, and keyword. Unary messages consist of a single selector without any arguments. A binary message contains a selector and a single argument, which is also an object. Keyword messages have one or more keywords, each of which are terminated with a colon and are followed by an argument.23 Message passing is call-by-value, thus limiting the possibility of causing side effects. An object passed as an argument remains unevaluated until the method decides to evaluate it, or passes it as an argument to another object.

When a message is sent to an object, the Smalltalk-80 virtual machine finds the object's class and uses the selector to locate the appropriate method. If the method is not found, the class' superclass24 is searched for the method. Superclasses are recursively search until the method is found and executed, or the search terminates in the class called Class25 and an error is returned to the caller.

A number of primitive data types, or classes, are built into the virtual machine interpreter. Numeric objects include floating point, fractions, and integers of several different formats. The virtual machine automatically performs conversion between these formats when necessary. Primitive classes also exist for boolean, characters, arrays, pointers, processes, and semaphores. The class Collection contains Bag, Set, OrderedCollection, LinkedLists, MappedCollection, SortedCollection, and IndexedCollection. A subclass of Set is Dictionary which is a set of Associations. String and Array are both subclasses of IndexedCollection. In turn, Symbol (individual characters) are a subclass of String. Arrays are an indexed collection of non-homogeneous objects, which sharply contrasts with non-object-oriented language.s where each and every element of an array must be of the same type. Other notable classes are Object, Class, Message, CompiledMethod, and Context. The class Context contains two subclasses - BlockContext and MethodContext. Instances of these last two classes represent instances of active objects. A block is a piece of code within a method, such as the code in a loop. Blocks may be passes as arguments in expressions, or stored and referenced by other objects such as arrays.26

One aspect of Smalltalk-80., and similar languages, is that an object's class determines how a selector is to be interpreted. The binary messages +, -, *, and / may take on different meanings depending upon the class of the receiver. The selector + will invoke different methods if applied to object of different classes. It can be used to add integers, or to perform union of sets. The interpretation is strictly up to the method for an object. Conventions for commonly used selectors (i.e., +,-,*,/), permit abstract operations to be performed upon objects of many different classes.

Abstraction is a fundamental part of Smalltalk-80.. New types are created through the aggregation of existing types. A new class defines a set of instance variables and methods which form the representation and implementation for the new data type. An object is a sealed entity whose representation is accessible only by the methods of the object's class. Therefore, instance variables reference objects created and manipulated by the existing methods in their respective classes. Lazy evaluation of the message arguments permits the method to define its own interpretation. Because the identifiers are not statically typed, the compiler is unable to anticipate the actual values(s) that the receiver's method will need. It is quite possible that each time an expression is invoked, the class of the receiver is different and needs to send a message to a method in a different class. The use of lazy evaluation enhances the language's ability to provide abstract operations on objects over a wide range of classes.

Smalltalk-80 provides many primitive objects and classes, and the system contains many others which form a rich set of data types. All of the types and type extensions of Modula-2 are in Smalltalk-80.. Sets, arrays and pointers are available. Subranges and records are easily created, while procedure types are replaced by Blocks. Enumeration can be defined as a Collection, and numeric subranges are represented as instances of the class Interval. Records are instances of a class where subfields are represented by the instance variables. An object's methods determine which instance variables are accessible outside the class, and what information can be derived from the instance variables. This approach for the creation of records is much more abstract than in languages such as Pascal and Modula-2 because the methods can always return the same values regardless of the representation of the object, whereas a record is a static structure which directly associates storage with subfields. Record subfields can not be changed to call a function if the data structure's representation is to be modified.

Smalltalk-80 provides abstract iteration constructs for objects which belong to a subclass of Collection.27 The first example in Smalltalk-80 - Iteration Statement Examples checks each book in the object books to see if it is fiction. The block counts the number of fiction books in the object books. The second example creates a new object fictionBooks which only contains the fiction books in object books. It is not necessary to know the class of books as long as it is a subclass of Collection. The iterator keywords and arguments are:


Figure: Smalltalk-80 - Iteration Statement Examples
The iterator variable is each. The expression each isFiction returns a boolean object. For each book in books, if it is fiction, one is added to numberOfFiction. Create a new object fictionBooks by selecting each book that is fiction from the object books.
books do: [:each | each isFiction
                     ifTrue: [numberOfFiction <--
                                 numberOfFiction + 1]]

fictionBooks <-- books select: [:each | each isFiction]

D
Find the first element for which aBlock returns True. If none, execute the exceptionBlock.
do: aBlock Evaluate aBlock for each element in the receiver.
select: aBlock Create a new collection containing all elements in the receiver for which aBlock returns True.
reject: aBlock Create a new collection containing all elements in the receiver for which aBlock returns False.
collect: aBlock A new collection of objects returned from aBlock.
detect: aBlock ifNone: exceptionBlock
These iterator constructs provide very powerful and useful tools. Because they are not type specific, they can be applied to a wide range of objects regardless of their representation.

Enumeration constructs in the class Interval are defined for numbers. Interval is a subclass of SequencableCollection and is a Collection. The keywords and arguments are:
from: firstInteger to lastInteger Creates an instance of Interval which contains the sequence from firstInteger to lastInteger, by increments of one.
from: firstInteger to: lastInteger by: stepValue Creates an instance of Interval which contains the sequence from firstInteger to lastInteger, by increments of stepValue.
firstInteger to: lastInteger Same as the first case.
firstInteger to: lastInteger by: stepValue Same as the second case.
Interval objects can be used to create the equivalent of a for loop. The statement

(10 to: 100) do: [:i | statements].
will cause the iteration block to execute with i taking on the values {10,11,12,...,100} in succession. Intervals complement the iteration constructs, and can be used to define numeric subranges.

Everything in Smalltalk-80 is oriented around objects. Process management, the user interface, I/O devices, and data are all objects, and uniformly use the message passing constructs. This orthogonal design simplifies the use of objects in the system and the design of new software.

Protection mechanisms are minimal. Smalltalk-80 is designed as a single user multiprocessing system. Objects form the basic protection mechanism because they are sealed entities. Processes can not interfere with one another, unless they share resources, or they manipulate process scheduling. Problems arise when using shared class or global variables. The system provides synchronization mechanisms, although their use is not enforced. The class structure is defined hierarchically. A method has access to all class variables and instance variables in its class and superclasses, regardless of its needs. The same is true of the methods. The only mechanism for blocking the use of methods in superclasses is to define a method in the class which responds to the offending message and takes appropriate action (i.e., issues an error message). A more desirable approach would be to define those methods and variables in the superclasses which are applicable, and to make the others inaccessible. This restriction would satisfy the principal of least privilege.. Because Smalltalk-80 is a single user system, all classes are available to all processes. There are no access restrictions because they are deemed unnecessary for a single user environment. If Smalltalk-80 is to become part of a multi-user or distributed computing environment, this issue will need to be addressed.

Flavors

Flavors is a message passing, object-oriented construct first implemented for the Lisp Machine [WEIN80] and subsequently for Franz Lisp [WOOD82]. Flavors is an extension of the Lisp dialect in which it is implemented. This enables Lisp to take on the characteristics of the object-oriented environment similar in many respects to Smalltalk-80.. In Flavors, each object is an instance of a flavor.28 Each flavor definition consists of the flavor name, instance variables with optional default initial values, a set of components, and options. The components are a list29 of flavors from which the flavor being defined inherits methods and instance variables (See Flavors - Flavor Definition).


Figure: Flavors - Flavor Definition
An instance-variable may be given a default value by using the form (instance-variable initial-value). The list of component-names may be null.
(defflavor flavor-name (instance-variable-1
                         instance-variable-2
                         instance-variable-3
                         ...)
           (component-names)
           :option-1
           :option-2
           :option-3  )


Each method definition consists of the flavor name, the method-type, the message-selector, the lambda-list, and the body of the method. The method-type is used to describe how flavors inherit from other flavors, and is described below. The lambda list describes the method arguments and "aux variables" (See Flavors - Method Definition).


Figure: Flavors - Method Definition
(defmethod method-name method-type message-selector)
                        lambda-list
                        form1 form2 ....)

Three options are commonly used in a flavor definition. The :gettable-instance-variables option causes the automatic creation of a method for each instance variable which returns the value of the instance variable. The method name is created by prefixing the instance variable with a colon. A method is automatically created to set instance variables using the :settable-instance-variables option. The methods' names are created by prefixing the instance variables' names with :set-. When a new object is created, instance variables can be initialized, or override the default values, if the :initable-instance-variables option is used.

The components form an inheritance tree30 for a flavor. When searching for a method, the search is performed by a top-down, depth-first walk of the tree. Each node in the tree is check for the method before its subtrees. If duplicate components are found during the search, all but the first are ignored. Eliminating duplicates also prevents infinite cycling through the graph (tree).

A flavor may change an inherited method by defining a new method with the same name, and is called the primary method. The inherited methods with the same name are called daemons. These daemons can be called before or after the primary method by specifying :before or :after in the method-type of the method definition. When a message is passed to a method, all daemons for the method with a method-type of :before are invoked. Subsequently, the primary method is invoked followed by the methods with method-type :after. Before-daemons are called in the order of inheritance, and after-daemons are called in reverse order. "The reasons for this order is to keep the modularity order correct."31

In many respects, Flavors is similar to Smalltalk-80 because of the object-oriented message-passing style. The obvious differences are with respect to the syntax, complier options and inheritance. Flavors is Lisp based, and retains the syntax of the language. Flavors is a subset of Lisp, whereas Smalltalk-80 is a language as well as a system.

Flavors provides the encapsulation of objects which protects them from access except through the use of the objects' methods. Other protection mechanisms are strictly implementation dependent.

Programming Languages - Discussion

Evolution of Abstraction Mechanisms

As complex systems are developed, needs for programming languages which better describe and support such systems evolve. In turn, these new languages enable the construction of more complex and sophisticated systems. This symbiotic behavior has spurred the development of programming language.s.

People recognized the need to develop computer systems based upon abstract models. Early languages such as FORTRAN and COBOL allowed people to readily express their models and ideas. With the aid of these languages, people could envision even more complex modules and systems. As ideas and concepts developed, the expressive powers of these early programming language.s were insufficient. Refinements were made to the languages, or new ones were created to represent ideas and concepts of greater complexity.

Through the late 1960's, means for expressing abstraction in programming language.s was limited. Most languages supported a small number of data types. The remaining types would be created ad hoc; mechanisms for implementing abstract data types did not exist. Creation of complex structures were bound-up in the implementation of particular systems. Enforcement of proper use of the implementation was strictly the responsibility of the user; no compile-time checks were performed. The most readily available mechanisms for providing abstraction were procedures and functions for which specifications could be written.

Another emphasis in the evolution of programming language abstraction mechanisms was the concept of structured programming, sometimes referred to as step-wise refinement or top-down programming [WIRT71]. The top level of a system would contain the main logic, suppressing the details of the implementation in the lower layers. Each level in the system design could recursively treat the lower layers, regardless of their complexity, as abstract functions which had defined parameters and results. Each iteration of the design provided increasing refinement and fewer abstractions. Through this methodology, a complex problem could be reduced to an implementation in a programming language..

A development of the early 1970's was the introduction of methods for proving properties of programs through the use of mathematical logic [FLOY67] [HOAR69] [HAMLET]. With the assistance of mathematical logic, relatively simple programs could be verified. This verification process relied upon the use of modularity, where each function or procedure represented a single abstraction.

Another phenomena of the era was the shift in emphasis from control logic to data structures. The shift was away from using procedures and functions as the primary abstraction mechanisms, to the design, construction and verification of data types. Attention was turned towards ways in which information would be stored, manipulated and retrieved from the data structures.

The specification techniques used were not rigorously defined sets of operations. Lack of formal and precise specifications lead to misunderstandings, or implementation dependencies. The

final program does not preserve the series of abstractions through which it was created, and so the task of modifying the program after it is completed is not necessarily simpler than it would be for a program developed in any other way.32
Hence, methodologies for formal program specifications were developed. The goal was to organize software in such a way that it could be more easily modified, thus reducing the cost of software maintenance.

The mid and late 1970's saw research in programming language abstraction mechanisms shift towards organizing programs around abstract data objects and emphasizing locality of related collections of information. The organization of the data became the focal point, rather than the control mechanisms. Modules were created as to encapsulate complete data structures and the set of operations which could be performed on them.

The result, called an abstract data type, effectively extends the set of types available to a program -- it explains the properties of a new group of variables by specifying the values one of these variables may have, and it explains the operations that will be permitted on the variables of the new type by giving the effects these operations have on the values of the variables.33

The implementation of the operators and the representation of the new types would be implemented in the modules. The implementation would use the base types of the language, and any other previously defined abstract data types.

Naming and Addressing Issues

Naming and addressing are two central issues in the design of languages which support abstraction mechanisms. Scoping rules, private versus external names of objects and operators, and aliasing are some of the issues which directly bear upon how naming and addressing are to be preformed. Type checking at both compile-time and run-time determines when and how objects may be manipulated and passed as arguments. Some programming language.s provide mechanisms whereby any type may be passed as an argument. Such languages use compile-time, loader, or run-time mechanisms which enable these generic procedures to operate on many different data types, regardless of their representation or implementation. When a language uses typing of the identifiers, the compiler may be able to resolve the specific target of an operator. Typing may be specified either by explicit declaration or implicitly in statements which cause the creation of new objects. A loader may be able to resolve the target of operations by checking the type of the objects, which are generated by the compiler. The entry points of the procedures or methods can then be bound before run-time. Languages which use run-time binding are similar to message passing systems previously described. A compromise is to use a combination of these three binding methods.

Another abstraction mechanism is the ability to iterate over the elements of an object without knowing its representation. This permits objects of different types and representations to use the same language constructs in a uniform manner. Along with generic procedures, higher level abstract constructs can be created.

Abstraction should permit operations to be performed on objects regardless of their type. For example, the program or function to sort a list of integers, should without modification, be able to sort a disk file [BACK78]. This goal has been elusive, but progress is being made [GOLD83] [LISK75] [WEIN80] [LIEB81a] [LIEB81b]. Other advantages of abstract data types and abstraction, is the ability to prove properties of programs, such as partial correctness, program termination, security properties, liveliness, mutual exclusion and deadlock avoidance in critical sections [HOAR69] [HOWA76] [OWIC76] [HABE72] [ANDR83] [ANDL73]. Work has also been done in proving the correctness of abstract data types [GUTA78].

Security

The simplest form of security is the use of strong type checking either at compile-time or run-time. Procedure-oriented languages tend to perform type-checking at compile-time by associating a type with an identifier. Object-oriented languages, and particularly the message-passing languages, perform type-checking at run-time. These are divergent philosophies because of the ways in which the data is mapped into memory. Procedure-oriented languages usually associate identifiers with fixed memory locations. Object-oriented languages associate identifiers with objects. Such an identifier may reference many different objects of different types during its lifetime. The object, not the identifier defines the operations which may be performed.

Protected or sealed data types and objects adds another layer of security. Aside from benefits of abstraction, sealed objects prevent three types of security violation [MORR83]:
Alteration unintended changes.
Discovery access the representation of an object, including private or restricted information.
Impersonation posing as a valid, bonafide object.
Alteration and impersonation can lead to unexpected results, and the possibility of program failure. Discovery may not be dangerous, but certainly violates security policies. Information obtained through illegitimate means may subsequently lead to errors if the representation of the object changes.

One proposal for restricting access and manipulation of an object is to declare the identifier's set of rights for the object [JONE76]. The defined interfaces are for object creation, information extraction, and information storage. A qualified type is a data type T with a set of rights {r1,r2,...,rn}. A variable is declared v: T {r1,r2,...,rn}, and is denoted {object id, qualified type}. It is therefore possible for two variables to reference the same object, but have different rights. Sharing of information is performed through an assignment. An assignment is permitted if the expression being evaluated (source) is of the same type as the destination identifier, and the set of rights of the destination is the subset of expression's rights.

Conclusion

The object model is a concept which allows us to create concrete examples of abstract concepts. When applied to computing systems, the model has two important parts - protection and abstraction mechanisms. An important factor in protection mechanisms is the principal of least privilege.. Abstraction mechanisms are a means for constructing large and complex systems. Abstraction has been one of the motivating factors in the design of programming language.s.

The best protection mechanisms are those which support small protection domains. These domains may be defined in either hardware or software. To be effective, domain switching must have a low overhead. Hardware implementations typically use segmented memory and descriptors which define access capabilities or rights. Each procedure or process may have a different capability for the segment. To share information, it must be possible to pass descriptors to other procedures and processes. Methods must be defined for restricting the set of rights which are passed, and means for rights amplification.

Abstraction has many roles, from the design of systems to verification of their implementation. Programming languages have evolved over the years from the simple abstractions of procedures and functions, to data structuring and the abstract data types of object-oriented language.s. The need for complex structure has led to the creation of programming language.s which support the necessary abstraction mechanisms.

The object model is a useful tool because it organizes abstract ideas in an orderly fashion. It has helped focus on specific problems, particularly those addressed in this paper. Viewing protection and abstraction mechanisms in terms of objects and object manipulation clarifies the problems and assists in finding the solutions.

Appendix

Modula-2 Examples

The following examples demonstrate abstract data types in Modula-2.
Enumeration Enumeration is a means for defining elements of an abstract entity. BOOLEAN is an example of an enumerated type with elements (FALSE, TRUE).

The function ORD(variable) returns the ordinal value of the variable. The value returned is between zero and N-1, where N is the number of elements in the enumerated type. See Modula-2 - Enumerated Type.

SET The type SET is the equivalent of the mathematical abstraction. An explicitly defined set may be assigned to a variable of type SET. Procedures INCL and EXCL perform set union and set difference respectively. Other SET operators not shown include +, -, *, and / which perform union, difference, intersection, and symmetric difference, respectively. See Modula-2 - SET.
Subrange When a variable is restricted to a subrange, run-time checking is performed to ensure that a variable is not assigned a value outside its subrange. If an attempt is made to assign a value outside the variable's subrange, the program will halt with an appropriate error message. Subranges can not be defined for the type REAL. See Modula-2 - Subrange.
ARRAY Arrays may be multi-dimensional objects. There are no restrictions on the number of dimensions. Arrays must be subscripted by CARDINAL numbers. See Modula-2 - ARRAY.
RECORD A record is a composite object which contains one or more fields that are directly addressable via their subfield identifiers. Records with variant parts, although not shown in the figure, permit different numbers and kinds of fields to be in a record depending upon a value in a designated field. This mechanism permits flexibility in record declaration and a saving of storage space. However, the language does not specify run-time error checking. This leaves the potential for program errors. See Modula-2 - RECORD.
POINTER Objects can be created using the function NEW, and discarded with the procedure DISPOSE. These objects do not have identifiers. They are referenced by POINTER variables. The symbol &uparrow. is used to dereference a variable. POINTER variables are frequently used to create abstract data structures such as lists and trees. See Modula-2 - POINTER.
PROCEDURE The PROCEDURE type allows run-time binding of procedure or function names. The PROCEDURE type declaration forms a template for the actual call. See Modula-2 - PROCEDURE.
CONST The CONST declaration proceeds other declarations in the main program or subprograms. It provides a way of establishing identifiers as constants. See Modula-2 - CONST.


Figure: Modula-2 - CONST
 ...
CONST
     PI               = 3.14159;
     SecondsPerMinute = 60;
 ...


Figure: Modula-2 - Enumerated Type
TYPE
     Names    = (Bilbo, Winnie, Ziggie,
                 Washington, Jefferson, Napoleon);
     Classify = (Fiction, NonFiction);
 ...

VAR
     Person   : Names;
     BookType : Classify;
 ...

     Person   := Winnie;   (* ORD(Person)=1   *)
     BookType := Fiction;  (* ORD(BookType)=0 *)
 ...

.


Figure: Modula-2 - SET
TYPE
     Persons  = SET OF Names;
     SelfType = SET OF Classify;
 ...

VAR
     WhoIsOnShelf : Persons;
     OnThisShelf  : ShelfType;
 ...

             (* place 3 elements in the set   *)
     WhoIsOnShelf := {Bilbo, Ziggy, Jefferson}

             (* union Fiction with the set    *)
     INCL(OnThisShelf, Fiction)

             (* remove Jefferson from the set *)
     EXCL(WhoIsOnShelf, Jefferson)
 ...


Figure: Modula-2 - Subrange
TYPE
     Bit    = [0..1];  (* values 0 and 1 *)

          (* values between 0 and W-1 inclusive *)
     BITSET = [0..W-1];

          (* Washington, Jefferson and Napoleon *)
     Heroes = [Washington..Napoleon];
 ...


Figure: Modula-2 - ARRAY
VAR
     BitStream : ARRAY[0..N] OF Bit;

         (* 2 ways to declare 2 dimensional arrays: *)
     Matrix : ARRAY[1..X] OF ARRAY[1..Y] OF INTEGER;
     Grid   : ARRAY[1..X],[1..Y] OF INTEGER;
 ...

             (* one dimension subscripting *)
     a:= BitStream[Q];

             (* two dimension subscripting *)
     b:= Matrix[R][S];
     c:= Matrix[R,S];
 ...


Figure: Modula-2 - RECORD
TYPE
     Date = RECORD
        Year  = [0..99];
        Month = [1..12];
        Day   = [1..31];
     END; (* end of Date *)

     Book = RECORD
        Title    = ARRAY[1..30] OF CHAR;
        Subject  = Names;
        Category = Classify;
        Due      = Date;
     END; (* end of Book *)
 ...

VAR
     BooksOnShelf : ARRAY[1..S] OF Book;
     DueDate      : Date;
     DueMonth     : INTEGER;
     aBook        : CARDINAL;
 ...

     DueDate := BooksOnShelf[aBook].Due;
     BooksOnShelf[aBook].Due.Month := DueMonth;
 ...


Figure: Modula-2 - POINTER
VAR
     NewBook = POINTER TO Book;

 ...

     (* NewBook now references an object of type Book *)
     NewBook := NEW(Book);

     (* assign Washington to the Names field *)
     NewBook&uparrow..Names := Washington;
 ...
     (* discard the object referenced by NewBook *)
     DISPOSE(NewBook);
 ...


Figure: Modula-2 - PROCEDURE
TYPE
     Funct = PROCEDURE(REAL);
 ...

VAR
     f : Funct;
 ...

     f := SQR;     (* perform square root function *)
     P(x,f);       (* call procedure P             *)
     f := LOG;     (* perform the logorithm of x   *)
     P(x,f);       (* call procedure P             *)
 ...
 ...
PROCEDURE P(n : REAL; fn : Funct);
 ...
BEGIN
     fn(x);        (* invoke the function passed in fn *)
 ...

Smalltalk-80 Examples

The following are examples of Smalltalk-80 constructs.

Message Formats

Messages may be unary, binary, or keyword.
unary Single tokens specify the operation on the object. See Smalltalk-80 - Unary Messages.
binary The operators +,-,*,/,=, and == (equivalence). See Smalltalk-80 - Binary Messages.
keywords All other messages are keyword. Each keyword is terminated by a colon followed by an argument object. See Smalltalk-80 - Keyword Messages.


Figure: Smalltalk-80 - Unary Messages
Create a new Book object. Get the author of aBook. Execute aBlock which is a piece of code, and return its value (if any).
aBook <-- Book new.

writer <-- aBook author.

aBlock value.


Figure: Smalltalk-80 - Binary Messages
Compare due date to today's date. The result is a boolean object (True or False). Add 5 to the number of books on the shelf.
(aBook dueDate) = (Date today).

onShelf <-- booksOnShelf + 5.


Figure: Smalltalk-80 - Keyword Messages
Compute the fine for 3 days overdue, and add the fine to the borrower's account. At array element 3, put the value 9.
borrowerAccount addFine: (Fines days: 3).

anArray at: 3 put: 9

Code Blocks

Blocks are pieces of code which may be executed conditionally, passed as parameters, stored in arrays, or used in the same manner as any other object. See Smalltalk-80 - Blocks.


Figure: Smalltalk-80 - Blocks
If a=b, then add one to value, else subtract one. Find an element in a list; if not found, execute the block. The operator &uparrow causes a return value of the expression (0). The block of code which adds one to value is put in element position in the array actions.
(a = b)
   ifTrue:  [value <-- value + 1]
   ifFalse: [value <-- value - 1].

list find: element notFound: [&uarrow.0].

actions at: position put: [value <-- value + 1].


Footnotes

1 Other aspects of protection, such as information flow policies, authentication, encryption, and confinement, can be found in [LAMP73] [DENN77] [DENN76].

2 Some aspects of protection not addressed in this paper are authentication, information flow controls, and the confinement problem. These issues are the subject of [DENN76] and [LAMP73].

3 The contents of a sealed object may be passed from domain to domain, but the contents may not be referenced (read or written) unless the current domain has the capabilities to unseal the object.

4 The two parts are maintained separately because the hardware is limited to PDP-11's with special memory protection and communication hardware. Separation also makes the garbage collection problem simpler.

5 [COHE75], p. 143.

6 The calling and the called programs distrust each other. The caller wants to restrict the called program to manipulation of only those objects which are explicitly passed as parameters. The called program wants to prevent the caller from accessing the representation of the called procedure's private objects.

7 Set of capabilities.

8 The abstract I/O device concept is similar to the virtual terminal protocol used by applications communicating with terminals in conventional systems.

9 [MYER80], p. 14.

10 Implementations of the virtual machine have been written for various machines, including Sun &ucb., XEROX Dorado, Motorola 68000, HP 3000 Series 44, DEC-20, DEC VAX, and DEC PDP-11 [KRAS83].

11 A method is similar to a procedure. The distinction between a method and a procedure, and the semantics of the language, will be clarified in the section on programming languages.

12 A class is similar to a data type.

13 Passing a copy of the object, not a copy of a pointer to the object.

14 Intel 432., Sward, and IBM System/38..

15 Reduced Instruction Set Chip &risc1 &risc2.

16 The concept of a class is universally accepted, although it appears under different guises.

17 Roughly, methods are the equivalent of procedures and functions.

18 Those not in COMMON blocks or the formal parameters for the subprogram.

19 The range of values for INTEGER, CARDINAL, and REAL are implementation dependent. The type CARDINAL is non-negative integers. Variables of type CARDINAL can typically have larger positive values than those of type INTEGER.

20 Examples of how primitive types and and extensions may be combined to form new types can be found in Appendix A.

21 Pascal does not have the MODULE construct.

22 Adapted from [WIRT83], p. 93-94.

23 Examples may be found in Appendix B.

24 Smalltalk-80 provides for single inheritance - a class may inherit properties from one other class.

25 All classes inherit from the class Class.

26 See Appendix B.

27 Collection includes Bag, Set, OrderedCollection, LinkedLists, MappedCollection, SortedCollection, and IndexedCollection, with subclasses Dictionary, String, Array, and plus others.

28 A flavor is the equivalent of a Smalltalk-80 class.

29 It may be a null list, implying no inheritance.

30 It is actually a directed graph which may be cyclic.

31 [WEIN80], p. 13.

32 [SHAW80], p. 4.

33 [SHAW80], p. 6.


References

[ANDL73] Andler, S. "Synchronization Primitives and the Verification of Concurrent Programs", Operating Systems: Theory and Practice, North Holland, 1973.
[ANDR83] Andrews, G.R., Schneider, F.B. "Concepts and Notations for Concurrent Programming", Computing Surveys, Vol. 15, No. 1, March 1983, pp. 3-43.
[BACK78] Backus, J. "Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs", Communications of the ACM, August 1978, pp. 613-641.
[BERS78] Berstis, V., Truxal, C.D., Ranweiler. "The IBM System/38 Addressing and Authorization", Computer Structures: Principles and Examples, Siewiorek, Bell and Newell, McGraw-Hill, 1982, pp. 540-544.
[BIRT66] Birtwistle, G, Dahl, O.-J., Myhrhaug, B., and Nygaard, K. Simula Begin, Philadelphia: Auerbach, 1973.
[BURR61] The Burroughs Corp., "The Descriptor - a definition of the B5000 Information Processing System", The Burroughs Corp., Detriot, Michigan, Bull. No. 5000-20002-P, February 1961.
[CHEH81] Cheheyl, M.H., Gasser, M., Huff, G.A., Millen, J.K. "Verifying Security", Computing Surveys, Vol. 13, No. 3, September 1981, pp.279-339.
[COHE75] Cohen, E., Jefferson, D. "Protection in the Hydra Operating System", Operating Systems Review, Vol. 9, No. 5; also Proceedings of the Fifth Symposium on Operating Systems Principles, November 1975, pp. 141-159.
[DAHL78] Dahlby, S.H., Henry, G., Reynolds, D.N., Taylor, P.T. "The IBM System/38.: A High-Level Machine", Computer Structures: Principles and Examples, Siewiorek, Bell and Newell, McGraw-Hill, 1982, pp.533-536.
[DENN76] Denning, Dorothy E. "A Lattice Model of Secure Information Flow", Communications of the ACM, May 1976, pp. 236-243.
[DENN77] Denning, Dorothy E., and Denning, Peter J. "Certification of Programs for Secure Information Flow", Communications of the ACM, July 1977, pp. 504-513.
[DENN66] Dennis, J.B., Van Horn, E.C. "Programming Semantics for Multiprogrammed Computations", Communications of the ACM, March 1966, pp. 143-155.
[FABR74] Fabry, R.S. "Capability-Based Addressing", Communications of the ACM, July 1974, pp. 403-412.
[FLOY67] Floyd, R.W. "Assigning Meaning to Programs", Symposium in Applied Mathematics, American Mathematical Society, 1967, pp. 19-32.
[GOLD83] Goldberg, A., Robson, D. Smalltalk-80: The Language and its Implementation, Addison-Wesley, Reading, MA., 1983.
[GUTA78] Gutag, J.V., Horowitz, E., and Musser, D.R. "Abstract Data Types and Software Validation", Communications of the ACM, December 1978, pp. 1048-1064.
[HABE72] Habermann, A.N. "Synchronization of Communicating Processes", Communications of the ACM, March 1972, pp. 171-176.
[HAMLET] Hamlet, R., Mills, H. "Functional Semantics", University of Maryland, College Park, MD., Computer Science Technical Report.
[HERB78] Herbert, A.J. "A New Protection Architecture for the Cambridge Capability Computer", Operating Systems Review, Vol. 12, No. 1, January 1978, pp. 24-28.
[HOAR69] Hoare, C.A.R. "An Axiomatic Basis for Computer Programming", Communications of the ACM, October 1969, pp. 576-583.
[HOFF78] Hoffman, R., Soltis, F.G. "The IBM System/38.: Hardware Organization of the System/38.", Computer Structures: Principles and Examples, Siewiorek, Bell and Newell, McGraw-Hill, 1982, pp. 544-546.
[HOUD81] Houdek, M.E., Soltis, F.G., Hoffman, R.L. "IBM System/38 Support For Capability-Based Addressing", Conference Proceedings of the Eighth Annual Symposium on Computer Architecture; also SIGARCH Newsletter 9,3, May 1981, pp. 341-348.
[HOWA76] Howard, J.H. "Proving Monitors", Communications of the ACM, May 1976, pp. 273-279.
[IBM80] _____, IBM System/370 Principles of Operation, GA22-7000-6, International Business Machines Corporation, 1980.
[JENS74] Jensen, K., Wirth, N. Pascal: User Manual and Report, Springer-Verlag, New York, 1974.
[JONE73] Jones, A.K. Protection in Programmed Systems, Ph. D. Thesis, Carnegie-Mellon University, June 1973.
[JONE76] Jones, A.K., and Liskov, B. "A Language Extension for Controlling Access to Shared Data", IEEE Transactions on Software Engineering, SE-2, No. 4, December 1976.
[JONE79] Jones, A.K. "The Object Model: A Conceptual Tool for Structuring Software", Operating Systems: An Advanced Course, R. Bayer, R.M. Graham, and G. Seegmuller, ed., Springer-Verlag, Berlin, 1979, pp. 8-16.
[KRAS81] Krasner, G. "The Smalltalk-80 Virtual Machine", BYTE, August 1981, pp. 300-320.
[KRAS83] Krasner, G. Smalltalk-80: Bits of History, Words of Advice, Addison-Wesley, Reading, MA., 1983.
[LAMP73] Lampson, B.W. "A Note on the Confinement Problem", Communications of the ACM, October 1973, pp. 613-615.
[LAMP79] Lampson, B.W., Sproull, R.F. "An open operating system for a single-user machine", 1979, pp. 98-105.
[LEVI75] Levin, R., Cohen, E., Corwin, W., Pollack, F., Wulf, W. "Policy/Mechanism Separation in Hydra", Operating Systems Review, Vol. 9, No. 5; also Proceedings of the Fifth Symposium on Operating Systems Principles, November 1975, pp. 132-140.
[LIEB81a] Lieberman, H. "A Preview of Act1", MIT AI Memo No. 625, June 1981.
[LIEB81b] Lieberman, H. "Thinking About Lots Of Things At Once Without Getting Confused: Parallellism in Act 1", MIT AI Memo No. 626, May 1981.
[LISK75] Liskov, B. "An Introduction to CLU", New Directions in Algorithmic Languages 1975, pp. 139-155.
[MILL76] Millen, J.K. "Security Kernel Validation in Practice", Communications of the ACM, May 1976, pp.243-250.
[MORR83] Morris, J.H., Jr. "Protection in Programming Languages", Communications of the ACM, January 1983, pp. 15-21,
[MYER80] Myers, G.J., Buckingham, B.R.S. "A Hardware Implementation of Capability-Based Addressing", Computer Architecture News, Vol. 8, No. 6, 15 October 1980, pp. 12-24.
[NEED72] Needham, R.M. "Protection systems and protection implementations", AFIPS Fall Joint Computer Conference, Vol. 41, Part I, 1972, pp.571-578.
[ORGA72] Organick, E.I. The Multics System: An Examination of Its Structure, The MIT Press, Cambridge, 1972.
[ORGA73] Organick, E.I. Computer Sysetm Organization: The B5700/B6700 Series, Academic Press, 1973.
[OWIC76] Owicki, S., and Gries, D. "Verifying Properties of Parallel Programs: An Axiomatic Approach", Communications of the ACM, May 1976, pp. 279-285.
[PINN78] Pinnow, K.W., Ranweiler, J.G., Miller, J.F. "The IBM System/38 Object-Oriented Architecture", Computer Structures: Principles and Examples, Siewiorek, Bell and Newell, McGraw-Hill, 1982, pp. 537-540.
[POPE77] Popek, G.J., Horning, J.J., Lampson, B.W., Mitchell, J.G., London, R.L. "Notes On The Design Of Euclid", SIGPLAN Notices, Vol. 12, No. 3, March 1977, pp. 11-18.
[RATT80] Rattner, J., Cox, G. "Object-Based Computer Architecture", Computer Architecture News, Vol. 8, No. 6, 15 October 1980, pp. 4-11.
[SCHR72] Schroeder, M.D., Saltzer, J.H. "A Hardware Architecture for Implementing Protection Rings", Communications of the ACM, March 1972, pp. 157-170.
[SHAW80] Shaw, M. "The Impact of Abstraction Concerns in Modern Programming Languages", CMU Technical Report CMU-CS-80-116; also in Proceedings of the IEEE, September 1980.
[WEIN80] Weinreb, D., and Moon, D. "Flavors: Message Passing in the Lisp Machine", MIT AI Memo No. 602, November 1980.
[WILK79] Wilkes, M.V., Needham, R.M. The Cambridge CAP Computer and its Operating System, North Holland, New York, 1979.
[WIRT71] Wirth, N. "Program Development by Stepwise Refinement", Communications of the ACM, April 1971.
[WIRT83] Wirth, N. Programming in MODULA-2, second, corrected edition. Springer-Verlag, Berlin, 1983.
[WOOD82] Wood, R.J. "Franz Flavors: An Implementation of Abstract Data Types in an Applicative Language", University of Maryland, College Park, MD., CS TR-1174, June 1982.
[WULF74] Wulf, W., Cohen, E., Corwin, W., Jones, A., Levin, R., Pierson, C., Pollack, F. "HYDRA: The Kernel of a Multiprocessor Operating System", Communications of the ACM, June 1974, pp. 337-345.
[WULF75] Wulf, W., Levin, R., Pierson, C. "Overview of the Hydra Operating System Development", Operating System Review, also the Proceedings of the 5th Symposium on Operating System Principles, November 1975, pp. 122-131.
[WULF76] Wulf, W.A., London, R.L., Shaw, M. "An Introduction to the Construction and Verification of Alphard Programs", IEEE Transactions on Software Engineering, Vol. SE-2, No. 4, December 1976, pp. 253-265.
[XERO81] The XEROX Learning Research Group. "The Smalltalk-80 System", BYTE, Vol. 6, Number 8, August 1981, pp 36-48.
[ZEIG81] Zeigler, S., Allegre, N., Johnson, R., Morris, J., Burns, G. "Ada for the Intel 432 Microcomputer", Computer, June 1981, pp. 47-56.