7. Programming Methodology

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

Top-down-design starts with an description of the overall system and usually consists of a hierarchical structure which contains more detailed descriptions of the system at each lower level. The lower level design details continue until further subdivision is no longer possible, i.e., until the system is described in terms of its "atomic" parts.

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 kind of system overview or main top-level module.

An alternate design metholodogy, Bottom-up design, starts with description of the lowest level system components together with description of how such components are assembled to form higher level system components. This design methodology continues until all levels of the system are connected in a hierarchical structure to form the entire system.

Top-down design is preferred because, at the beginning of an analysis and design cycle, it is usually not possible to know the lower level design details which are determined by a process of successive refinement.

7.2 An Interactive System

As an example of top-down design, consider the design of an interactive system. The 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 J programming notation. One might actually use some language other than J (such as Scheme or C) to implement a database system. However, the approach we use is valid since one might use J to implement a prototype system and then use the C programming language for the production system. This is an example 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, many software engineers also use this same technique. J is a particularly good language for prototyping as we shall soon see.

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

Similarly, we can use the J syntax for our data base command language. This means that we can use the J 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 J 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

We define a database to be 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 J 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 always) be a character list. The remaining items in each record may be any valid J object. Following is an example database (admittedly small) containing some information on people.


people =: ('howland' ; 'jack' ; 'computer science professor') ; ('clinton' ; 'bill' ; 'president usa') ; ('clinton' ; 'hillary' ; 'president usa') ; ('perot' ; 'ross' ; 'wanted to be president') ; < ('bush' ; 'george' ; 'used to be president')

Following is a function which will lookup up a key in a database. In the following definitions, we use the primitive J spelling for the words:


box =: <
append =: ,
link =: ;

In section 6.6.1 we defined a predicate, nullp, for empty lists as:


nullp =: (0 bond =) atop tally

which we also use below.

7.3.2 lookup a key in a database.


lookup =: monad define
('name' ; 'database') =. y.
if. nullp database
  do. ''
  else. if. name match head head database
          do. head database
          else. lookup name ; < rest database
        end.
end.
)

   lookup 'clinton';<people
+-------+----+-------------+
|clinton|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


lookup_all =: monad define
('key' ; 'datalist') =. y.
  if. nullp datalist
    do. ''
    else. if. key match head head datalist
          do. (< rest head datalist) , lookup_all key ; < rest datalist
          else. lookup_all key ; < rest datalist
          end.
end.
)

   lookup_all 'clinton' ; < people
+--------------------+-----------------------+
|+----+-------------+|+-------+-------------+|
||bill|president usa|||hillary|president 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 ==>
+-------+-------------+
|hillary|president usa|
+-------+-------------+

   lookup 'bill'; < lookup_all 'clinton' ; < people ==>
+----+-------------+
|bill|president usa|
+----+-------------+

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

7.3.6 add_data Function


add_data =: monad define
('item_pair' ; 'datalist') =. y.
  (< item_pair) , datalist
)

To examine the add_data operation note:

    
   people =: add_data ('howland';'glynne';'nail manufacturer');<people

   0 from people ==>
+----------------------------------+
|+-------+------+-----------------+|
||howland|glynne|nail manufacturer||
|+-------+------+-----------------+|
+----------------------------------+

   lookup_all 'howland' ; < people ==>
+--------------------------+---------------------------------+
|+------+-----------------+|+----+--------------------------+|
||glynne|nail manufacturer|||jack|computer science professor||
|+------+-----------------+|+----+--------------------------+|
+--------------------------+---------------------------------+

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


remove_data =: monad define
('key' ; 'datalist') =. y.
  if. nullp datalist
    do. ''
    else. if. key match head head datalist
            do. rest datalist
            else. (< head datalist) , remove_data key ; < rest datalist
          end.
end.
)

To examine the remove_data operation try:


   people =: remove_data 'howland' ; <people
   lookup_all 'howland';<people ==>
+---------------------------------+
|+----+--------------------------+|
||jack|computer science professor||
|+----+--------------------------+|
+---------------------------------+

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


remove_all_data =: monad define
('key' ; 'datalist') =. y.
  if. nullp datalist
    do. ''
    else. if. key match head head datalist
      do. remove_all_data key ; < rest datalist
      else. (< head datalist) , remove_all_data key ; < rest datalist
          end.
end.
)

To examine the operation of remove_all_data, recall that


   shape people ==>
5
   lookup_all 'clinton';<people ==>
+--------------------+-----------------------+
|+----+-------------+|+-------+-------------+|
||bill|president usa|||hillary|president usa||
|+----+-------------+|+-------+-------------+|
+--------------------+-----------------------+
   people =: remove_all_data 'clinton' ; < people
   lookup_all 'clinton' ; < people ==>

Note that there are no longer any 'clinton' keys in the people database.


   shape people ==>
3
   0 from people ==>
+-----------------------------------------+
|+-------+----+--------------------------+|
||howland|jack|computer science professor||
|+-------+----+--------------------------+|
+-----------------------------------------+
   1 from people ==>
+-----------------------------------+
|+-----+----+----------------------+|
||perot|ross|wanted to be president||
|+-----+----+----------------------+|
+-----------------------------------+
   2 from people ==>
+----------------------------------+
|+----+------+--------------------+|
||bush|george|used to be president||
|+----+------+--------------------+|
+----------------------------------+

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. These operations are more general because they are not tied to a specific database; they may be used with any appropriately structured database.

7.3.12 Specializing Operations to the people Database

We can define a people_looker function which does a lookup in the people database as:


people_lookup =: monad def 'lookup y. ; < people'

Similarly we can define:


people_all_looker =: monad def 'lookup_all y. ; < people'

The behavior of these specialized operations is examined in the following expressions.


   people_lookup'bush' ==>
+----+------+--------------------+
|bush|george|used to be president|
+----+------+--------------------+
   people_lookup'clinton' ==>

   people_all_looker 'howland' ==>
+---------------------------------+
|+----+--------------------------+|
||jack|computer science professor||
|+----+--------------------------+|
+---------------------------------+

7.3.13 Reading and Writing Files

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

There are four utility verbs which are needed to construct two verbs, write_list and read_list which will allow J lists to be permenantly saved as files. Two of the four utility verbs (read and write) will not be fully explained at this time. We will still be able to make effective use of read and write even though we may not fully understand their J definitions. Their definitions are:


read =: monad def '1 !: 1 < y.'
write =: dyad def 'x. 1 !: 2  < y.'

J objects are stored in files as strings of characters. The dyad write requires a character list for its left input and a quoted filename for its right input; the character list is written to the indicated file. For example,


   'Hi there' write 'junk'

creates a file named junk containing the characters 'Hi there'. A file may only contain characters as data. The monad read requires a quoted filename as its right input; the indicated file is read into the J environment. For example:


   read 'junk' ==>
Hi there

J lists may consist of arbitrary J items (numbers of various types, characters, functions, etc.). To write and read J lists to and from files it is necessary to convert these lists to and from character strings. Two utilities are available to do this, however, it should be noted that files created this way on one type of computer system (Unix) may not be readable on another type of computer system (Intel architecture). The utility functions are:


to_char =: 3 !: 1
to_internal =: 3 !: 2

These verbs are used to define the following verbs which may be used to store and retrieve J objects (including lists) as files.


write_list =. dyad def '(to_char x.) write y.'
read_list =. monad def 'to_internal read y.'

7.3.14 Example

We can save the people database as a file named people.database by writing:


people write_list 'people.database'

7.3.15 Example

We can read the people.database file back into the J environment and verify that it is the same as the original copy of people in the J environment by entering the sentence:


people match read_list 'people.database' ==>
1

Suppose we have the following database file, people.db such that:


   open read_list 'people.db' ==>
+-------+--------+--------------------------+
|konstam|patricia|newspaper writer          |
+-------+--------+--------------------------+
|konstam|aaron   |computer science professor|
+-------+--------+--------------------------+
|eggen  |maury   |computer science professor|
+-------+--------+--------------------------+
|howland|jack    |computer science professor|
+-------+--------+--------------------------+
|howland|glynne  |nail manufacturer         |
+-------+--------+--------------------------+
|clinton|bill    |president usa             |
+-------+--------+--------------------------+
|clinton|hillary |first lady usa            |
+-------+--------+--------------------------+
|perot  |ross    |wanted to be president    |
+-------+--------+--------------------------+
|bush   |george  |used to be president      |
+-------+--------+--------------------------+

7.3.16 lookup_file Function

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


lookup_file =: monad define
('key' ; 'filename') =. y.
lookup key ; < read_list filename
)

7.3.17 Example


   lookup_file 'eggen' ; 'people.db' ==>
+-----+-----+--------------------------+
|eggen|maury|computer science professor|
+-----+-----+--------------------------+

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.


lookup_all_file =: monad define
('key' ; 'filename') =. y.
lookup_all key ; < read_list filename
)

7.3.19 Example


   lookup_all_file 'clinton' ; 'people.db' ==>
+--------------------+------------------------+
|+----+-------------+|+-------+--------------+|
||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.


add_data_file =: monad define
('item_pair' ; 'filename') =. y.
(add_data item_pair ; < read_list filename) write_list filename
)

7.3.21 Example

To illustrate the use of add_data_file, try the sentence:

 
   tally read_list 'people.db' ==>
9
   add_data_file ('pitts';'gerald';'computer science professor');'people.db'
   tally read_list 'people.db' ==>
10
   open read_list 'people.db' ==>
+-------+--------+--------------------------+
|pitts  |gerald  |computer science professor|
+-------+--------+--------------------------+
|konstam|patricia|newspaper writer          |
+-------+--------+--------------------------+
|konstam|aaron   |computer science professor|
+-------+--------+--------------------------+
|eggen  |maury   |computer science professor|
+-------+--------+--------------------------+
|howland|jack    |computer science professor|
+-------+--------+--------------------------+
|howland|glynne  |nail manufacturer         |
+-------+--------+--------------------------+
|clinton|bill    |president usa             |
+-------+--------+--------------------------+
|clinton|hillary |first lady usa            |
+-------+--------+--------------------------+
|perot  |ross    |wanted to be president    |
+-------+--------+--------------------------+
|bush   |george  |used to be president      |
+-------+--------+--------------------------+

7.3.22 Specializing Operations to the people.db File

As above, we can bind a database filename to a database operation so that we need only give a key when we want to search a particular database file.

7.3.23 people_file_looker Function


people_file_looker =: monad def 'lookup_file y. ; ''people.db'''

Notice that this definition has the special problem of requiring that a single quote appear inside a quoted definition. The way this is accomplished is to represent a single ' by ''.

7.3.24 Example


   people_file_looker 'howland' ==>
+-------+----+--------------------------+
|howland|jack|computer science professor|
+-------+----+--------------------------+

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

7.4 Summary

We have shown that it is possible to build a simple working prototype for an interactive database system which may be used to store and retrieve information permenantly in files.