Leon Sterling. Ehud Shapiro with a foreword by David H. D. Warren. The Art of Prolog. Advanced Programming Techniques. Second Edition. The MIT Press. Title The Art of Prolog: Advanced Programming Techniques; Author(s) Leon S. Edition,Second edition (March 10, ); Hardcover pages; eBook PDF. This new edition of The Art of Prolog contains a number of important changes. Most background Open Access Title. Download PDF Support Open Access.
|Language:||English, Japanese, Hindi|
|Genre:||Academic & Education|
|ePub File Size:||27.33 MB|
|PDF File Size:||20.85 MB|
|Distribution:||Free* [*Registration Required]|
Views 40MB Size Report. DOWNLOAD PDF The Art of Prolog Advanced Programming Techniques Second Edition The MIT Press Cambridge. The Art of Prolog 2nd Ed - Leon Sterling, Ehud redelocidi.cf The_Art_of_Work redelocidi.cf The Art of Work: A Proven Path . The Art of Prolog (2nd Ed) - Leon Sterling, Ehud Shapiro - Free ebook download as PDF File .pdf) or read book online for free.
There is a single data structure: Facts are a means of stating that a relation holds between objects. An example is father abraham,isaac This fact says that Abraham is the father of Isaac, or that the relation father holds between the individuals named abraham and isaac.
Another name for a relation is a predicate. Names of individuals are known as atoms. Similarly, plus 2 , 3 , 5 expresses the relation that 2 plus 3 is 5. The familiar plus relation can be realized via a set of facts that defines the addition table. An initial segment of the table is plus O,O,0. A sufficiently large segment of this table, which happens to be also a legal logic program, will be assumed as the definition of the plus relation throughout this chapter.
The syntactic conventions used throughout the book are introduced as needed. The first is the case convention. It is significant that the names Basic Constructs Chapter 1 father terach,abraham father terach,nachor.
Logical consequences are obtained by applying deduction rules. The simplest rule of deduction is identity: A query is a logical consequence of an identical fact.
Operationally, answering simple queries using a program containing facts like Program 1. Search for a fact in the program that implies the query. If a fact identical to the query is found, the answer is yes. The answer no is given if a fact identical to the query is not found, because the fact is not a logical consequence of the program.
This answer does not reflect on the truth of the query; it merely says that we failed to prove the query from the program. Both the queries female abraham? Program 1. A finite set of facts constitutes a program.
This is the simplest form of logic program. A set of facts is also a description of a situation. This insight is the basis of database programming, to be discussed in the next chapter. The predicates f a t h e r , mother, male, and female express the obvious relationships.
Queries are a means of retrieving information from a logic program. A query asks whether a certain relation holds between objects. For example, the query father abraham, i s a a c? Given the facts of Program 1. Syntactically, queries and facts look the same, but they can be distinguished by the context. When there is a possibility of confusion, a terminating period will indicate a fact, while a terminating question mark will indicate a query.
We call the entity without the period or question mark a goal. A fact P. A query P? A simple query consists of a single goal. Answering a query with respect to a program is determining whether the query is a logical consequence of the program.
We define logical -- - - -- - - - 1. Consider its use in queries. Suppose we want to know of whom abraham is the father. One way is to ask a series of queries, f ather abraham, l o t?
A variable allows a better way of expressing the query as f a t h e r abraham, X? Used in this way, variables are a means o f summarizing many queries. A query containing a variable asks whether there is a value for the variable that makes the query a logical consequence of the program, as explained later.
Variables in logic programs behave differently from variables in conventional programming languages. They stand for an unspecified but single entity rather than for a store location in memory. Having introduced variables, we can define a term, the single data structure in logic programs. The definition is inductive. Constants and variables are terms. Also compound terms, or structures, are terms. A compound term comprises a functor called the principal functor of the term and a sequence of one or more arguments, which are terms.
A functor is characterized by its name, which is an atom, and its arity, or number of arguments. Syntactically, compound terms have Chapter 1 Basic Constructs the form f tl,tz,.. Examples of compound terms include s O , hot milk , name john,doe , list a,list b,nil , foo X , and tree tree nil,3,nil , 5 , R. Queries, goals, and more generally terms where variables do not occur are called ground.
Where variables do occur, they are called nonground. For example, foo a,b is ground, whereas bar XI is nonground. Substitutions can be applied to terms. Definition A is an instance of B if there is a substitution 8 such that A 1. If found, the answer, or solution, is that instance. A solution is represented in this chapter by the substitution that, if applied to the query, results in the solution.
The answer is no if there is no suitable fact in the program. In general, an existential query may have several solutions. Thus the query father haran,? Another query with multiple solutions is plus X,Y,4?
Note that the different variables X and Y correspond to possibly different objects. An interesting variant of the last query is plus X ,X ,4? Variables are also useful in facts. Suppose that all the biblical characters like pomegranates. Instead of including in the program an appropriate fact for every individual, - 1. The next deduction rule we introduce is generalization. An existential query P is a logical consequence of an instance of it, PO, for any substitution 8.
Used in this way, variables are a means of summarizing many facts. The fact times 0,X , 0 summarizes all the facts stating that 0 times some number is 0. Variables in facts are implicitly universally quantified, which means, intuitively, that the fact likes X,pomegranates states that for all X, X likes pomegranates. In general, a fact p Tl,. Logically, from a universally quantified fact one can deduce any instance of it.
For example, from likes X,pomegranates , deduce likes abraham,pomegranates. Chupter 1 This is the third deduction rule, called instantiation. From a universally quantified statement P, deduce an instance of it, P Q , for any substitution 0.
As for queries, two unspecified objects, denoted by variables, can be constrained to be the same by using the same variable name. The fact p l u s 0 , X, X expresses that 0 is a left identity for addition. It reads that for all values of X, 0 plus X is X. A similar use occurs when translating the English statement "Everybody likes himself" to l i k e s X, X. Answering a ground query with a universally quantified fact is straightforward.
Search for a fact for which the query is an instance. For example, the answer to p l u s 0 , 2 , 2? Answering a nonground quer? In general, to ansn,er a query using a fact, search for a common instance of the querj. The anslver is the common instance, if one exists. Otherwise the answer is no. Conjunctive queries are a conjunction of goals posed as a query,.
Logically, it asks whether a conjunction is deducible from the program. We use "," throughout to denote logical and. Do not confuse the comma that separates the arguments in a goal with commas used to separate goals, denoting conjunction.
In the simplest conjunctive queries all the goals are ground, for example, f a t h e r abraham, i s a a c ,male l o t?. The answer to this query using Program 1. I is clearly yes because both goals in the query are facts in. In general, the query goal, is answered yes with respect to a program P if each is implied by P. Hence ground conjunctive queries are not very interesting. Conjunctive queries are interesting when there are one or more shared variables, variables that occur in two different goals of the query.
The scope of a variable in a conjunctive query, as in a simple query, is the whole conjunction. Thus the quer? We have already seen an example cvith the query p l u s X ,X ,4? Alternatively, this query can be viewed as restricting solutions to the query male XI?
On the one hand, it restricts the sons of t e r a c h to those who are themselves fathers. On the other hand, it considers individuals Y, whose fathers are sons of t e r a c h. A sufficient condition is that there be a ground instance of the query that is a consequence of P. This instance then deduces the conjuncts in the query via generalization. The restriction to ground instances is unnecessary and will be lifted in Chapter 4 when we discuss the computation model of logic programs.
Chapter 1 Basic Constructs We employ this restriction in the meantime to simplify the discussion in the coming sections. Operationally, to solve the conjunctive query A1,A2,.. The same substitution applied to all the goals ensures that instances of variables are common throughout the query. For example, consider the query f a t h e r h a r a n , X ,male XI?
A rule for the g r a n d f a t h e r relationship is Interesting conjunctive queries are defining relationships in their own right. The query f a t h e r haran,X ,male X?
This brings us to the third and most important statement in logic programming, a rule, which enables us to define new relationships in terms of existing relationships. Rules are statements of the form: The goal A is the head of the rule, and the conjunction of goals B,,.
Rules, facts, and queries are also called Horn clauses, or clauses for short. Facts are also called unit clauses. Such a clause is called an iterative clause. As for facts, variables appearing in rules are universally quantified, and their scope is the whole rule. Similarly one can define a rule for the daughter relationship: First, they are a means of expressing new or complex queries in terms of simple queries.
A query son X ,haran?
A new query about the son relationship has been built from simple queries involving f a t h e r and male relationships. Interpreting rules in this way is their procedural reading.
The procedural reading for the g r a n d f a t h e r rule is: The backward arrow -is used to denote logical implication. The son rule reads: The predicate son has been defined in terms of the predicates f a t h e r and male. The associated reading of the rule is known as the declarative reading. The declarative reading of the g r a n d f a t h e r rule is: Whenever it is a source of confusion, the reader can resort back to the formal reading of a clause, in which all variables are universally quantified from the outside.
To incorporate rules into our framework of logical deduction, we need the law of modus ponens. Modus ponens states that from B and A B we can deduce A. Then recursively solve each B,8.
It is difficult in general to guess the correct ground instance and to choose the right rule. We show in Chapter 4 how the guessing of an instance can be removed. The rule given for son is correct but is an incomplete specification of the relationship. For example, we cannot conclude that Isaac is the son of Sarah.
What is missing is that a child can be the son of a mother as well as the son of a father. A new rule expressing this relationship can be added, namely, and the facts A' can be deduced if is an instance of R. We are now in a position to give a complete definition of the concept of a logic program and of its associated concept of logical consequence.
Definition A logic program is a finite set of rules. Definition An existentially quantified goal G is a logical consequence of a program P if there is a clause in P with a ground instance A B 1 ,.. Both the goals in the body of this rule are facts in Program 1. Thus universal modus ponens implies the quer? Operationally, answering queries reflects the definition of logical conseauence. Guess a ground instance of a goal, and a ground instance of a rule, and recursively answer the conjunctive query corresponding to the body of that rule.
There is a better, more compact, n-a ,of expressing these rules. The rules defining p a r e n t are straightforward, capturing the definition of a parent being a father or a mother.
Logic programs can incorporate a1ternatik. A collection of rules with the same predicate in the head, such as the pair of parent rules, is called a procedure. We shall see later that under the operational interpretation of these rules by Prolog, such a collection of rules is indeed the analogue of procedures or subroutines in conventional programming languages.
Reference Manual on Scientific Evidence: Third Edition
Basic Constructs Chapter 1 - - -- -- -- p - -- - Input: In this section, the details are fleshed out into an abstract interpreter for logic programs. In keeping with the restriction of universal modus ponens to ground goals, the interpreter only answers ground queries. It takes as input a program and a goal, and answers yes if the goal is a logical consequence of the program and no otherwise. The interpreter is given in Figure 1.
Note that the interpreter may fail to terminate if the goal is not deducible from the program, in which case no answer is given. The current, usually conjunctive, goal at any stage of the computation is called the resolvent.
A trace of the interpreter is the sequence of resolvents produced during the computation. Figure 1.
The Art of Prolog, Second Edition: Advanced Programming Techniques
For clarit. Each iteration of the while loop of the abstract interpreter corresponds to a single application of modus ponens. This is called a reduction. Initialize the resolvent to G. A' -B,,. A reduction is the basic computational step in logic programming. The goal replaced in a reduction is reduced, and the new goals are derived. In this chapter, we restrict ourselves to ground reductions, where the goal and the instance of the clause are ground. Later, in Chapter 4, we consider more general reductions where unification is used to choose the instance of the clause and make the goal to be reduced and the head of the clause identical.
Basic Constructs Chapter 1 The trace in Figure 1. The second reduction is of f a t h e r h a r a n , l o t and produces no derived goals. The third reduction also produces no derived goals in reducing male l o t.
There are two unspecified choices in the interpreter in Figure 1. The first is the goal to reduce from the resolvent. The second choice is the clause and an appropriate ground instance to reduce the goal. These two choices have very different natures.
The selection of the goal to be reduced is arbitrary. In any given resolvent, all the goals must be reduced. It can be shown that the order of reductions is immaterial for answering the query. In contrast, the choice of the clause and a suitable instance is critical.
In general, there are several choices of a clause, and infinitely many ground instances. The choice is made nondeterministically.
The concept of nondeterministic choice is used in the definition of many computation models, e. A nondeterministic choice is an unspecified choice from a number of alternatives, which is supposed to be made in a "clairvoyant" way. If only some of the alternatives lead to a successful computation, then one of them is chosen.
Formally, the concept is defined as follows. A computation that contains nondeterministic choices succeeds if there is a sequence of choices that leads to success. Of course, no real machine can directly implement this definition. However, it can be approximated in a useful way, as done in Prolog.
This is explained in Chapter 6. The interpreter given in Figure 1. Guess a ground instance of the query. This is identical to the step in the interpreter of guessing ground instances of the rules. It is difficult in general to guess the correct ground instance, since that means knowing the result of the computation before performing it. A new concept is needed to lift the restriction to ground instances and remove the burden of guessing them.
In Chapter 4, we show how the guess of ground instances can be eliminated, and we introduce the computational model of logic programs more fully. IJntil then it is assumed that the correct choices can be made. A more convenient representation of the proof is with a proof tree. A proof tree consists of nodes and edges that represent the goals reduced during the computation.
The root of the proof tree for a simple query is the query itself. The nodes of the tree are goals that are reduced during the computation. There is a directed edge from a node to each node corresponding to a derived goal of the reduced goal. The proof tree for a conjunctive query is just the collection of proof trees for the individual goals in the conjunction.
An important measure provided by proof trees is the number of nodes in the tree. It indicates how many reduction steps are performed in a computation. This measure is used as a basis of comparison between different programs in Chapter 3. If it is correct, or incorrect? In order to answer such questions, we have to define what is the meaning of a logic program.
Once defined, we can examine if the program means what we have intended it to mean. From this definition it follows that the meaning of a logic program composed just of ground facts, such as Program 1. In other words, for simple programs, the program "means just what Chapter 1 it says. What is its meaning? It contains, in addition to the facts about fathers and mothers, mentioned explicitly in the program, all goals of the form parent X,Y for every pair X and Y such that f a t h e r X ,Y or mother X ,Y is in the program.
This example shows that the meaning of a program contains explicitly whatever the program states implicitly. Assuming that we define the intended meaning of a program also to be a set of ground goals, we can ask what is the relation between the actual and the intended meanings of a program.
We can check whether everything the program says is correct, or whether the program says everything we wanted it to say.
Informally, we say that a program is correct with respect to some intended meaning M if the meaning of P, M P , is a subset of M. That is, a correct program does not say things that were not intended. A program is complete with respect to M if M is a subset of M P. That is, a complete program says everything that is intended. Throughout the book, when meaningful predicate and constant names are used, the intended meaning of the program is assumed to be the one intuitively implied by the choice of names.
For example, the program for the son relationship containing only the first axiom that uses f a t h e r is incomplete with respect to the intuitively understood intended meaning of son, since it cannot deduce s o n i s a a c , s a r a h.
If we add to Program 1. The notions of correctness and completeness of a logic program are studied further in Chapter 5. Although the notion of truth is not defined fully here, we will say that a ground goal is true with respect to an intended meaning if it is a member of it, and false otherwise.
We will say it is simply true if it is a member of the intended meaning implied by the names of the predicate and constant symbols appearing in the program. The basic structure in logic programs is a term. A term is a constant, a variable, or a compound term. Constants denote particular individuals such as integers and atoms, while variables denote a single but unspecified individual.
The symbol for an atom can be any sequence of characters, which is quoted if there is possibility of confusion with other symbols such as variables or integers. Symbols for variables are distinguished by beginning with an uppercase letter. A compound term comprises a functor called the principal functor of the term and a sequence of one or more terms called arguments.
A functor is characterized by its name, which is an atom, and its arity or number of arguments. Constants are considered functors of arity 0. Syntactically, compound terms have the form f t l,tL,..
Functors with the same name but different arities are distinct. Terms are ground if they contain no variables; otherwise they are nonground. Goals are atoms or compound terms, and are generally nonground. More will be said on this restriction on substitutions in the background to Chapter 4. A logic program is a finite set of clauses. A clause or rule is a universally quantified logical sentence of the form where A and the B, are goals. Such a sentence is read declaratively: A query is a conjunction of the form A, , Variables in a query are understood to be existentially quantified.
A computation of a logic program P finds an instance of a given query logically deducible from P. Deduction of a goal from an identical fact is a special case. The meaning of a program P is inductively defined using logical deduction. The set of ground instances of facts in P are in the meaning. A ground goal G is in the meaning if there is a ground instance G -BJ,.
The meaning consists of the ground instances that are deducible from the program. An intended meaning M of a program is also a set of ground unit goals. It is complete with respect to M if M is a subset of M P. A ground goal is true with respect to an intended meaning if it is a member of it, and false otherwise. Logical deduction is defined syntactically here, and hence also the meaning of logic programs. In Chapter 5 , alternative ways of describing the meaning of logic programs are presented, and their equivalence with the current definition is discussed.
There are two basic styles of using logic programs: This chapter discusses database programming. A logic database contains a set of facts and rules.
We show how a set of facts can define relations, as in relational databases. We show how rules can define complex relational queries, as in relational algebra. A logic program composed of a set of facts and rules of a rather restricted format can express the functionalities associated with relational databases.
We adopt a convention from database theory and give for each relation a relation scheme that specifies the role that each position in the relation or argument in the goal is intended to represent.
Relation schemes for the four predicates here are, respectively, f a t h e r F a t h e r , Child , mother Mother , C h i l d , male Person , and female Person. The mnemonic names are intended to speak for themselves. Variables are given mnemonic names in rules, but usually X or Y when discussing queries.
Multiword names are handled differently for variables and predicates. Each new word in a variable starts with an uppercase letter, for example, NieceOrNephew, while words are delimited by Database Programming Chapter 2 underscores for predicate and function names, for example, scheduleconflict.
New relations are built from these basic relationships by defining suitable rules. Appropriate relation schemes for the relationships introduced in the previous chapter are son Son, P a r e n t , d a u g h t e r Daughter, P a r e n t , p a r e n t P a r e n t , C h i l d , and g r a n d p a r e n t Grandparent, Grandchild. From the logical viewpoint, it is unimportant which relationships are defined by facts and which by rules.
For example, if the available database consisted of p a r e n t , male and female facts, the rules defining son and g r a n d p a r e n t are still correct.
New rules must be written for the relationships no longer defined by facts, namely, f a t h e r and mother. Interesting rules can be obtained by making relationships explicit that are present in the database only implicitly.
For example, since we know the father and mother of a child, we know which couples produced offspring, or to use a Biblical term, procreated. This is not given explicitly in the database, but a simple rule can be written recovering the information. The relation scheme is procreated Man, Woman. This reads: In order to preclude such cases from the meaning of the program, abraham f isaac. Figure 2. It is convenient to write this predicate as an i n k operator. Thus Terml f Term2 is true if Term1 and Term2 are different.
For the present it is restricted to constant terms. It can be defined, in principle, by a table X f Y for every two different individuals X and Y in the domain of interest.
Program 2. The definition of u n c l e in Program 2. This may or may not be the intended meaning. In general, different cultures define these family relationshps differently. In any case, the logic makes clear exactly what the programmer means by these family relationshps.
Chapter 2 Database Programming Another relationship implicit in the family database is whether a woman is a mother. The new relation scheme is mother Woman , defined by the rule mother Woman - mother Woman,Child. T h s reads: The mother predicate takes a different number of arguments, i. In general, the same predicate name denotes a different relation when it has a different arity.
We change examples, lest the example of family relationships become incestuous, and consider describing simple logical circuits.
A circuit can be viewed from two perspectives. The first is the topological layout of the physical components usually described in the circuit diagram. The second is the interaction of functional units. Both views are easily accommodated in a logic program. The circuit diagram is represented by a collection of facts, while rules describe the functional components.
The facts are the connections of the particular resistors and transistors comprising the circuit. The relation scheme for resistors is resistor Endl,End2 and for transistors transistor Gate,Source,Drain.
Power Figure 2. Each interesting procedure is preceded by a relation scheme for the procedure, shown in italic font, and by English text defining the relation. We recommend this style of commenting, whch emphasizes the declarative reading of programs, for Prolog programs as well. Particular configurations of resistors and transistors fulfill roles captured via rules defining the functional components of the circuit.
The circuit describes an and-gate, which takes two input signals and produces as output the logical and of these signals. One way of building an and-gate, and how this circuit is composed, is to connect a nand-gate with an inverter.
Relation schemes for these three components are andgate Inputl,Input2,0utput , nand-gate Inputl,Input2,0utput , and inverter Input,Output. Chapter 2 To appreciate Program 2. T h s states that an inverter is built up from a transistor with the source connected to the ground, and a resistor with one end connected to the power source. The gate of the transistor is the input to the inverter, whde the free end of the resistor must be connected to the drain of the transistor, whlch forms the output of the inverter.
Sharing of variables is used to insist on the common connection. Consider the query and-gate In1 , I d ,Out? T h s solution confirms that the circuit described by the facts is an and-gate, and indicates the inputs and output.
Using a predicate married-couple Wife ,Husband ,define the relationships mother-in-law, brother-in-law, and son-in-law. Describe the layout of objects in Figure 2.
Define predicates right-of Object1 ,Object2 and below Object l,Object2 in terms of lef t-of and above, respectively. There is no indication of the structure of the circuit in the answer to the and-gate query, even though the structure has been implicitly used in finding the answer.
The rules tell us that the circuit represents an and-gate, but the structure of the and-gate is present only implicitly. We remedy this by adding an extra argument to each of the goals in the database. For uniformity, the extra argument becomes the first argument. The base facts simply acquire an identifier. Proceeding from left to right in the diagram of Figure 2.
Names of the functional components should reflect their structure. An inverter is composed of a transistor and a resistor.
To represent t h s , we need structured data. The technique is to use a compound term, inv T ,R , where T and R are the respective names of the inverter's component transistor and rcsistor. Arcs represent the application of a programming technique and are labelled by a parameterized representation of the technique applied. The name is the technique and the arguments are what needs to be filled in to complete the enhancement.
Enhancement structures can help guide a proof of correctness for programs developed via stepwise enhancement. This will be sketched in Section 4. If the only change is to a single technique, all the programmer need do is create a new enhancement embodying the changed technique.
The sequence of enhancements and compositions can which built the original program can be replayed to give the new final program. The modifications and replay could readily be moderated through a user interface operating directly on the enhancement structure. Facilitating program modification by replaying operations that have not changed is certainly viable.
A prototype system was demonstrated at a logic programming workshop in which replayed a series of programming enhancements. The system was based on a poorer version of techniques proposed by Lakhotia Via a mouse- driven interface, a user can create extensions by applying techniques to skeletons. The user is prompted to fill in values for arguments and supply extra goals with the interface stepping through the code to the appropriate places.
The prototype currently facilitates construction of programs concerned with recursive data structure traversal. The environment allows the application of four techniques to skeletons: calculate, build, accumulate-calculate and accumulate-build. Seven skeletons are pre-defined with the environment, and the user can add others. Composition of extensions created in the environment is supported, and limited error checking has been incorporated. Each technique is parameterized for each skeleton to know where to add values.
For example, the build technique adds an extra argument to each essential predicate in the skeleton. A new goal is given for each rule where the extra argument in the head is determined by the arguments in the body. The PT programming environment supports simple program maintenance. The simplicity of program construction in the environment carries over to small modifications. Proving Prolog programs correct 4. Still it is necessary to have a specification, that is a document which explains the behavior of a program sufficiently so that the program can be used without the code having to be read.
We believe that a specification should be the primary form of documentation and be given for each procedure in a program. A suggested form for a specification of a Prolog program is given in Figure 3.
It consists of a procedure declaration, effectively giving the name and arity of the predicate, a series of type declarations about the arguments, a relation scheme, and other important information such as modes of use of the predicate and multiplicities of solutions in each mode of use.
Most relevant here is the relation scheme. The relation scheme is a precise statement in English which explains the relation computed by the program. It should be stressed that relation schemes must be precise statements. We believe that proving properties of programs should proceed in the way of mathematics where proofs are given by precise statements in an informal language.
Our view of specifications is heavily influenced by Deville Tn: typen Relation scheme: Modes of use: Multiplicities of solution: Figure 3: Template for a specification 4. The proof heavily depends on the way the program was derived.
The derivation is described by the concept of an enhancement structure presented in Section 3. The enhancement structure can help guide a proof of correctness for programs developed via stepwise enhancement.
The proof suggests leveraging the structure of the program development to help the final program. Establish that the connected program is correct using a straightforward induction argument.
Prove that path is correct relative to connected using the correctness of the programming technique. Prove that count is correct relative to connected using the correctness of the programming technique. A sample proof that count is correct relative to connected is sketched in the appendix, where an appropriate specification is given. The proof depends on the Computation Extension Theorem proved in Kirschenbaum et al.
This leads to the notion of design for provability. The way the program is built is shaped by the intention to prove it correct. The first author has been gathering anecdotal evidence about the efficacy of design for provability. Together with Liming Cao, Leon Sterling modified a program for partitioning a number so that it could be proved correct.
The Art of Prolog, Second Edition
Thinking about having to prove the program correct greatly improved the program. We also were forced to clarify the main data structure that would be needed in the design. Proofs of correctness have been sketched for several other examples. The largest are an object-oriented database language, and a translator from Z to Prolog Sterling et al. In both these cases, thinking of the need to prove the program correct improved the code.
The paradigm of meta-programming has emerged as a mature entity within logic programming since the pioneering work of Bowen and Kowalski Prolog, as a logic programming language, supports the paradigm.
Manipulating programs is easy, and rapid prototyping of new meta-linguistic abstractions is a normal style of development. It is worth exploring definitions of meta-programming.
We believe that meta-programming is best viewed as a relatively new paradigm for programming complex systems that has emerged in both functional and logic programming. A paradigm for our purposes, as discussed in Floyd, , is an approach to writing programs. Examples of paradigms are structured programming, rule-based programming, and dynamic programming.
Each of them are effective for a class of programming problems. In our opinion, the essence of meta-programming is building a language which abstracts and interprets other languages.
The purpose of meta-programming is to facilitate manipulation of object programs, either by syntactically manipulating them or executing them. This leads to a different definition of meta-programming. Prolog is particularly appropriate for manipulating symbols. Where the symbols are programs, we have the literal sense of meta-programming. Applications which are oriented to symbol manipulation such as parsing and compiling are most suitable.
An excellent case for the use of Prolog for parsing and compiling has been made by Cohen and Hickey Prolog has also made some impact in software testing. Here the specification of an abstract data type is manipulated to generate a computationally feasible set of test cases Dauchy and Marre, Again the power to manipulate symbols at a high level is very important.
In previous research, we have shown the power of language abstraction for expert systems, both for tools and specific applications.
Meta-programming is good for compiling one language to another as well as providing a means of abstraction for defining a language and its interpretation. There are two examples from developments at Quintus. The first extends and formulates a language and paradigm on top of Prolog.
Schachte and Saab describe the Quintus objects package, which was possible to build precisely because of the meta-programming approach. We believe this is a model for software development. After developing the abstract SQL, there was an interface to all the major databases. Adding them was not a real problem except linking with specific database libraries. Conclusions Taking a pattern view of programming is helpful.
There is no doubt that skeletons and techniques can help in teaching the effective use of logic programming languages. Within the classroom, emphasizing patterns has been valuable for teaching effective Prolog programming. Students are able to follow more complicated Prolog programs and the quality of code in student projects has increased. Graduate students find this approach useful for explaining code to others, and in the cases of meta-interpreters cited earlier complicated programs were more easily developed.
Finally, we reiterate our belief that abstraction is key to future development of complex software systems. It makes it easy to identify programming patterns so programming solutions can be re-used.
Also more literally, domain-specific abstractions can be rapidly prototyped and developed using a meta-programming approach. It will be a cornerstone in any applications we are involved with. The first author acknowledges support of his current location, the Department of Computer Science of the University of Melbourne. The second author acknowledges colleagues at Quintus. References Abelson, H. Sterling and Ehud Y. This new edition of The Art of Prolog contains a number of important changes.
Most background sections at the end of each chapter have been updated to take account of important recent research results, the references have been greatly expanded, and more advanced exercises have been added which have been used successfully in teaching the course. Part II, The Prolog Language, has been modified to be compatible with the new Prolog standard, and the chapter on program development has been significantly altered: A new chapter on interpreters describes a rule language and interpreter for expert systems, which better illustrates how Prolog should be used to construct expert systems.
The chapter on program transformation is completely new and the chapter on logic grammars adds new material for recognizing simple languages, showing how grammars apply to more computer science examples. Leon S. Sterling and Kuldar Taveter.Thls says that X is a member of Ys if Ys can be split into two lists where X is the head of the second list.
An abundance of books on Prolog have appeared. Beware though: Many of the concepts introduced haire meaningful analogues in terms of databases. The second author taught courses at the Weizmann Institute and Hebrew University of Jerusalem, and in industry. The way the program is built is shaped by the intention to prove it correct.
Relation schemes for these three components are andgate Inputl,Input2,0utput , nand-gate Inputl,Input2,0utput , and inverter Input,Output. It is interesting to note that the failure of this program, from which ensued the incompleteness and undecidability results of Godel and Turing, marks the beginning of the modern age of computers. Conceived appropriately, using logic programs is a formal method.