From e18b27f43ac23689822d4aaaaa3e8d550e41017a Mon Sep 17 00:00:00 2001 From: Shinya Sato Date: Mon, 30 May 2022 20:36:38 +0900 Subject: v0.8.2-2 --- Changelog.md | 21 +- README.md | 14 +- comparison/Haskell/Makefile | 6 +- comparison/Haskell/bsort-20000.hs | 45 ++ comparison/Haskell/isort-20000.hs | 39 ++ comparison/Inpla/main.sh | 8 +- comparison/Inpla/src/bsort-20000-reuse.in | 77 +++ comparison/Inpla/src/bsort-20000.in | 77 +++ .../Inpla/src/bsort-efficient-20000-reuse.in | 40 ++ comparison/Inpla/src/bsort-efficient-20000.in | 40 ++ comparison/Inpla/src/isort-20000-reuse.in | 38 ++ comparison/Inpla/src/isort-20000.in | 38 ++ comparison/OCaml/Makefile | 6 +- comparison/OCaml/bsort20000.ml | 39 ++ comparison/OCaml/isort20000.ml | 36 ++ comparison/Python/Makefile | 2 +- comparison/Python/bsort-20000.py | 31 + comparison/Python/isort-20000.py | 31 + comparison/SML/Makefile | 2 +- comparison/SML/bsort-20000.sml | 42 ++ comparison/SML/isort-20000.sml | 35 + pic/benchmark_reuse_v0.8.2-2.png | Bin 0 -> 30905 bytes src/config.h | 4 + src/id_table.h | 7 +- src/inpla.y | 719 +++++++++++---------- 25 files changed, 1048 insertions(+), 349 deletions(-) create mode 100644 comparison/Haskell/bsort-20000.hs create mode 100644 comparison/Haskell/isort-20000.hs create mode 100644 comparison/Inpla/src/bsort-20000-reuse.in create mode 100644 comparison/Inpla/src/bsort-20000.in create mode 100644 comparison/Inpla/src/bsort-efficient-20000-reuse.in create mode 100644 comparison/Inpla/src/bsort-efficient-20000.in create mode 100644 comparison/Inpla/src/isort-20000-reuse.in create mode 100644 comparison/Inpla/src/isort-20000.in create mode 100644 comparison/OCaml/bsort20000.ml create mode 100644 comparison/OCaml/isort20000.ml create mode 100644 comparison/Python/bsort-20000.py create mode 100644 comparison/Python/isort-20000.py create mode 100644 comparison/SML/bsort-20000.sml create mode 100644 comparison/SML/isort-20000.sml create mode 100644 pic/benchmark_reuse_v0.8.2-2.png diff --git a/Changelog.md b/Changelog.md index 79bf267..f25c109 100644 --- a/Changelog.md +++ b/Changelog.md @@ -1,6 +1,25 @@ # Change log +### v0.8.1-2 minor update (released on 30 May 2022) -### v0.8.1-2 minor update (released on 1 May 2022) +| | Haskell | OCaml | SML | Python | Inpla8 | Inpla8r | +| ------------ | :----------------------------------------: | :-------------------------------------: | :-------------------------------------: | :----------------------------------------: | :----------------------------------------------: | :----------------------------------------------------: | +| ack(3,11) | [2.30](comparison/Haskell/ack3-11.hs) | [0.46](comparison/OCaml/ack3_11.ml) | [**0.43**](comparison/SML/ack3-11.sml) | [-](comparison/Python/ack3-11.py) | [0.86](comparison/Inpla/src/ack-stream_3-11.in) | [0.71](comparison/Inpla/src/ack-stream_3-11-reuse.in) | +| fib 38 | [1.60](comparison/Haskell/fib38.hs) | [**0.15**](comparison/OCaml/fib38.ml) | [0.27](comparison/SML/fib38.sml) | [8.88](comparison/Python/fib38.py) | [0.40](comparison/Inpla/src/fib-38.in) | [0.43](comparison/Inpla/src/fib-38-reuse.in) | +| bsort 20000 | [4.98](comparison/Haskell/bsort-40000.hs) | [6.78](comparison/OCaml/bsort40000.ml) | [2.38](comparison/SML/bsort-40000.sml) | [19.91](comparison/Python/bsort-40000.py) | [2.16](comparison/Inpla/src/bsort-40000.in) | [**1.58**](comparison/Inpla/src/bsort-40000-reuse.in) | +| isort 20000 | [2.15](comparison/Haskell/isort-40000.hs) | [1.52](comparison/OCaml/isort40000.ml) | [0.60](comparison/SML/isort-40000.sml) | [9.58](comparison/Python/isort-40000.py) | [**0.29**](comparison/Inpla/src/isort-40000.in) | [0.33](comparison/Inpla/src/isort-40000-reuse.in) | +| qsort 260000 | [0.34](comparison/Haskell/qsort-800000.hs) | [0.25](comparison/OCaml/qsort800000.ml) | [0.27](comparison/SML/qsort-800000.sml) | [10.40](comparison/Python/qsort-800000.py) | [0.15](comparison/Inpla/src/qsort-800000.in) | [**0.11**](comparison/Inpla/src/qsort-800000-reuse.in) | +| msort 260000 | [0.39](comparison/Haskell/msort-800000.hs) | [0.29](comparison/OCaml/msort800000.ml) | [0.26](comparison/SML/msort-800000.sml) | [10.96](comparison/Python/msort-800000.py) | [**0.15**](comparison/Inpla/src/msort-800000.in) | [**0.15**](comparison/Inpla/src/msort-800000-reuse.in) | + +#### Bug fix + +* **`and` and `or` operations**: These operations had not work well due to bad effects of bytecode optimisations, and these has been fixed. + +#### Changes +* **The benchmark table**: Bubble sort in Inpla has been changed to be done in the same method to others, and still Inpla keeps the fastest. + + + +### v0.8.1-1 minor update (released on 2 May 2022) | | Haskell | OCaml | SML | Python | Inpla8 | Inpla8r | | ------------ | :----------------------------------------: | :-------------------------------------: | :-------------------------------------: | :----------------------------------------: | :----------------------------------------------: | :----------------------------------------------------: | diff --git a/README.md b/README.md index 730cafa..378b100 100644 --- a/README.md +++ b/README.md @@ -6,20 +6,20 @@ Inpla is a multi-threaded parallel interpreter of interaction nets. Once you write programs for sequential execution, it works also in multi-threaded parallel execution. Each thread is managed on each CPU-core with POSIX-thread library. -* The current version is 0.8.2-1, released on **2 May 2022**. (See [Changelog.md](Changelog.md) for details.) +* The current version is 0.8.2-2 (bugfix), released on **30 May 2022**. (See [Changelog.md](Changelog.md) for details.) * The below graph shows speed-up ratio to threads numbers for programs in the following benchmark table, though quick sort and merge sort are for 800000 elements. This is because 260000 elements, which are in the following benchmark table, are too small for Inpla to perform in parallel as shown in the description of v0.8.2-1 in [Changelog.md](./Changelog.md). -![speedup-ratio](pic/benchmark_reuse_v0.8.2-1.png) +![speedup-ratio](pic/benchmark_reuse_v0.8.2-2.png) | | Haskell | OCaml | SML | Python | Inpla8 | Inpla8r | | -------------- | :------: | :------: | :----: | :----: | :------: | :------: | -| ack(3,11) | [2.30](comparison/Haskell/ack3-11.hs) | [0.46](comparison/OCaml/ack3_11.ml) | [**0.43**](comparison/SML/ack3-11.sml) | [-](comparison/Python/ack3-11.py) | [0.84](comparison/Inpla/src/ack-stream_3-11.in) | [0.71](comparison/Inpla/src/ack-stream_3-11-reuse.in) | -| fib 38 | [1.60](comparison/Haskell/fib38.hs) | [**0.15**](comparison/OCaml/fib38.ml) | [0.27](comparison/SML/fib38.sml) | [8.88](comparison/Python/fib38.py) | [0.41](comparison/Inpla/src/fib-38.in) | [0.43](comparison/Inpla/src/fib-38-reuse.in) | -| bsort 40000 | [34.48](comparison/Haskell/bsort-40000.hs) | [34.62](comparison/OCaml/bsort40000.ml) | [12.06](comparison/SML/bsort-40000.sml) | [79.53](comparison/Python/bsort-40000.py) | [3.02](comparison/Inpla/src/bsort-40000.in) | [**2.52**](comparison/Inpla/src/bsort-40000-reuse.in) | -| isort 40000 | [12.54](comparison/Haskell/isort-40000.hs) | [7.45](comparison/OCaml/isort40000.ml) | [2.94](comparison/SML/isort-40000.sml) | [36.89](comparison/Python/isort-40000.py) | [**1.15**](comparison/Inpla/src/isort-40000.in) | [1.24](comparison/Inpla/src/isort-40000-reuse.in) | -| qsort 260000 | [0.34](comparison/Haskell/qsort-800000.hs) | [0.25](comparison/OCaml/qsort800000.ml) | [0.27](comparison/SML/qsort-800000.sml) | [10.40](comparison/Python/qsort-800000.py) | [0.15](comparison/Inpla/src/qsort-800000.in) | [**0.12**](comparison/Inpla/src/qsort-800000-reuse.in) | +| ack(3,11) | [2.30](comparison/Haskell/ack3-11.hs) | [0.46](comparison/OCaml/ack3_11.ml) | [**0.43**](comparison/SML/ack3-11.sml) | [-](comparison/Python/ack3-11.py) | [0.86](comparison/Inpla/src/ack-stream_3-11.in) | [0.71](comparison/Inpla/src/ack-stream_3-11-reuse.in) | +| fib 38 | [1.60](comparison/Haskell/fib38.hs) | [**0.15**](comparison/OCaml/fib38.ml) | [0.27](comparison/SML/fib38.sml) | [8.88](comparison/Python/fib38.py) | [0.40](comparison/Inpla/src/fib-38.in) | [0.43](comparison/Inpla/src/fib-38-reuse.in) | +| bsort 20000 | [4.98](comparison/Haskell/bsort-40000.hs) | [6.78](comparison/OCaml/bsort40000.ml) | [2.38](comparison/SML/bsort-40000.sml) | [19.91](comparison/Python/bsort-40000.py) | [2.16](comparison/Inpla/src/bsort-40000.in) | [**1.58**](comparison/Inpla/src/bsort-40000-reuse.in) | +| isort 20000 | [2.15](comparison/Haskell/isort-40000.hs) | [1.52](comparison/OCaml/isort40000.ml) | [0.60](comparison/SML/isort-40000.sml) | [9.58](comparison/Python/isort-40000.py) | [**0.29**](comparison/Inpla/src/isort-40000.in) | [0.33](comparison/Inpla/src/isort-40000-reuse.in) | +| qsort 260000 | [0.34](comparison/Haskell/qsort-800000.hs) | [0.25](comparison/OCaml/qsort800000.ml) | [0.27](comparison/SML/qsort-800000.sml) | [10.40](comparison/Python/qsort-800000.py) | [0.15](comparison/Inpla/src/qsort-800000.in) | [**0.11**](comparison/Inpla/src/qsort-800000-reuse.in) | | msort 260000 | [0.39](comparison/Haskell/msort-800000.hs) | [0.29](comparison/OCaml/msort800000.ml) | [0.26](comparison/SML/msort-800000.sml) | [10.96](comparison/Python/msort-800000.py) | [**0.15**](comparison/Inpla/src/msort-800000.in) | [**0.15**](comparison/Inpla/src/msort-800000-reuse.in) | - **Comparison in execution time** with other implementations: **Haskell** (GHC version 8.10.7), **OCaml** (ocamlopt, the native-code compiler, version 4.08.1), **Standard ML of New Jersey** v110.74 (interpreter mode) and **Python** 3.8.5 in execution time. diff --git a/comparison/Haskell/Makefile b/comparison/Haskell/Makefile index b55259f..13a1b83 100644 --- a/comparison/Haskell/Makefile +++ b/comparison/Haskell/Makefile @@ -1,7 +1,7 @@ CC = stack ghc CFLAGS = -O2 BENCHMARK = bash ../tools/sptest_commands.sh -TARGET = ack3-11 fib38 bsort-40000 isort-40000 qsort-260000 msort-260000 +TARGET = ack3-11 fib38 bsort-20000 isort-20000 qsort-260000 msort-260000 LOG = log.txt @@ -18,10 +18,10 @@ ack3-11: ack3-11.hs fib38: fib38.hs $(CC) -- $(CFLAGS) $< -bsort-40000: bsort-40000.hs +bsort-20000: bsort-20000.hs $(CC) -- $(CFLAGS) $< -isort-40000: isort-40000.hs +isort-20000: isort-20000.hs $(CC) -- $(CFLAGS) $< qsort-260000: qsort-260000.hs diff --git a/comparison/Haskell/bsort-20000.hs b/comparison/Haskell/bsort-20000.hs new file mode 100644 index 0000000..89ecfab --- /dev/null +++ b/comparison/Haskell/bsort-20000.hs @@ -0,0 +1,45 @@ +{- +https://gist.github.com/masquerade0324/68f4f3fd3ab897fbe1ad +http://files.farka.eu/pub/AC21007/lec5.pdf +-} + +import System.Random + +bs xs 0 = xs +bs (x:y:ys) n = + if x IO([Int]) +randomList 0 = return [] +randomList n = do + r <- randomRIO (1,10000) + rs <- randomList (n-1) + return (r:rs) + + +validation [] = True +validation (x:xs) = validation_cons x xs +validation_cons x [] = True +validation_cons x (y:ys) = + if x<=y then validation_cons y ys + else False + + +main = do + list <- randomList 20000 + let sorted = bsort list + print (validation sorted) diff --git a/comparison/Haskell/isort-20000.hs b/comparison/Haskell/isort-20000.hs new file mode 100644 index 0000000..a4cef88 --- /dev/null +++ b/comparison/Haskell/isort-20000.hs @@ -0,0 +1,39 @@ +{- +http://www.codecodex.com/wiki/Insertion_sort#Standard_ML +-} +import System.Random + +isort [] = [] +isort (x:xs) = insert x (isort xs) + +insert x [] = [x] +insert x (y:ys) = + if x<=y then x:y:ys + else y:(insert x ys) + + +{- +main = print $ isort [3,2,8,5] +-} + + +randomList :: Int -> IO([Int]) +randomList 0 = return [] +randomList n = do + r <- randomRIO (1,10000) + rs <- randomList (n-1) + return (r:rs) + + +validation [] = True +validation (x:xs) = validation_cons x xs +validation_cons x [] = True +validation_cons x (y:ys) = + if x<=y then validation_cons y ys + else False + + +main = do + list <- randomList 20000 + let sorted = isort list + print (validation sorted) diff --git a/comparison/Inpla/main.sh b/comparison/Inpla/main.sh index 6975046..13502b9 100644 --- a/comparison/Inpla/main.sh +++ b/comparison/Inpla/main.sh @@ -6,11 +6,11 @@ bash ./sptestInpla.sh src/fib-38-reuse.in bash ./sptestInpla.sh src/ack-stream_3-11.in bash ./sptestInpla.sh src/ack-stream_3-11-reuse.in -bash ./sptestInpla.sh src/bsort-40000.in -bash ./sptestInpla.sh src/bsort-40000-reuse.in +bash ./sptestInpla.sh src/bsort-20000.in +bash ./sptestInpla.sh src/bsort-20000-reuse.in -bash ./sptestInpla.sh src/isort-40000.in -bash ./sptestInpla.sh src/isort-40000-reuse.in +bash ./sptestInpla.sh src/isort-20000.in +bash ./sptestInpla.sh src/isort-20000-reuse.in bash ./sptestInpla.sh src/qsort-260000.in bash ./sptestInpla.sh src/qsort-260000-reuse.in '-Xms 17 -Xmt 0' diff --git a/comparison/Inpla/src/bsort-20000-reuse.in b/comparison/Inpla/src/bsort-20000-reuse.in new file mode 100644 index 0000000..c5080fe --- /dev/null +++ b/comparison/Inpla/src/bsort-20000-reuse.in @@ -0,0 +1,77 @@ +// Bubble sort with the same algorithm as others + +/* +// length +length_(r,n) >< [] => r~n; +length_(r,int n) >< (int x):xs => length_(r,n+1)~xs; + +length(r) >< [] => r~0; +length(r) >< x:xs => length_(r,0) ~ x:xs; +*/ + + +// stream length +len_stream_(len, list, int ct) >< [] => len~ct, list~(*R)[]; +len_stream_(len, list, int ct) >< x:xs => + list~(*R)(x:cnt), + len_stream_(len, cnt, ct+1) ~ xs; + + +len_stream(len, list) >< [] => len~0, list~(*R)[]; +len_stream(len, list) >< x:xs => + list~(x:cnt), + len_stream_(len, cnt, 1)~xs; + + +// bubble sort +bs(r, xs) >< (int n) +| n == 0 => r~xs +| _ => (*L)bs_Cons(r, n)~xs; + +bs_Cons(r, int n)>< x:xs => (*L)bs_ConsCons(r, n, x) ~ xs; +bs_Cons(r, int n)>< [] => r~(*R)[]; + +bs_ConsCons(r, int n, int x) >< (int y):ys +| x < y => r~x:cnt, (*L)bs(cnt, y:ys) ~(n-1) +| _ => r~y:cnt, (*L)bs(cnt, x:ys)~(n-1); +bs_ConsCons(r, int n, int x) >< [] => r~(*R)[x]; + +go(r,xs) >< (int n) +| n==0 => r~xs +| _ => bs(cnt, xs)~n, (*L)go(r, cnt)~(n-1); + +bsort(r) >< [] => r~[]; +bsort(r) >< x:xs => + (*L)len_stream(len, alist) ~ (*R)(x:xs), + go(r, alist)~lengthDec1, + Sub(lengthDec1,len)~1; + + +// Creates a random list +make_RandList(ret) >< (int n) +| n>0 => ret~(rd:cnt), (*L)make_RandList(cnt)~(n-1) + where rd=rand(10000) +| _ => ret~[]; + + +// validation checks +valid(ret) >< [] => ret~True; +valid(ret) >< x:xs => (*L)valid_Cons(ret,x)~xs; + +valid_Cons(ret, int x) >< [] => ret~True; +valid_Cons(ret, int x) >< (int y):ys +| x<=y => (*L)valid_Cons(ret,y)~ys +| _ => ret~False, Eraser~ys; + +// The `Eraser' is a built-in agent defined for any agents as follows: +//Eraser >< Alpha(a1, ..., a5) => Eraser~a1, ..., Eraser~a5; + + +// Main +const LIST_ELEM=20000; + +make_RandList(rndlist)~(LIST_ELEM), +bsort(sorted)~rndlist, +valid(ret)~sorted; + +ret; diff --git a/comparison/Inpla/src/bsort-20000.in b/comparison/Inpla/src/bsort-20000.in new file mode 100644 index 0000000..e012bc6 --- /dev/null +++ b/comparison/Inpla/src/bsort-20000.in @@ -0,0 +1,77 @@ +// Bubble sort with the same algorithm as others + +/* +// length +length_(r,n) >< [] => r~n; +length_(r,int n) >< (int x):xs => length_(r,n+1)~xs; + +length(r) >< [] => r~0; +length(r) >< x:xs => length_(r,0) ~ x:xs; +*/ + + +// stream length +len_stream_(len, list, int ct) >< [] => len~ct, list~[]; +len_stream_(len, list, int ct) >< x:xs => + list~x:cnt, + len_stream_(len, cnt, ct+1) ~xs; + + +len_stream(len, list) >< [] => len~0, list~[]; +len_stream(len, list) >< x:xs => + list~x:cnt, + len_stream_(len, cnt, 1)~xs; + + +// bubble sort +bs(r, xs) >< (int n) +| n == 0 => r~xs +| _ => bs_Cons(r, n)~xs; + +bs_Cons(r, int n)>< x:xs => bs_ConsCons(r, n, x) ~ xs; +bs_Cons(r, int n)>< [] => r~[]; + +bs_ConsCons(r, int n, int x) >< (int y):ys +| x < y => r~x:cnt, bs(cnt, y:ys) ~(n-1) +| _ => r~y:cnt, bs(cnt, x:ys)~(n-1); +bs_ConsCons(r, int n, int x) >< [] => r~[x]; + +go(r,xs) >< (int n) +| n==0 => r~xs +| _ => bs(cnt, xs)~n, go(r, cnt)~(n-1); + +bsort(r) >< [] => r~[]; +bsort(r) >< x:xs => + len_stream(len, alist) ~ x:xs, + go(r, alist)~lengthDec1, + Sub(lengthDec1,len)~1; + + +// creates a random list +make_RandList(ret) >< (int n) +| n>0 => ret~(rd:cnt), make_RandList(cnt)~(n-1) + where rd=rand(10000) +| _ => ret~[]; + + +// validation checks +valid(ret) >< [] => ret~True; +valid(ret) >< x:xs => valid_Cons(ret,x)~xs; + +valid_Cons(ret, int x) >< [] => ret~True; +valid_Cons(ret, int x) >< (int y):ys +| x<=y => valid_Cons(ret,y)~ys +| _ => ret~False, Eraser~ys; + +// The `Eraser' is a built-in agent defined for any agents as follows: +//Eraser >< Alpha(a1, ..., a5) => Eraser~a1, ..., Eraser~a5; + + +// Main +const LIST_ELEM=20000; + +make_RandList(rndlist)~(LIST_ELEM), +bsort(sorted)~rndlist, +valid(ret)~sorted; + +ret; \ No newline at end of file diff --git a/comparison/Inpla/src/bsort-efficient-20000-reuse.in b/comparison/Inpla/src/bsort-efficient-20000-reuse.in new file mode 100644 index 0000000..e496c3e --- /dev/null +++ b/comparison/Inpla/src/bsort-efficient-20000-reuse.in @@ -0,0 +1,40 @@ +// Bubble sort +bsort(ret) >< [] => ret~[]; +bsort(ret) >< x:xs => (*L)bsort(ret)~cnt, (*R)B(cnt, x)~xs; +bsort(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 ret~(*R)(x:cnt), (*L)B(cnt, y)~ys +| _ => ret~(*R)(y:cnt), (*L)B(cnt, x)~ys; + + +// Creates a random list +make_RandList(ret) >< (int n) +| n>0 => ret~(rd:cnt), (*L)make_RandList(cnt)~(n-1) + where rd=rand(10000) +| _ => ret~[]; + + +// validation checks +valid(ret) >< [] => ret~True; +valid(ret) >< x:xs => (*L)valid_Cons(ret,x)~xs; + +valid_Cons(ret, int x) >< [] => ret~True; +valid_Cons(ret, int x) >< (int y):ys +| x<=y => (*L)valid_Cons(ret,y)~ys +| _ => ret~False, Eraser~ys; + +// The `Eraser' is a built-in agent defined for any agents as follows: +//Eraser >< Alpha(a1, ..., a5) => Eraser~a1, ..., Eraser~a5; + + +// Main +const LIST_ELEM=20000; + +make_RandList(rndlist)~(LIST_ELEM), +bsort(sorted)~rndlist, +valid(ret)~sorted; + +ret; diff --git a/comparison/Inpla/src/bsort-efficient-20000.in b/comparison/Inpla/src/bsort-efficient-20000.in new file mode 100644 index 0000000..c9702fe --- /dev/null +++ b/comparison/Inpla/src/bsort-efficient-20000.in @@ -0,0 +1,40 @@ +// Bubble sort +bsort(ret) >< [] => ret~[]; +bsort(ret) >< x:xs => bsort(ret)~cnt, B(cnt, x)~xs; +bsort(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 ret~(x:cnt), B(cnt, y)~ys +| _ => ret~(y:cnt), B(cnt, x)~ys; + + +// creates a random list +make_RandList(ret) >< (int n) +| n>0 => ret~(rd:cnt), make_RandList(cnt)~(n-1) + where rd=rand(10000) +| _ => ret~[]; + + +// validation checks +valid(ret) >< [] => ret~True; +valid(ret) >< x:xs => valid_Cons(ret,x)~xs; + +valid_Cons(ret, int x) >< [] => ret~True; +valid_Cons(ret, int x) >< (int y):ys +| x<=y => valid_Cons(ret,y)~ys +| _ => ret~False, Eraser~ys; + +// The `Eraser' is a built-in agent defined for any agents as follows: +//Eraser >< Alpha(a1, ..., a5) => Eraser~a1, ..., Eraser~a5; + + +// Main +const LIST_ELEM=20000; + +make_RandList(rndlist)~(LIST_ELEM), +bsort(sorted)~rndlist, +valid(ret)~sorted; + +ret; diff --git a/comparison/Inpla/src/isort-20000-reuse.in b/comparison/Inpla/src/isort-20000-reuse.in new file mode 100644 index 0000000..9d7c7ab --- /dev/null +++ b/comparison/Inpla/src/isort-20000-reuse.in @@ -0,0 +1,38 @@ +// Insertion sort +isort(ret) >< [] => ret~[]; +isort(ret) >< x:xs => (*L)I(ret, x)~cnt, (*R)isort(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; + + +// creates a random list +make_RandList(ret) >< (int n) +| n>0 => ret~(rd:cnt), (*L)make_RandList(cnt)~(n-1) + where rd=rand(10000) +| _ => ret~[]; + + +// validation checks +valid(ret) >< [] => ret~True; +valid(ret) >< x:xs => (*L)valid_Cons(ret,x)~xs; + +valid_Cons(ret, int x) >< [] => ret~True; +valid_Cons(ret, int x) >< (int y):ys +| x<=y => (*L)valid_Cons(ret,y)~ys +| _ => ret~False, Eraser~ys; + +// The `Eraser' is a built-in agent defined for any agents as follows: +//Eraser >< Alpha(a1, ..., a5) => Eraser~a1, ..., Eraser~a5; + + +// Main +const LIST_ELEM=20000; + +make_RandList(rndlist)~(LIST_ELEM), +isort(sorted)~rndlist, +valid(ret)~sorted; + +ret; diff --git a/comparison/Inpla/src/isort-20000.in b/comparison/Inpla/src/isort-20000.in new file mode 100644 index 0000000..3ed10aa --- /dev/null +++ b/comparison/Inpla/src/isort-20000.in @@ -0,0 +1,38 @@ +// Insertion sort +isort(ret) >< [] => ret~[]; +isort(ret) >< x:xs => I(ret, x)~cnt, isort(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; + + +// creates a random list +make_RandList(ret) >< (int n) +| n>0 => ret~(rd:cnt), make_RandList(cnt)~(n-1) + where rd=rand(10000) +| _ => ret~[]; + + +// validation checks +valid(ret) >< [] => ret~True; +valid(ret) >< x:xs => valid_Cons(ret,x)~xs; + +valid_Cons(ret, int x) >< [] => ret~True; +valid_Cons(ret, int x) >< (int y):ys +| x<=y => valid_Cons(ret,y)~ys +| _ => ret~False, Eraser~ys; + +// The `Eraser' is a built-in agent defined for any agents as follows: +//Eraser >< Alpha(a1, ..., a5) => Eraser~a1, ..., Eraser~a5; + + +// Main +const LIST_ELEM=20000; + +make_RandList(rndlist)~(LIST_ELEM), +isort(sorted)~rndlist, +valid(ret)~sorted; + +ret; diff --git a/comparison/OCaml/Makefile b/comparison/OCaml/Makefile index d300b15..9db7726 100644 --- a/comparison/OCaml/Makefile +++ b/comparison/OCaml/Makefile @@ -1,7 +1,7 @@ CC = ocamlopt CFLAGS = BENCHMARK = bash ../tools/sptest_commands.sh -TARGET = ack3_11 fib38 bsort40000 isort40000 qsort260000 msort260000 +TARGET = ack3_11 fib38 bsort20000 isort20000 qsort260000 msort260000 LOG = log.txt @@ -18,10 +18,10 @@ ack3_11: ack3_11.ml fib38: fib38.ml $(CC) $(CFLAGS) $< -o $@ -bsort40000: bsort40000.ml +bsort20000: bsort20000.ml $(CC) $(CFLAGS) $< -o $@ -isort40000: isort40000.ml +isort20000: isort20000.ml $(CC) $(CFLAGS) $< -o $@ qsort260000: qsort260000.ml diff --git a/comparison/OCaml/bsort20000.ml b/comparison/OCaml/bsort20000.ml new file mode 100644 index 0000000..29a369c --- /dev/null +++ b/comparison/OCaml/bsort20000.ml @@ -0,0 +1,39 @@ +open Format + +let rec bs (alist : int list) n = + match alist with + (x::y::ys) -> + if x xs;; + + +let rec go xs n = + match n with + 0 -> xs + | n -> go (bs xs n) (n-1);; + +let bsort alist = + match alist with + [] -> [] + | xs -> go xs (List.length(xs) - 1);; + + +let rec mkRandList n = + match n with + 0 -> [] + | n -> (Random.int 10000)::(mkRandList (n-1));; + + +let rec validation alist = + let rec validation_cons x blist = + match blist with + [] -> true + | y::ys -> if x<=y then (validation_cons y ys) else false + in + match alist with + [] -> true + | x::xs -> validation_cons x xs;; + + +let () = print_bool (validation (bsort (mkRandList 20000)));; diff --git a/comparison/OCaml/isort20000.ml b/comparison/OCaml/isort20000.ml new file mode 100644 index 0000000..ddcdd2a --- /dev/null +++ b/comparison/OCaml/isort20000.ml @@ -0,0 +1,36 @@ +open Format + +let rec insert x ylist = + match ylist with + [] -> [x] + | y::ys -> if x<=y + then x::y::ys + else y::(insert x ys);; + + +let rec isort (alist : int list) = + match alist with + [] -> [] + | x::xs -> insert x (isort xs);; + + + +let rec mkRandList n = + match n with + 0 -> [] + | n -> (Random.int 10000)::(mkRandList (n-1));; + + +let rec validation alist = + let rec validation_cons x blist = + match blist with + [] -> true + | y::ys -> if x<=y then (validation_cons y ys) else false + in + match alist with + [] -> true + | x::xs -> validation_cons x xs;; + + +let () = print_bool (validation (isort (mkRandList 20000)));; + diff --git a/comparison/Python/Makefile b/comparison/Python/Makefile index 21f4b3d..c77d677 100644 --- a/comparison/Python/Makefile +++ b/comparison/Python/Makefile @@ -1,5 +1,5 @@ COMMAND = python3 -TARGET = dummy.py ack3-11.py fib38.py bsort-40000.py isort-40000.py qsort-260000.py msort-260000.py +TARGET = dummy.py ack3-11.py fib38.py bsort-20000.py isort-20000.py qsort-260000.py msort-260000.py BENCHMARK = bash ../tools/sptest_scripts.sh LOG = log.txt diff --git a/comparison/Python/bsort-20000.py b/comparison/Python/bsort-20000.py new file mode 100644 index 0000000..22cc8a7 --- /dev/null +++ b/comparison/Python/bsort-20000.py @@ -0,0 +1,31 @@ +# http://www.geekviewpoint.com/python/sorting/bubblesort +import random + +def bubblesort(A): + for i in range(len(A)): + for k in range(len(A)-1, i, -1): + if (A[k] < A[k-1]): + tmp = A[k] + A[k] = A[k-1] + A[k-1] = tmp + + +def mkRandList(n): + a=[] + for i in range(1,n+1): + a.insert(0, random.randint(0,10000)) + return a + + +def validation(alist): + for i in range(len(alist)-1): + if (alist[i] > alist[i+1]): + return False + + return True + + + +a=mkRandList(20000) +bubblesort(a) +print(validation(a)) diff --git a/comparison/Python/isort-20000.py b/comparison/Python/isort-20000.py new file mode 100644 index 0000000..b37fe5d --- /dev/null +++ b/comparison/Python/isort-20000.py @@ -0,0 +1,31 @@ +import random + +def insert_sort(arr): + for i in range(1, len(arr)): + j = i - 1 + ele = arr[i] + while arr[j] > ele and j >= 0: + arr[j + 1] = arr[j] + j -= 1 + arr[j + 1] = ele + return arr + + +def mkRandList(n): + a=[] + for i in range(1,n+1): + a.insert(0, random.randint(0,10000)) + return a + + +def validation(alist): + for i in range(len(alist)-1): + if (alist[i] > alist[i+1]): + return False + + return True + + +a = mkRandList(20000) +insert_sort(a) +print(validation(a)) diff --git a/comparison/SML/Makefile b/comparison/SML/Makefile index 0e4e2e3..14dca02 100644 --- a/comparison/SML/Makefile +++ b/comparison/SML/Makefile @@ -1,5 +1,5 @@ COMMAND = sml -TARGET = dummy.sml ack3-11.sml fib38.sml bsort-40000.sml isort-40000.sml qsort-260000.sml msort-260000.sml +TARGET = dummy.sml ack3-11.sml fib38.sml bsort-20000.sml isort-20000.sml qsort-260000.sml msort-260000.sml BENCHMARK = bash ../tools/sptest_scripts.sh LOG = log.txt diff --git a/comparison/SML/bsort-20000.sml b/comparison/SML/bsort-20000.sml new file mode 100644 index 0000000..2129cd6 --- /dev/null +++ b/comparison/SML/bsort-20000.sml @@ -0,0 +1,42 @@ +(* +https://gist.github.com/masquerade0324/68f4f3fd3ab897fbe1ad +*) + +fun bs xs 0 = xs + | bs (x::y::ys) n = + if (xcount_interaction); } @@ -2335,7 +2334,8 @@ typedef enum { // These are used for translation from intermediate codes to Bytecodes OP_LABEL, OP_DEAD_CODE, OP_BEGIN_BLOCK, OP_BEGIN_JMPCNCT_BLOCK, - OP_LOAD_META // keep dest as it is + OP_LOAD_META, // keep the `dest' in `OP_LOAD_META src dest' as it is + OP_LOADI_SHARED // The same register will be assigned for the `dest`. } Code; @@ -2468,7 +2468,8 @@ void IMCode_puts(int n) { "NOP", "LABEL", "__DEAD_CODE", "BEGIN_BLOCK", "BEGIN_CNCT_BLOCK", - "LOAD_META" + "LOAD_META", + "LOADI_SHARED" }; @@ -2641,6 +2642,7 @@ void IMCode_puts(int n) { case OP_PUSHI: case OP_LOADI: case OP_EQI_R0: + case OP_LOADI_SHARED: printf("%s $%ld var%ld\n", string_opcode[imcode->opcode], imcode->operand1, imcode->operand2); break; @@ -3532,15 +3534,14 @@ void CmEnv_retrieve_MKGNAME(void) { -int CmEnv_using_reg(int localvar) { +int CmEnv_using_reg_with_nothing_info(int localvar) { #ifndef OPTIMISE_TWO_ADDRESS for (int i=0; i= VM_OFFSET_LOCALVAR) - CmEnv.tmpRegState[reg] = -1; + // if (reg >= VM_OFFSET_LOCALVAR) // removed this comment out for v0.8.2-2 + // // so, regs for meta variables are not freed. + if (reg >= VM_OFFSET_LOCALVAR) + CmEnv.tmpRegState[reg] = -1; } #endif } @@ -3843,6 +3871,10 @@ int CmEnv_Optimise_VMCode_CopyPropagation_LOADI(int target_imcode_addr) { // This optimisation will last until OP_BEGIN_BLOCK return 0; } + if (imcode->opcode == OP_LABEL) { + // This optimisation will last until OP_LABEL + return 0; + } // if (imcode->opcode == OP_BEGIN_JMPCNCT_BLOCK) { // // This optimisation will last until OP_BEGIN_BLOCK // return 0; @@ -3962,13 +3994,13 @@ int CmEnv_Optimise_VMCode_CopyPropagation(int target_imcode_addr) { load_from = IMCode[target_imcode_addr].operand1; load_to = IMCode[target_imcode_addr].operand2; - // When the given line is: LOAD src src + // When the given line is: LOAD src1 src1 if ((load_from == load_to) && (IMCode[target_imcode_addr].opcode == OP_LOAD)) { IMCode[target_imcode_addr].opcode = OP_DEAD_CODE; return 1; } - // When the given line is: LOAD_META src src + // When the given line is: LOAD_META src1 src1 if ((load_from == load_to) && (IMCode[target_imcode_addr].opcode == OP_LOAD_META)) { IMCode[target_imcode_addr].opcode = OP_DEAD_CODE; @@ -4190,6 +4222,11 @@ int CmEnv_generate_VMCode(void **code) { for (int line_num=0; line_num [reg2/reg1]. @@ -4756,6 +4793,33 @@ int CmEnv_generate_VMCode(void **code) { break; } + + case OP_LOADI_SHARED: { + // OP_LOADI int1 dest + long dest = imcode->operand2; + +#ifdef OPTIMISE_IMCODE + // dest = CmEnv_get_newreg(dest); + { + dest = CmEnv_using_reg_with_nothing_info(dest); + if (dest == -1) { + dest = CmEnv_get_newreg(imcode->operand2); + } + } +#endif + + code[addr++] = CodeAddr[OP_LOADI]; + code[addr++] = (void *)INT2FIX(imcode->operand1); + code[addr++] = (void *)(unsigned long)dest; + + break; + } + + + // OP_LOADI_META を入れよう + // META ではなく、KEEP_REG とか、OPT を遠ざける意味としよう。 + // TODO: and と or の LABEL分岐による結果導出 loadi $1 reg1, load $0 reg1 + // の reg1 を同じものに割り当てたい。だから、この KEEP_REG を使いたい case OP_PUSH: @@ -5784,13 +5848,13 @@ int Compile_expr_on_ast(Ast *ptr, int target) { if (!Compile_expr_on_ast(ptr->right, newreg2)) return 0; IMCode_genCode2(OP_JMPEQ0, newreg2, label1); - IMCode_genCode2(OP_LOADI, 1, target); + IMCode_genCode2(OP_LOADI_SHARED, 1, target); int label2 = CmEnv_get_newlabel(); IMCode_genCode1(OP_JMP, label2); IMCode_genCode1(OP_LABEL, label1); - IMCode_genCode2(OP_LOADI, 0, target); + IMCode_genCode2(OP_LOADI_SHARED, 0, target); IMCode_genCode1(OP_LABEL, label2); @@ -5819,13 +5883,13 @@ int Compile_expr_on_ast(Ast *ptr, int target) { if (!Compile_expr_on_ast(ptr->right, newreg2)) return 0; IMCode_genCode2(OP_JMPNEQ0, newreg2, label1); - IMCode_genCode2(OP_LOADI, 0, target); + IMCode_genCode2(OP_LOADI_SHARED, 0, target); int label2 = CmEnv_get_newlabel(); IMCode_genCode1(OP_JMP, label2); IMCode_genCode1(OP_LABEL, label1); - IMCode_genCode2(OP_LOADI, 1, target); + IMCode_genCode2(OP_LOADI_SHARED, 1, target); IMCode_genCode1(OP_LABEL, label2); @@ -7249,7 +7313,7 @@ int make_rule_oneway(Ast *ast) { #endif - // #define MKRULE_DEBUG + // #define MKRULE_DEBUG #ifndef MKRULE_DEBUG gencode_num += CmEnv_generate_VMCode(&code[2]); #else @@ -8674,7 +8738,8 @@ loop_a2IsFixnum: RuleTable_get_code_for_Int(a1, &code); if (code == NULL) { - // built-in + // built-in: BUILT-IN_OP >< int + switch (BASIC(a1)->id) { case ID_ADD: { @@ -8944,362 +9009,366 @@ loop_a2IsAgent: code = RuleTable_get_code(a1, a2, &result); if (result == 0) { +loop_agent_a1_a2_this_order: - - if (BASIC(a2)->id < START_ID_OF_BUILTIN_AGENT) { - // a2 is a constructor - switch (BASIC(a1)->id) { - - case ID_TUPLE0: - if (BASIC(a2)->id == ID_TUPLE0) { - // [] ~ [] --> nothing - COUNTUP_INTERACTION(vm); - - // free_Agent(a1); - // free_Agent(a2); - free_Agent2(a1, a2); - return; - } + // suppose that a2 is a constructor + switch (BASIC(a1)->id) { - break; // end ID_TUPLE0 - - - case ID_TUPLE2: - if (BASIC(a2)->id == ID_TUPLE2) { - // (x1,x2) ~ (y1,y2) --> x1~y1, x2~y2 - COUNTUP_INTERACTION(vm); + case ID_ERASER: + { + // Eps ~ Alpha(a1,...,a5) + COUNTUP_INTERACTION(vm); + + int arity = IdTable_get_arity(BASIC(a2)->id); + switch (arity) { + case 0: + { + free_Agent2(a1, a2); + return; + } - VALUE a1p1 = AGENT(a1)->port[1]; - VALUE a2p1 = AGENT(a2)->port[1]; - PUSH(vm, a1p1, a2p1); - - // free_Agent(a1); - // free_Agent(a2); - free_Agent2(a1,a2); - a1 = AGENT(a1)->port[0]; - a2 = AGENT(a2)->port[0]; - goto loop; - } - - break; // end ID_TUPLE2 - - case ID_TUPLE3: - if (BASIC(a2)->id == ID_TUPLE3) { - // (x1,x2,x3) ~ (y1,y2,y3) --> x1~y1, x2~y2, x3~y3 - COUNTUP_INTERACTION(vm); + case 1: + { + VALUE a2p0 = AGENT(a2)->port[0]; + free_Agent(a2); + a2 = a2p0; + goto loop; + } - PUSH(vm, AGENT(a1)->port[2], AGENT(a2)->port[2]); - PUSH(vm, AGENT(a1)->port[1], AGENT(a2)->port[1]); - - // free_Agent(a1); - // free_Agent(a2); - free_Agent2(a1, a2); - a1 = AGENT(a1)->port[0]; - a2 = AGENT(a2)->port[0]; - goto loop; - } - - break; // end ID_TUPLE2 - - - case ID_TUPLE4: - if (BASIC(a2)->id == ID_TUPLE4) { - // (x1,x2,x3) ~ (y1,y2,y3) --> x1~y1, x2~y2, x3~y3 - COUNTUP_INTERACTION(vm); + default: + for (int i=1; iport[1]; + VALUE eps = make_Agent(vm, ID_ERASER); + PUSH(vm, eps, a2port); + } - PUSH(vm, AGENT(a1)->port[3], AGENT(a2)->port[3]); - PUSH(vm, AGENT(a1)->port[2], AGENT(a2)->port[2]); - PUSH(vm, AGENT(a1)->port[1], AGENT(a2)->port[1]); - - // free_Agent(a1); - // free_Agent(a2); - free_Agent2(a1, a2); - a1 = AGENT(a1)->port[0]; - a2 = AGENT(a2)->port[0]; + VALUE a2p0 = AGENT(a2)->port[0]; + free_Agent(a2); + a2 = a2p0; goto loop; } + } + break; - break; // end ID_TUPLE2 - + case ID_TUPLE0: + if (BASIC(a2)->id == ID_TUPLE0) { + // [] ~ [] --> nothing + COUNTUP_INTERACTION(vm); + + // free_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); + return; + } - case ID_TUPLE5: - if (BASIC(a2)->id == ID_TUPLE5) { - // (x1,x2,x3) ~ (y1,y2,y3) --> x1~y1, x2~y2, x3~y3 - COUNTUP_INTERACTION(vm); - - PUSH(vm, AGENT(a1)->port[4], AGENT(a2)->port[4]); - PUSH(vm, AGENT(a1)->port[3], AGENT(a2)->port[3]); - PUSH(vm, AGENT(a1)->port[2], AGENT(a2)->port[2]); - PUSH(vm, AGENT(a1)->port[1], AGENT(a2)->port[1]); - - // free_Agent(a1); - // free_Agent(a2); - free_Agent2(a1, a2); - a1 = AGENT(a1)->port[0]; - a2 = AGENT(a2)->port[0]; - goto loop; - } + break; // end ID_TUPLE0 - break; // end ID_TUPLE2 - + case ID_TUPLE2: + if (BASIC(a2)->id == ID_TUPLE2) { + // (x1,x2) ~ (y1,y2) --> x1~y1, x2~y2 + COUNTUP_INTERACTION(vm); + + VALUE a1p1 = AGENT(a1)->port[1]; + VALUE a2p1 = AGENT(a2)->port[1]; + PUSH(vm, a1p1, a2p1); + + // free_Agent(a1); + // free_Agent(a2); + free_Agent2(a1,a2); + a1 = AGENT(a1)->port[0]; + a2 = AGENT(a2)->port[0]; + goto loop; + } + + break; // end ID_TUPLE2 + + case ID_TUPLE3: + if (BASIC(a2)->id == ID_TUPLE3) { + // (x1,x2,x3) ~ (y1,y2,y3) --> x1~y1, x2~y2, x3~y3 + COUNTUP_INTERACTION(vm); + + PUSH(vm, AGENT(a1)->port[2], AGENT(a2)->port[2]); + PUSH(vm, AGENT(a1)->port[1], AGENT(a2)->port[1]); + + // free_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); + a1 = AGENT(a1)->port[0]; + a2 = AGENT(a2)->port[0]; + goto loop; + } + + break; // end ID_TUPLE2 + + + case ID_TUPLE4: + if (BASIC(a2)->id == ID_TUPLE4) { + // (x1,x2,x3) ~ (y1,y2,y3) --> x1~y1, x2~y2, x3~y3 + COUNTUP_INTERACTION(vm); + + PUSH(vm, AGENT(a1)->port[3], AGENT(a2)->port[3]); + PUSH(vm, AGENT(a1)->port[2], AGENT(a2)->port[2]); + PUSH(vm, AGENT(a1)->port[1], AGENT(a2)->port[1]); + + // free_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); + a1 = AGENT(a1)->port[0]; + a2 = AGENT(a2)->port[0]; + goto loop; + } + + break; // end ID_TUPLE2 + + + case ID_TUPLE5: + if (BASIC(a2)->id == ID_TUPLE5) { + // (x1,x2,x3) ~ (y1,y2,y3) --> x1~y1, x2~y2, x3~y3 + COUNTUP_INTERACTION(vm); + + PUSH(vm, AGENT(a1)->port[4], AGENT(a2)->port[4]); + PUSH(vm, AGENT(a1)->port[3], AGENT(a2)->port[3]); + PUSH(vm, AGENT(a1)->port[2], AGENT(a2)->port[2]); + PUSH(vm, AGENT(a1)->port[1], AGENT(a2)->port[1]); + + // free_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); + a1 = AGENT(a1)->port[0]; + a2 = AGENT(a2)->port[0]; + goto loop; + } + + break; // end ID_TUPLE2 + + + case ID_NIL: + if (BASIC(a2)->id == ID_NIL) { + // [] ~ [] --> nothing + COUNTUP_INTERACTION(vm); + + // free_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); + + return; + } + + break; // end ID_NIL + + + case ID_CONS: + if (BASIC(a2)->id == ID_CONS) { + // a:b ~ c:d --> a~c, b~d + COUNTUP_INTERACTION(vm); + + VALUE a1p1 = AGENT(a1)->port[1]; + VALUE a2p1 = AGENT(a2)->port[1]; + PUSH(vm, a1p1, a2p1); + + // free_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); + a1 = AGENT(a1)->port[0]; + a2 = AGENT(a2)->port[0]; + goto loop; + } + + break; // end ID_CONS + + + + // built-in funcAgent for lists and tuples + case ID_APPEND: + switch (BASIC(a2)->id) { case ID_NIL: - if (BASIC(a2)->id == ID_NIL) { - // [] ~ [] --> nothing + { + // App(r,a) >< [] => r~a; COUNTUP_INTERACTION(vm); - // free_Agent(a1); - // free_Agent(a2); + VALUE a1p0 = AGENT(a1)->port[0]; + VALUE a1p1 = AGENT(a1)->port[1]; + // free_Agent(a1); + // free_Agent(a2); free_Agent2(a1, a2); - - return; + a1=a1p0; + a2=a1p1; + goto loop; } - - break; // end ID_NIL - - + case ID_CONS: - if (BASIC(a2)->id == ID_CONS) { - // a:b ~ c:d --> a~c, b~d + { + // App(r,a) >< [x|xs] => r~(*R)[x|w], (*L)App(w,a)~xs; COUNTUP_INTERACTION(vm); - VALUE a1p1 = AGENT(a1)->port[1]; + VALUE a1p0 = AGENT(a1)->port[0]; VALUE a2p1 = AGENT(a2)->port[1]; - PUSH(vm, a1p1, a2p1); - - // free_Agent(a1); - // free_Agent(a2); - free_Agent2(a1, a2); - a1 = AGENT(a1)->port[0]; - a2 = AGENT(a2)->port[0]; + VALUE w = make_Name(vm); + + AGENT(a2)->port[1] = w; + PUSH(vm, a1p0, a2); + //VM_EQStack_Push(vm, a1p1, a2); + + AGENT(a1)->port[0] = w; + a2 = a2p1; goto loop; } + } - break; // end ID_CONS - - + break; // end ID_APPEND - // built-in funcAgent for lists and tuples - case ID_APPEND: - switch (BASIC(a2)->id) { - case ID_NIL: - { - // App(r,a) >< [] => r~a; - COUNTUP_INTERACTION(vm); + + case ID_MERGER: + switch (BASIC(a2)->id) { + case ID_TUPLE2: + { + // MG(r) ~ (a|b) => *MGp(*r)~a, *MGp(*r)~b + COUNTUP_INTERACTION(vm); - VALUE a1p0 = AGENT(a1)->port[0]; - VALUE a1p1 = AGENT(a1)->port[1]; - // free_Agent(a1); - // free_Agent(a2); - free_Agent2(a1, a2); - a1=a1p0; - a2=a1p1; - goto loop; - } - - case ID_CONS: - { - // App(r,a) >< [x|xs] => r~(*R)[x|w], (*L)App(w,a)~xs; - COUNTUP_INTERACTION(vm); - - VALUE a1p0 = AGENT(a1)->port[0]; - VALUE a2p1 = AGENT(a2)->port[1]; - VALUE w = make_Name(vm); + BASIC(a1)->id = ID_MERGER_P; + AGENT(a1)->port[1] = (VALUE)NULL; + AGENT(a1)->port[2] = (VALUE)NULL; + PUSH(vm, a1, AGENT(a2)->port[1]); + PUSH(vm, a1, AGENT(a2)->port[0]); + free_Agent(a2); + return; - AGENT(a2)->port[1] = w; - PUSH(vm, a1p0, a2); - //VM_EQStack_Push(vm, a1p1, a2); - AGENT(a1)->port[0] = w; - a2 = a2p1; - goto loop; - } } - - break; // end ID_APPEND - + } + break; // end ID_MG - case ID_MERGER: - switch (BASIC(a2)->id) { - case ID_TUPLE2: - { - // MG(r) ~ (a|b) => *MGp(*r)~a, *MGp(*r)~b - COUNTUP_INTERACTION(vm); + case ID_MERGER_P: + switch (BASIC(a2)->id) { + case ID_NIL: + // *MGP(r)~[] +#ifndef THREAD + + COUNTUP_INTERACTION(vm); + + if (AGENT(a1)->port[1] == (VALUE)NULL) { + AGENT(a1)->port[1] = a2; + return; + } else { + VALUE a1p0 = AGENT(a1)->port[0]; + // free_Agent(AGENT(a1)->port[1]); + // free_Agent(a1); + free_Agent2(AGENT(a1)->port[1], a1); + + a1 = a1p0; + goto loop; + } +#else + // AGENT(a1)->port[2] is used as a lock for NIL case + if (AGENT(a1)->port[2] == (VALUE)NULL) { + if (!(__sync_bool_compare_and_swap(&(AGENT(a1)->port[2]), + NULL, a2))) { + // something exists already + goto loop; - BASIC(a1)->id = ID_MERGER_P; - AGENT(a1)->port[1] = (VALUE)NULL; - AGENT(a1)->port[2] = (VALUE)NULL; - PUSH(vm, a1, AGENT(a2)->port[1]); - PUSH(vm, a1, AGENT(a2)->port[0]); - free_Agent(a2); + } else { return; - - } + } else if ((AGENT(a1)->port[2] != (VALUE)NULL) && + (BASIC(AGENT(a1)->port[2])->id == ID_NIL)) { + + COUNTUP_INTERACTION(vm); + + VALUE a1p0 = AGENT(a1)->port[0]; + // free_Agent(AGENT(a1)->port[2]); + // free_Agent(a1); + free_Agent2(AGENT(a1)->port[2], a1); + a1 = a1p0; + goto loop; + } else { + goto loop; } - break; // end ID_MG - - case ID_MERGER_P: - switch (BASIC(a2)->id) { - case ID_NIL: - // *MGP(r)~[] + +#endif + case ID_CONS: + // *MGP(r)~x:xs => r~x:w, *MGP(w)~xs; + { #ifndef THREAD - + COUNTUP_INTERACTION(vm); - if (AGENT(a1)->port[1] == (VALUE)NULL) { - AGENT(a1)->port[1] = a2; - return; - } else { - VALUE a1p0 = AGENT(a1)->port[0]; - // free_Agent(AGENT(a1)->port[1]); - // free_Agent(a1); - free_Agent2(AGENT(a1)->port[1], a1); - - a1 = a1p0; - goto loop; - } + VALUE a1p0 = AGENT(a1)->port[0]; + VALUE w = make_Name(vm); + AGENT(a1)->port[0] = w; + PUSH(vm, a1, AGENT(a2)->port[1]); + + AGENT(a2)->port[1] = w; + a1 = a1p0; + goto loop; #else + // AGENT(a1)->port[1] is used as a lock for CONS case // AGENT(a1)->port[2] is used as a lock for NIL case - if (AGENT(a1)->port[2] == (VALUE)NULL) { - if (!(__sync_bool_compare_and_swap(&(AGENT(a1)->port[2]), - NULL, a2))) { - // something exists already - goto loop; - - } else { - return; - } - } else if ((AGENT(a1)->port[2] != (VALUE)NULL) && - (BASIC(AGENT(a1)->port[2])->id == ID_NIL)) { - + + if (AGENT(a1)->port[2] != (VALUE)NULL) { + // The other MGP finished still, so: + // *MGP(r)~x:xs => r~x:xs; + COUNTUP_INTERACTION(vm); VALUE a1p0 = AGENT(a1)->port[0]; - // free_Agent(AGENT(a1)->port[2]); - // free_Agent(a1); - free_Agent2(AGENT(a1)->port[2], a1); + // free_Agent(AGENT(a1)->port[2]); // free the lock for NIL + // free_Agent(a1); + free_Agent2(AGENT(a1)->port[2], a1); a1 = a1p0; goto loop; - } else { - goto loop; - } - -#endif - case ID_CONS: - // *MGP(r)~x:xs => r~x:w, *MGP(w)~xs; - { -#ifndef THREAD - + + } else if (AGENT(a1)->port[1] == (VALUE)NULL) { + if (!(__sync_bool_compare_and_swap(&(AGENT(a1)->port[1]), + NULL, + a2))) { + // Failure to be locked. + goto loop; + } + + // Succeed the lock COUNTUP_INTERACTION(vm); - VALUE a1p0 = AGENT(a1)->port[0]; + VALUE a1p0 = AGENT(a1)->port[0]; VALUE w = make_Name(vm); AGENT(a1)->port[0] = w; PUSH(vm, a1, AGENT(a2)->port[1]); AGENT(a2)->port[1] = w; - a1 = a1p0; - goto loop; -#else - // AGENT(a1)->port[1] is used as a lock for CONS case - // AGENT(a1)->port[2] is used as a lock for NIL case - - if (AGENT(a1)->port[2] != (VALUE)NULL) { - // The other MGP finished still, so: - // *MGP(r)~x:xs => r~x:xs; - - COUNTUP_INTERACTION(vm); - - VALUE a1p0 = AGENT(a1)->port[0]; - // free_Agent(AGENT(a1)->port[2]); // free the lock for NIL - // free_Agent(a1); - free_Agent2(AGENT(a1)->port[2], a1); - a1 = a1p0; - goto loop; - - } else if (AGENT(a1)->port[1] == (VALUE)NULL) { - if (!(__sync_bool_compare_and_swap(&(AGENT(a1)->port[1]), - NULL, - a2))) { - // Failure to be locked. - goto loop; - } - - // Succeed the lock - COUNTUP_INTERACTION(vm); - - VALUE a1p0 = AGENT(a1)->port[0]; - VALUE w = make_Name(vm); - AGENT(a1)->port[0] = w; - PUSH(vm, a1, AGENT(a2)->port[1]); - - AGENT(a2)->port[1] = w; - - AGENT(a1)->port[1] = (VALUE)NULL; // free the lock - - a1 = a1p0; - - goto loop; - - } else { - // MPG works for the other now. - - goto loop; - } + AGENT(a1)->port[1] = (VALUE)NULL; // free the lock -#endif - } - } - break; // end ID_MERGER_P - - - } // end switch(BASIC(a1)->id) - - } else { - // a2 is not a constructor - - switch (BASIC(a1)->id) { - case ID_ERASER: - { - // Eps ~ Alpha(a1,...,a5) - COUNTUP_INTERACTION(vm); - - int arity = IdTable_get_arity(BASIC(a2)->id); - switch (arity) { - case 0: - { - free_Agent2(a1, a2); - return; - } + a1 = a1p0; - case 1: - { - VALUE a2p0 = AGENT(a2)->port[0]; - free_Agent(a2); - a2 = a2p0; - goto loop; - } + goto loop; - default: - for (int i=1; iport[1]; - VALUE eps = make_Agent(vm, ID_ERASER); - PUSH(vm, eps, a2port); - } + } else { + // MPG works for the other now. - VALUE a2p0 = AGENT(a2)->port[0]; - free_Agent(a2); - a2 = a2p0; goto loop; } + + +#endif } - break; // end case ID_ERASER } - } + break; // end ID_MERGER_P + + + } // end switch(BASIC(a1)->id) + + + if ((BASIC(a1)->id < BASIC(a2)->id) + || (BASIC(a2)->id == ID_ERASER)){ + VALUE tmp; + tmp = a1; + a1 = a2; + a2 = tmp; + goto loop_agent_a1_a2_this_order; + } + printf("Runtime Error: There is no interaction rule for the following pair:\n "); puts_term(a1); @@ -9620,15 +9689,13 @@ int exec(Ast *at) { CmEnv_retrieve_MKGNAME(); CmEnv_generate_VMCode(code); - /* - // for debug - CmEnv_retrieve_MKGNAME(); - IMCode_puts(0); //exit(1); - - int codenum = CmEnv_generate_VMCode(code); - VMCode_puts(code, codenum-2); //exit(1); - // end for debug - */ + // // for debug + // CmEnv_retrieve_MKGNAME(); + // IMCode_puts(0); //exit(1); + // + // int codenum = CmEnv_generate_VMCode(code); + // VMCode_puts(code, codenum-2); //exit(1); + // // end for debug #ifdef COUNT_MKAGENT NumberOfMkAgent=0; @@ -9671,7 +9738,7 @@ int exec(Ast *at) { time=stop_timer(&t); #ifdef COUNT_INTERACTION - printf("(%d interactions, %.2f sec)\n", VM_Get_InteractionCount(&VM), + printf("(%lu interactions, %.2f sec)\n", VM_Get_InteractionCount(&VM), (double)(time)/1000000); #else printf("(%.2f sec)\n", -- cgit v1.2.3