AI Algorithms, Data Structures, and Idioms Part 1

Idioms, Patterns, and Programming

Idioms and Patterns

Design patterns capture and communicate a form of knowledge that is essential to creating computer programs that users will embrace, and that programmers will find to be elegant, logical, and maintainable.

Idioms are a form and structure for knowledge that helps us bridge the differences between patterns as abstract descriptions of a problem and its solution s and an understanding of how best to implement that solution in a given programming language.

A language idiom is the expression of a design pattern in a given language.

Design patterns + idioms = quality programs

Sample Design Patterns
map (operator O, list L){  
    if (L contains no elements) quit;
    h <- the first element of L.
    apply O to h;
    map(O, L minus h);

Consider a fragment of Lisp code that implements this same map pattern, where f is the mapped operator and list is the list:

(defun map(f list)
    (cond ((null list) nil)
        (t (cons (apply f (car list))
            (map f (cdr list))))))

This fuction map created by using the built-in Lisp defun function, not only implements the map pattern, bust also illustrates elements of the Lisp programming idiom. These include the use of the operators car and cdr to separate the list into its head and tail, the use of the cons operator to place the results into a new list, and also the use of recursion to move down the list.

Compare the Lisp map to a Java implementation that demonstrates how idioms vary across language:

public Vector map(Vector l){  
    Vector result = new Vector();
    Iterator iter = l.iterator();
    return result;

The most striking difference between the Java version and the Lisp version is that the Java version is iterative. Java offers us iterators for moving through lists. Further more, the Java version of map creates the new variable, result. When the iterator completes its task, result will be a vector of elements, each the result of applying f to each element of the input list, each the result of applying f to each element of the input list.

In Prolog, map will be a represented as a predicate. This predicate has three arguments, the first the function, f, which will be applied to every element of the list that is the second argument of the predicate. The third argument of the predicate map is the list resulting from applying f to each element of second argument. The pattern [X|Y] is the Prolog list representation, where X is the head of the list (cdr is Lisp). The is operator binds the result of f applied to H to the variable NH. As with Lisp, the map relationship is defined recursively, although no tail recursive optimization is possible in this case.

Prolog map function:

map(f, [], []).  
map(f, [H|T], [NH|NT]):-  
    NH is f(H), map(f, T, NT).

Selected Examples of AI language Idioms

Symbolic Computing: The Issue of Representation

Artificial Intelligence rests on two basic ideas: 1. representation or the use of symbol structures to represent problem solving knowledge; 2. search, the systematic consideration of sequences of operations on these knowledge structures to solve complex problems.

Conceptually, AI search algorithms are general: they can apply to any search space. We will define general, reusable search 'framework' that can be applied to a range of problem representations and operations for generating new states.

Lisp makes no syntactic distinction between functions and data structures: both can be represented as symbol expressions, and both can be handled identically as Lisp objects. In addition, Lisp does not enforce strong typing on s-expressions.

Prolog includes a list representation that is very similar to lists in Lisp, but differs in having built-in search and pattern matching in a language supporting direct representation of predicate calculus rules. We define the operators for generating states as rules, using pattern matching to determine when these rules apply. Prolog offers explicit meta level controls that allow us to direct the pattern matching, and control its built-in search.

Java presents its own unique idioms for generalizing search. Although Java provides a 'reflection' package that allows us to manipulate its objects, methods, and their parameters directly, this is not as simple to do as in Lisp or Prolog. Instead we will use Java interface definitions to specify the methods a state object must have at a general level, and define search algorithms that take as states instances of any class that instantiates the appropriate interface.

Pattern Matching

Approaches to pattern matching can vary from checking for identical memory locations, to comparing simple regular-expressions, to full pattern-based unification across predicate calculus expressions.

Prolog provides unification pattern matching directly in its interpreter: unification and search on Predicate Calculus based data structures are the basis of Prolog semantics. The question is not how to implement pattern matching, but how to use it to control search, the flow of program execution, and the use of variable binding s to construct problem solutions as search progresses.

Lisp, in contrast, requires that we implement unification pattern matching ourselves. Using its basic symbolic computing capabilities, Lisp makes it straightforward to match recursively the tree structures that implicitly define predicate calculus expressions. The main design problem facing us is the management of variable bindings across the unification algorithm.

Java is a strongly typed language. Consequently, our Java implementation will depend upon a number of user-created classes to define expressions, constants, variables, and variable bindings. The differences between the Java and Lisp implementations of pattern matching are interesting examples of the differences between the two languages, their distinct idioms, and their differing roles in AI programming.

Structured Types and Inheritance (Frames)

A major focus of AI work is on producing representations that reflect the way people think about problems. One of the most important complex structures comes from frame theory, and is based on structured data types, explicit relationships between objects, and the use of class inheritance to capture hierarchical organizations of classes and their attributes.

Just as Prolog bases is organization on predicate calculus and search, and Lisp builds on operations on symbolic structures, so Java builds directly on these ideas of structured representation and inheritance.

Meta-Linguistic Abstraction

Meta-Linguistic abstraction is one of the most powerful ways of organizing programs to solve complex problems. The idea behind meta-linguistic abstraction is straightforward: rather than trying to write a solution to a hard problem in an existing programming language, use that language to create another language that is better suited to solving the problem.

One example of meta-linguistic abstraction that is central to AI is the idea of an inference engine: a program that takes a declarative representation of domain knowledge in the form of rules, frames or some other representation, and applies that knowledge to problems using general inference algorithms.

Knowledge Level Design

The distinction between the symbol and knowledge level is reflected in the architectures of expert systems and other knowledge-based programs. These programs must preserve two invariants: 1. there must be a knowledge-level characterization; 2. there must be a clear distinction between this knowledge and its control.

The symbol level, just below the knowledge level, defines the knowledge representation language, whether it be direct use of the predicate calculus or production rules.

The implementation of the algorithm and data structure level constitutes a still lower level of program organization, and defines an additional set of design consideration.