ABSTRACT
A frequent programming problem is the classification of information on the basis of some of its properties. Suppose the classification in general requires that a large number of tests be applied to ITEM-TO-BE-CLASSIFIED. Conceptually we can think of this as forming a net or tree. To implement a search in the tree, one first defines two basic data structures: nodes and links. A node has CONTENTS and a list of links, LINK-LIST. A link has a KEY and a NODE. Each non-terminal internal node of the tree will have a TEST function and branches to sub-nodes. Applying TEST to ITEM will yield some value which will be used to pick the branch to the next NODE to look at. A different kind of discrimination net, classifies S-expressions according to their syntactic form. If the discrimination net search ends in a node written as (), then the desired list is not part of the database.
