Enter your search terms Submit search form
	Web pdp-10.trailing-edge.com

-*-Text-*-

This file describes Forbus' version of CONLAN.



File: Conlan	Node: Top	Up: (DIR)	Next: Overview

	CONLAN is a constraint language.  It was originally developed
as a pedagogic tool to illustrate the technique of propagation by
constraints.  Steele and Sussman's AI Memo describes the basics of the
language.  While some of the syntax is the same, the version described
here is a serious working tool that has been used in several AI
programs.  Several basic features have been added and "hooks" to allow
easy interconnections to other programs are provided.  The information
presented here is a synopsis of "The CONLAN Primer", BBN Technical
Report No. 4491.
	Technology marches on, but this version of CONLAN will not.
However, it is still useful as an illustration of constraint language
technology and for small-scale experiments.  Bugs and comments to
KDF@MIT-OZ.

* Menu:

* Overview::	Introduction to CONLAN
* Specifying::	How to specify constraints
* Building::	How to construct networks of constraints
* Examples::	Traces of the interpreter in operation
* Glossary::	Functions and flags for running it



File: CONLAN	Node:  Overview		Up: Top	Previous: top

	This is a brief and abstract description of CONLAN.

* Menu:

* Objects and Parts::	What constraints are
* Rules::		How computations are actually performed
* Composition::		How constraints are linked together


File: CONLAN,Previous: Overview,Node: Objects and Parts,Up: Overview,Next: Rules
Objects and Parts
	The basic object in CONLAN is a constraint.  A constraint is a
structured description with parameters.  Constraints are created by
instantiating prototypes, and can be joined together into networks to
describe complex systems or situations.
	Constraints are made up of two kinds of things: CELLS and
PARTS.  Cells hold the values of the parameters of the description.
For example, a constraint describing a ball might include cells to
hold the X and Y coordinates of its position at some instant, a valve
constraint might include a cell whose value indicates whether that
valve is open or closed, and an inequality constraint would include
cells naming the quantities being related.
	Parts of a constraint are themselves simpler constraints.  For
example, the ball constraint mentioned above might contain a vector
constraint to represent its velocity.  An inequality constraint would
include a "Taxonomy" constraint that would insist that exactly one of
the possible relations Greater-Than, Less-Than, or Equal-To holds
between the quantities being compared.  For a system of any
complexity, there are typically several levels of such embedding.



File: CONLAN,Node:Rules,Up: Overview,Previous: Objects and Parts,Next: Composition

	Relationships between the parameters in a constraint are
enforced by a set of rules.  Each rule has some set of cells that must
be known before it can be run (called the USES set), and a cell
that it will set if it runs sucessfully, called the SET cell.  The way
to think of these rules is "If I know the USES values, then I can compute
the SET value".  Rules can also return a special value that indicates an
inability to come up with a value for a particular set of input
values, and to signal a complaint when an inconsistency is discovered.
	Computation within CONLAN is done by forward deduction in the
following way.  When a cell is given a value, each rule that uses it
(the USERS) is examined to see if all cells in its uses set are
known.  If they are, the rule is placed on a queue and eventually run.
A rule may return a value, indicate that it has failed to get a
result, or signal a contradiction.  If a value is returned, it is
placed in the set cell.  If a contradiction occurs, a user procedure
is invoked to analyze the difficulty.  When a cell is set, a note is
made of the rule that set it (called the INFORMANT) so that the
reasons for each value may be determined.  Setting some new cell may
in turn cause other rules to be queued, and the process continues
until no more rules remain on the queue.



File: CONLAN,Node: Composition,Previous: Rules,Up: Overview
	To build a description of a complex system we want to
build descriptions of its parts first and then specify how those
parts are connected together.  CONLAN allows this operation to
be performed both on instances of constraints and in specifying
new types of constraints.
	The cells and parts in a constraint are connected by
SHARING STRUCTURE.  For example, in a real physical system, two
pipes might be joined by having an end of one pipe welded to the end
end of the other pipe, thus sharing a port between the two.  When
defining a constraint prototype a similar technique is used.  To
connect constraints into a network that describes a complex situation,
a mechanism that gives the effect of shared parts without actually
modifying the structures is used.  This allows the constraints in
a network to be easily disconnected when required.
	A convienent notation for constraint networks is to draw
constraints as objects and cells as terminals, as in logic diagrams.
Shared parts can be denoted by "wiring" two parts together.  These
conventions is illustrated in Steele & Sussman's paper.
	A special class of rules and cells is provided to facilitate
the construction of complex constraint networks.  An INDIRECT cell is
one that holds another constraint, as opposed to a value.  References
to parts that include this kind of cell can be made to act as if its
value were an actual part of the original constraint.  WIRING rules
are run when all of the indirect cells they depend on are filled, and
specify which parts are to be connected to each other and to the
constraint of which the rules are a part.  Making these connections
can result in new values being deduced, since some cells may now take
on values.  The dependence of values on these connections is stored so
that if the connection is broken the network will remain in a
consistent state.



File: CONLAN	Node: Specifying	Up:Top

	This section describes the syntax of constraint prototypes
and how to write them.

* Menu:

* Reference::		How to refer to constraint and their parts
* Prototypes::		What constraint prototypes look like
* Formulae::		How to specify rules
* Wiring::		How constraints can "connect themselves up"
* If-removed::		For interfacing with external representations
* Shared Structure::	A hack for storage economy



File: CONLAN,Node: Reference,Up: Specifying,Previous: Specifying,Next: Prototypes

	A uniform convention is used for referring to parts of a
structure both within a prototype description and for parts of a
constraint network.  For example, a list of the form:

(>> isolation bypass main-steam-stop)

should be read as "The isolation of the bypass of the
main-steam-stop".  The depth of such a reference can be arbitrary.  If
the values of indirect cells are being accessed, ">>i" should be used
instead.  For example, we would say

(>>i speed after previous Fly32)

to refer to "the speed of the ball after the thing that happened before
the act Fly32"



File:CONLAN,Node: Prototypes,Previous:Reference,Up: Specifying,Next: Formulae

	A prototype is specified by a list whose first element is the
keyword "CONSTRAINT" and whose second element is a list of parts.
(the keyword "DEFBODY" is also provided if using a TAGS package
is desired.) Each element of the parts list specifies the name of the
part and the kind of thing it is.  For example, an adder has three
parts (A1, A2 and SUM) each of which is a cell.
	The rest of the prototype specification is some number of a
set of special forms.  FORMULAE describes the rules that relate
the cells of the constraint.  WIRING describes the
interconnections that need to be made when indirects are known.
IF-REMOVED is used for updating external representations.  R==
is used to specify shared parts.  Each will be described in turn.



File: CONLAN,Node:Formulae,Up: Specifying,Previous: Prototypes,Next: Wiring

	The FORMULAE statement consists of a list of rules.
Each rule is of the form:

(<set> <uses> <body>)

or 

(<name> <set> <uses> <body>)

Where <set> is the cell the rule is intended to supply a 
value for, <uses> are the other cells in the constraint it uses, 
and <body> is a lisp expression in terms of the <uses> names
whose value is the result of the rule.  The <name> form of the
rule specification is mainly provided for mnemonic value.
It sometimes is useful when an external system runs and analyzes
the constraint net and must know how a value came about.
	Two potential rule values are treated specially.  The atom 
*DISMISS* means the rule was unable to compute a value with the
specific values of its input parameters, and so none is assigned.
The atom *LOSE* means the rule has detected an inconsistency, and
a contradiction should be signalled.  If <set> is nil, then whatever
value (except *LOSE*) will be ignored.  This convention is useful
for rules that run for effect, such as manipulating an external
representation or looking for inconsistent situations.  The 
FORMULAE statement is illustrated by the description of the
multiplier constraint below.

(defbody multiplier ((m1 cell)
		     (m2 cell)
		     (product cell))
(formulae
 (product (m1) (cond ((NEARLY-ZERO? m1) 0.0)
		     (t *dismiss*)))
 (product (m2) (cond ((NEARLY-ZERO? m2) 0.0)
		     (t *dismiss*)))
 (product (m1 m2)(COND ((NOT (OR (NEARLY-ZERO? M1)
				 (NEARLY-ZERO?  M2)))
			(times m1 m2))
		       (T *DISMISS*)))
 (m1 (product m2)(cond ((not (NEARLY-ZERO? m2))
			(quotient product m2))
		       (t (cond ((NEARLY-ZERO? product)
				 *dismiss*)
				(t *lose*)))))
 (m2 (product m1) (cond ((not (NEARLY-ZERO? m1))
			 (quotient product m1))
			(t (cond ((NEARLY-ZERO? product) 
				  *dismiss*)
				 (t *lose*)))))))



File: CONLAN,Node: Wiring,Up: Specifying,Previous: Formulae,Next: If-removed

	The WIRING statement specifies how the values of indirect
cells should be connected once they are known.  Each rule in the
statement has the syntax:

(<uses> <form-1> <form-2> ... <form-n>)

The <uses> list contains both indirect cells and the names of parts of
the constraint being described which will be refered to within the
rule.  The rule is run whenever all the indirect cells have values.
The <form-i> are either equality statements between parts or
assignments of values to cells.  To enable referencing the constraint
from within its rules, the atom $SELF always has the value of the
constraint the rule is from when the rule is run.  While arbitrary
Lisp code could be placed inside the wiring rule, equality statements
and assignments of values to cells are the only types whose
consequences are automatically retacted when the connection is "broken"
(by forgetting the value of an indirect cell).  The constraint below
uses wiring rules to express the assertion that two containers have the same
level of fluid.

(Constraint Same-Level-Numeric ((Container1 conlan-cell)
				(Container2 conlan-cell)
				(Level cell))
;;;Assumes level parameter of the containers it is given
;;;are numbers in a common global coordinate frame, and
;;;equates them - when one is known, the other is, and
;;;they must be consistent.
(Wiring ((Container1 Level) (== (>> Level Container1)
				Level))
	((Container2 Level) (== (>> Level Container2)
				Level))))

(Constraint Same-Level-Symbolic ((Container1 conlan-cell)
				 (Container2 conlan-cell)
				 (Comp comparator))
;;;Assumes global frame, but uses the level cell as a 
;;;symbolic parameter. A comparator constraint asserts
;;;the equality in a global lattice and thus may enable
;;;other comparators to draw conclusions.
(Wiring ((Container1 Comp)
	 (Set-parameter (>> A comp) 
			(>> Level Container1)))
	((Container2 Comp)
	 (Set-parameter (>> B comp)
			(>> Level Container2))))
;assert that whatever the levels are, they are equal.
(Constant (>> Equal-To? Comp) T))



File: CONLAN,Node: If-removed,Up: Specifying,Previous: Wiring,Next: Shared Structure

	Sometimes it is necessary to use a constraint network with
another kind of representation, such as a diagram or inequality
expert.  Since the body of a rule is a piece of Lisp code, it can
perform bookkeeping by means of side effects.  However, some way must
exist to undo these effects when the values used in the rule are
forgotten.  The IF-REMOVED statement allows this.  The elements of
an IF-REMOVED statements are called "forget functions", and have
the syntax: 

(<trigger> <form-1> <form-2> ... <form-n>)

The trigger can be either a cell or a named rule.  When the trigger is
forgotten, the forms are evaluated from left to right.  The
environment for their evaluation includes bindings for $SELF, the
constraint it belongs to, $SET-CELL, the cell being set, $VALUE, the
value in that cell, and $INFORMANT, the name of the rule.



File: CONLAN,Node: Shared Structure,Up: Specifying,Previous: If-removed

To specify shared structure in a constraint prototype, the statement

(R== <ref-1> <ref-2> ... <ref-n>)

is used.  (As a mnemonic, think of this as "Really equal" or "Rplac-Equal").
Each reference must evaluate to a cell, and during instantiation of the
prototype only one thing will be created and given all of the names.
Below R== is used to define a 3 input adder assuming 2 input adders have
already been defined.

(Constraint three-adder ((A1 cell)
			 (A2 cell)
			 (A3 cell)
			 (Sum cell)
			 (Add1 adder)
			 (Add2 adder))
(R== A1 (>> A1 Add1))
(R== A2 (>> A2 Add1))
(R== (>> Sum Add1) (>> A1 Add2))
(R== A3 (>> A2 Add2))
(R== Sum (>> Sum Add2)))

This illustrates a misfeature of CONLAN (and the language described in
Steele's technical report).  Having a fixed number of parts makes
access simple - finding out what rules are applicable or what cell
values a rule needs can be done without using a global database.
Sadly, it makes things which are really the same (adders) into
different kinds of things (2 input adders, 3 input adders).  A second
problem is that the "connections" between things can change over time
(Influence adders for a Qualitative Process theory implementation, for
example, cannot be easily written in CONLAN).  Several attempts to fix
this problem have been made, but none of them are satisfactory.  The
BBN technical report describes two of them, for the morbid.



File: CONLAN	Node: Building		Up: Top

	There are two ways to build a network out of indivdual constraints.
The first way is to use indirect cells.  The second is to equate parts.
Equating parts makes the constraints behave as if they were the same
thing.  The syntax is:

(== <ref> <ref>)

Unlike R==, the parts refered to can be any two things of the same
type rather than just cells.  The equality mechanism actually works by
making special equality constraints hold between corresponding cells
of the parts.  The equality constraints contain two rules, called
"1<-2" and "2<-1" which place the value of one of the cells into the
other as soon as it is known.  The connection can be broken by using
UN==.



File: CONLAN	Node: Examples		Up: Top

This section contains two examples of interaction with CONLAN.

In the scenarios below, ">>" is the interpreter prompt for more input, and
indented lines are annotations.  The environment was initialized each time
by calling (Conlan-Init).  The function call (Run-Constraints) starts
the read-eval-propagate-print cycle.

* Menu:

* Temperature Conversion::	Classic constraint network example
* Qualitative Boyle's Law	de Kleer's IQ algebra in use



File: CONLAN,Node: Temperature Conversion,Up: Examples,Next: Qualitative Boyle's Law

	Here we will construct and debug a network to convert temperatures
from one scale to another.

;	first start constraint interpreter

>(run-constraints)
>>(create farenheight 'cell)
G0002 
>>(create centigrade 'cell)
G0004 

;	create the parts to perform the computation

>>(create add1 'adder)
G0006 
>>(create mul1 'multiplier)
G0011 
>>(create mul2 'multiplier)
G0016 

;	Now we connect them up

>>(== farenheight (>> sum add1))
IDENTITY 
>>(set-parameter (>> a1 add1) 32.0)
32.0 
>>(== (>> a2 add1) (>> product mul1))
IDENTITY 
>>(== (>> m1 mul1) centigrade)
IDENTITY 
>>(== (>> m2 mul1) (>> m1 mul2))
IDENTITY 
>>(set-parameter (>> product mul2) 5.0)
5.0 
>>(set-parameter (>> m2 mul2) 9.0)
9.0 
>>(set-parameter centigrade 100.0)
100.0 

>>(what-is farenheight)
FARENHEIGHT = 87.555555
T 

;	Oops! We can use dependencies to find the bug...

>>(why farenheight)
I used rule (1<-2 >> 1<=>2) on the following inputs: 
   (>> SUM ADD1)
(G0009) 
>>(premises farenheight)
(>> M2 MUL2) = 9.0 
(>> PRODUCT MUL2) = 5.0 
(>> CENTIGRADE) = 100.0 
(>> A1 ADD1) = 32.0 
T 

;	Must switch the constants around-

>>(change-parameter (>> m2 mul2) 5.0)
5.0 
>>(change-parameter (>> product mul2) 9.0)
9.0 

;	Notice that farenheight is already recomputed-

>>(what-is farenheight)
FARENHEIGHT = 212.0
T 
>>(un== (>> m1 mul1) centigrade)
T 

;	removing a part can undo deductions-

>>(what-is farenheight)
Sorry, I don't know it.



File: CONLAN,Node: Qualitative Boyle's Law,Up: Top,Next: glossary,Previous: Temperature Conversion

Qualitative Reasoning about Boyle's law
	Below we use de Kleer's Incremental Qualitative algebra
to represent the relationship between changes in the parameters
of a gas.  The value of a quantity is represented by either:
	c = "constant"
	u = "increasing"
	d = "decreasing"
	? = "don't know"

>>(create boyle 'gas-law)
G0007 

;   The gas-law constraint encodes PV=KT in the IQ algebra

>>(partnames? boyle)
(PRESSURE TEMPERATURE VOLUME P1 P2) 

;   P1 and P2 are adders that work with the IQ algebra.

>>(set-parameter (>> temperature boyle) 'c)
C 
>>(set-parameter (>> volume boyle) 'd)
D 
>>(what-is (>> pressure boyle))
(>> (A1 P1 BOYLE) (PRESSURE BOYLE)) = U 
NIL 

;   Temperature constant, volume decreasing means the 
;   pressure is increasing.

>>(why (>> pressure boyle))
I used rule (RULE-2 >> P1 BOYLE) on the following inputs: 
   (>> (SUM P2 BOYLE) (SUM P1 BOYLE))
   (>> (A2 P1 BOYLE) (VOLUME BOYLE))
(G0012 G0010) 

;   Why cites the rule directly responsible.

>>(premises (>> pressure boyle))
(>> (A2 P1 BOYLE) (VOLUME BOYLE)) = D 
(>> (A1 P2 BOYLE) (TEMPERATURE BOYLE)) = C 
T 

;	Premises are the assumptions the user made.

>>(results (>> temperature boyle))
Rule (RULE-1 . G0013) got (>> (SUM P2 BOYLE) (SUM P1 BOYLE)) = C 
T 
>>(results (>> sum p1 boyle))
Rule (RULE-2 . G0011) got (>> (A1 P1 BOYLE) (PRESSURE BOYLE)) = U 
T 

;   Using RESULTS we can trace the path of the computation.

>>(change-parameter (>> volume boyle) 'u)
U 

;   Changing a parameter first forgets the results of the old
;   value and then sets the new one.

>>(what-is (>> pressure boyle))
(>> (A1 P1 BOYLE) (PRESSURE BOYLE)) = D 
NIL 
>>(forget-parameter (>> temperature boyle))
((G0008 G0012 G0009) G0009) 
>>(what-is (>> pressure boyle))
Sorry, I don't know it.  I need:
   (>> (SUM P2 BOYLE) (SUM P1 BOYLE)) 
 to use rule: (RULE-2 >> P1 BOYLE)
MUST-BE-ENTERED 
>>



File: CONLAN,Node: Glossary,Up: Top,Previous: Qualitative Boyle's Law

This glossary contains the calls required to run the interpreter,
create networks of constraints, and some relevant flags.

* Menu:

* Functions::	Functions needed to run it
* Flags::	Useful flags in the interpreter





File: CONLAN,Node: Functions,Up: Glossary,Previous: flags

(CONLAN-INIT)
Initializes the interpreter state and destroys whatever networks
currently exist.

(RUN-CONSTRAINTS)
Top level loop for system.  Operates like the normal Lisp read-eval-print
loop, except that the constraint interpreter is fired on each cycle and
allowed to run until it is quiescent or has a clash.

(CREATE <name> <type>)
Creates a constraint of <type> called <name>.  The name must be atomic
and the type must be a legal constraint prototype.

(== <A> <B>)
Equates <A> and <B>.  In particular, whenever a cell in <A> gets a 
value the corresponding cell in <B> will get the same value.  

(un== <A> <B>)
Removes the equality between <A> and <B>, if any.  It will not work
on R=='s used in a prototype.

(SET-PARAMETER <cell> <value>)
Sets <cell> to <value>, giving the informant as the user.  If an
inconsistent value is given a clash occurs.  If <value> is of the
form (<number> <atom>) then <number> is assumed to be the value
and <atom> the units.

(FORGET-PARAMETER <cell>)
If the user was the informant, the value for the cell is forgotten
and all consequences of it forgotten as well.  If the value did not
come from the user nothing happens.

(CHANGE-PARAMETER <cell> <value>)
A combination of FORGET-PARAMETER and SET-PARAMETER.

(WHAT-IS <cell>)
Types the name and value of the cell if it is known, or what
it would need to compute it if it is not.

(WHY <cell>)
Types the informant of the cell and the values (if any) the rule used.

(PREMISES <cell>)
Types all of the user supplied parameters that were used in deducing 
the value for the cell.

(RESULTS <cell>)
Types what was directly computed using the value of the cell.

(SUPPLIERS <cell>)
Types the rules that could provide a value for that cell.

(USERS <cell>)
Types the rules that use the cell.

(NEEDS <cell>)
Types what is needed to compute a value for the cell 
from rules that directly set it.

(UNKNOWN-VALUES <constraint>)
Lists the cells in the constraint that do not yet have values.

(KNOWN-VALUES? <constraint>)
Lists the cells in the constraint that have values.

(INTERNAL-VALUES <constraint>)
Lists the cells that have been set by rules in the constraint.

(EXTERNAL-VALUES <constraint>)
Lists the cells that have been set by something outside the constraint.

(PRINT-RULE <rule>)
Pretty-prints the lisp code that comprises the rule.



File: CONLAN,Node: Flags,Up: Glossary,Previous: Functions

CONLAN flags

*CONLAN-STATUS*
If interpreter ran out of things to do, QUIESCENT.  If a clash
occured, it should be noted by changing this variable to 
(CLASH <disputants>)

*CONLAN-CONTRADICTION-HANDLER*
If bound, it must be a function of one argument that will be 
called whenever a clash occurs.  The argument is a list of 
two copies of a cell, with the conflicting values.

DEBUG-CONLAN
If T, a message is printed when each cell is set.  NIL muzzles it.

*DISPUTANTS*
A list consisting of a cell and a cell-like entity which clash.
This is the argument to the contradiction handling code.

*STOP-CONLAN*
If T, the interpreter will stop.