next up previous contents
Next: 4.3 Clause level Up: 4 The classifier Previous: 4.1 Procedure level

4.2 Indexing

Syntax:

 
indexing     		 ::= 		 (indexing [iblock])

iblock ::= pblock tex2html_wrap_inline2907 sblock

pblock ::= (pblock rblock {sblock tex2html_wrap_inline2907 1block} tex2html_wrap_inline2789 )

rblock ::= (rblock clauses {arg-col} tex2html_wrap_inline2789 )

clauses ::= (clauses {clause-number} tex2html_wrap_inline2789 )

arg-col ::= (arg arg-number {base-type} tex2html_wrap_inline2789 )

base-type ::= const tex2html_wrap_inline2907 struct tex2html_wrap_inline2907 var

const ::= (const symbol)

struct ::= (struct symbol arity)

var ::= (var symbol)

1block ::= (1block clauses {arg-col} tex2html_wrap_inline2789 )

sblock ::= (sblock rblock seqind [pblock])

seqind ::= (seqind {seqind-arg} tex2html_wrap_inline2789 )

seqind-arg ::= (arg arg-number (info inhomogenity) constants

structures lists empty-lists [others])

constants ::= (const {element}*)

structures ::= (struct {element}*)

element ::= (element-name clauses [iblock])

element-name ::= symbol tex2html_wrap_inline2907 (symbol arity)

lists ::= (list clauses [iblock])

empty-lists ::= (nil clauses [iblock])

others ::= (other clauses [iblock])

Description:

iblock
indexed block
pblock
partition block
sblock
standard index block
1block
block consisting of only one clause
rblock
raw block containing the initial data
seqind
sequential indexing
arg-col
argument column
others
(possibly indexed) clauses for elements not occurring in any hash table

Example:

Prolog-like source:
foo(alpha,beta).
foo(T,gamma) :- . . .  .
.  .  .
Lisp-like source:
(hn (foo alpha beta))
(ft (foo _t gamma) . . .)
.  .  .

Classified Clauses:

(db (proc foo/2 2
          (indexing
           (sblock
            (rblock
             (clauses 1 2)
             (arg 1 (const alpha) (var t))
             (arg 2 (const beta) (const gamma)) )
            (seqind
             (arg 2
              (info 2)
              (const (beta (clauses 1)) (gamma (clauses 2)))
              (struct) (list) (nil) )
             (arg 1
              (info 1)
              (const (alpha (clauses 1 2)))
              (struct) (list) (nil)
              (other (clauses 2)) ) ) ) )
       .  .  .)

Here we insert a more complete example from a propositional normalizer [Sin93]:

Prolog-like source:

norm(X, X) :- literal(X).
norm(or[X, Y], or[X, Y]) :- literal(X), literal(Y).
norm(and[X, Y], and[X, Y]) :- literal(X), literal(Y).
norm(or[X, Y], or[X1, Y]) :- literal(Y), norm(X, X1).
norm(or[X, or[Y, Z]], W) :- norm(or[or[X, Y], Z], W).
norm(or[X, and[Y1, Y2]], or[X1, Y12]) :-
        norm(X, X1), norm(and[Y1, Y2], Y12).
norm(and[X, Y], and[X1, Y]) :- literal(Y), norm(X, X1).
norm(and[X, and[Y, Z]], W) :- norm(and[and[X, Y], Z], W).
norm(and[X, or[Y1, Y2]], and[X1, Y12]) :- norm(X, X1),
        norm(or[Y1, Y2], Y12).

Classified Clauses:

(db (proc norm/2 9                  ; norm/2 has 9 clauses
     (indexing
      (sblock
       (rblock                      ; info block for first node
        (clauses 1 2 3 4 5 6 7 8 9) ; of the index tree
        (arg 1         ; possible contents of the first argument
         (var x) (struct or 2) (struct and 2) (struct or 2)
         (struct or 2) (struct or 2) (struct and 2)
         (struct and 2) (struct and 2) )
        (arg 2         ; possible contents of the second argument
         (var x) (struct or 2) (struct and 2) (struct or 2)
         (var w) (struct or 2) (struct and 2)
         (var w) (struct and 2) ) )
       (seqind         ; first node of the index tree
        (arg 1         ; indexing for the first arg
         (info 2)      ; there are 2 possible arguments
         (const)       ; no constant in first arg
         (struct       ; there are heads with struct as 1st arg
                       ; create new node in index tree
          ((or 2)      ; norm(or[..],..)
           (clauses 1 2 4 5 6) ; matches these clauses
           (sblock     ; new node for 2nd-arg indexing
            (rblock    ; information for possible subtree pruning
             (clauses 1 2 4 5 6)
             (arg 2 (var x) (struct or 2)
                    (struct or 2) (var w) (struct or 2)) )
            (seqind
             (arg 2
              (info 1) ; 1 possible arg
              (const)  ; no constant as 2nd arg
              (struct  ; norm(or[..],or[..])
               ((or 2) (clauses 1 2 4 5 6))) ; create try-trust block for
                                             ; these clauses
              (list)   ; no list as 2nd arg
              (nil)    ; no [] as 2nd rg
              (other (clauses 1 5)) ) ) ) ) ; variable as 2nd
          ((and 2)     ; norm(and[..],..)
           (clauses 1 3 7 8 9) ; matches these clauses
           (sblock      ; new node for 2nd-arg indexing
            (rblock     ; information for possible subtree pruning
             (clauses 1 3 7 8 9)
             (arg 2 (var x) (struct and 2)
                    (struct and 2) (var w) (struct and 2)) )
            (seqind
             (arg 2
              (info 1) ; 1 possible arg
              (const)  ; no constant as 2nd arg
              (struct
               ((and 2) (clauses 1 3 7 8 9))) ; create try-trust block for
                                              ; these clauses
              (list)   ; no list as 2nd arg
              (nil)    ; no [] as 2nd arg
              (other (clauses 1 8)) ; variable as 2nd arg
              ))))) ; (struct ...
         (list)        ; no list as 1st arg
         (nil)         ; no list as 1st arg
         (other (clauses 1)) ; variable as 1st arg
         ) ; (arg 1 ...
        (arg 2         ; indexing for the 2nd arg
         (info 2)      ; 2 possible arguments
         (const)       ; no constants
         (struct       ; there are heads with struct as 2nd arg
          ((or 2) (clauses 1 2 4 5 6 8)) ; create try-trust block for
                                         ; norm(..,or[..])
          ((and 2) (clauses 1 3 5 7 8 9))) ; and for norm(..,and[..])
         (list)        ; no list as 2nd arg
         (nil)         ; no [] as 2nd arg
         (other (clauses 1 5 8)) ) ) ) ) ; variable as 2nd arg
       .  .  . )

Remark:
For further information about indexing see [Ste93, Sin93, SS92].



Harold Boley (boley@informatik.uni-kl.de)