From fe97dadef0a6bd009998952a3183ec6822cf6fbc Mon Sep 17 00:00:00 2001 From: Shinya Sato Date: Mon, 16 Mar 2026 15:17:54 +0900 Subject: v0.13.2 --- Changelog.md | 110 +++++++++++ Gentle_introduction_Inpla.md | 17 -- README.md | 5 +- src/config.h | 18 ++ src/inpla.y | 453 ++++++++++++++++++++++++++++++++++++++----- 5 files changed, 534 insertions(+), 69 deletions(-) diff --git a/Changelog.md b/Changelog.md index 3b6a564..231344e 100644 --- a/Changelog.md +++ b/Changelog.md @@ -1,5 +1,115 @@ # Change log +### v0.13.2 (released on 16 March 2026) + +#### Polished + +- **The compilation method for lists has been changed:** The compilation order for list structures (`AST_OPCONS`) has been inverted to a bottom-up approach to prevent register exhaustion. For example, a list like `[t1, t2]` is structured as `Cons(t1, Cons(t2, Nil))`. Previously, it was compiled top-down as follows: + + ``` + compile([t1, t2]) + --> MKAGENT ID_CONS reg13 // reg[13] := Cons (Wait until the tail is compiled!) + compile(t1, reg14) // reg[14] := t1 + LOADP reg14, 0, reg13 // reg[13].port[0] := t1 + compile([t2], reg15) // Recursively compile the tail ([t2]) + LOADP reg15, 1, reg13 // reg[13].port[1] := reg15 + + --> MKAGENT ID_CONS reg13 // reg[13] := Cons (Wait until the tail is compiled!) + compile(t1, reg14) // reg[14] := t1 + LOADP reg14, 0, reg13 // reg[13].port[0] := t1 + MKAGENT ID_CONS reg15 // reg[15] := Cons (Wait until the tail is compiled!) + compile(t2, reg16) // reg[16] := t2 + LOADP reg16, 0, reg15 // reg[15].port[0] := t2 + compile([], reg17) // reg[17] := [] + LOADP reg17, 1, reg15 // reg[15].port[1] := [] + LOADP reg15, 1, reg13 // reg[13].port[1] := reg15 + + --> MKAGENT ID_CONS reg13 // reg[13] := Cons (Wait until the tail is compiled!) + compile(t1, reg14) // reg[14] := t1 + LOADP reg14, 0, reg13 // reg[13].port[0] := t1 + MKAGENT ID_CONS reg15 // reg[15] := Cons (Wait until the tail is compiled!) + compile(t2, reg16) // reg[16] := t2 + LOADP reg16, 0, reg15 // reg[15].port[0] := t2 + MKAGENT ID_NIL reg17 // reg[17] := [] + LOADP reg17, 1, reg15 // reg[15].port[1] := [] + LOADP reg15, 1, reg13 // reg[13].port[1] := reg15 + ``` + + In this old approach, the register for the parent Cons cell (`reg13`) must be kept alive until the entire tail is compiled. For a very long list, this deep recursion consumed too many registers, causing the VM to run out of registers (yielding an `All registers run up` error). + + To solve this, the compilation order is changed to compile the tail first: + + ``` + compile([t1, t2]) + --> compile([t2], reg13) // Compile the tail first (deep recursion probably) + compile(t1, reg14) // Compile the head + MKAGENT ID_CONS reg15 // reg[15] := Cons + LOADP reg14, 0, reg15 // reg[15].port[0] := t1 (reg14 is reused!) + LOADP reg13, 1, reg15 // reg[15].port[1] := the tail (reg13 is reused!) + + --> compile([], reg16) // reg[16] := [] + compile(t2, reg17) // reg[17] := t2 + MKAGENT ID_CONS reg18 // reg[18] := Cons + LOADP reg17, 0, reg18 // reg[18].port[0] := reg17 (reg17 is reused!) + LOADP reg16, 1, reg18 // reg[18].port[1] := reg16 (reg16 is reused!) + compile(t1, reg14) // reg[14] := t1 + MKAGENT ID_CONS reg15 // reg[15] := Cons + LOADP reg14, 0, reg15 // reg[15].port[0] := t1 (reg14 is reused!) + LOADP reg13, 1, reg15 // reg[15].port[1] := reg13 (reg13 is reused!) + + --> MKAGENT ID_NIL reg16 // reg[16] := Nil + compile(t2, reg17) // reg[17] := t2 + MKAGENT ID_CONS reg18 // reg[18] := Cons + LOADP reg17, 0, reg18 // reg[18].port[0] := reg17 (reg17 is reused!) + LOADP reg16, 1, reg18 // reg[18].port[1] := reg16 (reg16 is reused!) + compile(t1, reg14) // reg[14] := t1 + MKAGENT ID_CONS reg15 // reg[15] := Cons + LOADP reg14, 0, reg15 // reg[15].port[0] := t1 (reg14 is reused!) + LOADP reg13, 1, reg15 // reg[15].port[1] := reg13 (reg13 is reused!) + + ==> Optimise + MKAGENT ID_NIL reg14 // reg[14] := Nil + compile(t2, reg15) // reg[15] := t2 + MKAGENT ID_CONS reg16 // reg[16] := Cons + LOADP reg15, 0, reg16 // reg[16].port[0] := reg15 (reg15 is reused) + LOADP reg14, 1, reg16 // reg[16].port[1] := reg14 (reg14 is reused) + compile(t1, reg14) // reg[14] := t1 + MKAGENT ID_CONS reg15 // reg[15] := Cons + LOADP reg14, 0, reg15 // reg[15].port[0] := t1 (reg14 is reused!) + LOADP reg16, 1, reg15 // reg[15].port[1] := reg16 (reg16 is reused!) + ``` + + Because the tail and head are evaluated before the parent Cons cell is created, they can be connected immediately. This allows the compiler's 2nd pass to reuse a small number of registers efficiently. With this approach, even extremely huge lists can now be compiled smoothly without exhausting the 64 VM registers. + +- **Parsing of large lists**: Previously, the maximum size of VM codes was strictly defined as 1024, which prevented parsing lists with a large number of elements (causing stack smashing). The buffer for the top-level execution is now dynamically allocated with a much larger size (e.g., 1,000,000) and de-allocated immediately after the compilation and execution finish. These constants are newly defined in `config.h`: + + ``` + // ------------------------------------------------ + // Maximum Number of VMCode Sequence + // ------------------------------------------------ + // MAX_VMCODE_SEQUENCE defines the maximum number of VM codes + // for each rule. This value limits the code size stored in the RuleTable. + // Default is 1024. + #define MAX_VMCODE_SEQUENCE 1024 + + // MAX_EXEC_VMCODE_SEQUENCE defines the maximum number of VM codes + // for the top-level execution. + // This buffer for this is dynamically allocated + // at the start of the top-level execution + // and de-allocated immediately after the compilation and execution finish. + // Default is 1000000. + #define MAX_EXEC_VMCODE_SEQUENCE 1000000 + ``` + + Now, we can safely parse long lists at the top level! + + ``` + >>> a~[1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0]; + (0 interactions, 0.00 sec) + ``` + + + ### v0.13.1 (released on 15 March 2026) #### Polished diff --git a/Gentle_introduction_Inpla.md b/Gentle_introduction_Inpla.md index bd31326..6f15868 100644 --- a/Gentle_introduction_Inpla.md +++ b/Gentle_introduction_Inpla.md @@ -659,23 +659,6 @@ Inpla has the following macro: -c Enable output of compiled codes (Default: disable) -h Print this help message -foptimise-tail-calls Enable tail call optimisation (Default: disable) - - Inpla version 0.12.0 - Usage: inpla [options] - - Options: - -f Set input file name (Default: STDIN) - -d = Bind to - -Xms Set initial heap size to 2^ (Default: 12 (=4096)) - -Xmt Set multiple heap increment to 2^ (Default: 3 (= 8)) - 0: the same size heap is inserted when it runs up. - 1: the twice (=2^1) size heap is inserted. - -Xes Set initial equation stack size (Default: 256) - -t Set the number of threads (Default: 8) - -w Enable Weak Reduction strategy (Default: false) - -c Enable to output compiled codes (Default: disable) - -h Print this help message - -foptimise-tail-calls Enable tail call optimisation (Default: disable) ``` **Note**: diff --git a/README.md b/README.md index 707892a..2ff9b95 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.13.1, released on **15 March 2026**. (See [Changelog.md](Changelog.md) for details.) +* The current version is 0.13.2, released on **16 March 2026**. (See [Changelog.md](Changelog.md) for details.) * The below graph shows speed-up ratio to threads numbers for programs in the following benchmark table. ![speedup-ratio](pic/benchmark_reuse_v0.13.0.png) @@ -267,14 +267,13 @@ Inpla is a multi-threaded parallel interpreter of interaction nets. Once you wri [Gentle_introduction_Inpla.md](Gentle_introduction_Inpla.md) explains how to make programs in Inpla step by step. Please look it over! + ## Updates See [Changelog.md](Changelog.md) for details. - - ## Publications * [1] Ian Mackie, Shinya Sato, [*In-place Graph Rewriting with Interaction Nets*](https://arxiv.org/abs/1609.03641), TERMGRAPH 2016, EPTCS 225, pp.15-24, 2016. diff --git a/src/config.h b/src/config.h index 00fae8a..5365829 100644 --- a/src/config.h +++ b/src/config.h @@ -9,6 +9,24 @@ #define MAX_PORT 5 +// ------------------------------------------------ +// Maximum Number of VMCode Sequence +// ------------------------------------------------ +// MAX_VMCODE_SEQUENCE defines the maximum number of VM codes +// for each rule. This value limits the code size stored in the RuleTable. +// Default is 1024. +#define MAX_VMCODE_SEQUENCE 1024 + +// MAX_EXEC_VMCODE_SEQUENCE defines the maximum number of VM codes +// for the top-level execution. +// This buffer for this is dynamically allocated +// at the start of the top-level execution +// and de-allocated immediately after the compilation and execution finish. +// Default is 1000000. +#define MAX_EXEC_VMCODE_SEQUENCE 1000000 + + + // ------------------------------------------------ // Heaps diff --git a/src/inpla.y b/src/inpla.y index f0f9c82..aa13dbd 100644 --- a/src/inpla.y +++ b/src/inpla.y @@ -22,8 +22,8 @@ // ---------------------------------------------- -#define VERSION "0.13.1" -#define BUILT_DATE "15 March 2026" +#define VERSION "0.13.2" +#define BUILT_DATE "16 March 2026" // ------------------------------------------------------------------ @@ -222,9 +222,9 @@ abr_annotate //%left ADD SUB //%left MULT DIV - // For error message information - %define parse.error verbose - %locations +// For error message information +%define parse.error verbose +%locations %% @@ -2839,8 +2839,10 @@ void IMCode_puts(int n) { +// The following is now defined in config.h +//#define MAX_VMCODE_SEQUENCE 1024 // The code size of each rule in RuleTable +//#define MAX_EXEC_VMCODE_SEQUENCE 1000000 // For top-level execution -#define MAX_VMCODE_SEQUENCE 1024 void VMCode_puts(void **code, int n) { int line = 0; @@ -4214,7 +4216,7 @@ int CmEnv_Optimise_VMCode_CopyPropagation(int target_imcode_addr) { #define MAX_LABEL 50 #define MAX_BACKPATCH MAX_LABEL*2 -int CmEnv_generate_VMCode(void **code) { +int CmEnv_generate_VMCode(void **code, int max_size) { int addr = 0; struct IMCode_tag *imcode; @@ -4227,6 +4229,13 @@ int CmEnv_generate_VMCode(void **code) { #endif for (int line_num=0; line_num= max_size - 10) { + fprintf(stderr, "ERROR[CmEnv_generate_VMCode]: VMCode buffer overflow!\n"); + exit(-1); + } + + imcode = &IMCode[line_num]; // DEBUG @@ -5743,6 +5752,7 @@ int Compile_term_on_ast(Ast *ptr, int target) { if (target == -1) { + /* result = CmEnv_newvar(); // expanded operations @@ -5753,6 +5763,17 @@ int Compile_term_on_ast(Ast *ptr, int target) { alloc = Compile_term_on_ast(ptr->right->left, -1); IMCode_genCode3(OP_LOADP, alloc, 1, result); + */ + + int head_alloc, tail_alloc; + tail_alloc = Compile_term_on_ast(ptr->right->left, -1); + head_alloc = Compile_term_on_ast(ptr->left, -1); + + result = CmEnv_newvar(); + IMCode_genCode2(OP_MKAGENT, ID_CONS, result); + IMCode_genCode3(OP_LOADP, head_alloc, 0, result); + IMCode_genCode3(OP_LOADP, tail_alloc, 1, result); + } else { result = target; @@ -7332,7 +7353,7 @@ int make_rule_oneway(Ast *ast) { // #define DEBUG_MKRULE #ifndef DEBUG_MKRULE - gencode_num += CmEnv_generate_VMCode(&code[2]); + gencode_num += CmEnv_generate_VMCode(&code[2], MAX_VMCODE_SEQUENCE); #else //int here_flag = is_tco; @@ -7345,7 +7366,7 @@ int make_rule_oneway(Ast *ast) { IMCode_puts(0); } - gencode_num += CmEnv_generate_VMCode(&code[2]); + gencode_num += CmEnv_generate_VMCode(&code[2], MAX_VMCODE_SEQUENCE); if (here_flag) { @@ -9857,11 +9878,6 @@ label_exec_agent_a1_a2: - - - - - void select_kind_of_push(Ast *ast, int p1, int p2) { int sym_id = NameTable_get_id(ast->left->sym); @@ -9933,8 +9949,14 @@ int check_ast_arity(Ast *ast) { #ifndef THREAD +// ----------------------------------------- +// Execution WITHOUT threads +// ----------------------------------------- +// ---------------------------------- +// for WHNF +// ---------------------------------- #define WHNF_UNUSED_STACK_SIZE 100 typedef struct { // EQStack @@ -9947,14 +9969,19 @@ WHNF_Info WHNFinfo; void Init_WHNFinfo(void) { WHNFinfo.eqs_index = 0; - WHNFinfo.size = WHNF_UNUSED_STACK_SIZE; + WHNFinfo.size = 0; WHNFinfo.enable = 0; // not Enable +} + +void WHNFInfo_populate_stack(void) { + WHNFinfo.size = WHNF_UNUSED_STACK_SIZE; WHNFinfo.eqs = malloc(sizeof(EQ) * WHNF_UNUSED_STACK_SIZE); if (WHNFinfo.eqs == NULL) { printf("WHNFinfo.eqs: Malloc error\n"); exit(-1); } + } void WHNFInfo_push_equation(VALUE t1, VALUE t2) { @@ -9973,15 +10000,18 @@ void WHNF_execution_loop(void) { while (EQStack_Pop(&VM, &t1, &t2)) { + printf("pop:"); puts_term(t1); printf("~"); puts_term(t2); puts(""); if ((NameTable_check_if_term_has_gname(t1) == 1) || (NameTable_check_if_term_has_gname(t2) == 1)) { + printf("--> Executed.\n"); eval_equation(&VM, t1, t2); } else { + printf("--> Not executed and pushed to the stack.\n"); WHNFInfo_push_equation(t1, t2); } } @@ -9989,13 +10019,240 @@ void WHNF_execution_loop(void) { } +// ---------------------------------- +// for simulation on multi-threads +// ---------------------------------- +typedef struct { + // VM + VirtualMachine *vm; // use only for EQStack + // + int threads_num; // -1: not Enable. 0: Maximum. 1..n: n-threads. + int verbose_stacked_eq; // not Enable (default) 1: Enable +} Simulation_Info; +Simulation_Info SimulationInfo; + + +void Init_SimulationInfo(void) { + SimulationInfo.threads_num = -1; // not Enable + SimulationInfo.verbose_stacked_eq = 0; // not Enable + SimulationInfo.vm = NULL; + + // set stderr as non-buffered + setvbuf(stderr, NULL, _IONBF, 0); + +} + +void SimulationInfo_prepare_stack(int stack_size) { + + SimulationInfo.vm = malloc(sizeof(VirtualMachine)); + if (SimulationInfo.vm == NULL) { + printf("SimulationInfo.eqs: Malloc error\n"); + exit(-1); + } + VM_EQStack_Init(SimulationInfo.vm, stack_size); + + + +} + +void SimulationInfo_set_threads_num(int num) { + SimulationInfo.threads_num = num; +} + + +typedef struct { + int idL; + int idR; +} IdPair; + + +int SimulationInfo_getid(VALUE ptr) { + if (IS_FIXNUM(ptr)) { + return ID_INT; + } + + if (IS_NAMEID(BASIC(ptr)->id)) { + if (NAME(ptr)->port == (VALUE)NULL) { + return ID_NAME; + } + return SimulationInfo_getid(NAME(ptr)->port); + } + + return BASIC(ptr)->id; +} + + +void SimulationInfo_execution_loop(void) { + VALUE t1, t2; + unsigned long step=1; + + + fprintf(stderr,"step,exec(%d),stacked,agents", SimulationInfo.threads_num); + + + // Get sorts of all rules + int ruleCount[NUM_AGENTS][NUM_AGENTS]; + int rule_num = 0; + + for (int idL=0; idL 0) { + + // Limited threads num + for (i=0; inextPtr_eqStack == -1) { + // no stacked AP + //printf("%ld,0,0\n", step); + return; // Loop termination + } + + + + } + + // one step execution by n-threads + fprintf(stderr, "%ld,%d,%d", step, i, VM.nextPtr_eqStack+1); + + + // Clear ruleCount + for (int i=0; i= 0) { + // Simulation mode + SimulationInfo_execution_loop(); + + } else { + // Normal operation VALUE t1, t2; while (EQStack_Pop(&VM, &t1, &t2)) { eval_equation(&VM, t1, t2); - } - - } else { - // WHNF stragety - WHNF_execution_loop(); - } - + } + } + time=stop_timer(&t); #ifdef COUNT_INTERACTION - printf("(%lu interactions, %.2f sec)\n", VM_Get_InteractionCount(&VM), + + printf("(%lu interactions, %.2f sec", VM_Get_InteractionCount(&VM), (double)(time)/1000000); + + if (SimulationInfo.threads_num >= 0) { + printf(", %lu agents)\n", Heap_GetNum_Usage_forAgent(&VM.agentHeap)); + } else { + printf(")\n"); + } + + #else printf("(%.2f sec)\n", (double)(time)/1000000); @@ -10165,12 +10441,10 @@ int exec(Ast *at) { printf("(%d mkAgent calls)\n", NumberOfMkAgent); #endif - if (GlobalOptions.verbose_memory_use) { puts_memory_usage(&VM.agentHeap, &VM.nameHeap); } - #ifdef COUNT_CNCT printf("JMP_CNCT:%d true:%d ratio:%.2f%%\n", @@ -10178,11 +10452,16 @@ int exec(Ast *at) { printf(" ind_op:%d ratio(ind/JMP_CNCT):%.2f%%\n", Count_cnct_indirect_op, Count_cnct_indirect_op*100.0/Count_cnct); #endif - + return 1; } + + #else +// --------------------------------------------------- +// Execution by multi-threads +// --------------------------------------------------- // For setting the number of CPUs. // it is calculated by using sysconf(_SC_NPROSSEORS_CONF) in tpool_init @@ -10315,10 +10594,15 @@ int exec(Ast *at) { // Ast at: (AST_BODY stmlist aplist) unsigned long long t, time; - - void* code[MAX_VMCODE_SEQUENCE]; int eqsnum = 0; + void** code = (void**)malloc(sizeof(void*) * MAX_EXEC_VMCODE_SEQUENCE); + if (code == NULL) { + puts("Error: Malloc error for code in exec func."); + exit(-1); + } + + #ifdef COUNT_INTERACTION for (int i=0; i Set the number of threads (Default: %10d)\n", MaxThreadsNum); #else printf(" -w Enable Weak Reduction strategy (Default: disable)\n"); #endif + + + +#ifndef THREAD + printf(" -s [Experimental] Simulate parallel execution with threads\n"); + printf(" 0: unlimited\n"); + printf(" -fverbose-simulation-info\n"); + printf(" Outputs active pairs selected for execution when using -s\n"); +#endif + + + printf(" -c Enable output of compiled codes (Default: disable)\n"); @@ -10739,6 +11055,13 @@ int main(int argc, char *argv[]) GlobalOptions.verbose_memory_use = 1; break; } + + + if (!strcmp(argv[i], "-fverbose-simulation-info")) { + SimulationInfo.verbose_stacked_eq = 1; + break; + } + #endif // for files @@ -10790,15 +11113,19 @@ int main(int argc, char *argv[]) exit(-1); } } else { - printf("ERROR: The option `-t' needs a number of threads."); + printf("ERROR: The option `-t' needs a number of threads.\n"); exit(-1); } MaxThreadsNum=param; break; -#else +#endif + +#ifndef THREAD case 'w': WHNFinfo.enable = 1; + WHNFInfo_populate_stack(); + break; #endif @@ -10807,6 +11134,29 @@ int main(int argc, char *argv[]) CmEnv.put_compiled_codes = 1; break; + + +#ifndef THREAD + + case 's': + { + int num; + i++; + if (i < argc) { + num = atoi(argv[i]); + } else { + printf("ERROR: The option '-s' needs a number of threads.\n"); + exit(1); + } + + + SimulationInfo_prepare_stack(max_EQStack); + SimulationInfo_set_threads_num(num); + break; + } +#endif + + default: printf("ERROR: Unrecognized option %s\n", argv[i]); @@ -10843,6 +11193,11 @@ int main(int argc, char *argv[]) if (WHNFinfo.enable) { printf("Inpla %s (Weak Strategy) : Interaction nets as a programming language", VERSION); printf(" [%s]\n", BUILT_DATE); + + } else if (SimulationInfo.threads_num >= 0) { + printf("Inpla %s (Simulation Mode) : Interaction nets as a programming language", VERSION); + printf(" [%s]\n", BUILT_DATE); + } else { printf("Inpla %s : Interaction nets as a programming language", VERSION); printf(" [built: %s]\n", BUILT_DATE); -- cgit v1.2.3