Extending C with Prolog

An expert advisor for resolving IRQ conflicts

Dennis is the author of the Active Prolog Tutor and a principal of Amzi!, a vendor of Prolog products and custom applications. Dennis can be reached at 508-897-7332 or on the Internet at [email protected].

Prolog in a Nutshell

For instance, Figure 1(a) is a simple control loop (written in C) that reads a command from a user and then does some processing. Figure 1(b) is the equivalent code written in Prolog. Notice the lack of data-definition statements and string compares in the Prolog version. In Prolog, dynamically allocated symbols are used instead of character strings.

As an integral part of the language, Prolog also has a sophisticated pattern-matching algorithm called "unification" and a search mechanism called "backtracking." In Figure 1(b), the pattern do(X) is unified against the first of the three do rules, defined by the if operator (:--). If the user types open when prompted, then the first rule (or "clause," as its usually called) is matched and the code on the right of the :-- is executed. If the user enters something other than open, Prolog backtracks to the adjacent clause and continues to look for a do rule that matches the user's input. Similarly, matching and backtracking take place in the main clause with the use of repeat and X==quit, which cause the code between these two statements to loop until the user types quit.

With Prolog, you don't write if-then-else statements, function calls, while loops, or other flow-control constructs. However, between unification and backtracking, you can induce any flow-control behavior in a Prolog program that can be achieved in any other language. Symbols, unification, backtracking, and dynamic-memory management all tend to eliminate the procedural code you normally need to write. It is no surprise that what is left looks much more declarative than conventional code and is often a fraction of the size.

From Prolog to C and Back

Prolog programs are essentially a collection of rules activated by queries much in the same way a database is queried. This is true whether the code is interpreted or compiled. When Figure 1(b) is compiled, main is used to start the program; it then queries other rules, which query other rules, and so on. However, this program can also be loaded and run from an interpreter. In this case, any of the clauses in the program can be queried directly. The nature of this interaction with Prolog dictates the nature of a C-to-Prolog interface, which must be able to either execute compiled Prolog code or query a loaded Prolog program. In this sense, the C-to-Prolog interface will look more like a database API than procedural, interlanguage calls.

Figure 1(b) also illustrates that the write statement has nothing to do with logic, pattern-matching, or searching; it simply performs I/O. Prolog provides a number of special predicates, such as write, used primarily for their side effects. It is in this area that Prolog is weaker than C. In Prolog, you must rely on whatever special predicates a particular vendor provides with an implementation. So, for example, if a particular Prolog implementation doesn't supply the tools for accessing Windows, it can't be used to implement Windows applications. This is where Prolog-to-C connections come in--they let you define extended predicates, such as write, to allow Prolog code access to any services accessible from C.

Advising on IRQ Conflicts

We recently installed Gateway multi-media kits on our PCs, but the installation was somewhat difficult because of conflicts in our interrupt-request lines (IRQs). Since an expert system is ideal for resolving such conflicts, I wrote a Prolog program (Listing One) that embodies a few rules of expertise for sorting out IRQ conflicts. It first checks to see if the default IRQ for the device being installed is available. If so, there is no problem. If not, it tries the alternate IRQs and recommends an available slot, telling the user to reset the IRQ switches on the card for the device. If the alternates aren't available, the program tries to move existing IRQs around. Failing all else, the program looks for COM ports that can be doubled up on a single IRQ, thus freeing one for the new device.

This example is intended to illustrate how this knowledge is expressed in Prolog, not to be the last word on IRQ conflicts. The example does illustrate how expert systems evolve. These rules came about from the particular cases of installing the Gateway SoundBlaster on two different machines. As new cases are encountered, new rules can be added, or old rules can be modified to reflect the new situations. In this way, the system gets smarter as new installation situations are encountered.

Listing Two is a simple DOS C program that calls the Prolog IRQ advisor. The main entry point could easily be a function called from a menu choice of a larger installation application. Listing Two finds out what type of device is being installed, then calls the IRQ advisor to see if there will be any IRQ conflicts installing that device, and if so, how they can be resolved. The advisor has, coded into it, the knowledge of various devices and the allowable IRQs.

The main() function in Listing Two uses cpCallStr(&t, "irq_advice('%s')", sDevice) to call the main entry point of the advisor. It dynamically builds a query and poses it to the compiled Prolog program. This is very similar to a database call. When the Prolog clause irq_advice(Device) is called, it gets the existing IRQ assignments and asserts them into Prolog's dynamic database by calling the Prolog predicate get_irqs. get_irqs is in turn mapped to a C function that provides the service. (In this example, the C function simply reads the data from a file of test IRQ data. However, a typical implementation would have the code necessary to determine the IRQs from the machine itself.) In the C function p_get_irqs, each IRQ is asserted to the Prolog database using the appropriate API function calls. In this case, a printf-like function is used to build the Prolog term to be asserted.

These terms (or facts) are used by the Prolog rules for finding open slots or making recommendations on rearranging slots. For example, the make_room predicate in Listing One uses pattern matching to find two IRQs with single COM ports on them. It then recommends that the user combine them and makes the same change to its own dynamic database. The rule that called make_room then tries again to fit in the device's IRQ request with the new free space. This approach is very similar to the approach taken with puzzle-solving applications. The program starts with an initial state (the current IRQs) and a goal state (the IRQs with the device installed on one of them). The rules transform the state until the goal condition is reached. The various steps of the transformation are the recommended steps for the user to take in rearranging IRQs.

The sample program is set up to allow installation of two different devices, a SoundBlaster and a Mitsumi CD-ROM. Each has different IRQs it can use. The current IRQ settings are listed in the file IRQTEST1.DAT; see Listing Three . These are the possible devices installed on IRQ channels 0--15, respectively. Running the program for each of these produces the results shown in Figure 2. The output is the result of the third key aspect of the C-Prolog interface: Rather than use Prolog I/O statements, the Prolog msg predicate calls the p_msg function defined by the C program, which uses printfs to generate the output. This way, the Prolog program is independent of the user-interface environment in which it is deployed. (The interface could have just as easily been Windows, or been implemented using a GUI library, such as Zinc or XVT.) To illustrate other transformations between Prolog and C, the p_msg function accepts either a term or a list of terms (represented within square brackets [] in Prolog) as an argument. The C function dynamically determines which type of Prolog argument it has received, and, if it's a list, walks through the list outputting each term after first converting it to a C string.

Conclusion

David is a developer at Microsoft research and can be contacted at [email protected].

Windows NT networking installation and configuration is controlled by the file NCPA.CPL, which the user sees as the Networks icon within the Control Panel's main window. The bulk of this DLL is written in C++, but it also contains a simplified Prolog interpreter known as "Small Prolog," written by Henri de Feraudy during the late 1980s and put into the public domain. It is available through the C User's Group (Lawrence, KS).

Small Prolog (or "SProlog") follows the Cambridge syntax and includes most standard built-ins (predicates) defined by Clocksin and Mellish in their seminal book Programming in Prolog; you can further extend the language with user-defined built-ins. The disk from the C User's Group (#CUG297) includes C source files, makefiles, documentation, and examples that demonstrate Prolog features for C programmers. The interpreter is written in portable C code--it compiles for MS-DOS, UNIX, and Atari platforms, as well as Macintosh (if you modify the UNIX version using the Think C Console function) and OS/2 (by modifying the PC version).

SProlog supports most standard Prolog-interpreter functionality with one notable exception: It does not do garbage collection. SProlog defines a reduced form of the Prolog language which looks very much like Lisp. For example, a typical Prolog predicate might read pet(C):animal(C),ownedBy(D),person(D). In SProlog, this would look like ((pet C) (animal C) (ownedBy D) (person D)).

To be useful, each hardware or software component installed on a Windows NT machine must be connected at run time to some other component--nothing stands alone. However, certain constraints define which connections are reasonable and legitimate. Possibilities such as multiple network cards, multiple protocol stacks, and conflicting software needs must be handled.

As each network-related component is installed, it writes several textual records into its own area of the Configuration Registry. In typical OOP fashion, these records define the class of each component and the constraints and requirements of each class. At configuration time, the C++ code in the NCPA.CPL file exhaustively browses the Registry, collects these records, and converts them to SProlog format.

Along with its C++ code and SProlog interpreter, the NCPA.CPL file has a 700-line SProlog program embedded into it as a textual Windows "resource." This program is the actual network-configuration algorithm; a C++ class "wrapper" encapsulates the SProlog engine and exposes C++ member functions for facilities such as consulting and querying. Network configuration is performed by consulting the "rules" (the resource-based algorithm), consulting the "facts" (the Registry-derived declarative information), and performing a single query which runs the configure everything predicate. Then the C++ code performs many smaller queries to enumerate the results of the main query from the SProlog database. This information is rearranged and written back into each network component's Registry area. Then, when the network is started, this updated information is used by each software process to determine what other software modules are to be dynamically connected to it.

The SProlog algorithm has several features, but primarily it exploits Prolog's inherent backtracking mechanism by exhaustively checking each extant component with every other to determine compatibility. A set of potential "bindings" (one-directional links) is asserted into the Prolog database in the first pass. Then the other constraints are checked, and any associations which would violate negative constraints are retracted. Finally, the remaining database information is used to construct NT namespace device names for each component's "bindings."

This network configuration methodology was designed to facilitate the installation of component ensembles which could not be foreseen in 1991, when the work began. Since components declare their classes and constraints themselves, the Prolog interpreter can be counted upon to perform correctly without requiring updates to the NT binaries themselves.

The SProlog interpreter was chosen for this project because the problem required search-space control, simple and reliable database access, and easy string-manipulation operations, all of which are hallmarks of Prolog.

Figure 1: (a) Control loop written in C that reads a command from the user and processes; (b) similar function written in Prolog.

(a)
void main()
{
   char buf[20];
   do {
      gets(buf);
      if (0 == strcmp(buf, open)) ...
      else if (0 == strcmp(buf,add)) ...
      else if (0 == strcmp(buf, delete)) ...
   } while (strcmp(buf, quit));
   printf(done);
}

(b)
main :-
   repeat,
   read(X),
   do(X),
   X == quit,
   write(done).
do(open) :- ...
do(add) :- ...
do(delete) :- ...
do(quit).

Figure 2: Sample session with the IRQ advisor program.

What device are you installing? <I>Sound Blaster</I>
Use which test file? <I>irqtest1.dat</I>
IRQ Conflict Resolution Analysis
<I>Put com ports 3 and 4 together on IRQ 3</I>
<I>Move device mouse to IRQ 4</I>
<I>Continue normal install</I>
What device are you installing? <I>Mitsumi CD-ROM</I>
Use which test file? <I>irqtest1.dat</I>
IRQ Conflict Resolution Analysis
<I>Default IRQ not available. Set device to use 11 instead</I>
<I>Continue normal install</I>

Listing One

/* Prolog program to illustrate how an expert system that resolves installation
   conflicts might be implemented. In this case, it resolves conficts in the
   IRQ table, by either selecting another IRQ for the device being installed, 
   rearranges another device's IRQ to open a slot for the new device, or, if 
   there is no room doubles up the com ports on a single IRQ to free up a slot.
   The predicate msg/1, which takes either a single term or a list as
   an argument, is implemented in C.
   The predicate get_irqs/0 is also implemented in C and asserts a
   number of Prolog facts in the form irq/2.
*/

irq_advice(Device) :-
  msg($IRQ Conflict Resolution Analysis$),
  get_irqs,                         % get IRQs from C program
  free_irq(Device),
  msg($  Continue normal install$).

/* rules for finding a free IRQ */
free_irq(Dev) :-                    % fail if unknown device
  not(ok_irq(Dev,_,_)),
  msg([$  Unknown Device $, Dev]),
  !,
  fail. 
free_irq(Dev) :-                    % see if requested IRQ is free
  ok_irq(Dev,IRQ,Option),
  is_free(IRQ,Option), !.
free_irq(Dev) :-                    % see if requested IRQ can be cleared
  ok_irq(Dev,IRQ,Option),
  clear(IRQ), !.
free_irq(Dev) :-                    % see if an IRQ can be opened
  make_room,
  free_irq(Dev).                    % try again with new open slot
is_free(IRQ,default) :-             % if default is free, no problem
  irq(IRQ, open),
  msg($  The default IRQ is open.  No action needed$).
is_free(IRQ,optional) :-            % use different device IRQ
  irq(IRQ, open),
  msg([$  Default IRQ not available. Set device to use $, IRQ, $ instead.$]).
clear(I) :-       % move another device's IRQ to free up requested IRQ
  irq(X, open),
  irq(I, D),
  ok_irq(D, X, _),   % make sure the device can be moved
  msg([$  Move device $, D, $ to IRQ $, X]),
  retract(irq(X,open)),   % update dynamic database with the switch
  retract(irq(I,D)),
  assert(irq(X,D)),
  assert(irq(I,open)).
make_room :-     % double up COM ports to make room, if possible
  irq(IRQ_X, com(COM_X)),
  irq(IRQ_Y, com(COM_Y)),
  IRQ_X \= IRQ_Y,
  msg([$  Put com ports $, COM_X, $ and $, COM_Y, $ together on IRQ $, IRQ_X]),
  retract(irq(IRQ_X, _)),      % update the dynamic database
  assert(irq(IRQ_X, com(COM_X)+com(COM_Y))),
  retract(irq(IRQ_Y, _)),
  assert(irq(IRQ_Y, open)).
% IRQs that can be used for different devices.  We only do Sound Blasters
% and Mitsumi CD-ROMs for now.
ok_irq('Sound Blaster', 5, default).
ok_irq('Sound Blaster', 2, optional).
ok_irq('Sound Blaster', 3, optional).
ok_irq('Sound Blaster', 7, optional).
ok_irq('Mitsumi CD-ROM', 15, default).
ok_irq('Mitsumi CD-ROM', 11, optional).
ok_irq('Mitsumi CD-ROM', 12, optional).
/* this IRQ information is used for relocating the mouse if necessary */
ok_irq(mouse, 2, optional).
ok_irq(mouse, 3, optional).
ok_irq(mouse, 4, optional).
ok_irq(mouse, 5, optional).

Listing Two

/* Sample expert system advisor embedded in C. This particular 
   system is used to resolve and fix conflicts for IRQ slots 
   when installing new devices in a computer. It is set up here 
   as a simple DOS program, but it can be used as a module in a 
   larger program, called, for example, when a menu item is 
   selected in a GUI interface.
   It illustrates the three key aspects of integrating Prolog 
   and C.
   1.  The rules for deciding how to rearrange the IRQs are 
       declarative and expressed in Prolog code. (Note that the 
       advantage of Prolog is when there is no clear algorithm 
       for describing how to solve a problem, but rather a 
       collection of seemingly disconnected rules.)  The rules,  
       or logic base, is called from the C program.
   2.  The Prolog program calls back to C to get low level 
       information. In this case, the C program determines the 
       current IRQ use for the machine it's running on. 
       For the example, the information is read from a test data 
       file, but a real example would have code that digs around 
       in the machine or asks for this information. The 
       predicate is called get_irqs.
   3.  The Prolog program relies on C for its I/O, so that the 
       Prolog program is independent of Ui. In this example, it 
       simply sends output to a predicate, implemented in C, called 
       msg. Msg is made a little interesting by the fact that it 
       can either take a single argument, to be displayed, or a list 
       of Prolog terms to be displayed. The I/O, for this example is 
       just printfs, but could be any fancy GUI display.
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>

#include "cogent.h"

char  sTestFile[80];        /* global to hold name of test data file */
/*---- built-in predicates, callable from Prolog ----*/
/* function prototypes */
TF p_get_irqs(void);
TF p_msg(void);
/* Extended predicate table definitions, mapping Prolog predicate
   names to C functions. */
PRED_INIT irqPreds[] =
{
   {"get_irqs", 0, p_get_irqs},
   {"msg", 1, p_msg},
   {NULL, 0, NULL}
};
/* extended predicates */
TF p_get_irqs(void)
{
   int  i;
   FILE * fp;
   char buf[80];
/* Assert facts about the IRQs to the Prolog dynamic database */
/* Read them from the test file for now */
   fp = fopen(sTestFile, "r");
   for (i=0; i<16; i++)
   {
      fgets(buf, 80, fp);
      cpAssertzStr("irq(%i, %s)", i, buf);
   }
   fclose(fp);
   return(TRUE);
}
TF p_msg(void)
{
   char  buf[80];
   TERM  t, tm;
   pTYPE ptype;
/* Get the first (and only) parameter and determine its type.  If its
   a list, walk the list converting each term to a string and printing
   it. If its not a list, then just convert and print the term.
*/
   cpGetParm(1, cTERM, &t);
   ptype = cpGetTermType(t);
   if (ptype == pLIST)
   {
      while (OK == cpPopList(&t, cTERM, &tm))
      {
         cpTermToStr(tm, buf, 80);
         printf("%s", buf);
      }
   }
   else
   {
      cpTermToStr(t, buf, 80);
      printf("%s", buf);
   }
   printf("\n");
   return(TRUE);
}
/* ----- Main ------------------------------------------------------------ */
void main()
{
   TERM t;
   TF   tf;
   char sDevice[80];
   cpInit("irqxs");
   cpInitPreds(irqPreds);
   cpLoad("irqxs");
   printf("What device are you installing? ");
   gets(sDevice);
   printf("Use which test file? ");
   gets(sTestFile);
   cpCallStr(&t, "irq_advice('%s')", sDevice);
   cpClose();
   return;
}

Listing Three

timer
keyboard
com(1)+com(2)
com(3)
com(4)
mouse
disk
lpt1
clock
redirect
open
open
open
coprocessor
disk
network