|CSC 153||Grinnell College||Spring, 2005|
|Computer Science Fundamentals|
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") ) ) ) ) ) )
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-dirwere 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.
directoryclass does no error checking of any parameters -- this class only checks if the requested operation is not valid. Add appropriate error checking to the
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.
directoryclass, 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
created March 26, 1998
last revised February 2, 2005
|For more information, please contact Henry M. Walker at firstname.lastname@example.org.|