home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / compsrcs / unix / volume03 / infer < prev    next >
Encoding:
Internet Message Format  |  1988-09-11  |  22.4 KB
  1. From: talcott!seismo!gatech!itm!danny
  2. Newsgroups: mod.sources
  3. Subject: infer - inference engine
  4. Approved: jpn@panda.UUCP
  5.  
  6. Mod.sources:  Volume 3, Issue 104
  7. Submitted by: itm!danny (Daniel S. Cox)
  8.  
  9.     The following is a shell archive containing "infer" which is a
  10. re-write of George Hageman's routines "rulecomp" and "inference".
  11.  
  12.     Enjoy!
  13.  
  14.                                     Daniel S. Cox
  15.                                     ihnp4!akgua!itm!danny
  16. -------------------- Cut Here --------------------------------------
  17.  
  18. ############################################################
  19. #
  20. #                       infer.ar
  21. #
  22. # To extract the files from this shell archive file
  23. # simply create a directory for this file
  24. # and move the archive file to it, strip off these comments
  25. # and enter the command
  26. #
  27. # sh filename
  28. #
  29. # Do not use csh
  30. # The files will be extracted automatically
  31. #
  32. ############################################################
  33.  
  34. echo "Extracting README <-- infer.ar"
  35. cat << \===README=== > README
  36.     infer --- an inference engine written in C, based on George
  37. Hageman's programs "rulecomp", and "inference".
  38.  
  39.     Unfortunatly, not much is left of the original sources.  I began
  40. by copying the expert.h file into infer.h, but now, the only things
  41. left from the original are some names, and the keywords it recognizes.
  42.  
  43.     Now, down to building the thing.  First, edit the Makefile
  44. and modify the BIN and CFLAGS variables to be compatible with your
  45. system.  Type "make" and stand well back.  To crank it up type
  46. "infer file" where file contains some rules.  The knowledge base
  47. named "animal" is included, and is a copy of the original.  Infer
  48. understands one option, "-v" for verbose.  It will display each
  49. line it compiles to stdout, and display each rule it considers
  50. as it contorts.  It's not espcially useful output, but, boy, is
  51. it verbose!
  52.  
  53.     As it asks a question, infer understands [YyTt] for TRUE,
  54. [NnFf] for FALSE, [Qq] for quit, and [Ww] for why.  The why only
  55. shows rules proven TRUE, and the rule under consideration.
  56.  
  57.     If infer detects circular logic, it will attempt to display
  58. each rule in the circle.  This should help isolate things pretty
  59. well.
  60.  
  61.     Error messages are intended to be self-explanatory.  It mostly
  62. complains about unopenable files, and improperly formed lines.
  63.  
  64.     If you find usefulness in this program, drop me a line.  I'd
  65. be interested in knowing where it's used.
  66.  
  67.     If you need to contact me, my UUCP path is:
  68.         ihnp4!akgua!itm!danny
  69.  
  70.     US Snail is:
  71.         In Touch
  72.         796 West Peachtree St. NE
  73.         Atlanta, GA 30308
  74.         ATTN Daniel S. Cox
  75.         (404) 881-0550
  76.  
  77.     IF I think
  78.     THENHYP I am
  79.  
  80. Daniel (Call me Danny) S. Cox
  81. ===README===
  82. echo "Extracting Makefile <-- infer.ar"
  83. cat << \===Makefile=== > Makefile
  84. CFLAGS = -O
  85. LDFLAGS = -n
  86. OBJECTS = infer.o compile.o
  87. SOURCES = infer.c compile.c
  88. BIN = /u/danny/bin
  89.  
  90. infer: $(OBJECTS)
  91.     $(CC) $(OBJECTS) $(LDFLAGS) -o infer
  92.  
  93. $(OBJECTS): infer.h
  94.  
  95. clean:
  96.     rm -f $(OBJECTS) core
  97.  
  98. clobber: clean
  99.     rm -f infer
  100.  
  101. install: infer
  102.     cp infer $(BIN)/infer
  103.     strip $(BIN)/infer
  104.  
  105. lint:
  106.     lint $(SOURCES) >fluff
  107. ===Makefile===
  108. echo "Extracting infer.c <-- infer.ar"
  109. cat << \===infer.c=== > infer.c
  110. /* infer --- inference engine */
  111.  
  112. # include <stdio.h>
  113. # include <ctype.h>
  114. # include "infer.h"
  115.  
  116. # define TRUTHVAL(E)    ((E->type & NOT) ? (E->str->val == TRUE) ? FALSE : TRUE : (E->str->val))
  117.  
  118. char *progname;
  119. RULE_T *Rule[MAXRULE];
  120. int nrules = 0;
  121. RULE_T *why[MAXWHY];
  122. int nwhy = 0;
  123. STR *SP = 0;
  124. int verbose;
  125.  
  126. main (argc, argv)
  127. int argc;
  128. char **argv;
  129. {
  130.     FILE *fp;
  131.  
  132.     progname = argv[0];
  133.     while (argv[1][0] == '-') { /* check for options */
  134.     if (argv[1][1] == 'v')  /* I know only one */
  135.         verbose++;
  136.     else
  137.         fprintf (stderr, "%s: unknown arg \"%s\"\n", progname,
  138.           argv[1]);
  139.     argc--;
  140.     argv++;
  141.     }
  142.  
  143.     if (argc !=2) {
  144.     fprintf (stderr, "Usage: %s [-v] file\n", progname);
  145.     exit (1);
  146.     }
  147.  
  148.     if ((fp = fopen (argv[1], "r")) == NULL) {
  149.     fprintf (stderr, "%s: can't open %s (%s)\n", progname, argv[1],
  150.       sys_errlist[errno]);
  151.     exit (1);
  152.     }
  153.  
  154.     compile (fp);
  155.     fclose (fp);
  156.     return (infer ());
  157. }
  158.  
  159. /* infer --- inference engine */
  160.  
  161. infer ()
  162. {
  163.     register int i;
  164.     int proved;
  165.  
  166.     for (i = 0; i < nrules; i++) {      /* verify each CON */
  167.     if (Rule[i]->con == 0) {
  168.         fprintf (stderr, "%s: RULE has no THENs:\n", progname);
  169.         prrule (Rule[i], stderr);
  170.         exit (1);
  171.     }
  172.     if (TRUTHVAL (Rule[i]->con) == TRUE)
  173.         continue;
  174.  
  175.     if (verify (Rule[i]) == TRUE) {
  176.         register ELEMENT_T *e;
  177.         for (e = Rule[i]->con; e; e = e->next) {
  178.         if (e->type & ROUTINE) {
  179.             if (e->str->val == TRUE)
  180.             continue;
  181.             if (run (e) == TRUE) {
  182.             e->str->val = TRUE;
  183.             if (e->type & HYP) {
  184.                 printf ("Conclusion\n");
  185.                 return (0);
  186.             }
  187.             }
  188.             else {
  189.             e->str->val = FALSE;
  190.             }
  191.         }
  192.         else {
  193.             e->str->val = TRUE;
  194.             proved = TRUE;
  195.             printf ("I infer that: %s\n", e->str->p);
  196.             if (e->type & HYP) {
  197.             printf ("Conclusion\n");
  198.             return (0);
  199.             }
  200.         }
  201.         }
  202.     }
  203.     }
  204.     if (proved == FALSE) {
  205.     printf ("I can't prove anything!!!\n");
  206.     return (1);
  207.     }
  208.     return (0);
  209. }
  210.  
  211. /* verify --- verify a CON.  May be called recursivly */
  212.  
  213. verify (rule)
  214. register RULE_T *rule;
  215. {
  216.     register ELEMENT_T *e;
  217.     register int i;
  218.  
  219.     pushwhy (rule);
  220.     if (rule->con->str->val == TRUE) {
  221.     popwhy ();
  222.     return (TRUE);
  223.     }
  224.  
  225.     if (verbose)
  226.     prrule (rule, stdout);
  227.  
  228.     if (rule->ant == 0) {
  229.     fprintf (stderr, "%s: RULE has no IFs:\n", progname);
  230.     prrule (rule, stderr);
  231.     popwhy ();
  232.     return (TRUE);
  233.     }
  234.  
  235.     for (e = rule->ant; e; e = e->next) {   /* for each ANT */
  236.     for (i = 0; i < nrules; i++)
  237.         if (e->str == Rule[i]->con->str)    /* this ANT is a CON */
  238.         break;
  239.     if (i == nrules) {      /* NOT a CON */
  240.         if (prove (e) == TRUE)
  241.         continue;
  242.         else {
  243.         popwhy ();
  244.         return (FALSE);
  245.         }
  246.     }
  247.     else {
  248.         int anytrue = 0;
  249.         for (i = 0; i < nrules; i++) {
  250.         if (e->str == Rule[i]->con->str) {  /* match */
  251.             int ret;
  252.             if (Rule[i]->vfy == 1) {
  253.             fprintf (stderr, "%s: Circular logic in Rules! Rules are:\n", progname);
  254.             prcirc ();
  255.             exit (1);
  256.             }
  257.             Rule[i]->vfy = 1;
  258.             ret = verify (Rule[i]);
  259.             Rule[i]->vfy = 0;
  260.             if (ret == TRUE) {
  261.             register ELEMENT_T *f;
  262.             anytrue++;
  263.             for (f = Rule[i]->con; f; f = f->next) {
  264.                 if (f->str->val == UNKNOWN) {
  265.                 printf ("I infer that: %s\n", f->str->p);
  266.                 f->str->val = TRUE;
  267.                 }
  268.             }
  269.             if (prove (e) == TRUE)
  270.                 break;
  271.             else {
  272.                 popwhy ();
  273.                 return (FALSE);
  274.             }
  275.             }
  276.         }
  277.         }
  278.         if (!anytrue)
  279.         if (e->type & NOT)
  280.             continue;
  281.         else {
  282.             popwhy ();
  283.             return (FALSE);
  284.         }
  285.         else
  286.         if (e->type & NOT) {
  287.             popwhy ();
  288.             return (FALSE);
  289.         }
  290.         else
  291.             continue;
  292.     }
  293.     }               /* don't pop the why stack if TRUE */
  294.     return (TRUE);
  295. }
  296.  
  297. /* prove --- prove this ANT (may be already proven) */
  298.  
  299. prove (e)
  300. ELEMENT_T *e;
  301. {
  302.     if (e->str->val != UNKNOWN)
  303.     return (TRUTHVAL (e));
  304.     if (e->type & ROUTINE)
  305.     return (run (e));
  306.     else
  307.     return (askval (e));
  308. }
  309.  
  310. /* askval --- get truth from user */
  311.  
  312. askval (e)
  313. register ELEMENT_T *e;
  314. {
  315.     char line[80];
  316.     register int value;
  317.     
  318.     value = UNKNOWN;
  319.     for (;;) {
  320.     printf ("Is the following statement true?\n");
  321.     printf ("%s : ", e->str->p);
  322.     if (fgets (line, sizeof (line), stdin) == NULL)
  323.         *line = 'q';
  324.     if (isupper (*line))
  325.         *line = tolower (*line);
  326.     switch (*line) {
  327.     case 'y':
  328.     case 't':
  329.         value = TRUE;
  330.         break;
  331.     case 'n':
  332.     case 'f':
  333.         value = FALSE;
  334.         break;
  335.     case 'q':
  336.         printf ("OK, Bye!\n");
  337.         exit (0);
  338.         break;
  339.     case 'w':
  340.         showwhy ();
  341.         continue;
  342.     }
  343.     if (value != UNKNOWN)
  344.         break;
  345.     printf ("How about typeing t/f/y/n?\n");
  346.     }
  347.     e->str->val = value;
  348.     return (TRUTHVAL (e));
  349. }
  350.  
  351. /* run --- execute this string */
  352.  
  353. run (e)
  354. register ELEMENT_T *e;
  355. {
  356.     register int value, ret;
  357.     
  358.     if ((ret = system (e->str->p)) < 0) {
  359.     printf ("%s: can't execute %s (%s) returning TRUE\n", progname,
  360.       e->str->p, sys_errlist[errno]);
  361.     value = TRUE;
  362.     }
  363.     else if (ret == 0)
  364.     value = TRUE;
  365.     else
  366.     value = FALSE;
  367.  
  368.     e->str->val = value;
  369.     return (TRUTHVAL (e));
  370. }
  371.  
  372. /* prrule --- print this rule in a readable form */
  373.  
  374. prrule (rule, fp)
  375. register RULE_T *rule;
  376. FILE *fp;
  377. {
  378.     register ELEMENT_T *e;
  379.     char *prval (), *prtype ();
  380.  
  381.     for (e = rule->ant; e; e = e->next)
  382.     fprintf (fp, "%s %s (%s)\n", prtype (e->type, "IF"), e->str->p,
  383.       prval (e));
  384.     for (e = rule->con; e; e = e->next)
  385.     fprintf (fp, "%s %s (%s)\n", prtype (e->type, "THEN"), e->str->p,
  386.       prval (e));
  387.     fprintf (fp, "\n");
  388. }
  389.  
  390. /* prval --- return the char representation of this value */
  391.  
  392. char *
  393. prval (e)
  394. register ELEMENT_T *e;
  395. {
  396.  
  397.     if (e->str->val == UNKNOWN)
  398.     return ("UNKNOWN");
  399.     else if (e->str->val == TRUE || e->str->val == FALSE) {
  400.     if (TRUTHVAL (e) == TRUE)
  401.         return ("TRUE");
  402.     else
  403.         return ("FALSE");
  404.     }
  405.     else
  406.     return ("BADVAL");
  407. }
  408.  
  409. /* prtype --- return the char representation of this type */
  410.  
  411. char *
  412. prtype (type, word)
  413. register short type;
  414. register char *word;
  415. {
  416.     static char str_type[20];
  417.  
  418.     strcpy (str_type, word);
  419.     if (type & NOT)
  420.     strcat (str_type, "NOT");
  421.     if (type & ROUTINE)
  422.     strcat (str_type, "RUN");
  423.     if (type & HYP)
  424.     strcat (str_type, "HYP");
  425.     return (str_type);
  426. }
  427.  
  428. /* pushwhy --- push this rule onto the "why" stack */
  429.  
  430. pushwhy (r)
  431. register RULE_T *r;
  432. {
  433.     if (nwhy >= MAXWHY) {
  434.     fprintf (stderr, "%s: blew why stack!\n", progname);
  435.     exit (1);
  436.     }
  437.     why[nwhy++] = r;
  438. }
  439.  
  440. /* popwhy --- pop a value off of the "why" stack */
  441.  
  442. popwhy ()
  443. {
  444.     if (--nwhy < 0) {
  445.     fprintf (stderr, "%s: why stack underflow!\n", progname);
  446.     exit (1);
  447.     }
  448. }
  449.  
  450. /* showwhy --- print the details of the "why" stack */
  451.  
  452. showwhy ()
  453. {
  454.     register int i;
  455.     
  456.     for (i = 0; i < nwhy; i++)
  457.     prrule (why[i], stdout);
  458. }
  459.  
  460. /* prcirc --- print the details of the circular loop */
  461.  
  462. prcirc ()
  463. {
  464.     register int i;
  465.     
  466.     for (i = 0; i < nrules; i++)
  467.     if (Rule[i]->vfy == 1)
  468.         prrule (Rule[i], stderr);
  469. }
  470. ===infer.c===
  471. echo "Extracting compile.c <-- infer.ar"
  472. cat << \===compile.c=== > compile.c
  473. /* compile --- compile the rules into the internal form */
  474.  
  475. # include <stdio.h>
  476. # include <ctype.h>
  477. # include "infer.h"
  478.  
  479. int Curline;
  480. int State;
  481.  
  482. compile (fp)
  483. register FILE *fp;
  484. {
  485.     register int key;
  486.     char line[STRSIZE];
  487.     STR *savestr ();
  488.  
  489.     Curline = 0;
  490.     State = ANT;
  491.     rulealloc ();
  492.     while (fgets (line, sizeof (line), fp)) {
  493.     Curline++;
  494.     squeeze (line, '\n');
  495.     stripbl (line);
  496.     if (verbose)
  497.         printf ("%4d    %s\n", Curline, line);
  498.     key = getkey (line);
  499.     if (key == NONE)
  500.         fprintf (stderr, "%s: no keyword found on line %d\n",
  501.           progname, Curline);
  502.     else if (key == COMMENT)
  503.         ;
  504.     else
  505.         push (key, savestr (line));
  506.     }
  507. }
  508.  
  509. /* newstate --- if switching from CON to ANT, start a new rule */
  510.  
  511. newstate (new)
  512. register int new;
  513. {
  514.     if (new != ANT && new != CON) {     /* paranoia */
  515.     fprintf (stderr, "%s: bad new val: %d\n", new);
  516.     exit (1);
  517.     }
  518.  
  519.     if (State != new) {
  520.     if (State == CON)
  521.         rulealloc ();
  522.     State = new;
  523.     }
  524. }
  525.  
  526. /* push --- add an element to this rule */
  527.  
  528. push (type, ptr)
  529. register int type;
  530. register STR *ptr;
  531. {
  532.     register ELEMENT_T *e, *last;
  533.  
  534.     if (ptr == 0)   /* keyword only, ignore */
  535.     return;
  536.     e = (ELEMENT_T *) emalloc ((unsigned) sizeof (ELEMENT_T));
  537.     e->str = ptr;
  538.     e->type = type;
  539.     e->next = 0;
  540.     if (State == CON) {
  541.     if (Rule[nrules-1]->con == 0) /* first element */
  542.         Rule[nrules-1]->con = e;
  543.     else                          /* place on end */
  544.         for (last = Rule[nrules-1]->con; last; last = last->next)
  545.         if (last->next == 0) {
  546.             last->next = e;
  547.             break;
  548.         }
  549.     }
  550.     else {
  551.     if (Rule[nrules-1]->ant == 0)
  552.         Rule[nrules-1]->ant = e;
  553.     else
  554.         for (last = Rule[nrules-1]->ant; last; last = last->next)
  555.         if (last->next == 0) {
  556.             last->next = e;
  557.             break;
  558.         }
  559.     }
  560. }
  561.  
  562. /* savestr --- skip 1st word, save rest of line in str buffer */
  563.  
  564. STR *
  565. savestr (line)
  566. char *line;
  567. {
  568.     register char *s;
  569.     register STR *sp;
  570.  
  571.     for (s = line; *s; s++)     /* skip to 1st space */
  572.     if (*s == ' ')
  573.         break;
  574.  
  575.     while (isspace (*s))        /* skip to 1st non-space */
  576.     s++;
  577.  
  578.     if (*s == 0) {
  579.     fprintf (stderr, "%s: line %d has nothing but a keyword\n",
  580.       progname, Curline);
  581.     return (0);
  582.     }
  583.  
  584.     for (sp = SP; sp; sp = sp->next)    /* is string already present? */
  585.     if (strcmp (sp->p, s) == 0)
  586.         return (sp);
  587.  
  588.     sp = (STR *) emalloc ((unsigned) sizeof (STR)); /* new string */
  589.     sp->p = emalloc ((unsigned) strlen (s)+1);
  590.     strcpy (sp->p, s);
  591.     sp->val = UNKNOWN;
  592.     sp->next = SP;      /* place at head */
  593.     SP = sp;
  594.     return (sp);
  595. }
  596.  
  597. /* getkey --- determine the keyword on this line */
  598.  
  599. getkey (line)
  600. char *line;
  601. {
  602.     register int i;
  603.     register char *s, *p;
  604.     char word[20];
  605.     static struct {
  606.     char    *name;
  607.     short   type;
  608.     short   newstate;
  609.     } keytab[] = {              /* these are sorted based on frequency */
  610.     "THEN", STRING, CON,    /* of use in 3 files I had access to */
  611.     "AND", STRING, ANT,     /* change at will */
  612.     "IF", STRING, ANT,
  613.     "ANDRUN", ROUTINE, ANT,
  614.     "ANDNOT", STRING|NOT, ANT,
  615.     "THENHYP", STRING|HYP, CON,
  616.     "IFRUN", ROUTINE, ANT,
  617.     "ANDIF", STRING, ANT,
  618.     "IFNOT", STRING|NOT, ANT,
  619.     "THENRUNHYP", ROUTINE|HYP, CON,
  620.     "THENRUN", ROUTINE, CON,
  621.     "ANDIFRUN", ROUTINE, ANT,
  622.     "ANDNOTRUN", ROUTINE|NOT, ANT,
  623.     "IFNOTRUN", ROUTINE|NOT, ANT,
  624.     "ANDTHEN", STRING, CON,
  625.     "ANDTHENHYP", STRING|HYP, CON,
  626.     "ANDTHENRUN", ROUTINE, CON,
  627.     "ANDTHENRUNHYP", ROUTINE|HYP, CON,
  628.     0,  0, 0
  629.     };
  630.  
  631.     if (line[0] == COMMENT_CHAR)
  632.     return (COMMENT);
  633.  
  634.     for (p = word, s = line; *s; s++) /* copy chars into word */
  635.     if (isupper (*s))
  636.         *p++ = *s;
  637.     else
  638.         break;
  639.     *p = 0;
  640.     
  641.     for (i = 0; keytab[i].name; i++)    /* look for match */
  642.     if (strcmp (word, keytab[i].name) == 0) {
  643.         newstate (keytab[i].newstate);
  644.         return (keytab[i].type);
  645.     }
  646.  
  647.     return (NONE);
  648. }
  649.  
  650. /* squeeze --- squeeze all c from s */
  651.  
  652. squeeze (s, c)
  653. register char *s;
  654. register char c;
  655. {
  656.     register char *p;
  657.  
  658.     for (p = s; *s; s++)
  659.     if (*s != c)
  660.         *p++ = *s;
  661.     *p = '\0';
  662. }
  663.  
  664. /* stripbl --- remove trailing blanks from s */
  665.  
  666. stripbl (s)
  667. register char *s;
  668. {
  669.     register char *p;
  670.  
  671.     for (p = s; *s; s++)
  672.     if (*s != ' ')
  673.         p = s+1;
  674.  
  675.     *p = 0;
  676. }
  677.  
  678. /* rulealloc --- allocate a new rule, and advance the pointer */
  679.  
  680. rulealloc ()
  681. {
  682.     if (nrules >= MAXRULE) {
  683.     fprintf (stderr, "%s: too many rules!\n", progname);
  684.     exit (1);
  685.     }
  686.  
  687.     Rule[nrules] = (RULE_T *) emalloc ((unsigned) sizeof (RULE_T));
  688.     Rule[nrules]->ant = 0;
  689.     Rule[nrules]->con = 0;
  690.     Rule[nrules]->vfy = 0;
  691.     nrules++;
  692. }
  693.  
  694. /* emalloc --- call malloc and check return */
  695.  
  696. char *
  697. emalloc (n)
  698. unsigned n;
  699. {
  700.     char *p, *malloc ();
  701.  
  702.     if ((p = malloc (n)) == NULL) {
  703.     fprintf (stderr, "%s: Out of memory!\n", progname);
  704.     exit (1);
  705.     }
  706.     return (p);
  707. }
  708. ===compile.c===
  709. echo "Extracting animal <-- infer.ar"
  710. cat << \===animal=== > animal
  711. ! THIS IS THE KNOWLEDGE BASE FOR THE
  712. ! ANIMAL CLASIFICATION EXPERT
  713. !
  714. IF ANIMAL HAS FEATHERS
  715. ANDIF ANIMAL LAYS EGGS
  716. THEN ANIMAL IS BIRD
  717. !
  718. IFNOT ANIMAL IS BIRD
  719. THEN ANIMAL IS MAMMAL
  720. !
  721. IF ANIMAL IS MAMMAL
  722. AND ANIMAL EATS MEAT
  723. THEN ANIMAL IS CARNIVORE
  724. !
  725. IF ANIMAL IS CARNIVORE
  726. AND ANIMAL HAS POINTED TEETH
  727. AND ANIMAL HAS RETRACTABLE CLAWS
  728. AND ANIMAL HAS FORWARD POINTING EYES
  729. THEN ANIMAL IS CAT
  730. !
  731. IF ANIMAL IS MAMMAL
  732. ANDNOT ANIMAL IS CARNIVORE
  733. AND ANIMAL HAS HOOFS
  734. THEN ANIMAL IS UNGULATE
  735. !
  736. IF ANIMAL IS CAT
  737. AND ANIMAL HAS TAWNY COLOR
  738. AND ANIMAL HAS DARK SPOTS
  739. THENHYP ANIMAL IS CHEETA
  740. !
  741. IF ANIMAL IS CAT
  742. AND ANIMAL HAS TAWNY COLOR
  743. AND ANIMAL HAS BLACK STRIPES
  744. THENHYP ANIMAL IS TIGER
  745. !
  746. IF ANIMAL IS CAT
  747. AND ANIMAL IS SMALL
  748. AND ANIMAL IS DOMESTICATED
  749. AND ANIMAL MOSTLY CATCHES MICE
  750. AND ANIMAL LOVES WARM LAPS
  751. THENHYP ANIMAL IS A HOUSE CAT
  752. !
  753. IF ANIMAL IS UNGULATE
  754. AND ANIMAL HAS LONG NECK
  755. AND ANIMAL HAS LONG LEGS
  756. AND ANIMAL HAS DARK SPOTS
  757. THENHYP ANIMAL IS GIRAFFE
  758. !
  759. IF ANIMAL IS BIRD
  760. ANDNOT ANIMAL FLIES
  761. ANDNOT ANIMAL SWIMS
  762. AND ANIMAL HAS LONG NECK
  763. AND ANIMAL IS BLACK AND WHITE
  764. THENHYP ANIMAL IS OSTRICH
  765. !
  766. IF ANIMAL IS UNGULATE
  767. AND ANIMAL HAS BLACK STRIPES
  768. THENHYP ANIMAL IS ZEBRA
  769. !
  770. IF ANIMAL IS UNGULATE
  771. AND ANIMAL HAS HORNS
  772. THENHYP ANIMAL IS COW
  773. !
  774. IF ANIMAL IS BIRD
  775. ANDNOT ANIMAL FLIES
  776. AND ANIMAL SWIMS
  777. AND ANIMAL IS BLACK AND WHITE
  778. THENHYP ANIMAL IS PENGUIN
  779. !
  780. IF ANIMAL IS BIRD
  781. AND ANIMAL FLIES
  782. AND ANIMAL FLIES WELL
  783. AND ANIMAL HAS WEBBED FEET
  784. ANDNOT ANIMAL HAS FLAT BILL
  785. THENHYP ANIMAL IS ALBATROS
  786. !
  787. IF ANIMAL IS BIRD
  788. AND ANIMAL FLIES
  789. AND ANIMAL FLIES WELL
  790. AND ANIMAL HAS WEBBED FEET
  791. AND ANIMAL HAS FLAT BILL
  792. THENHYP ANIMAL IS DUCK
  793. !
  794. !
  795. !
  796. IFNOT ANIMAL IS CHEETA
  797. IFNOT ANIMAL IS TIGER
  798. IFNOT ANIMAL IS A HOUSE CAT
  799. IFNOT ANIMAL IS GIRAFFE
  800. IFNOT ANIMAL IS OSTRICH
  801. IFNOT ANIMAL IS ZEBRA
  802. IFNOT ANIMAL IS PENGUIN
  803. IFNOT ANIMAL IS ALBATROS
  804. IFNOT ANIMAL IS DUCK
  805. IFNOT ANIMAL IS COW
  806. THENHYP THIS ANIMAL IS NOT WITHIN MY KNOWLEDGE
  807. ===animal===
  808. echo "Extracting rewrite <-- infer.ar"
  809. cat << \===rewrite=== > rewrite
  810.     Not long ago, George Hageman posted an inference engine written
  811. in C to the net.  Infer is a re-write of "rulecomp" and "inference".
  812.  
  813.     My goals in the rewrite were: remove restrictions, centralize I/O,
  814. simplify, enhance, and (if I may coin a word) Unixfy.
  815.  
  816. REMOVING RESTRICTIONS:
  817.     Well, the best way to do that was to malloc everything.  The concept
  818. of "rule" has changed from value-string pair to a group of ANTECEDENTS
  819. and a group of CONSEQUENTS.  Thus, with the original 500 rules, there
  820. could be a max of 500 ANTs and CONs with 1 rule used to seperate each.
  821. It is roughly one rule per line, plus overhead.  With the new, 1000
  822. rules is 1000 statement groups.  Beyond that, there are no limitations
  823. on the number of strings.  The maximum string size is 512 - length of
  824. keyword - 1 for the space.
  825.  
  826.     The other restriction removed is the need for a seperate compiler,
  827. and the intermediate file that it produces.  I realize that one
  828. goal of Mr. Hageman was to keep the two modules seperate, and therefore
  829. smaller, but I'd rather keep the two together and eliminate the extra
  830. file.  This also simplifies the expert system which wishes to build
  831. it's own rule-set, and run the engine on it.
  832.  
  833. CENTRALIZING I/O:
  834.     In both originals, input and output were spread among all source
  835. files.  To effect a change, one had to discover all locations that
  836. performed the operation.  For example, to make "rulecomp" quiet, I
  837. had to change lines in three different source files.
  838.  
  839. SIMPLIFYING:
  840.     Where there were two programs, now there is one.  There
  841. are no more stacks (except for the crude "WHY" interface).  I/O all
  842. happens in one place for each operation (not true for output).
  843. There was a large amount of code duplication in the original that I
  844. bundled into a function or two, and the six different types, along with
  845. the 18 keyword representations, have become four flags which may be
  846. ORed together.
  847.  
  848. ENHANCING:
  849.     There is now a rather crude "Why" processor, and the code can
  850. detect and display circular logic rules.  The strings to be run
  851. by the system are executed via system(3).  Although this requires
  852. the overhead of a shell, the advantages are great.  One can use
  853. environment variables and redirection, for example.
  854.  
  855. UNIXFING:
  856.     The concept of quiet and verbose has already been mentioned,
  857. and the optional argument to make it verbose has been added.  Blank
  858. lines are not present in the output, and upper/lower case is used
  859. extensivly.  Error returns from system and library calls are checked,
  860. and apropriate messages are displayed.  The exit value from a program
  861. is more in line with tradition: 0 = TRUE, !0 = FALSE.  Thus, one can
  862. call, for example, grep(1) and properly determine the truth-value.
  863.  
  864.     As far as size is concerned, infer is smaller than inference,
  865. realizing of course that infer mallocs the world, while inference
  866. has static data already declared.
  867.  
  868.     I've been unable to measure any noticable difference in the speed
  869. of the programs, both of which have user time < 1 second.  Of course
  870. I'd like to say mine is faster, but that would be fibbing.
  871.  
  872.     I had read somewhere that only a language traditionally suited for
  873. AI was able to handle things like "inference".  Thanks, Mr. Hageman,
  874. for dissolving that myth.
  875.  
  876.     I've gained some valuable knowledge from this rewrite.  Thanks,
  877. again, Mr. Hageman, for sharing your code with me.
  878.  
  879.     I now place this program in the public domain, with no
  880. restrictions as to its use.  If bugs are found (I'm sure some will
  881. be) let me know, so I can incorporate them into my "official"
  882. version.  Use this program freely, but at your own risk.  One should
  883. also not sell this program for profit; it was freely given, therefore,
  884. freely give.
  885.  
  886. Daniel S. Cox
  887. ihnp4!akgua!itm!danny
  888. ===rewrite===
  889. echo "Extracting infer.h <-- infer.ar"
  890. cat << \===infer.h=== > infer.h
  891. typedef struct STR {        /* Keeper of the Strings */
  892.     char    *p;                 /* pointer to string */
  893.     short   val;                /* UNKNOWN, TRUE, FALSE */
  894.     struct  STR *next;          /* yet-another-linked-list */
  895. } STR;
  896.  
  897. typedef struct ELM {        /* Antecedent or Consequence */
  898.     STR     *str;               /* Associated string */
  899.     short   type;               /* STRING or ROUTINE, NOT, HYP */
  900.     struct  ELM *next;          /* kept in linked-list */
  901. } ELEMENT_T;
  902.  
  903. typedef struct {            /* Rule */
  904.     ELEMENT_T   *ant;           /* Head of antecedents for this rule */
  905.     ELEMENT_T   *con;           /* Head of consequences for this rule */
  906.     short       vfy;            /* to detect circular logic */
  907. } RULE_T;
  908.  
  909. /*
  910. **  General Manifest Constants
  911. */
  912.  
  913. # define ANT            1           /* in IF part of rule */
  914. # define CON            2           /* in THEN part of rule */
  915. # define COMMENT_CHAR   '!'         /* ignore lines beginning with this */
  916. # define MAXRULE        1000        /* plenty */
  917. # define MAXWHY         100         /* things proven true, plus current */
  918. # define STRSIZE        512         /* should be plenty */
  919.  
  920.  
  921. /*
  922. **      Type definitions
  923. */
  924.  
  925. # define STRING     000             /* display this string */
  926. # define ROUTINE    001             /* run this string via the shell */
  927. # define NOT        002             /* invert truth-value of assoc. string */
  928. # define HYP        004             /* if TRUE, exit */
  929. # define COMMENT    010             /* this line is a comment */
  930. # define NONE       020             /* no keyword recognized */
  931.  
  932. /*
  933. **  Defines for element vals
  934. */
  935.  
  936. # define UNKNOWN    42          /* the answer to Life, the Universe, etc */
  937. # define TRUE       (-1)        /* all binary ones (most places) */
  938. # define FALSE      0           /* all zeros (most places) */
  939.  
  940. /*
  941. **      External stuff
  942. */
  943.  
  944. extern char *progname;
  945. extern int errno;
  946. extern char *sys_errlist[];
  947. extern int verbose;
  948. extern STR *SP;
  949. extern RULE_T *Rule[];
  950. extern int nrules;
  951. extern char *emalloc (), *strcpy (), *strcat ();
  952. extern void exit ();
  953. ===infer.h===
  954. exit
  955.