Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Tools

Executable Specifications with Prolog


OCT89: EXECUTABLE SPECIFICATIONS WITH PROLOG

EXECUTABLE SPECIFICATIONS WITH PROLOG

Prolog's dual nature takes you from design to implementation

Gregory L. Lazarev

Gregory Lazarev is the president of Applied Logic Programming, Inc. and can be reached at 262 Tomkenn Rd., Philadelphia, PA 19151.


The Prolog language is the best known example of a Logic Programming implementation, with the uniqueness that it can be viewed declaratively as well as procedurally. Therefore, Prolog may provide an attractive tool in software engineering, particularly in the areas of "executable" specifications and rapid prototyping (Davis, 1982; Kowalski, 1982; Leibrandt and Schnupp, 1984). Lazarev (1989) described a mapping mechanism for converting a structured specification in the form of data flow diagrams (DFDs) into an executable Prolog program. In this article, the mapping is extended by including a case of partial matching. Several examples of mapping are presented, and the advantages of using this methodology to improve the quality of DFDs are discussed.

Introduction

The standard software development cycle of analysis, design, and implementation provides many benefits, but it also has serious drawbacks. One problem is that the mapping from a declarative specification to its procedural implementation is complex. There is no automated procedure to transform analysis into design, and verifying program correctness is an unresolved problem.

The nonexplicit representation of requirements reveals itself in maintenance problems. The lack of executable specifications (due to informal syntax and semantics) leads to long delays in evaluating whether the direction chosen for development is right.

Practical experiences using methodologies based on the analysis-design-implementation model clearly demonstrate the critical nature of these difficulties (Richter, 1986). It has been recognized that "an analysis specification, once finished, proved to be of little value." In other words, it neither can be verified nor transformed automatically into a design. Further, "good analysis may require some design and implementation -- some REAL TESTING of feasibility -- along the way."

Structured Analysis (De Marco, 1979) is often used to perform the software analysis phase. Structured Analysis is a data-oriented methodology with three main elements. First, there are data flow diagrams consisting of transformations and data flows. Transformations (or "bubbles") represent distinct logical functions, and data flows stand for the data input and output associated with transformations.

The second element is a data dictionary, which defines elements of structured analysis (that is, data flows, transformations, files, and so forth). Finally, there is a structured English specification used to describe functional primitives. Functional primitives are the nonpartitioned, lowest-level bubbles.

In structured analysis, we decompose a transformation into new transformations on a lower level. This procedure is continued until no more decompositions are possible, and then structured English is used to describe the lowest-level nondecomposable elements.

It can be argued that the core of the described problems is the existence of two orthogonal semantics involved; the specification is declarative and the implementation is procedural (Lazarev, 1987). Procedural information (such as correlations between data flows) is provided on the level of functional primitives but is totally separated from DFDs. Therefore, the usefulness of structured analysis as a software engineering tool is limited. Prolog provides a direction that narrows the gap between analysis and implementation. Prolog's declarative nature is ideally suited for the analysis phase, while Prolog's procedural capabilities are well suited for software implementation by making a specification "executable." The specification becomes a program that can be run and debugged. This approach is conceptually similar to rapid prototyping: A user can see whether his requirements as stated are what he actually wants, and the programmer can verify the correspondence of the program to the user's requirements.

Mapping DFDs to an Executable Specification

The mechanism of automatic mapping between the DFDs (for all levels above the level of functional primitives) and an executable Prolog program was described by Lazarev (1989). The most important feature of this mapping is the one-to-one correspondence between the DFDs and the resulting Prolog program. Each DFD is represented as a Prolog predicate with two arguments -- input and output structures. Each structure's components are elements of the Data Dictionary. DFDs by themselves are not enough to generate Prolog code automatically. The missing ingredient is a correlation among the input and output data flows for each transformation or, alternatively, a correlation among transformations themselves. We'll assume that these correlations (AND and OR correlations) are known.

The following steps describe a mapping algorithm. The case of partially matched inputs and outputs represented by (d.4) and (d.5) is an extension of the original algorithm. Steps (a), (b), and (c) are performed on every DFD level. Step (d) deals with interaction among levels:

a) Describe each transformation as a predicate with the same name. All predicates have two arguments; an input argument represented as structure i(I1, I2, ..., In), where I1, .., In are input data flows; and an output argument represented as structure o(O1, O2, ..., On), where O1, .., On are output data flows.

b) Represent OR-correlations explicitly by replacing predicates with several predicates of the same name, one for each mutually exclusive case. For example, a predicate bb( i(B), o(B1, B2, B3)) with OR-correlations among data flows B1, B2, and B3 can be replaced with the following:

     bb( i(B), o(B1))
     bb( i(B), o(B2))
     bb( i(B), o(B3))

c) Review the resulting set of predicates and mark all groups that form mutually exclusive sets. Such cases may arise either from OR-correlations among data flows or from more complicated OR-correlations among transformations.

d) Build a set of Horn clauses. Each clause has an upper-level predicate as its head, and predicates from one level below as its body. There may be multiple clauses for any given upper-level predicate. Clauses must satisfy the following requirements for a goal (that is, a head's predicate) and subgoals (body's predicates):

  • d.1) Each group of mutually exclusive predicates marked in (c) can provide, at most, one subgoal in a clause.
  • d.2) Each input of each subgoal must be matched with some input of the goal or with an output of some previous subgoal (a balanced input).
  • d.3) Each output of each subgoal must be matched with some output of the goal or with an input of some later subgoal (a balanced output).
  • d.4) If (d.2) or (d.3) fail then unmatched inputs (outputs) of a subgoal are replaced by an atom nil. At least one input and one output of each subgoal must be non-nil.
  • d.5) Unmatched arguments of the goal (inputs and outputs) are replaced by an atom nil.
Let's illustrate this procedure using a model project life cycle taken from De Marco (1979) (see
Figure 1a, Figure 1b, and Figure 1c). Minor changes have been made in decomposing the structured analysis "bubble" (Figure 1c).

These DFDs do not include any OR-correlations, so steps (b) and (c) in the mapping algorithm do not apply. The corresponding Prolog program is shown in Listing One. In order to be executable, it includes facts (like those shown in Example 1) that provide a representation for the lowest decomposition level.

Example 1: Sample Prolog facts from Listing One

  str_design( i( struct_spec, config_data),
              o( test_plan, pack_design) ).
  derive_log_equiv( i( user_req, curr_phys_DFD),
                    o( curr_log_DFD) ).

Despite the fact that the decomposition process can be stopped at any level, the value of such a mapping program is maximized by going to the level of nondecomposable functional primitives.

As Listing One demonstrates, the mapping preserves key features of DFDs such as a top-down design with capabilities for further refinement, and modularity. Developing an executable specification substitutes -- to a large degree -- for the design and programming phases of the traditional structured methodology. The resulting program is strictly logical, therefore there are no predefined input/output arguments (a property known as invertability). Three query types are supported:

  1. Find all possible input/output combinations. This corresponds to the case of totally unbound parameters. The query has the form:

      ?- predicate( X, Y)

    • For some given input/output parameters find unbound parameters (that is, conditions under which the DFD predicate is true). This corresponds to the case of partially instantiated variables, and includes two important subclasses:

      a) For a totally defined input, find an output

      b) For a totally defined output, find an input

      • Check whether the DFD predicate with all variables instantiated is true.

The queries, shown in Figure 2, for Listing One provide an illustration.

Figure 2: Queries used for Listing One

  ?-     project(X, Y).
         X = i(user_req0)
         Y = o(system0, budg_sched0)

  ?-     project(i( user_req0), Out).
         Out = o(system0, budg_sched0)

  ?-     project(i( user_req0), o(system0, budg_sched0)).
         yes

  ?-     str_anal(X, Y).
         X = i(user_req0, feas_doct0)
         Y = o(struct_spec0, budg_sched0, phys_req0)

  ?-     str_anal((user_req0, 12), Out).
         12 = feas_doct0
         Out = o(struct_spec0, budg_sched0, phys_req0)

Extension to Partial Matching

Data flow diagrams may have serious deficiencies, and because of the complexity of the total picture, problems often remain hidden. The mapping procedure based on Prolog may be helpful in revealing these problems. Examples in this and the following sections illustrate this point.

Consider the diagrams in Figure 3.

Suppose that transformations bb and cc are declared to be OR-correlated. Step (c) of the mapping algorithm produces the following set of mutually exclusive predicates:

   bb(i(A,B), o(O1))
   cc(i(C), o(O2))

Step (d) cannot be achieved using full matching, but partial matching using nil atoms is possible. The output is shown in Figure 4.

Figure 4: Resulting program generated from the DFD in Figure 3

     top(i(l), o(O1, nil)):-     aa(i(I), o(A, B, nil)),
                                    bb(i(A, B), o(O1)).
     top(i(l), o(nil, O2)):-     aa(i(I), o(nil, nil, C)),
                                    cc(i(C), o(O2)).

The program in Figure 4 demonstrates that, because of OR-correlations between transformations bb and cc; the output of transformation aa is either (A and B), or C (but not both); and the output of the transformation top is either O1 or O2 (but not both). In other words, the appearance of "nils" shows that DFDs can be further decomposed ("normalized"). In our case, the diagram on each level can be replaced by two, as shown in Figure 5.

The mapping of this diagram results in a "nil-free" Prolog program. The same program can also be obtained from Figure 3 by declaring two OR-correlations among data flows:

     (1) O1, O2
     (2) (A, B), C

One role of nil-arguments in programs, similar to Figure 4, is to perform a unification of distinct concepts. Under some circumstances it makes sense to use such programs rather than to perform further decomposition.

"Disconnected networks" are a special case of partial matching. Consider, for example, the two-level diagrams in Figure 6.

Suppose that level 2 diagrams are mutually exclusive (that is, OR-correlated). As can be seen from Listing Two the nil arguments in the heads of both clauses fully complement each other. This is an indicator of disconnected networks. Such a case must be transformed into a simpler case (in this case, by deleting a level 1 diagram and moving current level 2 diagrams to level 1).

Lost Causality

I've shown how the quality of DFDs can be evaluated by analyzing the corresponding executable specifications. But, an inability to create an executable specification from DFDs when using the described algorithm may be a sign of problems in the diagrams: They may be "non-normalized" or they may have sequencing ambiguities (which are resolved in structured English). For instance, consider the two-level diagram in Figure 7.

Suppose that there are no OR-correlations and no further decomposition provided. Step (a) of the mapping algorithm produces the following set of predicates:

   top( i(K), o( L) ).
   aa_ee( i(K, D), o( A, L) ).
   bb_dd( i(A, C), o( B, D) ).
   cc( i(B), o(C)).

But step (d) fails because there is no way to express the predicate top in terms of three lower-level predicates (aa_ee, bb_dd, cc). The reason is straightforward: The predicates are involved in a circular relation. For example, the predicate bb_dd must precede cc according to the data flow B, but the same predicate must follow cc according to data flow C. In a more complex diagram, circular structures may not be seen as easily, but the mapping algorithm provides a good indication of such problems. One solution may be further decomposition. Suppose that predicates aa_ee and bb_dd may be decomposed into two independent predicates (aa, ee and bb, dd). In this case, step (a) results in:

   top( i( K), o( L) ).
   aa( i( K), o( A) ).
   ee( i( D), o( L) ).
   bb( i( A), o( B) ).
   dd( i( C), o( D) ).
   cc( i( B), o( C) ).

The resulting clause is straightforward:

   top( i(K), o(L) ) :-
       aa( i( K), o(A) ),
       bb( i( A), o( B) ),
       cc( i( B), o( C) ),
       dd( i( C), o( D) ),
       ee( i( D), o( L) ).

The sequence of processes in this program (aa, bb, cc, dd, ee, in this order) shows that any attempt to express top in terms of composite processes (like aa_ee or bb_dd) with nontime-sequential elements will fail. "Causality," or time-dependence, is lost and a program cannot be constructed.

Conclusion

By incorporating 1. a set of DFDs with data flows defined by a data dictionary, 2. procedural information taken from functional primitives, and 3. the procedural semantics of Prolog, it is possible to create executable specifications as software programs. Such a program would contain basic control structures that is, sequence, decision, and repetition (through recursion). The output programs are in Prolog. Although Prolog is base on a restricted form of logic, it is adequate for our purposes. These programs are "pure" (free from side effects). As such, they are invertible and consequently provide a broader scope of experimentation than corresponding DFDs.

Not only can the specification be made executable, but the suggested approach is also helpful in verifying and improving specifications. This is done by incorporating a partial matching extension into an original algorithm.

The approach presented is evolutionary. It extends the DFDs' methodology by making it executable. As a result, the main advantage of the standard DFD methodology -- a graphical language used to solve a communication problem -- remains intact. All of the above makes logic programming and Prolog very promising in software engineering.

References

Davis, R. Runnable Specification as a Design Tool, "Logic Programming" (eds. Clark and Tarnlund), Academic Press, London: 1982, pp. 141-149.

Kowalski, R.A. "AI and Software Engineering," Datamation, Nov. 1984, pp. 92-102.

Lazarev, G.L. "Solving Problems with Prolog," AI EXPERT, July 1987, pp. 59-68. Why Prolog? Prentice-Hall, 1989.

Leibrandt, U. and Schnupp, P. "An Evaluation of Prolog as a Prototyping System," in Rapid Prototyping, R. Budde (ed.), Springer-Verlag, Berlin: 1984, pp. 424-433.

De Marco, T. (1979) Structured Analysis and System Specification, Yourdon Press, New York, N.Y.: 1979.

Richter, C. "An Assessment of Structured Analysis and Structured Design," ACM Sigsoft Software Engineering Notes, 1986, v.11, no. 4, pp. 75-83.

_Executable Specifications With Prolog_ by Gregory Lazarev

[LISTING ONE]

<a name="0209_000e">


project( i( User_req), o( System, Budg_sched) ):-
  survey( i( User_req), o( Feas_doct) ),
  str_anal( i( User_req, Feas_doct),
            o( Struct_spec, Budg_sched, Phys_req) ),
  hw_study( i( Phys_req), o( Config_data, Hardw) ),
  str_design( i( Struct_spec, Config_data),
              o( Test_plan, Pack_design) ),
  implem( i( Hardw, Test_plan, Pack_design), o( System) ).

str_anal( i( User_req, Feas_doct),
          o( Struct_spec, Budg_sched, Phys_req) ):-
  study_curr_environ( i( User_req), o( Curr_phys_DFD) ),
  derive_log_equiv( i( User_req, Curr_phys_DFD),
                    o( Curr_log_DFD) ),
  model_new_log_sys( i( User_req, Curr_log_DFD, Feas_doct),
                     o( New_log_DFD, DD, Trans_desc) ),
  model_new_phys_sys( i( New_log_DFD),
                      o( New_phys_DFD, Budg_sched, Phys_req) ),
  produce_struct_spec( i( New_phys_DFD, DD, Trans_desc),
                       o( Struct_spec) ).

survey( i( user_req0), o( feas_doct0) ).
hw_study( i( phys_req0), o( config_data0, hardw0) ).
str_design( i( struct_spec0, config_data0),
            o( test_plan0, pack_design0) ).
implem( i( hardw0, test_plan0, pack_design0), o( system0) ).
study_curr_environ( i( user_req0), o( curr_phys_DFD0) ).
derive_log_equiv( i( user_req0, curr_phys_DFD0),
                  o( curr_log_DFD0) ).
model_new_log_sys( i( user_req0, curr_log_DFD0, feas_doct0),
                   o( new_log_DFD0, dd0, trans_desc0) ).
model_new_phys_sys( i( new_log_DFD0),
                    o( new_phys_DFD0, budg_sched0, phys_req0) ).
produce_struct_spec( i( new_phys_DFD0, dd0, trans_desc0),
                     o( struct_spec0) ).





<a name="0209_000f"><a name="0209_000f">
<a name="0209_0010">
[LISTING TWO]
<a name="0209_0010">

bb( i( B, B1, nil), o( nil, E) ) :-
    bb'( i( B, B1), o(E) ).
bb( i( nil, nil, C), o( D, nil) ) :-
    bb''( i( C), o( D) ).












Copyright © 1989, Dr. Dobb's Journal


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.