// FILE. . . . . d:/hak/hlt/src/hlt/fot/fuz/SignatureSimilarity.java
// EDIT BY . . . Hassan Ait-Kaci
// ON MACHINE. . Hak-Laptop
// STARTED ON. . Sat Jul 14 07:23:57 2018
/** *
* @version Last modified on Mon Dec 16 09:57:31 2019 by hak
* @author Hassan Aït-Kaci
* @copyright © by the author
*/
package hlt.fot.fuz;
import hlt.fot.*;
import hlt.math.fuzzy.FuzzyMatrix;
import hlt.math.fuzzy.FuzzyMatrix;
import hlt.language.util.Stack;
import hlt.language.util.Queue;
import hlt.language.util.SetOf;
import java.util.ArrayList; // hlt.language.util.ArrayList causes a bug - check this out later
import java.util.HashMap;
import java.util.Iterator;
/**
* This is a class for a similarity on a first-order term constructor
* signature. It extends the class FuzzyMatrix
* with fields and operations dealing with the functor names and arities
* and how argument positions of each pair of similar functors
* correspond. It also provides fuzzy unification and generalization lattice operations modulo
* the subsumption ordering that the similarity and argument-position
* correspondances induce on FirstOrderTerms. The formal
* details are reported in this
* article and its references.
*
* @see ../Signature
* @see ../FirstOrderTerm
* @see SimilarFunctorSignature
* @see ../../math/fuzzy/FuzzyMatrix
*/
public class SignatureSimilarity extends FuzzyMatrix
{
/* ************************************************************************ */
/**
* FOT COMPONENTS ACCESSORS
*/
/**
* Contains the functors. Initialized in the constructor
* SignatureSimilarity(SimilarFunctorSignature signature,
* double[][] data).
*/
private SimilarFunctorSignature signature;
/**
* Returns the signature of this similarity.
*/
public SimilarFunctorSignature signature ()
{
return signature;
}
/**
* Returns the functor at index functorIndex in this
* similarity's signature, where 1 ≤
* functorIndex ≤ signature.size(). If this
* signature is empty, returns null. Important: for a
* functor f, the index of f in its signature
* (i.e., the value of f.index()) is numbered from
* 0 to signature.size()-1, whereas
* this.functor(functorIndex) and
* signature.functor(functorIndex) expect their argument
* numbered from 1 to signature.size(). In other
* words, this.functor(functorIndex).index() =
* functorIndex-1.
*/
public Functor functor (int functorIndex)
{
return signature.functor(functorIndex);
}
/**
* Returns the functor called name in this similarity's
* signature.
*/
public Functor functor (String name)
{
return signature.functor(name);
}
/* ************************************************************************ */
/**
* CLASS COMPONENTS ACCESSORS
*/
/**
* This keeps a global record of a unique representation per each
* similarity class for this similarity as an ArrayList of
* sets of functors. It is initialized in the
* SignatureSimilarity constructor, and is updated by need
* upon construction of a new functor similarity class.
*/
private ArrayList similarityClasses;
/**
* This is a private cache for a set-of-functors object representing
* the similariry class of functors consisting of the full signature,
* and is its unique representative.
*/
private SetOf fullSignatureClass;
/**
* This is a private tool that returns the unique set of functors that
* is the full signature, creating it and recording it if needed. It
* is invoked by need upon building the functor partition consisting
* of the full signature in fullSignaturePartition().
*/
private SetOf fullSignatureClass ()
{
// if already built, return it
if (fullSignatureClass != null)
return fullSignatureClass;
// otherwise, create it
fullSignatureClass = new SetOf(signature.functors());
// populate it will all the existing functors
for (int i = 1; i <= signature.size(); i++)
fullSignatureClass.add(signature.functor(i));
// record it
sayIfTracing(3,
"recording full signature class "+fullSignatureClass+
" in classes "+similarityClasses);
similarityClasses.add(fullSignatureClass);
sayIfTracing(3,
"now classes = "+similarityClasses);
// and return it
return fullSignatureClass;
}
/**
* This is a private tool that returns the (unique) canonical
* similarity class corresponding to the specified set of functors
* similarityClass. It is invoked in the private tool
* partition(degreeIndex).
*/
private SetOf canonicalClass (SetOf similarityClass)
{
int degreeIndex = similarityClasses.indexOf(similarityClass);
if (degreeIndex != -1)
{
sayIfTracing(2,
"found canonical class for "+similarityClass+
" in known classes "+similarityClasses+
" at index "+degreeIndex+": "+(SetOf)similarityClasses.get(degreeIndex));
// found it; return it
return (SetOf)similarityClasses.get(degreeIndex);
}
// otherwise, add it as a canonical class and return it
sayIfTracing(2,
"recording it as a new signature class "+similarityClass+" in classes "+similarityClasses);
similarityClasses.add(similarityClass);
sayIfTracing(2,
"now classes = "+similarityClasses);
return similarityClass;
}
/* ************************************************************************ */
/**
* CONSTRUCTOR
*/
/**
* Constructs a SignatureSimilarity on the given signature
* using the specified square matrix of fuzzy degrees.
*/
public SignatureSimilarity (SimilarFunctorSignature signature, double[][] data)
{
super(data);
this.signature = signature;
signature.setSimilarity(this);
similarityClasses = new ArrayList();
// // This is just to see the seed pairs as a matrix before computing the closure:
// System.out.println(">>> Declared pairs of functors in this signature:\n");
// show();
this.i_similarity_closure();
computeDegrees();
}
/* ************************************************************************ */
/**
* PARTITIONS
*/
/**
* A private cache for the one-element array that is the unique
* representative of the partition consisting of the full functor
* signature.
*/
private SetOf[] fullSignaturePartition;
/**
* This is a private tool that returns the partition of the functor
* signature as a unique one-element array containing only one class
* that is unique set of functors representing the full signature,
* creating it and recording it if needed. It is invoked by need upon
* building all the partitions when invoking
* partition(degreeIndex) for each of the indices in the
* degrees array.
*/
private SetOf[] fullSignaturePartition ()
{
if (fullSignaturePartition != null)
return fullSignaturePartition;
fullSignaturePartition = new SetOf[signature.size()];
for (int i = 0; i < fullSignaturePartition.length; i++)
fullSignaturePartition[i] = fullSignatureClass();
return fullSignaturePartition;
}
/**
* An array of caches for the partition arrays per degree so
* partitions share the same unique set objects many times over. This
* is an array of length degrees.size() of arrays of length
* signature.size() of sets of functors representing the
* α-partitions for each cut α ∈
* degrees.
*/
private SetOf[][] partitions;
/**
* Returns the partitions (an array of arrays of sets of functors),
* creating it if needed.
*/
public SetOf[][] partitions ()
{
// initialize partitions if needed as an array of similarity classes (sets of functors)
// of the size of the set of degrees.
if (partitions == null)
partitions = new SetOf[degrees.size()][];
return partitions;
}
/**
* Returns the partition (an array of sets of functors) at the
* greatest degree in degrees that is ≤ than the specified
* cut.
*/
public SetOf[] getPartition (double degreeCut)
{
return getPartition(getDegreeIndex(degreeCut));
}
/**
* Returns the partition (an array of sets of functors) at the
* approximation degree degreeIndex located at the specified
* index in degrees.
*/
public SetOf[] getPartition (int degreeIndex)
{
// SetOf[] partition;
// System.err.println("%%% partitions:");
// for (int i = 0; i < partitions().length; i++)
// partition = partitions[i];
// {
// partition = partitions[i];
// if (partition != null)
// {
// // System.err.println("%%% partitions["+i+"] contains "+partition.length+
// // " class"+(+partition.length==0?"":"es")+": "+
// // partitionToString(partition));
// System.err.println("%%% for degree "+degrees.elementAt(i)+
// ", partition["+i+"]: "+partitionToString(partition));
// }
// }
// if partitions[degreeIndex] is there, return it
if (partitions()[degreeIndex] != null) // need the () to initialize partitions if needed
return partitions[degreeIndex];
// {
// System.err.println("%%% partition at index "+degreeIndex);
// partition = partitions[degreeIndex];
// System.err.println("%%% evaluated partition corresponding to degree "+
// degrees.elementAt(degreeIndex)+" at index "+degreeIndex+": "+
// partitionToString(partition));
// System.err.println("%%% getPartition("+degreeIndex+") returning "+partitionToString(partition));
// return partition;
// }
// otherwise set partition[degreeIndex] to the partition at the degree at this index and return it
sayIfTracing(3,
"partitioning for index "+degreeIndex+" corresponding to degree "+
degrees.elementAt(degreeIndex));
// System.err.println("%%% returning partition["+degreeIndex+"] = partition("+degreeIndex+")");
return partitions[degreeIndex] = partition(degreeIndex);
}
/**
* Returns a string version of the specified partition (i.e.,
* as a set of similarity classes with no class repeated).
*/
public String partitionToString (SetOf[] partition)
{
ArrayList dejavu = new ArrayList();
StringBuffer buf = new StringBuffer("{ ");
for (int i = 0; i < partition.length; i++)
if (!dejavu.contains(partition[i]))
{
buf.append((i==0?"":", ")+partition[i]);
dejavu.add(partition[i]);
}
return buf.append(" }").toString();
}
/**
* Invoking partition(degreeIndex), where 0 ≤
* degreeIndex ≤ degrees.size(), will return an
* array of sets of functors from this similarity's signature, one
* array per functor. Hence, this array has the same size as the
* signature. Each entry in this array is the canonical set of
* functors that is a similarity class at the fuzzy approximation
* degree at this index in the DoubleArrayList
* degrees. Each class whose index is an entry in this array
* corresponding to a functor f in the signature contains
* f and all the other functors that are
* degrees.get(degreeIndex)-similar to f. Each class
* is uniquely represented and shared in all partitions (it is the
* same functor-set object in all the partitions it belongs to). For
* example, if for a signature equal to {a,b,c,f,g,h}, the
* similarity's data matrix is:
*
*
*
*
* a b c f g h
* --- --- --- --- --- ---
* a | 1.0 0.5 0.0 0.5 0.4 0.2
* b | 0.5 1.0 0.0 0.5 0.4 0.0
* c | 0.0 0.0 1.0 0.0 0.0 0.0
* f | 0.5 0.5 0.0 1.0 0.4 1.2
* g | 0.4 0.4 0.0 0.4 1.0 0.2
* h | 0.2 0.2 0.0 0.2 0.2 1.0
*
*
* then, its degrees is the DoubleArrayList
* [0.0, 0.2, 0.4, 0.5, 1.0] and its partition at degree
* 0.4, i.e., at degree degreeIndex
* 2, is the set of functor classes {{a, b,
* f, g}, {c} {h}} which is
* represented by the 6-element array given by partition(2) =
* partitions[2]:
*
*
* a: A
* b: A
* c: C
* f: A
* g: A
* h: H
*
*
* where A={a,b,f,g}, C={c}, and H={h} are
* canonical similarity classes.
*/
private SetOf[] partition (int degreeIndex)
{
if (degreeIndex == 0)
return fullSignaturePartition();
double degreeCut = degrees.get(degreeIndex);
SetOf[] partition = new SetOf[signature.size()];
sayIfTracing(3,
"created an array of similarity classes for "+
signature.size()+" functors: "+signature.functors()+
" at approximation degree "+degreeCut+" (degreeIndex "+degreeIndex+")");
for (int i = 1; i <= signature.size(); i++)
{
SetOf similarityClass = new SetOf(signature.functors());
for (int j = 1; j <= signature.size(); j++)
if (similarityDegree(functor(i),functor(j)) >= degreeCut)
similarityClass.add(functor(j));
sayIfTracing(3,
"");
sayIfTracing(3,
"computed class of functor "+functor(i)+": "+similarityClass);
similarityClass = canonicalClass(similarityClass);
partition[i-1] = similarityClass;
}
sayIfTracing(3,
"partition("+degreeCut+") :");
if (tracing)
{
for (int i = 0; i < partition.length; i++)
sayIfTracing(3,
"@@@ the set of functors "+degreeCut+"-similar to "+functor(i+1)+" is "+partition[i]);
}
return partition;
}
/* ************************************************************************ */
/**
* CLASS REPRESENTATIVES
*/
/**
* For any degreeCut ∈ [0.0,0.1], this returns
* the index of the largest degree ∈ degrees
* such that degree ≤ degreeCut. Since
* 1.0 is always the largest degree in degrees and
* corresponds to the finest partition, it is always the case that
* degrees.get(degrees.size()-1) = 1.0. Because
* degrees is an IntArrayList sorted in increasing
* order, in order to find the largest index, this sweeps it
* down starting at its highest index.
*/
public int getDegreeIndex (double degreeCut)
{
boolean found = false;
int degreeIndex = degrees.size(); // start at the end
// System.err.println("### defined degrees are "+degrees);
double degree = 1.0;
// as long as it hasn't been found and we're not at 0 yet
while (!found && --degreeIndex >= 0)
// if this degree is <= degreeCut, this is the one we want
found = degrees.elementAt(degreeIndex) <= degreeCut;
// if at this point found is still false, then degreeIndex must be 0; this
// means that no degree in degrees is <= degreeCut
if (!found)
sayIfTracing(1,
"no degree in this similarity is <= "+degreeCut);
// therefore, the partition consists only one similarity class
// containing all the functors in the signature and is always the
// value of partitions[0].
return degreeIndex;
}
/**
* To each similarity class of functors is associated a unique
* functor representative at each degree α
* ∈ degrees. It is always the functor of least index
* among the functors of least arity in the class. The array
* functorReps is a cache structure for these representatives
* that eliminates useless repeated recomputation each time the
* functorRep method is invoked.
*/
private Functor[][] functorReps;
/**
* This returns the unique representative of the specified functor at
* the specified cut.
*/
public Functor functorRep (Functor functor, double degreeCut)
{
return functorRep(functor,getDegreeIndex(degreeCut));
}
/**
* This returns the unique representative of the specified functor for
* the degree at the specified index in degrees
*/
private Functor functorRep (Functor functor, int degreeIndex)
{
if (functorReps == null)
functorReps = new Functor[signature().size()][degrees.size()];
Functor rep = functor;
for (Iterator it = functorClass(functor,degreeIndex).iterator(); it.hasNext();)
{
Functor F = (Functor)it.next();
if (F.arity() < rep.arity())
{
rep = F;
continue;
}
if (F.arity() == rep.arity() && F.index() <= rep.index())
rep = F;
}
return functorReps[functor.index()][degreeIndex] = rep;
}
/**
* This returns the degreeCut-similarity class of the specified
* functor.
*/
public SetOf functorClass (Functor functor, double degreeCut)
{
// return functorClass(functor,getDegreeIndex(degreeCut));
// equivalent to:
return getPartition(degreeCut)[functor.index()];
}
/**
* This returns the degrees.get(degreeIndex)-similarity class of
* the specified functor.
*/
public SetOf functorClass (Functor functor, int degreeIndex)
{
return getPartition(degreeIndex)[functor.index()];
// System.err.println("&&& retrieving the "+degrees.elementAt(degreeIndex)+
// "-similarity functor class of "+functor+" (degree index "+degreeIndex+")");
// SetOf[] partition = getPartition(degreeIndex);
// System.err.println("!!! getPartition("+degreeIndex+") is "+partitionToString(partition));
// System.err.println("!!! the index of functor "+functor+" is "+functor.index());
// SetOf functorclass = partition[functor.index()];
// System.err.println();
// System.err.println("&&& returning class partition["+degreeIndex+
// "] for functor "+functor+" from class partition: "+
// partitionToString(partition)+
// " (functor index: "+functor.index()+");"+
// " result is: "+functorclass);
// return functorclass;
}
/**
* This returns the unique term-similarity class representation for
* the given term at the given degree cut.
*/
public FirstOrderTerm termRep (FirstOrderTerm term, double degreeCut)
{
return termRep(term.deref(),getDegreeIndex(degreeCut));
}
/**
* This is a private tools that returns the unique term-similarity
* class representation for the given term at the given degree index.
*/
private FirstOrderTerm termRep (FirstOrderTerm term, int degreeIndex)
{
if (term.isVariable())
return term;
FirstOrderTermStructure T = (FirstOrderTermStructure)term;
Functor functor = functorRep(T.functor(),degreeIndex);
if (T.isConstant())
return new FirstOrderTermStructure(functor);
FirstOrderTerm[] arguments = new FirstOrderTerm[functor.arity()];
int minArity = Math.min(T.functor().arity(),functor.arity());
for (int i = 0; i < minArity; i++)
arguments[i] = termRep(T.arguments()[i],degreeIndex);
// we don't care about the left-over arguments since a functor rep
// has always least arity in its similarity class
return new FirstOrderTermStructure(functor,arguments);
}
/**
* This returns the degreeCut-similarity class of a dereferenced
* copy of the specified first-order term as an ArrayList of
* first-order terms.
*/
public ArrayList termClass (FirstOrderTerm term, double degreeCut)
{
return termClass(term.deref(),getDegreeIndex(degreeCut));
}
/**
* This returns the degrees.get(degreeIndex)-similarity class
* of the specified first-order term as an ArrayList of
* first-order terms. It enumerates all the terms that are obtainable
* by replacing each functor by one that is
* degrees.get(degreeIndex)-similar to it. A variable is
* replaced only by itself at any degree. For larger-arity functors,
* the extra-arguments are new variables. N.B., this assumes
* that all variables in the term have been dereferenced; i.e.,
* that term was the result of applying deref() to
* an initial term possibly containing bound variables - a virginal
* clean copy as it were since this eliminates all bound
* variables. All the terms in the class will be so clean as well (no
* bound variables).
*/
private ArrayList termClass (FirstOrderTerm term, int degreeIndex)
{
sayIfTracing("computing the similarity class of term "+term+
" at degree index "+degreeIndex);
// this is the list of all the terms that will be returned that gathers all
// those similar to the specified term at the degree at specified index
ArrayList similarTerms = new ArrayList();
// if it's a variable, return the ArrayList that only contains it alone
if (term.isVariable())
{
similarTerms.add(term);
return similarTerms;
}
// so term is a structure: either without arguments (a constant) or
// with arguments (its functor's arity > 0)
FirstOrderTermStructure T = (FirstOrderTermStructure)term;
// compute the term's functor's class
SetOf functorClass = functorClass(T.functor(),degreeIndex);
// for each functor in the class
for (Iterator it = functorClass.iterator(); it.hasNext();)
{
Functor functor = (Functor)it.next();
// if this is a constant, add it and proceed with other functors
// in the class
if (functor.arity() == 0)
{
similarTerms.add(new FirstOrderTermStructure(functor));
continue;
}
// it is a structure with arguments: we need to collect them
// arrayOfArrayLists is an array of functor.arity() ArrayLists,
// one per argument each containing the term classes of each
// argument
ArrayList[] arrayOfArrayLists = new ArrayList[functor.arity()];
// fill it with the term classes of each the term's arguments
// that are present or anonymous variables
increaseTracingMargin(" of term "+T);
for (int i = 1; i <= functor.arity(); i++)
if (i <= T.functor().arity())
arrayOfArrayLists[i-1] = termClass(T.argument(i),degreeIndex);
else
arrayOfArrayLists[i-1] = termClass(Variable.anonymousVariable(),degreeIndex);
decreaseTracingMargin(" of term "+T);
// this will contain ArrayList indices, one per argument position
int[] listIndices = new int[functor.arity()];
// initialize it full of 0s
for (int i = 0; i < listIndices.length; i++)
listIndices[i] = 0;
// pick one term from each list of terms in the array of lists
// and build a new term to add to similarTerms
do
{
FirstOrderTerm[] arguments = new FirstOrderTerm[functor.arity()];
for (int i = 0; i < functor.arity(); i++)
if (i < Math.min(functor.arity(),T.functor().arity()))
arguments[i] = (FirstOrderTerm)arrayOfArrayLists[i].get(listIndices[i]);
else
arguments[i] = Variable.anonymousVariable();
similarTerms.add(new FirstOrderTermStructure(functor,arguments));
}
while (moreArguments(listIndices,arrayOfArrayLists));
}
return similarTerms;
}
/**
* This will try to update the array of indices by incrementing the
* one of least position that can still be and return true if
* this is possible. Otherwise, this means that all the int
* elements in the array of list indices have reached their maximum
* values (i.e., each is equal to the size of the corresponding
* ArrayList), and so this will return false.
*/
private boolean moreArguments (int[] listIndices, ArrayList[] arrayOfArraylists)
{
for (int i = listIndices.length-1; i >= 0 ; i--)
{
if (listIndices[i] < arrayOfArraylists[i].size()-1)
{
listIndices[i]++;
return true;
}
// here, listIndices[i] = arrayOfArraylists[i].size()-1: it has
// exhausted this list; reset it to 0 and all the previous lists
// of indices exhausted up to position i and increment the one
// at the highest position below that isn't exhausted; if not
// possible, there is no more combination of arguments
while (i >= 0 && listIndices[i] == arrayOfArraylists[i].size()-1)
listIndices[i--] = 0;
if (i >= 0)
{
listIndices[i]++;
return true;
}
// i == 0 we're out of combinations
}
return false;
}
/* ************************************************************************ */
/**
* UTILITIES
*/
/**
* Returns the similarity degree of the specified functors.
*/
public double similarityDegree (Functor lhs, Functor rhs)
{
return data[lhs.index()][rhs.index()];
}
/**
* Returns the similarity degree of the two specified terms. On pairs
* of structures, it proceeds recursively on the maximum number of
* common argument positions (i.e., the least of the two
* functors' arities). This is the one defined in this
* paper (see also the LOPSTR
* 2017 conference slides).
*/
public double similarityDegree (FirstOrderTerm lhs, FirstOrderTerm rhs)
{
sayIfTracing(2,
tracingIndentMargin+"computing similarity degree of "+lhs+" and "+rhs);
if (lhs == rhs)
{
sayIfTracing(2,
tracingIndentMargin+"results in 1.0");
return 1.0;
}
if (lhs != rhs && (lhs.isVariable() || rhs.isVariable()))
{
sayIfTracing(2,
tracingIndentMargin+"results in 0.0");
return 0.0;
}
// so both must be structures:
FirstOrderTermStructure L = (FirstOrderTermStructure)lhs;
FirstOrderTermStructure R = (FirstOrderTermStructure)rhs;
double degree = similarityDegree(L.functor(),R.functor());
int minArity = Math.min(L.functor().arity(),R.functor().arity());
// System.err.println("&&& min arity of "+
// L.functor()+"/"+L.functor().arity()+
// " and "+
// R.functor()+"/"+R.functor().arity()+
// " is: "+minArity);
// if (L.arguments() != null)
// {
// System.err.print("&&& "+L.functor()+" has "+L.arguments().length+" arguments:");
// for (int k=0; k 0.0 && i <= minArity)
{
degree = inf(degree,
similarityDegree(L.argument(i),
R.argument(i)));
i++;
}
sayIfTracing(2,
tracingIndentMargin+"results in "+degree);
return degree;
}
/* ************************************************************************ */
/**
* LATTICE OPERATIONS
*/
/**
* These are generic implementations for fuzzy unification and
* generalization of first-order terms using parameterized
* argument-position mappings when dealing with similar functors. The
* default argument-position mapping from any functor to another is
* the identity on {1,...,n}, where n is the least
* of the two functors' arities.
*/
/**
* This is the default argument-position mapping (the identity) from
* Functor from to Functor to at
* approximation degree for position.
*/
int positionMapping (Functor from, Functor to, double degree, int position)
{
return position;
}
/**
*
* Fuzzy Unification
*/
/**
* Fuzzy unify the given pair of first-order terms modulo this
* similarity and return their similarity degree, which will be
* greater than 0 iff these terms are fuzzy unifiable. This
* will possibly bind variables that occur in either term.
*/
public double unify (FirstOrderTerm lhs, FirstOrderTerm rhs)
{
unifyStack.clear();
unifyStack.push(lhs);
unifyStack.push(rhs);
double degree = 1.0;
while (degree > 0.0 && !unifyStack.isEmpty())
{
lhs = (FirstOrderTerm)unifyStack.pop();
rhs = (FirstOrderTerm)unifyStack.pop();
if (lhs.isVariable())
lhs = ((Variable)lhs).deref();
if (rhs.isVariable())
rhs = ((Variable)rhs).deref();
if (lhs == rhs)
continue;
if (lhs.isVariable())
{
Variable V = ((Variable)lhs);
if (V.occursIn(rhs))
degree = 0.0;
else
V.bind(rhs);
continue;
}
if (rhs.isVariable())
{
Variable V = ((Variable)rhs);
if (V.occursIn(lhs))
degree = 0.0;
else
V.bind(lhs);
continue;
}
// both are structures:
FirstOrderTermStructure L = (FirstOrderTermStructure)lhs;
FirstOrderTermStructure R = (FirstOrderTermStructure)rhs;
degree = inf(degree,
similarityDegree(L.functor(),R.functor()));
if (degree > 0.0)
{
int minArity = Math.min(L.functor().arity(),R.functor().arity());
for (int i=1; i <= minArity; i++)
{
int j = positionMapping(L.functor(),R.functor(),degree,i);
unifyStack.push(L.argument(i));
unifyStack.push(R.argument(j));
}
}
}
return degree;
}
// Unification accessories
/**
* Unification stack.
*/
static Stack unifyStack = new Stack();
/* ************************************************************************ */
/**
*
* Fuzzy Generalization
*/
/**
* Given a pair of terms lhs and rhs and a prior
* approximation degree degree, this returns a fuzzy term
* made of the term generalizing the pair, and the maximal
* approximation degree at which it generalizes them.
*/
public FuzzyFirstOrderTerm generalize (FirstOrderTerm lhs, FirstOrderTerm rhs, double degree)
{
// Fuzzy Equal Variables
if (lhs.isVariable() && lhs == rhs)
return new FuzzyFirstOrderTerm(lhs,degree);
// Fuzzy Variable-Term:
if ((lhs.isVariable() || rhs.isVariable()) && !lhs.equal(rhs))
{
Variable newVariable = Variable.anonymousVariable();
lSubstitution.put(newVariable,lhs);
rSubstitution.put(newVariable,rhs);
generatedVariables.add(newVariable);
return new FuzzyFirstOrderTerm(newVariable,degree);
}
// So both terms are structures:
FirstOrderTermStructure L = (FirstOrderTermStructure)lhs;
FirstOrderTermStructure R = (FirstOrderTermStructure)rhs;
// For dissimilar functors, introduce a new generalization variable
// and extend the left and right substitutions.
// Dissimilar Functors:
if (similarityDegree(L.functor(),R.functor()) == 0.0)
{
Variable newVariable = Variable.anonymousVariable();
lSubstitution.put(newVariable,lhs);
rSubstitution.put(newVariable,rhs);
generatedVariables.add(newVariable);
return new FuzzyFirstOrderTerm(newVariable,degree);
}
// For similar functors, proceed recursively by generalizing each
// pair of arguments having corresponding positions in each term,
// and simultaneously build up the left and right generalizing
// substitutions as needed along with refining the generalizing
// degree as required.
// Similar Functors:
Functor F = L.functor();
Functor G = R.functor();
int M = F.arity();
int N = G.arity();
// generalize only common-position arguments
int genArity = Math.min(M,N);
// the functor retained for the generalization is the one with
// least-arity
Functor genFunctor = M <= N ? F : G;
double functorsSimilarity = similarityDegree(F,G);
sayIfTracing(1,
"generalizing lhs term "+L+" and rhs term "+R+" at degree "+degree);
// initialize the generalization degree to the infimum of the prior
// one and the functors' similarity degree
double genDegree = inf(degree,functorsSimilarity);
if (functorsSimilarity < degree)
sayIfTracing(1,
"since "+F+" ~ "+G+" ["+functorsSimilarity+"]"+
" the new generalization degree is now "+genDegree);
if (genArity == 0)
// there are no arguments to generalize: we're done!
return new FuzzyFirstOrderTerm(new FirstOrderTermStructure(genFunctor),
genDegree);
// there are arguments to generalize:
// first build an argumentless generalized term structure:
FirstOrderTermStructure genStructure
= new FirstOrderTermStructure(genFunctor,
new FirstOrderTerm[genArity]);
increaseTracingMargin(" of a term with functor "+genFunctor+"/"+genFunctor.arity());
// then build each generalized argument:
for (int i = 1; i <= genArity; i++)
{
sayIfTracing(2,
"argument "+i);
int j = positionMapping(L.functor(),R.functor(),genDegree,i);
// we first compute the fuzzy-unapplied pair:
FuzzyFirstOrderTermPair unappliedPair = unapply(L.argument(i),
R.argument(j),
genDegree);
// we next fuzzy-generalize the unapplied arguments at the unapplied degree:
FuzzyFirstOrderTerm fuzzyGenArg = generalize(unappliedPair.left(),
unappliedPair.right(),
unappliedPair.degree());
// we finally set the ith argument to the generalized argument:
genStructure.setArgument(i,fuzzyGenArg.term());
// and update the generalization degree to the one resulting from generalizing the ith arguments:
genDegree = fuzzyGenArg.degree();
}
decreaseTracingMargin((" of "+genStructure));
// return the fuzzy-generalized structure and ultimate generalization degree:
return new FuzzyFirstOrderTerm(genStructure,genDegree);
}
// Generalization accessories
/**
* The generated generalizing variables.
*/
public static ArrayList generatedVariables = new ArrayList();
/**
* The substitution mapping generated variables to the subterms of the
* generalized lhs.
*/
public static HashMap lSubstitution = new HashMap();
/**
* The substitution mapping generated variables to the subterms of the
* generalized rhs.
*/
public static HashMap rSubstitution = new HashMap();
/**
* Clears all substitutions and generated variables.
*/
public static void resetGeneralizer ()
{
generatedVariables.clear();
lSubstitution.clear();
rSubstitution.clear();
}
/**
* Unapply the current left and right fuzzy-generalizing substitutions
* to the specified terms at the specified approximation degree, and
* return the resulting pair of terms and approximation degree as a
* FuzzyFirstOrderTermPair.
*/
private FuzzyFirstOrderTermPair unapply (FirstOrderTerm lhs, FirstOrderTerm rhs, double degree)
{
Variable V;
FirstOrderTerm L;
FirstOrderTerm R;
sayIfTracing(2,
"unapplying left substitution "+lSubstitution+
" and right substitution " +rSubstitution+
" to lhs term "+lhs+" and rhs term "+rhs+" at degree "+degree);
for (int i = 0; i < generatedVariables.size(); i++)
{
double unapplyDegree = degree;
V = (Variable)generatedVariables.get(i);
L = (FirstOrderTerm)lSubstitution.get(V);
R = (FirstOrderTerm)rSubstitution.get(V);
double lhsDegree = similarityDegree(lhs,L);
sayIfTracing(2,
"the lhs argument "+i+"'s unapplied variable "+V+
" gives term: "+L+" resulting in degree "+lhsDegree);
double rhsDegree = similarityDegree(rhs,R);
sayIfTracing(2,
"the rhs argument "+i+"'s unapplied variable "+V+
" gives term: "+R+" resulting in degree "+rhsDegree);
unapplyDegree = inf(unapplyDegree,
inf(lhsDegree,
rhsDegree));
sayIfTracing(2,
"so the resulting unapplication degree is "+unapplyDegree);
if (unapplyDegree > 0.0)
{
FuzzyFirstOrderTermPair fuzzyTermPair = new FuzzyFirstOrderTermPair(V,V,unapplyDegree);
sayIfTracing(2,
"therefore the final unapplied fuzzy pair is "+fuzzyTermPair);
return fuzzyTermPair;
}
}
FuzzyFirstOrderTermPair fuzzyTermPair = new FuzzyFirstOrderTermPair(lhs,rhs,degree);
sayIfTracing(2,
"there is no similar unapplication for "+lhs+" and "+rhs+" at degree "+degree);
sayIfTracing(2,
"the final unapplied fuzzy pair is the original unchanged "+fuzzyTermPair);
return fuzzyTermPair;
}
// /* ************************************************************************ */
// /**
// * DISPLAY
// */
// /**
// * Prints this SimilaritySignature to standard output at the
// * default precision FuzzyMatrix.precision.
// */
// public void show ()
// {
// show(FuzzyMatrix.precision);
// }
// /**
// * Prints this SimilaritySignature to standard output at the
// * specified precision. NB: this works nicely only for
// * one-letter functor names and one-digit arities. This is just a
// * quick-and-dirty method for now since to print a matrix with
// * correctly lined up entries for headers that could be any
// * String/int functor/arity, the precision width should
// * depend on the max-width of the functor/arity.
// */
// public void show (String precision)
// {
// FuzzyMatrix.precision = precision;
// System.out.print(" ");
// for (int i = 1; i <= rank(); i++)
// System.out.print(functor(i)+"/"+functor(i).arity()+" ");
// System.out.println();
// System.out.print(" ");
// for (int i = 1; i <= rank(); i++)
// System.out.print("--- ");
// System.out.println();
// for (int i = 1; i <= rank(); i++)
// {
// System.out.print(functor(i).name()+" | ");
// for (int j = 1; j <= rank(); j++)
// System.out.printf(precision, data[i-1][j-1]);
// System.out.println("\n");
// }
// }
/* ************************************************************************ */
/**
* TRACING
*/
/**
* Default tracing indentation.
*/
private static int tracingIndent = 3;
/**
* Sets the current value of the tracing indentation to
* indent blank spaces.
*/
public static void setTracingIndent (int indentValue)
{
tracingIndent = indentValue;
}
/**
* Default tracing indentation margin.
*/
private static String tracingIndentMargin = "";
/**
* Increase the current tracing indentation margin.
*/
public static void increaseTracingMargin (String msg)
{
sayIfTracing("process the arguments"+msg);
for (int i = 0; i < tracingIndent; i++)
tracingIndentMargin = tracingIndentMargin+" ";
}
/**
* Decrease the current tracing indentation margin.
*/
public static void decreaseTracingMargin (String msg)
{
if (tracingIndentMargin.length() > 0)
tracingIndentMargin = tracingIndentMargin.substring(0,tracingIndentMargin.length()-tracingIndent);
sayIfTracing("finished processsing the arguments"+msg);
}
/**
* Tracing flag.
*/
private static boolean tracing = false;
/**
* If already tracing, this disables it; otherwise, it enables it.
*/
public static void toggleTracing (int verbosityLevel)
{
setTracingVerbosity(verbosityLevel);
tracing = verbosityLevel == 0 ? false : true;
System.err.println("@@@ tracing in now turned "+
(tracing?("ON at level "+verbosityLevel):"OFF"));
}
/**
* The maximum level of tracing detail verbosity.
*/
final private static int maxTracingVerbosity = 3;
/**
* The current level of tracing detail verbosity.
*/
private static int tracingVerbosity = 0;
/**
* Set the current level of tracing detail verbosity.
*/
public static void setTracingVerbosity (int verbosityLevel)
{
tracingVerbosity = Math.max(0,Math.min(verbosityLevel,
maxTracingVerbosity));
}
/**
* If tracing, report message on a new line indented by the
* current tracing indentation margin on the error output stream
* giving details at the current level of tracing verbosity.
*/
public static void sayIfTracing (String message)
{
sayIfTracing(tracingVerbosity,message);
}
/**
* If tracing, report message on a new line indented by the
* current tracing indentation margin on the error output stream at
* the specified level of tracing verbosity.
*/
public static void sayIfTracing (int verbosity, String message)
{
if (tracing && verbosity >= tracingVerbosity)
System.err.println("@@@ "+tracingIndentMargin+message);
}
}