Building an Expert System

Prolog and C/C++ make a powerful combination

Gregg Weissman

Gregg was formerly manager of systems software development at Xircom. Currently, he is director of PC security products at Spyrus and can be reached at geeman@best.com.

Anyone who has used a PC card knows the frustration of a technology that tries to be "plug and play," and too often becomes "plug and pray." The sources of this frustration include user error, manufacturers' loose interpretations of the PCMCIA specification, and subtle differences in the interactions between card, computer, and operating system.

Clearly, it's an overwhelming task for PC Card manufacturers to be compatible with a dozen laptop makers (with a dozen models each), a number of current and legacy versions of PC Card system software, several species of operating systems, and PC Cards from other manufacturers.

At Xircom, we realized that we either had to limit the scope of compatibility ("How many laptops do you really want to support?"), or tackle the problem head-on. We chose to tackle the problem by building an expert system that handled the most common and serious obstacles to successful installation and operation of our network and network/modem combo-cards.

The system we developed was built using three off-the-shelf tools: Borland C++ 4.5 for front- and back-end development, Microsoft Assembler 6.1 for low-level functions, and Amzi! Prolog+Logic Server to integrate the expert system's rule-based components. The Logic Server is a complete implementation of Prolog, providing the ability to load, query, and update a database of rules and data, callable from C/C++ or, under Windows, any tool that calls a DLL (C, C++, Delphi, Visual Basic, PowerBuilder, Access, Excel, and others). The Logic Server is available for Windows 3.x/95/NT, DOS, Linux, OpenVMS, and Digital UNIX.

With Amzi! Prolog, development and compilation can be done within a Windows IDE, or you can edit a Prolog source file and compile it from the DOS command line. The compiled source resides in a proprietary binary-format file with an .XPL extension loaded by the "logic server"-a Prolog engine implemented in C (a DLL or OBJ) that links to your application. Some easily implemented conventions let you call Prolog functions from within a C/C++ program, or call C++ from Prolog functions.

System Structure

The design of the system (see Figure 1) involved accounting for three different tasks:

• Collecting as much information as possible about the target computer, its configuration, PC Card software, and other installed devices.
• Detecting failure modes that could prevent the installation from being successful.
• Making sense of this information so that a configuration for installing the card could be determined, if possible.

We accomplished the first task by designing a series of C++ modules, including a general class library for working with DOS and Windows and their dependencies, PC Cards, and PC Card system software (Card Services). A collection of classes that model system components utilized the services of the general class library. Deriving from a base Device class, classes for each component were responsible for detecting and reporting only those characteristics bound to that specific device type. An IODevice object was instantiated, for example. It was responsible for reporting on I/O port usage throughout the I/O space. Other examples include SoundCardDevice (which detected common sound cards and reported on their characteristics), IRQControllerDevice (which analyzed the settings on the Peripheral Interrupt Controller chip to detect free IRQs), and NetworkDevice (which looked for open network connections).

To analyze the PC Card environment, we defined a class that encapsulated examination and diagnostic functions that could report on a myriad of parameters representing the configuration parameters specific to PC Cards and Card Services. Functions highly specific to exercising Card Services capabilities and resource allocations checked that the complex system component was running correctly.

What the Card Services and system-diagnostics functions had in common was that their test results were collected in a linked list of objects derived from an Assertion class. The Assertion class had the responsibility of linking instances of itself and its subclasses, each instance containing a representation of a fact regarding system state. Assertions were generated in one of several canonical forms, with a subclass managing the storage and representation of that particular form. When system diagnostics were complete, a static member function of the Assertion class was invoked to dump assertions out to a disk file, in a form suitable for digestion by the Prolog-based expert system.

The back end, written in C/C++, was responsible for executing diagnostic functions on the PC Card being installed, under the control of the expert system. Taking parameters from the expert system, the back end tests various configurations to ensure that the card works the way it is supposed to (given the expert's analysis), then reports back a result. The Amzi! system allowed us to invoke the Prolog engine from the C++ front end and also call C functions from within the expert system.

The Expert System

The expert system consists of three main components:

• A driver.
• Rules.
• Assertions generated by the C++ front end.

The driver and rules were combined into a single compiled executable, which the Amzi! logic server executed. In the Amzi! architecture, the logic server is a C++ object, implemented as a DLL. It is invoked by the front end through calling initialization routines (including one that loads the target executable Prolog program) and issuing a run function to the server. The driver portion of the expert system was simply a series of Prolog "function calls" to perform more-complex rule processing.

To design the expert system, I needed a schema for how all the configuration information would be represented. After that was in place, the rules that would process the raw data (facts) and derive the answer to the main goal could be constructed: "Could the card be correctly installed, given the configuration of the user's system?"

The resulting schema represented configuration facts as a tuple associated with a resource type. The tuple defined the locus, value, and attributes of the resource. For example, to designate the availability of an I/O port, a fact ioresource(machine, 0x300,used) would appear in the Prolog database.

Once this schema was defined, the vocabulary for the possible loci and attributes that could be associated with a resource were defined. A resource locus could be machine, meaning the resource was analyzed as part of the system-hardware scan, or cardsrv (Card Services), meaning the resource was analyzed by the Card Services diagnostics, and other similar designations. Attributes were generally defined as "available" or "unavailable," with some adjunct attributes defined for additional flexibility.

The value portion of the tuple always refers to the value of the resource being tested-a memory address, I/O port address, IRQ number, and so on. A portion of the database the expert system operates on, therefore, looks like Example 1. The entire range of system resources pertaining to the installation and configuration analysis are represented this way. I/O port ranges are defined on 32-byte boundaries, and memory is analyzed on 4-KB boundaries, mainly because that's the minimum granularity of Card Services' memory-allocation logic and it keeps the size of the database reasonable.

There were many other system attributes to be tested (as part of the overall analysis) that did not fit this canonical model, and they were represented in ad hoc fashion. Still, the core of the analysis operates on the database as described here.

With the database constructs in place, we began to design the rules. We decided to implement the rules directly in Prolog, rather than in a specialized expert-system dialect interpreted by the Prolog engine. This provided more flexibility and was a better fit to the experimental nature of the project.

This is where Prolog's strength came into play. A rule was written simply as a series of Prolog clauses that tested resources in the appropriate combinations and produced a result: Either the combination of resources tested by a rule allowed configuration and installation of the card to proceed, or it revealed a conflict that would prevent proper operation and the process terminated with appropriate feedback to the user. Each rule could be designed totally independently from the others, since there is generally no data coupling between Prolog "functions." All we had to do was capture the essence of what constituted a well-configured system, express the rules in Prolog syntax, fire off the rules in sequence, and let them examine the data.

For example, a rule says, "If there is an I/O port that the system scan indicates is usable, and if Card Services thinks it's usable too, then it's a candidate for configuration of the card." Example 2 shows what this looks like in Prolog. In these three lines, Prolog is able to search the database of ioresource facts (where machine is the locus), find any that match the "usable" attribute, return the associated I/O port value in Port, then search the ioresource facts that have cardsrv as the locus, "usable" as the attribute, and that match the Port value. If these clauses succeed, then the Port is used in a final diagnostic routine try_io_port, which validates that the card will truly work with that value of I/O port. If that test succeeds, further logic is executed to do something useful with that I/O port value. If any of the three lines fails, then the rule fails, and the driver logic takes appropriate action.

This shortcuts a good deal of discussion of the actual mechanism Prolog uses for the exhaustive search capability (called "backtracking"), but conveys the power of using a nonprocedural language. To perform the same searching and matching task in C/C++ could take a half-dozen to dozens of lines of code, plus decisions as to data structure, variable naming, scoping, and the like.

Before the core resource analysis is executed, however, we thought it helpful to look for known and common conflicts in resource and system configuration, and report back to the user any conditions that we could detect early on that would prevent installation. Again exploiting Prolog's power for searching and pattern matching, we devised several-dozen complex rules defining conflicts, each of which took only a few lines to code.

We could, for example, detect if the memory manager was configured incorrectly. First, the front end scans upper-memory blocks to determine what upper-memory areas are excluded from the memory manager's control, and makes other independent tests of the usability of the memory and its status as known to Card Services. If there are no memory blocks excluded from the memory manager, this is simply expressed, as in Example 3(a). If Card Services is configured so that it might allocate a memory block that was not excluded from the memory manager, this is expressed, as in Example 3(b).

The front end is able to generate a "fingerprint" of the installed system, and Prolog searches for a match in a database of known problem platforms and incompatibilities. For example, the machine's identifier is obtained by the front end and stored as a fact in the database as "platform (XXXX)," where XXXX is the specific value of the fingerprint; we then have the set of rules in Example 4. In these four lines, we essentially say: "If the platform is platform_type_1, then if there is no memory free above upper-memory address 0xD000:0000, then there is a conflict."

Once you're familiar with the basic nature of Prolog programming, the modifiability and maintainability of this type of code is superior to traditional C/C++, where there would have been loops to search the data, boundary conditions, and a complete edit/build/test cycle for each change. With the Amzi! Prolog system and the architecture I've described, we were able to add and compile a new rule into the rule base in a matter of minutes, without having to touch any core code.

It was also useful to be able to call a Prolog program from a C++ superstructure, as well as call a C function, and have it look just like another Prolog clause. In Example 2, the try_io_port clause is actually a call to a C routine that takes an int value and performs low-level diagnostics on the card; again, a task much more reasonable to code in C and assembler than in Prolog. Note that these routines were in C and not C++, using the "extern C" linkage construct to force the C calling convention.

To do this is simple from the standpoint of integration with the logic server. A table of predicate names and their associated C function names, together with the number of arguments to be passed in from Prolog, is created in the C module. An initialization call is made to the logic server with a pointer to the table, and these predicates, written in C, are available to your Prolog program.

The C functions take one argument-a type, defined by the logic server-which allows function arguments passed in from Prolog to be extracted one-by-one. The return type is a Boolean truth value, indicating success or failure just as a native Prolog predicate returns.

Conclusion

The capability to integrate C/C++ and Prolog makes it possible for you to use the proper tool for the job. The Amzi! Prolog architecture allowed construction of a complex system requiring both procedural and nonprocedural tasks, and performed without any significant drawbacks. I did not, as is so often the case, have to see every problem as a nail because the only tool I had was a hammer.

Example 1: The portion of the database the expert system operates on.

ioresource(machine,0x200,available).
ioresource(machine,0x220,available).
ioresrouce(cardsrv,0x200,unavailable).

...
memresource(machine,0xD000,available).
memresource(machine,0xD100,available).
memresource(cardsrv,0xD000,available).

...
irqresource(machine,8,available).
irqresource(machine,9,available).
irqresource(cardsrv,8,unavailable).

...

Example 2: Typical rule implemented in Prolog.

iorule1 :-
     ioresource(machine,Port,usable),
     ioresource(cardsrv,Port,usable),
     try_io_port(Port),
     ...

Example 3: (a) No memory blocks excluded from the memory manager; (b) allocating a memory block not excluded from the memory manager.

(a)  conflict :- not memresource(memmgr,_,excluded)

(b)  conflict :- memresource(cardsvc,Mem,usable),
      not memresource(memmgr,Mem,excluded).

Example 4: A rule that detects a machine-specific conflict.

conflict :- platform(platform_type_1),
        not mem_rule.
mem_rule :- memresource(machine,Address,usable),
        Address > 0xCFFF.