7. Programming Methodology ( Terminal Session on this Machine )

Programming methodology deals with the analysis, design and implementation of programs. One important methodology involves what is referred to as a "top-down" approach to analysis, design and implementation.

7.1 Top-down Design

This method involves a hierarchical or tree-like structure for a system as illustrated by the following diagram:

At the top level, we have that part of the system which deals with the overall system; a sort of system overview.

7.2 An Interactive System

For example, if the system is an interactive system, this top level program will be the part of the system which ties together the key system components. One of these components might be the part of the system which reads a command; another component might evaluate the command just entered. Still another component might be the part of the system which displays the results of executing the command just entered. The overall structure of such a system is shown from the top down in the following diagram:

7.3 A Simple Interactive Data Base System

We wish to design and implement a simple data base system which allows commands to be entered interactively and results to be displayed.

We will attempt to illustrate this top-down methodology with an example. As with all of the topics covered so far in this course, we will model this system using the Scheme programming notation. One might actually use some language other than Scheme (such as C) to implement a database system. However, the approach we use is valid since one might use Scheme to implement a prototype system and then use the C programming language for the production system. This is an illustration of an important technique known as software prototyping. Just as an engineer always builds at least one prototype machine before giving the go-ahead to begin production of the machine, software engineers should also use this same technique. Scheme is a particularly good language for prototyping as we shall soon see.

Since most Scheme systems are already interactive systems, we can simplify our prototype design by using the Scheme top-level as our prototype's top-level.

Similarly, we can use the Scheme syntax for our commands. This means that we can use the Scheme system's read-eval-print loop (the second level in our system diagram) as our prototype's second level and third level. It should now begin to be obvious why Scheme is a good prototyping language for interactive systems. We are already down to the fourth level of our design and we have yet to begin to design or implement any programs!

Another aspect of this design method of building a system from the top down in distinct layers is that it is possible (and desirable) to attempt to make each layer of software independent from the layers above and below it. This involves design of some sort of abstract interface between the layers.

The most important benefit of design layers is that it should then be possible to change the software in one layer (provided the new version of that layer adhears to the same interface above and below) without having to change any other part of the software design.

This is a lofty design goal. In practice, it is often very difficult to achieve.

7.3.1 Design Definitions

A database will consist of a collection of records. Each record is a collection of related items. Each record will have a key field which we will use as an identifier of that record. Since we are implementing our prototype in Scheme we will use a list as our data structure for the database. Each record, itself, will be a list. The key field will be the first item of each record and will often (but not necessarily) be a symbol. The remaining items in each record may be any valid Scheme objects. Following is an example database (admittedly small) containing some information on people.

(define people
'(
   (howland (john (professor (computer (science)))))
   (howland (glynne (nail (manufacturer))))
   (clinton (bill (president (USA))))
   (clinton (hillary (First-lady (USA))))
   (perot (ross (former (presidential (candidate)))))))

Following is a function which will lookup up a key in a database.

7.3.2 lookup a key in a database.

(define lookup
  (lambda (key datalist)
    (if (null? datalist)
      '()
      (if (equal? key (caar datalist))
        (cdar datalist)
        (lookup key (cdr datalist))))))
(lookup 'clinton people) ==>((bill (president (usa))))

7.3.3 Exercise

What is the order of the lookup algorithm?

lookup just finds the first match in the database. Most databases of any size will have multiple matches for a given key. Following is a function which will lookup all matches of a given key.

7.3.4 lookup-all

(define lookup-all
  (lambda (key datalist)
    (if (null? datalist)
      '()
       (if (equal? key (caar datalist))
         (cons (cadar datalist)
               (lookup-all key (cdr datalist)))
         (lookup-all key (cdr datalist))))))
(lookup-all 'clinton people) ==>
((bill (president (usa))) (hillary (first-lady (usa))))

7.3.5 Exercise

What is the order of the lookup-all function?

Notice that by the way we have constructed the data associated with each key in the people database, that the result of using lookup-all is to produce a new database which might be used as the database for a lookup operation.

(lookup 'hillary (lookup-all 'clinton people)) ==>
((first-lady (usa)))

(lookup 'bill (lookup-all 'clinton people)) ==>
((president (usa)))

Next we consider the problem of adding items to an existing database. The result of this operation is a new database. Hence to actually add an item to an existing database we need to re-define the existing database to be the result of add-data.

7.3.6 add-data Function

; A function to add an item to a database.
; To actually change datalist we must use
; define as in the following:
; (define db (add-data '(smith (jim (broker))) db))

(define add-data
  (lambda (item-pair datalist)
    (cons item-pair datalist)))

(add-data '(konstam (aaron (professor))) people) ==>
((konstam (aaron (professor)))
(howland (john (professor (computer (science)))))
(howland (glynne (nail (manufacturer))))
(clinton (bill (president (usa))))
(clinton (hillary (first-lady (usa))))
(perot (ross (former (presidential (candidate))))))

To actually change the people database we must:

(define people
  (add-data '(konstam (aaron (professor))) people))
people ==>
((konstam (aaron (professor)))
(howland (john (professor (computer (science)))))
(howland (glynne (nail (manufacturer))))
(clinton (bill (president (usa))))
(clinton (hillary (first-lady (usa))))
(perot (ross (former (presidential (candidate))))))

We now address the problem of removing items from a database. As in the previous database operations we form a new database which is a copy of the old database less the item being removed.

7.3.7 remove-data Function

; A function to remove the first item matching
; key from a database.
; To actually change the database we must
; use define as above.

(define remove-data
  (lambda (key datalist)
    (if (null? datalist)
    '()
    (if (eq? key (caar datalist))
      (cdr datalist)
    (cons (car datalist)
          (remove-data key (cdr datalist)))))))

(remove-data 'howland people) ==>
((howland (glynne (nail (manufacturer))))
(clinton (bill (president (usa))))
(clinton (hillary (first-lady (usa))))
(perot (ross (former (presidential (candidate))))))

people ==>
((howland (john (professor (computer (science)))))
(howland (glynne (nail (manufacturer))))
(clinton (bill (president (usa))))
(clinton (hillary (first-lady (usa))))
(perot (ross (former (presidential (candidate))))))

7.3.8 Exercise

What is the order of the remove-data function?

We need to be able to remove all items matching a given key.

7.3.9 remove-all-data Function

; A function to remove all items matching
; key from a database.
; To actually change the database we must
; use define as above.

(define remove-all-data
  (lambda (key datalist)
    (if (null? datalist)
    '()
    (if (eq? key (caar datalist))
      (remove-all-data key (cdr datalist))
    (cons (car datalist)
          (remove-all-data key (cdr datalist)))))))

(remove-all-data 'howland people) ==>
(clinton (bill (president (usa))))
(clinton (hillary (first-lady (usa))))
(perot (ross (former (presidential (candidate))))))

Since we did not redefine people, the original people database is unchanged.

people ==>
((howland (john (professor (computer (science)))))
(howland (glynne (nail (manufacturer))))
(clinton (bill (president (usa))))
(clinton (hillary (first-lady (usa))))
(perot (ross (former (presidential (candidate))))))

7.3.10 Exercise

What is the order of the remove-all-data function?

7.3.11 Generalizing Software Constructions

You have probably noticed that so far, each database operation requires two arguments. The first is a key and the second is the database to which the operation is applied. This was a concious design choice which gives additional flexibility to the database operations. They do not have to be tied to a specific database. It is possible to consider a higher order function which constructs functions as results. If we start with an operation and a database, such a function might build a function with takes only a key as an argument and remembers which operation to perform and which database to perform it on. This function constructor is a general purpose tool which can be used to bind the more general database operations to a specific database. This is an example of software which can be used to automatically construct other useful programs.

Here is the database-operation-maker.

(define database-operation-maker
  (lambda (operation database)
    (lambda (key)
      (operation key database))))

7.3.12 Specializing Operations to the People Database

We can use this function to make a people-looker function which does a lookup in the people database.

(define people-looker
  (database-operation-maker lookup people))

Similarly we can define:

(define people-all-looker
  (database-operation-maker lookup-all people))
(people-looker 'howland) ==>
((john (professor (computer (science)))))
(people-all-looker 'howland) ==>
((john (professor (computer (science)))) (glynne (nail (manufacturer))))

Next we consider the problem of more permenant storage of our database in a filesystem. As it stands now, our database is stored as a Scheme list in the main memory of our computer. It is vulnerable to loss if the power to the computer goes down for example.

We need two utility functions for storing and retrieving Scheme objects as files.

7.3.13 Reading and Writing Files

; A function to write a lisp list to a file.
(define write-to-file
  (lambda (filename obj)
    (let ((port (open-output-file filename)))
      (write obj port)
      (close-output-port port))))

7.3.14 Example

(write-to-file "test" '((a b) c d)))
; A function to read a lisp list from a file.
(define read-from-file
  (lambda (filename)
    (car
      (let ((port (open-input-file filename)))
        (let f ((value (read port)))
          (if (eof-object? value)
            (begin
              (close-input-port port)
              '())
            (cons value (f (read port)))))))))

7.3.15 Example

(read-from-file "test") ==> ((a b) c d))

Suppose we have the following database file

(read-from-file "people") ==>
((konstam (patricia (editor (newspaper))))
 (konstam (aaron (professor (computer (science)))))
 (eggen (maury (professor (computer (science)))))
 (howland (john (professor (computer (science)))))
 (howland (glynne (nail (manufacturer))))
 (clinton (bill (president (usa))))
 (clinton (hillary (first-lady (usa))))
 (perot (ross (former (presidential (candidate))))))

7.3.16 lookup-file Function

Then, we can define a function which will lookup a key item in this database.

; A function to lookup the first item matching
; key from a database stored as a file.
(define lookup-file
  (lambda (key filename)
    (lookup key (read-from-file filename))))

7.3.17 Example

(lookup-file 'eggen "people") ==>
((maury (professor (computer (science)))))

7.3.18 lookup-all-file Function

As before, we can define a function which will lookup all items in a database which match a given key.

; A function to lookup all items matching
; key from a database stored as a file.
(define lookup-all-file
  (lambda (key filename)
    (lookup-all key (read-from-file filename))))

7.3.19 Example

(lookup-all-file 'clinton "people") ==>
((bill (president (usa)))
 (hillary (first-lady (usa))))

7.3.20 add-data-file Function

Next we consider the problem of adding items to a database which is stored as a file.

; A function to add data to a database stored
; as a file.
(define add-data-file
  (lambda (item-pair filename)
    (write-to-file filename
       (add-data item-pair
             (read-from-file filename)))))

7.3.21 Example

(add-data-file
  '(pitts (gerald (professor (computer (science)))))
  "people")

Then

(read-from-file "people") ==>
((pitts (gerald (professor (computer (science)))))
 (konstam (patricia (editor (newspaper))))
 (konstam (aaron (professor (computer (science)))))
 (eggen (maury (professor (computer (science)))))
 (howland (john (professor (computer (science)))))
 (howland (glynne (nail (manufacturer))))
 (clinton (bill (president (usa))))
 (clinton (hillary (first-lady (usa))))
 (perot (ross (former (presidential (candidate))))))

7.3.22 database-file-operation-maker Function

As above, we can bind a database filename to a database operation with a database-file-operation-maker as follows:

(define database-file-operation-maker
  (lambda (operation filename)
    (lambda (key)
      (operation
         key
         (read-from-file filename)))))

7.3.23 people-file-looker Function

Then we can define:

(define people-file-looker
  (database-file-operation-maker
    lookup
    "people"))

7.3.24 Example

(people-file-looker 'howland) ==>
((john (professor (computer (science)))))

Other people-file database operations are easily defined. Such functions are left as an exercise for the reader.