CSC 153 | Grinnell College | Spring, 2005 |
Computer Science Fundamentals | ||
Laboratory Exercise | ||
This laboratory exercise 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.
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") ) ) ) ) ) )
With this directory
definition, 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))))
(math-dir 'show) (math-dir 'lookup "John Stone") (math-dir 'lookup "George Apostle") (math-dir 'add "Chris Hill" 4556) (math-dir 'show)In each case, describe the results of the operation.
Similarly, we might create an initialized physics directory as follows:
(define physics-dir (directory '(("Robert Cadmus" 3016) ("William Case" 3014) ("Mark Schneider" 3018) ("Paul Tjossem" 4289))))
physics-dir
.
physics-dir
were created without initial
data? For example, what happens with
(define physics-dir (directory)) (physics-dir 'show)
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.
directory
class does no error checking of any
parameters -- this class only checks if the requested operation is not
valid. Add appropriate error checking to the add-name,
look-up
and show
procedures.
The given directory
class only allows initialization,
addition of a name, lookup of an entry by name, and printing of the full
directory. The original problem, however, specified some additional
operations as well.
directory
class, which allows
a user to remove an entry from the directory, based on the name field.
This document is available on the World Wide Web as
http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-adt.shtml
created March 26, 1998 last revised February 2, 2005 |
![]() ![]() |
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. |