Details
on Amine Structures Matching
by
Adil KABBAJ
Amine Structures and structures matching
Amine Object matching (the main call)
The match() operation is the main and basic operation of Amine algebraic level. Various operations are defined as specialization of the match operation (equal(), unify(), subsume(), generalize(), and maximalJoin()). match() and these operations are defined on all Amine structures (elementary objects like Integer, Double, and Boolean, collection objects like AmineSet and AmineList, and complex structures like Term, CG, Concept, and Relation). This document presents details on matching-based operations for all Amine structures except CG, Concept, and Relation (they are discussed in CG Matching).
Amine Structures: Recall
Basic structures in Amine are AmineSet, AmineList, and Term. AmineSet extends HashSet, AmineList extends ArrayList, and Term extends AmineList. See Structures for further details on these structures.
public class AmineSet extends HashSet implements java.io.Serializable,
AmineObject, Matching, AmineConstants {
... // no specific attribute
}
public class AmineList extends ArrayList implements
java.io.Serializable, AmineObject, Matching, AmineConstants {
... // no specific attribute
}
public class Term extends AmineList implements java.io.Serializable {
... // no specific attribute
}
Matching of Amine Structures
As noted in the introduction, match() operation is the most relevant operation in Amine algebraic level. Matching-based operations (equal(), generalize(), maximalJoin(), subsume(), unify()) are defined in term of match() operation which is a generic operation. match() attempts to compare two structures, the nature of the comparison depends on the nature of the match: equality matching, generalization matching, subsumption matching, or unification matching. Let us consider some points about match() operation, that concern all Amine structures:
some matching operations like generalize(), maximalJoin(), and subsumeWithResult() construct a new structure as a result of a successful matching. Other matching operations like equal() and subsume() does not construct a new structure, they check only if the match is true or not. Unification matching doesn't construct a new structure but it has a side effect on variable binding.
match() attempts to compare the current object with the specified object obj. Other parameters of match() include bindingContext and binding information which are necessary to interpret variables that can occur in the two structures to match.
The specification of match() is the same for all Amine structures :
/**
* Match the current object with the specified object obj, according to the value of
* the parameter matchOperation. Match considers the binding context and the binding
* information for the two objects.
* @param matchOperation A byte value that specifies which kind of matching to apply.
* Atually, these values are defined in AmineConstants interface and are: EQUAL,
* UNIFY, SUBSUME, SUBSUME_WITH_RSLT, MAXIMAL_JOIN, and GENERALIZE.
* @param bindContext The binding context
* @param bindInf The binding information for the current object
* @param obj The object to match with the current object
* @param bindInfObj The binding information for the parameter obj
* @return an object which is the result of the match operation. It may return null.
*/public Object match(byte matchOperation, BindingContext bindContext,
Object bindInf, Object obj, Object bindInfObj);
The first part of match() operation is the same for all Amine structures: since obj can be a variable and since match() considers the case of variable binding and resolution, the first step is to consider this case (variable binding and resolution). Let us assume, for next sections, that valObj refers to obj if obj is not a variable or if binding should not be considered. Otherwise, valObj refers to the value of obj. Two special cases are considered in the first part of the match operation: the case where the current object and valObj refeer to the same object, and the case where valObj is either null or it is a variable but binding context and resolution is not considered or it is a free variable (and binding is considered):
If the current object and valObj refeer to the same object; equality of reference, then the two objects match and a copy of the object is returned (if the match should return a value).
ElseIf valObj is null or it is a variable, then the matching depends on the nature of the match:
if matchOperation is maximalJoin then return a copy of the current object. Recall that maximalJoin seeks specificity, that is why it returns a copy of the current object.
elseIf matchOperation is equal or subsume then return failure. Since the current object is not null, neither a variable, then it is not equal to valObj. Also, subsume checks that current object is more general than valObj, but this is not the case here.
elseIf matchOperation is unify and valObj is a Variable then unify valObj with the current object (associate the current object to valObj in the current binding context).
elseIf matchOperation is generalize then return a variable. Recall that generalize seeks the minimal generalization and since, in this case, the current object is specific and valObj is a variable (or is null), then generalization matching returns a variable.
Let us consider now the matching of each Amine structure: matching of AmineSet, Term, and AmineList. Then, we present the matching of Variable and the matching over all Amine objects. CG matching is considered in CG Matching.
The complete code is in : aminePlatform.util.AmineSet
Matching two AmineSets is a simple operation since an AmineSet contains only elementary objects (Integer, Double, Boolean, String, Identifier, AmineInteger, AmineDouble, AmineBoolean). Each type of match corresponds to a specific set operation: equality matching to equality of two sets, generalization matching to intersection, maximalJoin matching to union, and subsumption matching to subset. If valObj is not an AmineSet but it can be an element of an AmineSet, then match will coerce valObj to an AmineSet (i.e. it creates an AmineSet with valObj as its only element) and then it attempts to match the two AmineSets.
The complete code is in : aminePlatform.util.Term
Match two terms consists in checking that they have the same number of arguments and that their arguments match according to their range and according to the type of the match. The code below, extracted from the class Term, illustrates this iterative call to match(): i is an iterator over elements of the first term (the current object represented by this) and j the iterator over elements of the second term (valObj). AmineObjects is a "service" class that provides methods defined on all Amine objects (elementary objects, collection structures, and complex structures).
for (Iterator i = this.iterator(); i.hasNext()
&& areMatched;) {
elem3 = AmineObjects.match(matchOperation, bindContext,
i.next(), bindInf,
j.next(), bindInfValObj);
if (elem3 != null)
areMatched = false;
// else areMatched = true; by default
}
The complete code is in : aminePlatform.util.AmineList
The main difference between Term and AmineList is that an AmineList can terminate with a constructor operator followed by a variable constructor. This structural difference between the two structures has its impact on matching: match the current list with the list valObj is performed in two steps:
Match the common 'fixed' parts of the two lists: The fixed part of a list is all the elements of the list without its last element if it is a constructor. However, to test the matching of the fixed parts, the method has to consider only the common part of the two fixed parts. For instance, the fixed parts of the two lists [a1, a2|x] and [b1, b2, b3|y] are [a1, a2] and [b1, b2, b3] respectively. So the method has to test first the matching of the common part : [a1, a2] and [b1, b2]. The matching of the fixed parts is identical to the matching of term's arguments; it is based on an iterative call of match() on the corresponding elements of the two lists.
Match the variable parts of the two lists: if the 'fixed' parts match, match() will consider next the matching of the 'variable' parts. In the example above, the variable parts of the two lists [a1, a2|x] and [b1, b2, b3|y] are x and [b3|y] respectively. Here is the main treatment:
2.1. If the two variable parts correspond to constructor's variables, then match the two variables (i.e. if the binding resolution is considered and the two variables have values, then the match operation will concern their values). If the match has to construct a result and the match of the two variables returns a value; a list, then match operation will append the returned value to the main list.
2.2. ElseIf one variable part corresponds to a constructor's variable and the other variable part not, then get the value of the constructor's variable (if binding is considered) and then match its value with the other variable part. Again, if the match has to construct a result and the match returns a value; a list, then match operation will append the returned value to the main list.
The complete code is in : aminePlatform.util.Variable
Match the current object, a variable in this case, with a specified object that can be a variable or any Amine Object. The first step is to get the value of the current object/variable and also the value of the second variable (if the specified object is a variable). Of course, this can be done only if binding context and resolution is considered. If the binding is considered and the two variables have values, then variables matching will involve the matching of their values. If the two variables are free or binding is not considered, then we assume that the two variables match (and the match will return a variable if it should return a value). If one input is a (free) variable and the other is a value (of the variable), then the result of the match will depend on the nature of the match:
if matchOperation is maximalJoin then return a copy of the value (maximalJoin returns the most specific),
elseIf matchOperation is unify then associate the value to the variable and return true,
elseIf matchOperation is equal then return failure,
elseIf matchOperation is subsume and the first input is the variable and the second the value, then returns true (since the first input is more general than the second input), otherwise (the inverse) returns false,
elseIf matchOperation is generalize then return a variable (generalize returns the most general).
Amine Object Matching (the main call)
The complete code is in : aminePlatform.util.AmineObjects
AmineObjects is a "service" class and a kind of a dispatcher: it provides static methods that operate on all Amine objects (elementary objects, collection structures, and complex structures). Let us consider match() method for instance:
public static Object match(byte matchOperation, BindingContext bindContext,
Object obj1, Object bindInf, Object obj2, Object bindInfObj);
Special cases and elementary objects are considered directly by the match() of AmineObjects but the matching of Amine structures that implement Matching interface (AmineSet, AmineList, Term, Concept, Relation, CG, and any user structure that implements this interface) is dispatched, via the matching interface, to the specific matching operation.
The general treatment of this "global" match is as follows: the first step performed by the match is to resolve variable binding for obj1 and/or obj2 (if one of them is a variable and binding is considered). Let us assume that valObj1 and valObj2 represent obj1 and obj2 after this first step. Several cases are considered:
if valObj1 is (still) a variable, then call variable matching,
elseIf valObj2 is (still) a variable, then the match will depend on the nature of the match:
if matchOperation is maximalJoin then returns the copy of valObj1 (if it is not null),
elseIf matchOperation is unify then associate valObj2 with valObj1,
elseIf matchOperation is equal or subsume then returns true if valObj1 is null and false otherwise,
elseIf matchOperation is generalize then returns a variable.
elseIf valObj1 is not an AmineSet and valObj2 is an AmineSet, then coerce valObj1 to an AmineSet (if valObj1 can be an element of an AmineSet) and call AmineSet matching.
If valObj1 can not be an element of an AmineSet and matchOperation is generalize, then returns a variable, otherwise returns failure.
elseIf valObj1 is an object that implements Matching, then call the specific matching of valObj1. This generic statement concerns all Amine structures that implements Matching (AmineSet, AmineList, Term, CG, Concept, Relation) and any other structure that implements Matching and that is integrated to Amine:
else if (obj1 instanceof Matching) {
result = ((Matching) obj1).match(matchOperation, bindContext,
bindInf, valObj2, bindInfValObj2);
}
elseIf valObj1 is not null and valObj1.equals(valObj2), then returns a copy of valObj1 (if the specific match should return a value) or return true,
else (i.e. valObj1 or valObj2 is null, or the two are different simple objects); the treatment will depend on the nature of the match:
if matchOperation is maximalJoin then (returns the most specific)
if one is null and the other is not then returns a copy of the non-null object,
elseIf both valObj1 and valObj2 are Type then return the maximalCommonSubType of the two types,
else return false,
if matchOperation is unify then (perform unification)
if both valObj1 and valObj2 are Type then check that they have a maximalCommonSubType,
else if both valObj1 and valObj2 are not null then returns false,
else returns success,
elseIf matchOperation is equal then (check equality)
if valObj1 is null and valObj2 is a (free) variable then returns true
else returns false,
elseIf matchOperation is subsume then (check generality: the first input is more general than the
second input)
if valObj1 is null then returns true
elseIf both valObj1 and valObj2 are Type then
if valObj1 is a superType of valObj2 then returns true
else returns false
elseIf matchOperation is generalize then
if both valObj1 and valObj2 are Type then returns the minimalCommonSuperType of the two types,
else returns a variable