Tutorial: Using Prolog as a Design Query System

Introduction

The VHDL-1076.1 parser enables a designer to have access to a deductive database with their hardware design as its realm of discourse. This tutorial demonstrates how to formulate and execute queries about a VHDL design. (The original tutorial is due to Peter B. Reintjes that was modified by K. Thirunarayan.)

Exercise A. Working with the VHDL Parser

Move to the distribution directory and make sure that the program vhdl97_parser has been made. See the README file to create the parser.

The first part of the tutorial will consist of the following steps:

Run the Prolog savestate containing the VHDL parser.
Test the VHDL parser.
Read in the VHDL file tkp_1.vhdl (and ams3.vhdl and tp_7.vhdl).
View the design_unit/2 clauses created by the VHDL parser.

The following sections describe these steps in detail. All text shown in lower-case or mixed case is typed by the user. The Prolog prompt ``?-'' and all upper-case text represent the system responses.

1. Starting The Prolog Interpreter

Execute the parser with the following command.


        unix%  vhdl97_parser

           ...HEADER INFORMATION...

        | ?-

2. Testing the VHDL Parser

Special goals called ``test'', ``timing'', and ``testall'' have been created to test and time the parser on small VHDL files. To run the first test, issue the command: ``test.''. Whenever a VHDL-97 design unit is read into the database, an asterisk will be printed on the screen.

        ?- test.
        TESTING INDIVIDUAL VHDL FILES
             ... etc ...


        YES.
        ?-

3. Reading in the VHDL Tutorial Example

Now we will explicitly call the parser to read in the file ``tkp_1.vhdl''. The command will be: ``vhdl_read(tkp_1).'' Note that the suffix, ``.vhd'' or ``.vhdl'', is left off when calling the parser on VHDL files in the distribution. Also, always remember to type the final period.


        ?- vhdl_read(tkp_1).

Similarly, read in ``ams3.vhdl'' and ``tp_7''.

In general, the command `` vhdl_read(NAME) '' will read a VHDL file where NAME is the prefix of the VHDL file of interest. If NAME is alu , the parser will look in the current directory (or subdirectories data or test_data) for a file named alu.vhd (or alu.vhdl) and read all VHDL-93 design entities from that file into the database.

4. Examining the Database

Now that several design units have been read in, we can examine this information by viewing the design_unit/2 clauses in the database. These design units were created from the information in the VHDL files and placed in the database by the parser. When the query ``design_unit(A,B).'' is typed by the user, note that A and B are variables and must be in upper-case. This is not to be confused with the computer responses given after the query which show the bindings for the variables A and B.


        ?- design_unit(A,B).
         A = [ LIBRARY( ... ETC ... ),  USE(FILENAME, ...)... ]

         B = ARCH(NAME, ENTITY, DECLARATIONS, ... ETC ...

Since the database contains more than one design unit, the user can type a semicolon after each pair of A,B variable bindings are given. This will direct the interpreter to display successive design_unit/2 clauses.

Exercise B. Creating a Query about Design Hierarchy

Once these design components are in the Prolog system, we want to define and then execute queries about the design. For example, such queries might include questions like:

What components are contained in architecture X?
What components are contained in the hierarchy under architecture X?
In what higher-level components does component Y appear?

To create these queries we need to write several Prolog predicates. The first, member/2 , will succeed when an item is found in a list. Since the concurrent and sequential statements from VHDL programs are stored in Prolog as lists, we will need member/2 to see if a particular type of statement is on these lists.

Now we want to define the predicate substructure/2 to determine if a particular hardware component is a sub-component of an architectural description. The first clause will locate the component instance statements for component Comp. This statement is represented as a comp_instant/4 term in the list Statements.


substructure(Comp,Arch) :-
    design_unit(_,arch(Arch,_,_,Statements)),
    member(comp_instant(_,Comp,_,_),Statements).

Failing this, the second clause will recursively search all sub-components of Arch to see if their architectures contain an instance of Comp.


substructure(Comp, Arch) :-
    design_unit(_,arch(Arch,_,_,Statements)),
    member(comp_instant(_,SubArch,_,_),Statements),
    substructure(Comp, SubArch).

Note that the entire substructure/2 predicate is defined only in terms of the design_unit/2 clauses in the database, the member/2 predicate, and itself. Furthermore, these two clauses correspond closely to an English language statement of their meaning. The first clause states that:

Comp is a substructure of Arch if one of the statements in architecture Arch refers to the component Comp.

While the second states:

Comp is a substructure of Arch if SubArch is a substructure of Arch and Comp is a substructure of SubArch .

Executing the Query

This query can be used in several ways by instantiating the arguments differently. Recall that the member/2 predicate can be used to:

Verify that an item is on a list. This is the case if both arguments are instantiated (e.g. member(a,[x,y,a,z]) will succeed, but member(a,[x,y,z]) will fail).
Produce successive members of a list by binding them to a variable first argument (e.g. member(A,[x,y,z]) will succeed for A=x, A=y, and A=z).
Create a list containing a specified item (e.g. member(x,L) will cause L to be unified with the structure [x|_] ).
Create a list containing an unspecified item (e.g. member(X,L) will unify L with [X|_] ).

The variety of functions that can be performed by the substructure/2 predicate are in sharp contrast to the four separate subroutines which would have to be written in a programming language such as C.

Verification (both arguments instantiated): The query substructure(nand,alu) will succeed if an instance of the sub-component nand occurs anywhere in the alu architecture. It will fail if nand does not appear in the alu hierarchy.
Generating Sub-components of a Design (second argument instantiated): The query substructure(SubComponent,alu) will succeed for every sub-component in the hierarchy of the alu architecture. When it succeeds, the variable SubComponent will be bound to the selected sub-component. This goal will only fail after all of the sub-components of the alu architecture have been tried.
Find all Designs which use a Sub-component (first argument instantiated): The query: substructure(xor,Arch) will succeed for every architecture which contains an exclusive-or component in its design hierarchy. Thus, the following query will produce a list of all architectures which use the exclusive-or.

bagof(Arch,contains(Arch,xor),Archs)
Generate all User/Sub-component pairs (neither argument instantiated): The query substructure(SubComp,Arch) will return every pair of architecture and sub-component which have ancestor/descendent relationship. This query might be used to create a cross-reference for a complex design.

Extending the Query

To make a query about software components such as procedures and functions as well as structural design units, we must examine the declarations and definitions which accompany the VHDL architectures. Furthermore, since there is other information here (the type of the Return variable indicates whether a software sub-component is a procedure or a function), a third argument will indicate the kind of subroutine.


type_of_subroutine(procedure,  null ).
type_of_subroutine( function, Return) :- \+ (Return = null).

subroutine(Sub,Arch,Type,Purity) :-
    design_unit(_,arch(Arch,_,Decls,_)),
    member(sub_program(sub_spec(Sub,_,Return,Purity),_),Decls),
    type_of_subroutine(Type,Return).

As before, when we fail the immediate-descendent test, the second clause will recursively search the procedure-call hierarchy.


subroutine(Sub,Arch,Type) :-
    design_unit(_,arch(Arch,_,Decls,_)),
    member(sub_program(sub_spec(First_Child,_,_,_),_),Decls),
    subroutine(Sub,First_Child,Type).

As before, this query can be used either to verify a relationship, find particular instances of the relationship, or generate all pairs of software components having the relationship.

Generalizing the Query

Now we can create a higher-level query which embodies the concept of sub-system relationships for hardware or software. In this predicate, the first two arguments are the names of the system and sub-system in question and the third argument describes the type of the sub-system.


contains(Arch,Comp,structure) :- substructure(Comp,Arch).

contains(Arch,Comp,Type)      :- subroutine(Comp,Arch,Type,_).

The English reading of these two clauses are:

Arch contains component Comp of type structure if Comp is a substructure of Arch.

OR,

Arch contains component Comp of type Type if Comp is a subroutine of type Type in the architecture Arch.

Exercise B. Testing the Hierarchy Queries

Consult the file queries.pl into the Prolog system.
Examine all related pairs in the system by typing `` contains(Parent,Child,Type).'' and then typing a semicolon after each successful binding is displayed. Eventually you will exhaust all of the possibilities.

1. Consulting the file queries.pl

Just as we consulted the VHDL parser before, you consult the source code file queries.pl by typing a left square bracket, the root file name queries, a close square bracket and a period.


        ?- [queries].

        YES.
        ?-

2.Testing the Query

The high-level query contains/3 is tested in the following dialog.


        ?- contains(Parent,Child,Type).

        PARENT = 'TEST'
        CHILD = 'CONCATENATE'
        TYPE = 'PROCEDURE' ->

At this point, the user must type a single semicolon to the -> prompt. This will cause the system to find the next set of bindings for the Parent/Child/Type variables that will satisfy the query.

We can explore the different ways in which this query can be used by giving the three arguments different instantiations. For example, if we instantiate the third argument to function we will limit the general search described above to operate only on functions and to ignore procedures or hardware structures. Similarly, we can instantiate the first argument and limit the search to only that architecture. For example, we might ask:


English:   What functions are used by the entity "test"?

Prolog:    contains(test,Function,function).

While the form of the query may not be completely intuitive to someone unfamiliar with Prolog, the information content of the query is identical to that of the English question. That is, the query does not contain extraneous information about data-structures, search procedures, memory allocation, and other traditional programming concepts.

Simple extensions of this basic facility can yield a substantial amount of interesting information. As one final example, suppose we want to know about all design entities which are not being used as parts of other designs.


English:
    What entity is not used as part of any other design? 

Prolog:
        design_unit(_,entity(Name,_,_)),
        not  contains(_,Name,_).

The anonymous variables ( _) and the negation ( not) are particularly useful when we want to know if an object is a member of a relation, but we do not care about the identity of the relative, or as in this case, whether the entity in question is a software or hardware component.

VHDL Hardware Design Browser

To make the system usable, Laura DeBrock implemented a Tcl/TK front that enables the hardware designers to create the queries using a graphical user interface, thereby shielding them from Prolog details. Currently, Tianrong Hu is developing a more general Java front end for the same purpose.