USERs GUIDE TO THE DEMO SYSTEM

E-mail: henning@dat.ruc.dk
Copyright © October 1994, July 1996 by Henning Christiansen. All rights reserved.

Contents

1.   Introduction
   1. The status of the system and documentation
   2. Background reading
   3. Overview of this guide
2.   Starting the Demo system
3.   An extended syntax for names of object language phrases
   1. Using the extended syntax with Prolog
   2. Meta-variables
   3. Naming operators of programs, clauses, formulas, and terms
   4. The extended syntax - in program files
   5. Cautions
   6. Summary of the object language syntax
4.   An annotated example
   1. The program file
   2. Using demo
5.   Declaring your own object program modules
6.   Constraints provided by the Demo system
   1. Available type and instance constraints
   2. Member constraints
   3. Dynamic properties of the constraints
7.   Getting rid of delayed constraints in the answers from demo
8.   On control and potential loops in demo
   1. The basic control pattern in demo
   2. A good practical reason for viewing programs as sets

1.   Introduction

Demo is a proof predicate specified as follows,

     demo( P' , Q')    iff   P' and Q' are names of program and query,
                             P and Q, such that there exists subst. sigma:
                            
                               P |-  Q sigma

P and Q refer to an object language, which we call O, of definite clause programs; by a name of an O-phrase (O-program, O-formula, etc.) we understand a unique ground term which identifies it.

Our implementation is logically complete which implies a power of demo not only to execute programs but also to generate programs which make given goals provable. I.e., a variable in the first argument to demo is a meta-variable which stands for (part of) a program text. An answer from the system, then, gives a value for this variable which represents the ``missing'' program text.

In order to generate useful programs in this way one needs often define a meta-program which determines this class of useful programs. This Demo package provides tools for writing such meta-programs, so you can write your own predicate, say, useful(_) and use it in conjunction with demo, e.g.:

    useful( P ), demo( P, <a series of object language facts> )

The use of co-routines makes it possible to achieve a reasonable execution speed by interleaving the actions of the two predicates.

The applications which you will find in the Examples directory of this package demonstrates the approach for task such as

• abduction also with integrity constraints and under linear-logic-like conditions,
• induction, learning of rules from positive and negative examples,
• diagnosis.

We provide an extended notation with explicit naming operators which makes programming about the ground representation much more attractive. If you write, say,

    \\ p(a,X)

this stands for the ground term which at the meta-level represents the O-atom p(a,X). As a programmer you do not need to be aware of the fact that \\ p(a,X) really means the following huge structure:

    atom(predicate(p,2),[constant(a),variable('X')]).

We recommend you to experiment with the Examples files before you build your own applications. To begin with you may have a look at the annotated example in section 4 below.

The authors own experience is that this---despite the extended notation and other tailored facilities---is a new style of meta-programming that one has to learn.

1.1.   The status of the system and documentation

It should also be made clear that this Users Guide is not a reference manual and the advice, if you miss some information, might be (alas) to have a look at the source files (or send a quick request to the author by e-mail).

The documentation needed for using this system consists of

• the README file (in the topmost directory!) which explains how to achieve and install the system.
• this document, USERSGUIDE, which gives an informal introduction to the systems use and its facilities
• the complete description of the extended syntax in the document EXTENDED_SYNTAX_GUIDE (briefly introduced in section 3 below).

If you want to be informed about major revisions; or if you have problems, questions, complaints, suggestions or perhaps applications of the Demo system which would fit into the Examples directory---do not hesitate to write to:

1.2.   Background reading

The ideas behind our Demo system and references to related work are described in a number of papers:

• ``Automated reasoning with a constraint-based meta-interpreter.''

  The paper gives a comprehensive account on the approach, and is available in postscript [and html to appear].

• ``On proof predicates in logic programming.''

  This short introductory paper will become available in html and postscript.

• ``Efficient and complete demo predicates for definite clause languages.''

  This technical report describes an earlier version of the constraint solver. It is available in dvi and postscript.

For a general introduction to meta-programming in logic we recommend two survey papers:

• P.M. Hill & J.G. Gallagher: ``Meta-Programming in Logic Programming,''
  in: Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. V, Oxford University Press.

  Currently also available from University of Leeds, School of Computer Studies, as
  Research Report number 94.22.

• J. Barklund: ``Metaprogramming in Logic,''
  in: Encyclopedia of Computer Science and Technology, Vol. 33 (eds. A. Kent and J.G. Williams), pp205--227. Marcel Dekker, New York, 1995.

  Also available from Uppsala University, Computing Science Department, as
  UPMAIL Technical Report No. 80.

and the book

• K.R. Apt & F. Turini (eds.): Meta-Logics and Logic Programming, MIT Press 1995.

As the Demo system runs under SICStus Prolog you may occasionally need:

• SICStus Prolog User's Manual, Release 3 #5.
  SICS, Swedish Institute of Computer Science, Oct.1996.

1.3.   Overview of this guide

The basic use of the system is explained by means of examples in sections 2 to 4,

Section 5 explains how modules of object language clauses can be declared and used.

Section 6 explains the constraint system which is used by the demo program and which also can be used in user predicates.

Section 7 presents two useful utilities.

Section 8 explains what a programmer who wants to make more than very trivial applications of demo needs to know about its internal control.

In the following, it is assumed that the reader is acquainted with the use of a traditional Prolog system such as SICStus Prolog.

2.   Starting the Demo system

We open the DemoPackage directory and start SICStus Prolog, probably as follows:

     $ cd DemoPackage
     $ prolog

Inside Prolog, we start the Demo system as follows

     | ?- [demoSYSTEMcompiled].

You will see a large number of mostly rubbish messages and after a few seconds, the system is compiled and ready for use.

If your Prolog installation does not support compilation or if, for some other reason, you want an interpreted version, use instead

     | ?- [demoSYSTEM].

To leave the system and Prolog, write as usual

     | ?- halt.

3.   An extended syntax for names of object language phrases

It is implemented by pre- and post-processors which

1. reads user queries and program files, and translates the extended syntax into Prolog terms before invoking Prolog,
2. translates answers back into the extended syntax whenever possible before printing out.

The extended syntax is available in an alternative dialogue mode which resembles Prologs read-execute-print-result fashion­-­except that you can use a system of naming operators with a special meaning.

A complete description of this mode is found in the separate document EXTENDED_SYNTAX_GUIDE.

Credits to Erwan De Bleeckere and Geraud Lacaze, Erasmus students visiting from Rennes summer 1994, who implemented this part of the Demo system and wrote the separate guide.

3.1.   Using the extended syntax with Prolog

You activate this mode by typing backslash-space-period-return; this gives you a new prompt and you can submit your query. We try the following (the prompt `| ?-' is written by Prolog, `\ ?-' by the Demo system):

     | ?- \ .
     \ ?- Z = \\ p(a,X).

     Z = \\p(a,X) ?

     yes

Nothing unusual? But let us insert a call of writeq in the query.

     | ?- \ .
     \ ?- Z = \\ p(a,X), nl, writeq(Z), nl.

     atom(predicate(p,2),[constant(a),variable('X')])

     Z = \\p(a,X) ?

     yes

Thus \\ p(a,X) is actually read as the ground term which you see gets printed out by writeq. The \\ is a kind of quotation mechanism; so although the X in \\ p(a, X) looks like a Prolog variable, it isn't.

3.2.   Meta-variables

     | ?- \ .
     \ ?- Z = \\ p(a,?X),  nl, writeq(Z), nl.

     atom(predicate(p,2),[constant(a),_440])

     Z = \\p(a,?X) ?

     yes

3.3.   Naming operators of programs, clauses, formulas, and terms

Here we show one example of each; we use normal list notation for programs:

     \ [ (p(X):- q(X)), p(a), q(b) ].

     \ ( p(X):- q(X) )

     \\ p(a, X)

     \\\ f(a,X)

There are also forms which make it possible to write O-atoms with unspecified predicate symbol, arity or argument list, ditto for structures---see the full catalogue in the EXTENDED_SYNTAX_GUIDE.

Below we will show also an operator `&' for composing programs and how references can be made to user-defined object program modules.

Notice: An object program is a set of clauses and the clauses mentioned in the name of a program are expected to be different. The demo predicate and the module mechanism (below) will check that there are no duplicates and provide an error message when needed. In general, however, the system does not prevent the user from writing---say, \[p, p]---thus creating a meta-level term which is not the name of a program.

3.4.   The extended syntax - in program files

When you use the Prolog predicates consult(...) (usually abbreviated as [ ... ]) or compile(...) inside the extended syntax mode, the file will automatically be translated into normal Prolog syntax before being consulted or compiled by Prolog.

Let us consult the sample file `wet_grass' in the `Examples' folder.

     | ?- \ .
     \ ?-  ['Examples/wet_grass'].
     The translation of your file called Examples/wet_grass
     will be available in the file called Examples/wet_grass_trans
     {consulting /..../DemoPackage/ Examples/wet_grass_trans...}
     {/..../DemoPackage/Examples/wet_grass_trans consulted, 20 msec 1104 bytes}

     Do you want Examples/wet_grass_trans to be deleted ?  (y/n)

     yes

The text explains that a translated file is created, and we are asked whether we want it to be deleted. Here we pressed the RET-key meaning yes. Normally we have no interest in the translated file but in case of unexpected behaviour it may be necessary to have a look at it.

3.5.   Cautions

• The extended syntax has been implemented partly by operator declarations in Prolog and you have to exercise the same care as in Prolog: now and then an extra space or an extra parenthesis is needed in order to get things right.
• You must type backslash-space-period-return for every query or directive you want to give in the extended syntax.
• If you leave out by mistake the backslash-space-period-return, Prolog will unfortunately understand your query or program file but the special meaning of the operators has gone! However, the demo predicate will issue an error message if its arguments are not of the right form.
• There is a minor, but annoying, error in the routines for printing out answers; so that a constant `X' sometimes gets printed without the quotes. Can be a bit confusing.

3.6.   Summary of the object language syntax

    <program>     ::=  [<clause> , ... <clause> ]
                   |   <module-name>
                   |   <program> & <program>
                   |   []

Restriction: the same clause must not occur twice, also in programs composed by `&' and modules.

    <module-name> ::= ... a Prolog constant which is not a number
    
    <clause>      ::=  <atom> :- <formula>
    
    <atom>        ::=  <predicate>( <term> , ... , <term> )
                   |   <predicate>

    <predicate>   ::= ... a Prolog constant different from
                          numbers, '=', and 'dif'

    <formula>     ::=  true
                   |   <atom>
                   |   <constraint>
                   |   <formula> , <formula>

    <constraint>  ::=  <term> = <term>
                   |   dif( <term> , <term> )

    <term>        ::=  <function>( <term> , ... , <term> )
                   |   <constant>
                   |   <number>

    <constant>    ::= ... a Prolog constant which is not a number

    <function>    ::= ... a Prolog constant which is not a number

    <number>      ::= ... a Prolog integer

Inside a program, a clause of the form `<atom> :- true' can be abbreviated to `<atom>'; but in all other contexts, it has to be written in the complete form.

Meta-variables preceeded by `?' can replace any sub-phrase, and its type will be deduced from the context.

Internally, predicates and functions carries an explicit indication of arity, which is deduced from the expression in which it occurs. If you wish to refer explicitly to predicate (function) symbol---with or without arity---and to the argument list, it is possible using the following syntax for atoms or functions:

    <name> / <arity> - <argument-list>

where

    <name>       ::= ... a Prolog constant which is not a number
    
    <arity>      ::= ... an integer >= 1
    
    <argument-list> ::=  [ <term> , ...., <term> ]

This is especially useful when used together with meta-variables, e.g.

    ?S / ?N - ?AL
    
    ?F - ?AL
    
    ?P - [a,?X]

The EXTENDED_SYNTAX_GUIDE describes a few other, however rarely used, variations of notation.

4.   An annotated example

4.1.   The program file

As explained above the program file may apply the extended syntax and should thus be consulted in the `\ .' mode:

     | ?- \ .
     \ ?-  ['Examples/wet_grass'].
     ....

The file defines, among other things, an object program module defined as follows:

     :- object_module( garden,

          \[ (grass_is_wet:- rained_last_night),
             (grass_is_wet:- sprinkler_was_on)
           ]).

The general syntax of a module declaration is the following:

     :- object_module( <constant> , <program-name> )

The <constant> is a Prolog constant; <program-name> is any term which can be accepted as the name of an O-program---and, of course, it is very convenient to use the \ naming operator. (The object_module(_,_) directive is described in more detail in section 5 below.)

The effect of the module declaration above is that you can use the constant `garden' anywhere an O-program is expected---instead of writing all the clauses each time! I.e, the expression

    \garden

is now a program name.

4.2.   Using demo

     | ?- \ .
     \ ?- demo( \(garden & [?WHY]), \\grass_is_wet ).

     WHY = \ (rained_last_night:-true) ?

The answer is a value for WHY which is the name of a clause which makes the conclusion in the demo-query provable. The actual answer we got seems to be a perfect abducible explanation.

Now, let's type `;' for alternative answers---and alas---the interpreter runs into a loop! And there is a good reason for this which we will discuss in section 8.

However, the main intuitive reason to these troubles is that our query to demo was not stated carefully enough. The query asked for any kind of clause which makes `grass_is_wet' hold. So we were actually very lucky that the internal control inside demo actually produced a sensible first answer!

Usually abduction is understood as the task of finding facts of a certain »primitive« kind.

To this end, our example file `Examples/wet_grass' defines a meta-predicate, abducible(_) as follows:

     :- block abducible(-).

     abducible( \ (rained_last_night:- true) ).    
     abducible( \ (sprinkler_was_on:- true) ).
     abducible( \ (full_moon:- true) ).
     abducible( \ (sun_shines:- true) ).
     abducible( \ (dog_on_lawn:- true) ).

The block declaration causes any call abducible(X) to delay until some other event, e.g., an internal action of demo, assigns a value to X. ( Block declarations are described in the SICStus Prolog User's Manual).

Consider, now, the following query:

     | ?- \ .
     \ ?- abducible(WHY), demo( \(garden & [?WHY]), \\grass_is_wet ).

     WHY = \ (rained_last_night:-true) ? ;

     WHY = \ (sprinkler_was_on:-true) ? ;

     no

This looks more like abduction. The call abducible(WHY) delays a a condition on WHY, which wakes up when demo actually begins to involve the »clause« WHY in a proof. ---In this tiny example, the block declaration does not actually make much difference but when things become more complicated it can be essential to have such additional conditions delay as long as possible.--- In section 6.2 and in section 8 we discuss more aspects of the use of the blocking mechanism.

This ends the first little annotated example intended as an introduction to the basic functionality of the Demo system. You may also want to have a look at the less trivial examples provided in the `Examples' directory.

5.   Declaring your own object program modules

An object program module is defined by a directive as follows:

     :- object_module( <identifier>, <program-name> ).

The <identifier> is a Prolog constant, <program-name> is a term which names an object program. Here the extended syntax is useful.

We give an example:

     :- object_module( pq_program,

          \[ (p(X):- q(X)),
             p(a),
             p(b)
           ]).

The execution of this directive makes pq_program available as a program module which can be used as (part of) a program name, e.g.:

     | ?- \ .
     \ ?- demo( \pq_program, .... ).

In the translation from extended syntax to Prolog structures, a name like \pq_program is not replaced by a copy of the original source text. The clauses have been preprocessed for efficiency and are stored as an asserted fact,

    object_module_nonground(pq_program,
                            <preprocessed program representation>).

Normally, each time demo enters an object language clause---given in the ground representation, the clause will be processed by an instance constraint, effectively translating it into a nonground form with Prolog variables consistently replacing ground names of object variables. The object_module(_,_) directive makes this translation once and for all---and when the module is used, the Prolog system will automatically put in fresh variables each time the (preprocessed) clause is invoked.

The program file for the demo program `Source_files/demo' illustrates how an interpreter can mix such pre-processed clauses with clauses given in the ground representation.

However, we keep also the ground representation given by the user--- because this is relevant for some predicates and constraints, e.g., the program_ constraint, that among other takes care that no duplication of object language clauses occurs in programs composed by `&' and object program modules.

The ground representation is stored as an asserted fact,

   object_module_source( name, <program-name> ).

You can also use the `&' syntax in the definition of a module, e.g.:

     :- object_module( extended_pq_program,

               \ ( pq_program & [(q(X):- r(X)), r(c)] ).

In this way you can build a hierarchy of object language programs which are extensions of each others.

It is checked that a module---in this way included in another---actually exists; but with a suitable order of redefinitions it is possible to create circular dependencies---which are not detected by the system (and you will probably get loops out of it).

- Uninstantiated meta-variables are not allowed in object program modules!

- The usual abbreviated form for facts, i.e., leaving out the trivial body, works only in the extended syntax as part of a program (as above). When denoting a fact out of context, you have to to write it in full, e.g., \ (p(a):- true).

- It is not allowed to mention the same clause twice in a module, directly or indirectly by means of `&'.

6.   Constraints provided by the demo system

In this section we explain which constraints are available and what one may need to know about their execution behaviour.

As a general introduction to constraint techniques in logic programming, we advocate the following:

• Jaffar, J.; Maher, M.J.: ``Constraint logic programming: A survey.''
  Journal of logic programming, Vol 19/20, pp503-581, May 1994.

6.1.   Available type and instance constraints

     program_(P)
     empty_program_(P)
     program_cons_(P)
     clause_(C)
     formula_(F)
     atom_(A)
     constraint_(C)
     conjunction_(C)
     true_(T)
     term_(T)
     constant_(C)
     structure_(S)
     predicate_(P)
     constraint_symbol_(C)
     function_(P)

Each constraint is satisfied whenever its argument is the name of an object phrase of the indicated type. Thus, for example, the following constraints are all satisfied:

    program_( \[] )      

    empty_program_( \[] )
    
    atom_( \\ p(a) )
    
    constraint( \\ ( X = b) )

    predicate_(predicate(p,1))

Notice that each constraint name ends with an underline character in order to have a consistent way to distinguish them from a few Prolog built-ins.

Notice that the program_(P) constraints includes the conditions that no duplicate clauses (properly, clause names) are allowed in P. The program_ constraint distributes correctly over object program modules and the `&' operator.

The following constraints describe primitive objects used in the names of O-phrases:

meta_constant_(C)

C is a Prolog constant different from `true' and `emptyprogram'

meta_identifier_(I)

I is a Prolog constant different from `integer' and `true' and `emptyprogram'

meta_integer_(N)

N is a Prolog `integer'

The following are the instance constraints:

     formula_instance_(Object1, Object2)
     term_instance_(Object1, Object2)
     clause_instance_(Object1, Object2)
     atom_instance_(Object1, Object2)
     constraint_instance_(Object1, Object2)

An instance constraint is satisfied whenever Object1 and Object2 are names of object language phrases, O1 and O2, of relevant category with O2 being an instance of O1.

Instance constraints are essential for defining a meta-interpreter such as demo, but users who stick to the delivered demo predicate will probably never need to use instance constraints.

These constraints are defined in the file `Sourcefiles/constraint' together with other constraints used for internal purposes.

An answer printed out by the system consists of a substitution for variables in the query together with the constraints which have not been evaluated. The constraints printed out will differ from those mentioned above, rather a collection of internal counterparts and small auxiliary constraints will be seen. (In section 7 we explain a means to get rid of those.)

Caution:
The notion of object language constraints did not appear in the first version of the system and it is not supported properly by the internal representation. Constraints (and constraint symbols) are represented as special kinds of atoms (and predicates)---however, the meta-level constraints atom_ and constraint_ (as well as predicate_ and constraint_symbol_) distinguish correctly between the categories, and the user will probably never sense this.

6.2.   Member constraints

The following can be understood in the usual, fully declarative way working on the ground representation:

    member_(C, P)

P is a term of type program of which C is a member. It distributes correctly over object program modules and the `&' operator.

The following is used for optimization purposes:

    member_(C, P, T)

T should be given as a variable and the call will instantiate it to one of:

groundRepresentation

in which case C is as for member_/2

nonGroundRepresentation

in which case C is a member of P but preprocessed by instance constraints.

The latter is the case when clauses are fetched from a user-defined object program module.

member_/3 distributes correctly over object program module and the `&' operator.

6.3.   Dynamic properties of the constraints

    program_(P)

Ideally, the user should not need to be aware of when or how constraints actually execute. However, the users meta-predicates may need to delay and these predicates will thus function as a sort of constraints which interact with those set up by the demo predicate.

Whenever a constraint `decides' to assign a value to a variable X, the event also triggers user-defined predicates. Or, the other way around; a simple unification made by user code may trigger a large collection of accumulated system constraints.

A precise and formal model for execution of constraints is given in the report ``Efficient and complete demo predicates ...'' (postscript). Here we present the basic rules in an informal way which we believe is sufficient for those who wants to develop their own meta-predicates:

1. Type constraints (e.g. program_(P)) delay as long as possible.
2. Whenever a constraint (type or instance) is set up on a variable it will be checked for satisfiability against possible other constraints which concern that variable.
3. An instance constraint <type>_instance_(X,Y) wakes up and reduces into simpler constraints---and perhaps assigns new structure to X or Y when
   1. a type constraint on X or Y appears which specializes <type>; and which implies restrictions on the other of X or Y, or
   2. X or Y gets a value which implies restrictions on the other of X or Y.

As an exception to (c) clause_instance_(X,Y) always reduces into constraints on the head and body components of X and Y.

Rule (a) indicates that even a constraint such as atom_(C) does not assign a value to C, despite the fact that any value for C which satisfies the constraint must be a term of the form atom(predicate(P,N), Ts). We found that this principle works better together with delayed user predicates.

We can illustrate rule (b) by the following combinations of constraints:

term_(X), constant_(X) succeeds and is equivalent to just constant_(X).

term_(X), formula_instance_(X,Y) fails.

term_(Y), formula_instance_(X,Y) fails.

As an advice we can give a rule of thumb saying that user-defined meta-predicates to be used in conjunction with demo should be as `lazy' as possible, i.e., have as many (sensible) block declarations as possible. The demo predicate will accumulate roughly one type constraint for each uninstantiated meta-variable---and when or if such a variable achieves a value the constraint evaluates as a test. Type constraints do not assign values to variables; hence, they do not trigger delayed user predicates. As a programmer or demo user you seldom have to worry about type constraints.

The interaction between user predicates and instance constraints is more interesting. Whenever a meta-variable, say X, which stands for a clause, is taken by demo for a clause to be used in a proof-step, X is assigned a rudimentary structure for a clause indicating head and body. This event can trigger a user predicate which provides detailed information about the kind of clause allowed---and this in turn affects the execution of instance constraints which reflect the part of an object proof step concerned with unify-head-of-clause-with-selected-atom. Now, when the instance constraint evaluates it may assign a yet more detailed structure to X which again triggers the fine-grained parts of the user predicates.

7.   Getting rid of delayed constraints in the answers from demo

To provide more compact answers we have provided a predicate

    close_constraints(AnyPhrase)

which localizes the uninstantiated meta-variables in the argument AnyPhrase and tries to assign values to them which will satisfy the accumulated constraints. The sample file `Examples/still_life' shows it at work.

The close_constraints predicate is a purely heuristic construction which succeeds only once giving a suggestion for a prototypical, concrete answer contained in the constraints.It includes strategies for reusing existing symbols and inventing new ones when necessary.

The following variants are available which take additional arguments where one can supply lists of preferred symbols to be used.

    close_constraints(AnyPhrase, Preds)
    close_constraints(AnyPhrase, Preds, Consts)
    close_constraints(AnyPhrase, Preds, Consts, Funs)

The format is illustrated by this example:

    close_constraints(X, [p/1, q/2], [a,b,c], [f/1, g/2])

Sometimes the set of accumulated constraints and delayed user predicates are unsatisfiable. In this case the predicate issues a warning and fails---hoping for demo and the user predicates to come up with a better set of constraints.

The following example shows a problem that can arise with close_constraints. Consider the following query:

    demo( \ .... ?X ...., ....),
    close_constraints(X),
    condition(X).

It may be the case that this query fails because close_constraints instantiates the solution provided by demo in a way different from what you would expect. Thus query may fail even if demo has produced a set of constraints that contain a grounded solution satsified by condition(X). The correct action is likely to reprogram condition(X) as a co-routine that interleaves with the actions of demo.

The close_constraints predicate is especially useful in the early experimental phases in the development of a new application of demo. The first version of a new meta-predicate to support demo is typically not precise enough---it can be quite a challenge to formalize what it means for an object program to be a good object program in a given context. So in your first experimental run,
good(P), demo( P, ...)
the concrete information you get about P is probably very little and the amount of delayed calls quite incomprehensible. Try instead
good(P), demo( P, ...), close_constraints(P)
and you will get a single prototypical representative for the (typically infinite) set of solutions contained in the constraint set. This will quite often indicate the points where the good(_) predicate needs revision.

The more you revise the good(_) predicate the less meta-variables are left for close_constraints and in the final version, close_constraintscan be dropped or is used only for trivial things such as closing open program tails.

We have found that the warning issued by close_constraints on failure is an effective means for recognition of programming errors in user predicates (but, alas, not for localizing the erroneous point!).

8.   On control and potential loops in demo

8.1.   The basic control pattern in demo

The following basic version of the demo predicate illustrates this control pattern.

    demo(P, Q):-
       program_(P),
       formula_instance_(Q, Q1),
       demo1(P, Q1).

    demo1(_, \\true).

    demo1(P, A):-
       member_( C, P),
       clause_instance_( C, \ (?A :- ?B1)),
       demo1(P, B1).

    demo1(P, \\ (?T1 = ?T2)):- T1 = T2.

    demo1(P, \\ dif(?T1, ?T2)):- dif(T1, T2).

    demo1(P, \\ (? A, ?B)):-
       demo1(P, A),
       demo1(P, B).

We will illustrate the potential problems with the following query to demo for object programs in which the object query `p' is true.

    | ?- \ .
    \ ?- demo(X, \\p).

The first answer is as follows (note that the extended syntax is used when the answer is printed out):

    X = \[(p:-true)|?_519]
    constraints:blocking_syntax(program,_374,_519,_375)

This says that X is a program having a fact saying ``p holds'' and some internal (and, alas, undocumented) constraint expressing that the tail of X must be a program.

Asking for a second solution, we run into a loop which is very easy to explain. Asked for an alternative answer, demo will try to redo its last choice which was to expand the tail of the novel clause to `true'. Alternatively it tries to expand it to an atom, and this atom must unify with the head of a clause in the program; as expected it tries the first clause whose head is `p'---and the object clause `p:- p' is created.

However, the observed behaviour only reflects the quality of the query. It is difficult to imagine an application where one is interested in just a program which makes `p' provable---there will be many weird ones, also which include the clause `p:- p'. In most cases there will besome inherent criteria, formalized, say, as a meta-predicate good(_), which will exclude this. We will refer to the abduction example in file `Examples/wet_grass' which we discussed in section 4 above.

The actual implementation of demo is slightly more complicated due to two optimizations, but the overall behaviour is the same.

• It can also handle clauses defined in object program modules which (cf. section 5) are stored in a preprocessed format.
• A pre-unification is added in the sense the call to member_(...) will carry information about the predicate of the selected atom; in this way fewer clauses needs to be processed by the more expensive instance constraint.

8.2.   A good practical reason for viewing programs as sets

This means that no duplicates are allowed at the representation level. In practice, this makes the demo predicate less prone to loops. Whenever demo needs to expand (using member_) a variable in the position of a program tail into a structure with one new clause and yet a new tail, it will not try to expand this new tail again on backtracking. Consider an example query,

    conditions(P), demo( P, \\p)

and assume that demo expands P to \ [?C1 | ?P1] and for some reason (e.g., due to conditions(P) ) this fails; i.e., there is no such clause which can make `p' provable. Without the mechanism mentioned, demo might now try to expand P1 into \ [?C2 | ?P2], which is likely also to fail---and so on.

With demo as we have implemented it, the whole demo call fails after the first failed expansion.

This principle, expand-tail-only-once-on-failure, extends to programs composed by the `&' operator. We illustrate this by the following query.

    yellow(Py), green(Pg), brown(Pb),
    demo( \ (?Py & ?Pg & ?Pb), \\p).

The predicates yellow(_), green(_), and brown(_) define different kinds of clauses which are relevant with respect to the given problem domain. Now, if the call to demo---or perhaps some deeply nested, recursive call fails on expanding the tail (of a tail of ...) of Py, i.e., there is no yellow clause which can do the job, then a green one is tried, and if this also fails a brown one is tried.

As the example indicates this makes it easier to structure ones meta-predicates in a more orthogonal way.