Compute Conditions

Author: Jeff Dalton

Updated: Sat Feb 18 03:02:02 2006 by Jeff Dalton


1. Introduction

Compute conditions are constraints that call functions or procedures.
They can be used to perform calculations, to manipulate data structures,
and to access external resources such as databases.

In a refinement that contains compute conditions, the computes
are implicitly at the beginning of the node being expanded and
also act as filters on the applicability of the refinement.
A compute condition either produces a single answer or multiple
answers that are treated as alternatives.  The automatic
planner will pick one of the alternatives and consider the
others only as needed.  However, compute and world-state
conditions are evaluated together, and it is often possible
to eliminate some possible combinations of values when
the refinement is applied.

In addition, there is a programming language, provisionally called
I-Script, that can be used to define new procedures that can be
called in compute conditions.  The procedures can be defined in
I-Script, or the I-Script interpreter may be extended by defining
new built-in functions in Java.  I-Script code can be incorporated
in objects, such as domain definitions, and can be input and output
as XML in the same manner as other I-X objects.

I-Script currently has two external syntaxes.  One is XML; the other
looks like Lisp.  Both can be used in XML, though the Lisp-syntax
code appears as text (inside a lisp-source-text element) rather than
having any structure visible as XML.

Here is a very simple example of a refinement that contains a
compute condition:

(refinement test (test)
  (variables ?x)
  (constraints
    (compute (+ 3 4) = ?x)
    (world-state effect (answer) = ?x)))

The general LTF (".lsp") syntax is:

  (compute [multiple-answer] <function call> = <value pattern>)

For a compute to be evaluated, it must be possible to give
values to all of the variables that appear in the <function call>.
The function is then called, and the <value pattern> is matched
against the result, which binds any variables in the pattern.
So, in the above example ?x would be bound to 7.

The part about giving values to all of the variables in the
function call means it must be possible to determine what
all of the possible values are.  Also, because compute
conditions act as filters on the choice of refinement,
it must be possible to determine the possible values at
the time when the planner is deciding which refinement
to use to refine an activity.

This turns out to mean that each variable must either appear
in the refinement's pattern (when the refinement is being
used in context in which the possible matches are known
and will all bind the variable) or appear in another constraint
that can be evaluated earlier.  For example:

(refinement test (test)
  (variables ?block ?volume ?density ?mass)
  (constraints
    (world-state condition (is-block ?block) = true)
    (world-state condition (volume ?block) = ?volume)
    (world-state condition (density ?block) = ?density)
    (compute (* ?volume ?density) = ?mass)

Note that, though in principle those constraints could be written
in any order, in practice, to simplify the implementation and to
make refinements easier to understand, they must be written in
an order that works as-is.


2. Detailed LTF syntax

Compute conditions:

  <compute condition> ::=
      (compute [multiple-answer] <function call> = <value pattern>)

  <value pattern> ::= <item>

  <item> ::= <number> | <symbol> | <string> | <pattern> | <variable>

  <pattern> = ( <item>* )

A pattern is a sequence of zero or more items inside parentheses,
i.e., as a list.  That is standard I-X terminology.  A "value
pattern" is often just called a "value"; but here we need to
emphasise that it can contain variables and will be matched
against the value (meaning a data object) returned by the function
call.

Function calls:

  <function call> ::= ( <function> <argument>* )

  <function> ::= <symbol> | <lambda expression>

  <argument> ::= <item>

The function is usually a symbol: the name of a built-in or
user-defined I-Script function.  The arguments are treated
as data objects, not as expressions that are evaluated.
The function is applied to those objects (after substitution
for any variables).

This is somewhat counterintuitive and has been done for technical
reasons; it is possible the future versions will work differently.
To make it easier to specify computations that cannot be written
as a single function call, the function may be a lambda expression:

  <lambda expression> ::= (lambda (<symbol>*) <expr>*)

The symbols are the formal parameters of the function; the
exprs are I-Script expressions written in the Lisp syntax.
Although ?-variables may be written in a lambda-expression,
and will be have values substituted in the usual way, that
should not normally be done, and it is tricky to write
something that will have the behaviour you expect.

Here's an example that tests whether the length of the
list that is the value of ?path is equal to 2:

  (compute ((lambda (p) (= (length p) 2)) ?path) = true)

You can think of lambda-expressions as a way to switch to
I-Script from the language normally used in constraints.

For more information lambda-expression, see the note on I-Script.


2. Multiple-answer compute conditions

When we gave the LTF syntax, above, it looked like this:

  (compute [multiple-answer] <function call> = <value pattern>)

The multiple-answer is optional.  When it is present, the
value returned by the function call must be a collection
(a list or set).  Each element of the collection is taken
as an alternative answer.

Note that the value can be a collection even when the compute
is not multiple-answer; but then the collection itself is taken
as the single answer.  (Also, with a multiple-answer compute,
one or more elements of the collection may also be collections.
In that case, each such element is taken as one of the
alternative answers; it is not expanded into further alternatives.)

In the following examples, we will use an "identity" function.
It just returns it's argument and is an easy way to specify
some values to be considered as alternative answers.

(refinement test1 (test1)
  (variables ?x)
  (constraints
    (compute multiple-answer (identity (a b c)) = ?x)
    (world-state effect (answer) = ?x)))

When test1 is used as a refinement, there are three possible
values of ?x: a, b, and c.

(refinement test2 (test2)
  (variables ?x)
  (constraints
    (compute multiple-answer (identity (a b c)) = ?x)
    (compute multiple-answer (identity (aa b cc)) = ?x)
    (world-state effect (answer) = ?x)))

In test2, since both compute conditions provide values for ?x,
and both conditions must be satisfied, there is only one possible
value for ?x: b.


3. XML syntax

In I-X XML, a compute condition is:

  a constraint element with:
    symbol attribute type = compute
    optional symbol attribute relation = multiple-answer
    sub-element parameters = a list containing one pattern-assignment

In the pattern-assignment, the pattern is the constraint's
<function call> and the value is the constraint's <value pattern>.

For example, constraint (compute (+ 3 4) = ?x) would be:

  <constraint type="compute">
    <parameters>
      <list>
        <pattern-assignment>
          <pattern>
            <list>
              <symbol>+</symbol>
              <long>3</long>
              <long>4</long>
            </list>
          </pattern>
          <value>
            <item-var>?x</item-var>
          </value>
        </pattern-assignment>
      </list>
    </parameters>
  </constraint>


4. Attaching I-Script code to domains

This is done by giving the domain a compute-support-code
annotation.  The value of the annotation can be either a
string, which is treated as a resource name (file name or URL),
or an instance of a class that implements the IScriptSource
interface.

In LTF syntax, at present only the version that gives a resource
name can be used; in XML, both are available.

The resource name is *not* relative to the domain's URL.
That is because I-X does not currently retain the information.
So, for example, 

  (annotations
    (compute-support-code = "test-domains/trains-1-support.lsp"))

refers to the file test-domains/trains-1-support.lsp, relative
to the user's current directory.

There are two classes that implement the IScriptSource interface,
one for including I-Script code in its Lisp syntax, and one for
the XML syntax.  They are i-script-lisp-source and i-script-xml-source,
respectively.  For example:

  <i-script-lisp-source>(defun f (x y) (+ x y))</i-script-lisp-source>

or, with details omitted:

  <i-script-xml-source>
   <expression>
    <assignment to="f">
     <value>
      ... definition of the function ...
     </value>
    </assignment>
   </expression>
  </i-script-xml-source>


5. Defining new built-in I-Script functions

Here is an example of one way to do it:

    import ix.ip2.*;

    import ix.util.lisp.Interpreter;

    public class MyIp2 extends Ip2 {

        ...

        protected ProcessModelManager makeModelManager() {
	    Ip2ModelManager mm = (Ip2ModelManager)super.makeModelManager();
            defineNewBuiltins(mm.getComputeInterpreter());
	    return mm;
        }

        protected void defineNewBuiltins(ComputeInterpreter comp) {
	    comp.define(new JFunction("get-rgb-value", 1) {
                public Object applyTo(Object[] args) {
		    String colour = (String)mustBe(String.class, args[0]);
                    return lookupRGB(colour);
                }
            });
	}

        ...

    }

The Java code above defines a subclass of ix.ip2.Ip2.  The method
that constructs the model-manager is used to get the compute
interpreter and tell it to add a new built-in function.
