In the macroscopic range, the width of transfer spans many words. The inner loop across a horizontal scan line gets executed many times, and the operations requested tend to be simple moves or constant stores. Examples of these are:

* clearing a line of text to white

* clearing an entire window to white

* scrolling a block of text up or down

Most processors provide a fast means for block moves and stores, and these can be made to serve the applications above. Suppose we structure the horizontal loop of BitBit as

1. move left partial word,

2. move many whole words (or none),

3. move right partial word (or none).

Special cases can be provided for 2 if the operation is a simple store or a simple copy with no skew (horizontal bit offset) from source to destination. In this way, most macroscopic applications of BitBit can be made fast, even on processors of modest power.

The microscopic range of BitBit is characterized by a zero count for the inner loop. The work on each scanline involves at most two partial words, and both overall setup and vertical loop overhead can be considerably reduced for these cases. Because characters tend to be less than a word wide and lines tend to be less than a word thick, nearly all text and line drawing falls into this category. A convenient way to provide such efficiency is to write a special case of BitBit which assumes the microscopic parameters, but goes to the general BitBit whenever these are not met. Because of the statistics (many small operations and a few very large ones), it does not hurt to pay the penalty of a false assumption on infrequent calls. One can play the same trick with clipping by assuming no clipping will occur and running the general code only when this assumption fails.
<figure><img src="image_201.png" /></figure>

<figure><img src="image_202.png" /></figure>

19

Pens

Class Pen

Geometric Designs

*Spirals*

*Dragon Curve*

*Hilbert Curve*

Commander Pen
Object

Magnitude

Character
Date
Time

Number

Float
Fraction

Integer

LargeNegativeInteger
LargePositiveInteger
SmallInteger

LookupKey

Association

Link

Process

Collection

SequenceableCollection
LinkedList

Semaphore

ArrayedCollection
Array

Bitmap

DisplayBitmap

RunArray

String
Symbol

Text

ByteArray

Interval

OrderedCollection
SortedCollection

Bag

MappedCollection

Set

Dictionary

IdentityDictionary

Stream

PositionableStream
ReadStream
WriteStream
ReadWriteStream

ExternalStream

FileStream

Random

File

FileDirectory

FilePage

UndefinedObject

Boolean
False

True

ProcessorScheduler

Delay
SharedQueue

Behavior

ClassDescription
Class
MetaClass

Point

Rectangle

BitBit

CharacterScanner

Pen

DisplayObject

DisplayMedium
Form
Cursor
DisplayScreen

InfiniteForm
OpaqueForm
Path

Arc
Circle

Curve
Line

LinearFit
Spline
As explained in the previous chapter, Forms represent images. Lines can be created by copying a Form to several locations in another Form at incremental distances between two designated points. Higher-level access to line drawing is provided by instances of class Pen.

Pen is a subclass of BitBlt. As such, it is a holder for source and destination Forms. The source Form can be colored black or white or different tones of gray, and copied into the destination Form with different combination rules, different halftone masks, and with respect to different clipping rectangles. The source Form is the Pen's writing tool or nib. The destination Form is the Pen's writing surface; it is usually the Form representing the display screen.

In addition to the implementations inherited from BitBlt, a Pen has a Point that indicates a position on the display screen and a Number that indicates a direction in which the Pen moves. A Pen understands messages that cause it to change its position or direction. When its position changes, the Pen can leave a copy of its Form at its former position. By moving the Pen to different screen positions and copying its Form to one or more of these positions, graphic designs are created.

Several programming systems provide this kind of access to line drawing. In these systems, the line drawer is typically called a "turtle" after the one first provided in the MIT/BBN Logo language (Seymour Papert, *MindStorms: Children, Computers and Powerful Ideas*, Basic Books, 1980; Harold Abelson and Andrea diSessa, *Turtle Geometry: The Computer as a Medium for Exploring Mathematics*, MIT Press, 1981). The protocol for Pens supports messages that are like the turtle commands provided in Logo. These consist of commands for telling the turtle to go some distance, turn some amount, to place a pen in a down position, and to place a pen in an up position. When the pen is down and it moves, a trace of the turtle's path is created. The corresponding Pen messages are go: distance, turn: amount, down, and up.

Multiple Pens can be created and their movement on the screen coordinated so that the process of creating a graphical design can itself be graphically pleasing. The next section contains the protocol that is provided in class Pen. Subsequent sections give examples of designs that can be created by sending messages to Pens.

## Class Pen

Instances of class Pen are created by sending Pen the message new. A Pen created this way can draw anywhere on the display screen; its initial position is the center of the screen, facing in a direction towards
the top of the screen. The Pen is set to draw (i.e., it is down) with a source Form or nib that is a 1 by 1 black dot.

There are two ways to change the source Form of a Pen. One way is to send the Pen the message defaultNib: widthInteger. The other way is to reset the source Form by sending the Pen the messages it inherits from its superclass, BitBlt. For example, the message sourceForm: changes the source form, or the message mask: changes the halftone form (the mask) used in displaying the source form. (Note that the default mask for displaying is black.)

### Pen instance protocol

initialize-release

defaultNib: shape

A "rib" is the tip of a pen. This is an easy way to set up a default pen. The Form for the receiver is a rectangular shape with height and width equal to (1) the argument, shape, if shape is an Integer; or (2) the coordinates of shape if shape is a Point.

Thus

bic - Pen new defaultNib: 2

creates a Pen with a black Form that is 2 bits wide by 2 bits high.

The accessing protocol for a Pen provides access to the Pen's current direction, location, and drawing region. The drawing region is referred to as the Pen's *frame*.

### Pen instance protocol

accessing

direction

Answer the receiver's current direction. 270 is towards the top of the screen.

location

Answer the receiver's current location.

frame

Answer the Rectangle in which the receiver can draw.

frame: aRectangle

Set the Rectangle in which the receiver can draw to be the argument, aRectangle.

Continuing to use the example, bic, and assuming that the display screen is 600 bits wide and 800 bits high, we have

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>bic direction</td><td>270</td></tr><tr><td>bic location</td><td>300@400</td></tr><tr><td>bic frame:<br>(50@50 extent: 200@200)</td><td></td></tr><tr><td>bic location</td><td>300@400</td></tr></tbody></table>
Notice that when the Pen direction is towards the top of the display screen, the angle is 270 degrees. Notice also that the Pen is currently outside its drawing region and would have to be placed within the Rec-tangle, 50@50 corner: 250@250, before any of its marks could be seen.

The "turtle" drawing commands alter the Pen's drawing state, orient its drawing direction, and reposition it.

Pen instance protocol

moving

down

Set the state of the receiver to "down" so that it leaves marks when it moves.

up

Set the state of the receiver to "up" so that it does not leave marks when it moves.

turn: degrees

Change the direction that the receiver faces by an amount equal to the argument, degrees.

north

Set the receiver's direction to facing toward the top of the display screen.

go: distance

Move the receiver in its current direction a number of bits equal to the argument, distance. If the receiver status is "down," a line will be drawn using the receiver's Form as the shape of the drawing brush.

goto: aPoint

Move the receiver to position aPoint. If the receiver status is "down", a line will be drawn from the current position to the new one using the receiver's Form as the shape of the drawing brush. The receiver's direction does not change.

place: aPoint

Set the receiver at position aPoint. No lines are drawn.

home

Place the receiver at the center of the region in which it can draw.

Thus we can place bic in the center of its frame by evaluating the expression

bic home

If we then ask

bic location

the response would be 150@150.

Suppose that we drew a line with a Pen and then decided that we wanted to erase it. If the line had been drawn with a black Form, then we can erase it by drawing over it with a white Form of at least the same size. Thus

bic go: 100
draws the black line. Then

bic white

sets the drawing mask to be all white (the message white is inherited from the protocol of BitBit), and then

bic go: -100

draws over the original line, erasing it.

An exercise that is common in the Logo examples is to create various polygon shapes, such as a square.

4 timesRepeat: [bic go: 100. bic turn: 90]

The following expression creates any polygon shape by computing the
angle of turning as a function of the number of sides. If nSides is the
number of sides of the desired polygon, then

nSides timesRepeat: [bic go: 100. bic turn: 360 // nSides]

will draw the polygon. We can create a class Polygon whose instances
refer to the number of sides and length of each side. In addition, each
Polygon has its own Pen for drawing. In the definition that follows, we
specify that a Polygon can be told to draw on the display screen; the
method is the one described earlier.

<table><tr><td>class name</td><td>Polygon</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>instance variable names</td><td>drawingPen<br>nSides<br>length</td></tr></table>

class methods

instance creation

new

↑super new default

instance methods

drawing

draw

drawingPen black.

nSides timesRepeat: [drawingPen go: length; turn: 360 // nSides]
accessing

**length: n**

length → n

**sides: n**

nSides → n

private

**default**

drawingPen → Pen new.

self length: 100.

self sides: 4

Then a Polygon can be created and a sequence of polygons drawn by
evaluating the expressions

poly → Polygon new.

3 to: 10 do: [ :sides | poly sides: sides. poly draw]

The result is shown in Figure 19.1.

<figure><img src="image_203.png" /><figcaption>Figure 19.1</figcaption></figure>
**Geometric**
**Designs**

The Logo books mentioned earlier provide extensive examples of how to use this kind of access to line drawing in order to create images on a computer display screen. We provide several examples of methods that can be added to a Pen so that any Pen can draw a geometric design such as those shown in Figures 19.2 - 19.5. (Note: These methods are in the system as part of the description of Pen so that users can play with creating geometric designs.)

Spirals

The first design is called a *spiral*. A spiral is created by having the Pen draw incrementally longer lines; after each line is drawn, the Pen turns some amount. The lines drawn begin at length 1 and increase by 1 each time until reaching a length equal to the first argument of the message `spiral:angle:`. The second argument of the message is the amount the Pen turns after drawing each line.

spiral: n angle: a

1 to: n do:

[:i | self go: i. self turn: a]

Each of the lines in Figure 19.2 was drawn by sending bic the message `spiral:angle:`, as follows.

bic spiral: 150 angle: 89

<figure><img src="image_204.png" /><figcaption>Figure 19.2a</figcaption></figure>
<figure><img src="image_205.png" /><figcaption>Figure 19.2b</figcaption></figure>

<figure><img src="image_206.png" /><figcaption>Figure 19.2c</figcaption></figure>
bic home.

bic spiral: 150 angle: 89.

bic home.

bic spiral: 150 angle: 91

<figure><img src="image_207.png" /><figcaption>Figure 19.2d</figcaption></figure>

### Dragon Curve

Figure 19.3 is an image of a "dragon curve" of order 8 which was drawn in the middle of the screen by evaluating the expression

bic - Pen new defaultNib: 4.

bic dragon: 9

The method associated with the message dragon: in class Pen is

#### dragon: n

n = 0

ifTrue: [self go: 10]

ifFalse:

[n > 0

ifTrue:

[self dragon: n - 1.

self turn: 90.

self dragon: 1 - n]

ifFalse:

[self dragon: -1 - n.

self turn: -90.

self dragon: 1 + n]]
<figure><img src="image_208.png" /><figcaption>Figure 19.3</figcaption></figure>

Dragon curves were discussed by Martin Gardner in his mathematical games column in *Scientific American* (March 1967, p. 124, and April 1967, p. 119). Another discussion of dragon curves appears in Donald Knuth and Chandler Davis, "Number Representations and Dragon Curves," *Journal of Recreation Mathematics*, Vol. 3, 1970, pp. 66-81 and 133-149.

### Hilbert Curve

Figure 19.4 is a space-filling curve attributed to the mathematician David Hilbert. A space-filling curve has an index; as the index increases to infinity, the curve tends to cover the points in a plane. The example is the result of evaluating the expression

Pen new hilbert: 5 side: 8

The index for the example is 5; at each point, a line 8 pixels long is drawn. The corresponding method for the message hilbert:side is

hilbert: n side: s

| a m |
n = 0 if True: [ itself turn: 180 ].
n > 0 if True: [ a ← 90 .
m ← n − 1 ]
if False: [ a ← − 90 .
m ← n + 1 ].
<figure><img src="image_209.png" /><figcaption>Figure 19.4</figcaption></figure>

self turn: a.
self hilbert: 0 — m side: s.
self turn: a.
self go: s.
self hilbert: m side: s.
self turn: 0 — a.
self go: s.
self turn: 0 — a.
self hilbert: m side: s.
self go: s.
self turn: a.
self hilbert: 0 — m side: s.
self turn: a

A Hilbert curve, where the source form is a different shape, creates a nice effect. Suppose the Form is three dots in a row; this is a system cursor referred to as wait. The image in Figure 19.5 was created by evaluating the expressions

bic → Pen new sourceForm: Cursor wait.

bic combinationRule: Form under.

bic hilbert: 4 side: 16
<figure><img src="image_210.png" /><figcaption>Figure 19.5</figcaption></figure>

Expressions Cursor wait and Form under access a Form and a combination rule, respectively, that are constants in the system and that are known to the named classes. Other such constants are listed in a section of the next chapter. The messages sourceForm: and combinationRule: are inherited by Pens from their superclass BitBlt.

Commander
Pen

The next example is shown in Figure 19.6. Although we can not show
the process by which the design was created, it is a nice example for
the reader to try. The basic idea is to create an object that controls sev-
eral Pens and coordinates their drawing a design. We call the class of
this kind of object, Commander. A Commander is an array of Pens.
Pens controlled by a Commander can be given directions by having the
Commander enumerate each Pen and evaluate a block containing Pen
commands. So if a Commander's Pens should each go: 100, for example,
then the Commander can be sent the message

do: [ :eachPen | eachPen go: 100]

A Commander also responds to messages to arrange its Pens so that in-
teresting designs based on symmetries can be created. The two mes-
sages given in the description of Commander shown next are fanOut and
**lineUpFrom:** startPoint to: endPoint. The first message arranges the Pens so that their angles are evenly distributed around 360 degrees. A Commander's Pens can be positioned evenly along a line using the message `lineUpFrom:to:`, where the arguments define the end points of the line.

A description for Commander follows. The message new: is redefined so that Pens are stored in each element of the Array.

<table><tr><td>class name</td><td>Commander</td></tr><tr><td>superclass</td><td>Array</td></tr><tr><td>class methods</td><td></td></tr></table>

### instance creation

**new: numberOfPens**

```
| newCommander |
newCommander ← super new: numberOfPens.
1 to: numberOfPens do:
    [ :index | newCommander at: index put: Pen new].
↑newCommander
```

### instance methods

### distributing

**fanOut**

1 to: self size do:
    [ :index |
     (self at: index) turn: (index - 1) * (360 / self size)]

**lineUpFrom:** startPoint to: endPoint

1 to: self size do:
    [ :index |
     (self at: index)
     place: startPoint + (stopPoint-startPoint*(index-1)/(self size-1))]

The methods are useful examples of sending messages to instances of class Point. The image in Figure 19.6 was drawn by evaluating the expressions

```
bic ← Commander new: 4.
bic fanOut.
bic do: [ :eachPen | eachPen up. eachPen go: 100. eachPen down].
bic do: [ :eachPen | eachPen spiral: 200 angle: 121]
```

The message do: to a Commander is inherited from its Collection superclass.
<figure><img src="image_211.png" /><figcaption>Figure 19.6</figcaption></figure>

Another example of the use of a Commander is given in Figure 19.7. This image was created by using the message `lineUpFrom/to:`. It is a simple sequence of spirals arranged along a line at an angle, created by evaluating the expressions

```
bic - Commander new: 6.
bic lineUpFrom: (300@150) to: (300@500).
bic do: [ :eachPen | eachPen spiral: 200 angle: 121]
```

□ **Additional Protocol for Commander Pen** An expanded description of Commander adds to Commander each message of the protocol of class Pen whose behavior changes position or orientation. This additional protocol supports the ability to send messages that are part of Pen's
<figure><img src="image_212.png" /><figcaption>Figure 19.7</figcaption></figure>
protocol to the Commander. Each such message is implemented as
broadcasting the message to the elements of the collection. In this way,
messages to Commander take the same form as messages to any Pen,
rather than that of a do: message. With the class defined in this way,
drawing sequences to a Commander appear more like drawing se-
quences to a Pen. Moreover, all the Pens commanded by a Commander
draw in parallel; for example, all the spirals of Figures 19.6 or 19.7
would grow at once.

**down**

self do: [ :each | each down]

**up**

self do: [ :each | each up]

**turn: degrees**

self do: [ :each | each turn: degrees]

**north**

self do: [ :each | each north]

**go: distance**

self do: [ :each | each go: distance]

**goto: aPoint**

self do: [ :each | each goto: aPoint]

**place: aPoint**

self do: [ :each | each place: aPoint]

**home**

self do: [ :each | each home]

**spiral: n angle: a**

1 to: n do:

[ :i | self go: i. self turn: a]

With this additional protocol, Figure 19.6 can be drawn by evaluating
the expressions

bic — Commander new: 4.

bic fanOut.

bic up.

bic go: 100.

bic down.

bic spiral: 200 angle: 121

and Figure 19.7 by the expressions

bic — Commander new: 6.

bic lineUpFrom: (300@150) to: (300@500).

bic spiral: 200 angle: 121
<figure><img src="image_213.png" /></figure>
<figure><img src="image_214.png" /></figure>

20

# Display Objects

**Class DisplayObject**

**Class DisplayMedium**

**Forms**

*Other Forms*

*Cursors*

*The Display Screen*

**Display Text**

**Paths**

**Image Manipulation with Forms**

*Magnification*

*Rotation*

*Area Filling*

*The Game of Life*
Object

Magnitude

Character
Date
Time

Number

Float
Fraction
Integer

LargeNegательInteger
LargePositiveInteger
SmallInteger

LookupKey
Association

Link

Process

Collection

SequenceableCollection
LinkedList

Semaphore

ArrayedCollection
Array

Bitmap
DisplayBitmap

RunArray
String
Symbol
Text
ByteArray

Interval
OrderedCollection
SortedCollection

Bag
MappedCollection
Set

Dictionary
IdentityDictionary

Stream

PositionableStream
ReadStream
WriteStream
ReadWriteStream
ExternalStream
FileStream

Random

File
FileDirectory
FilePage

UndefinedObject
Boolean
False
True

ProcessorScheduler
Delay
SharedQueue

Behavior
ClassDescription
Class
MetaClass

Point
Rectangle
BitBit
CharacterScanner

Pen

DisplayObject
DisplayMedium
Form
Cursor
DisplayScreen
InfiniteForm
OpaqueForm
Path
Arc
Circle
Curve
Line
LinearFit
Spline
Graphics in the Smalltalk-80 system begin with the specification of BitBlt. Supported by Points, Rectangles, Forms, Pens, and Text, a wide variety of imagery can be created. The images in Figure 20.1 illustrate some of the graphical entities made possible by extending the use of these five kinds of objects.

The more artistic images in Figures 20.2 and 20.3 were created using the additional display objects available in the Smalltalk-80 system. The methods used in creating these images are described later. This chapter describes the available kinds of display objects and the various ways to manipulate them.

## Class DisplayObject

A Form is a kind of display object. There are others in the system. The way in which these objects are implemented is as a hierarchy of classes whose superclass is named DisplayObject. Form is a subclass in this hierarchy.

A display object represents an image that has a width, a height, an assumed origin at 0@0, and an offset from this origin relative to which the image is to be displayed. All display objects are similar in their ability to copy their image into another image, to be scaled, and to be translated. They differ in how their image is created.

There are three primary subclasses of DisplayObject. They are DisplayMedium, DisplayText, and Path.

* DisplayMedium represents images that can be "colored" (that is, filled with a gray tone) and bordered (that is, their rectangular outline is colored).

* DisplayText represents textual images.

* Path represents images composed as collections of images.

A Form is a subclass of DisplayMedium; it adds the bitmap representation of the image. All DisplayObjects provide source information for images; Forms provide both the source and the destination information.

Class DisplayObject supports accessing messages for manipulating the various aspects of the image.

### DisplayObject instance protocol

accessing

width

Answer the width of the receiver's bounding box, a rectangle that represents the boundaries of the receiver's image.

height

Answer the height of the receiver's bounding box.

extent

Answer a Point representing the width and height of the receiver's bounding box.
<figure><img src="image_215.png" /><figcaption>Figure 20.1</figcaption></figure>
DOCUMENT

Dear friend,

I am writing this message to express my sincere thanks for your help in solving my problem.

Through your help and guidance in solving my problem, I have been able to overcome my difficulty and achieve my goal.

Thank you so much for your help. Without your help, I would not have been able to complete this project on time. I am very grateful to you and your company.

I am very grateful to you. Your help has been very important to me, and I will remember your help forever.

Yours sincerely,
Lingling

11/14 - 12/1

<figure><img src="image_216.png" /></figure>

Lingling, can you call me back?

11/14

OK

The phone number you gave me is wrong. Can you call me back please?

Lingling, can you call me back?

11/14 - 12/1

Lingling, it's me again.

11/14 - 12/1

OK

11/14 - 12/1

IMAGE

<figure><img src="image_217.png" /></figure>

BRUSHES

<figure><img src="image_218.png" /></figure>

<figure><img src="image_219.png" /></figure>

IDIOM

<figure><img src="image_220.png" /></figure>
<figure><img src="image_221.png" /><figcaption>Figure 20.2</figcaption></figure>
<figure><img src="image_222.png" /><figcaption>Figure 20.3</figcaption></figure>
**offset**
Answer a Point representing the amount by which the receiver should be offset when it is displayed or its position is tested.

**offset: aPoint**
Set the receiver's offset.

**rounded**
Set the receiver's offset to the nearest integral amount.

DisplayObject also provides three kinds of messages that support transforming an image, displaying the image, and computing the display box, that is, a rectangular area that represents the boundaries of the area for displaying the image.

### DisplayObject instance protocol

<table><tr><td><strong>transforming</strong></td><td></td></tr><tr><td>scaleBy: aPoint</td><td>Scale the receiver's offset by aPoint.</td></tr><tr><td>translateBy: aPoint</td><td>Translate the receiver's offset by aPoint.</td></tr><tr><td>align: alignmentPoint with: relativePoint</td><td>Translate the receiver's offset such that alignmentPoint aligns with relativePoint.</td></tr></table>

<table><tr><td><strong>display box access</strong></td><td></td></tr><tr><td>boundingBox</td><td>Answer the rectangular area that represents the boundaries of the receiver's space of information.</td></tr></table>

<table><tr><td><strong>displaying</strong></td><td></td></tr><tr><td>displayOn: aDisplayMedium</td><td></td></tr><tr><td>at: aDisplayPoint</td><td></td></tr><tr><td>clippingBox: clipRectangle</td><td></td></tr><tr><td>rule: ruleInteger</td><td></td></tr><tr><td>mask: aForm</td><td>Display the receiver at location aDisplayPoint with rule, ruleInteger, and halftone mask, aForm. Information to be displayed must be confined to the area that intersects with clipRectangle.</td></tr></table>

There are actually several displaying messages not shown above. Alternative displaying messages progressively omit a keyword (starting from the last one) and provide default masks, rules, clipping rectangles, and positions, when needed. Basically the display screen itself is the default clipping rectangle, 0@0 is the default display position, and the object that represents the system display screen, Display, (a global variable) is the default display medium.

The message `displayAt: aDisplayPoint` provides a generally useful message when the only parameter not defaulted is the location at which the image is to be placed. The message `display` assumes that the display location is 0@0.

### DisplayObject instance protocol

**displayAt: aDisplayPoint**
Display the receiver at location aDisplayPoint with rule "over" or "storing"; halftone mask, a black Form; clipping rectangle the whose display screen; onto the display screen (Display).

**display**
Display the receiver at location 0@0.
These last two displaying messages are provided for textual objects such as String and Text as well, so that the programmer can place characters on the screen by evaluating an expression such as

'This is text to be displayed' displayAt: 100@100

Suppose locomotive is the Form that looks like

LOCOMOTIVE

<figure><img src="image_223.png" /></figure>

then it can be displayed on the screen with top left corner at location
50@150 by evaluating the expression

locomotive displayAt: 50@150

DISPLAY SCREEN

50,150

<figure><img src="image_224.png" /></figure>
Class
DisplayMedium

DisplayMedium is a subclass of DisplayObject that represents an object onto which images can be copied. In addition to those messages inherited from its superclass, DisplayMedium provides protocol for coloring the interior of images and placing borders around the display boxes of images. The "colors" are Forms that are already available in the system. These are black (the bitmap is all ones), white (all zeros), and various gray tones, either gray, veryLightGray, lightGray, or darkGray (mixtures of ones and zeros). Images of these colors are given below. All or portions of the DisplayMedium's area can be changed to one of these colors using the following messages.

DisplayMedium instance protocol

coloring

<table><tr><td>black</td><td>Change all of the receiver's area to black.</td></tr><tr><td>black: aRectangle</td><td>Change the area of the receiver defined by the argument, aRectangle, to black.</td></tr><tr><td>white</td><td>Change all of the receiver's area to white.</td></tr><tr><td>white: aRectangle</td><td>Change the area of the receiver defined by the argument, aRectangle, to white.</td></tr><tr><td>gray</td><td>Change all of the receiver's area to gray.</td></tr><tr><td>gray: aRectangle</td><td>Change the area of the receiver defined by the argument, aRectangle, to gray.</td></tr><tr><td>veryLightGray</td><td>Change all of the receiver's area to very light gray.</td></tr><tr><td>veryLightGray: aRectangle</td><td>Change the area of the receiver defined by the argument, aRectangle, to very light gray.</td></tr><tr><td>lightGray</td><td>Change all of the receiver's area to light gray.</td></tr><tr><td>lightGray: aRectangle</td><td>Change the area of the receiver defined by the argument, aRectangle, to light gray.</td></tr><tr><td>darkGray</td><td>Change all of the receiver's area to dark gray.</td></tr><tr><td>darkGray: aRectangle</td><td>Change the area of the receiver defined by the argument, aRectangle, to dark gray.</td></tr></table>

In the above messages, the origin of the argument, aRectangle, is in the coordinate system of the receiver.

Suppose picture is a kind of DisplayMedium that is 100 pixels in width and 100 pixels in height, and that box is an instance of Rectangle with origin at 30 @ 30 and width and height of 40. Then the protocol for filling the subarea of picture represented by box is illustrated by the following sequence.
<table><thead><tr><th>expression</th><th>result</th></tr></thead><tbody><tr><td>picture black: box</td><td></td></tr><tr><td>picture white: box</td><td></td></tr><tr><td>picture gray: box</td><td></td></tr><tr><td>picture lightGray: box</td><td></td></tr><tr><td>picture veryLightGray: box</td><td></td></tr></tbody></table>

<figure><img src="image_225.png" /></figure>

<figure><img src="image_226.png" /></figure>

<figure><img src="image_227.png" /></figure>

<figure><img src="image_228.png" /></figure>

<figure><img src="image_229.png" /></figure>
picture darkGray: box

<figure><img src="image_230.png" /></figure>

Part of an image can be filled with a pattern by sending a DisplayMedium a message to fill a particular sub-area with a halftone pattern. The other coloring messages use these filling messages in their implementation.

### DisplayMedium instance protocol

fill: aRectangle mask: aHalftoneForm

Change the area of the receiver defined by the argument, aRectangle, to white, by filling it with the 16 x 16-bit pattern, aHalftoneForm. The combination rule for copying the mask to the receiver is 3 (Form over).

fill: aRectangle rule: anInteger mask: aHalftoneForm

Change the area of the receiver defined by the argument, aRectangle, to white, by filling it with the 16 x 16 bit pattern, aHalftoneForm. The combination rule for copying the mask to the receiver is anInteger.

As an example, the result of evaluating the expressions

box ← 16@16 extent: 64@64.

picture fill: box mask: locomotive

where locomotive is a 16x16-bit Form, is

<figure><img src="image_231.png" /></figure>

The result of evaluating the sequence of two expressions

picture lightGray: box.

picture fill: box rule: Form under mask: locomotive
is

<figure><img src="image_232.png" /></figure>

Note that in the above, the rule Form under refers to an Integer combination rule. Messages to Form to access combination rules and halftone masks were defined in Chapter 18.

*Reversing* an image means changing all the bits in the area that are white to black and those that are black to white. Either all or part of an image can be reversed.

### DisplayMedium instance Protocol

reverse: aRectangle mask: aHalftoneForm

Change the area in the receiver defined by the argument, aRectangle, so that, in only those bits in which the mask, aHalftoneForm, is black, white bits in the receiver become black and black become white.

reverse: aRectangle

Change the area in the receiver defined by the argument, aRectangle, so that white is black and black is white. The default mask is Form black.

reverse

Change all of the receiver's area so that white is black and black is white.

The result of

picture reverse: box

on the last image is

<figure><img src="image_233.png" /></figure>

*Bordering* means coloring the outline of a rectangle. Bordering is done using a source Form and mask. Three messages provide methods for bordering an image.
DisplayMedium instance protocol

bordering

border: aRectangle widthRectangle: insets mask: aHalftoneForm

Color an outline around the area within the receiver defined by the argument, aRectangle. The color is determined by the mask, aHalftoneForm. The width of the outline is determined by the Rectangle, insets, such that, origin x is the width of the left side, origin y is the width of the top side, corner x is the width of the right side, and corner y is the width of the bottom side.

border: aRectangle width: borderWidth mask: aHalftoneForm

Color an outline around the area within the receiver defined by the argument, aRectangle. The color is determined by the mask, aHalftoneForm. The width of all the sides is borderWidth.

border: aRectangle width: borderWidth

Color an outline around the area within the receiver defined by the argument, aRectangle. The color is Form black. The width of all the sides is borderWidth.

Examples are

<table><thead><tr><td>expression</td><td>result</td></tr></thead><tbody><tr><td>picture<br>border: box<br>width: 8</td><td></td></tr></tbody></table>

picture
border: box
width: 8
mask: Form gray

<figure><img src="image_234.png" /></figure>
picture

border: box

width: Rectangle

(4 @ 16 corner: 4 @ 16)

mask: Form darkGray

<figure><img src="image_235.png" /></figure>

picture

border: box

width: 16

mask: locomotive

<figure><img src="image_236.png" /></figure>

The next sequence of images shows how bordering can be done by manipulating the size of the rectangle used to designate which area within picture should be changed.

<table><thead><tr><th>expression</th><th>result</th></tr></thead><tbody><tr><td>frame - 48@48 extent: 16@16.</td><td></td></tr><tr><td>picture white.</td><td></td></tr><tr><td>picture reverse: frame</td><td></td></tr><tr><td>frame - frame expandBy: 16.</td><td></td></tr><tr><td>picture</td><td></td></tr><tr><td>fill: frame</td><td></td></tr><tr><td>rule: Form reverse</td><td></td></tr><tr><td>mask: Form black.</td><td></td></tr></tbody></table>
frame → frame expandBy: 16.

picture

border: frame

width: 16

mask: locomotive

<figure><img src="image_237.png" /></figure>

picture

border: frame

width: 1

<figure><img src="image_238.png" /></figure>

## Forms

Class Form is the only subclass of DisplayMedium in the standard Smalltalk-80 system. It was introduced in Chapter 18 in which we defined messages that provide access to constants representing masks and combination rules (modes). As an illustration of the use of Forms in creating complex images, the following sequence of expressions creates the image shown at the beginning of this chapter as Figure 20.2.

Suppose we have two Forms available, each 120 bits wide and 180 bits high. We name them face25 and face75. These images were created using a scanner to digitize photographs of a gentleman when he was in his 20's and on the occasion of his 75th birthday.

<figure><img src="image_239.png" /></figure>

<figure><img src="image_240.png" /></figure>
The scanned images were scaled to the desired size and then combined with halftone masks in the following way. Two Arrays, each size 8, contain references to the halftone masks (masks) and the Forms (forms) used in creating each part of the final image.

masks ← Array new: 8.
masks at: 1 put: Form black.
masks at: 2 put: Form darkGray.
masks at: 3 put: Form gray.
masks at: 4 put: Form lightGray.
masks at: 5 put: Form veryLightGray.
masks at: 6 put: Form lightGray.
masks at: 7 put: Form gray.
masks at: 8 put: Form black.
forms ← Array new: 8.
forms at: 1 put: face25.
forms at: 2 put: face25.
forms at: 3 put: face25.
forms at: 4 put: face25.
forms at: 5 put: face75.
forms at: 6 put: face75.
forms at: 7 put: face75.
forms at: 8 put: face75

The variable i is the initial index into the first halftone and first Form used in forming the first sub-image of each row. Each time a complete row is displayed, i is incremented by 1. Each row consists of 5 elements. The variable index is used to index 5 halftones and five Forms; index is set to i at the outset of each row. Thus the first row is made up by combining elements 1, 2, 3, 4, and 5 of masks and forms; the second row is made up by combining elements 2, 3, 4, 5, and 6 of masks and forms; and so on. The y coordinate of each row changes by 180 pixels each time; the x coordinate of each column changes by 120 pixels.

i ← 1.

0 to: 540 by: 180 do:

[ :y | index ← i.

0 to: 480 by: 120 do:

[ :x | (forms at: index)
    displayOn: Display
    at: x@y
    clippingBox: Display boundingBox
    rule: Form over
    mask: (masks at: index).
    index ← index + 1].
    i ← i + 1]
## Other Forms

Two other kinds of forms exist in the system, InfiniteForm and OpaqueForm. These two classes are subclasses of DisplayObject, rather than of DisplayMedium. They therefore do not share Form's inherited ability to be colored and bordered. InfiniteForm represents a Form obtained by replicating a pattern Form indefinitely in all directions. Typically the overlapping views displayed in the Smalltalk-80 programming interface (as shown in Chapter 17) are placed over a light gray background; this background is defined by an InfiniteForm whose replicated pattern is Form gray. OpaqueForms represent a shape as well as a figure Form. The shape indicates what part of the background should be occluded in displaying the image, so that patterns other than black in the figure will still appear opaque. Instances of OpaqueForm support creating animations. Neither InfiniteForm nor OpaqueForm adds new protocol.

## Cursors

Form has two subclasses of interest, class Cursor and class DisplayScreen. The Smalltalk-80 system makes extensive use of Forms to indicate both the current location of the hardware pointing device and the current status of the system. A Form used in this way is referred to as a *cursor* since its primary purpose is to move over the screen in order to locate screen coordinates.

Instances of class Cursor are Forms that are 16 pixels wide and 16 pixels high. Class Cursor adds three new messages to the displaying protocol that it inherits from DisplayObject.

### Cursor instance protocol

displaying

show

Make the receiver be the current cursor shape.

showGridded: gridPoint

Make the receiver be the current cursor shape, forcing the location of cursor to the point nearest the location, gridPoint.

showWhile: aBlock

While evaluating the argument, aBlock, make the receiver be the cursor shape.

Several different cursors are supplied with the standard Smalltalk-80 system. They are shown in Figure 20.4 both small and enlarged in order to illustrate their bitmaps. The name of each cursor, given below its image, is the same as the message to class Cursor which accesses that particular Cursor. For example, the following expression shows a cursor that looks like eyeglasses on the screen while the system computes the factorial of 50. It then reverts to showing the original cursor shape.
<figure><img src="image_241.png" /><figcaption>normal</figcaption></figure>

<figure><img src="image_242.png" /><figcaption>execute</figcaption></figure>

<figure><img src="image_243.png" /><figcaption>up</figcaption></figure>

<figure><img src="image_244.png" /><figcaption>down</figcaption></figure>

<figure><img src="image_245.png" /><figcaption>origin</figcaption></figure>

<figure><img src="image_246.png" /><figcaption>corner</figcaption></figure>

<figure><img src="image_247.png" /><figcaption>read</figcaption></figure>

<figure><img src="image_248.png" /><figcaption>write</figcaption></figure>

<figure><img src="image_249.png" /><figcaption>crosshair</figcaption></figure>

<figure><img src="image_250.png" /><figcaption>move</figcaption></figure>

<figure><img src="image_251.png" /></figure>

<figure><img src="image_252.png" /><figcaption>Figure 20.4 marker</figcaption></figure>

<caption>wait</caption>

Cursor read showWhile: [50 factorial]

Changing the cursor shape is a very effective way of communicating with the user. Attention is always on the cursor, and changing its shape does not alter the appearance of the display.
## The Display Screen

DisplayScreen is another subclass of Form. There is usually only one instance of DisplayScreen in the system. It is referred to as Display, a global variable used to handle general user requests to deal with the whole display screen. In addition to the messages it inherits from its superclasses, DisplayObject, DisplayMedium, and Form, DisplayScreen provides class protocol for resetting the width, height, and displayed image of the screen.

The one case when multiple instances of DisplayScreen may exist is when (double-buffered) full screen animation is being done by alternating which instance of DisplayScreen supplies bits to the display hardware. Typically, full screen animation is not used, rather, animation is done within a smaller rectangular area. A hidden buffer of bits is used to form the next image. Each new image is displayed by copying the bits to the rectangular area using the copyBits: message of a BitBit.

## DisplayText

The second subclass of DisplayObject is class DisplayText. An instance of DisplayText provides a font index (1 through 10) and an emphasis (italic, bold, underline) for each character of an instance of String. DisplayText consists of a Text and a TextStyle. A TextStyle associates each font index with an actual font (set of glyphs). In addition to representing this mapping to the set of fonts, a DisplayText supports the ability to display the characters on the screen. It does not support the protocol needed to create a user interface for editing either the characters or the choice of fonts and emphasis; this protocol must be supplied by subclasses of DisplayText.

## Paths

A third subclass of DisplayObject is class Path. A Path is an OrderedCollection of Points and a Form that should be displayed at each Point. Complex images can be created by copying the Form along the trajectory represented by the Points.

Class Path is the basic superclass of the graphic display objects that represent trajectories. Instances of Path refer to an OrderedCollection and to a Form. The elements of the collection are Points. They can be added to the Path (add:); all Points that are described by some criterion
can be removed from the Path (`removeAllSuchThat`); and the Points can be enumerated, collected, and selected (`do`, `collect`, and `select`).

Path instance protocol

accessing

form Answer the Form referred to by the receiver.

form: aForm Set the Form referred to by the receiver to be aForm.

at: index Answer the Point that is the indexth element of the receiver's collection.

at: index put: aPoint Set the argument, aPoint, to be the indexth element of the receiver's collection.

size Answer the number of Points in the receiver's collection.

testing

isEmpty Answer whether the receiver contains any Points.

adding

add: aPoint Add the argument, aPoint, as the last element of the receiver's collection of Points.

removing

removeAllSuchThat: aBlock Evaluate the argument, aBlock, for each Point in the receiver. Remove those Points for which aBlock evaluates to true.

enumerating

do: aBlock Evaluate the argument, aBlock, for each Point in the receiver.

collect: aBlock Evaluate the argument, aBlock, for each Point in the receiver. Collect the resulting values into an OrderedCollection and answer the new collection.

select: aBlock Evaluate the argument, aBlock, for each Point in the receiver. Collect into an OrderedCollection those Points for which aBlock evaluates to true. Answer the new collection.

As an example, we create a "star" Path, and display a dot-shaped Form, referred to by the name dot, at each point on that Path.

aPath ← Path new form: dot.

aPath add: 150 @ 285.

aPath add: 400 @ 285.

aPath add: 185 @ 430.

aPath add: 280 @ 200.

aPath add: 375 @ 430.
aPath add: 150 @ 285.

aPath display

The resulting image is shown as the first path in Figure 20.5.

<figure><img src="image_253.png" /><figcaption>Figure 20.5</figcaption></figure>
There are three paths in Figure 20.5.

* an instance of Path, created as indicated above

* an instance of LinearFit, using the same collection of Points

* an instance of Spline, using the same collection of Points

A LinearFit is displayed by connecting the Points in the collection, in order.

aPath ← LinearFit new form: dot.

aPath add: 150 @ 285.

aPath add: 400 @ 285.

aPath add: 185 @ 430.

aPath add: 280 @ 200.

aPath add: 375 @ 430.

aPath add: 150 @ 285.

aPath display

The Spline is obtained by fitting a cubic spline curve through the Points, again, in order. The order in which the Points are added to the Path significantly affects the outcome.

aPath ← Spline new form: dot.

aPath add: 150 @ 285.

aPath add: 400 @ 285.

aPath add: 185 @ 430.

aPath add: 280 @ 200.

aPath add: 375 @ 430.

aPath add: 150 @ 285.

aPath computeCurve.

aPath display

LinearFit and Spline are defined as subclasses of Path. In order to support the protocol of DisplayObject, each of these subclasses implements the message displayOn:at:clippingBox:rule:mask:.

Straight lines can be defined in terms of Paths. A Line is a Path specified by two points. An Arc is defined as a quarter of a circle. Instances of class Arc are specified to be one of the four possible quarters; they know their center Point and the radius of the circle. A Circle, then, is a kind of Arc that represents all four quarters. Again, in order to support the protocol of DisplayObject, each of these three classes (Line, Arc, and Circle) implements the messages displayOn:at:clippingBox:rule:mask:.

Class Curve is a subclass of Path. It represents a hyperbola that is tangent to lines determined by Points p1, p2 and p3, and that passes
through Points p1 and p3. The displaying message for Curve is defined as shown in the method below.

displayOn: aDisplayMedium

at: aPoint

clippingBox: aRectangle

rule: anInteger

mask: aForm

| pa pb k s p1 p2 p3 line |

line ← Line new.

line form: self form.

self size < 3 ifTrue: [self error: 'Curves are defined by three points'].

p1 ← self at: 1.

p2 ← self at: 2.

p3 ← self at: 3.

s ← Path new.

s add: p1.

pa ← p2 - p1.

pb ← p3 - p2.

k ← 5 max: pa x abs + pa y abs + pb x abs + pb y abs // 20.

"k is a guess as to how many line segments to use to approximate the curve."

1 to: k do:

[:i| s add:

pa*i//k + p1*(k-i) + (pb*(i-1)//k + p2*(i-1))//((k-1)].

s add: p3.

1 to: s size do:

[:i|

line at: 1 put: (s at: i).

line at: 2 put: (s at: i + 1).

line displayOn: aDisplayMedium

at: aPoint

clippingBox: aRectangle

rule: anInteger

mask: aForm]

The algorithm was devised by Ted Kaehler. Basically the idea is to divide the line segments p1, p2 and p3 into 10 sections. Numbering the sections as shown in the diagram, draw a line connecting point 1 on p1, p2 to point 1 on p2, p3; draw a line connecting point 2 on p1, p2 to point 2 on p2, p3; and so on. The hyperbola is the path formed from p1 to p3 by interpolating along the line segments formed on the outer shell.

Several curves are shown in Figure 20.6. The curves are the black lines; the gray lines indicate the lines connecting the points that were used to define the curves.
<figure><img src="image_254.png" /></figure>

Two Curves were used to create the image shown in Figure 20.3. The Form was one of the images of the gentleman used in Figure 20.2.

## Image Manipulation with Forms

We have shown in Chapter 18 how BitBlt can copy shapes and how repeated invocation can synthesize more complex images such as text and lines. BitBlt is also useful in the manipulation of existing images. For example, text can be made to look bold by ORing over itself, shifted right by one pixel. Just as complex images can be built from simple ones, complex processing can be achieved by repeated application of simple operations. In addition to its obvious manifestation in the DisplayObject protocol, the power of BitBlt is made available for manipulating images through such messages as copy:from:in:rule:.

We present here four examples of such structural manipulation: magnification, rotation, area filling, and the Game of Life.

A simple way to magnify a stored Form would be to copy it to a larger Form, making a big dot for every little dot in the original. For a height h and width w, this would take h*w operations. The algorithm presented here (as two messages to class Form) uses only a few more than h + w operations.

magnify: aRectangle by: scale

| wideForm bigForm spacing |
spacing ← 0 @ 0.

### Magnification
<figure><img src="image_255.png" /><figcaption>Figure 20.6</figcaption></figure>

wideForm -->
  Form new
    extent: aRectangle width * scale x @ aRectangle height.
wideForm
  spread: aRectangle
  from: self
  by: scale x
  spacing: spacing x
  direction: 1 @ 0.
bigForm --> Form new extent: aRectangle extent * scale.
bigForm
  spread: wideForm boundingBox
  from: wideForm
  by: scale y
  spacing: spacing y
  direction: 0 @ 1.
tbigForm
spread: rectangle

from: aForm

by: scale

spacing: spacing

direction: dir

| slice sourcePt |
slice ← 0@0 corner: dir transpose * self extent + dir.
sourcePt ← rectangle origin.

1 to: (rectangle extent dotProduct: dir) do:

[ :i |
"slice up original area"
self copy: slice
from: sourcePt
in: aForm
rule: 3.
sourcePt ← sourcePt + dir.
slice moveBy: dir * scale].

1 to: scale - spacing - 1 do:

[ :i |
"smear out the slices, leave white space"
self copy: (dir corner: self extent)
from: 0 @ 0
in: self
rule: 7]

The magnification proceeds in two steps. First, it slices up the image into vertical strips in wideForm separated by a space equal to the magnification factor. These are then smeared, using the ORing function, over the intervening area to achieve the horizontal magnification. The process is then repeated from wideForm into bigForm, with horizontal slices separated and smeared in the vertical direction, achieving the desired magnification. Figure 20.7 illustrates the progress of the above algorithm in producing the magnified "7".

<figure><img src="image_256.png" /><figcaption>Figure 20.7</figcaption></figure>
Rotation

Another useful operation on images is rotation by a multiple of 90 degrees. Rotation is often thought to be a fundamentally different operation from translation, and this point of view would dismiss the possibility of using BitBlt to rotate an image. However, the first transformation shown in Figure 20.8 is definitely a step toward rotating the image shown; all that remains is to rotate the insides of the four cells that have been permuted. The remainder of the figure shows each of these cells being further subdivided, its cells being similarly permuted, and so on. Eventually each cell being considered contains only a single pixel. At this point, no further subdivision is required, and the image has been faithfully rotated.

Each transformation shown in Figure 20.8 would appear to require successively greater amounts of computation, with the last one requiring several times more than h\*w operations. The tricky aspect of the algorithm below is to permute the subparts of every subdivided cell at once, thus performing the entire rotation in a constant times $log_2(h)$ operations. The parallel permutation of many cells is accomplished with the aid of two auxiliary Forms. The first, mask, carries a mask that selects the upper left quadrant of every cell; the second, temp, is used for temporary storage. A series of operations exchanges the right and left halves of every cell, and then another series exchanges the diagonal quadrants, achieving the desired permutation.

rotate

| mask temp quad all |

all ← self boundingBox.

mask ← Form extent: self extent.

temp ← Form extent: self extent.

mask white. "set up the first mask"

mask black: (0@0 extent: mask extent // 2).

quad ← self width // 2.

[quad >= 1] while True:

"First exchange left and right halves"

temp copy: all from: 0@0 in: mask rule: 3.

temp copy: all from: 0@quad negated in: mask rule: 7.

temp copy: all from: 0@0 in: self rule: 1.

self copy: all from: 0@0 in: temp rule: 6.

temp copy: all from: quad@0 in: self rule: 6.

self copy: all from: quad@0 in: self rule: 7.

self copy: all from: quad negated@0 in: temp rule: 6.

"then flip the diagonals"

temp copy: all from: 0@0 in: self rule: 3.

temp copy: all from: quad@quad in: self rule: 6.

temp copy: all from: 0@0 in: mask rule: 1.
<figure><img src="image_257.png" /><figcaption>Figure 20.8</figcaption></figure>
self copy: all from: 0@0 in: temp rule: 6.

self copy: all from: quad negated@quad negated in: temp rule: 6.

"Now refine the mask"

mask copy: all from: (quad//2)@(quad//2) in: mask rule: 1.

mask copy: all from: 0@quad negated in: mask rule: 7.

mask copy: all from: quad negated@0 in: mask rule: 7.

quad `←` quad // 2]

Figure 20.9 traces the state of temp and self after each successive operation.

<figure><img src="image_258.png" /><figcaption>Figure 20.9</figcaption></figure>

In the Figure 20.9, the offsets of each operation are not shown, though they are given in the program listing. After twelve operations, the desired permutation has been achieved. At this point the mask evolves to a finer grain, and the process is repeated for more smaller cells. Figure 20.10 shows the evolution of the mask from the first to the second stage of refinement.

<figure><img src="image_259.png" /><figcaption>Figure 20.10</figcaption></figure>

The algorithm presented here for rotation is applicable only to square forms whose size is a power of two. The extension of this technique to arbitrary rectangles is more involved. A somewhat simpler exercise is to apply the above technique to horizontal and vertical reflections about the center of a rectangle.
## Area Filling

A useful operation on Forms is to be able to fill the interior of an outlined region with a halftone mask. The method given here takes as one argument a Point that marks a location in the interior of the region. A mark is placed at this location as a *seed*, and then the *seed* is smeared (in all four directions) into a larger blob until it extends to the region boundary. At each stage of the smearing process, the original Form is copied over the blob using the “erase” rule. This has the effect of trimming any growth which would have crossed the region borders. In addition, after every ten smear cycles, the resulting smear is compared with its previous version. When there is no change, the smear has filled the region and halftoning is applied throughout.

### shapeFill: aMask interiorPoint: interiorPoint

| directors smearForm previousSmear all cycle noChange |

all ← self boundingBox.

smearForm ← Form extent: self extent.

"Place a seed in the interior"

smearForm valueAt: interiorPoint put: 1.

previousSmear ← smearForm deepCopy.

dirs ← Array with: 1@0 with: -1@0 with: 0@1 with: 0@-1.

cycle ← 0.

"check for no change every 10 smears"

(cycle ← cycle + 1) \ 10 = 0 and:

[previousSmear copy: all

from: 0@0

in: smearForm

rule: Form reverse.

noChange ← previousSmear isAllWhite.

previousSmear copy: all from: 0@0 in: smearForm rule: Form over.

noChange]]

whileFalse:

[dirs do:

[:dir |

"smear in each of the four directions"

smearForm copy: all

from: dir

in: smearForm

rule: Form under.

"After each smear, trim around the region border"

smearForm copy: all from: 0@0 in: self rule: Form erase]].

"Now paint the filled region in me with aMask"

smearForm displayOn: self

at: 0@0

clippingBox: self boundingBox

rule: Form under

mask: aMask
Figure 20.11 shows a Form with a flower-shaped region to be filled. Successive smears appear below, along with the final result.

<figure><img src="image_260.png" /><figcaption>Figure 20.11</figcaption></figure>

## *The Game of Life*

Conway's Game of Life is a simple rule for successive populations of a bitmap. The rule involves the neighbor count for each cell—how many of the eight adjacent cells are occupied. Each cell will be occupied in the next generation if it has exactly three neighbors, or if it was occupied and has exactly two neighbors. This is explained as follows: three neighboring organisms can give birth in an empty cell, and an existing organism will die of exposure with less than two neighbors or from overpopulation with more than three neighbors. Since BitBlt cannot add, it would seem to be of no use in this application. However BitBlt's combination rules, available in the Form operations, do include the rules for partial sum (XOR) and carry (AND). With some ingenuity and a fair amount of extra storage, the next generation of any size of bitmap can be computed using a *constant* number of BitBlt operations.

### `nextLifeGeneration`

```
nbr1 nbr2 nbr4 carry2 carry4 all delta |
nbr1  Form extent: self extent.
nbr2  Form extent: self extent.
nbr4  Form extent: self extent.
carry2 Form extent: self extent.
carry4 Form extent: self extent.
all   self boundingBox.
1 to: 8 do:
    [ :i |
        "delta is the offset of the eight neighboring cells"
        delta  ((#(-1 0 1 1 1 0 -1 -1) at: i)
                 @ (#(-1 -1 -1 0 1 1 1 0) at: i)).
carry2 copy: all from: 0@0 in: nbr1 rule: 3.
carry2 copy: all from: delta in: self rule: 1. "AND for carry into 2"
```
<figure><img src="image_261.png" /><figcaption>Figure 20.12</figcaption></figure>

nbr1 copy: all from: delta in: self rule: 6. "XOR for sum 1"

carry4 copy: all from: 0@0 in: nbr2 rule: 3.

carry4 copy: all from: 0@0 in: carry2 rule: 1. "AND for carry into 4"

nbr2 copy: all from: 0@0 in: carry2 rule: 6. "XOR for sum 2"

nbr4 copy: all from: 0@0 in: carry4 rule: 6].

"XOR for sum 4 (ignore carry into 8)"

self copy: all from: 0@0 in: nbro rule: 1.

nbr1 copy: all from: 0@0 in: nbro rule: 1.

self copy: all from: 0@0 in: nbro rule: 7.

self copy: all from: 0@0 in: nbro rule: 4

"compute next generation"

As shown in Figure 20.12, the number of neighbors is represented using three image planes for the 1's bit, 2's bit and 4's bit of the count in binary. The 8's bit can be ignored, since there are no survivors in that case, which is equivalent to zero (the result of ignoring the 8's bit). This Smalltalk-80 method is somewhat wasteful, as it performs the full carry propagation for each new neighbor, even though nothing will propagate into the 4-plane until at least the fourth neighbor.
<figure><img src="image_262.png" /></figure>
PART THREE

Part Three is an example of modeling discrete, event-driven simulations in the Smalltalk-80 system. A simulation is a representation of a system of objects in a real or fantasy world. The purpose of creating a computer simulation is to provide a framework in which to understand the simulation situation. In order to create the Smalltalk-80 simulations, we first describe a hierarchy of classes that represent probability distributions. Various kinds of probability distributions are used to determine arrival times of objects, such as customers, into a simulation; they are also used to randomly select response or service times for workers in a simulation. The example class SimulationObject represents any kind of object

<figure><img src="image_263.png" /></figure>
that enters into a simulation in order to carry out one or more
tasks; class Simulation represents the simulation itself and provides
the control structures for admitting and assigning tasks to new
SimulationObjects.

The objects that participate in event-driven simulations operate
more or less independently of one another. So it is necessary to
consider the problem of coordinating and synchronizing their ac-
tivities. The Smalltalk-80 system classes, Process, Semaphore, and
SharedQueue, provide synchronization facilities for otherwise inde-
pendent simulation events. The framework of classes defined in
this part support the creation of simulations that use consumable,
nonconsumable, and/or renewable resources. They also provide a
number of ways in which a programmer can gather statistics
about a running simulation.
# Probability Distributions

## Probability Distribution Framework

*Definitions*

*Introductory Examples*

*Class Probability Distribution*

*Class Discrete Probability*

*Class Continuous Probability*

## Discrete Probability Distributions

*The Bernoulli Distribution*

*The Binomial Distribution*

*The Geometric Distribution*

*The Poisson Distribution*

## Continuous Probability Distributions

*The Uniform Distribution*

*The Exponential Distribution*

*The Gamma Distribution*

*The Normal Distribution*

<figure><img src="image_264.png" /></figure>
## Probability Distribution Framework

Applications, such as simulations, often wish to obtain values associated with the outcomes of chance experiments. In such experiments, a number of possible questions might be asked, such as:

* What is the probability of a certain event occurring?

* What is the probability of one of several events occurring?

* What is the probability that, in the next N trials, at least one successful event will occur?

* How many successful events will occur in the next N trials?

* How many trials until the next successful event occurs?

## Definitions

In the terminology of simulations, a *trial* is a tick of the simulated clock (where a clock tick might represent seconds, minutes, hours, days, months, or years, depending on the unit of time appropriate to the situation). An *event* or *success* is a job arrival such as a car arriving to a car wash, a customer arriving in a bank, or a broken machine arriving in the repair shop.

In the realm of statistics, the probability that an event will occur is typically obtained from a large number of observations of actual trials. For example, a long series of observations of a repair shop would be needed in order to determine the probability of a broken machine arriving in the shop during a fixed time interval. In general, several events might occur during that time interval. The set of possible events is called a *sample space*. A *probability function* on a sample space is defined as an association of a number between 0 and 1 with each event in the sample space. The probability or chance that at least one of the events in the sample space will occur is defined as 1; if p is the probability that event E will occur, then the probability that E will not occur is defined as $1 - p$.

Sample spaces are classified into two types: *discrete* and *continuous*. A sample space is discrete if it contains a finite number of possible events or an infinite number of events that have a one-to-one relationship with the positive integers. For example, the six possible outcomes of a throw of a die constitute a discrete sample space. A sample space is continuous if it contains an ordered, infinite number of events, for example, any number between 1.0 and 4.0. Probability functions on each of these types of sample spaces are appropriately named *discrete probability functions* and *continuous probability functions*.

A *random variable* is a real-valued function defined over the events in a sample space. The adjectives "discrete" and "continuous" apply to random variables according to the characteristic of their range. The
probability function of a random variable is called a *probability distribution*; the values in the range of the function are the probabilities of occurrence of the possible values of the random variable. The *density* is a function that assigns probabilities to allowed ranges of the random variable. Any function can be a *density function* (discrete or continuous) if it has only positive values and its integral is 1.

Another useful function that plays an important role in simulations is called the *cumulative distribution function*. It gives the probability that the value of the random variable is within a designated range. For example, the cumulative distribution function answers the question: what is the probability that, in the throw of a die, the side is 4 or less?

The *mean* is defined as the average value that the random variable takes on. The *variance* is a measure of the spread of the distribution. It is defined as the average of the square of the deviations from the mean.

## Introductory Examples

Two examples of sample spaces are given here before entering into a detailed description of the Smalltalk-80 classes. Suppose the sample space is the possible outcomes of a toss of a die. The sample space consists of

* event 1: 1 is thrown

* event 2: 2 is thrown

* event 3: 3 is thrown

* event 4: 4 is thrown

* event 5: 5 is thrown

* event 6: 6 is thrown

Then, for this discrete probability distribution, the probability function for any event is

$$f(\text{event}) = 1/6$$

If X is a random variable over the sample space, then the probability distribution of X is g(X) such that

$$g(X=1) = f(\text{event1}) = 1/6, \dots, g(X=6) = f(\text{event6}) = 1/6.$$

The density of X is 1/6 for any value of X.

The cumulative distribution function of X is

$$c(a, b) = \sum_{n}^{b} g(X)$$

For example,

$$c(2,4) = g(X=2) + g(X=3) + g(X=4) = 1/6 + 1/6 + 1/6 = 1/2$$
As an example of a continuous probability distribution, let the sample space be the time of day where the start of the day is time = 12:00 a.m. and the end of the day is time = 11:59:59.99... p.m. The sample space is the interval between these two times.

The probability function is

$$f(\text{event}) = \text{probability } (\text{event}_i \le \text{time} < \text{event}_j)$$

where $event_i < event_j$. The density of X is

$$g(X = \text{any specified time}) = 0$$

Suppose this is a 24-hour clock. Then the probability that, upon looking at a clock, the time is between 1:00 p.m. and 3:00 p.m., is defined by the cumulative distribution function

$$c(1:00, 3:00) = \int_{1:00}^{3:00} g(X)$$

$g(X)$ is uniform over 24 hours. So

$$c(1:00, 3:00) = c(1:00, 2:00) + c(2:00, 3:00) = 1/24 + 1/24 = 1/12.$$

Class
ProbabilityDistribution

The superclass for probability distributions provides protocol for obtaining one or more random samplings from the distribution, and for computing the density and cumulative distribution functions. It has a class variable `U` which is an instance of class `Random`. Class `Random` provides a simple way in which to obtain a value with uniform probability distribution over the interval `[0,1]`.

Like class `Random`, `ProbabilityDistribution` is a `Stream` that accesses elements generated algorithmically. Whenever a random sampling is required, the message next is sent to the distribution. `ProbabilityDistribution` implements next by returning the result of the message `inverseDistribution`: `var`, where the argument `var` is a random number between 0 and 1. Subclasses of `ProbabilityDistribution` must implement `inverseDistribution`: in order to map `[0,1]` onto their sample space, or else they must override the definition of next. The message next: is inherited from the superclass `Stream`.

<table><tr><td>class name</td><td><code>ProbabilityDistribution</code></td></tr><tr><td>superclass</td><td><code>Stream</code></td></tr><tr><td>class variable names</td><td><code>U</code></td></tr><tr><td>class methods</td><td></td></tr><tr><td>class initialization</td><td></td></tr></table>

**initialize**

"Uniformly distributed random numbers in the range [0, 1]."
`U` ← Random new
instance creation

**new**

`tself basicNew`

instance methods

random sampling

**next**

"This is a general random number generation method for any probability law; use the (0, 1) uniformly distributed random variable U as the value of the law's distribution function. Obtain the next random value and then solve for the inverse. The inverse solution is defined by the subclass."

`tself inverseDistribution: U next`

probability functions

**density: x**

"This is the density function."

`self subclassResponsibility`

**distribution: aCollection**

"This is the cumulative distribution function. The argument is a range of contiguous values of the random variable. The distribution is mathematically the area under the probability curve within the specified interval."

`self subclassResponsibility`

private

**inverseDistribution: x**

`self subclassResponsibility`

**computeSample: m outOf: n**

"Compute the number of ways one can draw a sample without replacement of size m from a set of size n."

`m > n ifTrue: [10.0]`

`tn factorial / (n-m) factorial`

In order to initialize the class variable U, evaluate the expression

ProbabilityDistribution initialize

Computing the number of ways one can draw a sample without replacement of size m from a set of size n will prove a useful method shared by the subclass implementations that follow.

Class
DiscreteProbability

The two types of probability distributions, discrete and continuous, are specified as subclasses of class ProbabilityDistribution; each provides an implementation of the cumulative distribution function which depends
on the density function. These implementations assume that the density function will be provided in subclasses.

<table><tr><td>class name</td><td>DiscreteProbability</td></tr><tr><td>superclass</td><td>ProbabilityDistribution</td></tr><tr><td>instance methods</td><td></td></tr></table>

### probability functions

#### distribution: aCollection

"Answer the sum of the discrete values of the density function for each element in the collection."

```
| t |
t -> 0.0.
aCollection do: [ :i | t -> t + (self density: i)].
↑t
```

Class
ContinuousProbability

<table><tr><td>class name</td><td>ContinuousProbability</td></tr><tr><td>superclass</td><td>ProbabilityDistribution</td></tr><tr><td>instance methods</td><td></td></tr></table>

### probability functions

#### distribution: aCollection

"This is a slow and dirty trapezoidal integration to determine the area under the probability function curve y=density(x) for x in the specified collection. The method assumes that the collection contains numerically-ordered elements."

```
| t aStream x1 x2 y1 y2 |
t -> 0.0.
aStream ← ReadStream on: aCollection.
x2 ← aStream next.
y2 ← self density: x2.
[x1 ← x2. x2 ← aStream next]
whileTrue:
    [y1 ← y2.
y2 ← self density: x2.
t ← t + ((x2-x1)*(y2+y1))].
↑t*0.5
```

In order to implement the various kinds of probability distributions as subclasses of class DiscreteProbability or ContinuousProbability, both the density function and the inverse distribution function (or a different response to next) must be implemented.
## Discrete Probability Distributions

As an example of a discrete probability distribution, take the heights of a class of 20 students and arrange a table indicating the frequency of students having the same heights (the representation of height is given in inches). The table might be

<table><thead><tr><td>measured height</td><td>number of students</td></tr></thead><tbody><tr><td>60"</td><td>3</td></tr><tr><td>62"</td><td>2</td></tr><tr><td>64"</td><td>4</td></tr><tr><td>66"</td><td>3</td></tr><tr><td>68"</td><td>5</td></tr><tr><td>70"</td><td>3</td></tr></tbody></table>

Given this information, we might ask the question: what is the probability of randomly selecting a student who is 5'4" tall? This question is answered by computing the density function of the discrete probability associated with the observed information. In particular, we can define the density function in terms of the following table.

<table><thead><tr><td>height</td><td>density</td></tr></thead><tbody><tr><td>60"</td><td>3/20</td></tr><tr><td>62"</td><td>2/20</td></tr><tr><td>64"</td><td>4/20</td></tr><tr><td>66"</td><td>3/20</td></tr><tr><td>68"</td><td>5/20</td></tr><tr><td>70"</td><td>3/20</td></tr></tbody></table>

Suppose we define a subclass of DiscreteProbability which we name SampleSpace, and provide the above table as the value of an instance variable of SampleSpace. The response to the message density: x is the value associated with x in the table (in the example, the value of x is one of the possible heights); the value of the density of x, where x is not in the table, is 0. The probability of sampling each element of the collection is equally likely, so the density function is the reciprocal of the size of the collection. Since there may be several occurrences of a data element, the probability must be the appropriate sum of the probability for each occurrence. The implementation of the cumulative distribution function is inherited from the superclass.
<table><tr><td>class name</td><td>SampleSpace</td></tr><tr><td>superclass</td><td>DiscreteProbability</td></tr><tr><td>instance variable names</td><td>data</td></tr><tr><td>class methods</td><td></td></tr><tr><td>instance creation</td><td></td></tr></table>

**data: aCollection**

↑self new: aCollection

instance methods

probability functions

**density: x**

"x must be in the sample space; the probability must sum over all occurrences of x in the sample space"

(data includes: x)

ifTrue: [↑(data occurrencesOf: x) / data size]

ifFalse: [10]

private

**inverseDistribution: x**

↑data at: (x*data size) truncated + 1

**setData: aCollection**

data ← aCollection

Suppose heights is an instance of SampleSpace. The data is an array of 20 elements, the height of each student in the example.

heights ← SampleSpace data:

#(60 60 60 62 62 64 64 64 64 66 66 66 68 68 68 68 68 70 70 70)

Then we can ask heights the question, what is the probability of randomly selecting a student with height 64, or what is the probability of randomly selecting a student whose height is between 60" and 64"? The answer to the first question is the density function, that is, the response to the message density: 64. The answer to the second is the cumulative distribution function; that is, the answer is the response to the message distribution: (60 to: 64 by: 2).

SampleSpace, in many ways, resembles a discrete uniform distribution. In general, a discrete uniform distribution is defined over a finite range of values. For example, we might specify a uniform distribution defined for six values: 1, 2, 3, 4, 5, 6, representing the sides of a die. The density function, as the constant 1/6, indicates that the die is "fair," i.e., the probability that each of the sides will be selected is the same.

We define four kinds of discrete probability distributions that are useful in simulation studies. They are Bernoulli, Binomial, Geometric,
and Poisson. A Bernoulli distribution answers the question, will a success occur in the next trial? A binomial distribution represents N repeated, independent Bernoulli distributions, where N is greater than or equal to one. It answers the question, how many successes are there in N trials? Taking a slightly different point of view, the geometric distribution answers the question, how many repeated, independent Bernoulli trials are needed before the first success is obtained? A Poisson distribution is used to answer the question, how many events occur in a particular time interval? In particular, the Poisson determines the probability that K events will occur in a particular time interval, where K is greater than or equal to 0.

The Bernoulli Distribution

A Bernoulli distribution is used in the case of a sample space of two possibilities, each with a given probability of occurrence. Examples of sample spaces consisting of two possibilities are

* The throw of a die, in which I ask, did I get die side 4? The probability of success if the die is fair is 1/6; the probability of failure is 5/6.

* The toss of a coin, in which I ask, did I get heads? The probability of success if the coin is fair is 1/2; the probability of failure is 1/2.

* The draw of a playing card, in which I ask, is the playing card the queen of hearts? The probability of success if the card deck is standard is 1/52; the probability of failure is 51/52.

According to the specification of class Bernoulli, we create a Bernoulli distribution using expressions of the form

Bernoulli parameter: 0.17

In this example, we have created a Bernoulli distribution with a probability of success equal to 0.17. The probability of success is also referred to as the mean of the Bernoulli distribution.

The parameter, prob, of a Bernoulli distribution is the probability that one of the two possible outcomes will occur. This outcome is typically referred to as the successful one. The parameter prob is a number between 0.0 and 1.0. The density function maps the two possible outcomes, 1 or 0, onto the parameter prob or its inverse. The cumulative distribution, inherited from the superclass, can only return values prob or 1.

<table><tr><td>class name</td><td>Bernoulli</td></tr><tr><td>superclass</td><td>DiscreteProbability</td></tr><tr><td>instance variable names</td><td>prob</td></tr></table>
class methods

instance creation

**parameter: aNumber**

(aNumber between: 0.0 and: 1.0)

ifTrue: [↑self new setParameter: aNumber]

ifFalse: [self error: 'The probability must be between 0.0 and 1.0']

instance methods

accessing

**mean**

↑prob

**variance**

↑prob * (1.0 - prob)

probability functions

**density: x**

"let 1 denote success"

x = 1 ifTrue: [↑prob].

"let 0 denote failure"

x = 0 ifTrue: [↑1.0 - prob].

self error: 'outcomes of a Bernoulli can only be 1 or 0'

private

**inverseDistribution: x**

"Depending on the random variable x, the random sample is 1 or 0, denoting success or failure of the Bernoulli trial."

x <= prob

ifTrue: [↑1]

ifFalse: [↑0]

**setParameter: aNumber**

prob ← aNumber

Suppose, at some stage of playing a card game, we wish to determine whether or not the first draw of a card is an ace. Then a possible (randomly determined) answer is obtained by sampling from a Bernoulli distribution with mean of 4/52.

(Bernoulli parameter: 4/52) next

Let's trace how the response to the message next is carried out.

The method associated with the unary selector next is found in the method dictionary of class ProbabilityDistribution. The method returns the value of the expression self inverseDistribution: U next. That is, a uniformly distributed number between 0 and 1 is obtained (U next) in
order to be the argument of inverseDistribution. The method associated with the selector inverseDistribution: is found in the method dictionary of class Bernoulli. This is the inverse distribution function, a mapping from a value prob of the cumulative distribution function onto a value, x, such that prob is the probability that the random variable is less than or equal to x. In a Bernoulli distribution, x can only be one of two values; these are denoted by the integers 1 and 0.

## The Binomial Distribution

In simulations, we use a Bernoulli distribution to tell us whether or not an event occurs, for example, does a car arrive in the next second or will a machine break down today? The binomial distribution answers how many successes occurred in N trials. The density function of a Bernoulli distribution tells us the probability of occurrence of one of two events. In contrast, the density function of a binomial answers the question, what is the probability that x successes will occur in the next N trials?

The binomial distribution represents N repeated, independent Bernoulli trials. It is the same as Bernoulli for N = 1. In the description of class Binomial, a subclass of class Bernoulli, the additional instance variable, N, represents the number of trials. That is, given an instance of Binomial, the response to the message next answers the question, how many successes are there in N trials?

The probability function for the binomial is

$$ \frac{N!}{x!(N-x)!} p^x (1-p)^{N-x} $$

where x is the number of successes and p is the probability of success on each trial. The notation "!" represents the mathematical factorial operation. The first terms can be reduced to computing the number of ways to obtain x successes out of N trials, divided by the number of ways to obtain x successes out of x trials. Thus the implementation given below makes use of the method computeSample: a outOf: b provided in the superclass ProbabilityDistribution.

<table><tr><td>class name</td><td>Binomial</td></tr><tr><td>superclass</td><td>Bernoulli</td></tr><tr><td>instance variable names</td><td>N</td></tr><tr><td>class methods</td><td></td></tr></table>

instance creation

**events: n mean: m**

n truncated <= 0 if True: [self error: 'number of events must be > 0']

↑self new events: n mean: m
### instance methods

### random sampling

**next**

| t |

"A surefire but slow method is to sample a Bernoulli N times. Since the Bernoulli returns 0 or 1, the sum will be between 0 and N."

t ← 0.

N timesRepeat: [t ← t + super next].

↑t

### probability functions

**density: x**

(x between: 0 and: N)

ifTrue: [↑((self computeSample: x outOf: N)

/ (self computeSample: x outOf: x))

* (prob raisedTo: x) * ((1.0 - prob) raisedTo: N - x)]

ifFalse: [↑0.0]

### private

**events: n mean: m**

N → n truncated.

self setParameter: m/N

"setParameter: is implemented in my superclass"

Let's use flipping coins as our example. In five trials of a coin flip, where the probability of heads is 0.5, the Bernoulli distribution with parameter 0.5 represents one trial, i.e., one coin flip.

sampleA ← Bernoulli parameter: 0.5

The result of

sampleA next

is either 1 or 0, answering the question, did I get heads?
Suppose instead we create

sampleB ← Binomial events: 5 mean: 2.5

The result of

sampleB next
is a number between 0 and 5, answering the question, how many heads did I get in 5 trials?

The message

sampleB density: 3

is a number between 0 and 1, answering the question, what is the probability of getting heads 3 times in 5 trials?

The Geometric
Distribution

Suppose we wish to answer the question, how many repeated, independent Bernoulli trials are needed before the first success is obtained? This new perspective on a Bernoulli distribution is the geometric distribution. As in the Bernoulli and binomial cases, the probability of a success is between 0.0 and 1.0; the mean of the geometric is the reciprocal of the success probability. Thus if we create a geometric distribution as

Geometric mean: 5

then the mean is 5 and the probability of a success is 1/5. The mean must be greater than or equal to 1.

A geometric distribution is more suitable for an event-driven simulation design than a Bernoulli or binomial. Instead of asking how many cars arrive in the next 20 seconds (a binomial question), the geometric distribution asks, how many seconds before the next car arrives. In event-driven simulations, the (simulated) clock jumps to the time of the next event. Using a geometric distribution, we can determine when the next event will occur, set the clock accordingly, and then carry out the event, potentially "saving" a great deal of real time.

The probability distribution function is

$$p(1-p)^{x-1}$$

where x is the number of trials required and p is the probability of success on a single trial.

class name Geometric
superclass Bernoulli
class methods

instance creation

mean: m

tself parameter: 1/m

"Note that the message parameter: is implemented in the superclass"
instance methods

accessing

**mean**

↑ 1.0 / prob

**variance**

↑ (1.0 − prob) / prob squared

probability functions

**density: x**

x > 0 ifTrue: [↑prob * ((1.0−prob) raisedTo: x−1)]

ifFalse: [↑0.0]

private

**inverseDistribution: x**

"Method is from Knuth, Vol. 2, pp.116–117"

↑(x ln / (1.0−prob) ln) ceiling

Suppose, on the average, two cars arrive at a ferry landing every minute. We can express this statistical information as

sample ← Geometric mean: 2/60

The density function can be used to answer the question, what is the
probability that it will take N trials before the next success? For exam-
ple, what is the probability that it will take 30 seconds before the next
car arrives?

sample density: 30

The cumulative distribution function can be used to answer the ques-
tion, did the next car arrive in 30 to 40 seconds?

sample distribution: (30 to: 40)

The Poisson
Distribution

Suppose the question we wish to ask is, how many events occur in a
unit time (or space interval)? The binomial distribution considers the
occurrence of two independent events, such as drawing a king of hearts
or a king of spades from a full deck of cards. There are random events,
however, that occur at random points in time or space. These events do
not occur as the outcomes of trials. In these circumstances, it does not
make sense to consider the probability of an event happening or not
happening. One does not ask how many cars did not arrive at a ferry or
how many airplanes did not land at the airport; the appropriate ques-
tions are how many cars did arrive at the ferry and how many air-
planes did land at the airport, in the next unit of time?
In simulations, the Poisson distribution is useful for sampling poten-
tial demands by customers for service, say, of cashiers, salesmen, tech-
nicians, or Xerox copiers. Experience has shown that the rate at which
the service is provided often approximates a Poisson probability law.

The Poisson law describes the probability that exactly x events occur in a unit time interval, when the mean rate of occurrence per unit time is the variable mu. For a time interval of dt, the probability is mu*dt; mu must be greater than 0.0.

The probability function is

$$
\frac{a^x e^{-a}}{x!}
$$

where a is the mean rate (or mu), e the base of natural logarithms, x is
the number of occurrences, and ! the factorial notation.

<table>
   <tr>
    <td>
     class name
    </td>
    <td>
     Poisson
    </td>
   </tr>
   <tr>
    <td>
     superclass
    </td>
    <td>
     DiscreteProbability
    </td>
   </tr>
   <tr>
    <td>
     instance variable names
    </td>
    <td>
     mu
    </td>
   </tr>
   <tr>
    <td>
     class methods
    </td>
    <td>
    </td>
   </tr>
  </table>

instance creation

mean: p

"p is the average number of events happening per unit interval."

p > 0.0

ifTrue: [↑self new setMean: p]

ifFalse: [self error: 'mean must be greater than 0.0']

instance methods

accessing

mean

↑mu

variance

↑mu

random sampling

next

"how many events occur in the next unit interval?"

| p n q |

p ← mu negated exp.

n ← 0.

q ← 1.0.

[q ← q * U next.

q >= p]

whileTrue: [n ← n + 1].

↑n
probability functions

**density: x**

"the probability that in a unit interval, x events will occur"

$$x \ge 0$$

ifTrue: [1((mu raisedTo: x) * (mu negated exp)) / x factorial]

ifFalse: [10.0]

private

**setMean: p**

mu $\leftarrow$ p

The response to the message next answers the question, how many
events occur in the next unit of time or space? The density function of x
determines the probability that, in a unit interval (of time or space), x
events will occur. The cumulative distribution function of x determines
the probability that, in a unit interval, x events or fewer will occur.

**Continuous**
**Probability**
**Distributions**

A continuous random variable can assume any value in an interval or
collection of intervals. In the continuous case, questions similar to those
asked in the discrete case are asked and the continuous probability dis-
tributions show strong correspondence to the discrete ones. An example
of a question one asks of a continuous probability distribution is, what
is the probability of obtaining a temperature at some moment of time.
Temperature is a physical property which is measured on a continuous
scale.

We define four kinds of continuous probability distributions; they are
uniform, exponential, gamma, and normal distributions. The uniform
distribution answers the question, given a set of equally likely events,
which one occurs? Given that the underlying events are Poisson distrib-
uted, the exponential distribution is used to answer the question, how
long before the first (next) event occurs? The gamma distribution is re-
lated in that it answers the question, how long before the Nth event oc-
curs? The normal or Gaussian distribution is useful for approximating
limiting forms of other distributions. It plays a significant role in statis-
tics because it is simple to use; symmetrical about the mean; completely
determined by two parameters, the mean and the variance; and reflects
the distribution of everyday events.

We have already examined the uniform distribution from the perspec-
tive of selecting discrete elements from a finite sample space. The ques-
tion we asked was, given a set of equally likely descriptions, which one
to pick? In the continuous case, the sample space is a continuum, such as time or the interval between 0 and 1. The class Uniform provided here extends the capabilities of class Random by generating a random variable within any interval as a response to the message next.

<table><tr><td>class name</td><td>Uniform</td></tr><tr><td>superclass</td><td>ContinuousProbability</td></tr><tr><td>instance variable names</td><td>startNumber<br/>stopNumber</td></tr></table>

class methods

instance creation

**from: begin to: end**

begin > end
ifTrue: [self error: 'illegal interval']
ifFalse: [↑self new setStart: begin toEnd: end]

instance methods

accessing

**mean**

$$↑(startNumber + stopNumber)/2$$

**variance**

$$↑(stopNumber - startNumber) squared / 12$$

probability functions

**density: x**

(x between: startNumber and: stopNumber)
ifTrue: [↑1.0 / (stopNumber - startNumber)]
ifFalse: [↑0]

private

**inverseDistribution: x**

"x is a random number between 0 and 1"
↑startNumber + (x * (stopNumber - startNumber))

**setStart: begin toEnd: end**

startNumber ← begin.
stopNumber ← end

### The Exponential Distribution

Given that the underlying events are Poisson distributed, the exponential distribution determines how long before the next event occurs. This is more suitable for a simulation design than is Poisson in the same sense that the geometric distribution was more suitable than the binomial, because we can jump the simulated clock setting to the next occurrence of an event, rather than stepping sequentially through each time unit.
As an example of sampling with an exponential, we might ask, when
will the next car arrive? The density function of x is the probability
that the next event will occur in the time interval x, for example, what
is the probability of the next car arriving in the next 10 minutes?

Exponential is typically used in situations in which the sample dete-
riorates with time. For example, an exponential is used to determine
the probability that a light bulb or a piece of electronic equipment will
fail prior to some time x. Exponential is useful in these cases because
the longer the piece of equipment is used, the less likely it is to keep
running.

As in the case of a Poisson, the parameter of the exponential distri-
bution, mu, is in terms of events per unit time, although the domain of
this distribution is time (not events).

The probability function for the exponential distribution is

$$
\frac{e^{-\frac{x}{a}}}{a}
$$

where a is the mean rate (mu = 1/a) between occurrences.

class name Exponential

superclass ContinuousProbability

instance variable names mu

class methods

instance creation

mean: p

"Since the exponential parameter mu is the same as Poisson mu, if we
are given the mean of the exponential, we take reciprocal to get the
probability parameter"

↑self parameter: 1.0/p

parameter: p

p > 0.0

ifTrue: [↑self new setParameter: p]

ifFalse: [self error:

'The probability parameter must be greater than 0.0']

instance methods

accessing

mean

↑1.0/mu

variance

↑1.0/(mu * mu)
probability functions

**density: x**

$x > 0.0$

ifTrue: [↑mu * (mu*x) negated exp]

ifFalse: [↑0.0]

**distribution: anInterval**

anInterval stop <= 0.0

ifTrue: [↑0.0]

ifFalse: [↑11.0 — (mu * anInterval stop) negated exp —

(anInterval start > 0.0

ifTrue: [self distribution:

(0.0 to: anInterval start)]

ifFalse: [0.0)]

private

**inverseDistribution: x**

"implementation according to Knuth, Vol. 2, p. 114"

↑x In negated / mu

**setParameter: p**

mu ← p

The Gamma
Distribution

A distribution related to the exponential is gamma, which answers the question, how long before the Nth event occurs? For example, we use a gamma distribution to sample how long before the Nth car arrives at the ferry landing. Each instance of class Gamma represents an Nth event and the probability of occurrence of that Nth event (inherited from the superclass Exponential). The variable N specified in class Gamma must be a positive integer.

The probability function is

$$ \frac{x^{k-1} e^{-x}}{a^k (k-1)!} $$

where k is greater than zero and the probability parameter mu is 1/a. The second term of the denominator, (k-1)!, is the gamma function when it is known that k is greater than 0. The implementation given below does not make this assumption.

class name

superclass

instance variable names

Gamma

Exponential

N
* class methods

* instance creation

**events: k mean: p**

k ← k truncated.

k > 0

ifTrue: [↑(self parameter: k/p) setEvents: k]

ifFalse: [self error: 'the number of events must be greater than 0']

* instance methods

* accessing

**mean**

↑super mean * N

**variance**

↑super variance * N

* probability functions

**density: x**

| t |

x > 0.0

ifTrue: [t ← mu * x.

↑(mu raisedTo: N) / (self gamma: N)

* (x raisedTo: N - 1)

* t negated exp]

ifFalse: [↑0.0]

* private

**gamma: n**

| t |

t ← n - 1.0.

↑self computeSample: t outOf: t

**setEvents: events**

N ← events

### The Normal Distribution

The normal distribution, also called the Gaussian, is useful for summarizing or approximating other distributions. Using the normal distribution, we can ask questions such as how long before a success occurs (similar to the discrete binomial distribution) or how many events occur in a certain time interval (similar to the Poisson). Indeed, the normal can be used to approximate a binomial when the number of events is very large or a Poisson when the mean is large. However, the approximation is only accurate in the regions near the mean; the errors in approximation increase towards the tail.

A normal distribution is used when there is a central dominating value (the mean), and the probability of obtaining a value decreases with a deviation from the mean. If we plot a curve with the possible values on the x-axis and the probabilities on the y-axis, the curve will
look like a bell shape. This bell shape is due to the requirements that the probabilities are symmetric about the mean, the possible values from the sample space are infinite, and yet the probabilities of all of these infinite values must sum to 1. The normal distribution is useful when determining the probability of a measurement, for example, when measuring the size of ball bearings. The measurements will result in values that cluster about a central mean value, off by a small amount.

The parameters of a normal distribution are the mean (mu) and a standard deviation (sigma). The standard deviation must be greater than 0. The probability function is

$$ \frac{e^{\frac{1}{2} \left(\frac{x-a}{b}\right)^2}}{b\sqrt{2\pi}} $$

where a is the parameter mu and b is the standard deviation sigma.

class name

Normal

superclass

ContinuousProbability

instance variable names

mu

sigma

class methods

instance creation

**mean: a deviation: b**

b > 0.0

ifTrue: [!self new setMean: a standardDeviation: b]

ifFalse: [self error: 'standard deviation must be greater than 0.0']

instance methods

accessing

**mean**

↑mu

**variance**

↑sigma squared

random sampling

**next**

"Polar method for normal deviates, Knuth vol. 2, pp. 104, 113"

| v1 v2 s rand u |

rand ← Uniform from: -1.0 to: 1.0.

[v1 ← rand next.

v2 ← rand next.

s ← v1 squared + v2 squared.

s >= 1] while True.

u ← (-2.0 * s ln / s) sqrt.

↑mu + (sigma * v1 * u)
probability functions

**density: x**

| twoPi t |

twoPi ← 2 * 3.1415926536.

t ← x - mu / sigma.

t(-0.5 * t squared) exp / (sigma * twoPi sqrt)

private

**setMean: m standardDeviation: s**

mu ← m.

sigma ← s

In subsequent chapters, we define and provide examples of using class
descriptions that support discrete, event-driven simulation. The proba-
bility distributions defined in the current chapter will be used through-
out the example simulations.
# Event-Driven Simulations

## A Framework for Simulations

*Simulation Objects*

*Simulations*

*A "Default" Example: NothingAtAll*

## Implementation of the Simulation Classes

*Class SimulationObject*

*Class DelayedEvent*

*Class Simulation*

*Tracing the Example NothingAtAll*

<figure><img src="image_265.png" /></figure>
A simulation is a representation of a system of objects in a real or fantasy world. The purpose of creating a computer simulation is to provide a framework in which to understand the simulated situation, for example, to understand the behavior of a waiting line, the workload of clerks, or the timeliness of service to customers. Certain kinds of simulations are referred to as "counter simulations." They represent situations for which there are places or counters in which clerks work. Customers arrive at a place in order to get service from a clerk. If a clerk is not available, the customer enters a waiting line. The first customer in the line is serviced by the next available clerk. Often a given simulation has several kinds of places and several customers, each with an agenda of places to visit. There are many examples of such situations: banks, car washes, barber shops, hospitals, cafeterias, airports, post offices, amusement parks, and factories. A computer simulation makes it possible to collect statistics about these situations, and to test out new ideas about their organization.

The objects that participate in a counter simulation operate more or less independently of one another. So, it is necessary to consider the problem of coordinating or synchronizing the activities of the various simulated objects. They typically coordinate their actions through the mechanism of message passing. Some objects, however, must synchronize their actions at certain critical moments; some objects can not proceed to carry out their desired actions without access to specific resources that may be unavailable at a given moment. The Smalltalk-80 system classes, Process, Semaphore, and SharedQueue, provide synchronization facilities for otherwise independent activities. To support a general description of counter simulations, mechanisms are needed for coordinating

* the use of fixed-size resources,

* the use of fluctuating resources, and

* the appearance of simultaneity in the actions of two objects.

Fixed resources can either be consumable or nonconsumable. For example, jelly beans are consumable, fixed resources of a candy store; books are non-consumable resources of a library. Fluctuating resources are typically referred to as renewable or producer/consumer synchronized. A store can model its supply of jelly beans as a fluctuating resource because the supply can be renewed. One can also imagine a resource that is both renewable and nonconsumable. Such a resource might be modeled in a simulation of car rentals: cars are renewable resources since new ones are manufactured and added to the available supply of cars to rent; the cars are also nonconsumable because a rented car is returned to the dealer for use by other customers. Actually, most nonconsumable
resources are consumable, for example, library books eventually become too tattered for continued circulation; the rental cars eventually get junked. "Nonconsumable" means, minimally, that they are not consumed during the period of interest in the simulation.

When the actions of two objects in a simulation must be synchronized to give the appearance of carrying out a task together, the two objects are said to be in a server/client relationship. For example, a doctor needs the cooperation of the patient in order to carry out an examination. The server is a *coordinated* resource; it is a simulation object whose tasks can only be carried out when one or more clients request the resource.

An important aspect of simulations is that they model situations that change over time; customers enter and leave a bank; cars enter, get washed, get dried, and leave a car wash; airplanes land, unload passengers, load passengers, and take off from airports. It is often the case that these activities are time-related; at certain times or with certain intervals of time, events occur. Therefore, actions have to be synchronized with some notion of time. Often this notion of time is itself simulated.

There are a number of ways in which to represent the actions of simulated objects with respect to real or simulated time. In one approach, the clock runs in its usual manner. At each tick of the clock, all objects are given the opportunity to take any desired action. The clock acts as a synchronization device for the simulation, providing the opportunity to give the appearance of parallelism since the clock waits until all actions appropriate at the given time are completed. Often, no actions will take place at a given tick of the clock.

Alternatively, the clock can be moved forward according to the time at which the next action will take place. In this case, the system is driven by the next discrete action or event scheduled to occur. The implementation of a simulation using this approach depends on maintaining a queue of events, ordered with respect to simulated time. Each time an event is completed, the next one is taken from the queue and the clock is moved to the designated time.

The simulations presented in this chapter are based on this *event-driven* approach. They include simulations in which a collection of independent objects exist, each with a set of tasks to do (services or resources to obtain), and each needing to coordinate its activity's times with other objects in the simulated situation.

This chapter describes a framework in which such simulations can be developed. The class *SimulationObject* describes a general kind of object that might appear in a simulation, that is, one with a set of tasks to do. The message protocol of the class provides a framework in which the tasks are carried out. An instance of class *Simulation* maintains the simulated clock and the queue of events. The specification of the arrival of
new objects into the system (objects such as customers) and the specification of resources (such as the clerks) are coordinated in this class.

The next chapter, Chapter 23, deals with ways to collect the data generated in running a simulation. Statistics gathering can be handled by providing a general mechanism in subclasses of class Simulation and/or class SimulationObject. Alternatively, each example simulation can provide its own mechanism for collecting information about its behavior.

Chapter 24 describes example simulations that make use of two kinds of synchronizations, shared use of fixed resources and shared use of fluctuating resources; Chapter 25 introduces additional support for coordination between two simulation objects—those wanting service and those providing service.

## A Framework for Simulations

This section contains a description of the classes that provide the basic protocol for classes SimulationObject and Simulation. These classes are presented twice. First, a description of the protocol is given with an explanation of how to create a default example; second, an implementation of these classes is given.

Consider simulating a car wash. Major components of a car wash are washing places, drying places, paying places, washers, dryers, cashiers, and vehicles of different sorts such as trucks and cars. We can classify these components according to behavior. Major classifications are: places, where workers are located and work is performed; workers, such as washers, dryers, and cashiers; and the vehicles that are the customers of the places. These classifications might be translated into three classes of Smalltalk objects: Place, Worker, and Customer. But each of these classes of objects is similar in that each describes objects that have tasks to do—a Customer requests service, a Worker gives service, and a Place provides resources. In particular, a Place provides a waiting queue for the times when there are more customers than its workers can handle. These similarities are modeled in the superclass SimulationObject, which describes objects that appear in a simulated situation; a SimulationObject is any object that can be given a sequence of tasks to do. Each object defines a main sequence of activity that is initiated when the object enters the simulation. For example, the activities of a car in a car wash are to request a washer, wait while being washed, request a dryer, wait while being dried, pay for the service, and leave.

Class SimulationObject specifies a general control sequence by which the object enters, carries out its tasks, and leaves the simulation. This

### *Simulation Objects*
sequence consists of sending the object the messages `startUp`, `tasks`, and `finishUp`. Initialization of descriptive variables is specified as the response to message `initialize`. These messages are invoked by the method associated with `startUp`. Response to the messages `tasks` and `initialize` are implemented by subclasses of `SimulationObject`.

SimulationObject instance protocol

<table><tr><td>initialization</td><td></td></tr><tr><td>initialize</td><td>Initialize instance variables, if any.</td></tr><tr><td>simulation control</td><td></td></tr><tr><td>startUp</td><td>Initialize instance variables. Inform the simulation that the receiver is entering it, and then initiate the receiver's tasks.</td></tr><tr><td>tasks</td><td>Define the sequence of activities that the receiver must carry out.</td></tr><tr><td>finishUp</td><td>The receiver's tasks are completed. Inform the simulation.</td></tr></table>

There are several messages that any `SimulationObject` can use in order to describe its tasks. One is `holdFor: aTimeDelay`, where the argument `aTimeDelay` is some amount of simulated time for which the object delays further action. The idea of this delay is to create a period of time in which the object is presumably carrying out some activity.

We call the category of these messages, the modeler's task language to indicate that these are the messages sent to a `SimulationObject` as part of the implementation of the message tasks.

A simulation can contain simple or *static* resources, like "jelly beans," that can be acquired by a simulation object. Or a simulation can consist of *coordinated* resources, that is, simulation objects whose tasks must be synchronized with the tasks of other simulation objects. The task language includes messages for accessing each kind of resource, either to get or to give the resource.

There are 3 kinds of messages for static resources. There are 2 messages for getting an amount of the resource named `resourceName`. They are

* `acquire: amount ofResource: resourceName`

* `acquire: amount ofResource: resourceName withPriority: priorityInteger`

There is one for giving an amount of the resource named `resourceName`,

* `produce: amount ofResource: resourceName`

and one for giving up an acquired static resource,

* `release: aStaticResource`
There are also 3 kinds of messages for coordinated resources. The message for getting the resource named resourceName (here, the resource is a SimulationObject that models a kind of customer, and the asker is a server such as a clerk) is

`acquireResource: resourceName`

To produce the resource named resourceName (the asker is a customer), the message is

`produceResource: resourceName`

and to give up an acquired resource (which is a SimulationObject whose task events can now be resumed), the message is

`resume: anEvent`

When a SimulationObject makes a static resource request (`acquire`:ofResource: or `request`:)`, it can do so by stating the level of importance of the request. The number 0 represents the least important request, successively higher numbers represent successively higher levels of importance. The message `acquire`:ofResource: assumes a priority level of 0; `acquire`:ofResource:withPriority: specifies particular levels in its third argument.

Two queries check whether a static resource is in the simulation and how much of the resource is available. These are `resourceAvailable`: resourceName, which answers whether or not the simulation has a resource referred to by the String, `resourceName`; and `inquireFor`: amount of Resource: resourceName, which answers whether there is at least amount of the resource remaining.

When a SimulationObject is synchronizing its tasks with that of another SimulationObject, it might be useful to know whether such an object is available. Two additional inquiry messages support finding out whether a provider or requester of a coordinated task is available—` numberOfProviders`:ofResource: resourceName and ` numberOfRequesters`:ofResource: resourceName.

In addition, a message to a SimulationObject can request that the Simulation it is in stop running. This is the message `stopSimulation`.

SimulationObject instance protocol

task language

`holdFor: aTimeDelay`

Delay carrying out the receiver's next task until aTimeDelay amount of simulated time has passed.
**acquire: amount of Resource: resourceName**

Ask the simulation to provide a simple resource that is referred to by the String, resourceName. If one exists, ask it to give the receiver amount of resources. If one does not exist, notify the simulation user (programmer) that an error has occurred.

**acquire: amount of Resource: resourceName with Priority: priorityNumber**

Ask the simulation to provide a simple resource that is referred to by the String, resourceName. If one exists, ask it to give the receiver amount of resources, taking into account that the priority for acquiring the resource is to be set as priorityNumber. If one does not exist, notify the simulation user (programmer) that an error has occurred.

**produce: amount of Resource: resourceName**

Ask the simulation to provide a simple resource that is referred to by the String, resourceName. If one exists, add to it amount more of its resources. If one does not exist, create it.

**release: aStaticResource**

The receiver has been using the resource referred to by the argument, aStaticResource. It is no longer needed and can be recycled.

**inquireFor: amount of Resource: resourceName**

Answer whether or not the simulation has at least a quantity, amount, of a resource referred to by the String, resourceName.

**resourceAvailable: resourceName**

Answer whether or not the simulation has a resource referred to by the String, resourceName.

**acquireResource: resourceName**

Ask the simulation to provide a resource simulation object that is referred to by the String, resourceName. If one exists, ask it to give the receiver its services. If one does not exist, notify the simulation user (programmer) that an error has occurred.

**produceResource: resourceName**

Have the receiver act as a resource that is referred to by the String, resourceName. Wait for another SimulationObject that provides service to (acquires) this resource.

**resume: anEvent**

The receiver has been giving service to the resource referred to by the argument, anEvent. The service is completed so that the resource, a SimulationObject, can continue its tasks.

** numberOfProvidersOf Resource: resourceName**

Answer the number of SimulationObjects waiting to coordinate its tasks by acting as the resource referred to by the String, resourceName.

** numberOfRequestersOf Resource: resourceName**

Answer the number of SimulationObjects waiting to coordinate its tasks by acquiring the resource referred to by the String, resourceName.
### stopSimulation

Tell the simulation in which the receiver is running to stop. All scheduled events are removed and nothing more can happen in the simulation.

The examples we present in subsequent chapters illustrate each message in the modeler's task language.

## *Simulations*

The purpose of class Simulation is to manage the topology of simulation objects and to schedule actions to occur according to simulated time. Instances of class Simulation maintain a reference to a collection of SimulationObjects, to the current simulated time, and to a queue of events waiting to be invoked.

The unit of time appropriate to the simulation is saved in an instance variable and represented as a floating-point number. The unit might be milliseconds, minutes, days, etc. A simulation advances time by checking the queue to determine when the next event is scheduled to take place, and by setting its instance variable to the time associated with that next event. If the queue of events is empty, then the simulation terminates.

Simulation objects enter a simulation in response to one of several scheduling messages such as

* scheduleArrivalOf: aSimulationObjectClass

* accordingTo: aProbabilityDistribution or

* scheduleArrivalOf: aSimulationObject at: aTimeInteger.

These messages are sent to the simulation either at the time that the simulation is first initialized, in response to the message defineArrivalSchedule, or as part of the sequence of tasks that a SimulationObject carries out. The second argument of the first message, aProbabilityDistribution, is an instance of a probability distribution such as those defined in Chapter 21. In this chapter, we assume the availability of the definitions given in Chapter 21. The probability distribution defines the interval at which an instance of the first argument, aSimulationObjectClass, is to be created and sent the message startUp.

In addition, Simulation supports messages having to do with scheduling a particular sequence of actions. These are schedule: actionBlock at: timeInteger and schedule: actionBlock after: amountOfTime.

In order to define the resources in the simulation, the modeler can send the simulation one or more of two possible messages. Either

* self produce: amount of: resourceName

where the second argument, resourceName, is a String that names a simple quantifiable resource available in the simulation; the first argument is the (additional) quantity of this resource to be made available.
Or

self coordinate: resourceName

The argument, resourceName, is a String that names a resource that is to be provided by some objects in the simulation and requested by other objects. For example, the resource is car washing, the provider is a washer object and the requestor is a car object.

Simulation instance protocol

<table><tr><td>initialization</td><td></td></tr><tr><td>initialize</td><td>Initialize the receiver's instance variables.</td></tr><tr><td>modeler's initialization language</td><td></td></tr><tr><td>defineArrivalSchedule</td><td>Schedule simulation objects to enter the simulation at specified time intervals, typically based on probability distribution functions. This method is implemented by subclasses. It involves a sequence of messages to the receiver (i.e., to self) that are of the form schedule:at:, scheduleArrivalOf:at:, scheduleArrivalOf:accordingTo:, or scheduleArrivalOf:accordingTo:startingAt:.<br/>See the next category of messages for descriptions of these.</td></tr><tr><td>defineResources</td><td>Specify the resources that are initially entered into the simulation. These typically act as resources to be acquired. This method is implemented by subclasses and involves a sequence of messages to the receiver (i.e., to self) of the form produce: amount of: resourceName.</td></tr><tr><td>modeler's task language</td><td></td></tr><tr><td>produce: amount of: resourceName</td><td>An additional quantity of amount of a resource referred to by the String, resourceName, is to be part of the receiver. If the resource does not as yet exist in the receiver, add it; if it already exists, increase its available quantity.</td></tr><tr><td>coordinate: resourceName</td><td>Use of a resource referred to by the String, resourceName, is to be coordinated by the receiver.</td></tr><tr><td>schedule: actionBlock after: timeDelayInteger</td><td>Set up a program, actionBlock, that will be evaluated after a simulated amount of time, timeDelayInteger, passes.</td></tr><tr><td>schedule: actionBlock at: timeInteger</td><td>Schedule the sequence of actions (actionBlock) to occur at a particular simulated time, timeInteger.</td></tr><tr><td>scheduleArrivalOf: aSimulationObject at: timeInteger</td><td>Schedule the simulation object, aSimulationObject, to enter the simulation at a specified time, timeInteger.</td></tr></table>
scheduleArrivalOf: aSimulationObjectClass
accordingTo: aProbabilityDistribution

Schedule simulation objects that are instances of aSimulationObjectClass to enter the simulation at specified time intervals, based on the probability distribution aProbabilityDistribution. The first such instance should be scheduled to enter now. See Chapter 21 for definitions of possible probability distributions.

scheduleArrivalOf: aSimulationObjectClass
accordingTo: aProbabilityDistribution
startingAt: timeInteger

Schedule simulation objects that are instances of aSimulationObjectClass to enter the simulation at specified time intervals, based on the probability distribution aProbabilityDistribution. The first such instance should be scheduled to enter at time timeInteger.

Notice that in the above scheduling messages, scheduleArrivalOf:at: takes a SimulationObject instance as its first argument, while scheduleArrivalOf:accordingTo: takes a SimulationObject class. These messages are used differently; the first one can be used by the SimulationObject itself to reschedule itself, while the second is used to initiate the arrival of SimulationObjects into the system.

The protocol for Simulation includes several accessing messages. One, the message includesResourceFor: resourceName, can be sent by a SimulationObject in order to determine whether or not a resource having a given name exists in the simulation.

Simulation instance protocol

accessing

includesResourceFor: resourceName

Answer if the receiver has a resource that is referred to by the String, resourceName. If such a resource does not exist, then report an error.

provideResourceFor: resourceName

Answer a resource that is referred to by the String, resourceName.

time

Answer the receiver's current time.

The simulation control framework is like that of class SimulationObject. Initialization is handled by creating the Simulation and sending it the message startUp. Simulation objects and the scheduling of new objects create events that are placed in the event queue. Once initialized, the Simulation is made to run by sending it the message proceed until there are no longer any events in the queue.

In the course of running the simulation, objects will enter and exit. As part of the protocol for scheduling a simulation object, the object informs its simulation that it is entering or exiting. The corresponding
messages are enter: anObject and exit: anObject. In response to these messages, statistics might be collected about simulation objects upon their entrance and their exit to the simulation. Or a subclass might choose to deny an object entrance to the simulation; or a subclass might choose to reschedule an object rather than let it leave the simulation.

Simulation instance protocol

simulation control

startUp Specify the initial simulation objects and the arrival schedule of new objects.

proceed This is a single event execution. The first event in the queue, if any, is removed, time is updated to the time of the event, and the event is initiated.

finishUp Release references to any remaining simulation objects.

enter: anObject The argument, anObject, is informing the receiver that it is entering.

exit: anObject The argument, anObject, is informing the receiver that it is exiting.

Of the above messages, the default responses in class Simulation are mostly to do nothing. In particular, the response to messages enter: and exit: are to do nothing. Messages defineArrivalSchedule and defineResources also do nothing. As a result, the message startUp accomplishes nothing. These messages provide the framework that subclasses are to use—a subclass is created that overrides these messages in order to add simulation-specific behavior.

Unlike many of the system class examples of earlier chapters, the superclasses Simulation and SimulationObject typically do not implement their basic messages as

self subclassResponsibility

By not doing so, instances of either of these classes can be successfully created. These instances can then be used as part of a basic or a "default" simulation that serves as a skeletal example. As we have seen, such simulation objects are scheduled to do nothing and consist of no events. Development of more substantive simulations can proceed by gradual refinement of these defaults. With a running, default example, the designer/programmer can incrementally modify and test the simulation, replacing the uninteresting instances of the superclasses with instances of appropriate subclasses. The example simulation NothingAtAll illustrates the idea of a "default" simulation.

Suppose we literally do nothing other than to declare the class NothingAtAll as a subclass of Simulation. A NothingAtAll has no initial re-

A "Default"
Example:
NothingAtAll
sources since it does nothing in response to the message `defineResources`. And it has no simulation objects arriving at various intervals, because it does nothing in response to the message `defineArrivalSchedule`. Now we execute the following statement.

NothingAtAll new startUp proceed

The result is that an instance of `NothingAtAll` is created and sent the message `startUp`. It is a simulation with no resources and no objects scheduled, so the queue of events is empty. In response to the message proceed, the simulation determines that the queue is empty and does nothing.

As a modification of the description of `NothingAtAll`, we specify a response to the message `defineArrivalSchedule`. In it, the objects scheduled for arrival are instances of class `DoNothing`. `DoNothing` is created simply as a subclass of `SimulationObject`. A `DoNothing` has no tasks to carry out, so as soon as it enters the simulation, it leaves.

class name DoNothing
superclass SimulationObject
definition methods

no new methods

class name NothingAtAll
superclass Simulation
definition methods

initialization

defineArrivalSchedule

self scheduleArrivalOf: DoNothing

accordingTo: (Uniform from: 1 to: 5)

This version of `NothingAtAll` might represent a series of visitors entering an empty room, looking around without taking time to do so, and leaving. The probability distribution, `Uniform`, in the example in this chapter is assumed to be the one specified in Chapter 21. According to the above specification, new instances of class `DoNothing` should arrive in the simulation every 1 to 5 units of simulated time starting at time 0. The following expressions, when evaluated, create the simulation, send it the message `startUp`, and then iteratively send it the message `proceed`.

aSimulation ← NothingAtAll new startUp.

[aSimulation proceed] while True

The message `startUp` invokes the message `defineArrivalSchedule` which schedules instances of `DoNothing`. Each time the message `proceed` is
sent to the simulation, a `DoNothing` enters or exits. Evaluation might result in the following sequence of events. The time of each event is shown on the left and a description of the event is shown on the right.

<table><tr><td>0.0</td><td>a DoNothing enters</td></tr><tr><td>0.0</td><td>a DoNothing exits</td></tr><tr><td>3.21</td><td>a DoNothing enters</td></tr><tr><td>3.21</td><td>a DoNothing exits</td></tr><tr><td>7.76</td><td>a DoNothing enters</td></tr><tr><td>7.76</td><td>a DoNothing exits</td></tr></table>

and so on.

We can now make the simulation more interesting by scheduling the arrival of more kinds of simulation objects, ones that have tasks to do. We define `Visitor` to be a `SimulationObject` whose task is to enter the empty room and look around, taking between 4 and 10 simulated units to do so, that is, a random amount determined by evaluating the expression (Uniform from: 4 to: 10) next.

<table><tr><td>class name</td><td>Visitor</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>simulation control</td><td></td></tr></table>

### tasks

self holdFor: (Uniform from: 4.0 to: 10.0) next

`NothingAtAll` is now defined as

<table><tr><td>class name</td><td>NothingAtAll</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>initialization</td><td></td></tr></table>

### defineArrivalSchedule

self scheduleArrivalOf: DoNothing
accordingTo: (Uniform from: 1 to: 5).
self scheduleArrivalOf: Visitor
accordingTo: (Uniform from: 4 to: 8)
startingAt: 3

Two kinds of objects enter the simulation, one that takes no time to look around (a `DoNothing`) and one that visits a short while (a `Visitor`). Execution of

a Simulation → NothingAtAll new startUp.
[aSimulation proceed] while True
might result in the following sequence of events.

<table><tr><td>0.0</td><td>a DoNothing enters</td></tr><tr><td>0.0</td><td>a DoNothing exits</td></tr><tr><td>3.0</td><td>a Visitor enters</td></tr><tr><td>3.21</td><td>a DoNothing enters</td></tr><tr><td>3.21</td><td>a DoNothing exits</td></tr><tr><td>7.76</td><td>a DoNothing enters</td></tr><tr><td>7.76</td><td>a DoNothing exits</td></tr><tr><td>8.23</td><td>a (the first) Visitor exits after 5.23 seconds</td></tr></table>

and so on.

## Implementation of the Simulation Classes

In order to trace the way in which the sequence of events occurs in the examples provided so far, it is necessary to show an implementation of the two classes. The implementations illustrate the control of multiple independent processes in the Smalltalk-80 system that were described in Chapter 15.

### Class SimulationObject

Every SimulationObject created in the system needs access to the Simulation in which it is functioning. Such access is necessary, for example, in order to send messages that inform the simulation that an object is entering or exiting. In order to support such access, SimulationObject has a class variable, ActiveSimulation, that is initialized by each instance of Simulation when that instance is activated (that is, sent the message startUp). This approach assumes only one Simulation will be active at one time. It means that the tasks for any subclass of SimulationObject can send messages directly to its simulation, for example, to determine the current time. SimulationObject specifies no instance variables.

<table><tr><td>class name</td><td>SimulationObject</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>class variable names</td><td>ActiveSimulation</td></tr><tr><td>class methods</td><td></td></tr><tr><td>class initialization</td><td></td></tr></table>

**activeSimulation: existingSimulation**

ActiveSimulation ← existingSimulation

instance creation

**new**

1super new initialize
The simulation control framework, sometimes referred to as the "life cycle" of the object, involves the sequence `startUp`—`tasks`—`finishUp`. When the `SimulationObject` first arrives at the simulation, it is sent the message `startUp`.

* instance methods

* simulation control

**initialize**

"Do nothing. Subclasses will initialize instance variables."

↑self

**startUp**

ActiveSimulation enter: self.

"First tell the simulation that the receiver is beginning to do my tasks."

self tasks.

self finishUp

**tasks**

"Do nothing. Subclasses will schedule activities."

↑self

**finishUp**

"Tell the simulation that the receiver is done with its tasks."

ActiveSimulation exit: self

The category `task` language consists of messages the modeler can use in specifying the `SimulationObject`'s sequence of actions. The object might hold for an increment of simulated time (`holdFor:`). The object might try to acquire access to another simulation object that is playing the role of a resource (`acquire`:ofResource:). Or the object might determine whether a resource is available (`resourceAvailable:`).

* task language

**holdFor:** `aTimeDelay`

ActiveSimulation delayFor: aTimeDelay

**acquire:** `amount ofResource: resourceName`

"Get the resource and then tell it to acquire amount of it. Answers an instance of `StaticResource`"

↑(ActiveSimulation provideResourceFor: resourceName)

acquire: amount

withPriority: 0

**acquire:** `amount ofResource: resourceName`

**withPriority:** `priority`

↑(ActiveSimulation provideResourceFor: resourceName)

acquire: amount

withPriority: priority

**produce:** `amount ofResource: resourceName`

ActiveSimulation produce: amount of: resourceName
**release: aStaticResource**

↑aStaticResource release

**inquireFor: amount of Resource: resourceName**

↑(ActiveSimulation provideResourceFor: resourceName)

amountAvailable > = amount

**resourceAvailable: resourceName**

"Does the active simulation have a resource with this attribute available?"

↑ActiveSimulation includesResourceFor: resourceName

**acquireResource: resourceName**

↑(ActiveSimulation provideResourceFor: resourceName)

acquire

**produceResource: resourceName**

↑(ActiveSimulation provideResourceFor: resourceName)

producedBy: self

**resume: anEvent**

↑anEvent resume

**numberOfProvidersOfResource: resourceName**

| resource |

resource ← ActiveSimulation provideResourceFor: resourceName.

resource serversWaiting

ifTrue: [↑resource queueLength]

ifFalse: [↑0]

**numberOfRequestersOfResource: resourceName**

| resource |

resource ← ActiveSimulation provideResourceFor: resourceName.

resource customersWaiting

ifTrue: [↑resource queueLength]

ifFalse: [↑0]

**stopSimulation**

ActiveSimulation finishUp

A Simulation stores a Set of resources. In the case of static resources, instances of class ResourceProvider are stored; in the case of resources that consist of tasks coordinated among two or more simulation objects, instances of ResourceCoordinator are stored.

When a SimulationObject requests a static resource (acquire:ofResource:) and that request succeeds, then the SimulationObject is given an instance of class StaticResource. A StaticResource refers to the resource that created it and the quantity of the resource it represents. Given the methods shown for class SimulationObject, we can see that a resource responds to the message amountAvailable to return the currently available quantity of the resource that the SimulationObject might acquire. This message is sent in the method associated with inquireFor:ofResource:.

In the methods associated with SimulationObject messages acquire:of-Resource: and acquire:ofResource:withPriority:, a ResourceProvider is
obtained and sent the message acquire: amount withPriority: priorityNumber. The result of this message is an instance of class StaticResource. However, if the amount is not available, the process in which the request was made will be suspended until the necessary resources become available. A StaticResource is sent the message release in order to recycle the acquired resource.

When a SimulationObject requests a coordinated resource (acquireResource:), and that request succeeds, then the object co-opts another simulation object acting as the resource (the object in need of service) until some tasks (services) are completed. If such a resource is not available, the process in which the request was made will be suspended until the necessary resources become available. Instances of class ResourceCoordinator understand messages acquire in order to make the request to coordinate service tasks and producedBy: a SimulationObject in order to specify that the argument is to be co-opted by another object in order to synchronize activities. As indicated by the implementation of SimulationObject, a ResourceCoordinator can answer queries such as customersWaiting or serversWaiting to determine if resources (customers) or service givers (servers) are waiting to coordinate their activities, and queueLength to say how many are waiting.

Explanations of the implementations of classes ResourceProvider and ResourceCoordinator are provided in Chapters 24 and 25.

The implementation of a scheduling mechanism for class Simulation makes extensive use of the Smalltalk-80 processor scheduler classes presented in the chapter on multiple processes (Chapter 15). There are several problems that have to be solved in the design of class Simulation. First, how do we store an event that must be delayed for some increment of simulated time? Second, how do we make certain that all processes initiated at a particular time are completed before changing the clock? And third, in terms of the solutions to the first two problems, how do we implement the request to repeatedly schedule a sequence of actions, in particular, instantiation and initiation of a particular kind of SimulationObject?

In order to solve the first problem, the Simulation maintains a queue of all the scheduled events. This queue is a SortedCollection whose elements are the events, sorted with respect to the simulated time in which they must be invoked. Each event on the queue is placed there within a package that is an instance of class DelayedEvent. At the time the package is created, the event is the system's active process. As such, it can be stored with its needed running context by creating a Semaphore. When the event is put on the queue, the DelayedEvent is sent the message pause which sends its Semaphore the message wait; when the event is taken off the queue, it is continued by sending it the message resume. The method associated with resume sends the DelayedEvent's Semaphore the message signal.
The protocol for instances of class DelayedEvent consists of five messages.

DelayedEvent instance protocol

<table><tr><td>accessing</td><td></td></tr><tr><td>condition</td><td>Answer a condition under which the event should be sequenced.</td></tr><tr><td>condition: anObject</td><td>Set the argument, anObject, to be the condition under which the event should be sequenced.</td></tr><tr><td>scheduling</td><td></td></tr><tr><td>pause</td><td>Suspend the current active process, that is, the current event that is running.</td></tr><tr><td>resume</td><td>Resume the suspended process.</td></tr><tr><td>comparing</td><td></td></tr><tr><td>&lt;= aDelayedEvent</td><td>Answer whether the receiver should be sequenced before the argument, aDelayedEvent.</td></tr></table>

A DelayedEvent is created by sending the class the message new or onCondition: anObject. The implementation of class DelayedEvent is given next.

<table><tr><td>class name</td><td>DelayedEvent</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>instance variable names</td><td>resumptionSemaphore resumptionCondition</td></tr><tr><td>class methods</td><td></td></tr><tr><td>instance creation</td><td></td></tr><tr><td><strong>new</strong></td><td></td></tr><tr><td>↑super new initialize</td><td></td></tr><tr><td><strong>onCondition: anObject</strong></td><td></td></tr><tr><td>↑super new setCondition: anObject</td><td></td></tr><tr><td>instance methods</td><td></td></tr><tr><td>accessing</td><td></td></tr><tr><td><strong>condition</strong></td><td></td></tr><tr><td>↑resumptionCondition</td><td></td></tr><tr><td><strong>condition: anObject</strong></td><td></td></tr><tr><td>resumptionCondition ← anObject</td><td></td></tr><tr><td>comparing</td><td></td></tr><tr><td>&lt;= aDelayedEvent</td><td></td></tr><tr><td>resumptionCondition isNil</td><td></td></tr><tr><td>ifTrue: [↑true]</td><td></td></tr><tr><td>ifFalse: [↑resumptionCondition &lt;= aDelayedEvent condition]</td><td></td></tr></table>
### scheduling

**pause**

resumptionSemaphore wait

**resume**

resumptionSemaphore signal.

tresumptionCondition

### private

**initialize**

resumptionSemaphore ← Semaphore new

**setCondition: anObject**

self initialize.

resumptionCondition ← anObject

According to the above specification, any object used as a resumption condition must respond to the message `< =`; `SimulationObject` is, in general, such a condition.

### Class Simulation

Instances of class `Simulation` own four instance variables: a Set of objects that act as resources of the simulation (resources), a Number representing the current time (`currentTime`), a `SortedCollection` representing a queue of delayed events (`eventQueue`), and an `Integer` denoting the number of processes active at the current time (`processCount`).

Initialization of a `Simulation` sets the instance variables to their values. When the instance is sent the scheduling message `startUp`, it sends itself the message `activate` which informs interested other classes which `Simulation` is now the active one.

class name Simulation

superclass Object

instance variable names resources currentTime

eventQueue processCount

class methods

instance creation

**new**

tsuper new initialize

instance methods

initialization

**initialize**

resources ← Set new.

currentTime ← 0.0.

processCount ← 0.

eventQueue ← SortedCollection new
**activate**

"This instance is now the active simulation. Inform class SimulationObject."

SimulationObject activeSimulation: self.

"Resource is the superclass for ResourceProvider and ResourceCoordinator"

Resource activeSimulation: self

Initialization messages are also needed by the subclasses. The messages provided for the modeler to use in specifying arrival schedules and resource objects provides an interface to the process scheduling messages.

initialization

**defineArrivalSchedule**

"A subclass specifies the schedule by which simulation objects dynamically enter into the simulation."

↑self

**defineResources**

"A subclass specifies the simulation objects that are initially entered into the simulation."

↑self

task language

**produce: amount of: resourceName**

(self includesResourceFor: resourceName)
ifTrue: [(self provideResourceFor: resourceName) produce: amount]
ifFalse: [resources add:
          (ResourceProvider named: resourceName with: amount)]

**coordinate: resourceName**

(self includesResourceFor: resourceName)
ifFalse: [resources add:
          (ResourceCoordinator named: resourceName)]

**schedule: actionBlock after: timeDelay**

self schedule: actionBlock at: currentTime + timeDelay

**schedule: aBlock at: timeInteger**

"This is the mechanism for scheduling a single action"

self newProcessFor:
    [self delayUntil: timeInteger.
     aBlock value]

**scheduleArrivalOf: aSimulationObject at: timeInteger**

self schedule: [aSimulationObject startUp] at: timeInteger

**scheduleArrivalOf: aSimulationObjectClass accordingTo: aProbabilityDistribution**

"This means start now"
self scheduleArrivalOf: aSimulationObjectClass
accordingTo: aProbabilityDistribution
startingAt: currentTime
scheduleArrivalOf: aSimulationObjectClass
accordingTo: aProbabilityDistribution
startingAt: timeInteger

"Note that aClass is the class SimulationObject or one of its subclasses. The real work is done in the private message schedule:startingAt:andThenEvery:"

self schedule: [aSimulationObjectClass new startUp]
    startingAt: timeInteger
    andThenEvery: aProbabilityDistribution

The scheduling messages of the task language implement a reference-counting solution to keeping track of initiated processes. This is the technique used to solve the second problem cited earlier, that is, how to make certain that all processes initiated for a particular time are carried out by the single Smalltalk-80 processor scheduler before a different process gets the opportunity to change the clock. Using reference counting, we guarantee that simulated time does not change unless the reference count is zero.

The key methods are the ones associated with schedule: aBlock at: timeInteger and schedule: aBlock startingAt: timeInteger andThenEvery: aProbabilityDistribution. This second message is a private one called by the method associated with scheduleArrivalOf: aSimulationObjectClass accordingTo: aProbabilityDistribution startingAt: timeInteger. It provides a general mechanism for scheduling repeated actions and therefore represents a solution to the third design problem mentioned earlier, how we implement the request to repeatedly schedule a sequence of actions.

The basic idea for the schedule: aBlock at: timeInteger is to create a process in which to delay the evaluation of the sequence of actions (aBlock) until the simulation reaches the appropriate simulated time (timeInteger). The delay is performed by the message delayUntil: delayedTime. The associated method creates a DelayedEvent to be added to the simulation's event queue. The process associated with this DelayedEvent is then suspended (by sending it the message pause). When this instance of DelayedEvent is the first in the queue, it will be removed and the time will be bumped to the stored (delayed) time. Then this instance of DelayedEvent will be sent the message resume which will cause the evaluation of the block; the action of this block is to schedule some simulation activity.

A process that was active is suspended when the DelayedEvent is signaled to wait. Therefore, the count of the number of processes must be decremented (stopProcess). When the DelayedEvent resumes, the process continues evaluation with the last expression in the method delayedUntil; therefore at this time, the count of the number of processes must be incremented (startProcess).
## scheduling

**delayUntil: aTime**

```pascal
| delayEvent |
delayEvent    DelayEvent onCondition: timeInteger.
eventQueue add: delayEvent.
self stopProcess.
delayEvent pause.
self startProcess
```

**delayFor: timeDelay**

```pascal
self delayUntil: currentTime + timeDelay
```

**startProcess**

```pascal
processCount ← processCount + 1
```

**stopProcess**

```pascal
processCount ← processCount - 1
```

Reference counting of processes is also handled in the method associated with class Simulation's scheduling message newProcessFor: aBlock. It is implemented as follows.

**newProcessFor: aBlock**

```pascal
self startProcess.
[aBlock value.
self stopProcess] fork
```

The first expression increments the count of processes. The second expression is a block that is forked. When the Smalltalk processor scheduler evaluates this block, the simulation sequence of actions, aBlock, is evaluated. The completion of evaluating aBlock signals the need to decrement the count of processes. In this way, a single sequence of actions is scheduled in the event queue of the Simulation and delayed until the correct simulated time. In summary, the reference count of processes increments whenever a new sequence of actions is initiated, decrements whenever a sequence completes, decrements whenever a DelayedEvent is created, and increments whenever the DelayedEvent is continued.

The method for the private message schedule: aBlock startingAt: timeInteger andThenEvery: aProbabilityDistribution forks a process that repeatedly schedules actions. The algorithm consists of iterations of two messages,

```pascal
self delayUntil: timeInteger.
self newProcessFor: aBlock
```

Repetition of the two messages delayUntil: and newProcessFor: depends on a probability distribution function. The number of repetitions equals the number of times the distribution can be sampled. The number that is sampled represents the next time that the sequence of actions (aBlock)
should be invoked. Elements of the distribution are enumerated by
sending the distribution the message `do`:

private

**schedule: aBlock**

**startingAt: timeInteger**

**andThenEvery: aProbabilityDistribution**

`self newProcessFor:`

```[

`self delayUntil: timeInteger.`

```"Do the action."```

`self newProcessFor: aBlock copy.`

`aProbabilityDistribution`

`do: [ :nextTimeDelay |`

```"For each sample from the distribution,
delay the amount sampled,"```

`self delayFor: nextTimeDelay.`

```"then do the action"```

`self newProcessFor: aBlock copy]]`

Simulation itself has a control framework similar to that of `SimulationObject`. The response to `startUp` is to make the simulation the currently active one and then to define the simulation objects and arrival schedule. The inner loop of scheduled activity is given as the response to the message `proceed`. Whenever the Simulation receives the message `proceed`, it checks the reference count of processes (by sending the message `readyToContinue`). If the reference count is not zero, then there are still processes active for the current simulated time. So, the system-wide processor, `Processor`, is asked to yield control and let these processes proceed. If the reference count is zero, then the event queue is checked. If it is not empty, the next event is removed from the event queue, time is changed, and the delayed process is resumed.

simulation control

**startUp**

`self activate.`

`self defineResources.`

`self defineArrivalSchedule`

**proceed**

`| eventProcess |`

`[self readyToContinue] whileFalse: [Processor yield].`

`eventQueue empty?`

`ifTrue: [!self finishUp]`

`ifFalse: [eventProcess -- eventQueue removeFirst.`

`currentTime -- eventProcess time.`

`eventProcess resume]`
**finishUp**

"We need to empty out the event queue"

eventQueue → SortedCollection new.

tfalse

**enter: anObject**

tself

**exit: anObject**

tself

private

**readyToContinue**

↑processCount = 0

In addition to these various modeler's languages and simulation control messages, several accessing messages are provided in the protocol of Simulation.

accessing

**includesResourceFor: resourceName**

| test |

test ← resources

detect: [ :each | each name = resourceName]

ifNone: [nil].

↑test notNil

**provideResourceFor: resourceName**

tresources detect: [ :each | each name = resourceName]

**time**

↑currentTime

The implementations of Simulation and SimulationObject illustrate the use of messages fork to a BlockContext, yield to a ProcessorScheduler, and signal and wait to a Semaphore.

*Tracing the Example*
NothingAtAll

We can now trace the execution of the first example of the simulation, NothingAtAll, in which DoNothings only were scheduled. After sending the message

NothingAtAll new

the instance variables of the new simulation consist of

resources = Set ()

currentTime = 0.0

processCount = 0

eventQueue = SortedCollection ()
We then send this simulation the message `startUp`, which invokes the message `scheduleArrivalOf`: `DoNothing` accordingTo: `(Uniform from: 1 to: 5)`. This is identical to sending the simulation the message

```
schedule: [DoNothing new startUp]
startingAt: 0.0
andThenEvery: (Uniform from: 1 to: 5)
```

The response is to call on `newProcessFor`:

Step 1. `newProcessFor:` increments the `processCount` (self `startProcess`) and then creates a new `Process` that evaluates the following block, which will be referred to as block A.

```pascal
[self delayUntil: timeInteger.
self newProcessFor: block copy.
aProbabilityDistribution do:
  [ :nextTimeDelay |
    self delayFor: nextTimeDelay.
    self newProcessFor: block copy]
```

where the variable block is

`[DoNothing new startUp]`

which will be referred to as block B.

Step 2. When the process returns to the second expression of the method `newProcessFor:`, execution continues by evaluating block A. Its first expression decrements the process count and suspends an activity until time is 0.0 (i.e., create a `DelayedEvent` for the active simulation scheduler to tell the `DoNothing` to `startUp` at time 0.0; put it on the event queue).

```
resources = Set()
currentTime = 0.0
processCount = 0
eventQueue = SortedCollection (a DelayedEvent 0.0)
```

Now we send the simulation the message `proceed`. The process count is 0 so `readyToContinue` returns true; the event queue is not empty so the first `DelayedEvent` is removed, time is set to 0.0, and the delayed process is resumed (this was the scheduler block A). The next action increments the process count and evaluates block B. This lets a `DoNothing` enter and do its task, which is nothing, so it leaves immediately. The `newProcessFor:` message decrements the process count to 0, gets a number from the probability distribution, delays for this number of
time units, and schedules a new process for some time later. The sequence continues indefinitely, as long as the message *proceed* is re-sent to the simulation.

Other tasks will enter the event queue depending on the method associated with the message tasks in a subclass of `SimulationObject`. Thus if `Visitor` is scheduled in `NothingAtAll`, then the expression `self.holdFor: someTime` will enter an event on the queue, intermingled with events that schedule new arrivals of `Visitors` and `DoNothings`.
23

# Statistics Gathering in Event-Driven Simulations

- Duration Statistics

- Throughput Histograms

- Tallying Events

- Event Monitoring

<figure><img src="image_266.png" /></figure>
A framework for specifying event-driven simulations was presented in the previous chapter. This framework did not include methods for gathering statistics about a simulation as it is running. Statistics might consist of the amount of time each simulation object spends in the simulation (and, therefore, how well the model supports carrying out the kinds of tasks specified by the objects); information about the length of the queues such as the maximum, minimum and average lengths and amount of time spent in each queue; and information about the utilization of the simulation's resources.

There are a number of ways to add statistics gathering to class Simulation or class SimulationObject. In this chapter, we provide four examples of statistics gathering: duration statistics, throughput histograms, event tallying, and event monitoring. Each of these examples involves creating a subclass of Simulation or SimulationObject in order to provide a dictionary in which data can be stored or a file into which data can be written, and, in that subclass, modifying the appropriate methods in order to store the appropriate data.

## Duration Statistics

For the first example of statistics gathering, we create a general subclass of Simulation that simply stores the time an object enters and exits the simulation. The times are kept in a special record whose fields are the time at which the object entered the simulation (entranceTime) and the length of time the object spent in the simulation (duration). Records are described as follows.

<table><tr><td>class name</td><td>SimulationObjectRecord</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>instance variable names</td><td>entranceTime<br/>duration</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>accessing</td><td></td></tr></table>

**entrance: currentTime**

entranceTime ← currentTime

**exit: currentTime**

duration ← entranceTime - currentTime

**entrance**

↑entranceTime

**exit**

↑entranceTime + duration

**duration**

↑duration
## printing

### printOn: aStream

entranceTime printOn: aStream.

aStream tab.

duration printOn: aStream

An example subclass of Simulation which uses SimulationObjectRecords for gathering statistics is StatisticsWithSimulation. It is defined as follows.

<table><tr><td>class name</td><td>StatisticsWithSimulation</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>instance variable names</td><td>statistics</td></tr><tr><td>instance methods</td><td></td></tr></table>

## initialization

### initialize

super initialize.

statistics ← Dictionary new

## simulation scheduling

### enter: anObject

statistics at: anObject

put: (SimulationObjectRecord new entrance: currentTime)

### exit: anObject

(statistics at: anObject) exit: currentTime

## statistics

### printStatisticsOn: aStream

| stat |

aStream cr.

aStream nextPutAll: 'Object'.

aStream tab.

aStream nextPutAll: 'Entrance Time'.

aStream tab.

aStream nextPutAll: 'Duration'.

aStream cr.

"Sort with respect to the time the object entered the simulation. Because the keys as well as the values are needed, it is necessary to first obtain the set of associations and then sort them."

stat ← SortedCollection

sortBlock: [ :i :j | i value entrance <= j value entrance].

statistics associationsDo: [ :each | stat add: each].
stat do:

[ :anAssociation |
    aStream cr.
    anAssociation key printOn: aStream.
    aStream tab.
    anAssociation value printOn: aStream
    "The value is a SimulationObjectRecord which prints the entrance
time and duration"]

Suppose we created NothingAtAll as a subclass of StatisticsWithSimulation.
In this example, NothingAtAll schedules two simulation objects: one that
does nothing (a DoNothing), arriving according to a uniform distribution
from 3 to 5 units of time starting at 0; and one that looks around for 5
units of simulated time (a Visitor), arriving according to a uniform distri-
bution from 5 to 10 units of time starting at 1. Whenever one of these
objects enters the simulation, an entry is put in the statistics dictionary.
The key is the object itself; the equals (==) test is the default (==),
so each object is a unique key. The value is an instance of
SimulationObjectRecord with entrance data initialized. When the object
exits, the record associated with it is retrieved and a message is sent to
it in order to set the exit data.

class name DoNothing
superclass SimulationObject
instance methods

no new methods

class name Visitor
superclass SimulationObject
instance methods

simulation control

tasks

self holdFor: 5

class name NothingAtAll
superclass StatisticsWithSimulation
instance methods

initialization

defineArrivalSchedule

self scheduleArrivalOf: DoNothing
    accordingTo: (Uniform from: 3 to: 5).

self scheduleArrivalOf: Visitor
    accordingTo: (Uniform from: 5 to: 10)
    startingAt: 1
Whenever we halt the simulation, we can send the message `printStatisticsOn:` aFile (where aFile is a kind of `生活的流`. The result might look like:

<table><thead><tr><th>Object</th><th>Entrance Time</th><th>Duration</th></tr></thead><tbody><tr><td>a DoNothing</td><td>0.0</td><td>0.0</td></tr><tr><td>a Visitor</td><td>1.0</td><td>5.0</td></tr><tr><td>a DoNothing</td><td>4.58728</td><td>0.0</td></tr><tr><td>a Visitor</td><td>6.71938</td><td>5.0</td></tr><tr><td>a DoNothing</td><td>9.3493</td><td>0.0</td></tr><tr><td>a DoNothing</td><td>13.9047</td><td>0.0</td></tr><tr><td>a Visitor</td><td>16.7068</td><td>5.0</td></tr><tr><td>a DoNothing</td><td>17.1963</td><td>0.0</td></tr><tr><td>a DoNothing</td><td>21.7292</td><td>0.0</td></tr><tr><td>a Visitor</td><td>23.2563</td><td>5.0</td></tr><tr><td>a DoNothing</td><td>25.6805</td><td>0.0</td></tr><tr><td>a DoNothing</td><td>29.3202</td><td>0.0</td></tr><tr><td>a Visitor</td><td>32.1147</td><td>5.0</td></tr><tr><td>a DoNothing</td><td>32.686</td><td>0.0</td></tr><tr><td>a DoNothing</td><td>36.698</td><td>0.0</td></tr><tr><td>a DoNothing</td><td>41.1135</td><td>0.0</td></tr><tr><td>a Visitor</td><td>41.1614</td><td>5.0</td></tr><tr><td>a DoNothing</td><td>44.3258</td><td>0.0</td></tr><tr><td>a Visitor</td><td>48.4145</td><td>5.0</td></tr><tr><td>a DoNothing</td><td>48.492</td><td>0.0</td></tr><tr><td>a DoNothing</td><td>51.7833</td><td>0.0</td></tr><tr><td>a Visitor</td><td>53.5166</td><td>5.0</td></tr><tr><td>a DoNothing</td><td>56.4262</td><td>0.0</td></tr><tr><td>a DoNothing</td><td>60.5357</td><td>0.0</td></tr><tr><td>a Visitor</td><td>63.4532</td><td>5.0</td></tr><tr><td>a DoNothing</td><td>64.8572</td><td>0.0</td></tr><tr><td>a DoNothing</td><td>68.7634</td><td>0.0</td></tr><tr><td>a Visitor</td><td>68.921</td><td>5.0</td></tr><tr><td>a DoNothing</td><td>72.4788</td><td>0.0</td></tr><tr><td>a DoNothing</td><td>75.8567</td><td>0.0</td></tr></tbody></table>

## Throughput Histograms

A common statistic gathered in simulations is the throughput of objects, that is, how many objects pass through the simulation in some amount of time; this is proportional to how much time each object spends in the simulation. Gathering such statistics involves keeping track of the number of objects that spend time within predetermined
intervals of time. Reporting the results involves displaying the number of objects, the minimum time, maximum time, and the number of objects whose times fall within each specified interval. Such statistics are especially useful in simulations involving resources in order to determine whether or not there are sufficient resources to handle requests—if objects have to wait a long time to get a resource, then they must spend more time in the simulation.

In order to support the gathering of throughput statistics, we provide class Histogram. Histograms maintain a tally of values within prespecified ranges. For example, we might tally the number of times various values fall between 1 and 5, 5 and 10, 10 and 20, 20 and 25, 25 and 30, 30 and 35, 35 and 40, and 40 and 45. That is, we divide the interval 5 to 45 into bins of size 5 and keep a running count of the number of times a value is stored into each bin.

Class Histogram is created by specifying the lower bound, the upper bound, and the bin size. To obtain a Histogram for the above example, evaluate

Histogram from: 5 to: 45 by: 5

Besides data on the bins, a Histogram keeps track of minimum, maximum, and total values entered. An entry might not fit within the bounds of the interval; an additional variable is used to store all such entries (extraEntries). The bins are stored as elements of an array; the array size equals the number of bins (that is, upper bound - lower bound // bin size). The message store: aValue is used to put values in the Histogram. The index of the array element to be incremented is 1 + (aValue - lower bound // bins size). Most of the methods shown support printing the collected information.

<table><tr><td>class name</td><td>Histogram</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>instance variable names</td><td>tallyArray<br>lowerBound upperBound<br>step<br>minValue maxValue<br>totalValues<br>extraEntries</td></tr></table>

class methods

class initialization

from: lowerNum to: upperNum by: step

tself new newLower: lowerNum upper: upperNum by: step
instance methods

accessing

**contains: aValue**

`1lowerBound <= aValue and: [aValue < upperBound]`

**store: aValue**

`| index |`

`minValue isNil`

`ifTrue: [minValue -> maxValue -> aValue]`

`ifFalse: [minValue -> minValue min: aValue.`

`maxValue -> maxValue max: aValue].`

`totalValues -> totalValues + aValue.`

(self contains: aValue)

`ifTrue: [index -> (aValue - lowerBound // step) + 1.`

`tallyArray at: index put: (tallyArray at: index) + 1]`

`ifFalse: [extraEntries -> extraEntries + 1]`

printing

**printStatisticsOn: aStream**

`| totalObjs pos |`

`self firstHeader: aStream.`

`aStream cr; tab.`

`totalObjs -> extraEntries.`

"count the number of entries the throughput records know"

`tallyArray do: [ :each | totalObjs -> totalObjs + each].`

`totalObjs printOn: aStream.`

`aStream tab.`

`minValue printOn: aStream.`

`aStream tab.`

`maxValue printOn: aStream.`

`aStream tab.`

`(totalValues / totalObjs) asFloat printOn: aStream.`

`aStream cr.`

`self secondHeader: aStream.`

`aStream cr.`

`pos -> lowerBound.`

`tallyArray do:`

`[ :entry |`

`pos printOn: aStream.`

`aStream nextPut: $-.`

`(pos -> pos + step) printOn: aStream.`

`aStream tab.`

`entry printOn: aStream.`

`aStream tab.`

`(entry / totalObjs) asFloat printOn: aStream.`
aStream tab.

aStream nextPut: $| .

"print the X's"

entry rounded times Repeat: [aStream nextPut: $X].

aStream cr]

**firstHeader: aStream**

aStream cr; tab.

aStream nextPutAll: 'Number of'.

aStream tab.

aStream nextPutAll: 'Minimum'.

aStream tab.

aStream nextPutAll: 'Maximum'.

aStream tab.

aStream nextPutAll: 'Average'.

aStream cr; tab.

aStream nextPutAll: 'Objects'.

aStream tab.

aStream nextPutAll: 'Value'.

aStream tab.

aStream nextPutAll: 'Value'.

aStream tab.

aStream nextPutAll: 'Value'.

**secondHeader: aStream**

aStream cr; tab.

aStream nextPutAll: 'Number of'.

aStream cr.

aStream nextPutAll: 'Entry'.

aStream tab.

aStream nextPutAll: 'Objects'.

aStream tab.

aStream nextPutAll: 'Frequency'.

private

**newLower: lowerNum upper: upperNum by: stepAmount**

tallyArray ← Array new: (upperNum - lowerNum // stepAmount).

tallyArray atAllPut: 0.

lowerBound ← lowerNum.

upperBound ← upperNum.

step ← stepAmount.

minValue ← maxValue ← nil.

totalValues ← 0.

extraEntries ← 0

A simulation of visitors to a museum serves as an example of the use of a Histogram. Museum is like NothingAtAll in that Visitors arrive and look around. The Visitors take a varying amount of time to look around,
depending on their interest in the museum artifacts. We assume that this time is normally distributed with a mean of 20 and a standard deviation of 5. Visitors come to the museum throughout the day, one every 5 to 10 units of simulated time.

<table><tr><td>class name</td><td>Museum</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>instance variable names</td><td>statistics</td></tr><tr><td>instance methods</td><td></td></tr></table>

### initialization

**initialize**

super initialize.

statistics ← Histogram from: 5 to: 45 by: 5

**defineArrivalSchedule**

self scheduleArrivalOf: Visitor

accordingTo: (Uniform from: 5 to: 10)

### scheduling

**exit: aSimulationObject**

super exit: aSimulationObject.

statistics store: current Time - aSimulationObject entryTime

**printStatisticsOn: aStream**

statistics printStatisticsOn: aStream

In order for class Museum to update the statistics, Visitors must keep track of when they entered the museum and be able to respond to an inquiry as to their time of entry.

<table><tr><td>class name</td><td>Visitor</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance variable names</td><td>entryTime</td></tr><tr><td>instance methods</td><td></td></tr></table>

### initialization

**initialize**

super initialize.

entryTime ← ActiveSimulation time

### accessing

**entryTime**

fentryTime

### simulation control

**tasks**

self holdFor: (Normal mean: 20 deviation: 5) next
To create and run the simulation, we evaluate

aSimulation → Museum new startUp.

[aSimulation time < 50] while True: [aSimulation proceed]

When the Museum was created, a Histogram for statistics was created. Each time a Visitor left the Museum, data was stored in the Histogram. The data consists of the duration of the visit.

After running the simulation until time 50, we ask the Museum for a report.

aSimulation printStatisticsOn: (Disk file: 'museum.report')

The method associated with printStatisticsOn: sends the same message, printStatisticsOn:, to the Histogram, which prints the following information on the file museum report.

<table><thead><tr><th>Number of<br>Objects</th><th>Minimum<br>Value</th><th>Maximum<br>Value</th><th>Average<br>Value</th></tr></thead><tbody><tr><td>64</td><td>10.0202</td><td>31.2791</td><td>20.152</td></tr></tbody></table>

<table><thead><tr><th>Entry</th><th>Number of<br>Objects</th><th>Frequency</th><th></th></tr></thead><tbody><tr><td>5-10</td><td>0</td><td>0</td><td></td></tr><tr><td>10-15</td><td>14</td><td>0.21875</td><td>XXXXXXXXXXXXXXX</td></tr><tr><td>15-20</td><td>16</td><td>0.25</td><td>XXXXXXXXXXXXXXX</td></tr><tr><td>20-25</td><td>20</td><td>0.3125</td><td>XXXXXXXXXXXXXXX</td></tr><tr><td>25-30</td><td>13</td><td>0.203125</td><td>XXXXXXXXXXXXXXX</td></tr><tr><td>30-35</td><td>1</td><td>0.015625</td><td>X</td></tr><tr><td>35-40</td><td>0</td><td>0</td><td></td></tr><tr><td>40-45</td><td>0</td><td>0</td><td></td></tr></tbody></table>

## Tallying Events

As another example of tallying the events in a simulation, we present a commonly-used example of a simulation of Traffic. In this simulation, we tally the number of cars that enter an intersection, distinguishing those that drive straight through the intersection from those that turn left and those that turn right. By observation, we note that twice as many cars go straight as turn right or left, but twice as many turn left as right. A new car arrives at the intersection according to a uniform distribution every 0.5 to 2 units of time (self scheduleArrivalOf: Car accordingTo: (Uniform from: 0.5 to: 2)). We will run the simulation until simulated time exceeds 100.
<table><tr><td>class name</td><td>Traffic</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>instance variable names</td><td>statistics</td></tr><tr><td>instance methods</td><td></td></tr></table>

initialization

initialize

super initialize.

statistics ← Dictionary new: 3.

statistics at: #straight put: 0.

statistics at: #right put: 0.

statistics at: #left put: 0.

defineArrivalSchedule

self scheduleArrivalOf: Car accordingTo: (Uniform from: 0.5 to: 2).

self schedule: [self finishUp] at: 100

statistics

update: key

statistics at: key put: (statistics at: key) + 1

printStatisticsOn: aStream

aStream cr.

aStream nextPutAll: 'Car Direction Tally'

statistics associationsDo:

[ :assoc |

aStream cr.

assoc key printOn: aStream.

aStream tab.

assoc value printOn: aStream]

Note that in the method associated with `defineArrivalSchedule`, the action `self finishUp` is scheduled to occur at simulated time 100. This event will terminate the simulation as desired.

<table><tr><td>class name</td><td>Car</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance methods</td><td></td></tr></table>

simulation control

tasks

"Sample, without replacement, the direction through the intersection that the car will travel."

| sample |

sample ← SampleSpace data:

#(left left right straight straight straight straight straight straight straight)

ActiveSimulation update: sample next
SampleSpace was a class we introduced in Chapter 21. Cars are scheduled to enter the simulation with the sole task of picking a direction to tell the simulation. After running the simulation, we ask the Traffic simulation to report the tallies by sending it the `printStatisticsOn:` message. A possible outcome of evaluating

`aSimulation` — Traffic new startUp.

[aSimulation proceed] while True.

`aSimulation` printStatisticsOn: (Disk file: 'traffic.data')

is the following information written on the file `traffic.data`.

<table><thead><tr><td>Car Direction</td><td>Tally</td></tr></thead><tbody><tr><td>straight</td><td>57</td></tr><tr><td>right</td><td>8</td></tr><tr><td>left</td><td>15</td></tr></tbody></table>

## Event Monitoring

Another possible technique for gathering data from a simulation is to note the occurrence of each (major) event, including the entering and exiting of simulation objects. This is accomplished by creating a subclass of `SimulationObject` that we call `EventMonitor`. In this example, a class variable refers to a file onto which notations about their events can be stored. Each message that represents an event to be monitored must be overridden in the subclass to include the instructions for storing information on the file. The method in the superclass is still executed by distributing the message to the pseudo-variable `super`.

Basically, the notations consist of the time and identification of the receiver (a kind of `SimulationObject`), and an annotation such as `"enters"` or `"requests"` or `"releases."`

<table><tr><td>class name</td><td>EventMonitor</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>class variable names</td><td>DataFile</td></tr><tr><td>class methods</td><td></td></tr></table>

class initialization

file: aFile

DataFile ← aFile
instance methods

scheduling

**startUp**

self timeStamp.
DataFile nextPutAll: 'enters '.
super startUp

**finishUp**

super finishUp.
self timeStamp.
DataFile nextPutAll: 'exits '

task language

**holdFor: aTimeDelay**

self timeStamp.
DataFile nextPutAll: 'holds for '.
aTimeDelay printOn: DataFile.
super holdFor: aTimeDelay

**acquire: amount ofResource: resourceName**

| aStaticResource |
"Store fact that resource is being requested."
self timeStamp.
DataFile nextPutAll: 'requests '.
amount printOn: DataFile.
DataFile nextPutAll: 'of ', resourceName.
"Now try to get the resource."
aStaticResource ← super acquire: amount
  ofResource: resourceName.
"Returns here when resource is obtained; store the fact."
self timeStamp.
DataFile nextPutAll: 'obtained '.
amount printOn: DataFile.
DataFile nextPutAll: 'of ', resourceName.
taStaticResource

**acquire: amount**

ofResource: resourceName

withPriority: priorityNumber

| aStaticResource |
"Store fact that resource is being requested"
self timeStamp.
DataFile nextPutAll: 'requests '.
amount printOn: DataFile.
DataFile nextPutAll: 'at priority '.
priorityNumber printOn: DataFile.
DataFile nextPutAll: 'of ', resourceName.
"Now try to get the resource."

aStaticResource ←

super acquire: amount
ofResource: resourceName
withPriority: priorityNumber.

"Returns here when resource is obtained; store the fact."

self timeStamp.

DataFile nextPutAll: 'obtained'.

amount printOn: DataFile.

DataFile nextPutAll: 'of ', resourceName.

↑aStaticResource

**produce: amount ofResource: resourceName**

self timeStamp.

DataFile nextPutAll: 'produces'.

amount printOn: DataFile.

DataFile nextPutAll: 'of ', resourceName.

super produce: amount ofResource: resourceName

**release: aStaticResource**

self timeStamp.

DataFile nextPutAll: 'releases'.

aStaticResource amount printOn: DataFile.

DataFile nextPutAll: 'of ', aStaticResource name.

super release: aStaticResource

**acquireResource: resourceName**

| anEvent |

"Store fact that resource is being requested"

self timeStamp.

DataFile nextPutAll: 'wants to serve for'.

DataFile nextPutAll: resourceName.

"Now try to get the resource."

anEvent ← super acquireResource: resourceName.

"Returns here when resource is obtained; store the fact."

self timeStamp.

DataFile nextPutAll: 'can serve'.

anEvent condition printOn: DataFile.

↑anEvent

**produceResource: resourceName**

self timeStamp.

DataFile nextPutAll: 'wants to get service as'.

DataFile nextPutAll: resourceName.

super produce: amount ofResource: resourceName

**resume: anEvent**

self timeStamp.

DataFile nextPutAll: 'resumes'.
anEvent condition printOn: DataFile.

super resume: anEvent

### private

### timeStamp

DataFile cr.

ActiveSimulation time printOn: DataFile.

DataFile tab.

self printOn: DataFile.

We can monitor the events of the NothingAtAll simulation consisting of arrivals of Visitors and default simulations (DoNothings). Except for creating Visitor and DoNothing as subclasses of EventMonitor rather than of SimulationObject, the class definitions are the same.

<table><tr><td>class name</td><td>DoNothing</td></tr><tr><td>superclass</td><td>EventMonitor</td></tr><tr><td>instance methods</td><td></td></tr></table>

### no new methods

<table><tr><td>class name</td><td>Visitor</td></tr><tr><td>superclass</td><td>EventMonitor</td></tr><tr><td>instance methods</td><td></td></tr></table>

### simulation control

### tasks

self holdFor: (Uniform from: 4.0 to: 10.0) next

NothingAtAll is redefined so that the default simulation is an EventMonitor.

<table><tr><td>class name</td><td>NothingAtAll</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>instance methods</td><td></td></tr></table>

### initialization

### defineArrivalSchedule

self scheduleArrivalOf: DoNothing
accordingTo: (Uniform from: 1 to: 5).

self scheduleArrivalOf: Visitor
accordingTo: (Uniform from: 4 to: 8)
startingAt: 3

### After executing
Visitor file: (Disk file: 'NothingAtAll.events').

"This informs DoNothing too"

aSimulation ← NothingAtAll new startUp.

[aSimulation time < 25] while True: [aSimulation proceed]

the file 'NothingAtAll.events' contains the following information

<table><tr><td>0.0</td><td>a DoNothing enters</td></tr><tr><td>0.0</td><td>a DoNothing exits</td></tr><tr><td>3.0</td><td>a Visitor enters</td></tr><tr><td>3.0</td><td>a Visitor holds for 7.5885</td></tr><tr><td>4.32703</td><td>a DoNothing enters</td></tr><tr><td>4.32703</td><td>a DoNothing exits</td></tr><tr><td>7.74896</td><td>a Visitor enters</td></tr><tr><td>7.74896</td><td>a Visitor holds for 4.14163</td></tr><tr><td>8.20233</td><td>a DoNothing enters</td></tr><tr><td>8.20233</td><td>a DoNothing exits</td></tr><tr><td>10.5885</td><td>a Visitor exits</td></tr><tr><td>11.8906</td><td>a Visitor exits</td></tr><tr><td>12.5153</td><td>a DoNothing enters</td></tr><tr><td>12.5153</td><td>a DoNothing exits</td></tr><tr><td>14.2642</td><td>a Visitor enters</td></tr><tr><td>14.2642</td><td>a Visitor holds for 4.51334</td></tr><tr><td>16.6951</td><td>a DoNothing enters</td></tr><tr><td>16.6951</td><td>a DoNothing exits</td></tr><tr><td>18.7776</td><td>a Visitor exits</td></tr><tr><td>19.8544</td><td>a Visitor enters</td></tr><tr><td>19.8544</td><td>a Visitor holds for 5.10907</td></tr><tr><td>20.5342</td><td>a DoNothing enters</td></tr><tr><td>20.5342</td><td>a DoNothing exits</td></tr><tr><td>23.464</td><td>a DoNothing enters</td></tr><tr><td>23.464</td><td>a DoNothing exits</td></tr><tr><td>24.9635</td><td>a Visitor exits</td></tr></table>

Distinctively labeling each arriving SimulationObject might improve the ability to follow the sequence of events. The goal is to have a trace for an execution of the NothingAtAll simulation look like the following.

<table><tr><td>0.0</td><td>DoNothing 1 enters</td></tr><tr><td>0.0</td><td>DoNothing 1 exits</td></tr><tr><td>3.0</td><td>Visitor 1 enters</td></tr><tr><td>3.0</td><td>Visitor 1 holds for 7.5885</td></tr><tr><td>4.32703</td><td>DoNothing 2 enters</td></tr><tr><td>4.32703</td><td>DoNothing 2 exits</td></tr><tr><td>7.74896</td><td>Visitor 2 enters</td></tr></table>
<table><tr><td>7.74896</td><td>Visitor 2 holds for 4.14163</td></tr><tr><td>8.20233</td><td>DoNothing 3 enters</td></tr><tr><td>8.20233</td><td>DoNothing 3 exits</td></tr><tr><td>10.5885</td><td>Visitor 1 exits</td></tr><tr><td>11.8906</td><td>Visitor 2 exits</td></tr><tr><td>12.5153</td><td>DoNothing 4 enters</td></tr><tr><td>12.5153</td><td>DoNothing 4 exits</td></tr><tr><td>14.2642</td><td>Visitor 3 enters</td></tr><tr><td>14.2642</td><td>Visitor 3 holds for 4.51334</td></tr><tr><td>16.6951</td><td>DoNothing 5 enters</td></tr><tr><td>16.6951</td><td>DoNothing 5 exits</td></tr><tr><td>18.7776</td><td>Visitor 3 exits</td></tr><tr><td>19.8544</td><td>Visitor 4 enters</td></tr><tr><td>19.8544</td><td>Visitor 4 holds for 5.10907</td></tr><tr><td>20.5342</td><td>DoNothing 6 enters</td></tr><tr><td>20.5342</td><td>DoNothing 6 exits</td></tr><tr><td>23.464</td><td>DoNothing 7 enters</td></tr><tr><td>23.464</td><td>DoNothing 7 exits</td></tr><tr><td>24.9635</td><td>Visitor 4 exits</td></tr></table>

Each subclass of EventMonitor must create its own sequence of labels. EventMonitor sets up a label framework in which the subclass can implement a way of distinguishing its instances. EventMonitor itself provides a model that the subclasses can duplicate; in this way, a default simulation using instances of EventMonitor can be used to produce the trace shown above. In addition to the scheduling, task language and private, messages shown in the earlier implementation of EventMonitor, the class description has the following messages.

<table><tr><td>class name</td><td>EventMonitor</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance variable names</td><td>label</td></tr><tr><td>class variable names</td><td>DataFile<br>Counter</td></tr></table>

class methods

class initialization

file: aFile

DataFile ← aFile.

Counter ← 0

instance methods

initialization

initialize

super initialize.

self setLabel
accessing

**setLabel**

Counter ← Counter + 1.

label ← Counter printString

**label**

↑label

printing

**printOn: aStream**

self class name printOn: aStream.

aStream space.

aStream nextPutAll: self label

Visitor, as a subclass of EventMonitor, has to have an independent class variable to act as the counter of its instances. The class description of Visitor is now

<table><tr><td>class name</td><td>Visitor</td></tr><tr><td>superclass</td><td>EventMonitor</td></tr><tr><td>class variable names</td><td>MyCounter</td></tr><tr><td>class methods</td><td></td></tr></table>

class initialization

**file: aFile**

super file: aFile.

MyCounter ← 0

instance methods

accessing

**setLabel**

MyCounter ← MyCounter + 1.

label ← MyCounter printString

simulation control

**tasks**

self holdFor: (Uniform from: 4.0 to: 10.0) next

MyCounter is set to 0 when the instance is told initialize; the method is found in class EventMonitor. Printing retrieves the label that Visitor redefines with respect to MyCounter. We let DoNothing use the class variable, Counter, of its superclass. Then the desired trace will be produced using these definitions.
# The Use of Resources in Event-Driven Simulations

* Implementing Classes ResourceProvider and StaticResource

* Consumable Resources

* Nonconsumable Resources
    * Example of a File System

* Renewable Resources
    * Example of a Ferry Service

<figure><img src="image_267.png" /></figure>
In the previous chapters, we introduced a framework in which to specify event-driven simulations and to gather statistics about such simulations. Without resources to contend for and use, the only real task that an object can perform in a simulation is to hold (wait) for some specified amount of simulated time. Two kinds of resources are illustrated in this chapter: fixed resources and fluctuating resources. These kinds of resources were introduced in Chapter 22; the example in that chapter of classes Simulation and SimulationObject defined a support for resources coordination that will be further described in this chapter.

A fixed resource can be *consumable*. The simulation with a consumable resource begins with a given quantity of some resource, say, jelly beans. As the simulation proceeds, objects acquire the resource, ultimately using up all that were originally available. New objects needing the resource either terminate without successfully completing their tasks, or are indefinitely delayed waiting for a resource that will never be provided. Alternatively, a fixed resource can be *nonconsumable*. The simulation begins with a given quantity of some nonconsumable resource, say, glass jars. As the simulation proceeds, objects acquire the resource. When an object no longer needs the resource, it is recycled. Objects needing the resource either obtain it immediately or are delayed until a recycled one becomes available.

A fluctuating resource models producer/consumer relationships. A simulation can begin with a given quantity of some resource, say cars. As the simulation proceeds, objects acquire the resource; when they no longer need the resource, they recycle it (such as in the used car market). New resources can be added (produced), increasing the supply of the resource. Objects needing the resource either obtain it immediately or must wait until a recycled one or a new one becomes available. A fluctuating resource for which additional quantities can be produced is called a *renewable* resource. The example of the car is an example of a resource that is both renewable and nonconsumable.

## Implementing ResourceProvider and StaticResource

The modeler's language for specifying resources in a Simulation includes expressions of the form

`self.produce: amount of: resourceName`

The response to this message is either to create an instance of class Resource with amount as its available quantity of resources, or to retrieve an existing Resource and increment its resources by amount. Instances of ResourceProvider are created by sending ResourceProvider the message named: `aString` or named: `aString` with: `amount`.

When a SimulationObject requests a resource (acquire: amount ofResource: resourceName), the currently active simulation
(ActiveSimulation) is asked to provide the corresponding resource (provideResourceFor:). Presumably the resource exists in the simulation as a result of the initialization of the Simulation; the Simulation refers to a Set of instances of ResourceProvider and can enumerate this Set in order to find one whose name is resourceName.

Once the SimulationObject has access to a ResourceProvider it can

ask how many resources it has available,

ask its name,

ask to acquire some amount (and with a particular access priority),

ask to produce some amount.

When a SimulationObject asks to acquire some resources, this request is added to a queue of such requests, ordered with respect to priority and, within identical priority levels, on a first-come first-served basis. Each time a request is made or more resources are produced, the ResourceProvider checks to see if one or more of its pending requests can be satisfied.

Each request is stored as an instance of class DelayedEvent. DelayedEvent was described in Chapter 22. Each DelayedEvent refers to a condition. In the case of delayed tasks, the condition is the time at which the tasks should be resumed; in the case of resource requests, the condition is an instance of StaticResource which is a representation of the requested resource and desired amount. Whenever a request is made, the request is stored on the waiting queue, pending, and then an attempt is made to provide the resource.

Class ResourceProvider is a subclass of class Resource. Class ResourceCoordinator, to be presented in the next chapter, is also a subclass of Resource. Resource represents the resource in terms of its name and the queue of requests that must be satisfied. A class variable refers to the currently active simulation (ActiveSimulation) for access to the time and process reference counting.

<table><tr><td>class name</td><td>Resource</td></tr><tr><td>superclass</td><td>Object</td></tr><tr><td>instance variable names</td><td>pending<br/>resourceName</td></tr><tr><td>class variable names</td><td>ActiveSimulation</td></tr><tr><td>class methods</td><td></td></tr><tr><td>class initialization</td><td></td></tr></table>

**activeSimulation: existingSimulation**

ActiveSimulation ← existingSimulation

instance creation

**named: resourceName**

↑self new: resourceName
instance methods

accessing

**addRequest: aDelayedEvent**

pending add: aDelayedEvent.

self provideResources.

ActiveSimulation stopProcess.

aDelayedEvent pause.

ActiveSimulation startProcess

**name**

tresourceName

private

**provideResources**

tself

**setName: aString**

resourceName -> aString.

pending -> SortedCollection new

Notice that the mechanism used for storing requests on the SortedCollection, pending, is similar to that used for storing delayed events on the eventQueue of a Simulation. That is, a process that was running is suspended so that the reference count for processes in the Simulation is decremented. At the point that the process continues again, the reference count is incremented. A Semaphore is used in order to synchronize pausing and resuming the simulation process.

Class ResourceProvider represents resources as simple quantifiable items that have no tasks to do and are, therefore, not created as actual SimulationObjects. Rather, a numerical count is kept of the number of the items. When a SimulationObject successfully acquires this kind of resource, the SimulationObject is given access to an instance of StaticResource. The last expression of the method in ResourceProvider associated with acquire:withPriority: creates and returns a StaticResource. Prior to evaluating this expression, a DelayedEvent is removed from the collection of pending requests and the amount requested decremented from the amount currently available.

<table><tr><td>class name</td><td>ResourceProvider</td></tr><tr><td>superclass</td><td>Resource</td></tr><tr><td>instance variable names</td><td>amountAvailable</td></tr><tr><td>class methods</td><td></td></tr></table>

instance creation

**named: resourceName with: amount**

tself new: resourceName with: amount
**named: resourceName**

```
this new setName: resourceName with: 0
```

instance methods

accessing

**amountAvailable**

```
this amountAvailable
```

task language

**acquire: amountNeeded withPriority: priorityNumber**

```
| anEvent |
anEvent --> DelayedEvent onCondition: (StaticResource
                                     for: amountNeeded
                                     of: self
                                     withPriority: priorityNumber).

this addRequest: anEvent.
this anEvent condition
```

**produce: amount**

```
this amountAvailable --> amountAvailable + amount.
```

this provideResources

private

**provideResources**

```
| anEvent |
[pending empty not
  and: [pending first condition amount <= amountAvailable]]
whileTrue:
    [anEvent --> pending removeFirst.
     amountAvailable --> amountAvailable - anEvent condition amount.
     anEvent resume]
```

**setName: resourceName with: amount**

```
this super setName: aString.
```

this amountAvailable --> amount

A StaticResource represents a SimulationObject with no tasks to do other than to hold quantities of items for some other SimulationObject.

<table><tr><td>class name</td><td>StaticResource</td></tr><tr><td>superclass</td><td>SimulationObject</td></tr><tr><td>instance variable names</td><td>amount<br>resource<br>priority</td></tr></table>

class methods

instance creation

**for: amount of: aResource withPriority: aNumber**

```
this new setAmount: amount resource: aResource withPriority: aNumber
```
instance methods

accessing

**amount**

↑amount

**name**

↑resource name

**priority**

↑priority

comparing

< = **aStaticResource**

↑priority <= aStaticResource priority

task language

**consume: aNumber**

amount ← (amount — aNumber) max: 0

**release**

resource produce: amount.

amount ← 0

private

**setAmount: aNumber**

**resource: aResource**

**withPriority: priorityNumber**

amount ← aNumber.

resource ← aResource.

priority ← priorityNumber

Since a SimulationObject can hold on to a reference to a StaticResource, the messages consume: and release are part of the task language of a SimulationObject. When a SimulationObject acquires a resource, it is presumably consuming that resource, until that resource is returned to the simulation. The amount of resource held in the StaticResource is returned to the simulation by sending the StaticResource the message release. (Typically, however, the SimulationObject sends itself the message release: aStaticResource so that a uniform style of sending messages to self is maintained in the method associated with the object's tasks. This uniformity simplifies the design of a method for tracing or monitoring the events of a simulation. Because all task messages are sent as messages to self and therefore to a SimulationObject, it is possible to create a subclass of SimulationObject (EventMonitor was the example we pres-
ented in Chapter 23) in which all task messages are intercepted in order to store a notation that the task is being done.

Using `acquire:ofResource:` and `release:`, the resource is treated as a nonconsumable resource. A mixture is possible. The `SimulationObject` can acquire some amount of a resource, say 10, consume 5, and return 5. The message `consume:` is used to remove resources from the simulation. Thus the example would be accomplished by sending a `StaticResource`, acquired with 10 resources, the message `consume:` 5, and then the message `release` (or sending `release:` a `StaticResource` to self).

## Consumable Resources

A simple jelly bean example illustrates the idea of a consumable resource. Recall the simulation example, `NothingAtAll`, introduced in Chapter 22. Suppose that whenever a `Visitor` enters the simulation and looks around, it has a task to acquire 2 jelly beans, take 2 units of time eating the beans, and leave. The simulation is initialized with one resource consisting of 15 jelly beans. The definition of this version of `NothingAtAll` is

<table><tr><td>class name</td><td>NothingAtAll</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>initialization</td><td></td></tr></table>

**defineResources**

`self produce:` 15 of: 'jelly beans'

**defineArrivalSchedule**

`self scheduleArrivalOf:` `Visitor` accordingTo: (Uniform from: 1 to: 3)

The `Visitor`'s tasks are expressed in two messages to self found in its method for tasks.

**tasks**

`self acquire:` 2 ofResource: 'jelly beans'.

`self holdFor:` 2

An example execution of this simulation, in which only exits and entries are monitored, is

<table><tr><td>0.0</td><td>Visitor 1 enters</td></tr><tr><td>2.0</td><td>Visitor 1 exits</td></tr><tr><td>2.03671</td><td>Visitor 2 enters</td></tr></table>
<table><tr><td>4.03671</td><td>Visitor 2 exits</td><td></td></tr><tr><td>4.34579</td><td>Visitor 3 enters</td><td></td></tr><tr><td>5.92712</td><td>Visitor 4 enters</td><td></td></tr><tr><td>6.34579</td><td>Visitor 3 exits</td><td></td></tr><tr><td>7.92712</td><td>Visitor 4 exits</td><td></td></tr><tr><td>8.46271</td><td>Visitor 5 enters</td><td></td></tr><tr><td>10.4627</td><td>Visitor 5 exits</td><td></td></tr><tr><td>10.5804</td><td>Visitor 6 enters</td><td></td></tr><tr><td>12.5804</td><td>Visitor 6 exits</td><td></td></tr><tr><td>12.7189</td><td>Visitor 7 enters</td><td></td></tr><tr><td>14.7189</td><td>Visitor 7 exits</td><td>last visitor to get jelly beans</td></tr><tr><td>15.0638</td><td>Visitor 8 enters</td><td>endless waiting from now on</td></tr><tr><td>17.6466</td><td>Visitor 9 enters</td><td></td></tr><tr><td>19.8276</td><td>Visitor 10 enters</td><td></td></tr></table>

After the seventh Visitor enters, there are no more jelly beans, so all the subsequent Visitors are endlessly delayed waiting for resources that will never be made available. Alternatively, the Visitor could check to see if any jelly beans remain available (inquireFor:ofResource:). If none remain, the Visitor can leave rather than getting caught in the queue. This corresponds to the following method for tasks.

### tasks

(self inquireFor: 2 ofResource: 'jelly beans')

ifTrue: [self acquire: 2 ofResource: 'jelly beans']

self holdFor: 2]

One additional refinement might be to inform the simulation that all resources are used up and that it is time to "close the store." This is done by sending the Visitor the message stopSimulation. If we were to send this message the first time a Visitor enters who can not acquire enough jelly beans, then it is possible that a Visitor who has entered the store will get locked in. We have to make certain that a Visitor who acquires the last jelly beans, closes the store upon exit; in this way, a later Visitor will not lock this last successful one into the store. This corresponds to the following method for tasks.

### tasks

| flag |

(self inquireFor: 2 ofResource: 'jelly beans')

ifTrue: [self acquire: 2 ofResource: 'jelly beans']

flag ← self inquireFor: 2 ofResource: 'jelly beans'.

"Are there still 2 left so that the next Visitor can be served?"

self holdFor: 2.

flag ifFalse: [self stopSimulation]]

Here is another example execution of the simulation NothingAtAll, in which only exits and entries are monitored.
<table><tr><td>0.0</td><td>Visitor 1 enters</td><td></td></tr><tr><td>2.0</td><td>Visitor 1 exits</td><td></td></tr><tr><td>2.26004</td><td>Visitor 2 enters</td><td></td></tr><tr><td>4.26004</td><td>Visitor 2 exits</td><td></td></tr><tr><td>4.83762</td><td>Visitor 3 enters</td><td></td></tr><tr><td>6.34491</td><td>Visitor 4 enters</td><td></td></tr><tr><td>6.83762</td><td>Visitor 3 exits</td><td></td></tr><tr><td>8.34491</td><td>Visitor 4 exits</td><td></td></tr><tr><td>8.51764</td><td>Visitor 5 enters</td><td></td></tr><tr><td>9.9006</td><td>Visitor 6 exits</td><td></td></tr><tr><td>10.5176</td><td>Visitor 5 exits</td><td></td></tr><tr><td>11.9006</td><td>Visitor 6 exits</td><td></td></tr><tr><td>12.6973</td><td>Visitor 7 enters</td><td>last successful requestor</td></tr><tr><td>14.0023</td><td>Visitor 8 enters</td><td>nothing available for this Visitor</td></tr><tr><td>14.0023</td><td>Visitor 8 exits</td><td></td></tr><tr><td>14.6973</td><td>Visitor 7 exits</td><td>last successful requestor closes shop on exit</td></tr></table>

The EventMonitor class described in the previous chapter also monitors the use of resources. So, a trace of NothingAtAll would include the times at which jelly beans were requested and obtained.

<table><tr><td>0.0</td><td>Visitor 1 enters</td><td></td></tr><tr><td>0.0</td><td>Visitor 1 requests 2 of jelly beans</td><td></td></tr><tr><td>0.0</td><td>Visitor 1 obtained 2 of jelly beans</td><td></td></tr><tr><td>0.0</td><td>Visitor 1 holds for 2</td><td></td></tr><tr><td>1.40527</td><td>Visitor 2 enters</td><td></td></tr><tr><td>1.40527</td><td>Visitor 2 requests 2 of jelly beans</td><td></td></tr><tr><td>1.40527</td><td>Visitor 2 obtained 2 of jelly beans</td><td></td></tr><tr><td>1.40527</td><td>Visitor 2 holds for 2</td><td></td></tr><tr><td>2.0</td><td>Visitor 1 exits</td><td></td></tr><tr><td>2.56522</td><td>Visitor 3 enters</td><td></td></tr><tr><td>2.56522</td><td>Visitor 3 requests 2 of jelly beans</td><td></td></tr><tr><td>2.56522</td><td>Visitor 3 obtained 2 of jelly beans</td><td></td></tr><tr><td>2.56522</td><td>Visitor 3 holds for 2</td><td></td></tr><tr><td>3.40527</td><td>Visitor 2 exits</td><td></td></tr><tr><td>4.56522</td><td>Visitor 3 exits</td><td></td></tr><tr><td>5.3884</td><td>Visitor 4 enters</td><td></td></tr><tr><td>5.3884</td><td>Visitor 4 requests 2 of jelly beans</td><td></td></tr><tr><td>5.3884</td><td>Visitor 4 obtained 2 of jelly beans</td><td></td></tr><tr><td>5.3884</td><td>Visitor 4 holds for 2</td><td></td></tr><tr><td>6.69794</td><td>Visitor 5 enters</td><td></td></tr><tr><td>6.69794</td><td>Visitor 5 requests 2 of jelly beans</td><td></td></tr><tr><td>6.69794</td><td>Visitor 5 obtained 2 of jelly beans</td><td></td></tr><tr><td>6.69794</td><td>Visitor 5 holds for 2</td><td></td></tr></table>
<table><tr><td>7.3884</td><td>Visitor 4 exits</td></tr><tr><td>7.72174</td><td>Visitor 6 enters</td></tr><tr><td>7.72174</td><td>Visitor 6 requests 2 of jelly beans</td></tr><tr><td>7.72174</td><td>Visitor 6 obtained 2 of jelly beans</td></tr><tr><td>7.72174</td><td>Visitor 6 holds for 2</td></tr><tr><td>8.69794</td><td>Visitor 5 exits</td></tr><tr><td>9.72174</td><td>Visitor 6 exits</td></tr><tr><td>10.153</td><td>Visitor 7 enters</td></tr><tr><td>10.153</td><td>Visitor 7 requests 2 of jelly beans</td></tr><tr><td>10.153</td><td>Visitor 7 obtained 2 of jelly beans</td></tr><tr><td>10.153</td><td>Visitor 7 holds for 2</td></tr><tr><td>11.875</td><td>Visitor 8 enters</td></tr><tr><td>11.875</td><td>Visitor 8 exits</td></tr><tr><td>12.153</td><td></td></tr></table>

At time 11.875, all but one jelly bean has been consumed. At time 12.153 Visitor number 7 stops the simulation.

## Nonconsumable Resources

A car rental simulation serves to illustrate the use of a nonconsumable resource. The example simulation is a short-term car rental agency that opens up with 15 cars and 3 trucks available. Renters of cars arrive with a mean rate of one every 30 minutes, and those requiring trucks one every 120 minutes. The first car renter arrives when the shop opens, and the first truck renter arrives 10 minutes later. Classes CarRenter and TruckRenter represent these simulation objects.

RentalAgency is specified as a subclass of Simulation. It implements the two initialization messages, defineArrivalSchedule and defineResources.

<table><tr><td>class name</td><td>RentalAgency</td></tr><tr><td>superclass</td><td>Simulation</td></tr><tr><td>instance methods</td><td></td></tr><tr><td>initialization</td><td></td></tr></table>

### defineArrivalSchedule

self scheduleArrivalOf: CarRenter
accordingTo: (Exponential mean: 30).

self scheduleArrivalOf: TruckRenter
accordingTo: (Exponential mean: 120)
startingAt: 10

### defineResources

self produce: 15 of: 'car'.

self produce: 3 of: 'truck'.
The tasks for CarRenter and TruckRenter are similar. First acquire a car or truck; if none are available, wait. Once the vehicle is obtained, use it. A CarRenter keeps the car between 4 and 8 hours (uniformly distributed); a TruckRenter keeps the truck between 1 and 4 hours (uniformly distributed). These usage times are indicated by having the renter hold for the appropriate amount of time before returning the vehicle (i.e., releasing the resource).

In order to monitor the two kinds of SimulationObject, and to have labels that separately identify each kind, the implementations of CarRenter and TruckRenter duplicate the labeling technique demonstrated earlier for class Visitor.

<table><tr><td>class name</td><td>CarRenter</td></tr><tr><td>superclass</td><td>EventMonitor</td></tr><tr><td>class variable names</td><td>CarCounter<br/>Hour</td></tr></table>

class methods

class initialization

**file: file**

super file: file.
CarCounter ← 0.
Hour ← 60

instance methods

accessing

**setLabel**

CarCounter ← CarCounter + 1.
label ← CarCounter printString

simulation control

**tasks**

| car |
car → self acquire: 1 of Resource: 'car'.
self holdFor: (Uniform from: 4*Hour to: 8*Hour) next.
self release: car

<table><tr><td>class name</td><td>TruckRenter</td></tr><tr><td>superclass</td><td>EventMonitor</td></tr><tr><td>class variable names</td><td>TruckCounter<br/>Hour</td></tr></table>

class methods

class initialization

**file: file**

super file: file.
TruckCounter ← 0
Hour ← 60