Next: Labels | Up: Table of Contents | Previous: Included Models
The constraint language is technically not part of TML. TML is not very useful, however, without a constraint language. This section describes version 1.0 of the constraint language, which is the version currently shipping with the TML compiler.
Like TML, constraints are case-sensitive and can contain arbitrary whitespace. Also like TML, both C and C++ style comments may be used in constraints. (Some care is required; see the end of this section.)
Constraints are used to attach numerical values to models, states, and arcs. Each individual constraint can have one or zero values. You can use integers, floating-point numbers, exponential notation, arithmetic operators, and parentheses to define a constraint's value. The following constraints all designate the same value. Note that the order of evaluation is the usual algebraic order.
($ 60 $) ($ 30.0 * 2 $) ($ (1/3)*(18*10) $) ($ 2*20+20 $) ($ 6*10e1 $)
Figure 1: Simple constraint examples
Variables can be assigned and used in constraints. Every variable must be assigned a value before it is used.
A variable is assigned by giving the variable name, which consists of upper- and lower-case letters, digits, and underscores, followed by an equal sign = and an expression for the value. Such expressions may reference other variables, and are evaluated in the order encountered within the constraint.
The following are some more constraints equivalent to those of Figure 1.
($ // Here the variable is not used. // Also notice that no delimiter is // requied after the assignment. a=5 60 // Value of the constraint is still 60. $) ($ a=2 30.0 * a $) ($ value=(1/3)*(18*10) value $) ($ // Assignments are evaluated in order. number = 2 a = number * 20 a = a + 20 a $) ($ // Again, the variable is not used. 6*10e1 // Value of constraint. a = 5 // Assignment. $)
Figure 2: Simple constraints using variables
Constraints may be attached to models, states, or arcs. To attach a constraint to any entity, just write the constraint immediately before the entity's declaration.
When a constraint is attached to an arc, it typically specifies the probability associated with the arc.
Here is a simple example of constraints attached to arcs.
[Work Saved]
($ 0.4 $) "Save" [Work Saved]
($ 0.2 $) "Exit" [Exit]
($ 0.4 $) "Close" [No Work]
Figure 3: Simple constraints on arcs
The scope of a variable assignment in an arc constraint is the constraint itself. This is called arc scope, since the scope of the variable assignment is the arc constraint. For example, the following will result in an error, since the variable a is not defined in the third arc.
[Work Saved]
($ a=0.4 a $) "Save" [Work Saved]
($ 0.2 $) "Exit" [Exit]
($ a $) "Close" [No Work]
Figure 4: Using an undefined variable
This may seem like a bad design, but there should be no required ordering among the arcs of a state. Because of this, the constraint parser cannot know in what order the arc constraints will be evaluated.
The solution is to assign the value to a in a state constraint. As with arcs, constraints on states are given immediately before the state declaration. The following example solves the problem of Figure 4.
($ // Note that this state constraint has no value.
// It just assigns a value to variable a.
a=0.4 $)
[Work Saved]
($ a $) "Save" [Work Saved]
($ 0.2 $) "Exit" [Exit]
($ a $) "Close" [No Work]
Figure 5: Using a state constraint
The scope of a's assignment is now the state constraint and any constraints on arcs from the state. The variable a may still be undefined in other state constraints and in the constraints of arcs from other states. (Again, the reason for this is that there is no ordering among states.) A variable assignment in a state constraint thus has state scope.
To declare a variable assignment whose scope is the entire model, assign the variable in a constraint attached to the model. Such a variable assignment has model scope, and is available in all state constraints and all arc constraints. Note, however, that if the variable's value is overridden in a state constraint, the overriding assignment has state scope.
Consider the following example.
[Work Saved]
($ 4 $) "Save" [Work Saved]
($ 2 $) "Exit" [Exit]
($ 1 $) "Close" [No Work]
Figure 6: Constraints need not sum to one
The constraints here sum to 7, and thus clearly are not exit probabilities for the arcs. What does this mean? To answer this, we have to introduce the idea of constraint resolution.
One way to resolve the above constraints is to normalize them so that they sum to one, as exit probabilities should. This can be requested using the normalize directive in a state constraint, as follows.
($ normalize(1) $)
[Work Saved]
($ 4 $) "Save" [Work Saved]
($ 2 $) "Exit" [Exit]
($ 1 $) "Close" [No Work]
Figure 7: Normalizing constraints
The normalize directive thus has state scope and the arcs are given probabilities equal to 4/7, 2/7, and 1/7, respectively. Note that any value can be given to normalize, though 1 will typically be used for probabilities and 100 for percentages.
Note that the above constraints capture the following relationships: "Exit" should be twice as likely as "Close", and "Save" should be twice as likely as "Exit".
However, what if one of the arcs does not have a constraint? In this case, some value must be assigned to the arc. The constraint language provides three ways to do this.
The simplest is to give a default "assumed" value for all unspecified arcs. This is done with the assume directive. The following is equivalent to Figure 7.
($ normalize(1) assume(1) $)
[Work Saved]
($ 4 $) "Save" [Work Saved]
($ 2 $) "Exit" [Exit]
"Close" [No Work]
Figure 8: Using assume
The value 1 is assumed for the unspecified arc "Close", and then normalization takes place exactly as before.
The second technique (fill) is typically used when one or more arc values are known, but others are not. The known arcs are summed, and the result is subtracted from the fill amount (typically 1 or 100). The difference (or zero, if the sum is greater than the fill amount) is divided evenly among the unspecified arcs. Consider the following.
($ normalize(1) fill(1) $)
[Work Saved]
($ 0.4 $) "Save" [Work Saved]
"Exit" [Exit]
"Close" [No Work]
Figure 9: Using fill
The difference is 1.0-0.4 = 0.6. This is split among the two unspecified arcs, and each is assigned 0.3. In this case, the normalization is redundant, though if the known arcs had summed to more than 1.0, the normalization would still have been needed.
The last technique is the entropy maximization. Without going into too much detail, this approach chooses a value for each unspecified arc such that the resulting single-step uncertainty will be maximized when the arcs are normalized.
Entropy maximization is signalled by the emax directive, which does not take a value as do the others.
As with variables, the constraint resolution directives assume, fill, emax, and normalize have either model, state, or arc scope. Note that arc scope is meaningless for the constraint resolution directives, and any such directives are ignored.
A common approach is to specify normalize(1) and any variables in the model constraint.
One may wish to specify two or more different probability distributions for a given model. Also, one might wish to specify weights, costs, or other numerical information for arcs, state, or models.
One way to do this is to allow multiple constraints to be attached to a single model, state, or arc. But how to tell which constraints are intended to go together?
Multiple constraints can be attached to an entity using keys. A key consists of upper- and lower-case letters, digits, and underscores, and is prefixed to the constraint with a colon :. All constraints with the same key go together. Variable definitions in a constraint with key x have their scope restricted to the those constraints which also have key x. This allows constraints with different keys to be independently resolved.
The following is an example of using multiple constraints on a model.
($ normalize(1) $) cost:($ assume(1) $) model BigModelByStacy // Within this model, probability // constraints do not have a key, // and cost constraints are not // normalized. end
Figure 10: Using keys
Users may use as many keys as desired, but every constraint attached to the same entity must have a unique key.
Whenever the TML parser encounters a ($ token, it reads all text up to the next $) token and passes this text to the constraint parser. The result is stored in the model, and parsing continues. This is important; while it allows the constraint language to be independent of TML, it can also result in what may seem unusual behavior.
Consider the following case of a comment in a constraint. This will result in a parse error.
// A constraint begins here.
($ /* This long comment contains the
end token for the constraint,
and will probably cause a syntax
error in the constraint parser -> $)
This line causes a syntax error in TML.
*/
$) // The constraint is intended to end here.
Figure 11: Misuse of constraint syntax
The syntax error occurs because TML does not know anything about the constraint language; it blindly looks for the $) token. The comment in the constraint is thus not terminated, and may cause a syntax error in the constraint. The moral of the story is: do not use the end token $) anywhere in a constraint.
Also, you should be careful when commenting out constraints because of the way TML handles its own comments. Consider this example, which also causes a syntax error.
// Here is a long comment, intended to
// "comment out" a constraint. Unfortunately,
// TML looks for the first */ token as the end
// of a long comment, and sees the one in
// constraint. The $) token thus causes a
// syntax error in TML.
/*
($ /* This is a long comment in the
constraint, ending here -> */
$)
*/
Figure 12: Misuse of comment syntax
The moral of the story: do not try to comment out constraints which contain /*..*/ (C style) comments.. Even better, do not use long (C style) comments in constraints.
Next: Labels | Up: Table of Contents | Previous: Included Models