Thursday, June 11, 2009

Complex logic formulas #1

Dear all, after some days spent between papers, code and travels, I am back with a new post! Today, the topic is operators.


Look at a simple rule:

when
$p : Person ( name == "sotty" , age >= 27 , )
$m : Message ( sender == $p , length < 160 , $b : body)
then
System.out.println( $b );
end


This a "trivial" logical expression : all the constraints, including the Type checks, are AND-ed together: a tuple [person, message] must satisfy them all to generate an activation. Even in boolean logic, however, it is possible to define more complex formulas, using logical connectives.
These operators are AND (all constraints must be true), OR (at least one constraint must be true), XOR (only one constraint must be true) and IMPLY (the conclusion must be true when the premise is true). Moreover, there is the negation NEG, which reverses the result of its operand.


Those of you familiar with logic could object that it is not strictly necessary to have all operators as primitives, since they can be mutually defined. For example NEG and IMPLY (or NEG and AND) are sufficient to define all others: (A OR B) is equivalent to ((A IMPLY B) IMPLY B), or to NEG((NEG A) AND (NEG B)) and so on...

However, the conversion is verbose. The resulting formula is much less clear and understandable than the original one (and tends to be more expensive to evaluate) so operators should be available as primitive, at least to write rules.

Operators can still be used both within patterns: the usual "&&" and "||" have been extended with "^^" (XOR) , "->" (IMPLY) and "<->" (EQUIV) :


rule "In-Pattern"
when
$t : Tea ( lemon == true ^^ milk == true )
then
...
end


but also between patterns, where operators are denoted using a textual form (or, and, imples, equiv and xor) instead of a symbolic one. An example:


rule "Between-Pattern"
when
$c : Car( $o : owner, miles ~few || price ~low )
or
$b : Bike( owner == $o )
then
...
end



Normally, this rule would be split in two separate rules, but this is not the case in Chance.
The patterns are matched and evaluated, as usual, but then the operator, OR in the example, will combine the resulting degrees.
This actually open several questions, to which detailed answers will be given in future posts; but for now, just to give a hint:


what is the exact semantics of an operator such as OR ?
according to the spirit of Chance, it can be customized...

what does an operator such as OR actually operate on ?
operators may be truth-functional, i.e. just operate on the degrees resulting from evaluating the operands, or not, requiring additional information...

but what is the point of using and operator such as OR if the operands are automatically true?
the operands are not automatically true. Nor false. There's imperfection...



While a tuple is being built, the various degrees resulting from the various evaluations
are collected and organized in a tree structure, called "Evaluation", mirroring the structure of the formula. Something like:


or
and
class == Car
or
miles ~few
price ~low
and
class == Bike
owner == $o


So, regarding question #2: a truth-functional operator requires only the degrees of its operands to be evaluated; a semi-truth functional operator may require a deeper visit of the tree structure; a general, non-truth functional operator requires even more additional information, such as data from the tuple (the arguments) being evaluated.


To conclude this post, consider the final example:


rule "Not yet Socrates"
when
(implies
$p : Person( $n : name )
Person( this == $p , this ~mortal )
)
then
...
end


This rule somewhat recalls a famous example from the history of logics, Socrates' famous syllogism. In time I'll show how to turn it fully in the rule "All men are mortal", but for now some building blocks are still missing: quantifiers, induction and Modus Ponens among them.
Upcoming posts, instead, will deal with negation and operator customization. In which order, I'm not certain.
Share/Bookmark