Upload the comparison directory

12 files changed, 368 insertions, 0 deletions

diff --git a/comparison/Inpla/src/ack-stream_3-11-reuse.in b/comparison/Inpla/src/ack-stream_3-11-reuse.in
new file mode 100644
index 0000000..7d7c701
--- /dev/null
+++ b/comparison/Inpla/src/ack-stream_3-11-reuse.in
@@ -0,0 +1,42 @@
+// Ackermann Function: streaming version
+//
+// fun ack(0,n) = n+1
+// | ack(m,0) = ack(m-1,1)        
+// | ack(m,n) = ack(m-1,ack(m,n-1));
+
+// The below rule is wrong because there is no gurantee
+// such that cnt is an integer agent when Ack(r)~(m-1,cnt) is evaluated.
+//
+// Ack(r) >< (int m, int n)
+// | m==0 => r~(n+1)
+// | n==0 => Ack(r) ~ (m-1,1)
+// | _ => Ack(cnt)~(m,n-1), Ack(r)~(m-1,cnt);
+
+
+// When m==0, we should not have OneUp(ret)~n
+// because the n is correspoidng to cnt in Ack(ret,cnt)~(m-1),
+// and we have to wait for finishing evaluation of Ack(cnt,n-1)~m.
+// So, without waiting, we put ret~Inc(n) in order to continue evaluation.
+// The the number of Inc is evaluated later by using Sumup.
+
+Ack(ret, n) >< (int m)
+| m==0 => ret~(*L)Inc(n)
+| _ => (*L)Ackm(ret, m)~n;
+
+Ackm(ret, int m) >< (int n)
+| n==0 => Ack(ret,Inc(0)) ~ (m-1)
+| _ => (*L)Ack(cnt,n-1)~m, Ack(ret,cnt)~(m-1);
+
+Ackm(ret, int m) >< Inc(n)
+=> (*L)Ack(cnt,n)~m, (*R)Ack(ret,cnt)~(m-1);
+
+Sumup(ret, int sum) >< Inc(x) => (*L)Sumup(ret, sum+1)~x;
+Sumup(ret, int sum) >< (int n) => ret~sum+n;
+
+
+//AckMain(ret)><(int m, int n) => (*L)Ack(cnt,n)~m, (*R)Sumup(ret,0)~cnt;
+AckMain(ret)><(int m, int n) => Ack(cnt,n)~m, Sumup(ret,0)~cnt;
+
+AckMain(ret)~(3,11);
+ret;
+free ret;
diff --git a/comparison/Inpla/src/ack-stream_3-11.in b/comparison/Inpla/src/ack-stream_3-11.in
new file mode 100644
index 0000000..7b23d32
--- /dev/null
+++ b/comparison/Inpla/src/ack-stream_3-11.in
@@ -0,0 +1,41 @@
+// Ackermann Function: streaming version
+//
+// fun ack(0,n) = n+1
+// | ack(m,0) = ack(m-1,1)        
+// | ack(m,n) = ack(m-1,ack(m,n-1));
+
+// The below rule is wrong because there is no gurantee
+// such that cnt is an integer agent when Ack(r)~(m-1,cnt) is evaluated.
+//
+// Ack(r) >< (int m, int n)
+// | m==0 => r~(n+1)
+// | n==0 => Ack(r) ~ (m-1,1)
+// | _ => Ack(cnt)~(m,n-1), Ack(r)~(m-1,cnt);
+
+
+// When m==0, we should not have OneUp(ret)~n
+// because the n is correspoidng to cnt in Ack(ret,cnt)~(m-1),
+// and we have to wait for finishing evaluation of Ack(cnt,n-1)~m.
+// So, without waiting, we put ret~Inc(n) in order to continue evaluation.
+// The the number of Inc is evaluated later by using Sumup.
+
+Ack(ret, n) >< (int m)
+| m==0 => ret~Inc(n)
+| _ => Ackm(ret, m)~n;
+
+Ackm(ret, int m) >< (int n)
+| n==0 => Ack(ret,Inc(0)) ~ (m-1)
+| _ => Ack(cnt,n-1)~m, Ack(ret,cnt)~(m-1);
+
+Ackm(ret, int m) >< Inc(n)
+=> Ack(cnt,n)~m, Ack(ret,cnt)~(m-1);
+
+Sumup(ret, int sum) >< Inc(x) => Sumup(ret, sum+1)~x;
+Sumup(ret, int sum) >< (int n) => ret~sum+n;
+
+
+AckMain(ret)><(int m, int n) => Ack(cnt,n)~m, Sumup(ret,0)~cnt;
+
+AckMain(ret)~(3,11);
+ret;
+free ret;
diff --git a/comparison/Inpla/src/bsort-40000-reuse.in b/comparison/Inpla/src/bsort-40000-reuse.in
new file mode 100644
index 0000000..8b6a386
--- /dev/null
+++ b/comparison/Inpla/src/bsort-40000-reuse.in
@@ -0,0 +1,24 @@
+// Bubble sort
+BS(ret) >< [] => ret~[];
+BS(ret) >< x:xs => (*L)BS(ret)~cnt, (*R)B(cnt, x)~xs;
+BS(ret) >< M(x) => ret~x;
+
+B(ret, int x) >< [] => ret~M([x]);
+B(ret, int x) >< M(w) => ret~M(x:w);
+B(ret, int x) >< (int y):ys
+| x<y => ret~(*R)(x:cnt), (*L)B(cnt, y)~ys
+| _   => ret~(*R)(y:cnt), (*L)B(cnt, x)~ys;
+
+
+
+
+const LIST_ELEM=40000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), (*L)MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+BS(ret)~cnt;
+ret;
diff --git a/comparison/Inpla/src/bsort-40000.in b/comparison/Inpla/src/bsort-40000.in
new file mode 100644
index 0000000..0120900
--- /dev/null
+++ b/comparison/Inpla/src/bsort-40000.in
@@ -0,0 +1,24 @@
+// Bubble sort
+BS(ret) >< [] => ret~[];
+BS(ret) >< x:xs => BS(ret)~cnt, B(cnt, x)~xs;
+BS(ret) >< M(x) => ret~x;
+
+B(ret, int x) >< [] => ret~M([x]);
+B(ret, int x) >< M(w) => ret~M(x:w);
+B(ret, int x) >< (int y):ys
+| x<y => ret~(x:cnt), B(cnt, y)~ys
+| _   => ret~(y:cnt), B(cnt, x)~ys;
+
+
+
+
+const LIST_ELEM=40000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+BS(ret)~cnt;
+ret;
diff --git a/comparison/Inpla/src/fib-38-reuse.in b/comparison/Inpla/src/fib-38-reuse.in
new file mode 100644
index 0000000..6b3d32b
--- /dev/null
+++ b/comparison/Inpla/src/fib-38-reuse.in
@@ -0,0 +1,17 @@
+// Fibonacci number
+Fib(r) >< (int n)
+| n == 0 => r~0
+| n == 1 => r~1
+| _ => Fib(cnt1)~(n-1), Fib(cnt2)~(n-2), (*L)Add(r,cnt2)~cnt1;
+
+/* Add is realised as built-in.
+Addd(r,n) >< (int m)
+=> Addd2(r,m) ~ n;
+
+Addd2(r,int m) >< (int n)
+=> r~(m+n);
+*/
+
+Fib(r)~38;
+r;
+free r;
diff --git a/comparison/Inpla/src/fib-38.in b/comparison/Inpla/src/fib-38.in
new file mode 100644
index 0000000..a79eb5b
--- /dev/null
+++ b/comparison/Inpla/src/fib-38.in
@@ -0,0 +1,17 @@
+// Fibonacci number
+Fib(r) >< (int n)
+| n == 0 => r~0
+| n == 1 => r~1
+| _ => Add(r,cnt2)~cnt1, Fib(cnt1)~(n-1), Fib(cnt2)~(n-2);
+
+/*
+Addd(r,n) >< (int m)
+=> Addd2(r,m) ~ n;
+
+Addd2(r,int m) >< (int n)
+=> r~(m+n);
+*/
+
+Fib(r)~38;
+r;
+free r;
diff --git a/comparison/Inpla/src/isort-40000-reuse.in b/comparison/Inpla/src/isort-40000-reuse.in
new file mode 100644
index 0000000..00f0ecc
--- /dev/null
+++ b/comparison/Inpla/src/isort-40000-reuse.in
@@ -0,0 +1,22 @@
+// Insertion sort
+IS(ret) >< [] => ret~[];
+IS(ret) >< x:xs => (*L)I(ret, x)~cnt, (*R)IS(cnt)~xs;
+
+I(ret, int x) >< [] => ret~[x];
+I(ret, int x) >< (int y):ys
+| x<=y => ret~(*L)(x:(*R)(y:ys))
+| _    => ret~(*L)(y:cnt), (*R)I(cnt, x)~ys;
+
+
+const LIST_ELEM=40000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), (*L)MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+IS(ret)~cnt;
+ret;
+
+
diff --git a/comparison/Inpla/src/isort-40000.in b/comparison/Inpla/src/isort-40000.in
new file mode 100644
index 0000000..ff831a3
--- /dev/null
+++ b/comparison/Inpla/src/isort-40000.in
@@ -0,0 +1,22 @@
+// Insertion sort
+IS(ret) >< [] => ret~[];
+IS(ret) >< x:xs => I(ret, x)~cnt, IS(cnt)~xs;
+
+I(ret, int x) >< [] => ret~[x];
+I(ret, int x) >< (int y):ys
+| x<=y => ret~(x:y:ys)
+| _    => ret~(y:cnt), I(cnt, x)~ys;
+
+
+const LIST_ELEM=40000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+IS(ret)~cnt;
+ret;
+
+
diff --git a/comparison/Inpla/src/msort-800000-reuse.in b/comparison/Inpla/src/msort-800000-reuse.in
new file mode 100644
index 0000000..36723b9
--- /dev/null
+++ b/comparison/Inpla/src/msort-800000-reuse.in
@@ -0,0 +1,67 @@
+// Merge sort
+MS(ret) >< [] => ret~[];
+MS(ret) >< x:xs => MS_tail(ret, x)~xs;
+
+MS_tail(ret, n) >< [] => ret~(*R)[n];
+MS_tail(ret, int n) >< x:xs => 
+//	MS(a)~left, MS(b)~right, Append(ret,a)~b,
+//	Split(0, left,right) ~ (n:x:xs);
+	MS(a)~left, MS(b)~right, Append(ret,a)~b,
+	(*L)Split(left,right) ~ (*R)(n:x:xs);
+
+
+/*
+Splitn(int flag, a, b) >< [] => a~[], b~[];
+Splitn(int flag, a, b) >< (int y):ys
+| flag==0 => b~(*R)(y:cnt), (*L)Splitn(1, a, cnt)~ys
+| _       => a~(*R)(y:cnt), (*L)Splitn(0, cnt, b)~ys;
+
+Split(a,b) >< x:xs => Splitn(0,a,b)~x:xs;
+*/
+
+Split(a,b) >< [] => a~[], b~[];
+Split(a,b) >< x:xs => a~(x:cntl), (*L)Split(b,cntl)~xs;
+
+
+
+// この実験から、Merge は悪くないことがわかる。
+// Part でも -t 5 6 7 順に速くなる。
+// つまり、Split が悪いと言える。
+
+/*
+MS_tail(ret, n) >< [] => ret~(*R)[n];
+MS_tail(ret, n) >< x:xs => 
+	MS(a)~left, MS(b)~right, Merge(ret,b)~a,
+	(*L)Split(left,right) ~ (*R)(n:x:xs);
+*/
+
+Merge(ret, snd) >< [] => ret~snd;
+Merge(ret, snd) >< x:xs => (*L)MergeCC(ret, x, xs)~snd;
+
+MergeCC(ret, int y, ys) >< [] => ret~(*R)(y:ys);
+MergeCC(ret, int y, ys) >< (int x):xs
+| x <= y => ret~(x:cnt), (*L)MergeCC(cnt, y, ys) ~ xs
+| _      => ret~(y:cnt), (*L)MergeCC(cnt, x, xs) ~ ys;
+// ret~(*R)(x:cnt) less improvement
+
+// *** I should make an option that outputs bytecodes to a file. ***
+// *** Then, I have to look the reason why 
+// *** ret~(*R)(x:cnt), MergeCC(cnt, y, ys) ~ xs becomes less improvement.
+
+
+
+
+//	left~cntr, (*L)Split(cntr,cntl)~xs, right~(x:cntl);
+// This also make it less efficient.
+
+
+const LIST_ELEM=1200000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), (*L)MkRandList(cnt)~(n-1) 
+  where rd=rand(LIST_ELEM)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+MS(ret)~cnt;
+ret;
diff --git a/comparison/Inpla/src/msort-800000.in b/comparison/Inpla/src/msort-800000.in
new file mode 100644
index 0000000..e04803f
--- /dev/null
+++ b/comparison/Inpla/src/msort-800000.in
@@ -0,0 +1,34 @@
+// Merge sort
+MS(ret) >< [] => ret~[];
+MS(ret) >< x:xs => MS_tail(ret, x)~xs;
+
+MS_tail(ret, int n) >< [] => ret~[n];
+MS_tail(ret, int n) >< x:xs => 
+	Split(left,right) ~ (n:x:xs),
+	MS(a)~left, MS(b)~right, Merge(ret,b)~a;
+
+Merge(ret, snd) >< [] => ret~snd;
+Merge(ret, snd) >< x:xs => MergeC(ret, x, xs)~snd;
+
+MergeCC(ret, int y, ys) >< [] => ret~(y:ys);
+MergeCC(ret, int y, ys) >< (int x):xs
+| x <= y => ret~(x:cnt), MergeCC(cnt, y, ys) ~ xs
+| _      => ret~(y:cnt), MergeCC(cnt, x, xs) ~ ys;
+
+
+Split(right,left) >< [] => right~[], left~[];
+Split(right,left) >< x:xs =>
+	right~(x:cntl), left~cntr, Split(cntr,cntl)~xs;
+
+
+
+const LIST_ELEM=800000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+MS(ret)~cnt;
+ret;
diff --git a/comparison/Inpla/src/qsort-800000-reuse.in b/comparison/Inpla/src/qsort-800000-reuse.in
new file mode 100644
index 0000000..8bf7a83
--- /dev/null
+++ b/comparison/Inpla/src/qsort-800000-reuse.in
@@ -0,0 +1,29 @@
+// Quick sort
+QS(ret) >< [] => ret~(*R)[];
+QS(ret) >< (int x):xs =>
+	(*R)Part(x, left, right)~xs,
+	(*L)QS(cntl)~left, QS(cntr)~right,
+	Append(ret, x:cntl)~cntr;
+
+// Note: `Append' is implemented as built-in.
+
+// Apnd(ret, a)~b  -->  ret ~ b@a
+//Apnd(ret, a) >< [] => ret~a;
+//Apnd(ret, a) >< x:xs => ret~(x:cnt), Apnd(cnt, a)~xs;
+
+Part(int x, a, b) >< [] => a~(*L)[], b~(*R)[];
+Part(int x, a, b) >< (int y):ys
+| y<x => b~(*R)(y:cnt), (*L)Part(x, a, cnt)~ys
+| _   => a~(*R)(y:cnt), (*L)Part(x, cnt, b)~ys;
+
+
+const LIST_ELEM=800000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), (*L)MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+QS(ret)~cnt;
+ret;
diff --git a/comparison/Inpla/src/qsort-800000.in b/comparison/Inpla/src/qsort-800000.in
new file mode 100644
index 0000000..e8913e8
--- /dev/null
+++ b/comparison/Inpla/src/qsort-800000.in
@@ -0,0 +1,29 @@
+// Quick sort
+QS(ret) >< [] => ret~[];
+QS(ret) >< (int x):xs =>
+	Part(x, left, right)~xs,
+	QS(cntl)~left, QS(cntr)~right,
+	Append(ret, x:cntl)~cntr;
+
+// Note: `Append' is implemented as built-in.
+
+// Apnd(ret, a)~b  -->  ret ~ b@a
+//Apnd(ret, a) >< [] => ret~a;
+//Apnd(ret, a) >< x:xs => ret~(x:cnt), Apnd(cnt, a)~xs;
+
+Part(int x, a, b) >< [] => a~[], b~[];
+Part(int x, a, b) >< (int y):ys
+| y<x => b~(y:cnt), Part(x, a, cnt)~ys
+| _   => a~(y:cnt), Part(x, cnt, b)~ys;
+
+
+const LIST_ELEM=800000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+QS(ret)~cnt;
+ret;