Menu
▾
▴
[Jason-developers] SF.net SVN: jason:[1756] trunk
|
From: <jom...@us...> - 2013-11-04 11:27:53
|
Revision: 1756
http://sourceforge.net/p/jason/svn/1756
Author: jomifred
Date: 2013-11-04 11:27:47 +0000 (Mon, 04 Nov 2013)
Log Message:
-----------
initial implementation of tail recursion optimisation
Modified Paths:
--------------
trunk/applications/as-unit-test/src/jason/tests/BugListReturnUnification.java
trunk/applications/as-unit-test/src/jason/tests/TestAll.java
trunk/release-notes.txt
trunk/src/jason/asSemantics/Intention.java
trunk/src/jason/asSemantics/TransitionSystem.java
trunk/src/jason/asSemantics/Unifier.java
trunk/src/jason/runtime/Settings.java
Added Paths:
-----------
trunk/applications/as-unit-test/src/jason/tests/TestTRO.java
Modified: trunk/applications/as-unit-test/src/jason/tests/BugListReturnUnification.java
===================================================================
--- trunk/applications/as-unit-test/src/jason/tests/BugListReturnUnification.java 2013-10-31 20:20:03 UTC (rev 1755)
+++ trunk/applications/as-unit-test/src/jason/tests/BugListReturnUnification.java 2013-11-04 11:27:47 UTC (rev 1756)
@@ -28,8 +28,8 @@
"+!a(Y)[x(Z),kk] <- Y=3; Z=4. "+
"+!a(Y)[x(Z),source(self)] <- Y=1; Z=2. "+
- "+!test4 <- X = [a,b,c]; !deleteb(X,Y); jason.asunit.print(Y)."+
- "+!test5 <- X = [a,b,c]; !deleteb2(X,Y); jason.asunit.print(Y)."+
+ "+!test4 <- X = [a,b,c,b,b,d]; !deleteb(X,Y); jason.asunit.print(Y)."+
+ "+!test5 <- X = [a,b,c,b,b,d]; !deleteb2(X,Y); jason.asunit.print(Y)."+
"+!deleteb([], [])."+
"+!deleteb([b|L1], L2)"+
@@ -64,12 +64,12 @@
@Test(timeout=2000)
public void testDelete1() {
ag.addGoal("test4");
- ag.assertPrint("[a,c]", 10);
+ ag.assertPrint("[a,c,d]", 10);
}
@Test(timeout=2000)
public void testDelete2() {
ag.addGoal("test5");
- ag.assertPrint("[a,c]", 10);
+ ag.assertPrint("[a,c,d]", 20);
}
}
Modified: trunk/applications/as-unit-test/src/jason/tests/TestAll.java
===================================================================
--- trunk/applications/as-unit-test/src/jason/tests/TestAll.java 2013-10-31 20:20:03 UTC (rev 1755)
+++ trunk/applications/as-unit-test/src/jason/tests/TestAll.java 2013-11-04 11:27:47 UTC (rev 1756)
@@ -26,6 +26,7 @@
TestVarInContext.class,
TestUnnamedVar.class,
TestCopyTerm.class,
- TestNegatedVar.class
+ TestNegatedVar.class,
+ TestTRO.class
})
public class TestAll { }
Added: trunk/applications/as-unit-test/src/jason/tests/TestTRO.java
===================================================================
--- trunk/applications/as-unit-test/src/jason/tests/TestTRO.java (rev 0)
+++ trunk/applications/as-unit-test/src/jason/tests/TestTRO.java 2013-11-04 11:27:47 UTC (rev 1756)
@@ -0,0 +1,31 @@
+package jason.tests;
+
+import jason.asunit.TestAgent;
+
+import org.junit.Before;
+import org.junit.Test;
+
+// test Tail Recursion Optimization
+public class TestTRO {
+
+ TestAgent ag;
+
+ // initialisation of the agent test
+ @Before
+ public void setupAg() {
+ ag = new TestAgent();
+
+ // defines the agent's AgentSpeak code
+ ag.parseAScode(
+ "+!run <- !fat(5,1,F); jason.asunit.print(F). "+
+ "+!fat(1,V,V). "+
+ "+!fat(N,A,X) <- !fat(N-1,N*A,X)."
+ );
+ }
+
+ @Test(timeout=2000)
+ public void testGoalSrouce() {
+ ag.addGoal("run");
+ ag.assertPrint("120", 50);
+ }
+}
Modified: trunk/release-notes.txt
===================================================================
--- trunk/release-notes.txt 2013-10-31 20:20:03 UTC (rev 1755)
+++ trunk/release-notes.txt 2013-11-04 11:27:47 UTC (rev 1756)
@@ -1,3 +1,10 @@
+New features
+
+- implementation of tail recursion optimisation for sub-goals.
+ It can be turned off in agent options, e.g.:
+ agents: bob [tro=false];
+
+
---------------------------
version 1.3.10b
@@ -218,7 +225,7 @@
these events can than be handled by plans such as
^!goto(X,Y)[state(S)] <- .print("goto state is ",S).
for the state suspended, another annotation contains the
- suspension reason (.wait, .suspend, É)
+ suspension reason (.wait, .suspend, ...)
^!goto(X,Y)[state(S)[reason(R)]]
<- .print("goto state is ",S," due to ",R).
Modified: trunk/src/jason/asSemantics/Intention.java
===================================================================
--- trunk/src/jason/asSemantics/Intention.java 2013-10-31 20:20:03 UTC (rev 1755)
+++ trunk/src/jason/asSemantics/Intention.java 2013-11-04 11:27:47 UTC (rev 1756)
@@ -193,7 +193,7 @@
}
public String toString() {
- StringBuilder s = new StringBuilder("intention "+id+": ");
+ StringBuilder s = new StringBuilder("intention "+id+": \n");
for (IntendedMeans im: intendedMeans)
s.append(" " + im + "\n");
if (isFinished())
Modified: trunk/src/jason/asSemantics/TransitionSystem.java
===================================================================
--- trunk/src/jason/asSemantics/TransitionSystem.java 2013-10-31 20:20:03 UTC (rev 1755)
+++ trunk/src/jason/asSemantics/TransitionSystem.java 2013-11-04 11:27:47 UTC (rev 1756)
@@ -493,6 +493,41 @@
confP.C.addIntention(intention);
} else {
// Rule IntEv
+
+ // begin tail recursion optimisation (TRO)
+ if (setts.isTROon()) {
+ IntendedMeans top = confP.C.SE.intention.peek(); // top = the IM that will be removed from the intention due to TRO
+ if (top.getTrigger().isGoal() && im.getTrigger().isGoal() && // are both goal
+ top.getTrigger().getPredicateIndicator().equals( im.getTrigger().getPredicateIndicator()) && // are they equals
+ top.getCurrentStep().getBodyNext() == null) { // the plan below is finished
+ confP.C.SE.intention.pop(); // remove the top IM
+
+ IntendedMeans imBase = confP.C.SE.intention.peek(); // base = where the new IM will be place on top of
+ // move top relevant values into the base (relevant = renamed vars in base)
+ for (VarTerm v: imBase.renamedVars) {
+ VarTerm vvl = (VarTerm)imBase.renamedVars.function.get(v);
+ Term t = top.unif.get(vvl);
+ if (t != null) { // if v has got a value in top unif, put the value in the unifier
+ if (t instanceof Literal) {
+ Literal l= (Literal)t.clone();
+ l.apply(top.unif);
+ l.makeVarsAnnon(top.renamedVars);
+ im.unif.function.put(vvl, l);
+ } else {
+ im.unif.function.put(vvl, t);
+ }
+ } else {
+ // the vvl was renamed again in top, just replace in base the new value
+ VarTerm v0 = (VarTerm)top.renamedVars.function.get(vvl);
+ if (v0 != null) {
+ imBase.renamedVars.function.put(v, v0);
+ }
+ }
+ }
+ }
+ // end of TRO
+ }
+
confP.C.SE.intention.push(im);
confP.C.addIntention(confP.C.SE.intention);
}
@@ -807,10 +842,30 @@
body = body.copy();
body.apply(u);
Unifier renamedVars = new Unifier();
- if (imRenamedVars != null)
+ //System.out.println("antes "+body+" "+u+" ");
+ body.makeVarsAnnon(renamedVars); // free variables in an event cannot conflict with those in the plan
+ if (imRenamedVars != null) {
imRenamedVars.renamedVars = renamedVars;
- body.makeVarsAnnon(renamedVars); // free variables in an event cannot conflict with those in the plan
- //body.makeVarsAnnon(u); // free variables in an event cannot conflict with those in the plan
+
+ // Code for TRO (Tail Recursion Opt)
+ if (setts.isTROon()) {
+ // renamed vars binded with another var in u need to be preserved (since u will be lost in TRO)
+ Map<VarTerm, Term> adds = null;
+ for (VarTerm v: renamedVars) {
+ Term t = u.function.get(v);
+ if (t != null) {
+ //System.out.println("adding "+t+"="+renamedVars.function.get(v));
+ if (adds == null)
+ adds = new HashMap<VarTerm, Term>();
+ adds.put((VarTerm)t,renamedVars.function.get(v));
+ }
+ }
+ if (adds != null)
+ renamedVars.function.putAll(adds);
+ //System.out.println("depois "+body+" "+renamedVars+" u="+u);
+ // end code for TRO
+ }
+ }
body = body.forceFullLiteralImpl();
if (!body.hasSource()) { // do not add source(self) in case the programmer set the source
body.addAnnot(BeliefBase.TSelf);
@@ -883,52 +938,23 @@
// old code:
/*topLiteral.apply(topIM.unif);
topLiteral.makeVarsAnnon();
- im.unif.unifies(im.removeCurrentStep(), topLiteral);
+ Literal cstep = (Literal)im.removeCurrentStep();
+ boolean r = im.unif.unifies(cstep,topLiteral);
*/
// new code optimised: handle directly renamed vars for the call
- //System.out.println("* "+topLiteral+topIM.unif+" "+im.unif+" "+im.renamedVars);
- /*VarTerm[] lvt = null;
- Term[] lvl = null;
- int n = 0;
- // get vars in the unifier that comes from makeVarAnnon
- for (Term t: im.unif.function.values()) {
- if (t instanceof UnnamedVar) {
- UnnamedVar vt = (UnnamedVar)t;
- if (vt.isFromMakeVarAnnon()) {
- Term vl = topIM.unif.function.get(vt);
- if (vl != null) { // vt has value in top
- vl = vl.clone();
- vl.apply(topIM.unif);
- if (vl.isLiteral())
- ((Literal)vl).makeVarsAnnon();
- if (lvt == null) {
- int s = Math.max(im.unif.size(),topIM.unif.size());
- lvt = new VarTerm[s];
- lvl = new Term[s];
- }
- lvt[n] = vt;
- lvl[n] = vl;
- n++;
- }
- }
- }
- }
- for (int il=0; il<n; il++) {
- im.unif.bind(lvt[il], lvl[il]);
- }
- */
-
-
// get vars in the unifier that comes from makeVarAnnon (stored in renamedVars)
if (im.renamedVars != null) {
for (VarTerm ov: im.renamedVars.function.keySet()) {
+ //System.out.println("looking for a value for "+ov+" in "+im.renamedVars+" and "+topIM.unif);
UnnamedVar vt = (UnnamedVar)im.renamedVars.function.get(ov);
+ //System.out.println(" via "+vt);
im.unif.unifiesNoUndo(ov, vt); // introduces the renaming in the current unif
// if vt has got a value from the top (a "return" value), include this value in the current unif
Term vl = topIM.unif.function.get(vt);
//System.out.println(ov+"="+vt+"="+vl);
if (vl != null) { // vt has value in top
+ //System.out.println(" and found "+vl);
vl = vl.clone();
vl.apply(topIM.unif);
if (vl.isLiteral())
@@ -937,8 +963,7 @@
}
}
}
- //System.out.println("=> "+im.unif);
- im.removeCurrentStep();
+ im.removeCurrentStep();
}
}
}
Modified: trunk/src/jason/asSemantics/Unifier.java
===================================================================
--- trunk/src/jason/asSemantics/Unifier.java 2013-10-31 20:20:03 UTC (rev 1755)
+++ trunk/src/jason/asSemantics/Unifier.java 2013-11-04 11:27:47 UTC (rev 1756)
@@ -103,6 +103,16 @@
}
return vl;
}
+
+ public VarTerm getVarFromValue(Term vl) {
+ for (VarTerm v: function.keySet()) {
+ Term vvl = function.get(v);
+ if (vvl.equals(vl)) {
+ return v;
+ }
+ }
+ return null;
+ }
public boolean unifies(Trigger te1, Trigger te2) {
return te1.sameType(te2) && unifies(te1.getLiteral(), te2.getLiteral());
Modified: trunk/src/jason/runtime/Settings.java
===================================================================
--- trunk/src/jason/runtime/Settings.java 2013-10-31 20:20:03 UTC (rev 1755)
+++ trunk/src/jason/runtime/Settings.java 2013-11-04 11:27:47 UTC (rev 1756)
@@ -52,6 +52,7 @@
private boolean sync = ODefaultSync;
private boolean qCache = false; // whether to use query cache
private boolean qProfiling = false; // whether has query profiling
+ private boolean troON = true; // tail recursion optimisation is on by default
private Map<String,Object> userParameters = new HashMap<String,Object>();
@@ -108,6 +109,8 @@
} else if (key.equals("synchronised")) {
setSync("true".equals((String)options.get("synchronised")));
+ } else if (key.equals("tro")) {
+ setTRO("true".equals((String)options.get("tro")));
} else if (key.equals("qcache")) {
setQueryCache( "cycle".equals((String)options.get("qcache")) );
} else if (key.equals("qprofiling")) {
@@ -200,6 +203,13 @@
sync = pSync;
}
+ public boolean isTROon() {
+ return troON;
+ }
+ public void setTRO(boolean tro) {
+ troON = tro;
+ }
+
public boolean hasQueryCache() {
return qCache;
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
