Menu
▾
▴
[Jason-developers] SF.net SVN: jason:[1674] trunk/src
|
From: <jom...@us...> - 2012-03-01 18:16:41
|
Revision: 1674
http://jason.svn.sourceforge.net/jason/?rev=1674&view=rev
Author: jomifred
Date: 2012-03-01 18:16:35 +0000 (Thu, 01 Mar 2012)
Log Message:
-----------
initial implementation of cyclic terms
Modified Paths:
--------------
trunk/src/jason/asSemantics/Unifier.java
trunk/src/jason/asSyntax/DefaultTerm.java
trunk/src/jason/asSyntax/Pred.java
trunk/src/jason/asSyntax/Rule.java
trunk/src/jason/asSyntax/Structure.java
trunk/src/jason/asSyntax/Term.java
trunk/src/jason/asSyntax/VarTerm.java
trunk/src/test/ListTermTest.java
trunk/src/test/RuleTest.java
trunk/src/test/TermTest.java
trunk/src/test/VarTermTest.java
trunk/src/xml/agInspection.xsl
Added Paths:
-----------
trunk/src/jason/asSyntax/CyclicTerm.java
Modified: trunk/src/jason/asSemantics/Unifier.java
===================================================================
--- trunk/src/jason/asSemantics/Unifier.java 2011-12-15 22:15:25 UTC (rev 1673)
+++ trunk/src/jason/asSemantics/Unifier.java 2012-03-01 18:16:35 UTC (rev 1674)
@@ -24,6 +24,7 @@
package jason.asSemantics;
import jason.asSyntax.ASSyntax;
+import jason.asSyntax.CyclicTerm;
import jason.asSyntax.ListTerm;
import jason.asSyntax.ListTermImpl;
import jason.asSyntax.Literal;
@@ -69,6 +70,10 @@
return get(new VarTerm(var));
}
+ public Term remove(VarTerm v) {
+ return function.remove(v);
+ }
+
/**
* gets the value for a Var, if it is unified with another var, gets this
* other's value
@@ -132,6 +137,11 @@
}
}
+ if (t1g.isCyclicTerm()) // reintroduce cycles in the unifier
+ bind(t1g.getCyclicVar(), t1g);
+ if (t2g.isCyclicTerm())
+ bind(t2g.getCyclicVar(), t2g);
+
// unify as Term
boolean ok = unifyTerms(t1g, t2g);
@@ -161,6 +171,12 @@
}
}
}
+
+ /*if (t1g.isCyclicTerm())
+ remove(t1g.getCyclicVar());
+ if (t2g.isCyclicTerm())
+ remove(t2g.getCyclicVar());
+ */
return ok;
}
@@ -274,7 +290,7 @@
} // if they are the same (comp == 0), do not bind
}
- private void bind(VarTerm vt, Term vl) {
+ public void bind(VarTerm vt, Term vl) {
function.put((VarTerm) vt.clone(), vl);
}
@@ -305,8 +321,15 @@
/** add all unifications from u */
public void compose(Unifier u) {
- for (VarTerm k: u.function.keySet())
- function.put( (VarTerm)k.clone(), u.function.get(k).clone());
+ for (VarTerm k: u.function.keySet()) {
+ Term current = get(k);
+ Term kValue = u.function.get(k);
+ if (current != null && (current.isVar() || kValue.isVar())) { // current unifier has the new var
+ unifies(kValue, current);
+ } else {
+ function.put( (VarTerm)k.clone(), kValue.clone());
+ }
+ }
}
@SuppressWarnings("unchecked")
Added: trunk/src/jason/asSyntax/CyclicTerm.java
===================================================================
--- trunk/src/jason/asSyntax/CyclicTerm.java (rev 0)
+++ trunk/src/jason/asSyntax/CyclicTerm.java 2012-03-01 18:16:35 UTC (rev 1674)
@@ -0,0 +1,106 @@
+// ----------------------------------------------------------------------------
+// Copyright (C) 2003 Rafael H. Bordini, Jomi F. Hubner, et al.
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Lesser General Public
+// License as published by the Free Software Foundation; either
+// version 2.1 of the License, or (at your option) any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Lesser General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public
+// License along with this library; if not, write to the Free Software
+// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+//
+// To contact the authors:
+// http://www.inf.ufrgs.br/~bordini
+// http://www.das.ufsc.br/~jomi
+//
+//----------------------------------------------------------------------------
+
+package jason.asSyntax;
+
+import org.w3c.dom.Document;
+import org.w3c.dom.Element;
+
+import jason.asSemantics.Unifier;
+
+
+
+/**
+ * A term with recursion (cyclic), created by code like X = f(X).
+ */
+public class CyclicTerm extends LiteralImpl {
+
+ private static final long serialVersionUID = 1L;
+
+ private VarTerm cyclicVar = null;
+
+ /** creates a positive literal */
+ public CyclicTerm(Literal t, VarTerm v) {
+ super(t);
+ cyclicVar = v;
+ }
+
+ public VarTerm getCyclicVar() {
+ return cyclicVar;
+ }
+
+ @Override
+ public boolean isCyclicTerm() {
+ return true;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (o == null) return false;
+ if (o == this) return true;
+
+ if (o instanceof CyclicTerm) {
+ final CyclicTerm l = (CyclicTerm) o;
+ return super.equals(l);
+ }
+ return false;
+ }
+
+ @Override
+ public Literal makeVarsAnnon(Unifier u) {
+ super.makeVarsAnnon(u);
+ VarTerm v = u.deref(cyclicVar);
+ if (v != null)
+ cyclicVar = v;
+ return this;
+ }
+
+ @Override
+ public boolean apply(Unifier u) {
+ Term v = u.remove(cyclicVar);
+ boolean b = super.apply(u);
+ if (v != null)
+ u.bind(cyclicVar, v);
+ return b;
+ }
+
+ public Term clone() {
+ return new CyclicTerm(this, (VarTerm)cyclicVar.copy());
+ }
+
+ @Override
+ protected int calcHashCode() {
+ return super.calcHashCode() + cyclicVar.calcHashCode();
+ }
+
+ public String toString() {
+ return "..."+super.toString()+"/"+cyclicVar;
+ }
+
+ @Override
+ public Element getAsDOM(Document document) {
+ Element u = super.getAsDOM(document);
+ u.setAttribute("cyclic-var", cyclicVar.toString());
+ return u;
+ }
+}
Modified: trunk/src/jason/asSyntax/DefaultTerm.java
===================================================================
--- trunk/src/jason/asSyntax/DefaultTerm.java 2011-12-15 22:15:25 UTC (rev 1673)
+++ trunk/src/jason/asSyntax/DefaultTerm.java 2012-03-01 18:16:35 UTC (rev 1674)
@@ -76,7 +76,10 @@
public boolean isAtom() { return false; }
public boolean isPlanBody() { return false; }
public boolean isGround() { return true; }
- public boolean hasVar(VarTerm t) { return false; }
+ public boolean isCyclicTerm() { return false; }
+ public VarTerm getCyclicVar() { return null; }
+
+ public boolean hasVar(VarTerm t, Unifier u) { return false; }
public void countVars(Map<VarTerm, Integer> c) {}
Modified: trunk/src/jason/asSyntax/Pred.java
===================================================================
--- trunk/src/jason/asSyntax/Pred.java 2011-12-15 22:15:25 UTC (rev 1673)
+++ trunk/src/jason/asSyntax/Pred.java 2012-03-01 18:16:35 UTC (rev 1674)
@@ -217,12 +217,12 @@
}
@Override
- public boolean hasVar(VarTerm t) {
- if (super.hasVar(t))
+ public boolean hasVar(VarTerm t, Unifier u) {
+ if (super.hasVar(t, u))
return true;
if (annots != null)
for (Term v: annots)
- if (v.hasVar(t))
+ if (v.hasVar(t, u))
return true;
return false;
}
Modified: trunk/src/jason/asSyntax/Rule.java
===================================================================
--- trunk/src/jason/asSyntax/Rule.java 2011-12-15 22:15:25 UTC (rev 1673)
+++ trunk/src/jason/asSyntax/Rule.java 2012-03-01 18:16:35 UTC (rev 1674)
@@ -102,9 +102,9 @@
}
@Override
- public boolean hasVar(VarTerm t) {
- if (super.hasVar(t)) return true;
- return body.hasVar(t);
+ public boolean hasVar(VarTerm t, Unifier u) {
+ if (super.hasVar(t, u)) return true;
+ return body.hasVar(t, u);
}
public void countVars(Map<VarTerm, Integer> c) {
Modified: trunk/src/jason/asSyntax/Structure.java
===================================================================
--- trunk/src/jason/asSyntax/Structure.java 2011-12-15 22:15:25 UTC (rev 1673)
+++ trunk/src/jason/asSyntax/Structure.java 2012-03-01 18:16:35 UTC (rev 1674)
@@ -344,10 +344,10 @@
}
@Override
- public boolean hasVar(VarTerm t) {
+ public boolean hasVar(VarTerm t, Unifier u) {
final int size = getArity();
for (int i=0; i<size; i++)
- if (getTerm(i).hasVar(t))
+ if (getTerm(i).hasVar(t, u))
return true;
return false;
}
Modified: trunk/src/jason/asSyntax/Term.java
===================================================================
--- trunk/src/jason/asSyntax/Term.java 2011-12-15 22:15:25 UTC (rev 1673)
+++ trunk/src/jason/asSyntax/Term.java 2012-03-01 18:16:35 UTC (rev 1674)
@@ -27,8 +27,11 @@
public boolean isStructure();
public boolean isAtom();
public boolean isPlanBody();
+ public boolean isCyclicTerm();
- public boolean hasVar(VarTerm t);
+ public boolean hasVar(VarTerm t, Unifier u);
+ public VarTerm getCyclicVar();
+
public void countVars(Map<VarTerm, Integer> c);
public Term clone();
Modified: trunk/src/jason/asSyntax/VarTerm.java
===================================================================
--- trunk/src/jason/asSyntax/VarTerm.java 2011-12-15 22:15:25 UTC (rev 1673)
+++ trunk/src/jason/asSyntax/VarTerm.java 2012-03-01 18:16:35 UTC (rev 1674)
@@ -150,15 +150,25 @@
if (value == null) {
Term vl = u.get(this);
//System.out.println("applying "+this+"="+vl+" un="+u);
- if (vl != null) { // && !(vl instanceof VarsCluster)) {
- if (!vl.hasVar(this)) {
- setValue(vl);
- value.apply(u); // in case t has var args
- return true;
- } else {
- logger.warning("Value of variable contains itself, variable "+super.getFunctor()+" "+super.getSrcInfo()+", value="+value);
- return false;
+ if (vl != null) {
+ if (vl.hasVar(this, u)) {
+ //logger.warning("The value of a variable contains itself, variable "+super.getFunctor()+" "+super.getSrcInfo()+", value="+vl+", unifier="+u);
+
+ u.remove(this); // remove this var to avoid loops
+ Term tempVl = vl.clone();
+ tempVl.apply(u);
+ u.bind(this, vl);
+
+ CyclicTerm ct = new CyclicTerm((Literal)tempVl, this);
+ Unifier renamedVars = new Unifier(); // remove "this" from the value to avoid loops in apply
+ ct.makeVarsAnnon(renamedVars);
+ renamedVars.remove(this);
+ u.compose(renamedVars);
+ vl = ct;
}
+ setValue(vl);
+ value.apply(u); // in case t has var args
+ return true;
}
} else {
return getValue().apply(u);
@@ -398,14 +408,42 @@
}
@Override
- public boolean hasVar(VarTerm t) {
- if (value == null)
- return equals(t);
+ public boolean isCyclicTerm() {
+ return value != null && value.isCyclicTerm();
+ }
+
+ @Override
+ public VarTerm getCyclicVar() {
+ if (value != null)
+ return value.getCyclicVar();
else
- return value.hasVar(t);
+ return super.getCyclicVar();
}
@Override
+ public boolean hasVar(VarTerm t, Unifier u) {
+ if (value != null)
+ return value.hasVar(t, u);
+ if (equals(t))
+ return true;
+
+ if (u != null) { // if the var has a value in the unifier, search in that value
+ Term vl = u.get(this);
+ if (vl != null) {
+ try {
+ u.remove(this); // remove this var from the unifier to avoid going to seach inside it again
+ return vl.hasVar(t, u);
+ } finally {
+ u.bind(this, vl);
+ }
+ }
+
+ }
+
+ return false;
+ }
+
+ @Override
public void countVars(Map<VarTerm, Integer> c) {
if (value == null) {
int n = c.containsKey(this) ? c.get(this) : 0;
Modified: trunk/src/test/ListTermTest.java
===================================================================
--- trunk/src/test/ListTermTest.java 2011-12-15 22:15:25 UTC (rev 1673)
+++ trunk/src/test/ListTermTest.java 2012-03-01 18:16:35 UTC (rev 1674)
@@ -185,12 +185,15 @@
VarTerm l6 = new VarTerm("L6");
u.unifies(l5, l6);
l6.apply(u);
+ assertEquals(l6.toString(), "[c,b,a,x,y]");
l6.concat(ListTermImpl.parseList("[d]"));
+ assertEquals(l6.toString(), "[c,b,a,x,y,d]");
ListTerm lf = ListTermImpl.parseList("[c,b,a,x,y,d]");
assertTrue(u.unifies(l6,lf));
lf = ListTermImpl.parseList("[c,b,a,x,y]");
+ l5.apply(u);
assertTrue(u.unifies(l5,lf));
ListTerm ll = lf.cloneLT();
Modified: trunk/src/test/RuleTest.java
===================================================================
--- trunk/src/test/RuleTest.java 2011-12-15 22:15:25 UTC (rev 1673)
+++ trunk/src/test/RuleTest.java 2012-03-01 18:16:35 UTC (rev 1674)
@@ -138,9 +138,9 @@
assertEquals(1, r.getSingletonVars().size());
assertEquals("[R]", r.getSingletonVars().toString());
- assertTrue(r.hasVar(new VarTerm("X")));
- assertTrue(r.hasVar(new VarTerm("W")));
- assertFalse(r.hasVar(new VarTerm("III")));
+ assertTrue(r.hasVar(new VarTerm("X"), null));
+ assertTrue(r.hasVar(new VarTerm("W"), null));
+ assertFalse(r.hasVar(new VarTerm("III"), null));
}
Modified: trunk/src/test/TermTest.java
===================================================================
--- trunk/src/test/TermTest.java 2011-12-15 22:15:25 UTC (rev 1673)
+++ trunk/src/test/TermTest.java 2012-03-01 18:16:35 UTC (rev 1674)
@@ -872,10 +872,20 @@
public void testHasVar() throws ParseException {
Literal l = parseLiteral("a(Test,X,Y,b(g([V1,X,V2,V1]),c))[b,source(Y),B,kk(_),oo(oo(OO))]");
- assertTrue(l.hasVar(new VarTerm("X")));
- assertTrue(l.hasVar(new VarTerm("V2")));
- assertTrue(l.hasVar(new VarTerm("OO")));
- assertFalse(l.hasVar(new VarTerm("O")));
+ assertTrue(l.hasVar(new VarTerm("X"), null));
+ assertTrue(l.hasVar(new VarTerm("V2"), null));
+ assertTrue(l.hasVar(new VarTerm("OO"), null));
+ assertFalse(l.hasVar(new VarTerm("O"), null));
+
+ Unifier u = new Unifier();
+ u.unifies(parseTerm("X"), parseTerm("f(Y)"));
+ u.unifies(parseTerm("Y"), parseTerm("g(X)"));
+ u.unifies(parseTerm("T"), parseTerm("X"));
+ VarTerm t = new VarTerm("T");
+ assertFalse(t.hasVar(new VarTerm("X"), null));
+ assertTrue(t.hasVar(new VarTerm("X"), u));
+ assertFalse(t.hasVar(new VarTerm("Y"), null));
+ assertTrue(t.hasVar(new VarTerm("Y"), u));
}
public void testSingletonVars() {
@@ -974,4 +984,85 @@
assertTrue(variable.equals(term));
assertTrue(variable.equals(new ObjectTermImpl("test")));
}
+
+ public void testCyclicTerm1() throws ParseException {
+ Term t1 = parseTerm("f(f(g(X)))");
+ Term v1 = new VarTerm("X");
+ Unifier u = new Unifier();
+
+ assertTrue(u.unifies(t1, v1));
+
+ assertTrue(u.unifies(v1, parseTerm("f(f(g(f(f(g(_))))))")));
+ assertTrue(u.unifies(v1, parseTerm("f(f(g(f(f(g(f(f(g(_)))))))))")));
+ assertFalse(u.unifies(v1, parseTerm("f(f(g(f(f(g(f(g(_))))))))")));
+ assertFalse(u.unifies(v1, parseTerm("f(f(g(f(f(p(_))))))")));
+
+ assertTrue(v1.apply(u));
+ assertTrue(new Unifier().unifies(v1, parseTerm("f(f(g(f(f(g(_))))))")));
+ assertTrue(new Unifier().unifies(v1, parseTerm("f(f(g(f(f(g(f(f(g(_)))))))))")));
+ assertTrue(new Unifier().unifies(v1, parseTerm("f(f(g(f(f(g(f(f(_))))))))")));
+ assertFalse(new Unifier().unifies(v1, parseTerm("f(f(g(f(f(g(f(g(_))))))))")));
+ assertFalse(new Unifier().unifies(v1, parseTerm("f(_,_)")));
+ assertFalse(new Unifier().unifies(v1, parseTerm("f(f(g(f(f(p(K))))))")));
+
+ u = new Unifier();
+ assertTrue(u.unifies(v1, parseTerm("f(f(g(f(f(g(K))))))")));
+ assertTrue(u.get("K").isCyclicTerm());
+ VarTerm k = new VarTerm("K");
+ k.apply(u);
+ assertTrue(k.isCyclicTerm());
+
+ u = new Unifier();
+ assertTrue(u.unifies(v1, parseTerm("f(f(g(f(f(H)))))")));
+ VarTerm h = new VarTerm("H");
+ h.apply(u);
+ assertTrue(h.getTerm(0).isCyclicTerm());
+ }
+
+ public void testCyclicTerm2() throws ParseException {
+ Term t1 = parseTerm("f(f(g(X,H)))");
+ VarTerm v1 = new VarTerm("X");
+ Unifier u = new Unifier();
+
+ assertTrue(u.unifies(t1, v1));
+ assertTrue(u.unifies(v1, parseTerm("f(f(g(_,_)))")));
+ assertTrue(u.unifies(v1, parseTerm("f(f(g(f(f(g(_,_))),_)))")));
+
+ assertTrue(u.unifies(new VarTerm("H"), parseTerm("100")));
+ assertTrue(v1.apply(u));
+ assertTrue(v1.toString().indexOf("100") > 0);
+ }
+
+ public void testCyclicTerm3() throws ParseException {
+ Unifier u = new Unifier();
+
+ assertTrue(u.unifies(new VarTerm("Merge"), parseTerm("choice([Off,Fork])")));
+ assertTrue(u.unifies(new VarTerm("Off"), parseTerm("seq(tell(b,c,offer),seq(tell(c,b,counter),Merge))")));
+ assertTrue(u.unifies(new VarTerm("Fork"), parseTerm("fork(seq(tell(b,s,final),end),seq(tell(b,c,result),end))")));
+ assertTrue(u.unifies(new VarTerm("Glob"), parseTerm("seq(tell(s,b,item),Merge)")));
+
+ //assertTrue(u.unifies(new VarTerm("X"), parseTerm("f(Y)")));
+ //assertTrue(u.unifies(new VarTerm("Y"), parseTerm("g(X)")));
+
+ //System.out.println(u);
+ VarTerm m = new VarTerm("Glob");
+ m.apply(u);
+ assertTrue(m.getTerm(1).isCyclicTerm());
+ }
+
+ public void testCyclicTerm4() throws ParseException {
+ Unifier u = new Unifier();
+
+ assertTrue(u.unifies(new VarTerm("X"), parseTerm("f(Y)")));
+ assertTrue(u.unifies(new VarTerm("Y"), parseTerm("g(X)")));
+
+ //System.out.println(u);
+ VarTerm x = new VarTerm("X");
+ x.apply(u);
+ assertTrue(x.isCyclicTerm());
+ VarTerm y = new VarTerm("Y");
+ y.apply(u);
+ assertTrue(y.isCyclicTerm());
+ }
+
}
Modified: trunk/src/test/VarTermTest.java
===================================================================
--- trunk/src/test/VarTermTest.java 2011-12-15 22:15:25 UTC (rev 1673)
+++ trunk/src/test/VarTermTest.java 2012-03-01 18:16:35 UTC (rev 1674)
@@ -97,7 +97,7 @@
u.unifies(v1, lt); // L = [a,B,a(B)]
v1.apply(u);
ListTerm vlt = (ListTerm) v1.getValue();
- assertFalse(vlt.equals(lt)); // the apply in var should not change the orginal list
+ assertFalse(vlt.equals(lt)); // the apply in var should not change the original list
Iterator<Term> i = vlt.iterator();
i.next();
i.next();
Modified: trunk/src/xml/agInspection.xsl
===================================================================
--- trunk/src/xml/agInspection.xsl 2011-12-15 22:15:25 UTC (rev 1673)
+++ trunk/src/xml/agInspection.xsl 2012-03-01 18:16:35 UTC (rev 1674)
@@ -525,6 +525,9 @@
<xsl:if test="@negated = 'true'">
<b><xsl:text>~</xsl:text></b>
</xsl:if>
+ <xsl:if test="count(@cyclic-var) > 0">
+ <b><xsl:text>...</xsl:text></b>
+ </xsl:if>
<xsl:apply-templates />
</xsl:template>
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
