Introduction to Abstract Data Types

Goals

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.

Departmental Telephone Directories

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))))

1. After copying the above definitions into Scheme, check how this ADT can be used through the following commands:

   (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))))

2. Explain how this definition allows users to request operations to physics-dir.

3. What would happen if physics-dir were created without initial data? For example, what happens with

   (define physics-dir (directory))
   (physics-dir 'show)
   

Jargon

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.

4. Explain why the test cases above (in step 1) produce the output you observed.

5. As shown, the 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.

6. Add a "delete" operation to the directory class, which allows a user to remove an entry from the directory, based on the name field.

7. Add a "change" operation which allows a user to correct the entry of an entry, given name in the current directory entry.

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.