Chapter 10

Artificial Intelligence Programming Languages

10.1 A Range of Intelligent Systems Tools

The previous chapters have introduced a range of intelligent systems techniques, covering both knowledge-based systems and computational intelligence. The tools available to assist in constructing intelligent systems can be roughly divided into the following categories:

• Expert system shells, for example, Drools, CLIPS, and Jess.
• Artificial intelligence toolkits, for example, knowledge-based system tools such as Flex/VisiRule, neural network packages such as SNNS, and multiagent tools such as DARBS.
• Libraries, for example, extension libraries for MATLAB, C++, and Java.
• Object-oriented programming languages, for example, C++, Java, and CLOS.
• Traditional procedural programming languages, for example, C, Pascal, and Fortran.
• Artificial-intelligence programming languages for processing words, symbols, and relations, for example, Lisp and Prolog.

An expert system shell is an expert system that is complete except for the knowledge base. Expert-system shells were an early form of artificial intelligence toolkit. They were designed to allow the rapid design and implementation of rule-based expert systems, but often lacked flexibility. Typically, an expert system shell includes an inference engine, a user interface for programming, and a user interface for running the system. The programming interface might comprise a specialized editor for creating rules in a predetermined format, and some debugging tools. The shell user enters rules in a declarative fashion and ideally should not need to be concerned with the workings of the inference engine. In practice this ideal is rarely met, and a typical difficulty in using a shell is ensuring that rules are applied when expected. As the user has no direct control over the inference engine, it is usually necessary to gain some insight into its workings and to tailor the rules to achieve the desired effect. This is not necessarily easy and detracts from the advantages of having a separate knowledge base. Nevertheless, shells are easy to use in other respects and allow a simple knowledge-based system to be constructed quickly. They are, therefore, useful for building prototype expert systems and for educational purposes. However, their inflexible facilities for knowledge representation and inference tend to limit their general applicability.

The programming languages offer much greater flexibility and can be used to build customized tools. Most programming languages are procedural rather than declarative, although the Prolog language incorporates both programming styles. Some KBS toolkits such as Flex and its Visirule interface aim to provide the best of all worlds. They offer the programmer access to the underlying language and to tools for constructing rules, agents, and other knowledge-based entities. The provision of these tools can save considerable programming effort, while the ability to access the underlying language gives the freedom to build additional capabilities.

Libraries offer similar advantages to toolkits. Instead of supplying the complete programming environment, libraries provide specific functionality on the assumption that the underlying programming environment already exists. There is a range of KBS and computational intelligence libraries available, for example, for C++, MATLAB, and Java.

10.2 Features of AI Languages

The remainder of this chapter will focus on the two main AI programming languages: Lisp and Prolog. A key feature of both languages is the ability to manipulate symbolic data, that is, characters and words, as well as numerical data. One of the most important structures for this manipulation is lists, introduced in the following section.

10.2.1 Lists

A knowledge base may contain a mixture of numbers, letters, words, punctuation, and complete sentences. Most computer languages can handle such a mixture of characters, provided the general format can be anticipated in advance. Suppose we wanted to represent a simple fact such as:

pressure in valve_2 is 12.8 MPa.

where 1MPa = 1MNm–2. One possible C++ implementation (see Chapter 4) of this fact is to define a Valve class and the instance valve2, as follows:

class Valve

{

	public:

		// constructor

		Valve(int id, float pres, const char *u);

		// destructor

		~Valve();

	private:

		int identity_number;

		float pressure;

		char *units;

}

Valve::Valve(int id, float pres, const char *u)

{		//constructor definition

		identity_number = id;

		pressure = pres;

		units = (char*) u;

}

Valve::~Valve()

{		//destructor definition

		cout << "instance of Valve destroyed" << endl;

}

main()

{

		// create an instance of Valve

		Valve valve2(2, 12.8, "MPa");

}

The class definition could be specialized to handle different types of valves, but a completely new construction would be needed for a fact or rule with a different format, such as

if pressure is above 10 MPa then close valve.

Lists are data structures that allow words, numbers, and symbols to be combined in a wide variety of ways. They are useful for symbol manipulation and are a feature of Lisp and Prolog. The preceding example could be represented as a list in Lisp or Prolog, respectively, as follows:

(close_valve (exceeds pressure 10 mpa))

[if, pressure, exceeds, 10, MPa, then, close, valve]

Lisp uses round brackets with elements separated by spaces, whereas Prolog uses square brackets with elements separated by commas. The Lisp example includes a list within a list, that is, a nested list. Although the Prolog example looks like a rule, it is really just a list of words and numbers. Separate code would be required to interpret it as a rule.

It should be noted that C++ is a versatile language and that lists can be implemented within it by creating pairs of values and pointers, forming a so-called linked list. However, one strength of the AI languages is the integration of lists into the language, together with the necessary facilities for manipulating those lists.

10.2.2 Other Data Types

As well as lists, there are a number of other data types available in the AI languages. Unlike most other languages, variables in the AI languages can be used to store any type of data. A list could be assigned to a given variable immediately after assigning a real number to the same variable. The declaration of variables is not always necessary. However, declarations are normally made in Lisp to specify explicitly the scope of a variable, because undeclared variables are assumed to be global (i.e., memory is allocated for the whole duration of a program or interactive session).

Although the assignment of different types of data to variables is transparent to the programmer, the computer needs to know the type of data in order to handle it correctly. There are various techniques for achieving this. Typically, the value associated with a variable includes a tag, hidden from the programmer, which labels its type. Some commonly used data types in the AI languages are shown in Table 10.1.

Lisp also allows the creation of arrays and structures, similar to those used in C. Strings can be made up of any printable characters, including numbers and spaces, enclosed in quotation marks. Words can generally be regarded as a sequence of one or more characters without any spaces, as spaces and certain other characters may act as separators for words, depending on the language. Examples of words include variable names and the elements of the lists shown in Table 10.1. List elements are not always words, as lists can contain nested lists or numbers. The term atom is used in both languages to denote a fundamental data type that cannot be made up from other data types. For example, numbers and words are atoms, but lists are not.

During the execution of a program, various data structures may be created. There is, therefore, a need for management of the computer memory, that is, memory must be allocated when needed and subsequently reclaimed. In languages such as C, the responsibility for memory management rests with the programmer, who must allocate and reclaim memory at appropriate places in the program using the malloc and free commands (or their equivalent). In the AI languages (and some object-oriented languages, such as Smalltalk) the memory is managed automatically. The programming environment must be capable of both dynamically allocating memory and freeing memory that is no longer required. The latter process is called garbage collection. This is a useful facility, although it can result in a momentary pause in the computer’s response while the garbage collection takes place.

10.2.3 Programming Environments

In general, both of the AI languages considered here form part of their own interactive programming environment. Typically, there is a console window into which code can be typed. Such instructions are interpreted and obeyed immediately, and the output printed on the screen.

Typing commands in this way is a useful way of inspecting the values of variables and testing ideas, but it is not a practical way of writing a program. Instead, a text editor is used to enter code so that it can subsequently be modified, saved, compiled, and run. In an integrated programming environment, the code can be evaluated or compiled from within the editor. Debugging tools can stop the program at a selected point or when an error occurs, so the assignments up to that point can be examined.

Code that has been written in an AI language will, in general, run more slowly than a compiled C or C++ program. However, the appeal of AI languages is their power in terms of flexibility for the programmer, rather than their computational or memory efficiency.

10.3 Lisp

10.3.1 Background

It has already been noted that a feature of the AI languages is the integration of lists and list manipulation into the language. This is particularly so in the case of Lisp, as a Lisp program is itself a list made up of many lists. Indeed, the name Lisp is derived from the phrase list processing.

Historically, Lisp has developed in an unregulated fashion. Different syntax and features were introduced into different implementations, partly as a consequence of the existing hardware and software environment. As a result, many different Lisp dialects such as Interlisp, Franzlisp, Maclisp, Zetalisp, and Scheme were developed. A standard was subsequently produced—Common Lisp—that was intended to combine the most useful and portable features of the dialects into one machine-independent language (Steele 1990). This standard form of the language is also the basis of CLOS (Common Lisp Object Standard), an object-oriented extension of Common Lisp. All the examples introduced here are based upon the definition of Common Lisp and should work on any Common Lisp system.

A list is a collection of words, numbers, strings, functions, and further lists, enclosed in parentheses. The following are all examples of lists:

(a b c d)

(My car is 10 years old)

(a list (a b c) followed by an empty list ())

Lisp uses the key word nil to denote an empty list, so that () and nil are equivalent. Lisp extends the idea of a language based upon list manipulation to the point where everything is either a list or an element of a list. There are only a few basic rules to remember in order to understand how Lisp works. However, because its structure is so different from other languages, Lisp may seem rather strange to the novice.

10.3.2 Lisp Functions

While it is valid to describe Lisp as a procedural language (i.e., the computer is told exactly what to do and in what order to do it), a more precise description would be that it is a functional language. This is because a Lisp program is made up of lists that are interpreted as functions that, by definition, return a single value.

The three key rules to understanding Lisp are:

• Each item of a list is evaluated.
• The first item is interpreted as a function name.
• The remaining items are the parameters (or arguments) of the function.

Some of the functions with which we will be dealing are strictly speaking macros, which are predefined combinations of functions. However, the distinction need not concern us here. With a few exceptions, the parameters to a function are always evaluated before the function itself. The parameters themselves may also be functions and can even be the same function (thereby permitting recursion). The following example would be a valid Lisp call to the function print. The computer’s prompt, which precedes user input, varies between implementations but is shown here as <cl>, for Common Lisp:

<cl> (print "hello world")

hello world

hello world

The first element in the list was interpreted as a function name, and the second item as its argument. The argument evaluates to the string “hello world.” It might seem surprising that hello world is printed twice. It is first printed because we instructed Lisp to do so. It is then printed again because Lisp always prints out the value of the function that it is given. In this example, the function print returned as its value the item that it had printed. Consider what will happen if we type the following:

<cl> (print hello)

Error: Unbound variable: HELLO.

This error message has come about because Lisp evaluates every item in the list. In this example, the interpreter tried to evaluate hello, but found it to be undefined. A defined variable is one that has a value (perhaps another function) assigned to it. However, in this case we did not really want hello to be evaluated. There are many instances in writing Lisp code when we would like to suppress Lisp’s habit of evaluating every argument. A special function, quote, is provided for this specific purpose.

The quote function takes only one argument, which it does not evaluate but simply returns in the same form that it is typed:

<cl> (quote hello)

hello

<cl> (print (quote hello))

hello

hello

The quote function is used so often that a shorthand form has been made available. The following are equivalent:

(quote hello)

and

'hello

We would also wish to suppress the habit of functions evaluating their arguments when making assignments. Here is an assignment in C++:

my_variable = 2.5;

/* assign value 2.5 to my_variable in C++ */

A value of 2.5 is assigned to my_variable, which would need to have been declared as type float. Lisp provides various functions for achieving this, one of which is setf:

<cl> (setf my_variable 2.5)

2.5

Since the first argument is a variable name, only the second argument to setf is evaluated. This is because we want to make an assignment to the variable name and not to whatever was previously assigned to it. The second parameter of setf, namely 2.5, evaluates to itself, and this value is then assigned to my_variable. Like all Lisp functions, setf returns a value, in this case 2.5, and this value is printed on the screen by the Lisp interpreter.

As we noted earlier, Lisp usually tries to evaluate the parameters of a function before attempting to evaluate the function itself. The parameters may be further functions with their own parameters. There is no practical limit to the embedding of functions within functions in this manner, so complex composite functions can easily be built up and perhaps given names so that they can be reused. The important rules for reading or writing Lisp code are:

• List elements are interpreted as a function name and its parameters (unless the list is the argument to quote, setf, or a similar function).
• A function always returns a value.

Lisp code is constructed entirely from lists, and lists also represent an important form of data. Therefore, it is hardly surprising that built-in functions for manipulating lists form an important part of the Lisp language. Two basic functions for list manipulation are first and rest. For historical reasons, the functions car and cdr are also available to perform the same tasks. The first function returns the first item of that list, while rest returns the list but with the first item removed. Here are some examples:

<cl>(first '(a b c d))

a

<cl>(rest '(a b c d))

(b c d)

<cl>(first (rest '(a b c d)))

b

<cl>(first '((a b)(c d)))

(a b)

Used together, first and rest can find any element in a list. However, two convenient functions for finding parts of a list are nth and nthcdr:

(nth 0 x) finds the 1st element of list x

(nth 1 x) finds the 2nd element of list x

(nth 2 x) finds the 3rd element of list x

(nthcdr 2 x) is the same as (rest (rest x))

(nthcdr 3 x) is the same as (rest (rest (rest x)))

Note that rest and nthcdr both return a list, while first and nth may return a list or an atom. When rest is applied to a list that contains only one element, an empty list is returned, which is written as () or nil. When either first or rest is applied to an empty list, nil is returned.

There are many other functions provided in Lisp for list manipulation and program control. It is not intended that this overview of Lisp should introduce them all. The purpose of this section is not to replace the many texts on Lisp, but to give the reader a feel for the unusual syntax and structure of Lisp programs. We will see, by means of a worked example, how these programs can be constructed and, in so doing, we will meet some of the important functions in Lisp.

10.3.3 A Worked Example

We will discuss in Chapter 12 the application of intelligent systems to problems of selection. One of the selection tasks that will be discussed in some detail is the selection of an appropriate material from which to manufacture a product or component. For the purposes of this worked example, let us assume that we wish to build a shortlist of polymers that meet some numerical specifications. We will endeavor to solve this problem using Lisp, and later in this chapter will encode the same example in Prolog. The problem is specified in detail in Box 10.1.

The first part of our program will be the setting up of some appropriate materials data. There are a number of ways of doing this, including the creation of a list called materials_database:

((POLYPROPYLENE . THERMOPLASTIC)

	(POLYURETHANE_FOAM . THERMOSET))

(property_name minimum_value tolerance)

(flexural_modulus 1.0 0.1)

((property1 minimum_value1 tolerance1)

	(property2 minimum_value2 tolerance2)

	(property3 minimum_value3 tolerance3))

(defvar materials_database nil)

(setf materials_database '(

	(abs thermoplastic

		(impact_resistance 0.2)

		(flexural_modulus 2.7)

		(maximum_temperature 70))

	(polypropylene thermoplastic

		(impact_resistance 0.07)

		(flexural_modulus 1.5)

		(maximum_temperature 100))

	(polystyrene thermoplastic

		(impact_resistance 0.02)

		(flexural_modulus 3.0)

		(maximum_temperature 50))

	(polyurethane_foam thermoset

		(impact_resistance 1.06)

		(flexural_modulus 0.9)

		(maximum_temperature 80))

	(pvc thermoplastic

		(impact_resistance 1.06)

		(flexural_modulus 0.007)

		(maximum_temperature 50))

	(silicone thermoset

		(impact_resistance 0.02)

		(flexural_modulus 3.5)

		(maximum_temperature 240))))

The function defvar is used to declare the variable materials_database and to assign to it an initial value, in this case nil. The function setf is used to assign the list of materials properties to materials_database. In a real application we would be more likely to read this information from a file than to have it “hard coded” into our program, but this representation will suffice for the moment. The variable materials_database is used to store a list, each element of which is also a list. Each of these nested lists contains information about one polymer. The information is in the form of a name and category, followed by further lists in which property names and values are stored. Since materials_database does not have a predeclared size, materials and materials properties can be added or removed with ease.

Our task is to define a Lisp function, to be called accept, that takes a set of specifications as its parameters and returns a list of polymers (both their names and types) that meet the specifications. To define accept, we will use the function defun, whose purpose is to define a function. Like quote, defun does not evaluate its arguments. We will define accept as taking a single parameter, spec_list, that is a list of specifications to be met. Comments are indicated by a semi-colon:

(defun accept (spec_list)

	(let ((shortlist (setup)))

		(if (atom (first spec_list))

;if the first element of spec_list is an atom then

;consider the specification

		(setf shortlist (meets_one spec_list shortlist))

;else consider each specification in turn

		(dolist (each_spec spec_list)

		(setf shortlist (meets_one each_spec shortlist))))

	shortlist))	;return shortlist

In defining accept, we have assumed the form that the specification spec_list will take. It will be either a list of the form:

(property minimum_value tolerance)

or a list made up of several such specifications:

((property1 minimum_value1 tolerance1) (property2

minimum_value2 tolerance2) (property3 minimum_value3 tolerance3)).

Where more than one specification is given within spec_list, they must all be met.

The first function of accept is let, a function that allows us to declare and initialize local variables. In our example, the variable shortlist is declared and assigned the value returned by the function setup, which we have still to define. The variable shortlist is local in the sense that it exists only between (let and the matching closing bracket.

There then follows a Lisp conditional statement. The if function is used to test whether spec_list comprises one or many specifications. It does this by ascertaining whether the first element of spec_list is an atom. If it is, then spec_list contains only one specification, and the first element of spec_list is expected to be the name of the property to be considered. If, on the other hand, spec_list contains more than one specification, then its first element will be a list representing the first specification, so the test for whether the first element of spec_list is an atom will return nil (meaning “false”).

The general form of the if function is:

(if condition function1 function2)

which is interpreted as:

if <condition> then <do function1> else <do function2>.

In our example, function1 involves setting the value of shortlist to the value returned by the function meets_one (yet to be defined), which is passed the single specification and the current shortlist of materials as its parameters. The “else” part of the conditional function (function2) is more complicated, and comprises the dolist control function. In our example, dolist initially assigns the first element of spec_list to the local variable each_spec. It then evaluates all functions between (dolist and its associated closing bracket. In our example, this is only one function, which sets shortlist to the value returned from the function meets_one. Since dolist is an iterative control function, it will repeat the process with the second element of spec_list, and so on until there are no elements left.

It is our intention that the function accept should return a list of polymers that meet the specification or specifications. When a function is made up of many functions, the value returned is the last value to be evaluated. To ensure that the value returned by accept is the final shortlist of polymers, shortlist is evaluated as the last line of the definition of accept. Note that the bracketing is such that this evaluation takes place within the scope of the let function, within which shortlist is a local variable.

We have seen that the first task performed within the function accept was to establish the initial shortlist of polymers by evaluating the function setup. This function produces a list of all polymers (and their types) that are known to the system through the definition of materials_database. The setup function is defined as follows:

(defun setup ()

	(let ((shortlist nil))

		(dolist (material materials_database)

			(setf shortlist (cons (cons (first material) 					(nth 1

				material)) shortlist)))

		shortlist))

The empty brackets at the end of the first line of the function definition signify that setup takes no parameters. As in the definition of accept, let is used to declare a local variable and to give it an initial value of nil, that is, the empty list. Then dolist is used to consider each element of materials_database in turn and to assign it to the local variable material. Each successive value of material is a list comprising the polymer name, its type, and lists of properties and values. Our aim is to extract from it a list comprising a name and type only, and to collect all such two-element lists together into the list shortlist. The Lisp function cons adds an element to a list, and can therefore be used to build up shortlist.

Assuming that its second parameter is a list, cons will return the result of adding its first parameter to the front of that list. This can be illustrated by the following example:

<cl>(cons 'a '(b c d))

(a b c d)

However, the use of cons is still valid even if the second parameter is not a list. In such circumstances, a special type of two-element list, called a dotted pair, is produced:

<cl>(cons 'a 'b)

(a.b)

In our definition of setup we have used two embedded calls to cons, one of which produces a dotted pair while the other produces an ordinary list. The most deeply embedded (or nested) call to cons is called first, as Lisp always evaluates parameters to a function before evaluating the function itself. So the first cons to be evaluated returns a dotted pair comprising the first element of material (which is a polymer name) and the second element of material (which is the polymer type). The second cons to be evaluated returns the result of adding the dotted pair to the front of shortlist. Then shortlist is updated to this value by the call of setf. As in the definition of accept, shortlist is evaluated after the dolist loop has terminated, to ensure that setup returns the last value of shortlist.

As we have already seen, accept passes a single specification, together with the current shortlist, as parameters to the function meets_one. It is this function that performs the most important task in our program, namely, deciding which materials in the shortlist meet the specification:

(defun meets_one (spec shortlist)

	(dolist (material shortlist)

		(let ((actual (get_database_value (first spec) 				(first material))))

			(if (< actual (- (nth 1 spec) (nth 2 spec)))

				(setf shortlist (remove material shortlist)))))

				;;pseudo-C equivalent:

				;;if actual < (value - tolerance)

				;;shortlist=shortlist without material

shortlist)

We have already met most of the Lisp functions that make up meets_one. In order to consider each material–type pair in the shortlist, dolist is used. The actual value of a property (such as maximum operating temperature) for a given material is found by passing the property name and the material name as arguments to the function get_database_value, which has yet to be defined. The value returned from get_database_value is stored in the local variable actual. The value of actual is then compared with the result of subtracting the specified tolerance from the specified target value. In our example, the tolerance is used simply to make the specification less severe. It may be surprising at first to see that subtraction and arithmetic comparison are both handled as functions within Lisp. Nevertheless, this treatment is consistent with other Lisp operations. The code includes a comment showing the conventional positioning of the operators in other languages such as C. Note that nth is used in order to extract the second and third elements of spec, which represent the specification value and tolerance, respectively.

If the database value, actual, of the property in question is less than the specification value minus the tolerance, then the material is removed from the shortlist. The Lisp function remove is provided for this purpose. Because the arguments to the function are evaluated before the function itself, it follows that remove is not able to alter shortlist itself. Rather, it returns the list that would be produced if material were removed from a copy of shortlist. Therefore, setf has to be used to set shortlist to this new value.

As in our other functions, shortlist is evaluated, so its value will be returned as the value of the function meets_one. At a glance, it may appear that this is unnecessary, as setf would return the value of shortlist. However, it is important to remember that this function is embedded within other functions. The last function to be evaluated is in fact dolist. When dolist terminates by reaching the end of shortlist, it returns the empty list, (), which is clearly not the desired result.

There now remains only one more function to define in order to make our Lisp program work, namely, get_database_value. As mentioned previously, get_database_value should return the actual value of a property for a material, when the property and material names are passed as arguments. Common Lisp provides us with the function find, which is ideally suited to this task. The syntax of find is best illustrated by example. The following function call will search the list materials_database until it finds a list whose first element is identically equal (eq) to the value of material:

(find material materials_database :test #'eq :key #'first)

Other tests and keys can be used in conjunction with find, as defined in (Steele 1990). Having found the data corresponding to the material of interest, the name and type can be removed using nthcdr, and find can be called again in order to find the list corresponding to the property of interest. The function get_database_value can therefore be written as follows:

(defun get_database_value (prop_name material)

	(nth 1 (find prop_name

		(nthcdr 2

			(find material materials_database :test #'eq :key

				#'first))

		:test #'eq :key #'first)))

We are now in a position to put our program together, as shown in Box 10.2, and to ask Lisp some questions about polymers:

<cl> (accept '(maximum_temperature 100 5))

((SILICONE . THERMOSET) (POLYPROPYLENE . THERMOPLASTIC))

<cl> (accept '((maximum_temperature 100 5)

(impact_resistance 0.05 0)))

((POLYPROPYLENE . THERMOPLASTIC))

Once the function definitions have been evaluated, each function (such as accept) becomes known to Lisp in the same way as all of the predefined functions such as setf and dolist. Therefore, we have extended the Lisp language so that it has become specialized for our own specific purposes. It is this ability that makes Lisp such a powerful and flexible language. If a programmer does not like the facilities that Lisp offers, he or she can alter the syntax by defining his or her own functions, thereby producing an alternative language. Lisp-based KBS toolkits can be built on this basis.

(defvar materials_database nil)

(setf materials_database '(

	(abs thermoplastic

		(impact_resistance 0.2)

 		(flexural_modulus 2.7)

		(maximum_temperature 70))

	(polypropylene thermoplastic

		(impact_resistance 0.07)

		(flexural_modulus 1.5)

		(maximum_temperature 100))

	(polystyrene thermoplastic

		(impact_resistance 0.02)

		(flexural_modulus 3.0)

		(maximum_temperature 50))

	(polyurethane_foam thermoset

		(impact_resistance 1.06)

		(flexural_modulus 0.9)

		(maximum_temperature 80))

	(pvc thermoplastic

		(impact_resistance 1.06)

		(flexural_modulus 0.007)

		(maximum_temperature 50))

	(silicone thermoset

		(impact_resistance 0.02)

		(flexural_modulus 3.5)

		(maximum_temperature 240))))

(defun accept (spec_list)

	(let ((shortlist (setup)))

		(if (atom (first spec_list))

;;if the first element of spec_list is an atom,

;;then consider the specification

		(setf shortlist (meets_one spec_list shortlist))

;;else consider each specification in turn

		(dolist (each_spec spec_list)

			(setf shortlist (meets_one each_spec shortlist))))

		shortlist)) ;return shortlist

(defun setup ()

	(let ((shortlist nil))

		(dolist (material materials_database)

			(setf shortlist (cons (cons (first material) (nth 1 material)) shortlist)))

		shortlist))

(defun meets_one (spec shortlist)

	(dolist (material shortlist)

		(let ((actual (get_database_value (first spec) (first material))))

			(if (< actual (- (nth 1 spec) (nth 2 spec)))

				(setf shortlist (remove material shortlist)))))

	;;pseudo-C equivalent:

	;;if actual< (value - tolerance)

	;;shortlist=shortlist without material

shortlist)

(defun get_database_value (prop_name material)

	(nth 1 (find prop_name

		(nthcdr 2

			(find material materials_database :test #'eq :key

				#'first))

		:test #'eq :key #'first)))

10.4 Prolog

10.4.1 Background

Prolog is an AI language that can be programmed declaratively. It is, therefore, very different from Lisp, which is a procedural (or, more precisely, functional) language that can nevertheless be used to build declarative applications. As we will see, although Prolog can be used declaratively, an appreciation of the procedural behavior of the language is needed. In other words, programmers need to understand how Prolog uses the declarative information that they supply.

Prolog is suited to symbolic (rather than numerical) problems, particularly logical problems involving relationships between items. It is also suitable for tasks that involve data lookup and retrieval, as pattern-matching is fundamental to the functionality of the language. Because Prolog is so different from other languages in its underlying concepts, many newcomers find it a difficult language. Whereas most languages can be learned rapidly by someone with computing experience, Prolog is perhaps more easily learned by someone who has never programmed.

10.4.2 A Worked Example

The main building blocks of Prolog are lists (as in Lisp) and relations, which can be used to construct clauses. We will demonstrate the declarative nature of Prolog programs by constructing a small program for selecting polymers from a database of polymer properties. The task will be identical to that used to illustrate Lisp, namely selecting from a database those polymers that meet a numerical specification or set of specifications. The problem is described in more detail in Box 10.1. We have already said that Prolog is good for data lookup, so let us begin by creating a small database containing some properties of materials. Our database will comprise a number of clauses such as this one involving the relation materials_database:

materials_database(polypropylene, thermoplastic, [maximum_temperature, 100]).

The preceding clause means that the three items in parentheses are related through the relation called materials_database. The third argument of the clause is a list (denoted by square brackets), while the first two arguments are atoms. The clause is our first piece of Prolog code, and it is purely declarative. We have given the computer some information about polypropylene, and this is sufficient to produce a working (though rather trivial) program. Even though we have not given Prolog any procedural information (i.e., we have not told it how to use the information about polypropylene), we can still ask it some questions. Having typed the above line of Prolog code, not forgetting the period, we can ask Prolog the question:

“What type of material is polypropylene?”

Depending on the Prolog implementation, the screen prompt is usually ?-, indicating that what follows is treated as a query. Our query to Prolog could be expressed as:

?- materials_database(polypropylene, Family, _).

Prolog would respond:

Family = thermoplastic

This simple example illustrates several features of Prolog. Our program is a single line of code that states that polypropylene is a material of type thermoplastic and has a maximum operating temperature of 100 (°C assumed). Thus, the program is purely declarative. We have told Prolog what we know about polypropylene, but have given Prolog no procedural instructions about what to do with that information. Nevertheless, we were able to ask a sensible question and receive a sensible reply. Our query includes some distinct data types. As polypropylene began with a lowercase letter, it was recognized as a constant, whereas Family was recognized as a local variable by virtue of beginning with an uppercase letter. These distinctions stem from the following rules, which are always observed:

• local variables in Prolog can begin either with an uppercase letter or with an underscore character (for example, X, My_variable, _another are all valid variable names); and
• constants begin with a lowercase letter (for example, adrian, polypropylene, pi are all valid names for constants).

When presented with our query, Prolog has attempted to match the query to the relations (only one relation in our example) that it has stored. In order for any two terms to match, either:

• the two terms must be identical; or
• it must be possible to set (or instantiate) any local variables in such a way that the two terms become identical.

If Prolog is trying to match two or more clauses and comes across multiple occurrences of the same local variable name, it will always instantiate them identically. The only exception to this rule is the underscore character, which has a special meaning when used on its own. Each occurrence of the underscore character’s appearing alone means:

I don’t care what ‘_’ matches so long as it matches something.

Multiple occurrences of the character can be matched to different values. The ‘_’ character is used when the value of a variable is not needed in the evaluation of a clause. Thus:

materials_database(polypropylene, thermoplastic, [maximum_temperature, 100]).

matches:

materials_database(polypropylene, Family, _).

The relation name, materials_database, and its number of arguments (or its arity) are the same in each case. The first argument to materials_database is identical in each case, and the remaining two can be made identical by instantiating the variable Family to thermoplastic and the underscore variable to the list [maximum_temperature, 100]. We don’t care what the underscore variable matches, so long as it matches something.

Now let us see if we can extend our example into a useful program. First we will make our database more useful by adding some more data:

materials_database(abs, thermoplastic,

	[[impact_resistance, 0.2],

		[flexural_modulus, 2.7],

		[maximum_temperature, 70]]).

materials_database(polypropylene, thermoplastic,

	[[impact_resistance, 0.07],

		[flexural_modulus, 1.5],

		[maximum_temperature, 100]]).

materials_database(polystyrene, thermoplastic,

	[[impact_resistance, 0.02],

		[flexural_modulus, 3.0],

		[maximum_temperature, 50]]).

materials_database(polyurethane_foam, thermoset,

	[[impact_resistance, 1.06],

		[flexural_modulus, 0.9],

		[maximum_temperature, 80]]).

materials_database(pvc, thermoplastic,

	[[impact_resistance, 1.06],

		[flexural_modulus, 0.007],

		[maximum_temperature, 50]]).

materials_database(silicone, thermoset,

	[[impact_resistance, 0.02],

		[flexural_modulus, 3.5],

		[maximum_temperature, 240]]).

Our aim is to build a program that can select from the database those materials that meet a set of specifications. This requirement can be translated directly into a Prolog rule:

accept(Material,Type,Spec_list):-

	materials_database(Material,Type,Stored_data),

	meets_all_specs(Spec_list,Stored_data).

The :- symbol stands for the word “if” in the rule. Thus, the rule just stated means:

accept a material, given a list of specifications, if that material is in the database and if the stored data about the material meet the specifications.

We now have to let Prolog know what we mean by a material meeting all of the specifications in the user’s specification list. The simplest case is when there are no specifications at all, in other words, the specification list is empty. In this case, the (nonexistent) specifications will be met regardless of the stored data. This fact can be simply coded in Prolog as:

meets_all_specs([],_).

The next most straightforward case to deal with is when there is only one specification, which we can code as follows:

meets_all_specs(Spec_list, Data):-

	Spec_list= [Spec1|Rest],

	atom(Spec1),

	meets_one_spec([Spec1|Rest],Data).

This rule introduces the list separator |, which is used to separate the first element of a list from the rest of the list. As an example, consider the following Prolog query:

?- [Spec1|Rest] = [flexural_modulus, 1.0, 0.1]. Spec1 = flexural_modulus, Rest = [1,0.1]

The assignments to the variables immediately before and after the list separator are analogous to taking the first and rest of a list in Lisp. Consistent with this analogy, the item immediately following a | symbol will always be instantiated to a list. Returning now to our rule, the first condition requires Prolog to try to match Spec_list to the template [Spec1|Rest]. If the match is successful, Spec1 will become instantiated to the first element of Spec_list and Rest instantiated to Spec_list with its first element removed.

We could make our rule more compact by combining the first condition of the rule with the arguments to the goal:

meets_all_specs([Spec1|Rest], Data):-

	atom(Spec1),

	meets_one_spec([Spec1|Rest],Data).

If the match is successful, we need to establish whether Spec_list contains one or many specifications. This goal can be achieved by testing the type of its first element. If the first element is an atom, the user has supplied a single specification, whereas a list indicates that more than one specification has been supplied. All this assumes that the intended format was used for the query. The built-in Prolog relation atom succeeds if its argument is an atom, and otherwise it fails.

We have not yet told Prolog what is meant by the relation called meets_one_spec, but we will do so shortly. Next, we will consider the general case where the user has supplied several specifications:

meets_all_specs([Spec1|Rest],Data):-

	not atom(Spec1),

	meets_one_spec(Spec1,Data),

	meets_all_specs(Rest,Data).

An important feature demonstrated by this rule is the use of recursion, that is, the reuse of meets_all_specs within its own definition. Our rule says that the stored data meets the user’s specification if each of the following is satisfied:

• We can separate the first specification from the remainder.
• The first specification is not an atom.
• The stored data meet the first specification.
• The stored data meet all of the remaining specifications.

When presented with a list of specifications, individual specifications will be stripped off the list one at a time, and the rule will be deemed to have been satisfied if the stored data satisfy each of them.

Having dealt with multiple specifications by breaking down the list into a set of single specifications, it now remains for us to define what we mean by a specification being met. This requirement is coded as follows:

meets_one_spec([Property, Spec_value, Tolerance], List):-

	member([Property, Actual_value], List),

	Actual_value>Spec_value-Tolerance.

As in the Lisp example, we explicitly state that a user’s specification must be in a fixed format, that is, the material property name, its target value, and the tolerance of that value must appear in sequence in a list. A new relation called member is introduced in order to check that the stored data for a given material include the property being specified, and to assign the stored value for that property to Actual_value. If the relation member is not built into our particular Prolog implementation, we will have to define it ourselves. Finally, the stored value is deemed to meet the specification if it is greater than the specification minus the tolerance.

The definition of member (taken from (Bratko 2011)) is similar in concept to our definition of meets_all_specs. The definition is that an item is a member of a list if that item is the first member of the list or if the list may be split so that the item is the first member of the second part of the list. This can be expressed more concisely and elegantly in Prolog than it can in English:

member(A,[A|L]).

member(A,[_|L]):-member(A,L).

Our program is now complete and ready to be interrogated. The program is shown in full in Box 10.3. In order to run a Prolog program, Prolog must be set a goal that it can try to prove. If successful, it will return all of the sets of instantiations necessary to satisfy that goal. In our case, the goal is to find the materials that meet some specifications.

Now let us test our program with some example queries (or goals). First, we will determine which materials have a maximum operating temperature of at least 100°C, with a 5°C tolerance:

?- accept(M, T, [maximum_temperature, 100, 5]).

M = polypropylene, T = thermoplastic;

M = silicone, T = thermoset;

no

The word no at the end indicates that Prolog’s final attempt to find a match to the specification, after it had already found two such matches, was unsuccessful. We can now extend our query to find all materials that, as well as meeting the temperature requirement, have an impact resistance of at least 0.05 kJ/m:

?- accept(M,T,[[maximum_temperature, 100, 5],

	[impact_resistance, 0.05, 0]]).

M = polypropylene, T = thermoplastic;

no

materials_database(abs, thermoplastic,

	[[impact_resistance, 0.2],

		[flexural_modulus, 2.7],

		[maximum_temperature, 70]]).

materials_database(polypropylene, thermoplastic,

	[[impact_resistance, 0.07],

		[flexural_modulus, 1.5],

		[maximum_temperature, 100]]).

materials_database(polystyrene, thermoplastic,

	[[impact_resistance, 0.02],

		[flexural_modulus, 3.0],

		[maximum_temperature, 50]]).

materials_database(polyurethane_foam, thermoset,

	[[impact_resistance, 1.06],

		[flexural_modulus, 0.9],

		[maximum_temperature, 80]]).

materials_database(pvc, thermoplastic,

	[[impact_resistance, 1.06],

		[flexural_modulus, 0.007],

		[maximum_temperature, 50]]).

materials_database(silicone, thermoset,

	[[impact_resistance, 0.02],

		[flexural_modulus, 3.5],

		[maximum_temperature, 240]]).

accept(Material,Type,Spec_list):-

	materials_database(Material,Type,Stored_data),

	meets_all_specs(Spec_list,Stored_data).

meets_all_specs([],_).

meets_all_specs([Spec1|Rest],Data):-

	atom(Spec1),

	meets_one_spec([Spec1|Rest],Data).

meets_all_specs([Spec1|Rest],Data):-

	not atom(Spec1),

	meets_one_spec(Spec1,Data),

	meets_all_specs(Rest,Data).

meets_one_spec([Property, Spec_value, Tolerance], List):-

	member([Property, Actual_value], List),

	Actual_value>Spec_value-Tolerance.

member(A,[A|L]).

member(A,[_|L]):-member(A,L).

10.4.3 Backtracking in Prolog

So far we have seen how to program declaratively in Prolog, without giving any thought to how Prolog uses the declarative program to decide upon a sequential series of actions. In the example shown in the earlier section, it was not necessary to know how Prolog used the information supplied to arrive at the correct answer. This represents the ideal of declarative programming in Prolog. However, the Prolog programmer invariably needs to have an idea of the procedural behavior of Prolog in order to ensure that a program performs correctly and efficiently. In many circumstances, it is possible to type a valid declarative program, but for the program to fail to work as anticipated because the programmer has failed to take into account how Prolog works.

Let us start by considering our last example query to Prolog:

?- accept(M,T,[[maximum_temperature, 100, 5],

	[impact_resistance, 0.05, 0]]).

Prolog treats this query as a goal, whose truth it attempts to establish. As the goal contains some variables (M and T), these will need to be instantiated in order to achieve the goal. Prolog’s first attempt at achieving the goal is to see whether the program contains any clauses that directly match the query. In our example it does not, but it does find a rule with the accept relation as its conclusion:

accept(Material,Type,Spec_list):-

	materials_database(Material,Type,Stored_data),

	meets_all_specs(Spec_list,Stored_data).

Prolog now knows that the goal will be achieved if it can establish the two conditions of this rule with M matched to Material, T matched to Type, and Spec_list instantiated to [[maximum_temperature, 100, 5], [impact_resistance, 0.05, 0]]. The two conditions then become goals in their own right. The first one, involving the relation materials_database, is easily achieved, and the second condition:

meets_all_specs(Spec_list,Stored_data).

becomes the new goal. Prolog’s first attempt at satisfying this goal is to look at the relation:

meets_all_specs([],_).

However, this does not help as Spec_list is not instantiated to an empty list. Prolog must at this point backtrack to try another way of achieving the current subgoal. In other words, Prolog remembers the stage where it was before the failed attempt and resumes its reasoning along another path from there. Figure 10.1 shows the reasoning followed by Prolog when presented with the goal:

?- accept(M,T,[[maximum_temperature, 100, 5],

	[impact_resistance, 0.05, 0]]).

The illustration shows Prolog’s first attempt at a solution, namely, M=abs and T=thermoplastic, and the steps that are followed before rejecting these particular instantiations as a solution. The use of backtracking is sensible up until the point where it is discovered that the maximum operating temperature of ABS (acrylonitrile-butadiene-styrene) is too low. When this has been determined, we would ideally like the program to reject ABS as a candidate material and move on to the next contender. However, Prolog does not give up so easily. Instead, it backtracks through every step that it has taken, checking to see whether there may be an alternative solution (or set of instantiations) that could be used. Ultimately it arrives back at the materials_database relation, and Material and Type become reinstantiated.

Prolog provides two facilities for controlling backtracking. They can be used to increase efficiency and to alter the meaning of a program. These facilities are:

• the order of Prolog code;
• the use of the cut operator.

Prolog tries out possible solutions to a problem in the order in which they are presented. Thus, in our example, Prolog always starts by assuming that the user has supplied a single materials specification. Only when it discovers that this is not the case does Prolog consider that the user may have submitted a list of several specifications. This is an appropriate ordering, as it is sensible to try the simplest solution first. In general, the ordering of code will affect the procedural meaning of a Prolog program (i.e., how the problem will be solved), but not its declarative meaning. However, as soon as the Prolog programmer starts to use the second facility, namely, the cut operator, the order of Prolog clauses can affect both the procedural and the declarative meaning of programs.

In order to prevent Prolog from carrying out unwanted backtracking, the cut symbol (!) can be used. Cuts can be inserted as though they were goals in their own right. When Prolog comes across a cut, backtracking is prevented. Cuts can be used to make our example program more efficient by forcing Prolog immediately to try a new material once it has established whether or not a given material meets the specification. The revised program, with cuts included, is shown in Box 10.4 (the setting up of the materials_database relations is unchanged and has been omitted).

Although the discussion so far has regarded the cut as a means of improving efficiency by eliminating unwanted backtracking, cuts can also alter the declarative meaning of programs. This can be illustrated by referring once again to our materials selection program. The program contains three alternative means of achieving the meets_all_specs goal. The first deals with the case where the first argument is the empty list. The two others take identical arguments, and a distinction is made based upon whether the first element of the first argument (a list) is an atom. If the element is an atom, then the alternative case need not be considered, and this can be achieved using a cut (note that % indicates a comment):

accept(Material,Type,Spec_list):-

	materials_database(Material,Type,Stored_data),

	meets_all_specs(Spec_list,Stored_data).

meets_all_specs([],_):-!.

meets_all_specs([Spec1|Rest],Data):-

	atom(Spec1),!,

	meets_one_spec([Spec1|Rest],Data).

meets_all_specs([Spec1|Rest],Data):-

	meets_one_spec(Spec1,Data),

	meets_all_specs(Rest,Data).

meets_one_spec([Property, Spec_value, Tolerance], List):-

	member([Property, Actual_value], List),!,

	Actual_value>Spec_value-Tolerance.

member(A,[A|L]).

member(A,[_|L]):-member(A,L).

meets_all_specs([Spec1|Rest],Data):-

	atom(Spec1),!, % cut placed here

	meets_one_spec([Spec1|Rest],Data).

meets_all_specs([Spec1|Rest],Data):-

	not atom(Spec1), % this test is now redundant

	meets_one_spec(Spec1,Data),

	meets_all_specs(Rest,Data).

Because of the positioning of the cut, if:

atom(Spec1)

is successful, then the alternative rule will not be considered. Therefore, the test:

not atom(Spec1)

is now redundant and can be removed. However, this test can only be removed provided that the cut is included in the previous rule. This example shows that a cut can be used to create rules of the form:

if <condition> then <conclusion1> else <conclusion2>.

While much of the earlier discussion has concentrated on overcoming the inefficiencies that backtracking can introduce, it is important to remember that backtracking is essential for searching out a solution, and the elegance of Prolog in many applications lies in its ability to backtrack without the programmer needing to program this behavior explicitly.

10.5 Comparison of AI Languages

For each AI language, the worked example gives some feel for the language structure and syntax. However, it does not form the basis for a fair comparison of their merit. The Prolog code is the most compact and elegant solution to the problem of choosing materials that meet a specification, because Prolog is particularly good at tasks that involve pattern matching and retrieval of data. However, the language places a number of constraints on the programmer, particularly in committing him or her to one particular search strategy. As we have seen, the programmer can control this strategy to some extent by judicious ordering of clauses and use of the cut mechanism. Prolog doesn’t need a structure for iteration, for example, for x from 1 to 10, as recursion can be used to achieve the same effect.

Our Lisp program has a completely different structure from the Prolog example, as it has been programmed procedurally (or, more precisely, functionally). The language provides excellent facilities for manipulating symbols and lists of symbols. It is a powerful language that allows practically any reasoning strategy to be implemented. In fact, it is so flexible that it can be reconfigured by the programmer, although the worked example does not do justice to this flexibility. In particular, the materials database took the form of a long, flat list, whereas there are more structured ways of representing the data. As we have seen in Chapter 4, and will see in Chapter 12, object-oriented and frame-based programming allow a hierarchical representation of materials properties.

10.6 Summary

The two AI languages introduced here, Lisp and Prolog, are both well-suited to problems involving the manipulation of symbols. They can, therefore, form a good basis for the development of knowledge-based systems, although AI toolkits and extensions to conventional programming languages are a practical alternative. The AI languages are less suited than conventional languages to numerical problems.

Both AI languages are flexible, elegant, and concise. In contrast with conventional languages, the same variable in an AI language can be used to hold a variety of data types. Both AI languages allow various types of data to be combined into lists, and they provide facilities for list manipulation.

Most programming languages are procedural rather than declarative, but the Prolog language incorporates both programming styles. To enable declarative programming, Prolog includes a backtracking mechanism that allows it to explore all possible ways in which a goal might be achieved. The programmer can exercise control over Prolog’s backtracking by careful ordering of clauses and through the use of cuts.

In Lisp, lists are not only used for data, but also constitute the programs themselves. Lisp functions are represented as lists containing a function name and its arguments. As every Lisp function returns a value, the arguments themselves can be functions.

Further Reading

Barski, C. 2010. Land of Lisp. No Starch Press, San Francisco, CA.

Blackburn, P., J. Bos, and K. Striegnitz. 2006. Learn Prolog Now! College Publications, London.

Bramer, M. 2005. Logic Programming with Prolog. Springer, New York.

Bratko, I. 2011. Prolog Programming for Artificial Intelligence. 4th ed. Addison-Wesley, Reading, MA.

Clocksin, W. F., and C. S. Mellish. 2003. Programming in Prolog: Using the ISO Standard. 5th ed. Springer, New York.

Graham, P. 1995. The ANSI Common Lisp Book. Prentice Hall, Englewood Cliffs, NJ.

Kreiker, P. 2000. Visual Lisp: Guide to Artful Programming. Delmar, Albany, NY.

Luger, G. F., and W. A. Stubblefield. 2008. AI Algorithms, Data Structures, and Idioms in Prolog, Lisp, and Java. 6th ed. Addison-Wesley, Boston, MA.

Scott, R. 2010. A Guide to Artificial Intelligence with Visual Prolog. Outskirts Press, Denver, CO.

Seibel, P. 2005. Practical Common Lisp. Apress, New York.

Steele, G. L. 1990. Common Lisp: The Language. 2nd ed. Digital Press, Bedford, MA.