home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 June / SIMTEL_0692.cdr / msdos / aijournl / ai_feb87.arc / AIAPP.FEB < prev    next >
Text File  |  1987-01-29  |  8KB  |  195 lines
  1.  
  2.                           AI Apprentice
  3.                       Figures and Listings
  4.                AI EXPERT magazine -- February 1987
  5.  
  6.  
  7.  
  8.                  |----------|     |----------|     |----------|     
  9.                  |   cons   |     |   cons   |     |   cons   |     
  10.                  |----------|     |----------|     |----------|     
  11.                  |      --------->|      --------> |      ----->NIL 
  12.                  |----------|     |----------|     |----------|     
  13.                  |          |     |          |     |          |     
  14.                  |----|-----|     |----|-----|     |----|-----|     
  15.                       |                |                |           
  16.                       V                V                V           
  17.                  |----------|     |----------|     |----------|     
  18.                  |  functor |     | constant |     | variable |     
  19.                  |----------|     |----------|     |----------|     
  20.                  |   likes  |     |  vicky   |     |  skiing  |     
  21.                  |----------|     |----------|     |----------|     
  22.  
  23.  
  24. Figure 1.
  25. Linked list representation of "likes(vicky,skiing)."
  26.  
  27.   |----------|     |----------|     |----------|     
  28.   |   cons   |     |   cons   |     |   cons   |     
  29.   |----------|     |----------|     |----------|     
  30.   |      --------->|      --------> |      ----->NIL 
  31.   |----------|     |----------|     |----------|     
  32.   |          |     |          |     |          |     
  33.   |----|-----|     |----|-----|     |----|-----|     
  34.        |                |                |           
  35.        V                V                V           
  36.   |----------|     |----------|     |----------|    |---------|    |---------|
  37.   |  functor |     | constant |     |   cons   |    |  cons   |    |  cons   |
  38.   |----------|     |----------|     |----------|    |---------|    |---------|
  39.   |   list   |     |    a     |     |      -------->|     -------->|    -------> NIL
  40.   |----------|     |----------|     |----------|    |---------|    |---------|
  41.                                     |          |    |         |    |         |
  42.                                     |----|-----|    |----|----|    |----|----|
  43.                                          |               |              |
  44.                                          V               V              V
  45.                                     |----------|    |---------|    |---------|     
  46.                                     |  functor |    | constant|    | constant|     
  47.                                     |----------|    |---------|    |---------|     
  48.                                     |  list    |    |    b    |    |   nil   |     
  49.                                     |----------|    |---------|    |---------|     
  50.               
  51. Figure 2
  52. The internal representation of list(a,list(b,nil)).
  53.  
  54.  
  55.  
  56.      sentence ::- rule | query | command
  57.      rule ::- head '.' | head ':-' tail '.'
  58.      query ::- '?-' tail '.'
  59.      command ::- '@' file_name '.'
  60.      head ::- goal
  61.      tail ::- goal | goal ',' tail
  62.      goal ::- constant | variable | structure
  63.      constant ::- {quoted string} | {token beginning with 'a' .. 'z'}
  64.      variable ::- {identifier beginning with 'A' .. 'Z' or '_' }
  65.      structure ::- functor '(' component_list ')'
  66.      functor ::- {token beginning with 'a' .. 'z'}
  67.      component_list ::- term | term ',' component_list
  68.      term ::- goal | list
  69.      list ::- '[]' | '[' element_list ']'
  70.      element_list ::- term | term ',' element_list | term | term
  71.      file_name ::- {legitimate DOS file name, must be surrounded with
  72.                     single quotes if it contains a '.',':' or '\'}
  73.  
  74.  
  75. Figure 3 
  76. VTPROLOG Grammar.
  77.  
  78.  
  79.       PROCEDURE list(VAR l_ptr : node_ptr) ;
  80.        VAR
  81.         elem_list : node_ptr ;
  82.  
  83.        PROCEDURE element_list(VAR e_list : node_ptr) ;
  84.         VAR
  85.          e_list2 : node_ptr ;
  86.         BEGIN
  87.          term(e_list) ;
  88.          IF token = ','
  89.           THEN
  90.            BEGIN
  91.             scan(source,token) ;
  92.             element_list(e_list) ;
  93.            END
  94.          ELSE IF token = '|'
  95.           THEN
  96.            BEGIN
  97.             e_list2 := NIL ;
  98.             scan(source,token) ;
  99.             term(e_list2) ;
  100.             e_list := append_list(e_list,head(e_list2)) ;
  101.            END ;
  102.         END ; (* element_list *)
  103.  
  104.        BEGIN
  105.         scan(source,token) ;
  106.         IF token = ']'
  107.          THEN
  108.           BEGIN
  109.            l_ptr := append_list(l_ptr,cons(NIL,NIL)) ;
  110.            scan(source,token) ;
  111.           END
  112.          ELSE
  113.           BEGIN
  114.            elem_list := NIL ;
  115.            element_list(elem_list) ;
  116.            IF token = ']'
  117.             THEN
  118.              BEGIN
  119.               scan(source,token) ;
  120.               l_ptr := append_list(l_ptr,cons(elem_list,NIL)) ;
  121.              END
  122.             ELSE error('Missing '']''.') ;
  123.           END ;
  124.        END ; (* list *)
  125.  
  126. Figure 4
  127. A routine to recognize lists.
  128.  
  129.               |----------|     |----------|     |----------|     
  130.               |   cons   |     |   cons   |     |   cons   |     
  131.               |----------|     |----------|     |----------|     
  132.               |      --------->|      --------> |      ----->NIL 
  133.               |----------|     |----------|     |----------|     
  134.               |          |     |          |     |          |     
  135.               |----|-----|     |----|-----|     |----|-----|     
  136.                    |                |                |           
  137.                    V                V                V           
  138.               |----------|     |----------|     |----------|     
  139.               | constant |     | constant |     | constant |     
  140.               |----------|     |----------|     |----------|     
  141.               |    a     |     |    b     |     |    c     |     
  142.               |----------|     |----------|     |----------|     
  143.  
  144. Figure 5
  145. The internal representation of [a,b,c].
  146.  
  147.               |----------|     |----------|     |----------|     
  148.               |   cons   |     |   cons   |     | variable |     
  149.               |----------|     |----------|     |----------|     
  150.               |      --------->|      --------> |    Z     |     
  151.               |----------|     |----------|     |----------|     
  152.               |          |     |          |    
  153.               |----|-----|     |----|-----|    
  154.                    |                |          
  155.                    V                V          
  156.               |----------|     |----------|    
  157.               | variable |     | variable |    
  158.               |----------|     |----------|    
  159.               |    X     |     |    Y     |    
  160.               |----------|     |----------|    
  161.  
  162. Figure 6
  163. The internal structure of [X,Y|Z].
  164.  
  165.  
  166. item     |     Item within the query   
  167. in the   |
  168. rule     |     constant       variable       functor            list
  169.          |      (C2)           (V2)           (F2)              (L2)
  170.          |--------------------------------------------------------------------
  171. constant |     succeed if     succeed        fail               fail
  172. (C1)     |     C1 = C2        bind V2 to C1
  173.          |
  174. variable |     succeed        succeed        succeed            succeed
  175. (V1)     |     bind V1 to C2  bind V1 to V2  bind V1 to F2      bind V1 to L2
  176.          |
  177. functor  |     fail           succeed        succeed if         fail
  178. (F1)     |                    bind V2 to F1  expressions have 
  179.          |                                   same functor and 
  180.          |                                   arity and each
  181.          |                                   of components
  182.          |                                   can be unified
  183.          |
  184. list     |     fail           succeed        fail               succeed if
  185. (L1)     |                    bind V2 to L1                     heads can be unified
  186.          |                                                      and tails can be
  187.          |                                                      unified
  188.  
  189. Table 1
  190. Unification table for rules and queries.
  191.  
  192.         |                                                      unified
  193.  
  194. Table 1
  195. Unification table for rules and queri