The Smalltalk-80 Bytecodes

<table><thead><tr><th>Range</th><th>Bits</th><th>Function</th></tr></thead><tbody><tr><td>0-15</td><td>0000 iiii</td><td>Push Receiver Variable #iiii</td></tr><tr><td>16-31</td><td>0001 iiii</td><td>Push Temporary Location #iiii</td></tr><tr><td>32-63</td><td>001 iiii</td><td>Push Literal Constant #iiiii</td></tr><tr><td>64-95</td><td>010 iiii</td><td>Push Literal Variable #iiiii</td></tr><tr><td>96-103</td><td>01100 iiii</td><td>Pop and Store Receiver Variable #iii</td></tr><tr><td>104-111</td><td>01101 iiii</td><td>Pop and Store Temporary Location #iii</td></tr><tr><td>112-119</td><td>01110 iiii</td><td>Push (receiver, true, false, nil, -1, 0, 1, 2) [iii]</td></tr><tr><td>120-123</td><td>011110 ii</td><td>Return (receiver, true, false, nil) [ii] From Message</td></tr><tr><td>124-125</td><td>0111110 i</td><td>Return Stack Top From (Message, Block) [i]</td></tr><tr><td>126-127</td><td>0111111 i</td><td>unused</td></tr><tr><td>128</td><td>10000000</td><td>Push (Receiver Variable, Temporary Location, Litteral Constant, Literal Variable) [jj] #kkkkk</td></tr><tr><td>129</td><td>10000001</td><td>Store (Receiver Variable, Temporary Location, Illegal, Literal Variable) [jj] #kkkkk</td></tr><tr><td>130</td><td>10000010</td><td>Pop and Store (Receiver Variable, Temporary Location, Illegal, Literal Variable) [jj] #kkkkk</td></tr><tr><td>131</td><td>10000011</td><td>Send Literal Selector #kkkk With jjj Arguments</td></tr><tr><td>132</td><td>10000100</td><td>Send Literal Selector #kkkkkkk With jjjjjjj Arguments</td></tr><tr><td>133</td><td>10000101</td><td>Send Literal Selector #kkkk To Superclass With jjj Arguments</td></tr><tr><td>134</td><td>10000110</td><td>Send Literal Selector #kkkkkkk To Superclass With jjjjjjj Arguments</td></tr><tr><td>135</td><td>10000111</td><td>Pop Stack Top</td></tr><tr><td>136</td><td>10001000</td><td>Duplicate Stack Top</td></tr><tr><td>137</td><td>10001001</td><td>Push Active Context</td></tr><tr><td>138-143</td><td></td><td>unused</td></tr><tr><td>144-151</td><td>10010 iiii</td><td>Jump iii+1 (i.e., 1 through 8)</td></tr><tr><td>152-159</td><td>10011 iiii</td><td>Pop and Jump On False iii+1 (i.e., 1 through 8)</td></tr><tr><td>160-167</td><td>10100 iiii</td><td>Jump (iii-4)*256+jjjjjjj</td></tr><tr><td>168-171</td><td>101010 ii</td><td>Pop and Jump On True ii*256+jjjjjjj</td></tr><tr><td>172-175</td><td>101011 ii</td><td>Pop and Jump On False ii*256+jjjjjjj</td></tr><tr><td>176-191</td><td>1011 iiii</td><td>Send Arithmetic Message #iiii</td></tr><tr><td>192-207</td><td>1100 iiii</td><td>Send Special Message #iiii</td></tr><tr><td>208-223</td><td>1101 iiii</td><td>Send Literal Selector #iiii With No Arguments</td></tr><tr><td>224-239</td><td>1110 iiii</td><td>Send Literal Selector #iiii With 1 Argument</td></tr><tr><td>240-255</td><td>1111 iiii</td><td>Send Literal Selector #iiii With 2 Arguments</td></tr></tbody></table>
## Stack Bytecodes

The stack bytecodes all perform simple operations on the active context's evaluation stack.

* 107 bytecodes *push* an object pointer on the stack

* 99 push an object pointer found in the object memory

* 7 push a constant object pointer

* 1 pushes the interpreter's active context register (activeContext)

* 18 bytecodes *store* an object pointer found on the stack into the object memory

* 17 of these also remove it from the stack

* 1 leaves it on the stack

* 1 bytecode *removes* an object pointer from the stack without storing it anywhere.

The routines used to manipulate the stack were described in the section of the previous chapter on contexts (`push:`, `popStack`, `pop:`). The `stackBytecode` routine dispatches to the appropriate routine for the current bytecode.

### stackBytecode

(currentBytecode between: 0 and: 15)
  ifTrue: [↑self pushReceiverVariableBytecode].
(currentBytecode between: 16 and: 31)
  ifTrue: [↑self pushTemporaryVariableBytecode].
(currentBytecode between: 32 and: 63)
  ifTrue: [↑self pushLiteralConstantBytecode].
(currentBytecode between: 64 and: 95)
  ifTrue: [↑self pushLiteralVariableBytecode].
(currentBytecode between: 96 and: 103)
  ifTrue: [↑self storeAndPopReceiverVariableBytecode].
(currentBytecode between: 104 and: 111)
  ifTrue: [↑self storeAndPopTemporaryVariableBytecode].
currentBytecode = 112
  ifTrue: [↑self pushReceiverBytecode].
(currentBytecode between: 113 and: 119)
  ifTrue: [↑self pushConstantBytecode].
currentBytecode = 128
  ifTrue: [↑self extendedPushBytecode].
currentBytecode = 129
  ifTrue: [↑self extendedStoreBytecode].
currentBytecode = 130
  ifTrue: [↑self extendedStoreAndPopBytecode].
currentBytecode = 135
  ifTrue: [↑self popStackBytecode].
currentBytecode = 136
  ifTrue: [↑self duplicateTopBytecode].
currentBytecode = 137
  ifTrue: [↑self pushActiveContextBytecode]

There are single byte instructions that push the first 16 instance vari-
ables of the receiver and the first 16 temporary frame locations. Recall
that the temporary frame includes the arguments and the temporary
variables.

pushReceiverVariableBytecode

| fieldIndex |
fieldIndex ← self extractBits: 12 to: 15
  of: currentBytecode.
self pushReceiverVariable: fieldIndex

pushReceiverVariable: fieldIndex

self push: (memory fetchPointer: fieldIndex
  ofObject: receiver)

pushTemporaryVariableBytecode

| fieldIndex |
fieldIndex ← self extractBits: 12 to: 15
  of: currentBytecode.
self pushTemporaryVariable: fieldIndex

pushTemporaryVariable: temporaryIndex

self push: (self temporary: temporaryIndex)

There are also single byte instructions that reference the first 32 loca-
tions in the literal frame of the active context's method. The contents of
one of these locations can be pushed with pushLiteralConstantBytecode.
The contents of the value field of an Association stored in one of these
locations can be pushed with pushLiteralVariableBytecode.

pushLiteralConstantBytecode

| fieldIndex |
fieldIndex ← self extractBits: 11 to: 15
  of: currentBytecode.
self pushLiteralConstant: fieldIndex

pushLiteralConstant: literalIndex

self push: (self literal: literalIndex)

pushLiteralVariableBytecode

| fieldIndex |
fieldIndex ← self extractBits: 11 to: 15
  of: currentBytecode.
self pushLiteralVariable: fieldIndex
**pushLiteralVariable: literalIndex**

| association |

association ← self literal: literalIndex.

self push: (memory fetchPointer: ValueIndex
ofObject: association)

Associations are objects with two fields, one for a name and one for a value. They are used to implement shared variables (global variables, class variables, and pool variables). The following routine initializes the index used to fetch the value field of Associations.

**initializeAssociationIndex**

ValueIndex ← 1

The extended push bytecode can perform any of the four operations described above (receiver variable, temporary frame location, literal constant, or literal variable). However, instead of a limit of 16 or 32 variables accessible, it can access up to 64 instance variables, temporary locations, literal constants, or literal variables. The extended push bytecode is followed by a byte whose high order two bits determine which type of push is being done and whose low order six bits determine the offset to use.

**extendedPushBytecode**

| descriptor variableType variableIndex |

descriptor ← self fetchByte.

variableType ← self extractBits: 8 to: 9
of: descriptor.

variableIndex ← self extractBits: 10 to: 15
of: descriptor.

variableType=0 ifTrue: [↑self pushReceiverVariable: variableIndex].

variableType=1 ifTrue: [↑self pushTemporaryVariable: variableIndex].

variableType=2 ifTrue: [↑self pushLiteralConstant: variableIndex].

variableType=3 ifTrue: [↑self pushLiteralVariable: variableIndex]

The pushReceiverBytecode routine pushes a pointer to the active context's receiver. This corresponds to the use of self or super in a Smalltalk method.

**pushReceiverBytecode**

self push: receiver

The duplicateTopBytecode routine pushes another copy of the object pointer on the top of the stack.

**duplicateTopBytecode**

↑self push: self stackTop

The pushConstantBytecode routine pushes one of seven constant object pointers (true, false, nil, -1, 0, 1, or 2).
**pushConstantBytecode**

currentBytecode = 113 ifTrue: [↑self push: TruePointer].

currentBytecode = 114 ifTrue: [↑self push: FalsePointer].

currentBytecode = 115 ifTrue: [↑self push: NilPointer].

currentBytecode = 116 ifTrue: [↑self push: MinusOnePointer].

currentBytecode = 117 ifTrue: [↑self push: ZeroPointer].

currentBytecode = 118 ifTrue: [↑self push: OnePointer].

currentBytecode = 119 ifTrue: [↑self push: TwoPointer].

The pushActiveContextBytecode routine pushes a pointer to the active context itself. This corresponds to the use of thisContext in a Smalltalk method.

**pushActiveContextBytecode**

self push: activeContext

The store bytecodes transfer references in the opposite direction from the push bytecodes; from the top of the stack to the receiver's instance variables, the temporary frame, or the literal frame. There are single byte versions for storing into the first eight variables of the receiver or the temporary frame and then popping the stack.

**storeAndPopReceiverVariableBytecode**

| variableIndex |
variableIndex ← self extractBits: 13 to: 15
  of: currentBytecode.
memory storePointer: variableIndex
  ofObject: receiver
  withValue: self popStack

**storeAndPopTemporaryVariableBytecode**

| variableIndex |
variableIndex ← self extractBits: 13 to: 15
  of: currentBytecode.
memory storePointer: variableIndex + TempFrameStart
  ofObject: homeContext
  withValue: self popStack

Stores into variables other than those accessible by the single byte versions are accomplished by two extended store bytecodes. One pops the stack after storing and the other does not. Both extended stores take a following byte of the same form as the extended push. It is illegal, however, to follow an extended store with a byte of the form 10xxxxxx since this would mean changing the value of a literal constant.

**extendedStoreAndPopBytecode**

self extendedStoreBytecode.

self popStackBytecode

**extendedStoreBytecode**

| descriptor variableType variableIndex association |
descriptor ← self fetchByte.

variableType ← self extractBits: 8 to: 9
  of: descriptor.

variableIndex ← self extractBits: 10 to: 15
  of: descriptor.

variableType = 0 ifTrue:

[↑memory storePointer: variableIndex
  ofObject: receiver
  withValue: self stackTop].

variableType = 1 ifTrue:

[↑memory storePointer: variableIndex + TempFrameStart
  ofObject: homeContext
  withValue: self stackTop].

variableType = 2 ifTrue:

[↑self error: 'illegal store'].

variableType = 3 ifTrue:

[association ← self literal: variableIndex.
↑memory storePointer: ValueIndex
  ofObject: association
  withValue: self stackTop]

The last stack bytecode removes the top object pointer from the stack
without doing anything else with it.

### popStackBytecode

self popStack

## Jump Bytecodes

The jump bytecodes change the active context's instruction pointer by a specified amount. Unconditional jumps change the instruction pointer whenever they are encountered. Conditional jumps only change the instruction pointer if the object pointer on the top of the stack is a specified Boolean object (either true or false). Both unconditional and conditional jumps have a short (single-byte) and a long (two-byte) form.

### jumpBytecode

(currentBytecode between: 144 and: 151)
  ifTrue: [↑self shortUnconditionalJump].

(currentBytecode between: 152 and: 159)
  ifTrue: [↑self shortConditionalJump].

(currentBytecode between: 160 and: 167)
  ifTrue: [↑self longUnconditionalJump].

(currentBytecode between: 168 and: 175)
  ifTrue: [↑self longConditionalJump]
The jump bytecodes use the jump: routine to actually change the bytecode index.

**jump: offset**

instructionPointer ← instructionPointer + offset

The eight short unconditional jumps advance the instruction pointer by 1 through 8.

**shortUnconditionalJump**

| offset |

offset ← self extractBits: 13 to: 15

of: currentBytecode.

self jump: offset + 1

The eight long unconditional jumps are followed by another byte. The low order three bits of the jump bytecode provide the high order three bits of an 11-bit twos complement displacement to be added to the instruction pointer. The byte following the jump provides the low order eight bits of the displacement. So long unconditional jumps can jump up to 1023 forward and 1024 back.

**longUnconditionalJump**

| offset |

offset ← self extractBits: 13 to: 15

of: currentBytecode.

self jump: offset - 4 * 256 + self fetchByte

The conditional jumps use the jumpIf:by: routine to test the top of the stack and decide whether to perform the jump. The top of stack is discarded after it is tested.

**jumpIf: condition by: offset**

| boolean |

boolean ← self popStack.

boolean = condition

ifTrue: [self jump: offset]

ifFalse: [(boolean = TruePointer) | (boolean = FalsePointer)]

ifFalse: [self unPop: 1.

self sendMustBeBoolean]]

The conditional jumps are used in the compiled form of messages to booleans (e.g., ifTrue: and whileFalse:). If the top of the stack at the time of a conditional jump is not true or false it is an error since an object other than a boolean has been sent a message that only booleans understand. Instead of sending doesNotUnderstand:, the interpreter sends mustBeBoolean to it.
**sendMustBeBoolean**

self sendSelector: MustBeBooleanSelector
argumentCount: 0

The sendSelector:argumentCount: routine is described in the next section on send bytecodes.

The eight short conditional jumps advance the instruction pointer by 1 through 8 if the top of the stack is false.

**shortConditionalJump**

| offset |
offset ← self extractBits: 13 to: 15
  of: currentBytecode.
self jumpIf: FalsePointer
  by: offset + 1

So, there are three possible outcomes to a short conditional jump:

* If the top of the stack is false, the jump is taken.

* If the top of the stack is true, the jump is not taken.

* If the top of the stack is neither, mustBeBoolean is sent to it.

Half of the long conditional jumps perform the jump if the top of the stack is false while the other half perform the jump if it is true. The low order two bits of the bytecode become the high order two bits of a 10-bit unsigned displacement. The byte following the jump provides the low order eight bits of the displacement. So long conditional jumps can jump up to 1023 forward.

**longConditionalJump**

| offset |
offset ← self extractBits: 14 to: 15
  of: currentBytecode.
offset ← offset * 256 + self fetchByte.
(currentBytecode between: 168 and: 171)
ifTrue: [↑self jumpIf: TruePointer
  by: offset].
(currentBytecode between: 172 and: 175)
ifTrue: [↑self jumpIf: FalsePointer
  by: offset]

**Send Bytecodes**

The send bytecodes cause a message to be sent. The object pointers for the receiver and the arguments of the message are found on the active context's evaluation stack. The send bytecode determines the selector of
the message and how many arguments to take from the stack. The number of arguments is also indicated in the CompiledMethod invoked by the message. The compiler guarantees that this information is redundant except when a CompiledMethod is reached by a perform: message, in which case it is checked to make sure the CompiledMethod takes the right number of arguments. The perform: messages will be discussed in the next chapter in a section on control primitives.

The selectors of most messages are found in the literal frame of the CompiledMethod. The *literal-selector* bytecodes and the *extended-send* bytecodes specify the argument count of the message and the index of the selector in the literal frame. The 32 *special-selector* bytecodes specify the offset of the selector and argument count in an Array in the object memory. This Array is shared by all CompiledMethods in the system.

**sendBytecode**

(currentBytecode between: 131 and: 134)
ifTrue: [↑self extendedSendBytecode].

(currentBytecode between: 176 and: 207)
ifTrue: [↑self sendSpecialSelectorBytecode].

(currentBytecode between: 208 and: 255)
ifTrue: [↑self sendLiteralSelectorBytecode]

The literal-selector bytecodes are single bytes that can specify 0, 1, or 2 arguments and a selector in any one of the first 16 locations of the literal frame. Both the selector index and the argument count are encoded in the bits of the bytecode.

**sendLiteralSelectorBytecode**

<table><tr><td>selector</td><td>selector ← self literal: (self extractBits: 12 to: 15 of: currentBytecode).</td></tr><tr><td>self sendSelector</td><td>selector</td></tr><tr><td>argumentCount</td><td>(self extractBits: 10 to: 11 of: currentBytecode) - 1</td></tr></table>

Most of the send bytecodes call the `sendSelector:argumentCount:` routine after determining the appropriate selector and argument count. This routine sets up the variables `messageSelector` and `argumentCount`, which are available to the other routines in the interpreter that will lookup the message and perhaps activate a method.

**sendSelector: selector argumentCount: count**

<table><tr><td>newReceiver</td><td></td></tr><tr><td>messageSelector</td><td>selector.</td></tr><tr><td>argumentCount</td><td>count.</td></tr><tr><td>newReceiver</td><td>self stackValue: argumentCount.</td></tr><tr><td>self sendSelectorToClass</td><td>(memory fetchClassOf: newReceiver)</td></tr></table>
**sendSelectorToClass: classPointer**

self findNewMethodInClass: classPointer.

self executeNewMethod

The interpreter uses a method cache to reduce the number of dictionary lookups necessary to find CompiledMethods associated with selectors. The method cache may be omitted by substituting a call on `lookupMethodInClass:` for the call on `findNewMethodInClass:` in `sendSelectorToClass:` above. The `lookupMethodInClass:` routine is described in the previous chapter in a section on classes. The cache may be implemented in various ways. The following routine uses four sequential locations in an Array for each entry. The four locations store the selector, class, CompiledMethod, and primitive index for the entry. This routine does not allow for reprobes.

**findNewMethodInClass: class**

] hash |

hash ← (((messageSelector bitAnd: class) bitAnd: 16rFF) bitShift: 2) + 1.

((methodCache at: hash) = messageSelector and: [(methodCache at: hash + 1) = class])

ifTrue: [newMethod ← methodCache at: hash + 2.

primitiveIndex ← methodCache at: hash + 3]

ifFalse: [self lookupMethodInClass: class.
methodCache at: hash put: messageSelector.
methodCache at: hash + 1 put: class.
methodCache at: hash + 2 put: newMethod.
methodCache at: hash + 3 put: primitiveIndex]

The method cache is initialized with the following routine.

**initializeMethodCache**

methodCacheSize ← 1024.

methodCache ← Array new: methodCacheSize

The `executeNewMethod` routine calls a primitive routine if one is associated with the `CompiledMethod`. The `primitiveResponse` routine returns `false` if no primitive is indicated or the primitive routine is unable to produce a result. In that case, the `CompiledMethod` is activated. Primitive routines and the `primitiveResponse` routine will be described in the next chapter.

**executeNewMethod**

self primitiveResponse

ifFalse: [self activateNewMethod]

The routine that activates a method creates a `MethodContext` and transfers the receiver and arguments from the currently active context's stack to the new context's stack. It then makes this new context the interpreter's active context.
### activateNewMethod

| contextSize newContext newReceiver |
(self largeContextFlagOf: newMethod) = 1
    ifTrue: [contextSize ← 32 + TempFrameStart]
    ifFalse: [contextSize ← 12 + TempFrameStart].
newContext ← memory instantiateClass: ClassMethodContextPointer
    withPointers: contextSize.
memory storePointer: SenderIndex
    ofObject: newContext
    withValue: activeContext.
self storeInstructionPointerValue:
    (self initialInstructionPointerOfMethod: newMethod)
    inContext: newContext.
self storeStackPointerValue: (self temporaryCountOf: newMethod)
    inContext: newContext.
memory storePointer: MethodIndex
    ofObject: newContext
    withValue: newMethod.
self transfer: argumentCount + 1
    fromIndex: stackPointer - argumentCount
    ofObject: activeContext
    toIndex: ReceiverIndex
    ofObject: newContext.
self pop: argumentCount + 1.
self newActiveContext: newContext

There are four extended-send bytecodes. The first two have the same effect as the literal-selector bytecodes except that the selector index and argument count are found in one or two following bytes instead of in the bytecode itself. The other two extended-send bytecodes are used for superclass messages.

### extendedSendBytecode

currentBytecode = 131 ifTrue: [↑self singleExtendedSendBytecode].
currentBytecode = 132 ifTrue: [↑self doubleExtendedSendBytecode].
currentBytecode = 133 ifTrue: [↑self singleExtendedSuperBytecode].
currentBytecode = 134 ifTrue: [↑self doubleExtendedSuperBytecode]

The first form of extended send is followed by a single byte specifying the number of arguments in its high order three bits and selector index in the low order five bits.

### singleExtendedSendBytecode

| descriptor selectorIndex |
descriptor ← self fetchByte.
selectorIndex ← self extractBits: 11 to: 15
    of: descriptor.
self sendSelector: (self literal: selectorIndex)
argumentCount: (self extractBits: 8 to: 10
of: descriptor)

The second form of extended send bytecode is followed by two bytes; the first is the number of arguments and the second is the index of the selector in the literal frame.

### doubleExtendedSendBytecode

| count selector |
count ← self fetchByte.
selector ← self literal: self fetchByte.
self sendSelector: selector
argumentCount: count

When the compiler encounters a message to super in a symbolic method, it uses the bytecode that pushes self for the receiver, but it uses an extended-super bytecode to indicate the selector instead of a regular send bytecode. The two extended-super bytecodes are similar to the two extended-send bytecodes. The first is followed by a single byte and the second by two bytes that are interpreted exactly as for the extended-send bytecodes. The only difference in what these bytecodes do is that they start the message lookup in the superclass of the class in which the current CompiledMethod was found. Note that this is not necessarily the immediate superclass of self. Specifically, it will not be the immediate superclass of self if the CompiledMethod containing the extended-super bytecode was found in a superclass of self originally. All CompiledMethods that contain extended-super bytecodes have the class in which they are found as their last literal variable.

### singleExtendedSuperBytecode

| descriptor selectorIndex methodClass |
descriptor ← self fetchByte.
argumentCount ← self extractBits: 8 to: 10
of: descriptor.
selectorIndex ← self extractBits: 11 to: 15
of: descriptor.
messageSelector ← self literal: selectorIndex.
methodClass ← self methodClassOf: method.
self sendSelectorToClass: (self superclassOf: methodClass)

### doubleExtendedSuperBytecode

| methodClass |
argumentCount ← self fetchByte.
messageSelector ← self literal: self fetchByte.
methodClass ← self methodClassOf: method.
self sendSelectorToClass: (self superclassOf: methodClass)
The set of special selectors can be used in a message without being included in the literal frame. An Array in the object memory contains the object pointers of the selectors in alternating locations. The argument count for each selector is stored in the location following the selector's object pointer. The specialSelectorPrimitiveResponse routine will be described in the next chapter.

**sendSpecialSelectorBytecode**

| selectorIndex | selector count |
|---|---|
| self | specialSelectorPrimitiveResponse |
| ifFalse: | [selectorIndex ← (currentBytecode - 176) * 2. |
| selector | ← memory fetchPointer: selectorIndex |
| | ofObject: SpecialSelectorPointe |
| count | ← self fetchInteger: selectorIndex + 1 |
| | ofObject: SpecialSelectorPointe |
| self | sendSelector: selector |
| argumentCount | count] |

**Return Bytecodes**

There are six bytecodes that return control and a value from a context; five return the value of a message (invoked explicitly by "↑" or implicitly at the end of a method) and the other one returns the value of a block (invoked implicitly at the end of a block). The distinction between the two types of return is that the former returns to the sender of the home context while the latter returns to the caller of the active context. The values returned from the five return bytecodes are: the receiver (self), true, false, nil, or the top of the stack. The last return bytecode returns the top of the stack as the value of a block.

**returnBytecode**

currentBytecode = 120
ifTrue: [↑self returnValue: receiver to: self sender].
currentBytecode = 121
ifTrue: [↑self returnValue: TruePointer to: self sender].
currentBytecode = 122
ifTrue: [↑self returnValue: FalsePointer to: self sender].
currentBytecode = 123
ifTrue: [↑self returnValue: NilPointer to: self sender].
```
currentBytecode = 124
    ifTrue: [↑self returnValue: self popStack
              to: self sender].
```

```
currentBytecode = 125
    ifTrue: [↑self returnValue: self popStack
              to: self caller]
```

The simple way to return a value to a context would be to simply make it the active context and push the value on its stack.

**simpleReturnValue: resultPointer to: contextPointer**

```
self newActiveContext: contextPointer.
self push: resultPointer
```

However, there are three situations in which this routine is too simple to work correctly. If the sender of the active context were nil; this routine would store a nil in the interpreter's active context pointer, bringing the system to an unpleasant halt. In order to prevent this, the actual returnValue:to: routine first checks to see if the sender is nil. The interpreter also prevents returns to a context that has already been returned from. It does this by storing nil in the instruction pointer of the active context on return and checking for a nil instruction pointer of the context being returned to. Both of these situations can arise since contexts are objects and can be manipulated by user programs as well as by the interpreter. If either situation arises, the interpreter sends a message to the active context informing it of the problem. The third situation will arise in systems that automatically deallocate objects based on their reference counts. The active context may be deallocated as it is returning. It, in turn, may contain the only reference to the result being returned. In this case, the result will be deallocated before it can be pushed on the new context's stack. Because of these considerations, the returnValue: routine must be somewhat more complicated.

**returnValue: resultPointer to: contextPointer**

```
| sendersIP |
contextPointer = NilPointer
    ifTrue: [self push: activeContext.
              self push: resultPointer.
              ↑self sendSelector: CannotReturnSelector
                          argumentCount: 1].
sendersIP ← memory fetchPointer: InstructionPointerIndex
            ofObject: contextPointer.
```

```
sendersIP = NilPointer
    ifTrue: [self push: activeContext.
              self push: resultPointer.
              ↑self sendSelector: CannotReturnSelector
                          argumentCount: 1].
```

```
sendersIP = NilPointer
    ifTrue: [self push: activeContext.
              self push: resultPointer.
              ↑self sendSelector: CannotReturnSelector
                          argumentCount: 1].
```
memory increaseReferencesTo: resultPointer.

self returnToActiveContext: contextPointer.

self push: resultPointer.

memory decreaseReferencesTo: resultPointer

This routine prevents the deallocation of the result being returned by
raising the reference count until it is pushed on the new stack. It could
also have pushed the result before switching active contexts. The
returnToActiveContext: routine is basically the same as the
newActiveContext: routine except that instead of restoring any cached
fields of the context being returned from, it stores nil into the sender
and instruction pointer fields.

**returnToActiveContext: aContext**

memory increaseReferencesTo: aContext.

self nilContextFields.

memory decreaseReferencesTo: activeContext.

activeContext ← aContext.

self fetchContextRegisters

**nilContextFields**

memory storePointer: SenderIndex

ofObject: activeContext

withValue: NilPointer.

memory storePointer: InstructionPointerIndex

ofObject: activeContext

withValue: NilPointer
29

# Formal Specification of the Primitive Methods

Arithmetic Primitives

Array and Stream Primitives

Storage Management Primitives

Control Primitives

Input/Output Primitives

System Primitives

<figure><img src="image_293.png" /></figure>
When a message is sent, the interpreter usually responds by executing a Smalltalk CompiledMethod. This involves creating a new MethodContext for that CompiledMethod and executing its bytecodes until a return bytecode is encountered. Some messages, however, may be responded to *primitively*. A primitive response is performed directly by the interpreter without creating a new context or executing any other bytecodes. Each primitive response the interpreter can make is described by a *primitive routine*. A primitive routine removes the message receiver and arguments from the stack and replaces them with the appropriate result. Some primitive routines have other effects on the object memory or on some hardware devices. After a primitive response is completed, the interpreter proceeds with interpretation of the bytecode after the send bytecode that caused the primitive to be executed.

At any point in its execution, a primitive routine may determine that a primitive response cannot be made. This may, for example, be due to a message argument of the wrong class. This is called *primitive failure*. When a primitive fails, the Smalltalk method associated with the selector and receiver's class will be executed as if the primitive method did not exist.

The table below shows the class-selector pairs associated with each primitive routine. Some of these class-selector pairs have not appeared earlier in this book since they are part of the class's private protocol. Some of the primitive routines must meet their specification in order for the system to function properly. Other primitive routines are optional; the system will simply perform less efficiently if they always fail. The optional primitives are marked with an asterisk. The Smalltalk methods associated with optional primitive routines must do everything the primitive does. The Smalltalk methods associated with required primitive routines need only handle the cases for which the primitive fails.

## The Smalltalk Primitives

<table><thead><tr><td>Primitive Index</td><td>Class-Selector Pairs</td></tr></thead><tbody><tr><td>1</td><td>SmallInteger +</td></tr><tr><td>2</td><td>SmallInteger -</td></tr><tr><td>3</td><td>SmallInteger &lt;</td></tr><tr><td>4</td><td>SmallInteger &gt;</td></tr><tr><td>5*</td><td>SmallInteger &lt;=</td></tr><tr><td>6*</td><td>SmallInteger &gt;=</td></tr><tr><td>7</td><td>SmallInteger =</td></tr><tr><td>8*</td><td>SmallInteger ~=</td></tr><tr><td>9</td><td>SmallInteger *</td></tr><tr><td>10*</td><td>SmallInteger /</td></tr><tr><td>11*</td><td>SmallInteger \</td></tr><tr><td>12</td><td>SmallInteger //</td></tr></tbody></table>
<table>
  <tbody>
    <tr>
      <td>13*</td>
      <td>SmallInteger quo:</td>
    </tr>
    <tr>
      <td>14</td>
      <td>SmallInteger bitAnd:</td>
    </tr>
    <tr>
      <td>15</td>
      <td>SmallInteger bitOr:</td>
    </tr>
    <tr>
      <td>16</td>
      <td>SmallInteger bitXor:</td>
    </tr>
    <tr>
      <td>17</td>
      <td>SmallInteger bitShift:</td>
    </tr>
    <tr>
      <td>18*</td>
      <td>Number @</td>
    </tr>
    <tr>
      <td>19</td>
      <td></td>
    </tr>
    <tr>
      <td>20</td>
      <td></td>
    </tr>
    <tr>
      <td>21*</td>
      <td>Integer + LargePositiveInteger +</td>
    </tr>
    <tr>
      <td>22*</td>
      <td>Integer - LargePositiveInteger -</td>
    </tr>
    <tr>
      <td>23*</td>
      <td>Integer &lt; LargePositiveInteger &lt;</td>
    </tr>
    <tr>
      <td>24*</td>
      <td>Integer &gt; LargePositiveInteger &gt;</td>
    </tr>
    <tr>
      <td>25*</td>
      <td>Integer &lt;= LargePositiveInteger &lt;=</td>
    </tr>
    <tr>
      <td>26*</td>
      <td>Integer &gt;= LargePositiveInteger &gt;=</td>
    </tr>
    <tr>
      <td>27*</td>
      <td>Integer = LargePositiveInteger =</td>
    </tr>
    <tr>
      <td>28*</td>
      <td>Integer ~= LargePositiveInteger ~=</td>
    </tr>
    <tr>
      <td>29*</td>
      <td>Integer * LargePositiveInteger *</td>
    </tr>
    <tr>
      <td>30*</td>
      <td>Integer / LargePositiveInteger /</td>
    </tr>
    <tr>
      <td>31*</td>
      <td>Integer \\ LargePositiveInteger \\</td>
    </tr>
    <tr>
      <td>32*</td>
      <td>Integer // LargePositiveInteger //</td>
    </tr>
    <tr>
      <td>33*</td>
      <td>Integer quo: LargePositiveInteger quo:</td>
    </tr>
    <tr>
      <td>34*</td>
      <td>Integer bitAnd: LargePositiveInteger bitAnd:</td>
    </tr>
    <tr>
      <td>35*</td>
      <td>Integer bitOr: LargePositiveInteger bitOr:</td>
    </tr>
    <tr>
      <td>36*</td>
      <td>Integer bitXor: LargePositiveInteger bitXor:</td>
    </tr>
    <tr>
      <td>37*</td>
      <td>Integer bitShift: LargePositiveInteger bitShift:</td>
    </tr>
    <tr>
      <td>38</td>
      <td></td>
    </tr>
    <tr>
      <td>39</td>
      <td></td>
    </tr>
    <tr>
      <td>40</td>
      <td>SmallInteger asFloat</td>
    </tr>
    <tr>
      <td>41</td>
      <td>Float +</td>
    </tr>
    <tr>
      <td>42</td>
      <td>Float -</td>
    </tr>
    <tr>
      <td>43</td>
      <td>Float &lt;</td>
    </tr>
    <tr>
      <td>44</td>
      <td>Float &gt;</td>
    </tr>
    <tr>
      <td>45*</td>
      <td>Float &lt;=</td>
    </tr>
    <tr>
      <td>46*</td>
      <td>Float &gt;=</td>
    </tr>
    <tr>
      <td>47</td>
      <td>Float =</td>
    </tr>
    <tr>
      <td>48*</td>
      <td>Float ~=</td>
    </tr>
    <tr>
      <td>49</td>
      <td>Float *</td>
    </tr>
    <tr>
      <td>50</td>
      <td>Float /</td>
    </tr>
    <tr>
      <td>51</td>
      <td>Float truncated</td>
    </tr>
    <tr>
      <td>52*</td>
      <td>Float fractionPart</td>
    </tr>
    <tr>
      <td>53*</td>
      <td>Float exponent</td>
    </tr>
    <tr>
      <td>54*</td>
      <td>Float timesTwoPower:</td>
    </tr>
    <tr>
      <td>55</td>
      <td></td>
    </tr>
    <tr>
      <td>56</td>
      <td></td>
    </tr>
    <tr>
      <td>57</td>
      <td></td>
    </tr>
    <tr>
      <td>58</td>
      <td></td>
    </tr>
  </tbody>
</table>
59

60 LargeNegativeInteger digitAt:
LargePositiveInteger digitAt:
Object at:
Object basicAt:

61 LargeNegativeInteger digitAt:put:
LargePositiveInteger digitAt:put:
Object basicAt:put:
Object at:put:

62 ArrayedCollection size

LargeNegativeInteger digitLength

LargePositiveInteger digitLength

Object basicSize

Object size

String size

63 String at:

String basicAt:

64 String basicAt:put:

String at:put:

65* ReadStream next ReadWriteStream next

66* WriteStream nextPut:

67* PositionableStream atEnd

68 CompiledMethod objectAt:

69 CompiledMethod objectAt:put:

70 Behavior basicNew Behavior new
Interval class new

71 Behavior new:
Behavior basicNew:

72 Object become:

73 Object instVarAt:

74 Object instVarAt:put:

75 Object asOop

Object hash

Symbol hash

76 SmallInteger asObject
SmallInteger asObjectNoFail

77 Behavior someInstance

78 Object nextInstance

79 CompiledMethod class newMethod:header:

80* ContextPart blockCopy:

81 BlockContext value:value:value:
BlockContext value:

BlockContext value:

BlockContext value:value:

82 BlockContext valueWithArguments:

83* Object perform:with:with:with:
Object perform:with:

Object perform:with:with:

Object perform:

84 Object perform:withArguments:

85 Semaphore signal

86 Semaphore wait

87 Process resume

88 Process suspend

89 Behavior flushCache

90* InputSensor primMousePt InputState primMousePt

91 InputState primCursorLocPut:
InputState primCursorLocPutAgain:

92 Cursor class cursorLink:

93 InputState primInputSemaphore:

94 InputState primSampleInterval:

95 InputState primInputWord

96 BitBlt copyBitsAgain BitBlt copyBits

97 SystemDictionary snapshotPrimitive

98 Time class secondClockInto:

99 Time class millisecondClockInto:

100 ProcessorScheduler signal:atMilliseconds:

101 Cursor beCursor

102 DisplayScreen beDisplay

103* CharacterScanner scanCharactersFrom:to:in:
  rightX:stopConditions:displaying:

104* BitBlt drawLoopX:Y:

105* ByteArray primReplaceFrom:to:with:startingAt:

ByteArray replaceFrom:to:withString:startingAt:

String replaceFrom:to:withByteArray:startingAt:

String primReplaceFrom:to:with:startingAt:

106

107

108

109

110 Character =

Object ==

111 Object class

112 SystemDictionary coreLeft

113 SystemDictionary quitPrimitive

114 SystemDictionary exitToDebugger

115 SystemDictionary oopsLeft

116 SystemDictionary signal:atOopsLeft:wordsLeft:

117

118

119

120
121
122
123
124
125
126
127

An example of a primitive method is the response of instances of `SmallInteger` to messages with selector `+`. If the argument is also an instance of `SmallInteger`, and the sum of the values of the receiver and argument is in the range that can be represented by `SmallInteger`, then the primitive method will remove the receiver and argument from the stack and replace them with an instance of `SmallInteger` whose value is the sum. If the argument is not a `SmallInteger` or the sum is out of range, the primitive will fail and the Smalltalk method associated with the selector `+` in `SmallInteger` will be executed.

The control structures used in the specification of the interpreter given in this book and the control structures used in a machine language implementation of the interpreter will probably use different mechanisms when primitive routines fail to complete. When a failure condition arises, a machine language primitive routine can decide not to return to its caller and simply jump to the appropriate place in the interpreter (usually the place that activates a `CompiledMethod`). However, since the formal specification is written in Smalltalk, all routines *must* return to their senders and Interpreter must keep track of primitive success or failure independently of the routine call structure. Part of the book specification, therefore, is a register called success that is initialized to true when a primitive is started and may be set to false if the routine fails. The following two routines set and test the state of the primitive success register.

**success: successValue**

`success` ← `successValue` & `success`

**success**

`↑success`

The following routines set the state of the success flag in the two common cases of initialization before a primitive routine runs and discovery by a primitive routine that it cannot complete.

**initPrimitive**

`success` ← `true`

**primitiveFail**

`success` ← `false`
Many of the primitives manipulate integer quantities, so the interpreter includes several routines that perform common functions. The `popInteger` routine is used when a primitive expects a `SmallInteger` on the top of the stack. If it is a `SmallInteger`, its value is returned; if not, a primitive failure is signaled.

**popInteger**

| integerPointer |
integerPointer ← self popStack.
self success: (memory isIntegerObject: integerPointer).
self success
  ifTrue: [↑memory integerValueOf: integerPointer]

Recall that the `fetchInteger:ofObject:` routine signaled a primitive failure if the indicated field did not contain a `SmallInteger`. The `pushInteger:` routine converts a value to a `SmallInteger` and pushes it on the stack.

**pushInteger: integerValue**

self push: (memory integerObjectOf: integerValue)

Since the largest indexable collections may have 65534 indexable elements, and `SmallIntegers` can only represent values up to 16383, primitive routines that deal with indices or sizes must be able to manipulate `LargePositiveIntegers`. The following two routines convert back and forth between 16-bit unsigned values and object pointers to `SmallIntegers` or `LargePositiveIntegers`.

**positive 16BitIntegerFor: integerValue**

| newLargeInteger |
integerValue < 0
  ifTrue: [↑self primitiveFail].
  (memory isIntegerValue: integerValue)
  ifTrue: [↑memory integerObjectOf: integerValue].
newLargeInteger ← memory instantiateClass:
  ClassLargePositiveIntegerPointer
  withBytes: 2.
memory storeByte: 0
  ofObject: newLargeInteger
  withValue: (self lowByteOf: integerValue).
memory storeByte: 1
  ofObject: newLargeInteger
  withValue: (self highByteOf: integerValue).
↑newLargeInteger

**positive 16BitValueOf: integerPointer**

| value |
(memory isIntegerObject: integerPointer)
```pascal
ifTrue: [ memory integerValueOf: integerPointer ].
(memory fetchClassOf: integerPointer) =
    ClassLargePositiveIntegerPointer
ifFalse: [ !self primitiveFail ].
(memory fetchByteLengthOf: integerPointer) = 2
ifFalse: [ !self primitiveFail ].
value := memory fetchByte: 1
    ofObject: integerPointer.
value := value * 256 + (memory fetchByte: 0
    ofObject: integerPointer).
tvalue
```

There are three ways that a primitive routine can be reached in the process of interpreting a send-message bytecode.

1. Some primitive routines are associated with send-special-selector bytecodes for certain classes of receiver. These can be reached without a message lookup.

2. The two most common primitive routines (returning self or an instance variable) can be indicated in the flag value of the header of a CompiledMethod. These are only found after a message lookup has produced a CompiledMethod, but only the header need be examined.

3. Most primitive routines are indicated by a number in the header extension of a CompiledMethod. These are also found after a message lookup.

The first path to a primitive routine was represented by the call on specialSelectorPrimitiveResponse in the sendSpecialSelectorBytecode routine. The specialSelectorPrimitiveResponse routine selects an appropriate primitive routine and returns true if a primitive response was successfully made and false otherwise. Recall that the sendSpecialSelectorBytecode routine looks up the special selector if specialSelectorPrimitiveResponse returns false.

### specialSelectorPrimitiveResponse

```pascal
self initPrimitive.
(currentBytecode between: 176 and: 191)
    ifTrue: [ self arithmeticSelectorPrimitive ].
(currentBytecode between: 192 and: 207)
    ifTrue: [ self commonSelectorPrimitive ].
tself success
```

A primitive routine will be accessed by a special arithmetic selector only if the receiver is a SmallInteger. The actual primitive routines will be described in the section on arithmetic primitives.
### arithmeticSelectorPrimitive

self success: (memory isIntegerObject: (self stackValue: 1)).

self success

ifTrue: [currentBytecode = 176 ifTrue: [↑self primitiveAdd].
          currentBytecode = 177 ifTrue: [↑self primitiveSubtract].
          currentBytecode = 178 ifTrue: [↑self primitiveLessThan].
          currentBytecode = 179 ifTrue: [↑self primitiveGreaterThan].
          currentBytecode = 180 ifTrue: [↑self primitiveLessOrEqual].
          currentBytecode = 181 ifTrue: [↑self primitiveGreaterOrEqual].
          currentBytecode = 182 ifTrue: [↑self primitiveEqual].
          currentBytecode = 183 ifTrue: [↑self primitiveNotEqual].
          currentBytecode = 184 ifTrue: [↑self primitiveMultiply].
          currentBytecode = 185 ifTrue: [↑self primitiveDivide].
          currentBytecode = 186 ifTrue: [↑self primitiveMod].
          currentBytecode = 187 ifTrue: [↑self primitiveMakePoint].
          currentBytecode = 188 ifTrue: [↑self primitiveBitShift].
          currentBytecode = 189 ifTrue: [↑self primitiveDiv].
          currentBytecode = 190 ifTrue: [↑self primitiveBitAnd].
          currentBytecode = 191 ifTrue: [↑self primitiveBitOr]]

Only five of the non-arithmetic special selectors invoke primitives without a message lookup (==, class, blockCopy, value, and value:). The primitive routine for == is found in the section on system primitives and the routine for class in storage management primitives. They are both invoked for any class of receiver. The routines for blockCopy, value, and value: are found in the section on control primitives. The routine for blockCopy: will be invoked if the receiver is a MethodContext or a BlockContext. The routines for value and value: will only be invoked if the receiver is a BlockContext.

### commonSelectorPrimitive

| receiverClass |
argumentCount ← self fetchInteger: (currentBytecode - 176) * 2 + 1
  ofObject: SpecialSelectorPointer.
receiverClass ←
  memory fetchClassOf: (self stackValue: argumentCount).
  currentBytecode = 198 ifTrue: [↑self primitiveEquivalent].
  currentBytecode = 199 ifTrue: [↑self primitiveClass].
  currentBytecode = 200
ifTrue: [self success:
  (receiverClass = ClassMethodContextPointer)
  | (receiverClass = ClassBlockContextPointer).
↑self success ifTrue: [self primitiveBlockCopy]].
(currentBytecode = 201) | (currentBytecode = 202)
  ifTrue: [self success: receiverClass = ClassBlockContextPointer.
↑self success ifTrue: [self primitiveValue]].
self primitiveFail
The second and third paths to primitive routines listed above are taken after a CompiledMethod for a message has been found. The presence of a primitive is detected by the primitiveResponse routine called in executeNewMethod. The primitiveResponse routine is similar to the specialSelectorPrimitiveResponse routine in that it returns true if a primitive response was successfully made and false otherwise. Recall that the executeNewMethod routine activates the CompiledMethod that has been looked up if primitiveResponse returns false.

### primitiveResponse

```
| flagValue thisReceiver offset |
primitiveIndex = 0
ifTrue: [flagValue ← self flagValueOf: newMethod.
          flagValue = 5
          ifTrue: [self quickReturnSelf.
                    ↑true].
          flagValue = 6
          ifTrue: [self quickInstanceLoad.
                    ↑true].
          ↑false]
ifFalse: [self initPrimitive.
           self dispatchPrimitives.
           ↑self success]
```

Flag values of 5 and 6 reach the two most commonly found primitives, a simple return of self and a simple return of one of the receiver's instance variables. Returning self is a no-op as far as the interpreter is concerned since self's object pointer occupies the same place on the stack as the message receiver that it should occupy as the message response.

### quickReturnSelf

Returning an instance variable of the receiver is almost as easy.

### quickInstanceLoad

```
| thisReceiver fieldIndex |
thisReceiver ← self popStack.
fieldIndex ← self fieldIndexOf: newMethod.
self push: (memory fetchPointer: fieldIndex
             ofObject: thisReceiver)
```

The six types of primitives in the formal specification deal with arithmetic, subscripting and streaming, storage management, control structures, input/output, and general system access. These correspond to six ranges of primitive indices. A range of primitive indices has been reserved for implementation-private primitive routines. They may be
assigned any meaning, but cannot be depended upon from interpreter to interpreter. Since these are not part of the specification, they cannot be described here.

### dispatchPrimitives

<table><tr><td>primitiveIndex &lt; 60</td><td>ifTrue: [↑self dispatchArithmeticPrimitives].</td></tr><tr><td>primitiveIndex &lt; 68</td><td>ifTrue: [↑self dispatchSubscriptAndStreamPrimitives].</td></tr><tr><td>primitiveIndex &lt; 80</td><td>ifTrue: [↑self dispatchStorageManagementPrimitives].</td></tr><tr><td>primitiveIndex &lt; 90</td><td>ifTrue: [↑self dispatchControlPrimitives].</td></tr><tr><td>primitiveIndex &lt; 110</td><td>ifTrue: [↑self dispatchInputOutputPrimitives].</td></tr><tr><td>primitiveIndex &lt; 128</td><td>ifTrue: [↑self dispatchSystemPrimitives].</td></tr><tr><td>primitiveIndex &lt; 256</td><td>ifTrue: [↑self dispatchPrivatePrimitives]</td></tr></table>

## Arithmetic Primitives

There are three sets of arithmetic primitive routines, one for SmallIntegers, one for large integers (LargePositiveIntegers and LargeNegativeIntegers), and one for Floats. The primitives for SmallIntegers and Floats must be implemented, the primitives for large integers are optional.

### dispatchArithmeticPrimitives

<table><tr><td>primitiveIndex &lt; 20</td><td>ifTrue: [↑self dispatchIntegerPrimitives].</td></tr><tr><td>primitiveIndex &lt; 40</td><td>ifTrue: [↑self dispatchLargeIntegerPrimitives].</td></tr><tr><td>primitiveIndex &lt; 60</td><td>ifTrue: [↑self dispatchFloatPrimitives]</td></tr></table>

The first set of arithmetic primitive routines all pop a receiver and argument off the stack and fail if they are not both SmallIntegers. The routines then push on the stack either the integral result of a computation or the Boolean result of a comparison. The routines that produce an integral result fail if the value cannot be represented as a SmallInteger.

### dispatchIntegerPrimitives

<table><tr><td>primitiveIndex = 1</td><td>ifTrue: [↑self primitiveAdd].</td></tr><tr><td>primitiveIndex = 2</td><td>ifTrue: [↑self primitiveSubtract].</td></tr><tr><td>primitiveIndex = 3</td><td>ifTrue: [↑self primitiveLessThan].</td></tr></table>
primitivelndex = 4 ifTrue: [↑self primitiveGreaterThan].
primitivelndex = 5 ifTrue: [↑self primitiveLessOrEqual].
primitivelndex = 6 ifTrue: [↑self primitiveGreaterOrEqual].
primitivelndex = 7 ifTrue: [↑self primitiveEqual].
primitivelndex = 8 ifTrue: [↑self primitiveNotEqual].
primitivelndex = 9 ifTrue: [↑self primitiveMultiply].
primitivelndex = 10 ifTrue: [↑self primitiveDivide].
primitivelndex = 11 ifTrue: [↑self primitiveMod].
primitivelndex = 12 ifTrue: [↑self primitiveDiv].
primitivelndex = 13 ifTrue: [↑self primitiveQuo].
primitivelndex = 14 ifTrue: [↑self primitiveBitAnd].
primitivelndex = 15 ifTrue: [↑self primitiveBitOr].
primitivelndex = 16 ifTrue: [↑self primitiveBitXor].
primitivelndex = 17 ifTrue: [↑self primitiveBitShift].
primitivelndex = 18 ifTrue: [↑self primitiveMakePoint]

The primitiveAdd, primitiveSubtract, and primitiveMultiply routines are all identical except for the arithmetic operation used, so only the primitiveAdd routine will be shown here.

**primitiveAdd**

| integerReceiver integerArgument integerResult |
integerArgument ← self popInteger.
integerReceiver ← self popInteger.
self success
    ifTrue: [integerResult ← integerReceiver + integerArgument.
              self success: (memory isIntegerValue: integerResult)].
self success
    ifTrue: [self pushInteger: integerResult]
    ifFalse: [self unPop: 2]

The primitive routine for division (associated with the selector `/`) is different than the other three arithmetic primitives since it only produces a result if the division is exact, otherwise the primitive fails. This primitive, and the next three that have to do with rounding division, all fail if their argument is 0.

**primitiveDivide**

| integerReceiver integerArgument integerResult |
integerArgument ← self popInteger.
integerReceiver ← self popInteger.
self success: integerArgument≈=0.
self success: integerReceiver \ \ integerArgument=0.
self success
    ifTrue: [integerResult ← integerReceiver//integerArgument.
              self success: (memory isIntegerValue: integerResult)].
self success
    ifTrue: [self push: (memory integerObjectOf: integerResult)]
    ifFalse: [self unPop: 2]

The primitive routine for the modulo function (associated with the se-
lector \ \) gives the remainder of a division where the quotient is al-
ways rounded down (toward negative infinity).

primitiveMod

| integerReceiver integerArgument integerResult |
integerArgument ← self popInteger.
integerReceiver ← self popInteger.
self success: integerArgument~=0.
self success
    ifTrue: [integerResult ← integerReceiver\\integerArgument.
              self success: (memory isIntegerValue: integerResult)].
self success
    ifTrue: [self pushInteger: integerResult]
    ifFalse: [self unPop: 2]

There are two primitive routines for rounding division (associated with
the selectors // and quo:). The result of // is always rounded down (to-
ward negative infinity).

primitiveDiv

| integerReceiver integerArgument integerResult |
integerArgument ← self popInteger.
integerReceiver ← self popInteger.
self success: integerArgument~=0.
self success
    ifTrue: [integerResult ← integerReceiver//integerArgument.
              self success: (memory isIntegerValue: integerResult)].
self success
    ifTrue: [self pushInteger: integerResult]
    ifFalse: [self unPop: 2]

The result of quo: is truncated (rounded toward zero).

primitiveQuo

| integerReceiver integerArgument integerResult |
integerArgument ← self popInteger.
integerReceiver ← self popInteger.
self success: integerArgument~=0.
self success
    ifTrue: [integerResult ← integerReceiver quo: integerArgument.
              self success: (memory isIntegerValue: integerResult)].
self success
ifTrue: [self pushInteger: integerResult]
ifFalse: [self unPop: 2]

The primitiveEqual, primitiveNotEqual, primitiveLessThan, primitiveLessOrEqual, primitiveGreaterThan, and primitiveGreaterOrEqual routines are all identical except for the comparison operation used, so only the primitiveEqual routine will be shown here.

### primitiveEqual

| integerReceiver integerArgument integerResult |
integerArgument ← self popInteger.
integerReceiver ← self popInteger.
self success
ifTrue: [integerReceiver = integerArgument
ifTrue: [self push: TruePointer]
ifFalse: [self push: FalsePointer]]
ifFalse: [self unPop: 2]

The primitiveBitAnd, primitiveBitOr, and primitiveBitXor routines perform logical operations on the two's-complement binary representations of SmallInteger values. They are identical except for the logical operation used, so only the primitiveBitAnd routine will be shown here.

### primitiveBitAnd

| integerReceiver integerArgument integerResult |
integerArgument ← self popInteger.
integerReceiver ← self popInteger.
self success
ifTrue: [integerResult ← integerReceiver bitAnd: integerArgument].
self success
ifTrue: [self pushInteger: integerResult]
ifFalse: [self unPop: 2]

The primitive routine for shifting (associated with the selector bitShift:) returns a SmallInteger whose value represented in two's-complement is the receiver's value represented in two's-complement shifted left by the number of bits indicated by the argument. Negative arguments shift right. Zeros are shifted in from the right in left shifts. The sign bit is extended in right shifts. This primitive fails if the correct result cannot be represented as a SmallInteger.

### primitiveBitShift

| integerReceiver integerArgument integerResult |
integerArgument ← self popInteger.
integerReceiver ← self popInteger.
self success
ifTrue: [integerResult ← integerReceiver bitShift: integerArgument.
         self success: (memory isIntegerValue: integerResult)].

self success
ifTrue: [self pushInteger: integerResult]
ifFalse: [self unPop: 2]

The primitive routine associated with the selector @ returns a new Point whose x value is the receiver and whose y value is the argument.

**primitiveMakePoint**
| integerReceiver integerArgument pointResult |
integerArgument ← self popStack.
integerReceiver ← self popStack.
self success: (memory isIntegerValue: integerReceiver).
self success: (memory isIntegerValue: integerArgument).
self success
ifTrue: [pointResult ← memory instantiateClass: ClassPointer
         withPointers: ClassPointSize.
memory storePointer: XIndex
ofObject: pointResult
withValue: integerReceiver.
memory storePointer: YIndex
ofObject: pointResult
withValue: integerArgument.
self push: pointResult]
ifFalse: [self unPop: 2]

**initializePointIndices**
XIndex ← 0.
YIndex ← 1.
ClassPointSize ← 2

The primitive indices 21 to 37 are the same as primitives 1 to 17 except that they perform their operations on large integers (instances of LargePositiveInteger and LargeNegativeInteger). There are adequate Smalltalk implementations for all of these operations so the primitive routines are optional and will not be specified in this chapter. To implement them, the corresponding Smalltalk methods should be translated into machine language routines.

**dispatchLargeIntegerPrimitives**
self primitiveFail

Instances of Float are represented in IEEE single-precision (32-bit) format. This format represents a floating point quantity as a number between one and two, a power of two, and a sign. A Float is a word-size, nonpointer object. The most significant bit of the first field indicates the sign of the number (1 means negative). The next eight most significant
bits of the first field are the 8-bit exponent of two biased by 127 (0 means an exponent of -127, 128 means an exponent of 1, and so on). The seven least significant bits of the first field are the seven most significant bits of the fractional part of the number between one and two. The fractional part is 23 bits long and its 16 least significant bits are the contents of the second field of the Float. So a Float whose fields are

SEEEEEE EFFFFFF
-FF FFFFFFF FFFFFFFF

represents the value

$$
-1^{\mathit{S}} * 2^{E-127} * 1.F
$$

0 is represented as both fields=0. The floating point primitives fail if
the argument is not an instance of Float or if the result cannot be rep-
resented as a Float. This specification of the Smalltalk-80 virtual ma-
chine does not specifically include the parts of the IEEE standard other
than the representation of floating point numbers. The implementation
of routines that perform the necessary operations on floating point val-
ues is left to the implementer.

The primitiveAsFloat routine converts its SmallInteger receiver into a
Float. The routines for primitives 41 through 50 perform the same oper-
ations as 1 through 10 or 21 through 30, except that they operate on
Floats. The primitiveTruncated routine returns a SmallInteger equal to
the value of the receiver without any fractional part. It fails if its
truncated value cannot be represented as a SmallInteger. The
primitiveFractionalPart returns the difference between the receiver and
its truncated value. The primitiveExponent routine returns the exponent
of the receiver and the primitiveTimesTwoPower routine increases the
exponent by an amount specified by the argument.

dispatchFloatPrimitives

primitivelndex = 40 ifTrue: [↑self primitiveAsFloat].

primitivelndex = 41 ifTrue: [↑self primitiveFloatAdd].

primitivelndex = 42 ifTrue: [↑self primitiveFloatSubtract].

primitivelndex = 43 ifTrue: [↑self primitiveFloatLessThan].

primitivelndex = 44 ifTrue: [↑self primitiveFloatGreaterThan].

primitivelndex = 45 ifTrue: [↑self primitiveFloatLessOrEqual].

primitivelndex = 46 ifTrue: [↑self primitiveFloatGreaterOrEqual].

primitivelndex = 47 ifTrue: [↑self primitiveFloatEqual].

primitivelndex = 48 ifTrue: [↑self primitiveFloatNotEqual].

primitivelndex = 49 ifTrue: [↑self primitiveFloatMultiply].

primitivelndex = 50 ifTrue: [↑self primitiveFloatDivide].

primitivelndex = 51 ifTrue: [↑self primitiveTruncated].
primitiveIndex = 52 ifTrue: [↑self primitiveFractionalPart].

primitiveIndex = 53 ifTrue: [↑self primitiveExponent].

primitiveIndex = 54 ifTrue: [↑self primitiveTimesTwoPower]

## Array and Stream Primitives

The second set of primitive routines are for manipulating the indexable fields of objects both directly, by subscripting, and indirectly, by streaming. These routines make use of the 16-bit positive integer routines, since the limit on indexable fields is 65534.

### dispatchSubscriptAndStreamPrimitives

primitiveIndex = 60 ifTrue: [↑self primitiveAt].

primitiveIndex = 61 ifTrue: [↑self primitiveAtPut].

primitiveIndex = 62 ifTrue: [↑self primitiveSize].

primitiveIndex = 63 ifTrue: [↑self primitiveStringAt].

primitiveIndex = 64 ifTrue: [↑self primitiveStringAtPut].

primitiveIndex = 65 ifTrue: [↑self primitiveNext].

primitiveIndex = 66 ifTrue: [↑self primitiveNextPut].

primitiveIndex = 67 ifTrue: [↑self primitiveAtEnd]

The following routines are used to check the bounds on subscripting operations and to perform the subscripting accesses. They determine whether the object being indexed contains pointers, 16-bit integer values, or 8-bit integer values, in its indexable fields. The check-IndexableBoundsOf:in: routine takes a one-relative index and determines whether it is a legal subscript of an object. It must take into account any fixed fields.

### checkIndexableBoundsOf: index in: array

| class |

class ← memory fetchClassOf: array.

self success: index > = 1.

self success: index + (self fixedFieldsOf: class) < = (self lengthOf: array)

### lengthOf: array

(self isWords: (memory fetchClassOf: array))

ifTrue: [↑memory fetchWordLengthOf: array]

ifFalse: [↑memory fetchByteLengthOf: array]

The subscript:with: and subscript:with:storing: routines assume that the number of fixed fields has been added into the index, so they use it as a one-relative index into the object as a whole.
**subscript: array with: index**

| class value |
class ← memory fetchClassOf: array.
(self isWords: class)
ifTrue: [(self isPointers: class)
    ifTrue: [↑memory fetchPointer: index - 1
              ofObject: array]
    ifFalse: [value ← memory fetchWord: index - 1
              ofObject: array.
              ↑self positive16BitIntegerFor: value]]
ifFalse: [value ← memory fetchByte: index - 1
              ofObject: array.
              ↑memory integerObjectOf: value]

**subscript: array with: index storing: value**

| class |
class ← memory fetchClassOf: array.
(self isWords: class)
ifTrue: [(self isPointers: class)
    ifTrue: [↑memory storePointer: index - 1
              ofObject: array
              withValue: value]
    ifFalse: [self success: (memory isIntegerObject: value).
              self success ifTrue:
                [↑memory
                  storeWord: index - 1
                  ofObject: array
                  withValue: (self positive16BitValueOf:
                    value)]]]
ifFalse: [self success: (memory isIntegerObject: value).
              self success ifTrue:
                [↑memory storeByte: index - 1
                  ofObject: array
                  withValue: (self lowByteOf:
                    (memory integerValueOf:
                      value))]]

The primitiveAt and primitiveAtPut routines simply fetch or store one of the indexable fields of the receiver. They fail if the index is not a SmallInteger or if it is out of bounds.

**primitiveAt**

| index array arrayClass result |
index ← self positive16BitValueOf: self popStack.
array ← self popStack.
arrayClass ← memory fetchClassOf: array.
self checkIndexableBoundsOf: index
in: array.
```
self success
    ifTrue: [index ← index + (self fixedFieldsOf: arrayClass).
        result ← self subscript: array
            with: index].
self success
    ifTrue: [self push: result]
    ifFalse: [self unPop: 2]
```

The `primitiveAtPut` routine also fails if the receiver is not a pointer type and the second argument is not an 8-bit (for byte-indexable objects) or 16-bit (for word-indexable objects) positive integer. The primitive routine returns the stored value as its value.

### primitiveAtPut
```
| array index arrayClass value result |
value ← self popStack.
index ← self positive16BitValueOf: self popStack.
array ← self popStack.
arrayClass ← memory fetchClassOf: array.
self checkIndexableBoundsOf: index
    in: array.
self success
    ifTrue: [index ← index + (self fixedFieldsOf: arrayClass).
        self subscript: array
            with: index
            storing: value].
self success
    ifTrue: [self push: value]
    ifFalse: [self unPop: 3]
```

The `primitiveSize` routine returns the number of indexable fields the receiver has (i.e., the largest legal subscript).

### primitiveSize
```
| array class length |
array ← self popStack.
class ← memory fetchClassOf: array.
length ← self positive16BitIntegerFor:
    (self lengthOf: array) - (self fixedFieldsOf: class).
self success
    ifTrue: [self push: length]
    ifFalse: [self unPop: 1]
```

The `primitiveStringAt` and `primitiveStringAtPut` routines are special responses to the `at:` and `at:put:` messages by instances of `String`. A `String`
actually stores 8-bit numbers in byte-indexable fields, but it communi-
cates through the at: and at:put: messages with instances of Character. A
Character has a single instance variable that holds a SmallInteger. The
value of the SmallInteger returned from the at: message is the byte
stored in the indicated field of the String. The primitiveStringAt routine
always returns the same instance of Character for any particular value.
It gets the Characters from an Array in the object memory that has a
guaranteed object pointer called characterTablePointer.

primitiveStringAt

| index array ascii character |
index -> self positive16BitValueOf: self popStack.
array -> self popStack.
self checkIndexableBoundsOf: index
  in: array.
self success
  ifTrue: [ascii -> memorychtementer: (self subscript: array
                                           with: index).
            character -> memory fetchPointer: ascii
            ofObject: CharacterTablePointer].
self success
  ifTrue: [self push: character]
  ifFalse: [self unPop: 2]
initializeCharacterIndex
CharacterValueIndex -> 0

The primitiveStringAtPut routine stores the value of a Character in one of
the receiver's indexable bytes. It fails if the second argument of the
at:put: message is not a Character.

primitiveStringAtPut

| index array ascii character |
character -> self popStack.
index -> self positive16BitValueOf: self popStack.
array -> self popStack.
self checkIndexableBoundsOf: index
  in: array.
self success: (memory fetchClassOf: character) = ClassCharacterPointer.
self success
  ifTrue: [ascii -> memory fetchPointer: CharacterValueIndex
            ofObject: character.
            self subscript: array
            with: index
            storing: ascii].
self success
  ifTrue: [self push: character]
  ifFalse: [self unPop: 2]
The primitiveNext, primitiveNextPut, and primitiveAtEnd routines are optional primitive versions of the Smalltalk code for the next, nextPut, and atEnd messages to streams. The primitiveNext and primitiveNextPut routines only work if the object being streamed is an Array or a String.

### initializeStreamIndices

StreamArrayIndex → 0.
StreamIndexIndex → 1.
StreamReadLimitIndex → 2.
StreamWriteLimitIndex → 3

### primitiveNext

| stream index limit array arrayClass result ascii |
stream → self popStack.
array → memory fetchPointer: StreamArrayIndex
  ofObject: stream.
arrayClass → memory fetchClassOf: array.
index → self fetchInteger: StreamIndexIndex
  ofObject: stream.
limit → self fetchInteger: StreamReadLimitIndex
  ofObject: stream.
self success: index < limit.
self success:
  (arrayClass=ClassArrayPointer) | (arrayClass=ClassStringPointer).
self checkIndexableBoundsOf: index + 1
  in: array.
self success
  ifTrue: [index → index + 1.
    result → self subscript: array
      with: index].
self success
  ifTrue: [self storeInteger: StreamIndexIndex
    ofObject: stream
    withValue: index].
self success
  ifTrue: [arrayClass=ClassArrayPointer
    ifTrue: [self push: result]
    ifFalse: [ascii → memorychtValueOf: result.
      self push: (memory fetchPointer: ascii
        ofObject:
          CharacterTablePointer)]]
    ifFalse: [self unPop: 1]

### primitiveNextPut

| value stream index limit array arrayClass result ascii |
value → self popStack.
stream → self popStack.
array ← memory fetchPointer: StreamArrayIndex
         ofObject: stream.
arrayClass ← memory fetchClassOf: array.
index ← self fetchInteger: StreamIndexIndex
         ofObject: stream.
limit ← self fetchInteger: StreamWriteLimitIndex
         ofObject: stream.
self success: index < limit.
self success:
  (arrayClass=ClassArrayPointer) | (arrayClass=ClassStringPointer).
self checkIndexableBoundsOf: index + 1
  in: array.
self success
  ifTrue: [index ← index + 1.
        arrayClass=ClassArrayPointer
        ifTrue: [self subscript: array
                  with: index
                  storing: value]
        ifFalse: [ascii ← memory fetchPointer:
                   CharacterValueIndex
                   ofObject: value.
                   self subscript: array
                   with: index
                   storing: ascii]].
self success
  ifTrue: [self storeInteger: StreamIndexIndex
         ofObject: stream
         withValue: index].
self success
  ifTrue: [self push: value]
  ifFalse: [self unPop: 2]
primitiveAtEnd
  | stream array arrayClass length index limit |
  stream ← self popStack.
array ← memory fetchPointer: StreamArrayIndex
         ofObject: stream.
arrayClass ← memory fetchClassOf: array.
length ← self lengthOf: array.
index ← self fetchInteger: StreamIndexIndex
         ofObject: stream.
limit ← self fetchInteger: StreamReadLimitIndex
         ofObject: stream.
self success:
  (arrayClass=ClassArrayPointer) | (arrayClass=ClassStringPointer).
self success

ifTrue: [(index >= limit) | (index >= length)
         ifTrue: [self push: TruePointer]
         ifFalse: [self push: FalsePointer]]

ifFalse: [self unPop: 1]

## Storage Management Primitives

The storage management primitive routines manipulate the representation of objects. They include primitives for manipulating object pointers, accessing fields, creating new instances of a class, and enumerating the instances of a class.

### dispatchStorageManagementPrimitives

primitivelndex = 68 ifTrue: [↑self primitiveObjectAt].
primitivelndex = 69 ifTrue: [↑self primitiveObjectAtPut].
primitivelndex = 70 ifTrue: [↑self primitiveNew].
primitivelndex = 71 ifTrue: [↑self primitiveNewWithArg].
primitivelndex = 72 ifTrue: [↑self primitiveBecome].
primitivelndex = 73 ifTrue: [↑self primitiveInstVarAt].
primitivelndex = 74 ifTrue: [↑self primitiveInstVarAtPut].
primitivelndex = 75 ifTrue: [↑self primitiveAsOop].
primitivelndex = 76 ifTrue: [↑self primitiveAsObject].
primitivelndex = 77 ifTrue: [↑self primitiveSomelnstance].
primitivelndex = 78 ifTrue: [↑self primitiveNextlnstance].
primitivelndex = 79 ifTrue: [↑self primitiveNewMethod]

The primitiveObjectAt and primitiveObjectAtPut routines are associated with the objectAt: and objectAt:put: messages in CompiledMethod. They provide access to the object pointer fields of the receiver (the method header and the literals) from Smalltalk. The header is accessed with an index of 1 and the literals are accessed with indices 2 through the number of literals plus 1. These messages are used primarily by the compiler.

### primitiveObjectAt

| thisReceiver index |
index - self popInteger.
thisReceiver - self popStack.
self success: index > 0.
self success: index <= (self objectPointerCountOf: thisReceiver).
self success
  ifTrue: [self push: (memory fetchPointer: index - 1
                                     ofObject: thisReceiver)]
  ifFalse: [self unPop: 2]
### primitiveObjectAtPut

| thisReceiver index newValue |
- newValue ← self popStack.
- index ← self popInteger.
- thisReceiver ← self popStack.
- self success: index > 0.
- self success: index <= (self objectPointerCountOf: thisReceiver).
- self success
  - ifTrue: [memory storePointer: index - 1
    - ofObject: thisReceiver
    - withValue: newValue.
    - self push: newValue]
  - ifFalse: [self unPop: 3]

The primitiveNew routine creates a new instance of the receiver (a class) without indexable fields. The primitive fails if the class is indexable.

### primitiveNew

| class size |
- class ← self popStack.
- size ← self fixedFieldsOf: class.
- self success: (self isIndexable: class) = false.
- self success
  - ifTrue: [(self isPointers: class)
    - ifTrue: [self push: (memory instantiateClass: class
    - withPointers: size)]
    - ifFalse: [self push: (memory instantiateClass: class
    - withWords: size)]]
  - ifFalse: [self unPop: 1]

The primitiveNewWithArg routine creates a new instance of the receiver (a class) with the number of indexable fields specified by the integer argument. The primitive fails if the class is not indexable.

### primitiveNewWithArg

| size class |
- size ← self positive16BitValueOf: self popStack.
- class ← self popStack.
- self success: (self isIndexable: class).
- self success
  - ifTrue: [size ← size + (self fixedFieldsOf: class).
    - (self isPointers: class)
    - ifTrue: [self push: (memory instantiateClass: class
    - withPointers: size)]
    - ifFalse: [(self isWords: class)
    - ifTrue: [self push: (memory instantiateClass:
    - class
    - withWords: size)]]
```
ifFalse: [self push: (memory instantiateClass:
                class
                withBytes: size)]]
```

```
ifFalse: [self unPop: 2]
```

The primitive Become routine swaps the instance pointers of the receiver and argument. This means that all objects that used to point to the receiver now point to the argument and vice versa.

### primitiveBecome

```
| thisReceiver otherPointer |
otherPointer ← self popStack.
thisReceiver ← self popStack.
self success: (memory isIntegerObject: otherPointer) not.
self success: (memory isIntegerObject: thisReceiver) not.
self success
    ifTrue: [memory swapPointersOf: thisReceiver and: otherPointer.
              self push: thisReceiver]
    ifFalse: [self unpop: 2]
```

The primitive InstVarAt and primitive InstVarAtPut routines are associated with the instVarAt: and instVarAt:put: messages in Object. They are similar to primitiveAt and primitiveAtPut except that the numbering of fields starts with the fixed fields (corresponding to named instance variables) instead of with the indexable fields. The indexable fields are numbered starting with one more than the number of fixed fields. These routines need a different routine to check the bounds of the subscript.

### checkInstanceVariableBoundsOf: index in: object

```
| class |
class ← memory fetchClassOf: object.
self success: index > = 1.
self success: index < = (self lengthOf: object)
```

### primitiveInstVarAt

```
| thisReceiver index value |
index ← self popInteger.
thisReceiver ← self popStack.
self checkInstanceVariableBoundsOf: index
    in: thisReceiver.
self success
    ifTrue: [value ← self subscript: thisReceiver
              with: index].
self success
    ifTrue: [self push: value]
    ifFalse: [self unPop: 2]
```

### primitiveInstVarAtPut

```
| thisReceiver index newValue realValue |
newValue ← self popStack.
```
index ← self popInteger.
thisReceiver ← self popStack.
self checkInstanceVariableBoundsOf: index
  in: thisReceiver.
self success
  ifTrue: [self subscript: thisReceiver
            with: index
            storing: newValue].
self success
  ifTrue: [self push: newValue]
  ifFalse: [self unPop: 3]

The primitiveAsOop routine produces a SmallInteger whose value is half of the receiver's object pointer (interpreting object pointers as 16-bit signed quantities). The primitive only works for non-SmallInteger receivers. Since non-SmallInteger object pointers are even, no information in the object pointer is lost. Because of the encoding of SmallIntegers, the halving operation can be performed by setting the least significant bit of the receiver's object pointer.

### primitiveAsOop

| thisReceiver |
thisReceiver ← self popStack.
self success: (memory isIntegerObject: thisReceiver) = false.
self success
  ifTrue: [self push: (thisReceiver bitOr: 1)]
  ifFalse: [self unPop: 1]

The primitiveAsObject routine performs the inverse operation of primitiveAsOop. It only works for SmallInteger receivers (it is associated with the asObject message in SmallInteger). It produces the object pointer that is twice the receiver's value. The primitive fails if there is no object for that pointer.

### primitiveAsObject

| thisReceiver newOop |
thisReceiver ← self popStack.
newOop ← thisReceiver bitAnd: 16rFFFE.
self success: (memory hasObject: newOop).
self success
  ifTrue: [self push: newOop]
  ifFalse: [self unPop: 1]

The primitiveSomeInstance and primitiveNextInstance routines allow for the enumeration of the instances of a class. They rely on the ability of the object memory to define an ordering on object pointers, to find the first instance of a class in that ordering, and, given an object pointer, to find the next instance of the same class.
**primitiveSomeInstance**

<table><tr><td>class</td><td>self popStack.</td></tr><tr><td>(memory instancesOf:</td><td>class)</td></tr><tr><td>ifTrue:</td><td>[self push: (memory initialInstanceOf: class)]</td></tr><tr><td>ifFalse:</td><td>[self primitiveFail]</td></tr></table>

**primitiveNextInstance**

<table><tr><td>object</td><td>self popStack.</td></tr><tr><td>(memory isLastInstance:</td><td>object)</td></tr><tr><td>ifTrue:</td><td>[self primitiveFail]</td></tr><tr><td>ifFalse:</td><td>[self push: (memory instanceAfter: object)]</td></tr></table>

The `primitiveNewMethod` routine is associated with the `newMethod:header: message` in `CompiledMethod` class. Instances of `CompiledMethod` are created with a special message. Since the part of a `CompiledMethod` that contains pointers instead of bytes is indicated in the header, all `CompiledMethods` must have a valid header. Therefore, `CompiledMethods` are created with a message (`newMethod:header:`) that takes the number of bytes as the first argument and the header as the second argument. The header, in turn, indicates the number of pointer fields.

**primitiveNewMethod**

<table><tr><td>header</td><td>bytecodeCount</td><td>class</td><td>size</td></tr><tr><td>header</td><td>self popStack.</td></tr><tr><td>bytecodeCount</td><td>self popInteger.</td></tr><tr><td>class</td><td>self popStack.</td></tr><tr><td>size</td><td colspan="3">(self literalCountOfHeader: header) + 1 * 2 + bytecodeCount.</td></tr><tr><td>self push:</td><td colspan="3">(memory instantiateClass: class withBytes: size)</td></tr></table>

## Control Primitives

The control primitives provide the control structures not provided by the bytecodes. They include support for the behavior of `BlockContexts`, `Processes`, and `Semaphores`. They also provide for messages with parameterized selectors.

**dispatchControlPrimitives**

<table><tr><td>primitiveIndex</td><td>80</td><td>ifTrue:</td><td>[↑self primitiveBlockCopy].</td></tr><tr><td>primitiveIndex</td><td>81</td><td>ifTrue:</td><td>[↑self primitiveValue].</td></tr><tr><td>primitiveIndex</td><td>82</td><td>ifTrue:</td><td>[↑self primitiveValueWithArgs].</td></tr><tr><td>primitiveIndex</td><td>83</td><td>ifTrue:</td><td>[↑self primitivePerform].</td></tr><tr><td>primitiveIndex</td><td>84</td><td>ifTrue:</td><td>[↑self primitivePerformWithArgs].</td></tr><tr><td>primitiveIndex</td><td>85</td><td>ifTrue:</td><td>[↑self primitiveSignal].</td></tr></table>
primitiveIndex = 86 ifTrue: [↑self primitiveWait].

primitiveIndex = 87 ifTrue: [↑self primitiveResume].

primitiveIndex = 88 ifTrue: [↑self primitiveSuspend].

primitiveIndex = 89 ifTrue: [↑self primitiveFlushCache]

The primitiveBlockCopy routine is associated with the blockCopy: message in both BlockContext and MethodContext. This message is only produced by the compiler. The number of block arguments the new BlockContext takes is passed as the argument. The primitiveBlockCopy routine creates a new instance of BlockContext. If the receiver is a MethodContext, it becomes the new BlockContext's home context. If the receiver is a BlockContext, its home context is used for the new BlockContext's home context.

### primitiveBlockCopy

| context methodContext blockArgumentCount newContext initialIP
contextSize |
blockArgumentCount ← self popStack.
context ← self popStack.
(self isBlockContext: context)
  ifTrue: [methodContext ← memory fetchPointer: HomeIndex
            ofObject: context]
  ifFalse: [methodContext ← context].
contextSize ← memory fetchWordLengthOf: methodContext.
newContext ← memory instantiateClass: ClassBlockContextPointer
             withPointers: contextSize.
initialIP ← memory integerObjectOf: instructionPointer + 3.
memory storePointer: InitialIPIndex
  ofObject: newContext
  withValue: initialIP.
memory storePointer: InstructionPointerIndex
  ofObject: newContext
  withValue: initialIP.
self storeStackPointerValue: 0
inContext: newContext.
memory storePointer: BlockArgumentCountIndex
  ofObject: newContext
  withValue: blockArgumentCount.
memory storePointer: HomeIndex
  ofObject: newContext
  withValue: methodContext.
self push: newContext

The primitiveValue routine is associated with all "value" messages in BlockContext (value, value:, value:value:, and so on). It checks that the receiver takes the same number of block arguments that the "value" message did and then transfers them from the active context's stack to
the receiver's stack. The primitive fails if the number of arguments do not match. The `primitiveValue` routine also stores the active context in the receiver's caller field and initializes the receiver's instruction pointer and stack pointer. After the receiver has been initialized, it becomes the active context.

### primitiveValue

| blockContext | blockArgumentCount | initialIP |
|---|---|---|
| blockContext | `self stackValue:` | `argumentCount` |
| `blockArgumentCount` | `self argumentCountOfBlock:` | `blockContext` |
| `self success:` | `argumentCount` = | `blockArgumentCount` |
| `self success` | | |
| `ifTrue:` | `self transfer:` | `argumentCount` |
| | `fromIndex:` | `stackPointer-argumentCount` + 1 |
| | `ofObject:` | `activeContext` |
| | `toIndex:` | `TempFrameStart` |
| | `ofObject:` | `blockContext` |
| | `self pop:` | `argumentCount` + 1 |
| `initialIP` | `memory fetchPointer:` | `InitialIPIndex` |
| | `ofObject:` | `blockContext` |
| `memory storePointer:` | `InstructionPointerIndex` | |
| | `ofObject:` | `blockContext` |
| | `withValue:` | `initialIP` |
| `self storeStackPointerValue:` | `argumentCount` | |
| `inContext:` | `blockContext` | |
| `memory storePointer:` | `CallerIndex` | |
| | `ofObject:` | `blockContext` |
| | `withValue:` | `activeContext` |
| `self newActiveContext:` | `blockContext` | |

The `primitiveValueWithArgs` routine is associated with the `valueWithArguments:` messages in `BlockContext`. It is basically the same as the `primitiveValue` routine except that the block arguments come in a single `Array` argument to the `valueWithArguments:` message instead of as multiple arguments to the `value` message.

### primitiveValueWithArgs

| `argumentArray` | `blockContext` | `blockArgumentCount` |
|---|---|---|
| `arrayClass` | `arrayArgumentCount` | `initialIP` |
| `argumentArray` | `self popStack` | |
| `blockContext` | `self popStack` | |
| `blockArgumentCount` | `self argumentCountOfBlock:` | `blockContext` |
| `arrayClass` | `memory fetchClassOf:` | `argumentArray` |
| `self success:` | `(arrayClass = ClassArrayPointer)` | |
| `self success` | | |
| `ifTrue:` | `[arrayArgumentCount ← memory fetchWordLengthOf:` | |
| | `argumentArray` | |
| | `self success:` | `arrayArgumentCount` = `blockArgumentCount`]. |
Formal Specification of the Primitive Methods

self success
ifTrue: [self transfer: arrayArgumentCount
         fromIndex: 0
         ofObject: argumentArray
         toIndex: TempFrameStart
         ofObject: blockContext.
         initialIP ← memory fetchPointer: InitialIPIndex
         ofObject: blockContext.
         memory storePointer: InstructionPointerIndex
         ofObject: blockContext
         withValue: initialIP.
         self storeStackPointerValue: arrayArgumentCount
         inContext: blockContext.
         memory storePointer: CallerIndex
         ofObject: blockContext
         withValue: activeContext.
         self newActiveContext: blockContext]
ifFalse: [self unPop: 2]

The primitivePerform routine is associated with all "perform" messages in Object (perform:, perform:with:, perform:with:with:, and so on). It is equivalent to sending a message to the receiver whose selector is the first argument of and whose arguments are the remaining arguments. It is, therefore, similar to the sendSelector:argumentCount: routine except that it must get rid of the selector from the stack before calling executeNewMethod and it must check that the CompiledMethod it finds takes one less argument that the "perform" message did. The primitive fails if the number of arguments does not match.

primitivePerform

| performSelector newReceiver selectorIndex |
performSelector ← messageSelector.
messageSelector ← self stackValue: argumentCount-1.
newReceiver ← self stackValue: argumentCount.
self lookupMethodInClass: (memory fetchClassOf: newReceiver).
self success: (self argumentCountOf: newMethod) = (argumentCount - 1).
self success
ifTrue: [selectorIndex ← stackPointer-argumentCount + 1.
self transfer: argumentCount - 1
         fromIndex: selectorIndex + 1
         ofObject: activeContext
         toIndex: selectorIndex
         ofObject: activeContext.
self pop: 1.
argumentCount ← argumentCount - 1.
self executeNewMethod]
ifFalse: [messageSelector ← performSelector]
The primitive PerformWithArgs routine is associated with the performWithArguments: messages in Object. It is basically the same as the primitive Perform routine except that the message arguments come in a single Array argument to the performWithArguments: message instead of as multiple arguments to the "perform" message.

### primitivePerformWithArgs

| thisReceiver performSelector argumentArray arrayClass arraySize index |
|---|
| argumentArray ← self popStack. |
| arraySize ← memory fetchWordLengthOf: argumentArray. |
| arrayClass ← memory fetchClassOf: argumentArray. |
| self success: (stackPointer + arraySize) < (memory fetchWordLengthOf: activeContext). |
| self success: (arrayClass = ClassArrayPointer). |
| self success |
|   ifTrue: [performSelector ← messageSelector. |
|   messageSelector ← self popStack. |
|   thisReceiver ← self stackTop. |
|   argumentCount ← arraySize. |
|   index ← 1. |
|   [index <= argumentCount] |
|   whileTrue: [self push: (memory fetchPointer: index - 1 ofObject: argumentArray). |
|   index ← index + 1]. |
|   self lookupMethodInClass: |
|   (memory fetchClassOf: thisReceiver). |
|   self success: (self argumentCountOf: newMethod) = argumentCount. |
|   self success |
|   ifTrue: [self executeNewMethod] |
|   ifFalse: [self unPop: argumentCount. |
|   self push: messageSelector. |
|   self push: argumentArray. |
|   argumentCount ← 2. |
|   messageSelector ← performSelector]] |
|   ifFalse: [self unPop: 1] |

The next four primitive routines (for primitive indices 85 through 88) are used for communication and scheduling of independent processes. The following routine initializes the indices used to access Processes, ProcessorSchedulers, and Semaphores.

### initializeSchedulerIndices

"Class ProcessorScheduler"
ProcessListsIndex ← 0.
ActiveProcessIndex ← 1.
"Class LinkedList"
FirstLinkIndex ← 0.
LastLinkIndex ← 1.
"Class Semaphore"
ExcessSignalsIndex ← 2.
"Class Link"
NextLinkIndex ← 0.
"Class Process"
SuspendedContextIndex ← 1.
PriorityIndex ← 2.
MyListIndex ← 3

Process switching must be synchronized with the execution of bytecodes. This is done using the following four interpreter registers and the four routines: checkProcessSwitch, asynchronousSignal;, synchronousSignal;, and transferTo:.

## Process-related Registers of the Interpreter

<table><tr><td>newProcessWaiting</td><td>The newProcessWaiting register will be true if a process switch is called for and false otherwise.</td></tr><tr><td>newProcess</td><td>If newProcessWaiting is true then the newProcess register will point to the Process to be transferred to.</td></tr><tr><td>semaphoreList</td><td>The semaphoreList register points to an Array used by the interpreter to buffer Semaphores that should be signaled. This is an Array in Interpreter, not in the object memory. It will be a table in a machine-language interpreter.</td></tr><tr><td>semaphoreIndex</td><td>The semaphoreIndex register holds the index of the last Semaphore in the semaphoreList buffer.</td></tr></table>

The asynchronousSignal: routine adds a Semaphore to the buffer.

### asynchronousSignal: aSemaphore

semaphoreIndex ← semaphoreIndex + 1.
semaphoreList at: semaphoreIndex put: aSemaphore

The Semaphores will actually be signaled in the checkProcessSwitch routine which calls the synchronousSignal: routine once for each Semaphore in the buffer. If a Process is waiting for the Semaphore, the synchronousSignal: routine resumes it. If no Process is waiting, the synchronousSignal: routine increments the Semaphore's count of excess signals. The emptyList, resume, and removeFirstLinkOfList: routines are described later in this section.
**synchronousSignal: aSemaphore**

| excessSignals |
(self emptyList: aSemaphore)
ifTrue: [excessSignals -- self fetchInteger: ExcessSignalsIndex
          ofObject: aSemaphore.
self storeInteger: ExcessSignalsIndex
          ofObject: aSemaphore
          withValue: excessSignals + 1]
ifFalse: [self resume: (self removeFirstLinkOfList: aSemaphore)]

The transferTo: routine is used whenever the need to switch processes is detected. It sets the newProcessWaiting and newProcess registers.

**transferTo: aProcess**

newProcessWaiting -- true.
newProcess - aProcess

The checkProcessSwitch routine is called before each bytecode fetch (in the interpret routine) and performs the actual process switch if one has been called for. It stores the active context pointer in the old Process, stores the new Process in the ProcessorScheduler's active process field, and loads the new active context out of that Process.

**checkProcessSwitch**

| activeProcess |
[semaphoreIndex > 0]
while True:
    [self synchronousSignal: (semaphoreList at: semaphoreIndex).
semaphoreIndex - semaphoreIndex - 1].
newProcessWaiting
if True: [newProcessWaiting -- false.
activeProcess -- self activeProcess.
memory storePointer: SuspendedContextIndex
  ofObject: activeProcess
  withValue: activeContext.
memory storePointer: ActiveProcessIndex
  ofObject: self schedulerPointer
  withValue: newProcess.
self newActiveContext:
    (memory fetchPointer: SuspendedContextIndex
      ofObject: newProcess)]

Any routines desiring to know what the active process will be must take into account the newProcessWaiting and newProcess registers. Therefore, they use the following routine.
**activeProcess**

newProcessWaiting
  ifTrue: [1newProcess]
  ifFalse: [1memory fetchPointer: ActiveProcessIndex
            ofObject: self schedulerPointer]

The instance of ProcessorScheduler responsible for scheduling the actual processor needs to be known globally so that the primitives will know where to resume and suspend Processes. This ProcessorScheduler is bound to the name Processor in the Smalltalk global dictionary. The association corresponding to Processor has a guaranteed object pointer, so the appropriate ProcessorScheduler can be found.

**schedulerPointer**

1memory fetchPointer: ValueIndex
ofObject: SchedulerAssociationPointer

When Smalltalk is started up, the initial active context is found through the scheduler's active Process.

**firstContext**

newProcessWaiting - false.
1memory fetchPointer: SuspendedContextIndex
ofObject: self activeProcess

If the object memory automatically deallocates objects on the basis of reference counting, special consideration must be given to reference counting in the process scheduling routines. During the execution of some of these routines, there will be times at which there are no references to some object from the object memory (e.g., after a Process has been removed from a Semaphore but before it has been placed on one of the ProcessorScheduler's LinkedLists). If the object memory uses garbage collection, it simply must avoid doing a collection in the middle of a primitive routine. The routines listed here ignore the reference-counting problem in the interest of clarity. Implementations using reference counting will have to modify these routines in order to prevent premature deallocation of objects.

The following three routines are used to manipulate LinkedLists.

**removeFirstLinkOfList: aLinkedList**

| firstLink | lastLink | nextLink |
|---|---|---|
| firstLink | ← | memory fetchPointer: FirstLinkIndex
ofObject: aLinkedList. |
| lastLink | ← | memory fetchPointer: LastLinkIndex
ofObject: aLinkedList. |
| lastLink | = | firstLink |
| ifTrue: | [memory storePointer: FirstLinkIndex
ofObject: aLinkedList
withValue: NilPointer. |
memory storePointer: LastLinkIndex

ofObject: aLinkedList

withValue: NilPointer]

ifFalse: [nextLink ← memory fetchPointer: NextLinkIndex

ofObject: firstLink.

memory storePointer: FirstLinkIndex

ofObject: aLinkedList

withValue: nextLink].

memory storePointer: NextLinkIndex

ofObject: firstLink

withValue: NilPointer.

tfirstLink

**addLastLink: aLink toList: aLinkedList**

| lastLink |

(self emptyList: aLinkedList)

ifTrue: [memory storePointer: FirstLinkIndex

ofObject: aLinkedList

withValue: aLink]

ifFalse: [lastLink ← memory fetchPointer: LastLinkIndex

ofObject: aLinkedList.

memory storePointer: NextLinkIndex

ofObject: lastLink

withValue: aLink].

memory storePointer: LastLinkIndex

ofObject: aLinkedList

withValue: aLink.

memory storePointer: MyListIndex

ofObject: aLink

withValue: aLinkedList

**emptyList: aLinkedList**

t(memory fetchPointer: FirstLinkIndex

ofObject: aLinkedList)

= NilPointer

These three `LinkedList` routines are used, in turn, to implement the following two routines that remove links from or add links to the `ProcessorScheduler`'s `LinkedLists` of quiescent Processes.

**wakeHighestPriority**

| priority processLists processList |

processLists ← memory fetchPointer: ProcessListsIndex

ofObject: self schedulerPointer.

priority ← memory fetchWordLengthOf: processLists.

[processList ← memory fetchPointer: priority - 1

ofObject: processLists.

self is EmptyList: processList] whileTrue: [priority ← priority - 1].
```
self removeFirstLinkOfList: processList!
```

**sleep: aProcess**

```
| priority processLists processList |
```

```
priority - self fetchInteger: PriorityIndex
          ofObject: aProcess.
```

```
processLists ← memory fetchPointer: ProcessListsIndex
               ofObject: self schedulerPointer.
```

```
processList ← memory fetchPointer: priority - 1
               ofObject: processLists.
```

```
self addLastLink: aProcess
```

```
toList: processList
```

These two routines are used, in turn, to implement the following two routines that actually suspend and resume Processes.

**suspendActive**

```
self transferTo: self wakeHighestPriority
```

**resume: aProcess**

```
| activeProcess activePriority newPriority |
```

```
activeProcess ← self activeProcess.
```

```
activePriority ← self fetchInteger: PriorityIndex
               ofObject: activeProcess.
```

```
newPriority ← self fetchInteger: PriorityIndex
               ofObject: aProcess.
```

```
newPriority > activePriority
```

```
ifTrue: [self sleep: activeProcess.
         self transferTo: aProcess]
```

```
ifFalse: [self sleep: aProcess]
```

The primitiveSignal routine is associated with the signal message in Semaphore. Since it is called in the process of interpreting a bytecode, it can use the synchronousSignal: routine. Any other signaling of Semaphores by the interpreter (for example, for timeouts and keystrokes) must use the asynchronousSignal: routine.

**primitiveSignal**

```
self synchronousSignal: self stackTop.
```

The primitiveWait routine is associated with the wait message in Semaphore. If the receiver has an excess signal count greater than 0, the primitiveWait routine decrements the count. If the excess signal count is 0, the primitiveWait suspends the active Process and adds it to the receiver's list of Processes.

**primitiveWait**

```
| thisReceiver excessSignals |
```

```
thisReceiver ← self stackTop.
```

```
excessSignals ← self fetchInteger: ExcessSignalsIndex
               ofObject: thisReceiver.
```
excessSignals > 0
ifTrue: [self storeInteger: ExcessSignalsIndex
         ofObject: thisReceiver
         withValue: excessSignals - 1]
ifFalse: [self addLastLink: self activeProcess
toList: thisReceiver.
self suspendActive]

The primitive Resume routine is associated with the resume message in Process. It simply calls the resume: routine with the receiver as argument.

**primitiveResume**

self resume: self stackTop

The primitive Suspend routine is associated with the suspend message in Process. The primitive Suspend routine suspends the receiver if it is the active Process. If the receiver is not the active Process, the primitive fails.

**primitiveSuspend**

self success: self stackTop = self activeProcess.
self success
  ifTrue: [self popStack.
          self push: NilPointer.
          self suspendActive]

The primitive FlushCache routine removes the contents of the method cache. Implementations that do not use a method cache can treat this as a no-op.

**primitiveFlushCache**

self initializeMethodCache

**Input/Output Primitives**

The input/output primitive routines provide Smalltalk with access to the state of the hardware devices. Since the implementation of these routines will be dependent on the structure of the implementing machine, no routines will be given, just a specification of the behavior of the primitives.

**dispatchInputOutputPrimitives**

primitiveIndex = 90 ifTrue: [↑self primitiveMousePoint].
primitiveIndex = 91 ifTrue: [↑self primitiveCursorLocPut].
primitiveIndex = 92 ifTrue: [↑self primitiveCursorLink].
primitiveIndex = 93 ifTrue: [↑self primitiveInputSemaphore].
primitiveIndex = 94 ifTrue: [↑self primitiveSampleInterval].
primitiveIndex = 95 ifTrue: [↑self primitiveInputWord].
primitiveIndex = 96 ifTrue: [↑self primitiveCopyBits].
primitiveIndex = 97 ifTrue: [↑self primitiveSnapshot].
primitiveIndex = 98 ifTrue: [↑self primitiveTimeWordsInto].
primitiveIndex = 99 ifTrue: [↑self primitiveTickWordsInto].
primitiveIndex = 100 ifTrue: [↑self primitiveSignalAtTick].
primitiveIndex = 101 ifTrue: [↑self primitiveBeCursor].
primitiveIndex = 102 ifTrue: [↑self primitiveBeDisplay].
primitiveIndex = 103 ifTrue: [↑self primitiveScanCharacters].
primitiveIndex = 104 ifTrue: [↑self primitiveDrawLoop].
primitiveIndex = 105 ifTrue: [↑self primitiveStringReplace]

Four of the primitive routines are used to detect actions by the user. The two types of user action the system can detect are changing the state of a bi-state device and moving the pointing device. The bi-state devices are the keys on the keyboard, three buttons associated with the pointing device and an optional five-paddle keyset. The buttons associated with the pointing device may or may not actually be on the physical pointing device. Three of the four input primitive routines (primitiveInputSemaphore, primitiveInputWord, and primitiveSampleInterval) provide an *active* or *event-initiated* mechanism to detect either state change or movement. The other primitive routine (primitiveMousePoint) provides a *passive* or *polling* mechanism to detect pointing device location.

The event-initiated mechanism provides a buffered stream of 16-bit words that encode changes to the bi-state devices or the pointing device location. Each time a word is placed in the buffer, a Semaphore is signaled (using the asynchronousSignal: routine). The Semaphore to signal is initialized by the primitiveInputSemaphore routine. This routine is associated with the primInputSemaphore: message in InputState and the argument of the message becomes the Semaphore to be signaled. The primitiveInputWord routine (associated with the primInputWord message in InputState) returns the next word in the buffer, removing it from the buffer. Since the Semaphore is signaled once for every word in the buffer, the Smalltalk process emptying the buffer should send the Semaphore a wait message before sending each primInputWord message. There are six types of 16-bit word placed in the buffer. Two types specify the time of an event, two types specify state change of a bi-state device, and two types specify pointing device movement. The type of the word is stored in its high order four bits. The low order 12-bits are referred to as the *parameter*.

The six type codes have the following meanings.
<table><thead><tr><td>type code</td><td>meaning</td></tr></thead><tbody><tr><td>0</td><td>Delta time (the parameter is the number of milliseconds since the last event of any type)</td></tr><tr><td>1</td><td>X location of the pointing device</td></tr><tr><td>2</td><td>Y location of the pointing device</td></tr><tr><td>3</td><td>Bi-state device turned on (the parameter indicates which device)</td></tr><tr><td>4</td><td>Bi-state device turned off (the parameter indicates which device)</td></tr><tr><td>5</td><td>Absolute time (the parameter is ignored, the next two words in the buffer contain a 32-bit unsigned number that is the absolute value of the millisecond clock)</td></tr></tbody></table>

Whenever a device state changes or the pointing device moves, a time word is put into the buffer. A type 0 word will be used if the number of milliseconds since the last event can be represented in 12 bits. Otherwise, a type 5 event is used followed by two words representing the absolute time. Note that the Semaphore will be signaled 3 times in the latter case. Following the time word(s) will be one or more words of type 1 through 4. Type 1 and 2 words will be generated whenever the pointing device moves at all. It should be remembered that Smalltalk uses a left-hand coordinate system to talk about the screen. The origin is the upper left corner of the screen, the x dimension increases toward the right, and the y dimension increases toward the bottom. The minimum time span between these events can be set by the primitive `SampleInterval` routine which is associated with the `primSampleInterval` message in `InputState`. The argument to `primSampleInterval` specifies the number of milliseconds between movement events if the pointing device is moving constantly.

Type 3 and 4 words use the low-order eight bits of the parameter to specify which device changed state. The numbering scheme is set up to work with both decoded and undecoded keyboards. An undecoded keyboard is made up of independent keys with independent down and up transitions. A decoded keyboard consists of some independent keys and some "meta" keys (shift and escape) that cannot be detected on their
own, but that change the value of the other keys. The keys on a decoded keyboard only indicate their down transition, not their up transition. On an undecoded keyboard, the standard keys produce parameters that are the ASCII code of the character on the keytop *without* shift or control information (i.e., the key with "A" on it produces the ASCII for "a" and the key with "2" and "@" on it produces the ASCII for "2"). The other standard keys produce the following parameters.

<table><thead><tr><td>key</td><td>parameter</td></tr></thead><tbody><tr><td>backspace</td><td>8</td></tr><tr><td>tab</td><td>9</td></tr><tr><td>line feed</td><td>10</td></tr><tr><td>return</td><td>13</td></tr><tr><td>escape</td><td>27</td></tr><tr><td>space</td><td>32</td></tr><tr><td>delete</td><td>127</td></tr></tbody></table>

For an undecoded keyboard, the meta keys have the following parameters.

<table><thead><tr><td>key</td><td>parameter</td></tr></thead><tbody><tr><td>left shift</td><td>136</td></tr><tr><td>right shift</td><td>137</td></tr><tr><td>control</td><td>138</td></tr><tr><td>alpha-lock</td><td>139</td></tr></tbody></table>

For a decoded keyboard, the full shifted and "controlled" ASCII should be used as a parameter and successive type 3 and 4 words should be produced for each keystroke.

The remaining bi-state devices have the following parameters.

<table><thead><tr><td>key</td><td>parameter</td></tr></thead><tbody><tr><td>left or top "pointing device" button</td><td>128</td></tr><tr><td>center "pointing device" button</td><td>129</td></tr><tr><td>right or bottom "pointing device" button</td><td>130</td></tr><tr><td>keyset paddles right to left</td><td>131 through 135</td></tr></tbody></table>
The primitive MousePoint routine allows the location of the pointing device to be polled. It allocates a new Point and stores the location of the pointing device in its x and y fields.

The display screen is a rectangular set of pixels that can each be one of two colors. The colors of the pixels are determined by the individual bits in a specially designated instance of DisplayScreen. DisplayScreen is a subclass of Form. The instance of DisplayScreen that should be used to update the screen is designated by sending it the message beDisplay. This message invokes the primitive BeDisplay primitive routine. The screen will be updated from the last recipient of beDisplay approximately 60 times a second.

Every time the screen is updated, a *cursor* is ORed into its pixels. The cursor image is determined by a specially designated instance of Cursor. Cursor is a subclass of Form whose instances always have both width and height of 16. The instance of Cursor that should be ORed into the screen is designated by sending it the message beCursor. This message invokes the primitive BeCursor primitive routine.

The location at which the cursor image should appear is called the *cursor location*. The cursor location may be linked to the location of the pointing device or the two locations may be independent. Whether or not the two locations are linked is determined by sending a message to class Cursor with the selector cursorLink: and either true or false as the argument. If the argument is true, then the two locations will be the same; if it is false, they are independent. The cursorLink: message in Cursor's metaclass invokes the primitive CursorLink primitive routine.

The cursor can be moved in two ways. If the cursor and pointing device have been linked, then moving the pointing device moves the cursor. The cursor can also be moved by sending the message primCursorLocPut: to an instance of InputState. This message takes a Point as an argument and invokes the primitive CursorLocPut primitive routine. This routine moves the cursor to the location specified by the argument. If the cursor and pointing device are linked, the primitive CursorLocPut routine also changes the location indicated by the pointing device.

The primitive CopyBits routine is associated with the copyBits message in BitBlt and performs an operation on a bitmap specified by the receiver. This routine is described in Chapter 18.

The primitive Snapshot routine writes the current state of the object memory on a file of the same format as the Smalltalk-80 release file. This file can be resumed in exactly the same way that the release file was originally started. Note that the pointer of the active context at the time of the primitive call must be stored in the active Process on the file.

The primitive TimeWordsInto and primitive TickWordsInto routines are associated with the timeWordsInto: and tickWordsInto: messages in Sen-
sor. Both of these messages take a byte indexable object of at least four bytes as an argument. The primitiveTimeWordsInto routine stores the number of seconds since the midnight previous to January 1, 1901 as an unsigned 32-bit integer into the first four bytes of the argument. The primitiveTickWordsInto routine stores the number of ticks of the millisecond clock (since it last was reset or rolled over) as an unsigned 32-bit integer into the first four bytes of the argument.

The primitiveSignalAtTick routine is associated with the signal:atTick: messages in ProcessorScheduler. This message takes a Semaphore as the first argument and a byte indexable object of at least four bytes as the second argument. The first four bytes of the second argument are interpreted as an unsigned 32-bit integer of the type stored by the primitiveTickWordsInto routine. The interpreter should signal the Semaphore argument when the millisecond clock reaches the value specified by the second argument. If the specified time has passed, the Semaphore is signaled immediately. This primitive signals the last Semaphore to be passed to it. If a new call is made on it before the last timer value has been reached, the last Semaphore will not be signaled. If the first argument is not a Semaphore, any currently waiting Semaphore will be forgotten.

The primitiveScanCharacters routine is an optional primitive associated with the scanCharactersFrom:to:in:rightX:stopConditions:displaying message in CharacterScanner. If the function of the Smalltalk method is duplicated in the primitive routine, text display will go faster. The primitiveDrawLoop routine is similarly an optional primitive associated with the drawLoopX:Y: message in BitBit. If the function of the Smalltalk method is duplicated in the primitive routine, drawing lines will go faster.

## System Primitives

The seven final primitives are grouped together as system primitives.

### dispatchSystemPrimitives

primitiveIndex = 110 ifTrue: [↑self primitiveEquivalent].

primitiveIndex = 111 ifTrue: [↑self primitiveClass].

primitiveIndex = 112 ifTrue: [↑self primitiveCoreLeft].

primitiveIndex = 113 ifTrue: [↑self primitiveQuit].

primitiveIndex = 114 ifTrue: [↑self primitiveExitToDebugger].

primitiveIndex = 115 ifTrue: [↑self primitiveOopsLeft].

primitiveIndex = 116 ifTrue: [↑self primitiveSignalAtOopsLeftWordsLeft]
The primitiveEquivalent routine is associated with the == message in Object. It returns true if the receiver and argument are the same object (have the same object pointer) and false otherwise.

**primitiveEquivalent**

| thisObject otherObject |
otherObject ← self popStack.
thisObject ← self popStack.
thisObject=otherObject
ifTrue: [self push: TruePointer]
ifFalse: [self push: FalsePointer]

The primitiveClass routine is associated with the class message in Object.
It returns the object pointer of the receiver's class.

**primitiveClass**

| instance |
instance ← self popStack.
self push: (memory fetchClassOf: instance)

The primitiveCoreLeft routine returns the number of unallocated words in the object space. The primitiveQuit routine exits to another operating system for the host machine, if one exists. The primitiveExitToDebugger routine calls the machine language debugger, if one exists.
<figure><img src="image_294.png" /></figure>
<figure><img src="image_295.png" /></figure>

30

# Formal Specification of the Object Memory

## Heap Storage

Compaction

## The Object Table

Object Pointers

Object Table Entries

Unallocated Space

## Allocation and Deallocation

An Allocation Algorithm

A Deallocation Algorithm

A Compaction Algorithm

## Garbage Collection

A Simple Reference-counting Collector

A Space-efficient Reference-counting Collector

A Marking Collector

## Nonpointer Objects

CompiledMethods

Interface to the Bytecode Interpreter
The two major components of any Smalltalk-80 implementation are the bytecode interpreter and the object memory. Chapters 28 and 29 described an implementation of the bytecode interpreter. This chapter describes an implementation of the object memory. The function of the object memory is to create, store, and destroy objects, and to provide access to their fields.

Memory-management systems fall into two major categories, real-memory implementations and virtual-memory implementations. In a real-memory implementation, all the objects in the environment reside in primary memory that is directly addressable by the program. In a virtual-memory implementation, objects reside in more than one level of a memory hierarchy and must be shuffled among the various levels during execution. This chapter describes the design of Real-ObjectMemory, an object memory for a real-memory Smalltalk-80.

Although Smalltalk can be implemented on computers of any word size, this presentation will be simplified by several assumptions in the standard algorithms. The routines of RealObjectMemory assume

* that there are eight bits in a byte,

* that there are two bytes in a word,

* that the more significant byte of a word precedes the less significant byte, and

* that the target computer is word addressed and word indexed.

Moreover, the routines assume that the address space is partitioned into 16 or fewer segments of 64K (65,536) words apiece. The standard algorithms can be systematically changed to adapt them to hardware with different properties. The routines of RealObjectMemory deal almost exclusively with 16-bit integers, as would a machine-language implementation.

To access locations in the address space of the host machine, machine language implementations use load and store instructions. In RealObjectMemory, the load and store instructions are symbolized by messages to an instance of RealWordMemory whose name is wordMemory. The protocol of RealWordMemory is shown below

### RealWordMemory instance protocol

segment: s word: w
Return word w of segment s

segment: s word: w put: value
Store value into word w of segment s; return value.

segment: s word: w byte: byteNumber
Return byte byteNumber of word w of segment s.

segment: s word: w byte: byteNumber put: value
Store value into byte byteNumber of word w of segment s; return value.
segment: s word: w bits: firstBitIndex to: lastBitIndex
Return bits firstBitIndex to lastBitIndex of word w of segment s.

segment: s word: w bits: firstBitIndex to: lastBitIndex put: value
Store value into bits firstBitIndex to lastBitIndex of word w of segment s; return value.

When it is necessary to distinguish the two bytes of a word, the left (more significant) byte will be referred to with the index 0 and the right (less significant) byte with the index 1. The most significant bit in a word will be referred to with the index 0 and the least significant with the index 15. Note that self is an instance of class RealObjectMemory in all routines of this chapter.

The most important thing about any implementation of the object memory is that it conform to the functional specification of the object memory interface given in Chapter 27. This chapter describes a range of possible implementations of that interface. In particular, simple versions of some routines are presented early in the chapter and refined versions are presented later as the need for those refinements becomes clear. These preliminary versions will be flagged by including the comment, "**Preliminary Version**", on the first line of the routine.

## Heap Storage

In a real-memory implementation of Smalltalk, all objects are stored in an area called the *heap*. A new object is created by obtaining space to store its fields in a contiguous series of words in the heap. An object is destroyed by releasing the heap space it occupied. The format of an allocated object in the heap is shown in Figure 30.1. The actual data of the object are preceded by a two-word *header*. The size field of the header indicates the number of words of heap that the object occupies, including the header. It is an unsigned 16-bit number, and can range from 2 up to 65,536.

<figure><img src="image_296.png" /><figcaption>Figure 30.1</figcaption></figure>
When memory is segmented, it is usually convenient for a Smalltalk-80 implementation to divide the heap into *heap segments*, each in a different memory segment. As stated earlier, the routines in this chapter assume that the target computer is segmented into address spaces of 65,536 words.

## Heap Related Constants

<table><tr><td>HeapSegmentCount</td><td>The number of heap segments used in the implementation.</td></tr><tr><td>FirstHeapSegment</td><td>The index of the first memory segment used to store the heap.</td></tr><tr><td>LastHeapSegment</td><td>The index of the last memory segment used to store the heap (FirstHeapSegment + HeapSegmentCount - 1).</td></tr><tr><td>HeapSpaceStop</td><td>The address of the last location used in each heap segment.</td></tr><tr><td>HeaderSize</td><td>The number of words in an object header (2).</td></tr></table>

<figure><img src="image_297.png" /><figcaption>Figure 30.2 Fragmented Memory</figcaption></figure>

<figure><img src="image_298.png" /><figcaption>Figure 30.3 Compacted Memory</figcaption></figure>
### Compaction

Suppose for a moment that an object once allocated never changes its location in the heap. To allocate a new object, a space between existing objects must be found that is large enough to hold the new object. After a while, the memory "fragments" or "checkerboards." That is, an allocation request is bound to arrive for an amount of space smaller than the total available memory but larger than any of the disjoint pieces (Figure 30.2a). This can occur even if there is a large amount of available space and a relatively small allocation request.

Fragmentation cannot be tolerated in an interactive system that is expected to preserve a dynamic environment for hundreds of hours or more without reinitialization. Therefore when memory fragments, it must be *compacted*. Memory is compacted by moving all objects that are still in use towards one end of the heap, squeezing out all the free space between them and leaving one large unallocated block at the other end (see Figure 30.2b).

Each heap segment is compacted separately. Even on a linearly-addressed machine it is preferable to segment a large heap to reduce the duration of each compaction.

## The Object Table

When an object is moved during compaction, all pointers to its heap memory must be updated. If many other objects contain pointers directly to the old location, then it is time-consuming on a sequential computer to find and update those references to point to the new location. Therefore to make the pointer update inexpensive, only one pointer to an object's heap memory is allowed. That pointer is stored in a table called the *object table*. All references to an object must be indirect through the object table. Thus, the object pointers found in Smalltalk objects are really indices into the object table, in which pointers into the heap are in turn found (see Figure 30.3).

Indirection through the object table provides another benefit. The number of objects of average size Z addressable by an n-bit pointer is on the order of $2^n$ instead of $2^n/Z$. In our experience, objects average 10 words in size (Z~10), so a significant gain in address space can be realized by indirection.

Throughout the object table, abandoned entries can occur that are not associated with any space on the heap. These entries are called *free entries* and their object pointers are called *free pointers*. It is easy to re-cycle a free entry, because all object table entries are the same size. Compaction of the object table is difficult and generally unnecessary, so it is not supported.

Although the heap is segmented, the object table is stored in a single segment so that an object pointer can be 16 bits and thus fit in one
<figure><img src="image_299.png" /><figcaption>Figure 30.3</figcaption></figure>

word. Consequently, the number of objects that can be addressed in real memory is limited to the number of object table entries that can fit in one segment. A common arrangement is for each object table entry to occupy two words and for the entire table to occupy 64K words or less, yielding a maximum capacity of 32K objects.

An object pointer occupies 16 bits, apportioned as in Figure 30.4.

Object Pointers

<table><tr><td>Object Table Index</td><td>0</td></tr></table>

<table><caption>Figure 30.4</caption><tr><td>Immediate Signed Integer</td><td>1</td></tr></table>

When the low-order bit of the object pointer is 0, the first 15 bits are an index into the object table. Up to $2^{15}$ (32K) objects can be addressed. When the low-order bit of the object pointer is 1, the first 15 bits are an immediate signed integer, and no additional space in the object table or the heap is utilized. The benefit of giving special treatment to integers in the range $\pm 2^{14}$ is that they come and go with high frequency during arithmetic and many other operations. The cost of their efficient representation is the number of tests the interpreter must perform to distinguish object pointers of small integers from object pointers of other objects.

The `isIntegerObject` routine tests the low order bit of `objectPointer` to determine whether the rest of the pointer is an immediate integer value rather than an object table index.

**isIntegerObject: objectPointer**

$\uparrow(\mathit{objectPointer} \ \mathit{bitAnd}: \ 1) = 1$
Every other object-access routine requires that its object pointer argument really be an object table index. The `cantBeIntegerObject:` routine is used to trap erroneous calls. If the hardware, the bytecode interpreter, and the object memory manager are bug free, then this error condition is never encountered.

**cantBeIntegerObject: objectPointer**

(self isIntegerObject: objectPointer)
ifTrue: [Sensor notify: 'A small integer has no object table entry']

### Object Table Entries

The format of an object table entry is shown in Figure 30.5. If the free entry bit is on, then the entry is free. If the free entry bit is off, then the four segment bits select a heap segment and the 16 location bits locate the beginning of the space in that segment that is owned by the object table entry. The count field, the odd length bit (O), and the pointer fields bit will be explained later in the chapter.

<table><caption>Figure 30.5</caption><tr><td>COUNT</td><td>O</td><td>P</td><td>F</td><td>SEGMENT</td></tr></table>

<table><tr><td>LOCATION</td></tr></table>

### Object Table Related Constants

<table><tr><td>ObjectTableSegment</td><td>The number of the memory segment containing the object table.</td></tr><tr><td>ObjectTableStart</td><td>The location in objectTableSegment of the base of the object table.</td></tr><tr><td>ObjectTableSize</td><td>The number of words in the object table (an even number ≤ 64K).</td></tr><tr><td>HugeSize</td><td>The smallest number that is too large to represent in an eight-bit count field; that is, 256.</td></tr><tr><td>NilPointer</td><td>The object table index of the object nil</td></tr></table>

The following set of routines accesses the first word of object table entries in four different ways: loading the whole word, storing the whole word, loading a bit field, and storing a bit field. These routines in turn utilize routines of `wordMemory`, an instance of `RealWordMemory`. They assume that `objectPointer` is expressed as an even word offset relative to `objectTableStart`, the base of the object table in segment `objectTableSegment`. Note that `ot` is an abbreviation for "object table."

**ot: objectPointer**

self cantBeIntegerObject: objectPointer.
1wordMemory segment: ObjectTableSegment
word: ObjectTableStart + objectPointer
**ot: objectPointer put: value**

self cantBeIntegerObject: objectPointer.

↑wordMemory segment: ObjectTableSegment

word: ObjectTableStart + objectPointer

put: value

**ot: objectPointer bits: firstBitIndex to: lastBitIndex**

self cantBeIntegerObject: objectPointer.

↑wordMemory segment: ObjectTableSegment

word: ObjectTableStart + objectPointer

bits: firstBitIndex

to: lastBitIndex

**ot: objectPointer bits: firstBitIndex to: lastBitIndex put: value**

self cantBeIntegerObject: objectPointer.

↑wordMemory segment: ObjectTableSegment

word: ObjectTableStart + objectPointer

bits: firstBitIndex

to: lastBitIndex

put: value

The following 12 object-access subroutines load or store the various
fields of the object table entry of objectPointer.

**countBitsOf: objectPointer**

↑self ot: objectPointer bits: 0 to: 7

**countBitsOf: objectPointer put: value**

↑self ot: objectPointer bits: 0 to: 7 put: value

**oddBitOf: objectPointer**

↑self ot: objectPointer bits: 8 to: 8

**oddBitOf: objectPointer put: value**

↑self ot: objectPointer bits: 8 to: 8 put: value

**pointerBitOf: objectPointer**

↑self ot: objectPointer bits: 9 to: 9

**pointerBitOf: objectPointer put: value**

↑self ot: objectPointer bits: 9 to: 9 put: value

**freeBitOf: objectPointer**

↑self ot: objectPointer bits: 10 to: 10

**freeBitOf: objectPointer put: value**

↑self ot: objectPointer bits: 10 to: 10 put: value

**segmentBitsOf: objectPointer**

↑self ot: objectPointer bits: 12 to: 15

**segmentBitsOf: objectPointer put: value**

↑self ot: objectPointer bits: 12 to: 15 put: value

**locationBitsOf: objectPointer**

self cantBeIntegerObject: objectPointer.

↑wordMemory segment: ObjectTableSegment

word: ObjectTableStart + objectPointer + 1
**locationBitsOf: objectPointer put: value**

self cantBeIntegerObject: objectPointer.
↑wordMemory segment: ObjectTableSegment
  word: ObjectTableStart + objectPointer + 1
  put: value

For objects that occupy a chunk of heap storage (those whose free bit is 0), the following four object-access subroutines load or store words or bytes from the chunk.

**heapChunkOf: objectPointer word: offset**

↑wordMemory segment: (self segmentBitsOf: objectPointer)
  word: ((self locationBitsOf: objectPointer) + offset)

**heapChunkOf: objectPointer word: offset put: value**

↑wordMemory segment: (self segmentBitsOf: objectPointer)
  word: ((self locationBitsOf: objectPointer) + offset)
  put: value

**heapChunkOf: objectPointer byte: offset**

↑wordMemory segment: (self segmentBitsOf: objectPointer)
  word: ((self locationBitsOf: objectPointer) + (offset//2))
  byte: (offset\2)

**heapChunkOf: objectPointer byte: offset put: value**

↑wordMemory segment: (self segmentBitsOf: objectPointer)
  word: ((self locationBitsOf: objectPointer) + (offset//2))
  byte: (offset\2) put: value

The next four object-access subroutines are more specialized in that they load or store words of the object header.

**sizeBitsOf: objectPointer**

↑self heapChunkOf: objectPointer word: 0

**sizeBitsOf: objectPointer put: value**

↑self heapChunkOf: objectPointer word: 0 put: value

**classBitsOf: objectPointer**

↑self heapChunkOf: objectPointer word: 1

**classBitsOf: objectPointer put: value**

↑self heapChunkOf: objectPointer word: 1 put: value

The remaining two object-access subroutines are functionally identical to sizeBitsOf: in the versions shown below. Later in this chapter, refinements to the object-memory manager will require new versions of both of these subroutines that will return something different from the object size in certain cases. For that reason, these methods are marked "preliminary."

**lastPointerOf: objectPointer** "**Preliminary Version**"

↑self sizeBitsOf: objectPointer

**spaceOccupiedBy: objectPointer** "**Preliminary Version**"

↑self sizeBitsOf: objectPointer
## Unallocated Space

All free entries in the object table are kept on a linked list headed at the location named freePointerList. The link from one free entry to the next is an object pointer in its location field (see Figure 30.6).

<figure><img src="image_300.png" /><figcaption>Figure 30.6</figcaption></figure>

Unallocated space in the heap is grouped into *free chunks* (contiguous blocks) of assorted sizes and each of those free chunks is assigned an object table entry. Free chunks are linked together on lists, each containing chunks of the same size. The link from one free chunk to the next is in its class field (Figure 30.7). To keep the table of list heads small, all free chunks bigger than 20 words are linked onto a single list.

## Free Space Related Constants

<table><tr><td>FreePointerList</td><td>The location of the head of the linked list of free object table entries.</td></tr><tr><td>BigSize</td><td>The smallest size of chunk that is not stored on a list whose chunks are the same size. (The index of the last free chunk list).</td></tr><tr><td>FirstFreeChunkList</td><td>The location of the head of the linked list of free chunks of size zero. Lists for chunks of larger sizes are stored in contiguous locations following FirstFreeChunkList. Note that the lists at FirstFreeChunkList and FirstFreeChunkList + 1 will always be empty since all chunks are at least two words long.</td></tr><tr><td>LastFreeChunkList</td><td>The location of the head of the linked list of free chunks of size BigSize or larger.</td></tr><tr><td>NonPointer</td><td>Any sixteen-bit value that cannot be an object table index, e.g., 2<sup>16</sup> - 1.</td></tr></table>

A separate set of free chunk lists is maintained for each heap segment, but only one free pointer list is maintained for the object table. Note that the object table entry associated with a "free chunk" is not a "free
<figure><img src="image_301.png" /><figcaption>Figure 30.7</figcaption></figure>

entry.” It is not on the free pointer list, and its free entry bit is not set. The way a free chunk is distinguished from an allocated chunk is by setting the count field of the object table entry to zero for a free chunk and to nonzero for an allocated chunk.

The following four routines manage the free pointer list headed at `freePointerList` in segment `objectTableSegment`. The first two routines simply load and store the list head.

**headOfFreePointerList**

1wordMemory segment: ObjectTableSegment

word: FreePointerList

**headOfFreePointerListPut: objectPointer**

1wordMemory segment: ObjectTableSegment

word: FreePointerList

put: objectPointer

The routine `toFreePointerListAdd:` adds a free entry to the head of the list.
**toFreePointerListAdd: objectPointer**

self locationBitsOf: objectPointer
put: (self headOfFreePointerList).
self headOfFreePointerListPut: objectPointer

The routine removeFromFreePointerList removes the first entry from the list and returns it; if the list was empty, it returns nil. The distinguished value NonPointer signifies the end of a linked list. A good value for NonPointer is 2¹⁶⁻¹, a value that is easily detected on most computers and that cannot be confused with an actual object table entry address because it is an odd number.

**removeFromFreePointerList**

| objectPointer |
objectPointer ← self headOfFreePointerList.
objectPointer = NonPointer ifTrue: [↑nil].
self headOfFreePointerListPut: (self locationBitsOf: objectPointer).
↑objectPointer

The following routines manage the free-chunk lists headed at FirstFreeChunkList + 2 through LastFreeChunkList of each heap segment. Their behavior is exactly analogous to that of the routines above. The first three routines work in the segment specified or implied by their second parameter. The fourth routine works in the segment specified by the register currentSegment.

**headOfFreeChunkList: size inSegment: segment**

1wordMemory segment: segment
word: FirstFreeChunkList + size

**headOfFreeChunkList: size**

**inSegment: segment**
**put: objectPointer**

1wordMemory segment: segment
word: FirstFreeChunkList + size
put: objectPointer

**toFreeChunkList: size add: objectPointer**

| segment |
segment ← self segmentBitsOf: objectPointer.
self classBitsOf: objectPointer
put: (self headOfFreeChunkList: size inSegment: segment).
self headOfFreeChunkList: size
inSegment: segment
put: objectPointer

**removeFromFreeChunkList: size**

| objectPointer secondChunk |
objectPointer ← self headOfFreeChunkList: size
inSegment: currentSegment.
objectPointer = NonPointer ifTrue: [↑nil].
secondChunk ← self classBitsOf: objectPointer.

self headOfFreeChunkList: size
inSegment: currentSegment
put: secondChunk.

objectPointer

The routine resetFreeChunkList:inSegment: resets the specified free-chunk list to an empty list.

**resetFreeChunkList: size inSegment: segment**

self headOfFreeChunkList: size
inSegment: segment
put: NonPointer

## Allocation and Deallocation

To allocate an object, an entry is obtained from the object table and sufficient space for the header and data is obtained from some heap segment. The heap segment in which space is found is called the *current segment*. It becomes the first segment in which to look for space to allocate the next object. The only register required by the object memory holds the index of the current segment.

## Registers of the Object Memory

currentSegment

The index of the heap segment currently being used for allocation.

To allocate a "large" object requiring n words of heap space (n >= BigSize), the list beginning at LastFreeChunkList in the current segment is searched for a free chunk whose size is either n words or at least n+headerSize words. If the free chunk found is larger than n words, it is *subdivided* and only n of the words are used to satisfy the allocation request.

To allocate a "small" object requiring n words of heap space (headerSize <= n < BigSize), the list beginning at freeChunkLists+n is searched. If the list is nonempty, its first free chunk is removed and used for the new object. If the list is empty, the above algorithm for "large" objects is used.

If no chunk of sufficient size is found in the current segment, then the next segment is made current and the search continues there. The new current segment is compacted first to improve the chances of finding sufficient space. In a compacted segment, all the allocated objects are at one end and the (presumably large) space at the other end is all
in one large chunk, the sole member of the list `LastFreeChunkLists`. If enough space is not found in any segment, execution is halted.

When an object is deallocated, its space is recycled on the list of free chunks of the appropriate size. However, to simplify the presentation in this chapter, the standard algorithms leave the unused part of any subdivided chunk on the list of big free chunks even if that part is small in size.

An Allocation Algorithm

The `allocate:class`: routine is presented below as an example of a simple allocation routine. It takes as parameters the size of the desired chunk (in words, including header) and the class of the object that chunk will represent. The actual allocation routine takes several other parameters and so the `allocate:class`: routine will be flagged as preliminary. A more complete routine, `allocate:extra:class:`, is presented in a later section and the actual routine used in the implementation, `allocate:odd:pointer:-extra:class`, is presented after that.

**allocate: size class: classPointer "*Preliminary Version*"**

| objectPointer |
objectPointer ← self allocateChunk: size. "actually allocate"
self classBitsOf: objectPointer put: classPointer. "fill in class"
"initialize all fields to the object table index of the object nil"
(headerSize to: size - 1) do:
    [ :i | self heapChunkOf: objectPointer word: i put: NilPointer].
self sizeBitsOf: objectPointer put: size.
"return the new object's pointer"
tobjectPointer

The routine `allocateChunk`: either succeeds in its allocation task, or it reports an unrecoverable error. It uses a subroutine, `attempt-ToAllocateChunk:`, that either completes the job or returns `nil` if no space can be found.

**allocateChunk: size "*Preliminary Version*"**

| objectPointer |
objectPointer ← self attemptToAllocateChunk: size.
objectPointer isNil ifFalse: [tobjectPointer].
tself error: 'Out of memory'

The `attemptToAllocateChunk`: routine first tries to allocate in `currentSegment`, the segment currently targeted for allocations. It does so using the subroutine `attemptToAllocateChunkInCurrentSegment`. If the subroutine fails (returns `nil`), then the routine compacts the next segment and retries the allocation there. This procedure continues until the original segment has been compacted and searched. If no space can be found anywhere, the routine returns `nil`. Note that it uses implementation-dependent constants: `HeapSegmentCount`, `FirstHeapSegment`, and `LastHeapSegment`.
### attemptToAllocateChunk: size

```pascal
| objectPointer |
objectPointer ← self attemptToAllocateChunkInCurrentSegment: size.
objectPointer isNil ifFalse: [↑objectPointer].
1 to: HeapSegmentCount do:
  [ :i |
    currentSegment ← currentSegment + 1.
    currentSegment > LastHeapSegment
      ifTrue: [currentSegment ← FirstHeapSegment].
    self compactCurrentSegment.
    objectPointer
      ← self attemptToAllocateChunkInCurrentSegment: size.
    objectPointer isNil ifFalse: [↑objectPointer].]
↑nil
```

The `attemptToAllocateChunkInCurrentSegment:` routine searches the current heap segment's free-chunk lists for the first chunk that is the right size or that can be subdivided to yield a chunk of the right size. Because most objects are smaller than `BigSize` and most allocation requests can be satisfied by recycling deallocated objects of the desired size, most allocations execute only the first four lines of the routine.

### attemptToAllocateChunkInCurrentSegment: size

```pascal
| objectPointer predecessor next availableSize excessSize newPointer |
size < BigSize
  ifTrue: [objectPointer ← self removeFromFreeChunkList: size].
objectPointer notNil
  ifTrue: [↑objectPointer]. "small chunk of exact size handy so use it"
predecessor ← NonPointer.
  "remember predecessor of chunk under consideration"
objectPointer ← self headOfFreeChunkList: LastFreeChunkList
  inSegment: currentSegment.
  "the search loop stops when the end of the linked list is encountered"
[objectPointer = NonPointer] whileFalse:
  [availableSize ← self sizeBitsOf: objectPointer.
  availableSize = size
  ifTrue: "exact fit — remove from free chunk list and return"
  [next ← self classBitsOf: objectPointer.
    "the link to the next chunk"
predecessor = NonPointer
  ifTrue: "it was the head of the list; make the next item the head"
  [self headOfFreeChunkList: LastFreeChunkList
    inSegment: currentSegment put: next]
  ifFalse: "it was between two chunks; link them together"
  [self classBitsOf: predecessor
    put: next].
↑objectPointer].
```
"this chunk was either too big or too small; inspect the amount of variance"
excessSize ← availableSize-size.
excessSize > = HeaderSize
if True: "can be broken into two usable parts: return the second part"
["obtain an object table entry for the second part"
newPointer ← self obtainPointer: size
location: (self locationBitsOf: objectPointer)
+ excessSize.
newPointer isNil if True: [↑nil].
"correct the size of the first part (which remains on the free list)"
self sizeBitsOf: objectPointer put: excessSize.
↑newPointer]
if False: "not big enough to use; try the next chunk on the list"
[predecessor ← objectPointer.
objectPointer ← self classBitsOf: objectPointer]].
↑nil "the end of the linked list was reached and no fit was found"

The subroutine `obtainPointer:location:` used by the above routine obtains a free object table entry, zeroes its free entry bit as well as the rest of the first word of the entry, points the entry at the specified location, and sets the size field of the header to the specified size.

**obtainPointer: size location: location**

| objectPointer |
objectPointer ← self removeFromFreePointerList.
objectPointer isNil if True: [↑nil].
self ot: objectPointer put: 0.
self segmentBitsOf: objectPointer put: currentSegment.
self locationBitsOf: objectPointer put: location.
self sizeBitsOf: objectPointer put: size.
↑objectPointer

A Deallocation Algorithm

It is much simpler to deallocate an object than to allocate one. The chunk is recycled on a free-chunk list. The following routine expects the count field to have been reset to zero by a higher-level routine.

**deallocate: objectPointer** "**Preliminary Version**"

| space |
space ← self spaceOccupiedBy: objectPointer.
self toFreeChunkList: (space min: BigSize)
add: objectPointer

Note that this routine computes the space occupied by the object using `spaceOccupiedBy:` instead of `sizeBitsOf:`. The reason will become clear later in the chapter when `spaceOccupiedBy:` is redefined.
A Compaction
Algorithm

The `compactCurrentSegment` routine invoked above by `attemptToAllocateChunk`: sweeps through a heap segment, massing all allocated objects together and updating their object table entries. For the benefit of subsequent allocation, it also links the object table entries reclaimed from the free chunk lists onto the free pointer list and creates a single free chunk from the unused portion of the heap segment. The algorithm for `compactCurrentSegment` will be presented shortly, after some preparatory discussion.

After a heap segment is compacted a number of times, relatively permanent objects sift to the bottom of the segment and most allocation and deallocation activity occurs nearer to the top. The segment consists of a densely packed region of allocated chunks, followed by a region of both allocated and free chunks. During compaction, chunks in the densely packed region never move, because there is no space beneath them to eliminate. Therefore, the compacter expends effort only on chunks above the first free chunk, whose location is referred to as `lowWaterMark`.

The `abandonFreeChunksInSegment`: routine computes `lowWaterMark`. It also finds all deallocated chunks, recycles their object table entries onto the list of free pointers using the subroutine `releasePointer:`, and changes their class fields to the distinguished value `nonPointer`. During the subsequent sweep, when the compacter encounters objects so marked it can recognize them as deallocated chunks.

**abandonFreeChunksInSegment: segment**

```
| lowWaterMark objectPointer nextPointer |
lowWaterMark ← HeapSpaceStop. "first assume that no chunk is free"
HeaderSize to: BigSize do: "for each free-chunk list"
[ :size |
  objectPointer ← self headOfFreeChunkList: size
               inSegment: segment.
  [objectPointer = NonPointer] whileFalse:
    [lowWaterMark ← lowWaterMark
               min: (self locationBitsOf: objectPointer).
               nextPointer ← self classBitsOf: objectPointer.
               "link to next free chunk"
               self classBitsOf: objectPointer put: NonPointer.
               "distinguish for sweep"
               self releasePointer: objectPointer.
               "add entry to free-pointer list"
             objectPointer ← nextPointer].
  self resetFreeChunkList: size inSegment: segment].
lowWaterMark
```

**releasePointer: objectPointer**

```
self freeBitOf: objectPointer put: 1.
self toFreePointerListAdd: objectPointer
```
A heap segment is compacted by sweeping through it from bottom to top. Each allocated object is moved as far down in the segment as possible without overwriting other allocated objects. For each object moved, the corresponding object table entry is found and its location field is updated to point to the new location of the object.

It is by no means trivial to find the object table entry of an object en-
countered during a sweep of the heap segment. The representation of
the object in the heap does not include a pointer back to the object ta-
ble entry. To avoid the cost of such a backpointer for every object or
making the compacter search the object table after every object is
moved, a trick called "reversing pointers" is employed. During compac-
tion, instead of the usual arrangement in which the object table entry
points to the header in the heap, the header points temporarily to the
object table entry.

Pointers are reversed before starting to sweep through a heap seg-
ment. The object table is scanned to find every in-use entry whose seg-
ment field refers to the segment being compacted and whose location
field is above lowWaterMark. Each such entry points to the header of an
object that is to be moved (Figure 30.8a). The pointer is then reversed,
i.e., the object's own object pointer is stored in the first word of its
header. This causes the header to point to the object table entry. By do-
ing this, the size field of the header is overwritten. To prevent losing
the size, it is saved in the second word of the object table entry (Figure
30.8b). By doing that, the location field is overwritten, but that is of no

<figure><img src="image_302.png" /><figcaption>Figure 30.8</figcaption></figure>
consequence, because the compacter recomputes the object's heap location after the move.

**reverseHeapPointersAbove: lowWaterMark**

| size |
0 to: ObjectTableSize-2 by: 2 do:
[ :objectPointer |
(self freeBitOf: objectPointer) = 0
ifTrue: "the Object Table entry is in use"
[(self segmentBitsOf: objectPointer) = currentSegment
ifTrue: "the object is in this segment"
[(self locationBitsOf: objectPointer) < lowWaterMark
ifFalse: "the object will be swept"
FUNTION
"rescue the size"
self sizeBitsOf: objectPointer
put: objectPointer. "reverse the pointer"
self locationBitsOf: objectPointer
put: size "save the size"]]]

After all preparations for compaction are complete, the current heap segment is swept using the `sweepCurrentSegmentFrom:` routine. It maintains two pointers into the segment, `si` (source index) and `di` (destination index). The pointer `si` points to the header of an object currently being considered for retention or elimination. The pointer `di` points to the location where that object will be moved if retained.

**sweepCurrentSegmentFrom: lowWaterMark**

| si di objectPointer size space |
si ← di ← lowWaterMark.
[si < HeapSpaceStop]
whileTrue: "for each object, si"
[(wordMemory segment: currentSegment word: si + 1) = NonPointer
ifTrue: "unallocated, so skip it"
FUNTION
FUNTION
si ← si + size]
ifFalse: "allocated, so keep it, but move it to compact storage"
[objectPointer
← wordMemory
segment: currentSegment word: si.
size ← self locationBitsOf: objectPointer.
"the reversed size"
self locationBitsOf: objectPointer
put: di. "point object table at new location"
self sizeBitsOf: objectPointer
put: size. "restore the size to its proper place"
si ← si + 1. "skip the size"
di ← di + 1. "skip the size"
2 to: (self spaceOccupiedBy: objectPointer) do:
    "move the rest of the object"
[ :i |
    wordMemory segment: currentSegment
    word: di
    put: (wordMemory segment:
        currentSegment
        word: si).
    si ← si + 1.
    di ← di + 1]]].
tdi

Note that while pointers are reversed, it is impossible to access the
heap memory of an object from its object table entry. Therefore the
Smalltalk interpreter cannot run during compaction.

The compactCurrentSegment routine invokes the above routines in
the proper order and then creates the single free chunk at the top of
the heap segment.

### compactCurrentSegment

| lowWaterMark bigSpace |
lowWaterMark ← self abandonFreeChunksInSegment: currentSegment.
lowWaterMark < HeapSpaceStop
ifTrue:
    [self reverseHeapPointersAbove: lowWaterMark.
     bigSpace ← self sweepCurrentSegmentFrom: lowWaterMark.
     self deallocate: (self obtainPointer:
         (HeapSpaceStop + 1 - bigSpace)
         location: bigSpace)]

If there are no free chunks within the segment when this routine is in-
voked, then it does not move any objects.

## Garbage Collection

In Smalltalk, a new object is allocated explicitly (e.g., when the message new is sent to a class) but there is no explicit language construct that causes an object to be deallocated. Such a construct would be unsafe, because it could be used to deallocate an object even though "dangling" references to it still existed in other objects. An environment containing dangling references would be inconsistent and would be likely to exhibit unintended behavior and to suffer unrecoverable errors.

Most noninteractive programming systems require explicit deallocation. The burden of avoiding dangling references is placed on the programmer. If a dangling reference arises, the programmer is
expected to find the bug that created it, fix that bug, and restart the program. In an interactive environment like Smalltalk (as well as most LISP and APL systems), to require a restart because of a common bug would be unacceptable, since it could require the user to redo a potentially large amount of work.

Because there is no explicit deallocation in Smalltalk, the memory manager must identify objects that have become *inaccessible* and deallocate them automatically. This task is traditionally known as *garbage collection*. As compared with explicit deallocation, garbage collection entails a large performance penalty. The penalty is incurred because the computer must manage deallocation at execution time instead of relying on the programmer to have done so during coding time. However, the cost is well worth the reliability it adds to an interactive system.

There are two traditional approaches to identifying inaccessible objects in an object memory: *marking* and *reference counting*. A marking garbage collector performs an exhaustive search of memory for accessible objects and marks them all. Then it scans memory in search of objects that are unmarked and thus inaccessible and deallocates them. A reference-counting garbage collector maintains a count of how many references there are to each object from other objects. When the count of references to some object reaches zero, that object is known to be inaccessible, and the space it occupies can be reclaimed.

Reference-counting systems do not deal with so-called "cyclic structures." Such a structure is said to occur when an object references itself directly or when an object references itself indirectly via other objects that reference it. In a reference-counting system, when a cyclic structure becomes inaccessible to the program, it will have non-zero reference counts due to the intrastructure references. Therefore the memory manager doesn't recognize that the structure should be deallocated, and the objects that constitute the structure are not deallocated. These inaccessible objects waste space; but, unlike dangling references, they do not cause inconsistency in the environment.

Both reference counting and marking involve performance penalties on conventional computers. In a reference-counting system, the frequently performed operation of storing a reference to an object involves overhead for reference-count maintenance, so programs run significantly more slowly. In a marking garbage collector, an extensive search of memory must be performed whenever space is entirely depleted. Therefore, program execution is subject to relatively lengthy interruptions that can be quite annoying in an interactive system. Both approaches incur space overhead. In a reference-counting system, space must be provided to store reference counts. In a marking system, extra space must be allotted in the heap to allow garbage to accumulate between collections. Otherwise, collections occur too frequently.
The approach to garbage collection that should be used in a particu-
lar implementation of Smalltalk depends in part on the capacity of the
hardware. If a relatively small amount of memory (e.g., 100 kilobytes) is
available, a reference counting system is intolerable, because it can
waste precious space by leaving inaccessible cyclic structures allocated.
On the other hand, a marking collector is quite acceptable in these cir-
cumstances, in spite of the interruption that occurs when it is invoked,
because when memory is small, the duration of the interruption can be
so brief as to be imperceptible. If an abundant supply of memory (e.g.,
two megabytes) is available, the time it takes to mark all accessible ob-
jects can be so long as to be intolerable. On the other hand, there is
enough space available that a moderate number of inaccessible objects
can be tolerated.

The contrast between the two approaches is accentuated in a large
virtual-memory system. Marking is even more costly because so much
time is spent in random accesses to secondary memory. Reference
counting is even less costly because unreclaimed cyclic structures sim-
ply migrate to secondary memory where wasted space is less bother-
some. When memory is abundant, a reference-counting garbage
collector is appropriate. However, Smalltalk programmers should take
precautions to avoid the accumulation of an excessive number of inac-
cessible cyclic structures, otherwise even a large memory will be deplet-
ed. To break a cyclic structure before it becomes inaccessible, the
program can change any pointer that participates in the cycle to nil.

The two approaches to garbage collection can be combined. Refer-
ences can be counted during normal operation and marking collections
performed periodically to reclaim inaccessible cyclic structures. A com-
bined approach is suitable for all but the smallest real-memory imple-
mentations. If a small-to-medium-size memory is available, a marking
collection can be performed whenever compaction fails to recover
enough space. If an abundant memory is available, marking collections
can be performed nightly or at other convenient intervals.

In the reference-counting collector described in this chapter, the refer-
ence count of an object is recorded in the count field of its object table
entry. If an object pointer is an immediate integer, it is its own only
reference, so its reference count is not recorded explicitly. Reference
counts are updated during store operations. When an object pointer ref-
erencing object *P* is stored into a location that formerly contained an
object pointer referencing object *Q*, the count field of *P* is incremented
and the count field of *Q* is decremented. Because the count field of an
object table entry has only eight bits, it is possible for an incremented
count to overflow. To facilitate overflow detection on most computers,
the high order bit of the count field serves as an overflow bit. Once the
count field reaches 128, it remains at that value and it will not increase or decrease. The algorithm for incrementing a reference count is

**countUp: objectPointer**

| count |
(self isIntegerObject: objectPointer)
ifFalse:
    [count ← (self countBitsOf: objectPointer) + 1.
     count < 129 ifTrue: [self countBitsOf: objectPointer put: count]].
↑objectPointer

If the decremented reference count of an object reaches zero, then that object is deallocated. Before doing so, the count field of every object referenced from that object is decremented, because once the object is deallocated it will no longer reference those other objects. Note that this procedure recurs if any of the latter counts reach zero. A recursive procedure that can traverse the original object plus all the objects it references is expressed below as the routine `forAllObjectsAccessibleFrom: - suchThat:do:`. This routine takes two procedural arguments represented by blocks, a **predicate** that decrements a count and tests for zero and an **action** that deallocates an object. Between evaluating the predicate and the action, the procedure's subroutine, `forAllOtherObjectsAccessibleFrom: - suchThat:do:`, recursively processes every pointer in the object. The procedure is allowed to alter the count as a side effect, so the action argument must restore the count to zero in preparation for deallocation.

**countDown: rootObjectPointer**

| count |
(self isIntegerObject: rootObjectPointer)
ifTrue: [↑rootObjectPointer]
ifFalse: "this is a pointer, so decrement its reference count"
[↑self forAllObjectsAccessibleFrom: rootObjectPointer
  suchThat:
    "the predicate decrements the count and tests for zero"
    [ :objectPointer |
      count ← (self countBitsOf: objectPointer) - 1.
      count < 127
      ifTrue: [self countBitsOf: objectPointer
                put: count].
      count = 0]
    do: "the action zeroes the count and deallocates the object"
    [ :objectPointer |
      self countBitsOf: objectPointer put: 0.
      self deallocate: objectPointer]]

The traversal routine shown below first tests the predicate on the supplied object. It then invokes a subroutine that (1) recursively processes
all objects referenced from within the supplied object that satisfy predicate, and (2) performs action on the supplied object.

**forAllObjectsAccessibleFrom: objectPointer**

**suchThat: predicate**

**do: action**

(predicate value: objectPointer)

ifTrue:

[↑self forAllOtherObjectsAccessibleFrom: objectPointer

suchThat: predicate

do: action]

**forAllOtherObjectsAccessibleFrom: objectPointer**

**suchThat: predicate**

**do: action**

| next |

1 to: (self lastPointerOf: objectPointer) - 1 do:

[ :offset |

next ← self heapChunkOf: objectPointer word: offset.

((self isIntegerObject: next) == false and: [predicate value: next])

ifTrue: "it's a non-immediate object and it should be processed"

[self forAllOtherObjectsAccessibleFrom: next

suchThat: predicate

do: action]].

"all pointers have been followed; now perform the action"

action value: objectPointer.

↑objectPointer

*A Space-efficient Reference-counting Collector*

The traversal algorithm outlined above is recursive and, therefore, must use a stack in its execution. To guard against stack overflow, the depth of the stack must be greater than the longest chain of pointers in memory. This requirement is difficult to satisfy when memory space is limited. To guarantee that enough space is available, the pointer chain itself can be used as the stack. If object A references object B from A's i-th field, and object B references object C from B's j-th field, and object C references another object from C's k-th field, and so on, the pointer chain can be represented as A.i → B.j → C.k → ... (Figure 30.9a). To use the pointer chain as a stack for the recursion of the traversal algorithm, the chain is temporarily reversed to ... → C.k → B.j → A.i so that each field in the chain points to its predecessor instead of to its successor (Figure 30.9b).

Each step of the traversal algorithm's recursion must be completed by "popping the stack." After processing any object in the chain (e.g., C), its predecessor (e.g., B) is found by following the reversed pointer chain. The algorithm also needs to know which field of the predecessor was being worked on. To maintain this information, the algorithm must be changed at the earlier stage where it left B to process C. At that stage, the index of the field, j, is copied into the count field of the object table
<figure><img src="image_303.png" /><figcaption>Figure 30.9</figcaption></figure>

entry of *B*. The count can be overwritten because the object is being deallocated. But if the size of *B* exceeds 255 words, then the count field will not be large enough to store every field index. Instead, the allocator is revised to over-allocate by one word any object that is HugeSize (256) words or more and to reserve that extra word for use by the transversal algorithm to store *offset*.

To accommodate over-allocation, the allocation routine is revised to accept an additional argument, extraWord, that is either 0 or 1. It is also necessary for the allocator to increment the reference count of the new object's class before storing the class into the header of the new object. (In fact, this must be accomplished even earlier, before calling allocateChunk, to assure that the class is not deallocated accidentally by some side effect of that subroutine.)

allocate: size extra: extraWord class: classPointer

**"*Preliminary Version**"**

| objectPointer |

self countUp: classPointer.

"increment the reference count of the class"

objectPointer ← self allocateChunk: size + extraWord.

"allocate enough"

self classBitsOf: objectPointer put: classPointer.
HeaderSize to: size-1 do:

[ :i | self heapChunkOf: objectPointer word: i put: NilPointer].

"the next statement to correct the SIZE need only be executed if
extraWord > 0"

self sizeBitsOf: objectPointer put: size.

↑objectPointer

The actual heap space occupied by an object with at least HugeSize
fields is one greater than that stated in its size field, because of the ex-
tra word allocated. Therefore, the spaceOccupiedBy: routine must be
changed to account for the difference.

**spaceOccupiedBy: objectPointer** "***Preliminary Version***"

| size |

size ← self sizeBitsOf: objectPointer.

size < HugeSize

ifTrue: [↑size]

ifFalse: [↑size + 1]

The deallocation algorithm must also be revised because deallocated ob-
jects have no provision for an extra word not counted in the size field.

**deallocate: objectPointer**

| space |

space ← self spaceOccupiedBy: objectPointer.

self sizeBitsOf: objectPointer put: space.

self toFreeChunkList: (space min: BigSize) add: objectPointer

The following routine implements the space-efficient traversal algo-
rithm, with A, B, and C of the above example represented by the vari-
ables prior, current, and next. To simplify the loop test, the method scans
the fields of each chunk in reverse order. Thus the class field is pro-
cessed last.

Note that the last statement of the method restores the pointer chain
to get *B.j* again pointing to *C* instead of to *A*. It is easy to do so when
returning to *B* from processing *C*, because object pointer of *C* can sim-
ply be stored in the *j*th field of *B*. One might think that step unneces-
sary, because *B* is being deallocated. However, the same traversal
algorithm can be used by a marking collector in which *B* is not being
deallocated.

**forAllOtherObjectsAccessibleFrom: objectPointer**

**suchThat: predicate**

**do: action**

| prior current offset size next |

"compute prior, current, offset, and size to begin processing
objectPointer"

prior ← NonPointer.
current ← objectPointer.
offset ← size ← self lastPointerOf: objectPointer.
[true] whileTrue: "for all pointers in all objects traversed"
  [(offset ← offset − 1) > 0 "decrement the field index"
   ifTrue: "the class field hasn't been passed yet"
   [next ← self heapChunkOf: current word: offset.
             "one of the pointers"
   ((self isIntegerObject: next) = false
    and: [predicate value: next])
   ifTrue: "it's a non-immediate object and it should be processed"
   ["reverse the pointer chain"
    self heapChunkOf: current word: offset put: prior.
    "save the offset either in the count field or in the extra word"
    size < HugeSize
     ifTrue: [self countBitsOf: current put: offset]
     ifFalse: [self heapChunkOf: current
                 word: size + 1 put: offset].
    "compute prior, current, offset, and size to begin processing next"
    prior ← current. current ← next.
    offset ← size ← self lastPointerOf: current]]
ifFalse:
  ["all pointers have been followed; now perform the action"
   action value: current.
   "did we get here from another object?"
   prior = NonPointer
     ifTrue: "this was the root object, so we are done"
     [↑objectPointer].
   "restore next, current, and size to resume processing prior"
   next ← current. current ← prior.
   size ← self lastPointerOf: current.
   "restore offset either from the count field or from the extra word"
   size < HugeSize
     ifTrue: [offset ← self countBitsOf: current]
     ifFalse: [offset ← self heapChunkOf: current word: size + 1].
   "restore prior from the reversed pointer chain"
   prior ← self heapChunkOf: current word: offset.
   "restore (unreverse) the pointer chain"
   self heapChunkOf: current word: offset put: next]]

The machine-language implementation can deal with the procedural arguments either by passing a pair of subroutine addresses to be called indirectly or by expanding the subroutines in line. If the hardware has enough registers, it is possible to keep the variables next, current, prior, size, and offset in registers for additional speed of execution.
## A Marking Collector

The job of the marking garbage collector is to mark all accessible objects so that the remaining inaccessible objects can be identified and added to the lists of free chunks. Accessible objects can be found most easily by a recursive search from the "roots of the world," namely, the interpreter's stacks and the table of global variables (the Dictionary named Smalltalk).

The following algorithm is performed on each root object. In the object table entry of the object, set the count field to 1 to mean "marked." Apply the algorithm of this paragraph to each unmarked object referenced by the object.

Note that the above *marking algorithm* is inherently recursive. In its implementation, the same traversal routine used for reference counting can be used, in either the simple or the space-efficient version. Before marking begins, the count fields of all objects are reset to 0 to mean "unmarked." After marking ends, all unmarked objects are deallocated and the reference counts of all marked objects are recomputed. The routine that performs all the necessary steps is called `reclaimInaccessibleObjects`.

### reclaimInaccessibleObjects

self zeroReferenceCounts.
self markAccessibleObjects.
self rectifyCountsAndDeallocateGarbage

The subroutine that sets the count fields of all objects to 0 is called `zeroReferenceCounts`. It is superfluous to zero the count field of a free chunk or of a free entry. Nevertheless, the following version zeroes the count field of every entry, because on most computers, it takes less time to zero the first byte of an entry than it takes to test the status of that entry.

### zeroReferenceCounts

0 to: ObjectTableSize-2 by: 2 do:
    [ :objectPointer |
      self countBitsOf: objectPointer put: 0 ]

The subroutine `markAccessibleObjects` invokes the marking algorithm `markObjectsAccessibleFrom:` for every object in the list `rootObjectPointers`. Typically, the list `rootObjectPointers` includes the object pointer of the current process and the object pointer of the global variable dictionary, from which all other accessible objects are referenced directly or indirectly.

### markAccessibleObjects

rootObjectPointers do:
    [ :rootObjectPointer |
      self markObjectsAccessibleFrom: rootObjectPointer]
The marking algorithm `markObjectsAccessibleFrom:` calls the same traversal routine as the reference-counting collector did. Its predicate succeeds for unmarked objects and it marks them with a count of 1 as a side effect. Its action restores the count field to 1 because the space-efficient version of the traversal routine could have changed that field to any nonzero value as a side effect.

### `markObjectsAccessibleFrom: rootObjectPointer`

```
| unmarked |
+---------+
|self forAllObjectsAccessibleFrom: rootObjectPointer
+---------+
suchThat: "the predicate tests for an unmarked object and marks it"

[ :objectPointer |
  unmarked ← (self countBitsOf: objectPointer) = 0.
  unmarked ifTrue: [self countBitsOf: objectPointer put: 1].
  unmarked]
do: "the action restores the mark to count=1"

[ :objectPointer |
  self countBitsOf: objectPointer put: 1]
```

After the marking algorithm has been executed, every non-free object table entry is examined using the subroutine `rectify-CountsAndDeallocateGarbage`. If the entry is unmarked, then the entry and its heap chunk are added to the appropriate free lists. If the entry is marked, then the count is decremented by one to unmark it, and the counts of all objects that it references directly are incremented. Note that when a marked object is processed, its count may exceed 1 because objects previously processed may have referenced it. That is why it is unmarked by subtraction instead of by setting its count to 0.

During the examination of object table entries, chunks that were already free before the marking collection began will be encountered. The count field of an already-free chunk is zero just like an unmarked object, so it will be added to a free-chunk list. Doing so would cause a problem if the chunk were already on a free-chunk list. Therefore before the scan begins, all heads of free-chunk lists are reset.

As a final step, the reference count of each root object is incremented to assure that it is not deallocated accidentally.

### `rectifyCountsAndDeallocateGarbage`

```
| count |
"reset heads of free-chunk lists"
FirstHeapSegment to: LastHeapSegment do: "for every segment"

[ :segment |
  HeaderSize to: BigSize do: "for every free chunk list"
  [ :size | "reset the list head"
    self resetFreeChunkList: size inSegment: segment]].
"rectify counts, and deallocate garbage"
```
0 to: ObjectTableSize-2 by: 2 do: "for every object table entry"

[ :objectPointer |

(self freeBitOf: objectPointer) = 0

ifTrue: "if it is not a free entry"

[(count ← self countBitsOf: objectPointer) = 0

ifTrue: "it is unmarked, so deallocate it"

[self deallocate: objectPointer]

ifFalse: "it is marked, so rectify reference counts"

[count < 128 ifTrue: "subtract 1 to compensate for the mark"

[self countBitsOf: objectPointer put: count-1].

1 to: (self lastPointerOf: objectPointer) - 1 do:

[ :offset | "increment the reference count of each
pointer"

self countUp: (self heapChunkOf: objectPointer
word: offset)]].

"be sure the root objects don't disappear"

rootObjectPointers do:

[ :rootObjectPointer | self countUp: rootObjectPointer].

self countBitsOf: NilPointer put: 128

The **allocateChunk**: routine can now be revised so that it attempts a marking collection if compaction of all segments has failed to yield enough space to satisfy an allocation request.

**allocateChunk: size**

| objectPointer |

objectPointer ← self attemptToAllocateChunk: size.

objectPointer isNil ifFalse: [↑objectPointer].

self reclaimInaccessibleObjects. "garbage collect and try again"

objectPointer ← self attemptToAllocateChunk: size.

objectPointer isNil ifFalse: [↑objectPointer].

self outOfMemoryError "give up"

**Nonpointer
Objects**

The object format presented in this chapter is not particularly space efficient, but since its uniformity makes the system software small and simple, the inefficiency can generally be forgiven. There are two classes of object for which the inefficiency is intolerable, namely, character strings and bytecoded methods. There are usually many strings and methods in memory, and when stored one character or one bytecode per word, they are quite wasteful of space.

To store such objects more efficiently, an alternate memory format is used in which the data part of an object contains 8-bit or 16-bit values
that are interpreted as unsigned integers rather than as object pointers. Such objects are distinguished by the setting of the pointer-fields bit of the object table entry: when that bit is 1, the data consist of object pointers; when that bit is 0, the data consist of positive 8- or 16-bit integers. When there are an odd number of bytes of data in a nonpointer object, the final byte of the last word is 0 (a slight waste of space), and the odd-length bit of the object table entry, which is normally 0, is set to 1. To support nonpointer objects, the allocator needs two additional parameters, pointerBit and oddBit. In the case of a nonpointer object (pointerBit=0), the default initial value of the elements is 0 instead of nil. The final version of the allocation routine is shown below.

**allocate: size**
**odd: oddBit**
**pointer: pointerBit**
**extra: extraWord**
**class: classPointer**
```
| objectPointer default |
self countUp: classPointer.
objectPointer ← self allocateChunk: size + extraWord.
self oddBitOf: objectPointer put: oddBit.
self pointerBitOf: objectPointer put: pointerBit.
self classBitsOf: objectPointer put: classPointer.
default ← pointerBit=0 ifTrue: [0] ifFalse: [NilPointer].
HeaderSize to: size-1 do:
    [ :i | self heapChunkOf: objectPointer word: i put: default].
self sizeBitsOf: objectPointer put: size.
tobjectPointer
```

The garbage-collecting traversal routines need only process the class field of each nonpointer object, because the data contain no pointers. To make this happen, the routine lastPointerOf: is changed as follows:

**lastPointerOf: objectPointer** "**Preliminary Version**"
(self pointerBitOf: objectPointer)=0
ifTrue:
    [↑HeaderSize]
ifFalse:
    [↑self sizeBitsOf: objectPointer]

The value of lastPointerOf: is never as large as 256 for a nonpointer object, so a nonpointer object never needs to be over-allocated. Therefore, spaceOccupiedBy: is revised again as follows:

**spaceOccupiedBy: objectPointer**
```
| size |
size ← self sizeBitsOf: objectPointer.
(size < HugeSize or: [(self pointerBitOf: objectPointer) = 0])
ifTrue: [↑size]
ifFalse: [↑size + 1]
```
## CompiledMethods

A CompiledMethod is an anomaly for the memory manager because its data are a mixture of 16-bit pointers and 8-bit unsigned integers. The only change needed to support CompiledMethods is to add to lastPointerOf: a computation similar to that in the bytecode interpreter's routine bytecodeIndexOf:.

MethodClass is the object table index of CompiledMethod.

### lastPointerOf: objectPointer

| methodHeader |
(self pointerBitOf: objectPointer) = 0
ifTrue:
    [↑HeaderSize]
ifFalse:
    [(self classBitsOf: objectPointer) = MethodClass
        ifTrue: [methodHeader ← self heapChunkOf: objectPointer
                  word: HeaderSize.
                  ↑HeaderSize + 1 + ((methodHeader bitAnd: 126)
                                      bitShift: -1)]
        ifFalse: [↑self sizeBitsOf: objectPointer]]

## Interface to the Bytecode Interpreter

The final step in the implementation of the object memory is to provide the interface routines required by the interpreter. Note that fetchClassOf: objectPointer returns IntegerClass (the object table index of SmallInteger) if its argument is an immediate integer.

object pointer access

### fetchPointer: fieldIndex ofObject: objectPointer

↑self heapChunkOf: objectPointer word: HeaderSize + fieldIndex

### storePointer: fieldIndex

ofObject: objectPointer

withValue: valuePointer

| chunkIndex |
chunkIndex ← HeaderSize + fieldIndex.
self countUp: valuePointer.
self countDown: (self heapChunkOf: objectPointer word: chunkIndex).
↑self heapChunkOf: objectPointer word: chunkIndex put: valuePointer

word access

### fetchWord: wordIndex ofObject: objectPointer

↑self heapChunkOf: objectPointer word: HeaderSize + wordIndex

### storeWord: wordIndex

ofObject: objectPointer

withValue: valueWord

↑self heapChunkOf: objectPointer word: HeaderSize + wordIndex

put: valueWord
byte access

**fetchByte: byteIndex ofObject: objectPointer**

↑self heapChunkOf: objectPointer byte: (HeaderSize*2 + byteIndex)

**storeByte: byteIndex**

**ofObject: objectPointer**

**withValue: valueByte**

↑self heapChunkOf: objectPointer

byte: (HeaderSize*2 + byteIndex)

put: valueByte

reference counting

**increaseReferencesTo: objectPointer**

self countUp: objectPointer

**decreaseReferencesTo: objectPointer**

self countDown: objectPointer

class pointer access

**fetchClassOf: objectPointer**

(self isIntegerObject: objectPointer)

ifTrue: [↑IntegerClass]

ifFalse: [↑self classBitsOf: objectPointer]

length access

**fetchWordLengthOf: objectPointer**

↑(self sizeBitsOf: objectPointer)-HeaderSize

**fetchByteLengthOf: objectPointer**

↑(self loadWordLengthOf: objectPointer)*2 - (self oddBitOf: objectPointer)

object creation

**instantiateClass: classPointer withPointers: length**

| size extra |

size → HeaderSize + length.

extra → size < HugeSize ifTrue: [0] ifFalse: [1].

↑self allocate: size odd: 0 pointer: 1 extra: extra class: classPointer

**instantiateClass: classPointer withWords: length**

| size |

size → HeaderSize + length.

↑self allocate: size odd: 0 pointer: 0 extra: 0 class: classPointer

**instantiateClass: classPointer withBytes: length**

| size |

size → HeaderSize + ((length + 1)/2).

↑self allocate: size odd: length\*\*2 pointer: 0 extra: 0 class: classPointer
## instance enumeration

### `initialInstanceOf: classPointer`

0 to: ObjectTableSize-2 by: 2 do:
[ :pointer |
    (self freeBitOf: pointer) = 0
    ifTrue: [(self fetchClassOf: pointer) = classPointer
             ifTrue: [↑pointer]]].

↑NilPointer

### `instanceAfter: objectPointer`

| classPointer |
objectPointer to: ObjectTableSize-2 by: 2 do:
[ :pointer |
    (self freeBitOf: pointer) = 0
    ifTrue: [(self fetchClassOf: pointer) = classPointer
             ifTrue: [↑pointer]]].

↑NilPointer

## pointer swapping

### `swapPointersOf: firstPointer and: secondPointer`

| firstSegment firstLocation firstPointer firstOdd |
firstSegment ← self segmentBitsOf: firstPointer.
firstLocation ← self locationBitsOf: firstPointer.
firstPointer ← self pointerBitOf: firstPointer.
firstOdd ← self oddBitOf: firstPointer.
self segmentBitsOf: firstPointer put: (self segmentBitsOf: secondPointer).
self locationBitsOf: firstPointer put: (self locationBitsOf: secondPointer).
self pointerBitOf: firstPointer put: (self pointerBitOf: secondPointer).
self oddBitOf: firstPointer put: (self oddBitOf: secondPointer).
self segmentBitsOf: secondPointer put: firstSegment.
self locationBitsOf: secondPointer put: firstLocation.
self pointerBitOf: secondPointer put: firstPointer.
self oddBitOf: secondPointer put: firstOdd

## integer access

### `integerValueOf: objectPointer`

↑objectPointer/2

### `integerObjectOf: value`

↑(value bitShift: 1) + 1

### `isIntegerObject: objectPointer`

↑(objectPointer bitAnd: 1) = 1

### `isIntegerValue: valueWord`

↑valueWord <= -16384 and: [valueWord > 16834]
Indexes
<figure><img src="image_304.png" /></figure>
Subject Index

There are four indexes to this book. The first is the type of index found in most books. It is called the *subject index* and includes the concepts discussed in the book. The other three indexes include the class names, variable names and message selectors referred to in the book. The *system index* includes names and selectors found in the actual Smalltalk-80 system. The *example class index* includes the names of classes introduced as examples but not found in the system. The *implementation index* includes the names and selectors used in the formal specification found in Part Four of the book.

Abelson, Hal, 365

abstract class. *See* class, abstract

accept command, 303-304, 306

accessing parts, 99-100

active context. *See* context, active

active process. *See* process, active

Algol, 13, 34, 119, 165

allocation, 667-671, 679-680, 684

animation, 331, 333, 400

argument. *See* message argument

count, 582-584, 587, 604, 606, 608

name. *See* expression, message argument name

arithmetic, 13, 24, 564, 569, 620-627, 660

on Dates 111

on Numbers 119-130

on Points 341-343

on Times 113

array, 13, 19, 21, 36-37, 69, 96, 126, 569

ASCII, 650

assignment, 563. *See* expression, assignment

association,

*See also* Association (system index)

bag, 13

binary message. *See* expression, message, binary

Birtwistle, Graham, 498-499, 507, 521, 533

bit,

fields, 575, 577, 579

manipulation, 128-129

BitBt, 333-334, 336, 349, 355, 405, 408, 412

combination rule, 336-337, 354, 361

bitmap, 15, 292, 331, 383, 398, 412

*See also* display
Subject Index

block, 15, 18, 31-37, 125-126, 128, 135-138, 151, 159, 164, 180, 188, 215, 239, 251-252, 460, 550, 559-560, 569, 580-581, 585-586, 608

See also expression, block

argument, 35-37, 138, 253, 560, 583-584, 638

context, 559-561

See also BlockContext (system index)

browser, 41, 43, 292-293, 297-307, 318

bytecode, 542-551, 554, 556, 558-560, 562, 568, 576-579, 581-583, 594-610, 612, 642, 646

extensions, 548, 560, 595, 599-600, 606-607

interpreter. See interpreter

jump, 550, 554, 595, 601-603

conditional, 550, 603

unconditional, 550

return, 549, 554, 595, 608-610, 612

special, 549

send, 549, 554-555, 561-562, 595, 603-608, 612, 618

super, 562-563, 607

stack, 595, 597-601

push, 548-549, 554, 595, 599-600

store, 549, 554, 595, 600

caller, 582, 608, 639

capitalization, 22, 40, 45

carat, 294-295

cascading. See expression, message, cascaded

categories command, 305

category. See message, category; class, category

change and update. See dependency

character, 19-21

class, 8, 16, 18, 40, 45-46, 53, 56-59, 73, 76, 95, 269-270, 300, 547, 561-564, 568, 570, 575, 580, 586-591, 605, 612, 618, 633, 636, 653, 657

See also subclass; superclass

abstract, 66-68, 72-73, 78, 81, 134, 198

See also subclassResponsibility (system index)

category, 80, 284, 298, 300, 303

comment, 283-284

creation, 77

definition, 303-307

description, 58, 269, 300, 568, 572

See also implementation description; protocol description

editing, 297

methods, 79, 269

See also method

name, 9, 40, 43, 57-58, 62, 269, 283-284, 288, 312

variable, 44, 53, 84, 219, 276, 288, 547

view, 297

clipping rectangle, 334, 351-352

clock, 566

close command, 317

collections, 133-141, 145, 172, 195, 212-234, 565, 617

See also array; bag; dictionary; set; string of integers, 565-566, 684

ordered. See SequenceableCollection (system index)

unordered. See Dictionary; Bag; Set (system index)

compaction, 659, 667-668, 671-674, 676, 684

comparing, 96-97, 107, 160, 166-167

compiler, 272-273, 285, 542-545, 550, 559, 575, 607, 633

concatenation, 155

conditionals. See bytecode, jump, conditional; control structures

context, 15, 555-556, 558-560, 575, 580-586, 612 active, 555, 558, 560, 563, 583-585, 595, 597, 599-600, 603, 605, 608-610, 638-639, 643-644, 651

home, 581-583, 585, 608, 638

suspended, 555-556, 561

control structures, 13, 23, 32-35, 550, 559, 564, 569-570, 616, 620, 637-647

See also enumeration; expression, block

conditional repetition, 13, 34-35, 550, 569

conditional selection, 13, 34, 238-239, 569-570

independent processes. See independent processes

iteration, 164-165

of the interpreter. See interpreter, control structures

converting, 123, 127

Characters, 116

Collections, 140-141, 157, 169, 175, 217

Dates and Times, 113

Strings, 167

copying, 97-99, 155-156, 285

cumulative distribution function, 419, 424, 430

cursor, 15, 292-297, 299, 302, 311-312, 398-399, 651

cut command, 296

cyclic structures, 675-676

dangling reference, 674

data structures, 13, 21, 24

See also collections

of the interpreter. See interpreter data structures

stack and queue, 157-158

tree structure. See examples, tree structure

Davis, Chandler, 373

deallocation, 667, 670-671, 674-675, 677, 683
debug command, 318, 320

debugger, 314, 320-327

definition command, 304

density function, 419, 423-424, 430

dependency, 240-243

deselection, 300

dictionary, 7-8, 13, 24, 45, 543, 547, 605

*See also* subclass examples

diSessa, Andrea, 365

disk, 566

display, 292, 331, 333, 365-367, 388, 398, 400, 566, 649, 651

dolt command, 297, 309-310

enumeration, 126, 128, 136-137, 151-152, 156-157, 165, 188, 195, 197, 215, 221, 233, 281, 573, 633, 636

*See also* do: (system index)

equality, 96, 145, 565, 587

*See also* comparing

equivalence, 96, 136, 145, 565

*See also* comparing

error reporting, 51, 61, 72-73, 102-103, 135-136, 138, 148, 214, 217, 237, 314-317, 561, 589, 602, 609

evaluating expressions. See expression evaluation

event, 418

examples,

*See also* example class index

calculator, 245-246

card game, 172-181

event-driven simulations. See simulation examples

financial transactions, 10, 25, 27

game of Life, 412-413

geometric designs. See geometric designs

hardware interrupt, 263-265

image manipulation, 405-413

multiple pens, 375-379

mutual exclusion, 258-262

probability distributions, 205, 418

*See also* probability distributions

random walk, 181-185

resource sharing, 262

traffic lights, 241-243

tree structure, 185-192, 208

exception handling, 135

expression, 18, 37, 297

assignment, 22, 27, 32, 37, 49-50

block. See block

evaluation, 297, 309, 324, 327

format, 30

literal, 18-19, 22, 37, 50

message, 18, 24-31

*See also* message

argument name, 42, 49, 51, 53, 323-324

binary, 27-30, 37

cascaded, 30, 37, 548

keyword, 26, 28-30, 36-37

pattern, 41, 48-49, 53, 57

unary, 26, 28-30, 37, 77

parsing, 28-30

pseudo-variable name, 23, 37, 49-50, 62-63, 73

variable name, 18, 21-22, 37, 58, 283, 544

extended bytecode. See bytecode extensions

field indices, 570-571, 574-576, 581, 586, 590

files, 15, 209, 286-288, 466

fixed-length object, 231, 280-281

flag value, 577-579, 618, 620

font, 15, 166, 334, 354, 400

formatting. See expression format

fragmentation, 659

free chunk, 664-671, 674, 682-683

free entry, 659, 664-665, 670, 683

free pointer, 659, 665, 671

freehand drawing, 331

garbage collection, 565, 571, 644, 674-685

marking, 675-676, 680, 682-684

reference counting. See reference counting

Gardner, Martin, 373

geometric designs, 370-375

dragon curve, 372-373

Hilbert curve, 373-375

spiral, 370-372, 377

global variable, 44-45, 53, 308, 547, 644, 682

declaration, 48

GPSS, 533

graphics, 292, 331-362, 365, 383

*See also* BitBlt

halftone, 336, 392, 411

hardware devices, 263-265, 542, 566, 612, 647

*See also* input/output

hashing, 70-72, 96, 222-224, 587

header. See method header or object header

heap, 657-659, 663-664

*See also* segment, heap

hierarchy, 83, 270-271, 273, 275, 277

*See also* inheritance; subclass; superclass

Hilbert, David, 373

home context. See context, home

Hydra, 7

identifier, 22-23

IEEE floating point standard, 625-626

image,

*See also* DisplayMedium (system index)

area filling, 390-392, 411-412

bordering, 393-395

display box, 388

displaying, 388-389
image (cont.)

magnifying, 405-407

reversing, 393

rotating, 408-410

transforming, 349, 388

immutable object, 107, 115

implementation description, 41, 43, 45-46, 53, 57-58, 78-81, 84

independent processes. See process

indexing, 46, 96, 145, 153, 627-630

inheritance, 58, 61, 81

See also multiple inheritance; subclass; superclass

initialization, 81

of classes, 77, 84-88

of instances, 77, 87, 274

input/output, 251, 564, 566, 620, 647-652

See also display; keyboard; pointing device

inspector, 311, 313, 323

instance, 8, 16, 18, 40, 46, 53, 56-58, 62, 76, 95, 269-270, 565, 591, 633-634, 636

creation, 40, 45, 47, 68, 76, 78, 80-81, 84, 87, 98, 110, 112, 115, 139-140, 160-161, 163, 168, 199, 212-213, 266, 269, 273-275, 287-288, 344, 564, 572, 633-634, 656

methods, 79

See also method

specification, 586, 590-591

variable 8, 16, 44-47, 53, 58, 61, 76, 96, 283-284, 311, 313, 543, 545, 548-549, 552, 564-565, 568, 578-579, 599-600, 618, 620, 630.

See private variable, instance

indexed, 45-47, 56-57, 99, 153, 212, 275-276, 281, 581, 587, 590

named, 45-47, 56-57, 99, 246-247, 276, 280, 543, 581, 590

instruction pointer, 551-552, 554, 560, 581-582, 584, 595, 602-603, 609-610, 639

interface, 8, 16, 40

See also message

interpreter, 272, 542, 547-548, 550-564, 566, 568-571, 574-576, 583-587, 589, 594-610, 612, 656, 660, 674, 682, 685

control structures, 569, 616

data structures, 575

registers, 583, 587, 642

state, 551, 554-555, 563

intervals. See Interval (system index)

iteration. See control structures, iteration

Kaehler, Ted, 404

key, 145, 148, 157, 161, 165, 168-169

See also collections

keyboard, 251, 292, 566, 648-650

keyword, 26, 37

See also expression, message, keyword

keyword message. See expression, message, keyword

Knuth, Donald, 130, 185, 373, 430, 437

large context flag, 577

Lehmer, 130, 204

line drawing, 351-352, 365, 403

See also Pen (system index)

Lisp, 100

list,

selection. See selection, list

view, 297, 302

literal, 546, 548, 579-580, 586, 633

See also expression, literal

constant. See expression, literal

count, 577-578

frame, 544, 546, 548-549, 563, 576-578, 580-582, 600, 604, 608

logarithmic functions, 124

logical operations, 238

Logo, 365, 368, 370

mapping. See MappedCollection (system index)

mean, 419

memory management, 656, 675, 685

See also object memory; compaction; fragmentation

real memory, 656-657

virtual memory, 656, 676

menu, 15, 296-297, 304

command. See name of command

selection. See selection, menu

message, 6-7, 16, 18, 24, 40, 56-66, 243-246, 543-545, 549, 551, 553-554, 558-559, 562-563, 566, 575, 580, 583, 587, 589, 603, 608, 612, 618, 640

argument, 25-26, 37, 42, 543, 545, 547-549, 551, 553-554, 560-561, 563, 568, 577-578, 581-582, 587, 603-605, 612, 616, 621, 635, 639-641

category, 42, 53, 80, 284-285, 298-300, 305-307

computed, 243-244

dictionary, 561-563, 580, 586-589

See also method dictionary

expression. See expression, message

receiver. See receiver

response, 27

selector, 25, 27, 37, 40, 57, 61, 243-244, 273, 299-300, 307, 544, 546, 549, 553, 561, 577, 586-589, 603-606, 637, 640

value, 18, 558
metaclass, 76-89, 269-271, 284

See also Metaclass (system index)

reference to, 77

method, 8, 16, 18, 40, 43-44, 48, 53, 56-57, 61-66, 77, 300, 322, 542-543, 545, 562, 568-569, 576-582, 585-588, 608, 684

See also message; primitive method or routine

cache, 605, 647

class, 580

determination, 61-66, 84, 86-89

See also overriding a method

dictionary, 273-276, 278

See also message dictionary

editing, 300, 305-307

header, 576-582, 618, 633, 637

extension, 579-580, 618

view, 298

modularity, 7

mouse. See pointing device

buttons, 292-297, 299, 302, 304, 312, 566, 648, 650

multiple inheritance, 57

mutual exclusion. See examples, mutual exclusion

nonpointer objects, 684-686

notifier, 314-315, 317-320

number, 13, 19-20, 96, 119-130, 546, 565-566, 569, 577

coercion, 125

generality, 124-125, 127

object, 6, 16, 18, 40, 56, 76, 95, 269, 542

header, 657, 663, 667, 670, 672

memory, 542, 564-566, 568-575, 585, 595, 612, 630, 636, 651, 656-688

pointer, 564-566, 568-572, 575-576, 578, 584, 587, 590, 595, 597, 601, 603, 608, 636, 644, 653, 659-661, 680, 685

table, 659-667

entry, 661-663, 666, 670-672, 674, 676, 683, 685 See also free entry; free pointer

overriding a method, 57, 64-66, 72-73, 87, 100, 212, 274, 589

Papert, Seymour, 365

parsing. See expression, parsing

pattern matching, 167

period, 31, 48, 52, 309

pixel, 331, 334, 336, 338, 340, 344, 349, 398, 651

pointing device, 251, 292, 398, 566, 648-649, 651

See also mouse buttons

pool, 47-48

pool variable, 44, 276, 547

primitive failure, 102, 563, 612, 616-617, 624, 626, 629, 634, 639-640, 647

primitive index, 579, 588, 605, 620

primitive method or routine, 9, 16, 52-53, 84, 100, 102, 213, 246-247, 563-564, 566, 568, 574, 578-579, 587, 595, 605, 612-653

See also method

optional, 612

printing and storing, 100-101, 127, 201-202, 218-219, 284-287, 313, 467-468, 503

printlt command, 297, 309-310, 320

private method category, 80, 214, 612

See also message category

private variable, 22, 47

See also instance variable; temporary variable
probability distributions, 418-438, 446

continuous, 420, 432-438

exponential, 432-435

gamma, 432, 435-436

normal or Gaussian, 432, 436-438

uniform, 420, 424, 432-433

discrete, 419, 423-432

Bernoulli, 425-427, 429

binomial, 425, 427-430

geometric, 425, 429-430

Poisson, 425, 430-432

probability function, 418

process, 15, 162, 251-266, 452, 459-461, 486, 583, 594, 641-647

active, 643

priorities, 254-257

scheduling, 254, 455, 644

See also ProcessorScheduler (system index)

programming environment, 7, 15, 41, 51, 243, 275, 278, 283-284, 287, 292-327, 398, 674

See also browsers

programming style, 7, 69, 72-73, 81, 84, 97, 100, 212, 214, 219, 247, 274, 449-452, 488

See also subclassResponsibility (system index)

protocol. See interface; message

protocol description, 41-42, 53

prototype, 98-99

pseudo-variable name. See expression, pseudo-variable name

queue. See data structures, stack and queue

random number generation, 129-130

See also Random (system index)

random variable, 418-419

raster, 338

rational numbers. See Fraction (system index)

realtime clock, 251, 263, 266

receiver, 6, 16, 18, 24-25, 27, 37, 61, 543, 545, 548-549, 551, 553-554, 556, 560-563, 579, 581-582, 586, 599-600, 603, 605, 607-608, 612, 616, 619-621, 635, 640, 653

See also message
rectangle, 8, 24, 311-312, 366

reference counting, 565, 571, 585, 609-610, 644, 675-683

in simulations, 459-461, 486

registers, 568, 570, 583-585, 588, 616, 642

resources, 440-444, 446-447, 454-455, 484-513, 516-537

consumable, 489-492

coordinated, 516-537

nonconsumable, 492-503

renewable, 503-513

result, 543-544, 549, 553-555, 612

returning values 585. See value, returning a

reversing pointers, 673-674, 678-680

routines, 568-570, 594, 616-617, 642

sample space, 172, 418-420

scheduling. See process or simulation

screen. See display

scroll bar, 302

scrolling, 302

seed, 204

See also random number generation

segments, 656, 658, 666

current, 667-669

heap, 658-659, 661, 667, 671-674

selection, 15, 292-293

list, 298-299

menu, 296

text, 293-295, 297

selector. See message selector

sender, 555, 558, 581-582, 585, 608-610

set, 13

shared variable, 22, 58, 288, 543, 546-549, 577, 599

See also class variable; global variable; pool variable

Simula, 7, 57, 119, 498

simulation, 7, 418, 440-464

event-driven, 441

examples,

bank, 526-532

car dealership, 504-507

car rental, 492-498

car traffic, 474-476

car wash, 442, 518-521

default (do nothing), 449-452, 462-464

ferry service, 507-513, 521-526

file system, 498-503

information system, 533-537

jelly bean store, 489-492

museum visitors, 472-474

resources. See resources

scheduling, 448-449, 453, 455, 458-462

statistics gathering. See statistics gathering time, 441, 443, 446

sorting, 145, 159-160

special constants, 545

special message selectors, 545, 549, 604, 608, 618-619

special return bytecodes. See bytecode, return, special

stack, 542-544, 548-552, 554, 558, 560-561, 575, 577, 581-583, 595, 597, 600-605, 608, 610, 612, 616-617, 620-621, 638-640, 682

See also data structures, stack and queue

stack pointer, 581-582, 584, 639

statistics gathering, 442, 466-483, 499, 509-510 durations, 466-469

event monitoring, 476-483

event tallying, 474-476

throughput histograms, 469-474, 504-506

storage management, 564, 591, 620, 633-637

See also garbage collection; reference counting

storing. See printing and storing

streaming. See Stream (system index)

strike format, 354

string, 13, 19-21, 126, 546, 684

See also concatenation; pattern matching

subclass, 57-60, 64-65, 73, 269-270, 300, 547, 562, 584

examples, 62, 64, 66-72

subview, 297-300, 302, 313, 320

superclass, 57-60, 64-66, 73, 81, 269, 322, 561-563, 580, 586, 588, 606-607

suspended process, 252-253, 266, 314, 317-318, 320, 561, 644, 646

See also debugger; notifier

symbol, 19, 21, 37

synchronization, 251, 257, 265

See also Semaphore (system index)

system browser. See browser

system classes, 11, 14, 16

temporary count, 577

temporary frame, 547-548, 581-582, 599-600

temporary variable, 44, 51-53, 86, 138, 323-324, 545-549, 551, 560, 577-578, 581-582, 585

testing, 95, 97, 115, 150, 197, 278-281, 348

text, 15, 166, 292, 302, 331, 351, 383, 400, 405

display, 354-355

editing, 296, 298

selection. See selection, text

trial, 418

trigonometric functions, 124

turtle drawing. See line drawing
unary message. *See* expression, message, unary

uparrow. *See* ↑ (system index)

user interface. *See* programming environment value,

*See also* message value; variable value

returning a, 27, 49, 544, 549, 558, 560, 579, 608-610, 620

variable, 21, 57

declaration, 43-48, 51, 58, 84

name. *See* expression, variable name

private. *See* private variable

shared. *See* shared variable

value, 549

variable-length object, 100, 215, 231, 274, 280-281, 289

variance, 419

view, 15, 292-293, 296, 302

*See also* browser; workspace

virtual image, 542, 564, 566

virtual machine, 251, 254, 263, 542, 545, 564, 566, 568-569

*See also* interpreter; object memory

formal specification, 568-688

window, 15, 334

*See also* view

workspace, 292-293, 298, 309
System Index

CompiledMethod, 273, 543-544, 546-551, 555, 559-563, 576-581, 586-589, 591, 594-595, 604-605, 607, 612, 616, 618, 620, 633, 637, 640, 685

Cursor, 374-375, 399, 651
  defined on, 398

Curve, 403, 405
  defined on, 404

Date, 40, 77-78, 107-108, 114
  defined on, 109-111, 113

Delay, 251, 263
  defined on, 266

detect, 138
  defined on, 137, 215

Dictionary, 56, 133, 145, 148, 157, 168, 220-221, 233, 269
  defined on, 149-152, 224-226
  used on, 44, 80, 467, 475

Disk, 210, 283, 287, 474, 476, 480, 494

Display, 388, 400
  used on, 397

displayAt, 389
  defined on, 388

DisplayBitmap, 333

DisplayMedium, 383, 396, 398, 400
  defined on, 390, 392-394

DisplayObject, 390, 398, 400, 403, 405
  defined on, 383, 388

DisplayScreen, 333, 398, 400, 651

DisplayText, 383, 400

do:, 36, 38, 148, 151, 164, 197, 461, 595
  defined on, 136, 215, 226, 228, 230, 233-234

doesNotUnderstand, 61, 323, 589
  defined on, 102

error, 51, 136, 138, 317
  defined on, 102

ExternalStream, 208
  defined on, 209

False, 237, 239

false, 23, 34-35, 85, 238, 545, 549-550, 599, 601-603, 608

File, 210

FileDirectory, 210

FilePage, 210

FileStream, 209-210, 469

Float, 119, 124-127, 130, 621, 625-626

fork, 251-252
  defined on, 253-254

Form, 331, 333-334, 336, 352, 354, 365-367, 374-375, 383, 389-390, 393, 396-398, 400, 405, 651
  defined on, 338-340
  used on, 406, 408, 411-412

Fraction, 119-120, 124-127

IdentityDictionary, 145, 148, 226, 587

ifFalse, 34, 38, 550
  defined on, 238-239

ifFalse:ifTrue, 37
  defined on, 238-239

ifTrue, 34, 37, 550, 602
  defined on, 238-239

ifTrue:ifFalse, 34, 37, 550
  defined on, 238-239

InfiniteForm, 398
inject:into, 138-139, 148, 185, 216
  defined on, 137, 216
  used on, 180

InputState, 648-649, 651

inspect, 311

Integer, 51, 108, 119, 122-124, 127, 164, 175, 209, 220, 224, 568, 570, 573
  defined on, 128-129

*See also* bit manipulation

Interval, 125-126, 136, 145, 157, 165, 174-175, 216, 219
  defined on, 163-164, 229-230

LargeNegativeInteger, 119, 124-125, 127, 565, 621, 625

LargePositiveInteger, 119, 124-125, 127, 209, 565, 568, 617, 621, 625

Line, 403

LinearFit, 403

Link, 145, 161-162, 185, 190, 205-206, 227, 286

LinkedList, 145, 157, 162, 185, 205-208, 229, 286, 644-645
  defined on, 161, 227-228

LookupKey, 107, 145

Magnitude, 111, 114, 166
  defined on, 107-108

MappedCollection, 145-146, 157, 168-169, 216, 219
  defined on, 233-234

Message, 243, 589-590

Metaclass, 77-78, 81, 89, 269-271, 283-284
  defined on, 287

MethodContext, 559, 563, 577-578, 580-581, 583-584, 605, 612, 638

new, 40, 81-84, 139, 274, 595
*See also* instance creation

new:, 47, 81, 139, 595
*See also* instance creation

nil, 23, 32, 34-35, 45, 47, 51, 76, 84, 97, 138, 237-238, 336, 545, 549, 588, 599, 608-610

Number, 107, 119, 145, 164-165, 219, 340-341, 365
  defined on, 120, 122-123, 125-126