Transcription
Building Expert Systems in PrologbyDennis Merritt
John Stannard on the first free ascent of Foops - 1967Published by:Amzi! inc.5861 Greentree RoadLebanon, OH 45036 U.S.A.phone 1-513-425-8050fax 1-513-425-8025e-mail info@amzi.comweb www.amzi.comBook Edition Copyright 1989 by Springer-Verlag.On-line Edition Copyright 2000 by Amzi! inc. All Rights Reserved.This document ("Work") is protected by copyright laws and international copyright treaties, as well as other intellectualproperty laws and treaties. You may use and distribute copies of this Work provided each copy of the Work is a true andcomplete copy, including all copyright and trademark notices, and each copy is accompanied by a copy of this notice.You may not distribute copies of this Work for profit either on a standalone basis or included as part of your ownproduct or work without written permission from Amzi! You may not charge any fees for copies of this work includingmedia or download fees. You may not include this Work as part of your own works. You may not rename, edit or createany derivative works from this Work. Contact Amzi! for additional licensing arrangements.Amzi! is a registered trademark and Logic Server, Active Prolog Tutor, Adventure in Prolog and the flying squirrel logoare trademarks of Amzi! inc.Last Updated: August 2000PDF version March 2001 edited, designed and compiled by Daniel L. Dudley (daniel.dudley@chello.no)ii
PrefaceWhen I compare the books on expert systems in my library with the production expert systems I know of, I note thatthere are few good books on building expert systems in Prolog. Of course, the set of actual production systems is a littlesmall for a valid statistical sample, at least at the time and place of this writing – here in Germany, and in the first daysof 1989. But there are at least some systems I have seen running in real life commercial and industrial environments,and not only at trade shows.I can observe the most impressive one in my immediate neighborhood. It is installed in the Telephone Shop of theGerman Federal PTT near the Munich National Theater, and helps configure telephone systems and small PBXs formostly private customers. It has a neat, graphical interface, and constructs and prices an individual telephoneinstallation interactively before the very eyes of the customer.The hidden features of the system are even more impressive. It is part of an expert system network with a distributedknowledge base that will grow to about 150 installations in every Telephone Shop throughout Germany. Each of themcan be updated individually overnight via Teletex to present special offers or to adapt the selection process to thehardware supplies currently available at the local warehouses.Another of these industrial systems supervises and controls in "soft" real time the excavators currently used in Tokyofor subway construction. It was developed on a Unix workstation and downloaded to a single board computer using areal time operating system. The production computer runs exactly the same Prolog implementation that was used forprogramming, too.And there are two or three other systems that are perhaps not as showy, but do useful work for real applications, such asoil drilling in the North Sea, or estimating the risks of life insurance for one of the largest insurance companies in theworld. What all these systems have in common is their implementation language: Prolog, and they run on "real life"computers like Unix workstations or minis like VAXs. Certainly this is one reason for the preference of Prolog incommercial applications.But there is one other, probably even more important advantage: Prolog is a programmer's and software engineer'sdream. It is compact, highly readable, and arguably the "most structured" language of them all. Not only has it doneaway with virtually all control flow statements, but even explicit variable assignment too!These virtues are certainly reason enough to base not only systems but textbooks on this language. Dennis Merritt hasdone this in an admirable manner. He explains the basic principles, as well as the specialized knowledge representationand processing techniques that are indispensable for the implementation of industrial software such as those mentionedabove. This is important because the foremost reason for the relative neglect of Prolog in expert system literature isprobably the prejudice that "it can be used only for backward chaining rules." Nothing is farther from the truth. Itsrelational data base model and its underlying unification mechanism adapt easily and naturally to virtually anyprogramming paradigm one cares to use. Merritt shows how this works using a copious variety of examples. His bookwill certainly be of particular value for the professional developer of industrial knowledge-based applications, as well asfor the student or programmer interested in learning about or building expert systems. I am, therefore, happy to haveserved as his editor.Peter H. SchnuppMunich, January 1989Building Expert Systems in Prologiii
AcknowledgementsA number of people have helped make this book possible. They include Dave Litwack and Bill Linn of Cullinet whoprovided the opportunity and encouragement to explore these ideas. Further thanks goes to Park Gerald and the BostonComputer Society, sounding boards for many of the programs in the book. Without the excellent Prolog products fromCogent (now Amzi!), AAIS, Arity, and Logic Programming Associates none of the code would have been developed. Aspecial thanks goes to Peter Gable and Paul Weiss of Arity for their early help and Allan Littleford, provider of bothCogent Prolog and feedback on the book. Jim Humphreys of Suffolk University gave the most careful reading of thebook, and advice based on years of experience. As have many other Mac converts, I feel compelled to mention myMacintosh SE, Microsoft Word and Cricket Draw for creating an enjoyable environment for writing books. And finallywithout both the technical and emotional support of Mary Kroening the book would not have been started or finished.iv
Table of ContentsPreface .iiiAcknowledgements .iv1 Introduction.11.1 Expert Systems . 11.2 Expert System Features. 3Goal-Driven Reasoning .3Uncertainty.4Data Driven Reasoning .4Data Representation.5User Interface .6Explanations .71.3 Sample Applications. 71.4 Prolog . 81.5 Assumptions. 82 Using Prolog's Inference Engine.92.1 The Bird Identification System. 9Rule formats .9Rules about birds.10Rules for hierarchical relationships.10Rules for other relationships.112.2 User Interface. 13Attribute Value pairs .13Asking the user .13Remembering the answer .14Multi-valued answers.14Menus for the user.15Other enhancements .162.3 A Simple Shell . 16Command loop .17A tool for non-programmers.192.4 Summary . 19Exercises. 193 Backward Chaining with Uncertainty.213.1 Certainty Factors . 21An Example .21Rule Uncertainty .22User Uncertainty .22Combining Certainties .23Properties of Certainty Factors.233.2 MYCINs Certainty Factors. 24Determining Premise CF .24Building Expert Systems in Prologv
Combining Premise CF and Conclusion CF.24Premise Threshold CF.25Combining CFs .253.3 Rule Format. 263.4 The Inference Engine . 27Working Storage .27Find a Value for an Attribute.27Attribute Value Already Known.28Ask User for Attribute Value .28Deduce Attribute Value from Rules .28Negation .303.5 Making the Shell. 30Starting the Inference .313.6 English-like Rules. 32Exercises. 334 Explanation .35Value of Explanations to the User .35Value of Explanations to the Developer .35Types of Explanation .364.1 Explanation in Clam . 36Tracing.38How Explanations.39Why Questions .414.2 Native Prolog Systems . 43Exercises. 465 Forward Chaining .475.1 Production Systems . 475.2 Using Oops. 485.3 Implementation. 525.4 Explanations for Oops . 565.5 Enhancements . 565.6 Rule Selection . 57Generating the conflict set.57Time stamps .585.7 LEX. 58Changes in the Rules .59Implementing LEX .595.8 MEA. 61Exercises. 626 Frames.656.1 The Code. 666.2 Data Structure . 66viTable of Contents
6.3 The Manipulation Predicates. 686.4 Using Frames . 746.5 Summary . 75Exercises. 757 Integration .777.1 Foops (Frames and Oops) . 77Instances .77Rules for frinsts.79Adding Prolog to Foops .807.2 Room Configuration . 81Furniture frames .82Frame Demons .83Initial Data.84Input Data .85The Rules .86Output Data .897.3 A Sample Run . 907.4 Summary . 91Exercises. 918 Performance.938.1 Backward Chaining Indexes. 938.2 Rete Match Algorithm. 94Network Nodes .95Network Propagation .96Example of Network Propagation .97Performance Improvements .998.3 The Rete Graph Data Structures. 1008.4 Propagating Tokens . 1018.5 The Rule Compiler . 1038.6 Integration with Foops . 1088.7 Design Tradeoffs . 109Exercises. 1099 User Interface.1119.1 Object Oriented Window Interface . 1119.2 Developer's Interface to Windows . 1119.3 High-Level Window Implementation. 114Message Passing .115Inheritance .1159.4 Low-Level Window Implementation. 117Exercises. 120Building Expert Systems in Prologvii
10 Two Hybrids .12110.1 CVGEN. 12110.2 The Knowledge Base . 122Rule for parameters.122Rules for derived information.123Questions for the user .124Default rules.124Rules for edits.125Static information .12510.3 Inference Engine . 12610.4 Explanations. 12710.5 Environment . 12810.6 AIJMP. 12910.7 Summary . 130Exercises. 13011 Prototyping.13111.1 The Problem. 13111.2 The Sales Advisor Knowledge Base . 131Qualifying.132Objectives - Benefits - Features .132Situation Analysis .133Competitive Analysis .133Miscellaneous Advice .134User Queries.13411.3 The Inference Engine . 13511.4 User Interface. 13611.5 Summary . 138Exercises. 13812 Rubik's Cube .13912.1 The Problem. 13912.2 The Cube. 14012.3 Rotation . 14212.4 High Level Rules . 14212.5 Improving the State . 14312.6 The Search. 14412.7 More Heuristics . 14512.8 User Interface. 14512.9 On the Limits of Machines. 146Exercises. 146viiiTable of Contents
Appendices - Full Source Code .147A Native.149Birds Knowledgebase (birds.nkb). 149Native Shell (native.pro) . 153B Clam.157Car Knowledgebase (car.ckb) . 157Birds Knowledgebase (birds.ckb). 158Clam Shell (clam.pro). 163Build Rules (bldrules.pro) . 176C Oops .179Room Knowledgebase (room.okb). 179Animal Knowledgebase (animal.okb) . 184Oops Interpreter (oops.pro). 187D Foops.193Room Knowledgebase (room.fkb). 193Foops (foops.pro) . 200E Rete-Foops .211Room Knowledgebase (room.rkb). 211Rete Compiler (retepred.pro) . 218Rete Runtime (retefoop.pro). 225F Windows.239Windows Demonstration (windemo.pro) . 239Windows (windows.pro) . 243G Rubik.273Cube Solver (rubik.pro) . 273Cube Display (rubdisp.pro). 286Cube Entry (rubedit.pro). 289Move History (rubhist.pro) . 291Moves and Rotations (rubmov.pro) . 293Rubik Help (rubhelp.pro) . 296Rubik Data (rubdata.pro). 297Building Expert Systems in Prologix
1 IntroductionOver the past several years there have been many implementations of expert systems usingvarious tools and various hardware platforms, from powerful LISP machine workstationsto smaller personal computers.The technology has left the confines of the academic world and has spread through manycommercial institutions. People wanting to explore the technology and experiment with ithave a bewildering selection of tools from which to choose. There continues to be a debateas to whether or not it is best to write expert systems using a high-level shell, an AIlanguage such as LISP or Prolog, or a conventional language such as C.This book is designed to teach you how to build expert systems from the inside out. Itpresents the various features used in expert systems, shows how to implement them inProlog, and how to use them to solve problems.The code presented in this book is a foundation from which many types of expert systemscan be built. It can be modified and tuned for particular applications. It can be used forrapid prototyping. It can be used as an educational laboratory for experimenting withexpert system concepts.1.1 Expert SystemsExpert systems are computer applications which embody some non-algorithmic expertisefor solving certain types of problems. For example, expert systems are used in diagnosticapplications servicing both people and machinery. They also play chess, make financialplanning decisions, configure computers, monitor real time systems, underwrite insurancepolicies, and perform many other services which previously required human ledgeBaseSystemEngineerWorkingStorageFigure 1.1 Expert system components and human interfacesExpert systems have a number of major system components and interface with individualsin various roles. These are illustrated in figure 1.1. The major components are:Building Expert Systems in Prolog1
Knowledge base – a declarative representation of
PDF version March 2001 edited, designed and compiled by Daniel L. Dudley (daniel.dudley@chello.no) . there are few good books on building expert systems in Prolog. Of course, the set of actual production systems is a little small for a valid statistical sample, at least at the time and place of this writing - here in Germany, and in the .
