The nondeterministic program evaluator of section also moves away from the view that programming is about constructing algorithms for computing unidirectional functions. In a nondeterministic language, expressions can have more than one value, and, as a result, the computation is dealing with relations rather than with single-valued functions. Logic programming extends this idea by combining a relational vision of programming with a powerful kind of symbolic pattern matching called unification . This approach, when it works, can be a very powerful way to write programs. As an example, consider the append operation, which takes two lists as arguments and combines their elements to form a single list.
Logic programming is an active field of research in computer science.
Now we will apply these ideas to discuss an interpreter for a logic programming language. We call this language the query language , because it is very useful for retrieving information from data bases by formulating queries , or questions, expressed in the language. An interpreter for a logic programming language is considerably more complex than an interpreter for a language like Lisp. Nevertheless, we will see that our query-language interpreter contains many of the same elements found in the interpreter of section . Also, a central role is played in the implementation by a frame data structure, which determines the correspondence between symbols and their associated values.