Symbol Manipulation Programs

Type of physical science: Computation

Field of study: Artificial intelligence

Symbol manipulation techniques are used in high-level computer programming, in contrast with programs that focus on efficient manipulation of numbers. Logical and systematic design allows the construction of large programs that achieve complex reasoning tasks and are easy to understand.

Overview

Symbol manipulation programs perform high-level computations on well-structured and organized data. Unlike number-crunching programs that perform arithmetic operations on numerical data, symbol manipulation programs manipulate and reason about knowledge represented as structures and organizations of symbols. Representations may be organized in various ways--for example, abstract data types, frames, semantic networks, and logical formulas.

In abstract data types, each object has a standardized structure and is accessed only through a restricted set of operations whose meaning is well understood. For example, a "queue" may be specified as a structured object whose components can be accessed using only operations, such as "first," "rest," and "add-to-Q"; the state of the queue may also be checked via the predicate "is empty;" a special operator to generate new (empty) queues may also be available. In such a specification, there is no mention of how queues are implemented on a specific computer or in a specific programming language. Cells and pointers may be used in one implementation, and arrays of some kind may be used in another implementation. One may choose to modify the underlying implementation at any time, perhaps to improve efficiency, without having to modify the high-level program itself. This is possible because there is no reference to implementation details in the high-level program that manipulates queues. Separation of concerns between the high-level program and the underlying implementation implies that programs are more easily understandable, maintainable, modifiable, and portable. Some other common examples of abstractly specified data types are lists, stacks, dequeues (double-ended queues), trees, and relations. All these have in common the property that their instances are accessed only through well-known and clearly defined operations. Variables in a program can be declared to belong to any of these classes of objects, just as variables can be declared to belong to one of the types (integers, characters, reals, and the like).

Frames are structured objects in which information is stored as a set of pairs. The first element in each pair is an "attribute" or "slot"; the second element is a "value" or "filler" associated with that attribute. The following is an example frame: {less than name, David's greater than, less than class, Restaurant greater than, less than me, eastern greater than, less than average--entree--price, $7 greater than, less than location, M.Street greater than, . . .}. Different frames may belong to the same schema, with the same attributes but different values. For example, many frames including the above "David's" frame may be instances of a "Restaurant" schema.

Schema may be organized into an inheritance hierarchy, with lower-level schema being subclasses of the schema above them in the hierarchy. One advantage of this methodology is that knowledge representation is more compact. Instead of separately specifying the attributes and values of each schema and frame, one can assume that every frame and schema inherits attribute-value pairs from the nodes above it in the hierarchy. For example, if the schema "birds" has an attribute "method of movement" with the value "flying," and "eagles" is a subschema of "birds," then one need not separately specify that eagles fly, since this property is inherited from the "birds" schema.

In specific cases, it is possible to override the inherited property by specifying an alternate value. For example, "penguins" may be a subclass of "birds" for which the value "walking" is associated with the attribute "method of movement." Now, if someone is told only that Tweety is a bird, one would infer that Tweety can fly; but if someone is told that Tweety is a penguin, the more specific result applies and one can conclude that Tweety walks rather than flies, although Tweety is a bird. This kind of inference mechanism is an important aspect of commonsense reasoning.

Symbol manipulation programs contain various reasoning and inference mechanisms.

Symbolic logic is used to represent knowledge, and the first step in problem-solving is to translate expressions and sentences from English (or some other natural language) into the language of logic.

The simplest logic is called "propositional logic": Each symbol stands for an entire proposition in this logic, and the legal expressions or well-formed formulas are obtained by using logical connectives (&,∨,→,¬) to combine these symbols. For example, if the symbol P stands for the proposition "molecules contain atoms" and Q stands for "crystals contain molecules," then P & Q is a well-formed formula whose meaning is intended to be "molecules contain atoms, and crystals contain molecules." Each of P, Q, P ∨ Q, ¬P, ¬Q, P → Q is also a well-formed formula. The meaning of each formula can be extracted uniquely from the meanings of the symbols and the connectives in the formula. For example, "P ∨ Q" stands for "P or Q," "P → Q" stands for "P implies Q," and "¬P" stands for "not P."

In classical propositional logic, there are only two truth values: true (T) and false (F), and the way in which connectives modify the meanings of formulas can be captured by "truth tables." Each truth table is a set of rows of truth values, where each row corresponds to one possible assignment of truth values to the individual "atomic" proposition symbols. In the following truth tables, each column represents the truth values of a formula for different combinations of truth values of the component atoms P, Q. The table needs to have only four rows of truth values, exhausting all possible combinations of truth vales of P, Q.

The last column illustrates the computation of truth values of complex formulas containing several connectives. The connectives behave in the same way even if other formulas are substituted for P and Q: For example, the truth value of "P → Q" when "P" is false and "Q" is true is exactly the same as the truth value of "(P & Q) → (P ∨ Q)" when "P & Q" is false and "P ∨ Q" is true. The truth values of "(P & Q) → (P ∨ Q)" depend uniquely on the truth values of "P & Q,"(P ∨ Q)" in the same way as the truth value of "P → Q" depends on the truth values of "P," "Q." The formula "(P & Q) → (P ∨ Q)" is called a "tautology" because it is always true, as shown in the last column of the above table, irrespective of the truth values of its component propositions. Some other formulas are called "contradictions," always false irrespective of the truth values of propositions in the formula. For example, P &∨ P is a contradiction, because both P and ¬P cannot be simultaneously true, irrespective of the intended meaning of the symbol P. Not every formula is a tautology or a contradiction.

Propositional logic cannot be used to express and reason about formulas with some inherent structure. For example, there is no way to conclude "crystals contain atoms" from representations of the statements "crystals contain molecules" and "molecules contain atoms" in propositional logic. Such reasoning is expressed naturally in a more complex formalism called "predicate logic," which also contains predicates, variables, and quantifiers. A predicate is something that can be applied to some number of arguments to yield a truth value. For example, one may use a predicate called Contain with two arguments, and consider Contain(crystals, molecules) to be true, and similarly consider Contain(molecules, atoms) to be true, whereas Contain(crystals, monkeys) is expected to be false. In order to conclude Contain(crystals, atoms) from those formulas, the idea must be expressed that if x contains y, and y contains z, then x contains z, for every set of values denoted by x,y and z. Formally, this is expressed as the formula "∀x, ∀y, ∀z. ([Contain (x,y)&Contain(y,z)] → Contain(x,z))," read as "for-all x, for-all y, for-all z, Contain(x,y) and Contain(y,z) imply Contain(x,z)." The symbols x,y,z are used here as variables, which can take on values from some domain of objects, and "∀" is a special symbol called the universal quantifier; a formula "∀x.F" holds if the formula F holds for every value of the variable x.

Variables may take value from an infinite number of objects, such as integers. For example, the formula "∀x.[odd(x)∨even(x)]" may be interpreted on the domain of integers to be equivalent to the following infinite set of formulas: {odd(0)∨even(0),odd∨even,odd∨even,…}. This means that it is not possible to verify predicate logic formulas by constructing finite truth tables for the formulas. The preferred way of reasoning with formulas in predicate logic is by using axioms and inference rules to derive theorems. Axioms are a set of formulas assumed to be truths, from which reasoning begins; all axioms are theorems, by definition. Inference rules are syntactic rules that tell which new theorems can be generated from other theorems. For example, if P → Q is a theorem, and if P is also a theorem, then an inference rule called modus ponens indicates that Q is also a theorem; the definition of this inference rule is not concerned with the details of what P and Q are, nor with the intended meaning of these formulas. Well-known formulations of axioms and inference rules for predicate logic are such that all and only tautologous formulas are provable theorems. This relates the proof techniques with the semantics of formulas, allowing one in practice to work entirely by manipulating symbols, rather than by trying to reason about their meanings.

Applications

The development of large computer programs is a difficult and complex task. Errors that appear to be minor can cause huge programs to crash, resulting in disasters and expenses that can be avoided by using more understandable symbol-manipulation programs. A large proportion of the effort in computer programming is spent in maintaining existing programs, rather than writing new programs. To tame such tasks, formal specifications using methodologies such as abstract data types have been found to be useful.

The more abstract and the higher the level of a program, the easier it is to understand its logic clearly, making it easier to modify it, port it to other machines, or add to its capabilities.

Entire programming languages and computers have been developed on the basis of the symbolic or logical processing paradigms. These have become increasingly popular, because the statement of a problem in a logic programming language can itself be directly executed to give the solution, instead of first going through a complicated translation into a computer program in a conventional programming language. So the task of the programmer essentially consists of specifying the problem in clear, logical, unambiguous terms, rather than encoding it in a language that is difficult to comprehend.

Another motivation for symbolic processing techniques is that they are capable of being used to describe cognition and reasoning tasks performed easily by humans. It is natural to describe qualitative reasoning in qualitative terms, using symbols to denote various objects and concepts, rather than in quantitative or numeric terms. Automated reasoning is an active research topic in artificial intelligence. Many computer programs that mimic human performance in various reasoning tasks have been built and successfully used to prove complex mathematical theorems. For purposes of simulating human commonsense reasoning, however, classical predicate logic appears to be inadequate.

Unlike classical logic, human reasoning commonly appears to be nonmonotonic in character; that is, conclusions are often revised when additional evidence is presented. Various alternative logics have hence been proposed and used in some artificial intelligence systems called truth maintenance systems.

Knowledge representation mechanisms such as frames and semantic networks have been widely used in applications such as natural language processing. The task in this context is for machines to process input sentences in a language like English, represent it in a way that captures the intended meaning of the sentence rather than merely the grammatical form, and answer questions about the knowledge contained in those sentences. Another related task is machine translation: The representation of an English sentence, for example, should be used together with the grammar rules for French, in order to obtain a French translation of the original sentence.

A semantic network is a graphlike structure, consisting of concept nodes whose interrelations are explicitly indicated using pointers or network connections. This mechanism combines the representations of concepts and their associations into one overall structure. Each concept or object has a unique representation, and disambiguation is performed when reference is made to the same object in different parts of a text or conversation, possibly using different words or phrases, as in "John left. He lives in Rome." Here, the italicized pronoun refers to "John," and understanding the latter assertion involves making the appropriate connection between the nodes representing the concepts "John" and "Rome." When a question "Where does John live?" is asked, such a system would start searching the network at the node representing "John," and produce the appropriate answer when a connection representing residence is located to the node representing "Rome."

Structured objects called relations modified by logical operations have been used successfully in large databases (stores of structured information). Each relation is essentially a table or two-dimensional array, in which each column is a separate field. Each row in a relation contains an entry from the domain (set of eligible values or elements) of each field. Each row is considered a member of the relation in which it occurs. Relations are generally manipulated using three special operations called selection, projection, and join. Selection extracts some rows of a relation, which satisfy some predicate. Projection results in a relation with fewer columns.

Join is the operator that combines relations that have some common fields, combining pairs of rows with matching values in the common fields. The following tables illustrate these ideas.

(EMP and MGR are two separate relations.)

The following relations show the results of: selection on EMP using the predicate "salary greater than age" and projection of MGR onto "manager" and "department" fields.

The following relation is obtained by performing a join operation of EMP and MGR relations, which have a common "employee" field.

Context

Computing techniques can be broadly classified as numeric, symbolic, or connectionist.

The first is the classical approach, which historically preceded the others and is still of great importance in fields such as scientific computing. A disproportionately large number of computer programs being used today have been built using programming languages and techniques dating back to the 1960's. In artificial intelligence applications, however, symbolic processing techniques constitute the dominant paradigm. The connectionist paradigm of computing with artificial neural networks has also been applied successfully to many tasks related to pattern recognition.

Unless properly represented, knowledge is useless. For example, although everything is stored in terms of 1's and 0's in a computer, that level of representation is completely incomprehensible to humans and therefore very little can be done with it. In computer programming, the lowest level of communication with a computer is via machine language programs, which are merely sequences of numbers. Assembly-language programs are a little higher in level: They consist of simple instructions, typically using mnemonic αbet sequences. Programming languages such as FORTRAN are one level higher and are easier to work with than assembly-language programs. Programs that manipulate symbolic representations, logical formulas, and abstractions are at a higher level and are much easier to understand. The higher the level of representation, the easier it is to perform high-level reasoning with the represented knowledge.

The lofty goal of research in artificial intelligence is to develop intelligent systems that should be able to reason in ways analogous to people. Hence, logic and theorem proving and automated reasoning are important. Present formulations of logic date their development from the work of Friedrich Ludwig Gottlob Frege in the early part of the twentieth century. In the 1970's and 1980's, there was much progress in building theorem-proving computer systems that perform logical deductions efficiently. In addition to proving mathematical theorems, they have been applied to problems such as proving the correctness of computer hardware and software.

In the 1980's, commercial and industrial applications of artificial intelligence became increasingly popular, under the name of "expert systems." An important trend for future development of such successful artificial intelligence applications is the combination of various knowledge-representation and database techniques with powerful reasoning methodologies. A central problem in artificial intelligence is the task of simultaneously obtaining a good representation language, inference mechanism, and domain knowledge. Often, the requirement of expressive adequacy conflicts with that of reasoning efficiency, and suitable compromises have to be chosen.

Principal terms

ABSTRACT DATA TYPE: a class of structured objects described abstractly in terms of the predicates, operations, and functions that can operate on it

FRAME: a structured object consisting of less than attribute, value greater than pairs

KNOWLEDGE: the result of processing, refining, and structuring data, extracting important aspects

PREDICATE LOGIC: a generalization of propositional logic, with symbols representing predicates and variables that may be quantified

PROPOSITIONAL LOGIC: a logic in which symbols denote propositions and are combined into formulas using connectives representing "and," "or," "implies," "not"

Bibliography

Barr, Avron, Edward A. Feigenbaum, and Paul R. Cohen, eds. HANDBOOK OF ARTIFICIAL INTELLIGENCE. 4 vols. Stanford, Calif.: HeurisTech Press, 1981-1989. These volumes constitute comprehensive reference material for various techniques and applications of artificial intelligence.

Brachman, Ronald J., and Hector J. Levesque, eds. READINGS IN KNOWLEDGE REPRESENTATION. San Mateo, Calif.: Morgan Kauffmann, 1985. This collection contains several oft-quoted articles by leading researchers on various approaches to knowledge representation. Recommended for interested readers who have some familiarity with the basics of artificial intelligence and logic.

Chang, Chin-Liang, and Richard C. Lee. SYMBOLIC LOGIC AND MECHANICAL THEOREM-PROVING. New York: Academic Press, 1973. This book presents logic from the viewpoint of automating reasoning techniques. The main focus is on the development of resolution, a well-known theorem-proving method discovered by J. A. Robinson in 1965.

Horowitz, Ellis. PROGRAMMING LANGUAGES: A GRAND TOUR. Rockville, Md.: Computer Science Press, 1983. Contains an introduction to various modern programming languages and is useful in obtaining a panoramic view of different styles of computing.

Liskov, Barbara, and John Guttag. ABSTRACTION AND SPECIFICATION IN PROGRAM DEVELOPMENT. Cambridge, Mass.: MIT Press, 1986. This book presents an excellent approach to program design. Recommended for its discussion of systematic software development.

Truth table

Two tables, or "relations," in a database, with selection samples