From add49f1df854ed333252b494d1899c8c899991dd Mon Sep 17 00:00:00 2001 From: Shinya Sato Date: Thu, 10 Mar 2022 21:10:34 +0900 Subject: v0.8.1-1 --- Changelog.md | 44 +++++++++++++++++++++++++++ Makefile | 3 +- README.md | 2 +- sample/ack_3_5.in | 22 ++++++-------- src/ast.c | 41 +++++++++++++++---------- src/ast.h | 2 +- src/config.h | 90 ++++++++++++++++++++++++++++++++++++++++--------------- src/inpla.y | 58 +++++++++++++++++++++++++++++++++-- 8 files changed, 204 insertions(+), 58 deletions(-) diff --git a/Changelog.md b/Changelog.md index 5232bca..cf224fe 100644 --- a/Changelog.md +++ b/Changelog.md @@ -1,5 +1,49 @@ # Change log + +### v0.8.1-1 minor update (released on 10 March 2022) +#### Polished + +* **The abbreviation**: it can take an empty arguments list on its left-hand side like: + + ``` + << Agent(paramlist,param) // this is an abbreviation for Agent(paramlist)~param + ``` + + This could be handy for elimination operation: + + ``` + Eps >< Z =>; + Eps >< S(x) => Eps~x; + + // Nets + Eps ~ S(Z); + + // Abbreviated notation of the nets + << Eps(S(Z)); + ``` + +* **Makefile**: The configuration file `src/config.h` is also included in update files. So, `make` command works when the file is changed. + +* **Rule table**: A simple implementation with arrays is prepared. It could be expected to work better, but it seems not so differences. It becomes available by making the following definition un-comment in `src/config.h`: + + ``` + // ------------------------------------------------ + // RuleTable + // ------------------------------------------------ + // There are two implementation for the rule table: + // * Hashed linear table (default) + // * Simple array table + // To use the hashed one, comment out the following RULETABLE_SIMPLE definition. + + //#define RULETABLE_SIMPLE + ``` + + + + + + ### v0.8.1 (released on 3 March 2022) | | Haskell | SML | Python | Inpla1 | Inpla1_r | Inpla7 | Inpla7_r | diff --git a/Makefile b/Makefile index c7e6e78..e350dce 100644 --- a/Makefile +++ b/Makefile @@ -7,6 +7,7 @@ SRC_DIR = ./src OBJ_DIR = ./build TARGET = inpla OBJS = $(OBJ_DIR)/inpla.tab.c $(OBJ_DIR)/ast.o $(OBJ_DIR)/id_table.o $(OBJ_DIR)/name_table.o $(OBJ_DIR)/linenoise.o +DEPS = $(SRC_DIR)/config.h #MYOPTION = -DHAND_FIB -DHAND_FIB_INT -DHAND_I_CONS -DHAND_IS_CONS -DHAND_Apnd_CONS -DHAND_Part_CONS -DHAND_Split_CONS -DHAND_MergeCC_CONS -DHAND_B_CONS -DHAND_DUP_S -DHAND_ADD_S -DHAND_ACK_S #MYOPTION = -DHAND_Split_CONS -DHAND_MergeCC_CONS @@ -16,7 +17,7 @@ OBJS = $(OBJ_DIR)/inpla.tab.c $(OBJ_DIR)/ast.o $(OBJ_DIR)/id_table.o $(OBJ_DI all: $(OBJ_DIR) $(TARGET) -$(TARGET): $(OBJS) $(LIBS) +$(TARGET): $(OBJS) $(LIBS) $(DEPS) $(CC) $(CFLAGS) $(INCLUDE) $(MYOPTION) -o $@ $(OBJS) $(LDFLAGS) $(OBJ_DIR)/linenoise.o: $(SRC_DIR)/linenoise/linenoise.c diff --git a/README.md b/README.md index 6a2a6ce..c1252fc 100644 --- a/README.md +++ b/README.md @@ -6,7 +6,7 @@ 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 released on **3 March 2022**. (See [Changelog.md](Changelog.md) for details.) +* The current version is 0.8.1-1 (minor update) released on **10 March 2022**. (See [Changelog.md](Changelog.md) for details.) ![speedup-ratio](pic/benchmark_reuse_v0.8.1.png) diff --git a/sample/ack_3_5.in b/sample/ack_3_5.in index 87057a2..7b6e0bd 100644 --- a/sample/ack_3_5.in +++ b/sample/ack_3_5.in @@ -4,25 +4,21 @@ // | 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 that -// the 'cnt' is an integer agent when ack(r)~(m-1,cnt) is evaluated. +// The following rule is wrong because there is no gurantee that +// the 'cnt' is connected to 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); +// +// So, the `cnt' should be connected as an element of connections. - -ack(ret, n) >< (int m) -| m==0 => inc(ret)~n -| _ => ackn(ret, m)~n; - -ackn(ret, int m) >< (int n) -| n==0 => ack(ret,1) ~ (m-1) -| _ => ack(cnt,n-1)~m, ack(ret,cnt)~(m-1); - -inc(ret)><(int n) => ret~(n+1); - +ack(ret, int m) >< (int n) +| m==0 => ret~(n+1) +| n==0 => ack(ret, m-1)~1 +| _ => ack(cnt, m)~(n-1), ack(ret, m-1)~cnt; ackMain(ret)><(int m, int n) => ack(ret,n)~m; diff --git a/src/ast.c b/src/ast.c index 8b894f6..88a40ff 100644 --- a/src/ast.c +++ b/src/ast.c @@ -308,9 +308,9 @@ void ast_puts(Ast *p) { } -Ast *ast_unfoldABR(Ast *left, char *sym, Ast *paramlist) { +Ast *ast_unfoldABR(Ast *left_params, char *sym, Ast *paramlist) { // input: - // left << (AST_AGENT, sym, paramlist) + // left_params << (AST_AGENT, sym, paramlist) // output: // p1,p2,...,pn << (AST_AGENT, sym, params @ [param]) @@ -318,6 +318,16 @@ Ast *ast_unfoldABR(Ast *left, char *sym, Ast *paramlist) { // where left = (AST_AGENT sym, p1,p2,...,pn,params) // right = (AST_NAME param) + if (!strcmp(sym, "Merger")) { + // left << Merger(paramlist) ==> Merger(left) ~ (paramlist) + Ast *agent_left = ast_makeAST(AST_AGENT, ast_makeSymbol("Merger"), + left_params); + Ast *agent_right = ast_makeTuple(paramlist); + Ast *cnct = ast_makeAST(AST_CNCT, agent_left, agent_right); + return cnct; + } + + if (!strcmp(sym, "Append")) { // paramlist: [a,b] => [b,a] if (paramlist->right != NULL) { @@ -325,13 +335,8 @@ Ast *ast_unfoldABR(Ast *left, char *sym, Ast *paramlist) { paramlist->left = paramlist->right->left; // a := b paramlist->right->left = tmp; // b := a } - } else if (!strcmp(sym, "Merger")) { - // left << Merger(paramlist) ==> Merger(left) ~ (paramlist) - Ast *agent_left = ast_makeAST(AST_AGENT, ast_makeSymbol("Merger"), left); - Ast *agent_right = ast_makeTuple(paramlist); - Ast *cnct = ast_makeAST(AST_CNCT, agent_left, agent_right); - return cnct; } + //ast_puts(left);puts(""); //ast_puts(paramlist);puts(""); @@ -363,19 +368,23 @@ Ast *ast_unfoldABR(Ast *left, char *sym, Ast *paramlist) { // ast_puts(param);puts(""); - // make left as left@params - at = left; - while (at != NULL) { - if (at->right == NULL) { - at->right = params; - break; + // make left_params as left_params @ params + at = left_params; + if (at == NULL) { + at = params; + } else { + while (at != NULL) { + if (at->right == NULL) { + at->right = params; + break; + } + at = at->right; } - at = at->right; } // ast_puts(left);puts(""); - Ast *agent_left = ast_makeAST(AST_AGENT, ast_makeSymbol(sym), left); + Ast *agent_left = ast_makeAST(AST_AGENT, ast_makeSymbol(sym), left_params); Ast *agent_right = param; Ast *cnct = ast_makeAST(AST_CNCT, agent_left, agent_right); diff --git a/src/ast.h b/src/ast.h index 5f7fe16..5d759fa 100644 --- a/src/ast.h +++ b/src/ast.h @@ -51,7 +51,7 @@ void ast_puts(Ast *p); Ast *ast_paramToCons(Ast *ast); int ast_recordConst(char *name, int val); Ast *ast_remove_tuple1(Ast *p); -Ast *ast_unfoldABR(Ast *left, char *sym, Ast *paramlist); +Ast *ast_unfoldABR(Ast *left_params, char *sym, Ast *paramlist); int ast_getRecordedVal(int entry); #define ast_makeCons(x1,x2) ast_makeAST(AST_LIST,x1,x2) diff --git a/src/config.h b/src/config.h index 0a46711..1f878e0 100644 --- a/src/config.h +++ b/src/config.h @@ -1,46 +1,86 @@ // Configurations --------------------------------------------------- -/* Heaps ------------------------------------------ - Choose one among the following three definitions: - -------------------------------------------------- */ -#define FLEX_EXPANDABLE_HEAP // Inserted heaps size can be flexible. -//#define EXPANDABLE_HEAP // Expandable heaps for agents and names -//#define FIXED_HEAP // The heap size is fixed. (Default) - - +// ------------------------------------------------ +// Heaps +// ------------------------------------------------ +// There are three methods for agents and names heaps: +// - Fixed-size ring buffers (default) +// The size is specified by an execution option -c +// +// - Expandable ring buffers +// Automatically new buffers are inserted when all are run up. +// +// - Ring buffers whose Initial size and newly inserted size +// are flexibly changed. +// The initial size and the expansion magnification are +// specified by execution options -Xms, -Xmt, respectively. +// +// Choose one among the following three definitions with uncomment. + + +//#define FIXED_HEAP +//#define EXPANDABLE_HEAP +#define FLEX_EXPANDABLE_HEAP + + +// +// For the expandable ring buffer, the unit size HOOP_SIZE can be changed. +// We note that HOOP_SIZE must be two to power. +// #ifdef EXPANDABLE_HEAP -// HOOP_SIZE must be two to power -#define HOOP_SIZE (1 << 18) +//#define HOOP_SIZE (1 << 12) // good for small heaps such as fib +#define HOOP_SIZE (1 << 18) // good for large heaps such as msort-80000 #endif + + +// ------------------------------------------------ +// RuleTable +// ------------------------------------------------ +// There are two implementation for the rule table: +// - Hashed linear table (default) +// - Simple array table +// To use the hashed one, comment out the following RULETABLE_SIMPLE definition. + +//#define RULETABLE_SIMPLE + + + + + -/* Optimisation ------------------------------------ - Comment out definitions if not needed. - ------------------------------------------------- */ +// ------------------------------------------------ +// Optimisation +// ------------------------------------------------ +// Comment out definitions if not needed. +// // Optimisation inspired by Tail Recursion Optimisation +// #define OPTIMISE_IMCODE_TRO - +// // Optimisation of the intermediate codes -/* - * Assign registers as little as possible with expecting cache works. - * Copy propagation and Dead code elimination for LOAD are performed. - * Reg0 is used as a special one that stores results of comparison. - * Some combinations are rewritten. - For instance, `SUBI src $1 dest' becomes `DEC src dest'. -*/ +// +// +// - Assign registers as little as possible with expecting cache works. +// - Copy propagation and Dead code elimination for LOAD are performed. +// - Reg0 is used as a special one that stores results of comparison. +// - Some combinations are rewritten. +// For instance, `SUBI src $1 dest' becomes `DEC src dest'. +// #define OPTIMISE_IMCODE #ifdef OPTIMISE_IMCODE -// Furthermore optimisations for codes: +// Furthermore optimisations on virtual machine codes: // the following can work when the OPTIMISE_IMCODE is defined: - +// // Generate virtual machine codes with two-address notation +// #define OPTIMISE_TWO_ADDRESS #ifdef OPTIMISE_TWO_ADDRESS @@ -52,7 +92,9 @@ #endif -// END Optimisation configuration -------------- +// ------------------------------------------------- + + #define COUNT_INTERACTION // Count interaction. diff --git a/src/inpla.y b/src/inpla.y index ea533f0..cb06e67 100644 --- a/src/inpla.y +++ b/src/inpla.y @@ -33,8 +33,8 @@ //#define COUNT_MKAGENT // count of execution fo mkagent -#define VERSION "0.8.1" -#define BUILT_DATE "3 Mar. 2022" +#define VERSION "0.8.1-1" +#define BUILT_DATE "10 Mar. 2022" // ------------------------------------------------------------------ @@ -468,9 +468,13 @@ ap // | astparams ABR AGENT LP astparams RP { $$ = ast_unfoldABR($1, $3, $5); } +| ABR AGENT LP astparams RP +{ $$ = ast_unfoldABR(NULL, $2, $4); } // | astparams ABR NAME LP astparams RP { $$ = ast_unfoldABR($1, $3, $5); } +| ABR NAME LP astparams RP +{ $$ = ast_unfoldABR(NULL, $2, $4); } ; @@ -6687,6 +6691,8 @@ int Compile_rule_mainbody_on_ast(Ast *mainbody) { // ------------------------------------------------------------ // TABLE for RULES // ------------------------------------------------------------ +#ifndef RULETABLE_SIMPLE + typedef struct RuleList { int sym; int available; @@ -6864,6 +6870,54 @@ void RuleTable_get_code_for_Int(VALUE heap_syml, void ***code) { return; } +#else +// ------------------------------------------ +// RuleTable: simple realisation with arrays +// ------------------------------------------ +// +// codes for alpha>basic.id; + int symrID = AGENT(heap_symr)->basic.id; + + void *code = RuleTable[symrID][symlID]; + if (code == NULL) { + *result = 0; + } else { + *result = 1; + } + + return code; +} + +static inline +void RuleTable_get_code_for_Int(VALUE heap_syml, void ***code) { + int symlID = AGENT(heap_syml)->basic.id; + *code = RuleTable[ID_INT][symlID]; +} + +#endif -- cgit v1.2.3