Smalltalk80LanguageImplementation:Chapter 12

From 흡혈양파의 번역工房
Revision as of 08:47, 9 May 2014 by Onionmixer (talk | contribs) (오타수정)
Jump to navigation Jump to search
Chapter 12 Protocol for Streams

Protocol for Streams

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
                IdentifyDictionary

    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


The collection classes provide the basic data structure for storing objects together as nonlinear and linear groups. The protocol for these classes makes it possible directly to access (store and retrieve) individual elements. It also, through the enumeration messages, supports noninterruptible accessing of all of the elements, in order. However, it does not support intermingling the two kinds of accessing operations-enumerating and storing. Nor does the collection protocol support accessing individual elements, one at a time, unless an external position reference is separately maintained.

Unless an easily computed external name for each element exists, interruptible enumeration of individual elements can not be carried out efficiently. It is possible, for example, sequentially to read elements of an OrderedCollection using a combination of first and after:, as long as the elements of the collection are unique. An alternative approach involves the collection itself remembering, in some way, which element was last accessed. We call this the "position reference" in the discussion that follows. The possibility of shared access to a sequence of elements, however, means that it is necessary to maintain a separate, external memory of the last element accessed.


Class Stream represents the ability to maintain a position reference into a collection of objects. We use the phrase streaming over a collection to mean accessing the elements of a collection in such a way that it is possible to enumerate or store each element, one at a time, possibly intermingling these operations. By creating several Streams over the same collection, it is possible to maintain multiple position references into the same collection.


There are a number of ways to maintain a position reference for streaming over a collection. A common one is to use an integer as an index. This approach can be used for any collection whose elements are externally named by an integer. All SequenceableCollections fall into this category. As we shall describe later, such a Stream is represented in the Smalltalk-80 system by the class PositionableStream. A second way to maintain a position reference is to use a seed for a generator of objects. An example of this kind of Stream in the Smalltalk-80 system is class Random which was already presented in Chapter 8. And a third way is to maintain a non-numerical position reference, such as a reference to a node in a sequence; this approach is illustrated in this chapter by an example class that supports streaming over a linked list or a tree structure.


Class Stream

Class Stream, a subclass of class Object, is a superclass that specifies the accessing protocol for streaming over collections. Included in this protocol are messages for reading (retrieving) and writing (storing) into the collection, although not all the subclasses of class Stream can support both kinds of accessing operations. The basic reading message is next; its response is the next element in the collection that is referenced by the Stream. Given the ability to access the next element, more general reading messages can be supported. These are next: anInteger, which responds with a collection of anInteger number of elements; nextMatchFor: anObject, which reads the next element and answers whether it is equal to the argument, anObject; and contents, which answers a collection of all of the elements.

accessing--reading
next Answer the next object accessible by the receiver.
next: anInteger Answer the next anInteger number of objects accessible by the receiver. Generally, the answer will be a collection of the same class as the one accessed by the receiver.
nextMatchFor: anObject Access the nex object and answer whether it is equal to the argument, anObject.
contents Answer all of the objects in the collection accessed by the receiver. Generally, the answer will be a collection of the same class as the one accessed by the receiver.
Stream instance protocol


The basic writing message is nextPut: anObject; this means to store the argument, anObject, as the next element accessible by the receiver. If both read and write messages are possible, a next message following a nextPut: anElement does not read the element just stored, but rather the one after it in the collection. Writing messages also include nextPutAll: aCollection, which stores all of the elements in the argument into the collection accessed by the receiver, and next: anInteger put: anObject, which stores the argument, anObject, as the next anInteger number of elements.

accessing--writing
nextPut: anObject Store the argument, anObject, as the next element accessible by the receiver. Answer anObject.
nextPutAll: aCollection Store the elements in the argument, aCollection, as the next elements accessible by the receiver. Answer aCollection.
next: anInteger put: anObject Store the argument, anObject, as the next anInteger number of elements accessible by the receiver. Answer anObject.
Stream instance protocol


The reading and writing messages each determine if a next element can be read or written and, if not, an error is reported. The programmer might therefore wish to determine whether accessing is still feasible; this is accomplished by sending the Stream the message atEnd.

testing
atEnd Answer whether the receiver cannot access any more objects.
Stream instance protocol


Noninterrupted reading of elements that are applied as arguments to a block can be done by sending the message do: aBlock, similar to the enumerating message supported by the collection classes.

enumerating
do: aBlock Evaluate the argument, aBlock, for each of the remaining elements that can be accessed by the receiver.
Stream instance protocol


The implementation of this enumeration message depends on sending the messages atEnd and next to the message receiver. We show this method as an example of the use of these messages. 

do: aBlock
    [self atEnd] whileFalse: [aBlock value: self next]


Each kind of Stream must specify its instance creation messages. In general, a Stream can not be created simply by sending the message new because the Stream must be informed of which collection it accesses and what is its initial position reference.


As a simple example, let's assume that the collection accessed by a Stream is an Array and that the Stream is called accessor. The contents of the Array are the Symbols 

Bob Dave Earl Frank Harold Jim Kim Mike Peter Rick Sam Tom


and the position reference is such that Bob is the next accessible element. Then

expression result
accessor next Bob
accessor next Dave
accessor nextMatchFor: #Bob false
accessor nextMatchFor: #Frank true
accessor next Harold
accessor nextPut: #James James
accessor contents (Bob Dave Earl Frank Harold James Kim Mike Peter Rick Sam Tom)
accessor nextPutAll: #(Karl Larry Paul) (Karl Larry Paul)
accessor contents (Bob Dave Earl Frank Harold James Karl Larry Paul Rick Sam Tom)
accessor next: 2 put: #John John
accessor contents (Bob Dave Earl Frank Harold James Karl Larry Paul John John Tom)
accessor next Tom
accessor atEnd true


Positionable Streams

In the introduction to this chapter we indicated three possible approaches that a Stream might use in order to maintain a position reference. The first one we will present uses an integer index which is incremented each time the Stream is accessed. The Stream accesses only those kinds of collections whose elements have integers as external keys; these include all of the subclasses of SequenceableCollection.


Class PositionableStream is a subclass of class Stream. It provides additional protocol appropriate to Streams that can reposition their position references, but, it is an abstract class because it does not provide an implementation of the inherited messages next and nextPut: anObject. The implementation of these messages is left to the subclasses of PositionableStream--ReadStream, WriteStream, and ReadWriteStream.


A PositionableStream is created by sending the class one of two instance creation messages, on" aCollection or on" aCollection from" firstIndex to: lastIndex. The argument, aCollection, is the collection the Stream accesses; in the second case, a copy of a subcollection of aCollection is accessed, i.e., the one delimited by the two arguments firstIndex and lastIndex.

instance creation
on: aCollection Answer an instance of a kind of PositionableStream that streams over the argument, aCollection.
on: aCollection from: firstIndex to: lastIndex Answer an instance of a kind of PositionableStream that streams over a copy of a subcollection of the argument, aCollection, from firstIndex to lastIndex.
PositionableStream class protocol


PositionableStream supports additional protocol for accessing and testing the contents of the collection.

testing
isEmpty Answer true if the collection the receiver accesses has no elements; otherwise, answer false.
accessing
peek Answer the next element in the collection (as in the message next), but do not change the position reference. Answer nil if the receiver is at the end.
peekFor: anObject Determine the response to the message peek. If it is the same as the argument, anObject, then increment the position reference and answer true. Otherwise answer false and do not change the position reference.
upTo: anObject Answer a collection of elements starting with the next element accessed by the receiver, and up to, not inclusive of, the next element that is equal to anObject. If anObject is not in the collection, answer the entire rest of the collection.
reverseContents Answer a copy of the receiver's contents in reverse order.
PositionableStream instance protocol


Since a PositionableStream is known to store an explicit position reference, protocol for accessing that reference is supported. In particular, the reference can be reset to access the beginning, the end, or any other position of the collection.

positioning
position Answer the receiver's current position reference for accessing the collection.
position: anInteger Set the receiver's current position reference for accessing the collection to be the argument, anInteger. If the argument is not within the bounds of the receiver's collection, report an error.
reset Set the receiver's position reference to the beginning of the collection.
setToEnd Set the receiver's position reference to the end of the collection.
skip: anInteger Set the receiver's position reference to be the current position plus the argument, anInteger, possibly adjusting the result so as to remain within the bounds of the collection.
skipTo: anObject Set the receiver's position reference to be past the next occurrence of the argument, anObject, in the collection. Answer whether such an occurrence existed.
PositionableStream instance protocol


Class ReadStream

Class ReadStream is a concrete subclass of PositionableStream that represents an accessor that can only read elements from its collection. We can create an example similar to the previous one to demonstrate the use of the additional protocol provided in class PositionableStream and inherited by all ReadStreams. None of the nextPut:, next:put:, nor nextPutAll: messages can be successfully sent to a ReadStream. 

accessor ← ReadStream on: #(Bob Dave Earl Frank Harold Jim Kim Mike Peter Rick Sam Tom)


expression result
accessor next Bob
accessor nextMatchFor: #Dave true
accessor peek Earl
accessor next Earl
accessor peekFor: #Frank true
accessor next Harold
accessor upTo: #Rick (Jim Kim Mike Peter)
accessor position 10
accessor skip: 1 the accessor itself
accessor next Tom
accessor atEnd true
accessor reset the accessor itself
accessor skipTo: #Frank true
accessor next Harold


Class WriteStream

Class WriteStream is a subclass of PositionableStream representing accessors for writing elements into a collection. None of the next, next:, nor do: messages can be successfully sent to a WriteStream.


WriteStrearns are used throughout the Smalltalk-80 system as a part of the methods for printing or storing a string description of any object. Each object in the system can respond to the messages printOn: aStream and storeOn: aStream. The methods associated with these messages consist of a sequence of messages to the argument, which is a kind of Stream that allows writing elements into the collection it accesses. These messages are nextPut:, where the argument is a Character, and nextPutAll:, where the argument is a String or a Symbol. An example will illustrate this idea.


Class Object printing protocol, as described in Chapter 6, includes the message printString. An implementation of this message is 

printString
    | aStream |
    aStream ← WriteStream on: (String new: 16).
    self printOn: aStream.
    ↑aStream contents


If a collection is sent the message printString, then the answer is a String that is a description of the instance. The method creates a WriteStream that the collection can store into, sends the message printOn: to the collection, and then responds with the contents of the resulting WriteStream. The message storeString to any object is similarly implemented in class Object, the difference being that the second expression consists of the message storeOn: aStream rather than printOn: aStream.


The general way in which collections print a description of themselves is to print their class name followed by a left parenthesis, followed by a description of each element separated by spaces, and terminated by a right parenthesis. So if a Set has four elements--the Symbols one, two, three, and four--then it prints on a Stream as 

Set (one two three four )


An OrderedCollection with the same elements prints on a Stream as 

OrderedCollection (one two three four )


and so on.


Recall that the definition of printOn: and storeOn: given in Chapter 6 is that any suitable description can be provided for printOn:, but the description created by storeOn: must be a well-formed expression that, when evaluated, re-constructs the object it purports to describe.


Here is an implementation in class Collection for printOn:. 

printOn: aStream
    aStream nextPutAll: self class name.
    aStream space.
    aStream nextPut: $(.
    self do:
        [ :element |
            element printOn: aStream.
            aStream space].
    aStream nextPut: $)


Notice that the message space is sent to the WriteStream (aStream). It, and a number of other messages are provided in class WriteStream to support concise expressions for storing delimiters into such Streams. They are

character writing
cr Store the return character as the next element of the receiver.
crTab Store the return character and a single tab character as the next two elements of the receiver.
crTab: anInteger Store the return character as the next element of the receiver, followed by anInteger number of tab characters.
space Store the space character as the next element of the receiver.
tab Store the tab character as the next element of the receiver.
WriteStream instance protocol


Thus to construct the String

name city
bob New York
joe Chicago
bill Rochester


from two corresponding Arrays, 

names ←  #(bob joe bill)
cities ←  #('New York' 'Chicago' 'Rochester')


evaluate the expressions 

aStream ← WriteStream on: (String new: 16).
aStream nextPutAll: 'name'.
aStream tab.
aStream nextPutAll: 'city'.
aStream cr; cr.
names with: cities do:
    [ :name :city |
        aStream nextPutAll: name.
        aStream tab.
        aStream nextPutAll: city.
        aStream cr]


then the desired result is obtained by evaluating aStream contents.


Suppose a collection already exists and we wish to append further information into it by using Stream protocol. Class WriteStream supports instance creation protocol that accepts a collection and sets the position reference for writing to the end.

instance creation
with: aCollection Answer an instance of WriteStream accessing the argument, aCollection, but positioned to store the next element at the end of it.
with: aCollection from: firstIndex to: lastIndex Answer an instance of WriteStream accessing the subcollection of the argument, aCollection, from locaton firstIndex to iastIndex, but positioned to store the next element at the end of the subcollection.
WriteStream class protocol


Thus if a String referred to as header already existed, containing

name city


then the previous example String would be constructed by 

aStream ← WriteStream with: header.
names with: cities do:
    [ :name :city |
        aStream nextPutAll: name.
        aStream tab.
        aStream nextPutAll: city.
        aStream cr].
aStream contents


Class ReadWriteStream

Class ReadWriteStream is a subclass of WriteStream that represents an accessor that can both read and write elements into its collection. It supports all the protocol of both ReadStream and WriteStream, as given above.


Streams of Generated Elements

Of the three ways to create a position reference for streaming over a collection, the second way cited in the introduction to this chapter was to specify a seed by which the next elements of the collection can be generated. This kind of Stream only permits reading the elements, not writing. The reference, however, can be repositioned by resetting the seed.


Class Random, introduced in Chapter 8, is a subclass of Stream that determines its elements based on an algorithm employing a number as a seed. Random provides a concrete implementation for next and atEnd. Because the size of the collection is infinite, it never ends; moreover, Random can not respond to the message contents. It can respond to the message do:, but the method will never end without the programmer's purposeful intervention.


The following is an implementation of class Random; the reader is referred to Chapters 11 and 21 for examples making use of instances of the class. The implementations for do: and nextMatchFor: anObject are inherited from class Stream.

class name Random
superclass Stream
instance variable names seed
class methods 
instance creation
    new
        ↑self basicNew setSeed
instance methods 
testing
    atEnd
        ↑false

accessing
    next
        | temp |
        "Lehmer's linear congruential method with modulus m = 2 raisedTo:16, a = 27181 odd, and 5 = a \\ 8, c = 13849 odd, and c/m approximately 0.21132"
        [seed ← 13849 + (27181 * seed) bitAnd: 8r177777.
        temp ← seed / 65536.0.
        temp = 0] whileTrue.
        ↑temp

private
    setSeed
        "For pseudo-random seed, get a time from the system clock. It is a large positive integer; just use the lower 16 bits."
        seed ← Time millisecondClockValue bitAnd: 8r177777


Another possible example of a stream of generated elements are the probability distributions that are presented in Chapter 21. The superclass ProbabilityDistribution is implemented as a subclass of Stream. The message next: anInteger is inherited from Stream. Each kind of ProbabilityDistribution determines whether it is "read-only" and, if so, implements nextPut: as self shouldNotlmplement. Class SampleSpace, another example in Chapter 21, maintains a collection of data items and implements nextPut: anObject as adding to the collection.


Streams for Collections Without External Keys

The third way to maintain a position reference for streaming over a collection cited in the introduction to this chapter was to maintain a nonnumerical reference. This would be useful in cases where the elements of the collection cannot be accessed by external keys or where such access is not the most efficient means to retrieve an element.


Streaming over instances of class LinkedList provides an example in which the elements can be accessed by indexes as the external keys, but each such access requires a search down the chain of linked elements. It is more efficient to maintain a reference to a particular element in the collection (a kind of Link)and then to access the next element by requesting the current elements nextLink. Both reading and writing into the LinkedList can be supported by such a Stream.


Suppose we create a subclass of Stream that we call LinkedListStream. Each instance maintains a reference to a LinkedList and a position reference to an element in the collection. Since both reading and writing are supported, the messages next, nextPut:, atEnd, and contents must be implemented. (Note that these~four messages are defined in class Stream as self subclassResponsibility.) A new instance of LinkedListStream is created by sending it the message on: aLinkedList.

class name LinkedListStrea
superclass Stream
instance variable names collection
currentNode
class methods 
instance creation
    on: aLinkedList
        ↑self basicNew setOn: aLinkedList
instance methods 
testing
    atEnd
        ↑currentNode isNil

accessing
    next
        | saveCurrentNode |
        saveCurrentNode ← currentNode.
        self atEnd
            ifFalse: [currentNode ← currentNode nextLink].
        ↑saveCurrentNode
    nextPut: aLink
        | index previousLink |
        self atEnd ifTrue: [↑collection addLast: aLink].
        index ← collection indexOf: currentNode
        index = 1
            ifTrue: [collection addFirst: aLink]
            ifFalse: [previousLink ← collection at: index - 1.
                previousLink nextLink: aLink].
        aLink nextLink: currentNode nextLink.
        currentNode ← aLink nextLink.
        ↑aLink

private
    setOn: aLinkedList
        collection ← aLinkedList.
        currentNode ← aLinkedList first


Now suppose in order to demonstrate the use of this new kind of Stream we make up a kinkedList of nodes that are instances of class WordLink; class Wordkink is a subclass of Link that stores a String or a Symbol.

class name WordLink
superclass Link
instance variable names word
class methods 
instance creation
    for: aStinrg
        ↑self new word: aString
instance methods 
accessing
    word
        ↑word
    word: aString
        word ← aString

comparing
    = aWordLink
        ↑word = aWordLink world

printing
    printOn: aStream
        aStream nextPutAll: 'a WorldLink for'.
        aStream nextPutAll: word


From the above we can see that an instance of WordLink for the word #one is created by 

WordLink for: #one


Its print string is 

'a WordLink for one'


We can then create a LinkedList of WordLinks and then a LinkedListStream that accesses this LinkedList. 

list ← LinkedList new.
list add: (WordLink for: #one).
list add: (WordLink for: #two).
list add: (WordLink for: #three).
list add: (WordLink for: #four).
list add: (WordLink for: #five). 
accessor ← LinkedListStream on: list


Then an example sequence of messages to accessor is

expression result
accessor next a WordLink for one
accessor next a WordLink for two
accessor nextMatchFor:(WordLink for: #three) true
accessor nextPut:(WordLink for: #insert) a WordLink for insert
accessor contents LinkedList(a WordLink for one a WordLink for two a WordLink for three a WordLink for insert a WordLink for five)
accessor next a WordLink for five
accessor atEnd true


Similarly, traversing the nodes of a tree structure, such as that of class Tree given in Chapter 11, can be done by a kind of Stream that maintains a reference to a current node and then accesses the next element by accessing the current node's left tree, root, or right tree. This kind of Stream is slightly more complicated to implement than that for a kinkedkist because it is necessary to retain knowledge of whether the left or right tree has been traversed and back references to the father of the current node. The order of traversal of the tree structure can be implemented in the Stream, ignoring the method by which subtrees were added to the structure. Thus, although we used in-order traversal in the implementations of class Tree and class Node, we can stream over a Tree with postorder traversal by implementing the messages next and nextPut: appropriately.


External Streams and File Streams

The Streams we have examined so far make the assumption that the elements of the collection can be any objects, independent of representation. For communicating with input/output devices, such as a disk, however, this assumption is not valid. In these cases, the elements are stored as binary, byte-sized elements that may prefer to be accessed as numbers, strings, words (two bytes), or bytes. Thus we have a need to support a mixture of nonhomogeneous accessing messages for reading and writing these different-sized "chunks" of information.


Class ExternalStream is a subclass of class ReadWriteStream. Its purpose is to add the nonhomogeneous accessing protocol. This includes protocol for positioning as well as accessing.

nonhomogeneous accessing
nextNumber: n Answer the next n bytes of the collection accessed by the receiver as a positive Small-Integer or LargePositiveInteger.
nextNumber: n put: v Store the argument, v, which is a positive SmallInteger or LargePositiveInteger, as the next n bytes of the collection accessed by the receiver. If necessary, pad with zeros.
nextString Answer a String made up of the next elements of the collection accessed by the receiver.
nextStringPut: aString Store the argument, aString, in the collection accessed by the receiver.
nextWord Answer the next two bytes from the collection accessed by the receiver as an Integer.
nextWordPut: anInteger Store the argument, anInteger, as the next two bytes of the collection accessed by the receiver.
nonhomogeneous positioning
padTo: bsize Skip to the next boundary of bsize characters, and answer how many characters were skipped.
padTo: bsize put: aCharacter Skip--writing the argument, aCharacter,into the collection accessed by the receiver in order to pad the collection--to the next boundary of bsize characters and answer how many characters were written (padded).
padToNextWord Make the position reference even (on word boundary), answering the padding character, if any.
padToNextWordPut: aCharacter Make the position reference even (on word boundary), writing the padding character, aCharacter, if necessary.
skipWords: nWords Position after nWords number of words.
wordPosition Answer the current position in words.
wordPosition: wp Set the current position in words to be the argument, wp.
ExternalStream instance protocol


Class FileStream is a subclass of ExternaiStream. All accesses to external files are done using an instance of FileStream. A FileStream acts as though it were accessing a large sequence of bytes or characters; the elements of the sequence are assumed to be Integers or Characters. The protocol for a FileStream is essentially that of class ExternalStream and its superclasses. In addition, protocol is provided to set and to test the status of the sequence the FileStream is streaming over.


Classes ExternalStream and FileStream are provided in the Smalltalk-80 system as the framework in which a file system can be created. Additional protocol in class FileStrearn assumes that a file system is based on a framework consisting of a directory or dictionary of files, where a file is a sequence of file pages. The Smalltalk-80 system includes classes FileDirectory, File, and FilePage to represent these structural parts of a file system. A FilePage is a record of data that is uniquely identified within its File by a page number. A File is uniquely identified both by an alphanumeric name and a serial number; it maintains a reference to the FileDirectory which contains the File. And the FileDirectory is itself uniquely identified by the device or reserver" to which it refers. User programs typically do not access a File or its FilePages directly; rather they access it as a sequence of characters or bytes through a FileStream. Thus the programmer can create a FileStream as an accessor to a file using an expression of the form 

Disk file: 'name.smalltalk'


where Disk is an instance of a FileDirectory. The FileStream can then be sent sequences of reading and writing messages as specified in the protocol of this chapter.


Notes

Retrieved from "https://trans.onionmixer.net/mediawiki/index.php?title=Smalltalk80LanguageImplementation:Chapter_12&oldid=4774"