last revised February 3, 2005
| CSC 153: Computer Science Fundamentals | Grinnell College | Spring, 2005 |
| Laboratory Exercise Reading | ||
This reading provides motivation for and a simple implementation of abstract data types. In subsequent labs, the concept of abstract data types will lead to an alternative approach to problem solving, called object-oriented programming.
On-line telephone directories are to be created for several departments. For each directory, one should be able to add names, delete names, correct a telephone number, look up an entry by name, and print the full directory.
A natural data structure for a directory would be an association list. Data for each individual would be stored as a (name, number) pair, and these pairs would be stored together on a list.
Writing code will be simplified significantly if we can be sure that data will be in an association list. Over time, however, additional code may be written, or other applications may be run in the same environment used for a directory. In such circumstances, we may want to ensure that other code will not change the structure of an association list.
In computer science, one approach to help guarantee that data structures will not be altered by other applications or code is to encapsulate the data and restrict what programs can access that data. This perspective motivates the concept of an abstract data type.
An abstract data type or ADT consists of a collection of data together with operations on that data. Further, the data and operations are packaged together, in such a way that only the specified operations may have direct access to the data. Other programs must use the specified ADT operations whenever those programs want to retrieve, store, or modify data within the ADT.
Within Scheme, the definition for a (very simple) telephone directory might be as follows:
(define directory
(lambda init-list
(let ((assoc-list ;; the ADT's data
(if (null? init-list)
'()
(car init-list))))
(letrec ;; the ADT's operations
((add-name ;; add names to directory
(lambda (name-entry)
(set! assoc-list (cons name-entry assoc-list))))
(look-up ;; find a name in the directory
(lambda (name)
(assoc name assoc-list)))
(show ;; show current state of directory
(lambda ()
assoc-list))
) ;; end of local definitions
(lambda (op . parameters)
(case op ;; process external requests
((add) (add-name parameters))
((lookup) (look-up (car parameters)))
((show) (show))
(else "unknown operation")
)
)
)
)
)
)
Before considering this directory definition in detail, we
review how such a definition could be used. The following declaration
creates a directory for some Mathematics/Computer Science faculty:
(define math-dir
(directory '(("Arnold Adelberg" 4201) ("Marc Chamberland" 4207)
("Christopher French" 4661) ("Benjamin Gum" 3127)
("Eugene Herman" 4202) ("Charles Jepsen" 4203)
("Keri Kornelson" 4661) ("Shonda Kuiper" 3806)
("Emily Moore" 4205) ("Thomas Moore" 4206)
("Samuel Rebelsky" 4410) ("David Romano" 3309)
("Karen Shuman" 4927) ("Nikolay Silkin" 4880)
("John Stone" 3181) ("Henry Walker" 4208)
("Royce Wolf" 4209))))
With these definitions, this ADT may be used though various commands:
(math-dir 'lookup "John Stone")
==> ("John Stone" 3181)
(math-dir 'lookup "Karen Thomson")
==> ()
(math-dir 'add "Karen Thomson" 3169)
(math-dir 'show)
==> (("Karen Thomson" 3169) ("Arnold Adelberg" 4201)
("Marc Chamberland" 4207) ("Christopher French" 4661)
("Benjamin Gum" 3127) ("Eugene Herman" 4202)
("Charles Jepsen" 4203) ("Keri Kornelson" 4661)
("Shonda Kuiper" 3806) ("Emily Moore" 4205)
("Thomas Moore" 4206) ("Samuel Rebelsky" 4410)
("David Romano" 3309) ("Karen Shuman" 4927)
("Nikolay Silkin" 4880) ("John Stone" 3181)
("Henry Walker" 4208) ("Royce Wolf" 4209))
We now examine the ADT structure and usage in more detail. In summary, ADTs may be implemented in Scheme using the following general structure:
(define ADT-name
(lambda initialization
(let ((local variables and data structures, using initialization))
(letrec ((definition of ADT operations))
(lambda (op . parameters)
(case op
(collection of operation names and calls to ADT operations)
)
)
)
)
)
)
An ADT is a template for storing data and processing requests. The initial lambda expression indicates the ADT will produce an logical data/operations entity when called. To allow an ADT to be initialized (e.g., with directory data), the main lambda expression has an optional parameter.
The structure specifies local variables (e.g., an association list) in the
opening let statement. Since the variables are declared
locally, data within the ADT cannot be accessed directly by outside code.
This guarantees that access to ADT data must be accessed through the
specified ADT operations.
Details of various operations are given within a letrec
statement. Again, such operations are defined within the ADT, so they
cannot be called or changed by outside. However, since the
letrec is nested within the let, these local
operations can access the ADT's local data directly.
Since a user will request various operations, an ADT involves a lambda
expression which returns results for each request. More specifically, a
user will specify an operation op when using the ADT, and this
operation may involve parameters. The ADT uses a case
statement to determine which operation is being requested and to respond
appropriately -- using the locally defined procedures as needed.
With this general definition of an ADT, we create specific variables for
individual instances of the ADT. In addition to the math-dir
above, for example, we could define a physics directory as follows:
(define physics-dir
(directory '(("Robert Cadmus" 3016)
("William Case" 3014)
("Mark Schneider" 3018)
("Paul Tjossem" 4289))))
This definition uses the directory to create an initialized
physics directory (the directory procedure is run with an
appropriate association list of data, returning an ADT structure).
In object-oriented programming, and ADT is called a class, and an individual instance of an ADT (e.g., math-dir or physics-dir) is called an object. To use an established object, we identify the object, the desired operation, and any required data.
This document is available on the World Wide Web as
http://www.walker.cs.grinnell.edu/courses/153.sp05/readings/reading-adt.shtml
|
created March 26, 1998 last revised February 3, 2005 |
|
| For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. |