Re: Good Design Strategies <Was comments on comments>

[rjh@cs.purdue.EDU (Bob Hathaway)]

In article <2542@goofy.megatest.UUCP>, djones@megatest.UUCP (Dave Jones) writes:
>...My assertion -- must I repeat it again? --
>is that good modules are more likely to come from a bottom-up approach.

Ok, I'll admit you've made a good point although I still think starting at
the top is the natural way to design systems (and algorithms).

>> By breaking the system into smaller pieces with each
>> piece providing some well defined and more manageable part of the system,
>> the components should emerge.
>>
>Components might emerge. But how they emerge may be dictated by the
>...

Ok, how about a quick example starting at top level.  When designing
a "Classical" compiler/interpreter front-end, I know the structure will
consist of a scanner to read input and a parser to read the grammar.  
I'll assume the parser functions return an intermediate code Adt for
triviality.  Now, I know I'll need a symbol table for identifiers and
reserved words and a token type to return to the parser, and we have:

|-------|       |------|     |------------|
|scanner|------>|parser|---->|intermediate|
|-------|       |------|     |    code    |
      \          /           |------------|
       \        /
        |-------|
        |symbol |
	|table  |
        |-------|

Their are four top-level modules immediately identified.  
1. Symbol Table 
    Provides a symbol_table_entry Adt (encapsulates a type).
    <Description>
    Operations
	a. lookup/insert
	   <Description>
	...
2. Scanner 
    Provides TokenType Adt (encapsulates a type).
    <Description>
    Operations
	a. Next_Token
	   <Description>
	b. Match_Token
	   <Description>
	...
3. Intermediate Code
    Provides Intermediate_Code Adt (encapsulates a type)
    <Description>
    Operations
	a. Make_Node
	   <Description>
	b. Make_Child
	   <Description>
	...
4. Parser
    Parses input (encapsulates functionally related subprograms).
    <Description>
    Operations
	a. Statement
		Returns an intermediate code representation of the 
		parsed statement...
	b. Parse
		Go for the whole thing:-)
	...

Thus, a modular design with Adts.  The design can proceed by identifying
the return values and parameters to operations and possibly some high level
pseudo code to insure the problem is well understood and all parts of the
system will work together as expected.  To begin the implementation we 
analyze the dependencies, almost always the Adts come last.
Dependencies
  parser:  	scanner, symbol table, intermediate code, 
  scanner: 	symbol table
  symbol table:	 nothing
  intermediate code: nothing
We can begin implementation with the intermediate code and symbol table
because we know what they need to provide and how they fit into the system
and because they don't depend on unwritten code.  Yes, the token, 
symbol table, and intermediate code Adts won't change much and
are good candidates for reuse; I wouldn't expect to add more than one
or two operations and change more than a few parameters for each Adt
above after the initial design is complete.  Each module provides a
well defined interface and encapsulates either a type (Adt) or a
set of functionally related subprograms (the parser).  After the top level
design is complete we can turn to the internal design of the Adts.
For example the intermediate code Adt may be complex requiring recursive
application of the above technique, i.e. top down.  So, a generic tree
Adt from a library can be used, and so on, nothing special purpose.
The parser functions can be designed top-down and implemented bottom-up,
so we'll know what gramatical constructs are necessary from the top and
get there fastest from the bottom (the preferred implementation technique
for parsers).  Efficiency considerations can come later *if* the system
doesn't meet its timing constraints, good design comes first.  We wouldn't
know where to optimize until profiling anyway.

Classification:
Object Oriented (design & implementation)
    Yes: objects identified, 2nd level design and coding begins with 
	 objects (data structures).
    No : no inheritance.
Top-Down (design)
    Yes: Top-down design is used within modules, especially in the parser.
    No : Structure charts were possible, but modules provided the best high
	 level view of the system.
Bottom-up (implementation)
    Yes: started with the lowest level Adt.  Generic linked lists, tree adts,
	 etc., would be used to implement the Adts from the bottom up.
What I call this mess:
    Modular design with abstract data types, top-down design within modules.
Reuse:
    All software tools and components are conceivably replaceable 
    and reusable.

>... Which method is best depends on the job at hand. ...

I agree, the above technique was chosen after carefully considering the 
problem and I have found it suitable for most, if not all applications.
Direct encoding of the design and implementation is possible in Ada
and to my understanding this is the preferred application of Ada's 
methodology.  Flamage and comments are welcome.  In view of the recent
object-oriented discussions, can anyone comment on how inheritance,
dynamic binding, or any other object oriented techniques fit into or
could improve the above scheme?  I'll be disappointed if the modular 
technique with Adts is the only one provided:-)

Bob Hathaway
rjh@purdue.edu