From eddac153a064648bee2aef6fb733ab6820bb96c3 Mon Sep 17 00:00:00 2001 From: Shinya Sato Date: Thu, 28 Apr 2022 21:41:58 +0900 Subject: v0.8.2 --- Changelog.md | 26 ++++- README.md | 61 ++++++---- comparison/Haskell/bsort-40000.hs | 10 +- comparison/Haskell/isort-40000.hs | 10 +- comparison/Haskell/msort-800000.hs | 12 +- comparison/Haskell/qsort-800000.hs | 12 +- comparison/Inpla/src/bsort-40000-reuse.in | 35 ++++-- comparison/Inpla/src/bsort-40000.in | 35 ++++-- comparison/Inpla/src/isort-40000-reuse.in | 34 ++++-- comparison/Inpla/src/isort-40000.in | 34 ++++-- comparison/Inpla/src/msort-800000-reuse.in | 59 ++++++---- comparison/Inpla/src/msort-800000.in | 59 ++++++---- comparison/Inpla/src/qsort-800000-reuse.in | 46 +++++--- comparison/Inpla/src/qsort-800000.in | 46 +++++--- comparison/OCaml/bsort40000.ml | 14 ++- comparison/OCaml/isort40000.ml | 22 ++-- comparison/OCaml/msort800000.ml | 16 ++- comparison/OCaml/qsort800000.ml | 18 ++- comparison/Python/bsort-40000.py | 13 ++- comparison/Python/isort-40000.py | 11 +- comparison/Python/msort-800000.py | 11 +- comparison/Python/qsort-800000.py | 12 +- comparison/SML/bsort-40000.sml | 17 ++- comparison/SML/isort-40000.sml | 21 +++- comparison/SML/msort-800000.sml | 15 ++- comparison/SML/qsort-800000.sml | 20 +++- pic/benchmark_reuse_v0.8.2.png | Bin 0 -> 29036 bytes pic/eraser.png | Bin 0 -> 8663 bytes sample/hanoi.in | 11 +- src/id_table.c | 51 ++------ src/id_table.h | 4 +- src/inpla.y | 182 ++++++++++++++++++++++------- 32 files changed, 657 insertions(+), 260 deletions(-) create mode 100644 pic/benchmark_reuse_v0.8.2.png create mode 100644 pic/eraser.png diff --git a/Changelog.md b/Changelog.md index 63e8670..bb96607 100644 --- a/Changelog.md +++ b/Changelog.md @@ -1,14 +1,36 @@ # Change log +### v0.8.2 (released on 28 April 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.83](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.39](comparison/Inpla/src/fib-38.in) | [0.40](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) | [**2.98**](comparison/Inpla/src/bsort-40000.in) | [2.48](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.21](comparison/Inpla/src/isort-40000-reuse.in) | +| qsort 800000 | [1.56](comparison/Haskell/qsort-800000.hs) | [-](comparison/OCaml/qsort800000.ml) | [1.14](comparison/SML/qsort-800000.sml) | [97.37](comparison/Python/qsort-800000.py) | [0.66](comparison/Inpla/src/qsort-800000.in) | [**0.37**](comparison/Inpla/src/qsort-800000-reuse.in) | +| msort 800000 | [1.55](comparison/Haskell/msort-800000.hs) | [-](comparison/OCaml/msort800000.ml) | [1.04](comparison/SML/msort-800000.sml) | [100.04](comparison/Python/msort-800000.py) | [0.48](comparison/Inpla/src/msort-800000.in) | [**0.35**](comparison/Inpla/src/msort-800000-reuse.in) | + +#### New Features + +* **A built-in agent** `Eraser`: it disposes any nets gradually with the following rules: + +![Eraser](pic/eraser.png) + +#### Bug fix +* **The benchmark table was wrong**: With respect to the results in Haskell, the execution times of sort works were too short due to its lazy evaluation strategy. To solve it, every sort work will be followed by a validation check if a given list is correctly sorted, not only in Haskell but also in others. + + + ### v0.8.1-2 minor update (released on 16 April 2022) #### Bug fix -* Integer numbers had been put out with 32-bit format, though it is manages as 61bit FIXINT. Now it is put out as a long integer. +* **Output format of integers**: Integer numbers had been outputted with 32-bit format, though it is manages as 61bit FIXINT. Now these are looked as long integers. #### Polished -* Several OCaml execution times have been added to the benchmark table. These programs are stored in `comparison/OCaml`. +* **The benchmark table**: Several OCaml execution times have been added to the benchmark table. These programs are stored in `comparison/OCaml`. diff --git a/README.md b/README.md index 43dcc55..db1560d 100644 --- a/README.md +++ b/README.md @@ -6,18 +6,18 @@ 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.1-2 (minor update) released on **16 April 2022**. (See [Changelog.md](Changelog.md) for details.) +* The current version is 0.8.2, released on **28 April 2022**. (See [Changelog.md](Changelog.md) for details.) -![speedup-ratio](pic/benchmark_reuse_v0.8.1.png) +![speedup-ratio](pic/benchmark_reuse_v0.8.2.png) | | Haskell | OCaml | SML | Python | Inpla8 | Inpla8r | | -------------- | :------: | :------: | :----: | :----: | :------: | :------: | -| ack(3,11) | [2.31](comparison/Haskell/ack3-11.hs) | [0.46](comparison/OCaml/ack3_11.ml) | [**0.41**](comparison/SML/ack3-11.sml) | [-](comparison/Python/ack3-11.py) | [0.82](comparison/Inpla/src/ack-stream_3-11.in) | [0.70](comparison/Inpla/src/ack-stream_3-11-reuse.in) | -| fib 38 | [1.60](comparison/Haskell/fib38.hs) | [**0.15**](comparison/OCaml/fib38.ml) | [0.26](comparison/SML/fib38.sml) | [8.49](comparison/Python/fib38.py) | [0.38](comparison/Inpla/src/fib-38.in) | [0.40](comparison/Inpla/src/fib-38-reuse.in) | -| bsort 40000 | [34.81](comparison/Haskell/bsort-40000.hs) | [35.52](comparison/OCaml/bsort40000.ml) | [11.17](comparison/SML/bsort-40000.sml) | [76.72](comparison/Python/bsort-40000.py) | [3.03](comparison/Inpla/src/bsort-40000.in) | [**2.42**](comparison/Inpla/src/bsort-40000-reuse.in) | -| isort 40000 | [**0.02**](comparison/Haskell/isort-40000.hs) | [7.44](comparison/OCaml/isort40000.ml) | [2.97](comparison/SML/isort-40000.sml) | [36.63](comparison/Python/isort-40000.py) | [1.18](comparison/Inpla/src/isort-40000.in) | [1.18](comparison/Inpla/src/isort-40000-reuse.in) | -| qsort 800000 | [**0.15**](comparison/Haskell/qsort-800000.hs) | [-](comparison/OCaml/qsort800000.ml) | [1.16](comparison/SML/qsort-800000.sml) | [97.30](comparison/Python/qsort-800000.py) | [0.61](comparison/Inpla/src/qsort-800000.in) | [0.35](comparison/Inpla/src/qsort-800000-reuse.in) | -| msort 800000 | [0.46](comparison/Haskell/msort-800000.hs) | [-](comparison/OCaml/msort800000.ml) | [1.00](comparison/SML/msort-800000.sml) | [98.27](comparison/Python/msort-800000.py) | [0.48](comparison/Inpla/src/msort-800000.in) | [**0.35**](comparison/Inpla/src/msort-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.83](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.39](comparison/Inpla/src/fib-38.in) | [0.40](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) | [**2.98**](comparison/Inpla/src/bsort-40000.in) | [2.48](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.21](comparison/Inpla/src/isort-40000-reuse.in) | +| qsort 800000 | [1.56](comparison/Haskell/qsort-800000.hs) | [-](comparison/OCaml/qsort800000.ml) | [1.14](comparison/SML/qsort-800000.sml) | [97.37](comparison/Python/qsort-800000.py) | [0.66](comparison/Inpla/src/qsort-800000.in) | [**0.37**](comparison/Inpla/src/qsort-800000-reuse.in) | +| msort 800000 | [1.55](comparison/Haskell/msort-800000.hs) | [-](comparison/OCaml/msort800000.ml) | [1.04](comparison/SML/msort-800000.sml) | [100.04](comparison/Python/msort-800000.py) | [0.48](comparison/Inpla/src/msort-800000.in) | [**0.35**](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. @@ -29,7 +29,7 @@ Inpla is a multi-threaded parallel interpreter of interaction nets. Once you wri - "fib 38" is computation to get the 38th Fibonacci number. - - "bsort *n*", "isort *n*", "qsort *n*" and "msort *n*" are computation of bubble sort, insertion sort, quick sort and merge sort for random *n*-element lists, respectively. The blanks in OCaml are due to the following error: `Stack overflow during evaluation (looping recursion?).` + - "bsort *n*", "isort *n*", "qsort *n*" and "msort *n*" are computation of bubble sort, insertion sort, quick sort and merge sort for random *n*-element lists, respectively, followed by a validation check process. The blanks in OCaml are due to the following error: `Fatal error: exception Stack_overflow` @@ -479,26 +479,17 @@ Inpla has built-in agents: ### Tuples -* `Tuple0`, `Tuple2(x1,x2)`, `Tuple3(x1,x2,x2)`, `Tuple4(x1,x2,x3,x4)`, `Tuple5(x1,x2,x3,x4,x5)`, - are written as - `()`, `(x1,x2)`, `(x1,x2,x3)`, `(x1,x2,x3,x4)`, `(x1,x2,x3,x4,x5)`. +* `Tuple0`, `Tuple2(x1,x2)`, `Tuple3(x1,x2,x2)`, `Tuple4(x1,x2,x3,x4)`, `Tuple5(x1,x2,x3,x4,x5)`, written as `()`, `(x1,x2)`, `(x1,x2,x3)`, `(x1,x2,x3,x4)`, `(x1,x2,x3,x4,x5)`, respectively. * There is no Tuple1, and so `(x)` is evaluated as just `x`. ### Lists -* `Nil`, `Cons(x,xs)` - are written as - `[]` and `x:xs`, respectively. -* A nested `Cons` that terminated at `Nil` is written as a list notation using brackets `[` and `]`. For instance, - `x1 : x2: x3 : Nil` - is written as - `[x1,x2,x3]` . +* `Nil`, `Cons(x,xs)`, written as `[]` and `x:xs`, respectively. +* A nested `Cons` that is terminated at `Nil` is written as a list notation using brackets `[` and `]`. For instance, `x1 : x2: x3 : Nil` is written as `[x1,x2,x3]` . - - -### Built-in rules for tuples and lists +#### Built-in rules for tuples and lists There are built-in rules for pairs of the same built-in agents that match and connect each element such that: @@ -539,7 +530,33 @@ Append(r, listB) ~ listA --> r ~ (listA ++ listB) // pseudo code >>> ``` +* We also have a built-in abbreviation for the Append to denote the operation naturally: + ``` + >>> r << Append([A,B,C], [Z, S(Z)]); + (4 interactions, 0.00 sec) + >>> r; + [A,B,C,Z,S(Z)] + >>> free x1 x2 y1 y2 y3 r; + >>> + ``` + + + +### Eraser + +* Eraser agent `Eraser` removes any nets gragually: + ![Eraser](pic/eraser.png) + ``` + >>> Eraser ~ A(x1,x2); + (1 interactions, 0.00 sec) + >>> x1 x2 + Eraser Eraser + >>> free x1 x2; + >>> + ``` + + ## Attributes (integers) Agents can be extended so that these can have integers in their ports. These integers are called *attributes*. diff --git a/comparison/Haskell/bsort-40000.hs b/comparison/Haskell/bsort-40000.hs index 401ceaf..90f208c 100644 --- a/comparison/Haskell/bsort-40000.hs +++ b/comparison/Haskell/bsort-40000.hs @@ -30,7 +30,15 @@ randomList n = do 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 40000 let sorted = bsort list - print (take 10 sorted) + print (validation sorted) diff --git a/comparison/Haskell/isort-40000.hs b/comparison/Haskell/isort-40000.hs index 1abc148..68200af 100644 --- a/comparison/Haskell/isort-40000.hs +++ b/comparison/Haskell/isort-40000.hs @@ -25,7 +25,15 @@ randomList n = do 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 40000 let sorted = isort list - print (take 10 sorted) + print (validation sorted) diff --git a/comparison/Haskell/msort-800000.hs b/comparison/Haskell/msort-800000.hs index eb1a24d..65a5807 100644 --- a/comparison/Haskell/msort-800000.hs +++ b/comparison/Haskell/msort-800000.hs @@ -28,6 +28,7 @@ msort xs = merge (msort m, msort n) main = print $ msort [3,2,8,5] -} + randomList :: Int -> IO([Int]) randomList 0 = return [] randomList n = do @@ -36,10 +37,15 @@ randomList n = do 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 800000 let sorted = msort list - print (take 10 sorted) - - + print (validation sorted) diff --git a/comparison/Haskell/qsort-800000.hs b/comparison/Haskell/qsort-800000.hs index 2a9d60d..72f7a03 100644 --- a/comparison/Haskell/qsort-800000.hs +++ b/comparison/Haskell/qsort-800000.hs @@ -15,10 +15,12 @@ part pivot (x:xs) where (below, above) = part pivot xs + {- main = print $ qsort [3,2,8,5] -} + randomList :: Int -> IO([Int]) randomList 0 = return [] randomList n = do @@ -27,7 +29,15 @@ randomList n = do 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 800000 let sorted = qsort list - print (take 10 sorted) + print (validation sorted) diff --git a/comparison/Inpla/src/bsort-40000-reuse.in b/comparison/Inpla/src/bsort-40000-reuse.in index 3abd0ec..5908f83 100644 --- a/comparison/Inpla/src/bsort-40000-reuse.in +++ b/comparison/Inpla/src/bsort-40000-reuse.in @@ -1,7 +1,7 @@ // Bubble sort -BS(ret) >< [] => ret~[]; -BS(ret) >< x:xs => (*L)BS(ret)~cnt, (*R)B(cnt, x)~xs; -BS(ret) >< M(x) => ret~x; +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); @@ -10,14 +10,31 @@ B(ret, int x) >< (int 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~False; +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=40000; -MkRandList(ret) >< (int n) -| n>0 => ret~(rd:cnt), (*L)MkRandList(cnt)~(n-1) - where rd=rand(10000) -| _ => ret~[]; +make_RandList(rndlist)~(LIST_ELEM), +bsort(sorted)~rndlist, +valid(ret)~sorted; -MkRandList(cnt)~(LIST_ELEM), -BS(ret)~cnt; ret; diff --git a/comparison/Inpla/src/bsort-40000.in b/comparison/Inpla/src/bsort-40000.in index d0a5e1c..d3c8267 100644 --- a/comparison/Inpla/src/bsort-40000.in +++ b/comparison/Inpla/src/bsort-40000.in @@ -1,7 +1,7 @@ // Bubble sort -BS(ret) >< [] => ret~[]; -BS(ret) >< x:xs => BS(ret)~cnt, B(cnt, x)~xs; -BS(ret) >< M(x) => ret~x; +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); @@ -10,14 +10,31 @@ B(ret, int x) >< (int 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~False; +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=40000; -MkRandList(ret) >< (int n) -| n>0 => ret~(rd:cnt), MkRandList(cnt)~(n-1) - where rd=rand(10000) -| _ => ret~[]; +make_RandList(rndlist)~(LIST_ELEM), +bsort(sorted)~rndlist, +valid(ret)~sorted; -MkRandList(cnt)~(LIST_ELEM), -BS(ret)~cnt; ret; diff --git a/comparison/Inpla/src/isort-40000-reuse.in b/comparison/Inpla/src/isort-40000-reuse.in index 3e7e2d2..1f7153d 100644 --- a/comparison/Inpla/src/isort-40000-reuse.in +++ b/comparison/Inpla/src/isort-40000-reuse.in @@ -1,6 +1,6 @@ // Insertion sort -IS(ret) >< [] => ret~[]; -IS(ret) >< x:xs => (*L)I(ret, x)~cnt, (*R)IS(cnt)~xs; +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 @@ -8,13 +8,31 @@ I(ret, int x) >< (int 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) +// 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~[]; -MkRandList(cnt)~(LIST_ELEM), -IS(ret)~cnt; + +// validation checks +valid(ret) >< [] => ret~False; +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=40000; + +make_RandList(rndlist)~(LIST_ELEM), +isort(sorted)~rndlist, +valid(ret)~sorted; + ret; diff --git a/comparison/Inpla/src/isort-40000.in b/comparison/Inpla/src/isort-40000.in index 295f6f4..0e3ed32 100644 --- a/comparison/Inpla/src/isort-40000.in +++ b/comparison/Inpla/src/isort-40000.in @@ -1,6 +1,6 @@ // Insertion sort -IS(ret) >< [] => ret~[]; -IS(ret) >< x:xs => I(ret, x)~cnt, IS(cnt)~xs; +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 @@ -8,13 +8,31 @@ I(ret, int x) >< (int 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) +// creates a random list +make_RandList(ret) >< (int n) +| n>0 => ret~(rd:cnt), make_RandList(cnt)~(n-1) where rd=rand(10000) | _ => ret~[]; -MkRandList(cnt)~(LIST_ELEM), -IS(ret)~cnt; + +// validation checks +valid(ret) >< [] => ret~False; +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=40000; + +make_RandList(rndlist)~(LIST_ELEM), +isort(sorted)~rndlist, +valid(ret)~sorted; + ret; diff --git a/comparison/Inpla/src/msort-800000-reuse.in b/comparison/Inpla/src/msort-800000-reuse.in index 5f57484..4572623 100644 --- a/comparison/Inpla/src/msort-800000-reuse.in +++ b/comparison/Inpla/src/msort-800000-reuse.in @@ -1,34 +1,51 @@ // Merge sort -MS(ret) >< [] => ret~[]; -MS(ret) >< x:xs => (*L)MS_tail(ret, x)~xs; +msort(ret) >< [] => ret~[]; +msort(ret) >< x:xs => (*L)msort_tail(ret, x)~xs; -MS_tail(ret, int n) >< [] => ret~[n]; -MS_tail(ret, int n) >< x:xs => - Split(left,right) ~ (*R)(n:x:xs), - MS(a)~left, MS(b)~right, (*L)Merge(ret,b)~a; +msort_tail(ret, int n) >< [] => ret~[n]; +msort_tail(ret, int n) >< x:xs => + split(left,right) ~ (*R)(n:x:xs), + msort(a)~left, msort(b)~right, (*L)merge(ret,b)~a; -Merge(ret, snd) >< [] => ret~snd; -Merge(ret, snd) >< x:xs => (*L)MergeCC(ret, x, xs)~snd; +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; +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; -Split(right,left) >< [] => right~[], left~[]; -Split(right,left) >< x:xs => - right~(*R)(x:cntl), left~cntr, (*L)Split(cntr,cntl)~xs; +split(right,left) >< [] => right~[], left~[]; +split(right,left) >< x:xs => + right~(*R)(x:cntl), left~cntr, (*L)split(cntr,cntl)~xs; +// 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~False; +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=800000; -MkRandList(ret) >< (int n) -| n>0 => ret~(rd:cnt), (*L)MkRandList(cnt)~(n-1) - where rd=rand(10000) -| _ => ret~[]; +make_RandList(rndlist)~(LIST_ELEM), +msort(sorted)~rndlist, +valid(ret)~sorted; -MkRandList(cnt)~(LIST_ELEM), -MS(ret)~cnt; ret; diff --git a/comparison/Inpla/src/msort-800000.in b/comparison/Inpla/src/msort-800000.in index b77f353..3c43aa6 100644 --- a/comparison/Inpla/src/msort-800000.in +++ b/comparison/Inpla/src/msort-800000.in @@ -1,34 +1,51 @@ // Merge sort -MS(ret) >< [] => ret~[]; -MS(ret) >< x:xs => MS_tail(ret, x)~xs; +msort(ret) >< [] => ret~[]; +msort(ret) >< x:xs => msort_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; +msort_tail(ret, int n) >< [] => ret~[n]; +msort_tail(ret, int n) >< x:xs => + split(left,right) ~ (n:x:xs), + msort(a)~left, msort(b)~right, merge(ret,b)~a; -Merge(ret, snd) >< [] => ret~snd; -Merge(ret, snd) >< x:xs => MergeCC(ret, x, xs)~snd; +merge(ret, snd) >< [] => ret~snd; +merge(ret, snd) >< x:xs => mergeCC(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; +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; +split(right,left) >< [] => right~[], left~[]; +split(right,left) >< x:xs => + right~(x:cntl), left~cntr, split(cntr,cntl)~xs; +// 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~False; +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=800000; -MkRandList(ret) >< (int n) -| n>0 => ret~(rd:cnt), MkRandList(cnt)~(n-1) - where rd=rand(10000) -| _ => ret~[]; +make_RandList(rndlist)~(LIST_ELEM), +msort(sorted)~rndlist, +valid(ret)~sorted; -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 index 810e446..7f41045 100644 --- a/comparison/Inpla/src/qsort-800000-reuse.in +++ b/comparison/Inpla/src/qsort-800000-reuse.in @@ -1,26 +1,44 @@ // Quick sort -QS(ret) >< [] => ret~(*R)[]; -QS(ret) >< (int x):xs => - (*R)Part(x, left, right)~xs, - (*L)QS(cntl)~left, QS(cntr)~right, +qsort(ret) >< [] => ret~(*R)[]; +qsort(ret) >< (int x):xs => + (*R)part(x, left, right)~xs, + (*L)qsort(cntl)~left, qsort(cntr)~right, Append(ret, x:cntl)~cntr; // Note: `Append' is implemented as built-in. -Part(int x, a, b) >< [] => a~(*L)[], b~(*R)[]; -Part(int x, a, b) >< (int y):ys -| y b~(*R)(y:cnt), (*L)Part(x, a, cnt)~ys -| _ => a~(*R)(y:cnt), (*L)Part(x, cnt, b)~ys; +part(int x, a, b) >< [] => a~(*L)[], b~(*R)[]; +part(int x, a, b) >< (int y):ys +| y 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) +// 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~[]; -MkRandList(cnt)~(LIST_ELEM), -QS(ret)~cnt; + +// validation checks +valid(ret) >< [] => ret~False; +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=800000; + +make_RandList(rndlist)~(LIST_ELEM), +qsort(sorted)~rndlist, +valid(ret)~sorted; + ret; diff --git a/comparison/Inpla/src/qsort-800000.in b/comparison/Inpla/src/qsort-800000.in index 8226655..6d28245 100644 --- a/comparison/Inpla/src/qsort-800000.in +++ b/comparison/Inpla/src/qsort-800000.in @@ -1,26 +1,44 @@ // Quick sort -QS(ret) >< [] => ret~[]; -QS(ret) >< (int x):xs => - Part(x, left, right)~xs, - QS(cntl)~left, QS(cntr)~right, +qsort(ret) >< [] => ret~[]; +qsort(ret) >< (int x):xs => + part(x, left, right)~xs, + qsort(cntl)~left, qsort(cntr)~right, Append(ret, x:cntl)~cntr; // Note: `Append' is implemented as built-in. -Part(int x, a, b) >< [] => a~[], b~[]; -Part(int x, a, b) >< (int y):ys -| y b~(y:cnt), Part(x, a, cnt)~ys -| _ => a~(y:cnt), Part(x, cnt, b)~ys; +part(int x, a, b) >< [] => a~[], b~[]; +part(int x, a, b) >< (int y):ys +| y 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) +// creates a random list +make_RandList(ret) >< (int n) +| n>0 => ret~(rd:cnt), make_RandList(cnt)~(n-1) where rd=rand(10000) | _ => ret~[]; -MkRandList(cnt)~(LIST_ELEM), -QS(ret)~cnt; + +// validation checks +valid(ret) >< [] => ret~False; +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=800000; + +make_RandList(rndlist)~(LIST_ELEM), +qsort(sorted)~rndlist, +valid(ret)~sorted; + ret; diff --git a/comparison/OCaml/bsort40000.ml b/comparison/OCaml/bsort40000.ml index 45744bd..2a06e85 100644 --- a/comparison/OCaml/bsort40000.ml +++ b/comparison/OCaml/bsort40000.ml @@ -19,5 +19,17 @@ let rec mkRandList n = 0 -> [] | n -> (Random.int 10000)::(mkRandList (n-1));; -let main = bsort (mkRandList 40000);; + +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 main = validation (bsort (mkRandList 40000));; diff --git a/comparison/OCaml/isort40000.ml b/comparison/OCaml/isort40000.ml index 686a7f6..92e127d 100644 --- a/comparison/OCaml/isort40000.ml +++ b/comparison/OCaml/isort40000.ml @@ -1,11 +1,3 @@ -(* -let rec insert x ylist = - match ylist with - [] -> [x] - | y::ys when x<=y -> x::y::ys - | y::ys -> y::(insert x ys);; -*) - let rec insert x ylist = match ylist with [] -> [x] @@ -26,5 +18,17 @@ let rec mkRandList n = 0 -> [] | n -> (Random.int 10000)::(mkRandList (n-1));; -let main = isort (mkRandList 40000);; + +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 main = validation(isort (mkRandList 40000));; diff --git a/comparison/OCaml/msort800000.ml b/comparison/OCaml/msort800000.ml index 1835b98..bbb8de6 100644 --- a/comparison/OCaml/msort800000.ml +++ b/comparison/OCaml/msort800000.ml @@ -33,11 +33,19 @@ let rec mkRandList n = 0 -> [] | n -> (Random.int 10000)::(mkRandList (n-1)) ;; -let main = msort (mkRandList 800000) ;; +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;; -(* -The following error arises: +let main = validation (msort (mkRandList 800000));; -Stack overflow during evaluation (looping recursion?). +(* +Fatal error: exception Stack_overflow *) diff --git a/comparison/OCaml/qsort800000.ml b/comparison/OCaml/qsort800000.ml index 627abd2..7547f45 100644 --- a/comparison/OCaml/qsort800000.ml +++ b/comparison/OCaml/qsort800000.ml @@ -21,10 +21,20 @@ let rec mkRandList n = 0 -> [] | n -> (Random.int 10000)::(mkRandList (n-1)) ;; -let main = qsort (mkRandList 800000) ;; -(* -The following error arises: +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;; + -Stack overflow during evaluation (looping recursion?). +let main = validation(qsort (mkRandList 800000));; + +(* +Fatal error: exception Stack_overflow *) diff --git a/comparison/Python/bsort-40000.py b/comparison/Python/bsort-40000.py index 25ea4c7..8eeb4e5 100644 --- a/comparison/Python/bsort-40000.py +++ b/comparison/Python/bsort-40000.py @@ -17,8 +17,15 @@ def mkRandList(n): return a - +def validation(alist): + for i in range(len(alist)-1): + if (alist[i] > alist[i+1]): + return False + + return True + + + a=mkRandList(40000) bubblesort(a) - -#print(a) +print(validation(a)) diff --git a/comparison/Python/isort-40000.py b/comparison/Python/isort-40000.py index 0bfc577..c8e106b 100644 --- a/comparison/Python/isort-40000.py +++ b/comparison/Python/isort-40000.py @@ -17,6 +17,15 @@ def mkRandList(n): 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(40000) insert_sort(a) -#print(a) +print(validation(a)) diff --git a/comparison/Python/msort-800000.py b/comparison/Python/msort-800000.py index fcb89e1..c244cb4 100644 --- a/comparison/Python/msort-800000.py +++ b/comparison/Python/msort-800000.py @@ -50,6 +50,15 @@ def mkRandList ( n ): 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(800000) mergeSort(a) -#print(a) +print(validation(a)) diff --git a/comparison/Python/qsort-800000.py b/comparison/Python/qsort-800000.py index b58bf1c..a4a66e2 100644 --- a/comparison/Python/qsort-800000.py +++ b/comparison/Python/qsort-800000.py @@ -22,12 +22,22 @@ def quickSort(arr): more = quickSort(more) return less + pivotList + more + 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(800000) b = quickSort(a) -#print(b) +print(validation(b)) diff --git a/comparison/SML/bsort-40000.sml b/comparison/SML/bsort-40000.sml index e892f09..5e6e98b 100644 --- a/comparison/SML/bsort-40000.sml +++ b/comparison/SML/bsort-40000.sml @@ -15,7 +15,7 @@ fun go xs 0 = xs fun bsort xs = go xs (length(xs) - 1); -(* mkRandList *) +(* Creates a random list *) local val nextInt = Random.randRange(1,10000); val r = Random.rand(1,1); @@ -25,4 +25,17 @@ in end; -bsort (mkRandList 40000); +(* Validation checks *) +fun validation [] = true + | validation (x::xs) = + let fun validation_cons x [] = true + | validation_cons x (y::ys) = + if x<=y then validation_cons y ys + else false + in + validation_cons x xs + end; + + +(* Main *) +validation(bsort(mkRandList 40000)); diff --git a/comparison/SML/isort-40000.sml b/comparison/SML/isort-40000.sml index a851dbd..9fbaf09 100644 --- a/comparison/SML/isort-40000.sml +++ b/comparison/SML/isort-40000.sml @@ -8,7 +8,8 @@ fun insertsort [] = [] in insert(x, insertsort xs) end; -(* mkRandList *) + +(* Creates a random list *) local val nextInt = Random.randRange(1,10000); val r = Random.rand(1,1); @@ -16,5 +17,19 @@ in fun mkRandList 0 = [] | mkRandList n = (nextInt r)::(mkRandList (n-1)) end; - -insertsort (mkRandList 40000); \ No newline at end of file + + +(* Validation checks *) +fun validation [] = true + | validation (x::xs) = + let fun validation_cons x [] = true + | validation_cons x (y::ys) = + if x<=y then validation_cons y ys + else false + in + validation_cons x xs + end; + + +(* Main *) +validation(insertsort(mkRandList 40000)); diff --git a/comparison/SML/msort-800000.sml b/comparison/SML/msort-800000.sml index 9209685..4ed65ea 100644 --- a/comparison/SML/msort-800000.sml +++ b/comparison/SML/msort-800000.sml @@ -28,7 +28,7 @@ fun msort [] = [] end; -(* mkRandList *) +(* Creates a random list *) local val nextInt = Random.randRange(1,10000); val r = Random.rand(1,1); @@ -38,5 +38,18 @@ in end; +(* Validation checks *) +fun validation [] = true + | validation (x::xs) = + let fun validation_cons x [] = true + | validation_cons x (y::ys) = + if x<=y then validation_cons y ys + else false + in + validation_cons x xs + end; + + +(* Main *) msort (mkRandList 800000); diff --git a/comparison/SML/qsort-800000.sml b/comparison/SML/qsort-800000.sml index e27af56..212029d 100644 --- a/comparison/SML/qsort-800000.sml +++ b/comparison/SML/qsort-800000.sml @@ -15,7 +15,7 @@ fun quicksort nil = nil end; -(* mkRandList *) +(* Creates a random list *) local val nextInt = Random.randRange(1,10000); val r = Random.rand(1,1); @@ -23,5 +23,19 @@ in fun mkRandList 0 = [] | mkRandList n = (nextInt r)::(mkRandList (n-1)) end; - -quicksort (mkRandList 800000); + + +(* Validation checks *) +fun validation [] = true + | validation (x::xs) = + let fun validation_cons x [] = true + | validation_cons x (y::ys) = + if x<=y then validation_cons y ys + else false + in + validation_cons x xs + end; + + +(* Main *) +validation(quicksort(mkRandList 800000)); diff --git a/pic/benchmark_reuse_v0.8.2.png b/pic/benchmark_reuse_v0.8.2.png new file mode 100644 index 0000000..e988d23 Binary files /dev/null and b/pic/benchmark_reuse_v0.8.2.png differ diff --git a/pic/eraser.png b/pic/eraser.png new file mode 100644 index 0000000..fe48a1b Binary files /dev/null and b/pic/eraser.png differ diff --git a/sample/hanoi.in b/sample/hanoi.in index 3ba6f5c..2801817 100644 --- a/sample/hanoi.in +++ b/sample/hanoi.in @@ -2,7 +2,7 @@ // Rules hanoi(return, source, target, auxiliary) >< (int n) -| n==0 => return~[], Eps~source, Eps~target, Eps~auxiliary +| n==0 => return~[], Eraser~source, Eraser~target, Eraser~auxiliary | _ => source ~ dup(src1, dup(src2, src3)), target ~ dup(tgt1, dup(tgt2, tgt3)), auxiliary ~ dup(aux1, aux2), @@ -14,9 +14,9 @@ hanoi(return, source, target, auxiliary) >< (int n) dup(a,b)> a~A, b~A; dup(a,b)> a~B, b~B; dup(a,b)> a~C, b~C; -Eps>; -Eps>; -Eps>; + +// The `Eraser' is defined as a built-in agent for any agents as follows: +//Eraser >< Alpha(a1, ..., a5) => Eraser~a1, ..., Eraser~a5; // Net @@ -26,7 +26,8 @@ result; // should be [(1,A,C),(2,A,B),(1,C,B),(3,A,C),(1,B,A),(2,B,C),(1,A,C)] // These are also written using abbreviation as follows: // hanoi(return, source, target, auxiliary) >< (int n) -// | n==0 => return~[], << Eps(source), << Eps(target), << Eps(auxiliary) +// | n==0 => return~[], +// << Eraser(source), << Eraser(target), << Eraser(auxiliary) // | _ => src1, dup(src2, src3) << dup(source), // tgt1, dup(tgt2, tgt3) << dup(target), // aux1, aux2 << dup(auxiliary), diff --git a/src/id_table.c b/src/id_table.c index 0b4a93a..86655b5 100644 --- a/src/id_table.c +++ b/src/id_table.c @@ -51,7 +51,9 @@ void IdTable_init() { IdTable[ID_DIV2].aux.arity = 2; IdTable[ID_MOD].aux.arity = 2; IdTable[ID_MOD2].aux.arity = 2; + IdTable[ID_ERASER].aux.arity = 0; + IdTable[ID_INT].name = "int"; IdTable[ID_TUPLE0].name = "Tuple0"; IdTable[ID_TUPLE1].name = "Tuple1"; @@ -76,6 +78,9 @@ void IdTable_init() { IdTable[ID_DIV2].name = "_Div"; IdTable[ID_MOD].name = "Mod"; IdTable[ID_MOD2].name = "_Mod"; + + IdTable[ID_ERASER].name = "Eraser"; + } @@ -104,56 +109,14 @@ int IdTable_getid_builtin_funcAgent(Ast *agent) { id = ID_INTAGENT; } else if (strcmp((char *)agent->left->sym, "Merger") == 0) { id = ID_MERGER; + } else if (strcmp((char *)agent->left->sym, "Eraser") == 0) { + id = ID_ERASER; } return id; } -int IdTable_is_builtin_rule(Ast *agentL, Ast *agentR) { - // puts_ast(agentL); - // printf(" "); - // puts_ast(agentR); - // printf("\n"); - - - if ( (agentL->id == AST_TUPLE) && (agentR->id == AST_TUPLE) ) { - // compare these arities - if (agentL->intval == agentR->intval) { - return 1; - } - return 0; - } - - int idL = IdTable_getid_builtin_funcAgent(agentL); - if (agentR->id == AST_INT) { - if ((idL == ID_ADD) || (idL == ID_SUB) || (idL == ID_MUL) - || (idL == ID_DIV) || (idL == ID_MOD)) { - return 1; - } - return 0; - } - - if (idL == ID_APPEND) { - if ((agentR->id == AST_OPCONS) || (agentR->id == AST_NIL)) { - return 1; - } - return 0; - } - - if (idL == ID_MERGER) { - if ((agentR->id == AST_TUPLE) && (agentR->intval == 2)) { - // Merger >< Tuple2 - return 1; - } - return 0; - } - - - - return 0; -} - void IdTable_set_name(int id, char *symname) { diff --git a/src/id_table.h b/src/id_table.h index fa27cfb..a7bb795 100644 --- a/src/id_table.h +++ b/src/id_table.h @@ -47,7 +47,8 @@ #define ID_DIV2 25 #define ID_MOD 26 #define ID_MOD2 27 -#define END_ID_OF_BUILTIN_AGENT 27 +#define ID_ERASER 28 +#define END_ID_OF_BUILTIN_AGENT 28 #define START_ID_OF_AGENT END_ID_OF_BUILTIN_AGENT+1 @@ -102,7 +103,6 @@ int IdTable_new_agentid(); int IdTable_new_gnameid(); int IdTable_getid_builtin_funcAgent(Ast *agent); -int IdTable_is_builtin_rule(Ast *agentL, Ast *agentR); #endif diff --git a/src/inpla.y b/src/inpla.y index 24f855e..c84703f 100644 --- a/src/inpla.y +++ b/src/inpla.y @@ -20,12 +20,15 @@ #include "config.h" - +// ---------------------------------------------- +#define VERSION "0.8.2" +#define BUILT_DATE "28 Apr. 2022" + +// ------------------------------------------------------------------ + -// ---------------------------------------------- - //#define DEBUG // For experiments of the tail recursion optimisation. @@ -33,12 +36,6 @@ //#define COUNT_MKAGENT // count of execution fo mkagent -#define VERSION "0.8.1-2" -#define BUILT_DATE "16 Apr. 2022" -// ------------------------------------------------------------------ - - - @@ -882,6 +879,14 @@ void myfree(VALUE ptr) { } +static inline +void myfree2(VALUE ptr, VALUE ptr2) { + + SET_HOOPFLAG_READYFORUSE(BASIC(ptr)->id); + SET_HOOPFLAG_READYFORUSE(BASIC(ptr2)->id); + +} + @@ -1200,6 +1205,14 @@ void myfree(VALUE ptr) { } +static inline +void myfree2(VALUE ptr, VALUE ptr2) { + + SET_HOOPFLAG_READYFORUSE(BASIC(ptr)->id); + SET_HOOPFLAG_READYFORUSE(BASIC(ptr2)->id); + +} + #else // v0.5.6 ------------------------------------- @@ -1365,6 +1378,16 @@ void myfree(VALUE ptr) { } +//static inline +void myfree2(VALUE ptr, VALUE ptr2) { + + // TOGGLE_HEAPFLAG_READYFORUSE(BASIC(ptr)->id); + SET_HEAPFLAG_READYFORUSE(BASIC(ptr)->id); + SET_HEAPFLAG_READYFORUSE(BASIC(ptr2)->id); +} + + + //--------------------------------------------- @@ -1970,14 +1993,25 @@ void VM_Clear_InteractionCount(VirtualMachine *vm) { //static inline void free_Agent(VALUE ptr) { - if (ptr == (VALUE)NULL) { - puts("ERROR: NULL is applied to free_Agent."); - return; - } + // if (ptr == (VALUE)NULL) { + // puts("ERROR: NULL is applied to free_Agent."); + // return; + // } myfree(ptr); } + +void free_Agent2(VALUE ptr, VALUE ptr2) { + + // if (ptr == (VALUE)NULL) { + // puts("ERROR: NULL is applied to free_Agent."); + // return; + // } + + myfree2(ptr, ptr2); +} + //static inline void free_Name(VALUE ptr) { if (ptr == (VALUE)NULL) { @@ -7863,8 +7897,10 @@ void *exec_code(int mode, VirtualMachine * restrict vm, void * restrict *code) { E_RET_FREE_LR: // puts("ret_free_LR"); - free_Agent(reg[VM_OFFSET_ANNOTATE_L]); - free_Agent(reg[VM_OFFSET_ANNOTATE_R]); + + //free_Agent(reg[VM_OFFSET_ANNOTATE_L]); + //free_Agent(reg[VM_OFFSET_ANNOTATE_R]); + free_Agent2(reg[VM_OFFSET_ANNOTATE_L], reg[VM_OFFSET_ANNOTATE_R]); return NULL; E_RET_FREE_L: @@ -8757,6 +8793,14 @@ loop_a2IsFixnum: a1 = a1port0; goto loop; } + case ID_ERASER: + { + COUNTUP_INTERACTION(vm); + + // Eps ~ (int n) + free_Agent(a1); + return; + } } @@ -8777,7 +8821,7 @@ loop_a2IsFixnum: #endif } - /* + /* JIT experimentation if (BASIC(a1)->id == 28) { vm->reg[VM_OFFSET_METAVAR_L(0)] = AGENT(a1)->port[0]; @@ -8906,7 +8950,7 @@ loop_a2IsAgent: if (BASIC(a2)->id < START_ID_OF_BUILTIN_AGENT) { - // built-in + // a2 is a constructor switch (BASIC(a1)->id) { case ID_TUPLE0: @@ -8914,8 +8958,9 @@ loop_a2IsAgent: // [] ~ [] --> nothing COUNTUP_INTERACTION(vm); - free_Agent(a1); - free_Agent(a2); + // free_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); return; } @@ -8931,8 +8976,9 @@ loop_a2IsAgent: VALUE a2p1 = AGENT(a2)->port[1]; PUSH(vm, a1p1, a2p1); - free_Agent(a1); - free_Agent(a2); + // free_Agent(a1); + // free_Agent(a2); + free_Agent2(a1,a2); a1 = AGENT(a1)->port[0]; a2 = AGENT(a2)->port[0]; goto loop; @@ -8948,8 +8994,9 @@ loop_a2IsAgent: 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_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); a1 = AGENT(a1)->port[0]; a2 = AGENT(a2)->port[0]; goto loop; @@ -8967,8 +9014,9 @@ loop_a2IsAgent: 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_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); a1 = AGENT(a1)->port[0]; a2 = AGENT(a2)->port[0]; goto loop; @@ -8987,8 +9035,9 @@ loop_a2IsAgent: 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_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); a1 = AGENT(a1)->port[0]; a2 = AGENT(a2)->port[0]; goto loop; @@ -9002,8 +9051,10 @@ loop_a2IsAgent: // [] ~ [] --> nothing COUNTUP_INTERACTION(vm); - free_Agent(a1); - free_Agent(a2); + // free_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); + return; } @@ -9019,8 +9070,9 @@ loop_a2IsAgent: VALUE a2p1 = AGENT(a2)->port[1]; PUSH(vm, a1p1, a2p1); - free_Agent(a1); - free_Agent(a2); + // free_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); a1 = AGENT(a1)->port[0]; a2 = AGENT(a2)->port[0]; goto loop; @@ -9040,8 +9092,9 @@ loop_a2IsAgent: VALUE a1p0 = AGENT(a1)->port[0]; VALUE a1p1 = AGENT(a1)->port[1]; - free_Agent(a1); - free_Agent(a2); + // free_Agent(a1); + // free_Agent(a2); + free_Agent2(a1, a2); a1=a1p0; a2=a1p1; goto loop; @@ -9102,8 +9155,10 @@ loop_a2IsAgent: return; } else { VALUE a1p0 = AGENT(a1)->port[0]; - free_Agent(AGENT(a1)->port[1]); - free_Agent(a1); + // free_Agent(AGENT(a1)->port[1]); + // free_Agent(a1); + free_Agent2(AGENT(a1)->port[1], a1); + a1 = a1p0; goto loop; } @@ -9124,8 +9179,9 @@ loop_a2IsAgent: COUNTUP_INTERACTION(vm); VALUE a1p0 = AGENT(a1)->port[0]; - free_Agent(AGENT(a1)->port[2]); - free_Agent(a1); + // free_Agent(AGENT(a1)->port[2]); + // free_Agent(a1); + free_Agent2(AGENT(a1)->port[2], a1); a1 = a1p0; goto loop; } else { @@ -9159,8 +9215,9 @@ loop_a2IsAgent: COUNTUP_INTERACTION(vm); VALUE a1p0 = AGENT(a1)->port[0]; - free_Agent(AGENT(a1)->port[2]); // free the lock for NIL - free_Agent(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; @@ -9197,12 +9254,53 @@ loop_a2IsAgent: #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; + } + + case 1: + { + VALUE a2p0 = AGENT(a2)->port[0]; + free_Agent(a2); + a2 = a2p0; + goto loop; + } + + default: + for (int i=1; iport[1]; + VALUE eps = make_Agent(vm, ID_ERASER); + PUSH(vm, eps, a2port); + } + + VALUE a2p0 = AGENT(a2)->port[0]; + free_Agent(a2); + a2 = a2p0; + goto loop; + } + } + break; // end case ID_ERASER } - } - + } printf("Runtime Error: There is no interaction rule for the following pair:\n "); -- cgit v1.2.3