/* SL language - compiler and virtual machine Created by user Ina Modified to run the code described below ------------------------------------------ The Collatz conjecture says the following sequence always reaches 1 for all positive integer initial values: n[i+1] = n[i] / 2 if n[i] is even = 3*n[i] + 1 if n[i] is odd The current program prints the sequence for the integer 19. The first four lines are for generating the number 19. It can be modified to any positive integer, as long as the numbers in its sequence don't exceed MAXINT (127). The source code: SoloLearn solo solo solo learn solole solo solo solo learn sol solo learn solo learn solo solo solo learn s solo solo learn learn ace learn solo solo learn block solo solo solo learn s solo learn learn learn burey cipherfox burey solo solo solo solo cipherfox solo solo learn solo learn solo solo learn solo solo solo learn so solo learn learn solo learn solo solo solo solo solo solo learn solo learn learn learn ahrifox hatsyrei ahrifox solo solo learn solo solo solo learn solo solo solo learn solo learn learn solo solo mod ace hatsyrei solo solo learn solo solo solo learn solo solo solo solo learn sol solo learn solo learn solo solo solo learn s solo solo learn learn mod ace LearnSolo In simpler(?) terms 0. start 1. push 6 to stack 2. push 3 to stack 3. multiply 6 and 3 4. push 1 to stack 5. add 18 and 1 (stack = [19]) 6. loop begins 7. duplicate n (n=19 initially) 8. print n 9. push 1 to stack (stack = [n, 1]) 10. compare n with 1 11. begin block for zero result from line 10 12. end program 13. begin block for positive result from line 10 14. pop off 1 15. duplicate n 16. push 2 to stack (stack = [n, n, 2]) 17. divide to get remainder and quotient 18. store quotient in register[0] 19. push 0 to stack (stack = [n, n%2, 0]) 20. compare n&2 with 0 21. begin block for zero result from line 20 22. pop off 0 23. pop off n%2 24. pop off n 25. load n/2 to stack from register[0] 26. go to the beginning of loop (line 6) 27. begin block for positive result from line 20 28. pop off 0 29. pop off n%2 30. push 3 to stack 31. multiply 3 and n 32. push 1 to stack 33. add 3n and 1 34. go to the beginning of loop (line 6) 35. stop Everything below this line is Ina's work */ #include #include #include #include const char* keywords[] = { // the language vocabulary "solo", "learn", "mod", "ban", "SoloLearn", "LearnSolo", "block", // special jump tokens - pmods // they are needed for unconditional // jumps and arithmetic if constructs "ace", "burey", "cipherfox", "ahrifox", "hatsyrei", "jay", "kamil", "tashi", "krishna", "shahane", "val", // sorry... last name is too long :/ "kuba", NULL }; /* .-----------------------. */ /* | Tokeniser component | */ /* '-----------------------' */ typedef struct tokeniser_s { // keep a copy of the source char* src; // in source positioning int line; // current line int pos_a; // token begin mark A int pos_b; // token end mark B // current read head char* cur; } tokeniser_t; tokeniser_t* new_tokeniser(const char*); void delete_tokeniser(tokeniser_t*); const char* next_token(tokeniser_t*); /* .-----------------------. */ /* | Compiler / SLVM | */ /* '-----------------------' */ // opcodes #define HALT 0x0 #define PUSH 0x1 #define POP 0x2 #define ADD 0x3 #define SUB 0x4 #define MUL 0x5 #define DIV 0x6 #define CMP 0x7 #define STO 0x8 #define DUP 0x9 #define MOD 0xA #define BAN 0xB #define LOAD 0xC #define BLK 0xD // opcodes 0xE - 0xF undefined /* .-----------------------. */ /* | Compiler unit | */ /* '-----------------------' */ // error codes #define ENOERROR 0 // all is well #define EBOP 1 // program begin token missing #define EEOP 2 // program end token missing #define EILLEGAL 3 // illegal token #define ENOSRC 4 // no source found #define ENOMEM 5 // memory allocation error #define EUNEXPECTEDEOS 6 // unexpected end of source #define EUTOK 7 // unexpected token #define EOPCODE 8 // unrecognised opcode #define EOPERAND 9 // required operand missing #define EUKNJMP 10 // unknown jump label #define EREUSEDJMP 11 // a jump label has been reused #define EUNRJMP 12 // unresolved jump // vm errors #define ESPOP 13 // pop off an empty stack #define EINSUFFOP 14 // insufficient operands on the stack for operation int error_code = ENOERROR; char* compile(tokeniser_t*, size_t*); void disassemble(char*, size_t); int execute(char*); int is_keyword(const char*, size_t); /* ___________________________________ */ /* ___ .-------------------------. ___ */ /* ___ | PROGRAM ENTRY POINT | ___ */ /* ___ | ====================== | ___ */ /* ___ | | ___ */ /* ___ | The main function reads | ___ */ /* ___ | this file and searches | ___ */ /* ___ | for the SL source code | ___ */ /* ___ | which is enclosed by | ___ */ /* ___ | keywords SoloLearn and | ___ */ /* ___ | LearnSolo. | ___ */ /* ___ | | ___ */ /* ___ ':::::::::::::::::::::::::' ___ */ /* ___________________________________ */ // input buffer char buf[4096]; int main() { // read this file ... FILE *source = fopen(__FILE__, "r"); if(!source) { perror("main"); return 1; } size_t nread = fread(buf, 1, 4096, source); fclose(source); buf[nread-1] = '\0'; // find beginning of source char *src = buf; srcloop: while(*src && *src != 'S') src++; if(!(strncmp(src, "SoloLearn", 9) == 0)) { src++; goto srcloop; } if(!*src) { puts("No source found in file."); return 1; } // habemus sourcem! tokeniser_t *tok = new_tokeniser(src); size_t bcsize; const char* token; //// if someone whishes to read the tokens //// in the stream s/he may uncomment the //// following lines.... // // while((token = next_token(tok)) != NULL) { // printf("Line: %d, Pos: %d :: Token \"%s\"\n", // tok->line, tok->pos_a, // (*token == '\n' ? "newline" : token)); // } // compile the source puts("Compiling source..."); char *bc = compile(tok, &bcsize); // check for errors if(error_code) { printf("Error %d; line %d, pos %d\n", error_code, tok->line, tok->pos_a); } else { puts("Compilation successful.\n"); puts(""); // run this sukka! puts("Running program...\n"); puts("Output:"); int err = execute(bc); if(err != 0) { printf("Execution error %d\n", err); } else { puts("\nDone."); } puts("\nDisassembly:"); disassemble(bc, bcsize); } // free resources. delete_tokeniser(tok); free(bc); // done ! return 0; } /* .-----------------------. */ /* | Tokeniser component | */ /* '-----------------------' */ tokeniser_t* new_tokeniser(const char* raw) { // assert source code if(!raw) return NULL; tokeniser_t *tok = (tokeniser_t*) malloc(sizeof(tokeniser_t)); if(!tok) return tok; memset(tok, 0, sizeof(tokeniser_t)); tok->src = strdup(raw); tok->cur = tok->src; tok->pos_a = 1; tok->pos_b = 1; tok->line = 1; return tok; } void delete_tokeniser(tokeniser_t* tok) { // assert tok if(!tok) return; if(tok->src) free(tok->src); tok->src = NULL; free(tok); } int is_keyword(const char* s, size_t n) { size_t idx = 0; while(keywords[idx]) { if(strlen(keywords[idx]) == n) { if(strcmp(keywords[idx], s) == 0) { return 1; } } idx++; } return 0; } #define MIN(x,y) ((x) < (y) ? (x) : (y)) const char* next_token(tokeniser_t* tok) { static const char newline = '\n'; static char token_buffer[10]; // assert object and source if(!tok) return NULL; if(!tok->src) return NULL; if(!tok->cur) return NULL; // reset markers tok->pos_a = tok->pos_b; while(*tok->cur && isblank(*tok->cur)) { tok->pos_a++; tok->cur++; } if(*tok->cur == '\0') return NULL; if(*tok->cur == '\n') { tok->line++; tok->pos_a = 0; tok->pos_b = tok->pos_a + 1; tok->cur++; return &newline; } tok->pos_b = tok->pos_a; const char* end = tok->cur + 1; while(*end && !isspace(*end)) end++; // copy token into buffer and advance size_t len = (size_t) (end - tok->cur); strncpy(token_buffer, tok->cur, MIN(9, len)); token_buffer[MIN(9, len)] = '\0'; tok->cur += len; tok->pos_b += len; return token_buffer; } /* .-----------------------. */ /* | Compiler unit | */ /* '-----------------------' */ // this serves as abstraction int is_valid_oc(char opcode) { switch(opcode) { case HALT: case PUSH: case POP: case ADD: case SUB: case MUL: case DIV: case CMP: case DUP: case MOD: case BAN: case LOAD: case STO: case BLK: return 1; default: return 0; } } int key_index(const char* token) { int idx = 0; while(keywords[idx]) { if(strcmp(token, keywords[idx]) == 0) { return idx; } idx++; } return -1; } #define CONSUME_NEWLINE \ do { \ token = next_token(tok); \ if(strcmp(token, "\n") != 0) { \ error_code = EILLEGAL; \ goto bail; \ } \ } while(0) #define ADJUST_BCBUF \ do { \ if(bc_fill + 1 == bc_size) { \ char *bc_tmp = byte_code; \ byte_code = (char*) realloc(byte_code, bc_size + 100); \ if(!byte_code) { \ error_code = ENOMEM; \ byte_code = bc_tmp; \ goto bail; \ } \ bc_size += 100; \ } \ } while(0) #define ADJUST_JMPTABLE \ do { \ if(jt_idx == jt_size) { \ unsigned *jt_tmp = jmp_table; \ jmp_table = (unsigned*) realloc(jmp_table, jt_size + 12); \ if(!jmp_table) { \ error_code = ENOMEM; \ jmp_table = jt_tmp; \ goto bail; \ } \ jt_size += 12; \ } \ } while(0) char* compile(tokeniser_t *tok, size_t *bcsz) { // assert tokeniser if(!tok) { error_code = ENOSRC; return NULL; } // jmp labels and their position // in the compiled byte code char sym_table[18] = {0}; // jump table in conditional // and unconditional jumps for // later resolution size_t jt_idx = 0, // index into jump table jt_size; // size of jump table unsigned *jmp_table; // jump table /* .---------------------. */ /* | | */ /* | setting up compiler | */ /* | | */ /* '---------------------' */ char opcode = 0; // compiled opcode int bc_fill = 0; // byte code index size_t bc_size = 0; // byte code memory size const char *token; // current token in source char *byte_code = calloc(100, sizeof(char)); // prepare initial byte code memory block if(!byte_code) { error_code = ENOMEM; return NULL; } bc_size = 100; // prepare initial jump table jmp_table = (unsigned*) calloc(20, sizeof(unsigned)); if(!jmp_table) { error_code = ENOMEM; goto bail; } jt_size = 20; /* .----------------------. */ /* | | */ /* | start compiling ... | */ /* | | */ /* '----------------------' */ // program start token token = next_token(tok); if(strcmp(token, "SoloLearn") != 0) { error_code = EBOP; goto bail; } else { CONSUME_NEWLINE; } // program source loop do { opcode = 0; // reset opcode // grab next token and process token = next_token(tok); if(!token) { error_code = EUNEXPECTEDEOS; goto bail; } if(!is_keyword(token, strlen(token))) { error_code = EILLEGAL; goto bail; } // resolve opcode if(strcmp(token, "ban") == 0) { opcode = BAN; } else if(strcmp(token, "mod") == 0) { opcode = MOD; } else if(strcmp(token, "block") == 0) { opcode = BLK; } else if(strcmp(token, "solo") == 0 || strcmp(token, "learn") == 0) { // "solo" and "learn" form a group of // four tokens which encode the opcode // "solo" is zero // "learn" is one // "solo learn solo solo" is 0100 = 4 // evaluate current token if(strcmp(token, "solo") == 0) { opcode <<= 1; } else if(strcmp(token, "learn") == 0) { opcode <<= 1; opcode |= 1; } else { error_code = EUTOK; goto bail; } // grab remaining 3 for(int i = 1; i < 4; i++) { token = next_token(tok); if(!token) { error_code = EUNEXPECTEDEOS; goto bail; } if(strcmp(token, "solo") == 0) { opcode <<= 1; } else if(strcmp(token, "learn") == 0) { opcode <<= 1; opcode |= 1; } else { error_code = EUTOK; goto bail; } } // end "solo" / "learn" opcode group } else { // end of program ? if(strcmp(token, "LearnSolo") == 0) { byte_code[bc_fill++] = (char) HALT; break; } // must be PMod jump label int idx = key_index(token); if(idx == -1) { error_code = EUKNJMP; goto bail; } if(sym_table[idx] == 0) { sym_table[idx] = bc_fill; CONSUME_NEWLINE; continue; } else { error_code = EREUSEDJMP; goto bail; } } /* .-------------------------. */ /* | by now we should have a | */ /* | valid operator. Some of | */ /* | them require operands | */ /* | while others operate | */ /* | directly on the stack. | */ /* '-------------------------' */ if(is_valid_oc(opcode)) { ADJUST_BCBUF; byte_code[bc_fill++] = opcode; // compile opcode specific switch(opcode) { case HALT: case POP: case ADD: case SUB: case MUL: case DIV: case DUP: case BAN: case BLK: // zero operand opcodes break; case LOAD: case STO: case PUSH: // LOAD NUMLIT // STO NUMLIT // PUSH NUMLIT // // they behave pretty // much the same... // // a missing operand // means a literal 0 token = next_token(tok); if(!token) { error_code = EOPERAND; goto bail; } // after this switch // we need to consume // a newline. If the // PUSH has no operand // then we already // read this newline // and we need to shrt // circuit execution. int shortcircuit = 0; size_t tlen; if(strcmp(token, "\n") == 0) { shortcircuit = 1; tlen = 0; } else { tlen = strlen(token); if(strncmp("sololearn", token, tlen) != 0) { error_code = EILLEGAL; goto bail; } } // store numeric lit. ADJUST_BCBUF; byte_code[bc_fill++] = (char)tlen; if(shortcircuit) continue; break; case CMP: // CMP L1 L2 L3 // // arithmetic if type // comparison. It re- // quires two jump // labels for(int i = 0; i < 2; i++) { token = next_token(tok); if(!token) { error_code = EOPERAND; goto bail; } // is jump label valid? int idx = key_index(token); if(idx == -1) { error_code = EILLEGAL; goto bail; } // add jump label // the jump table // and save a 0 // operand for now ADJUST_JMPTABLE; jmp_table[jt_idx++] = ((short) idx) << 16 | ((short)bc_fill); // store 0 ADJUST_BCBUF; byte_code[bc_fill++] = '\0'; } break; case MOD: // MOD LBL // // unconditional jump // to label LBL token = next_token(tok); if(!token) { error_code = EOPERAND; goto bail; } // is lable valid? int idx = key_index(token); if(idx == -1) { error_code = EILLEGAL; goto bail; } // add jump label // the jump table // and save a 0 // operand for now ADJUST_JMPTABLE; jmp_table[jt_idx++] = ((short) idx) << 16 | ((short)bc_fill); // store 0 ADJUST_BCBUF; byte_code[bc_fill++] = '\0'; break; default: // this shouldn't happen // but better to be safe // than sorry! error_code = EOPCODE; goto bail; } // switch CONSUME_NEWLINE; } // is valid opcode else { error_code = EOPCODE; goto bail; } } while(1); /* .------------------------. */ /* | resolve jump labels | */ /* '------------------------' */ for(size_t i = 0; i < jt_idx; i++) { short idx; short dst; dst = jmp_table[i] & 0xFFFF; idx = (jmp_table[i] >> 16); if(sym_table[idx] == 0) { error_code = EUNRJMP; tok->line = 0; tok->pos_a = dst; goto bail; } byte_code[dst] = sym_table[idx] - dst; } *bcsz = bc_fill; free(jmp_table); return byte_code; bail: if(byte_code) free(byte_code); if(jmp_table) free(jmp_table); return NULL; } // SL Virtual Machine typedef char* stack_t; typedef char regs_t; struct slvm_s { char* bc; // internal stack stack_t stack; int stack_size; // internal registers // for temporary storage // using STO and LOAD regs_t regs[10]; int ip, // instruction pointer sp; // stack pointer }; int init_vm(struct slvm_s *vm, char *bc) { // assert virtual machine and byte code if(!vm) return ENOMEM; if(!bc) return ENOMEM; vm->stack = (stack_t) calloc(100, sizeof(char)); if(!vm->stack) return ENOMEM; vm->stack_size = 100; vm->bc = bc; vm->sp = 0; vm->ip = 0; return 0; } #define EXEC_SWITCH \ switch(vm.bc[vm.ip]) { #define END_EXEC_SWITCH \ } \ #define REGISTER_CMD(name, opcode) \ case opcode: \ do #define END_REGISTER \ while(0); \ break; #define NEXT(i) \ vm.ip += i; int execute(char *bc) { int err; struct slvm_s vm; err = init_vm(&vm, bc); if(err != 0) return err; // execution loop do { EXEC_SWITCH REGISTER_CMD("halt", HALT) { // terminate execution err = ENOERROR; goto term; } END_REGISTER // elementary stack operations REGISTER_CMD("push", PUSH) { if(vm.sp == vm.stack_size) { // readjust the stack stack_t tmp = vm.stack; vm.stack = realloc(vm.stack, vm.stack_size + 100); if(!vm.stack) { vm.stack = tmp; err = ENOMEM; goto term; } vm.stack_size += 100; } vm.stack[vm.sp++] = vm.bc[vm.ip + 1]; NEXT(2) } END_REGISTER REGISTER_CMD("pop", POP) { if(vm.sp == 0) { err = ESPOP; goto term; } vm.sp--; NEXT(1) } END_REGISTER // on stack arithmetics REGISTER_CMD("add", ADD) { if(vm.sp < 2) { err = EINSUFFOP; goto term; } char x = vm.stack[--vm.sp]; char y = vm.stack[--vm.sp]; vm.stack[vm.sp++] = x + y; NEXT(1) } END_REGISTER REGISTER_CMD("sub", SUB) { if(vm.sp < 2) { err = EINSUFFOP; goto term; } char x = vm.stack[--vm.sp]; char y = vm.stack[--vm.sp]; vm.stack[vm.sp++] = y -x; NEXT(1) } END_REGISTER REGISTER_CMD("mul", MUL) { if(vm.sp < 2) { err = EINSUFFOP; goto term; } char x = vm.stack[--vm.sp]; char y = vm.stack[--vm.sp]; vm.stack[vm.sp++] = x * y; NEXT(1) } END_REGISTER REGISTER_CMD("idiv_rem", DIV) { if(vm.sp < 2) { err = EINSUFFOP; goto term; } char x = vm.stack[--vm.sp]; char y = vm.stack[--vm.sp]; vm.stack[vm.sp++] = y % x; vm.stack[vm.sp++] = y / x; NEXT(1) } END_REGISTER REGISTER_CMD("duplicate", DUP) { if(vm.sp < 1) { err = EINSUFFOP; goto term; } char x = vm.stack[vm.sp-1]; vm.stack[vm.sp++] = x; NEXT(1) } END_REGISTER // (un-)conditional jumps REGISTER_CMD("compare", CMP) { if(vm.sp < 2) { err = EINSUFFOP; goto term; } char x = vm.stack[vm.sp - 1]; char y = vm.stack[vm.sp - 2]; char on_zero = vm.bc[vm.ip+1]; char on_positive = vm.bc[vm.ip+2]; y -= x; if(y < 0) { NEXT(3) } else if(y == 0) { vm.ip += on_zero + 1; } else { vm.ip += on_positive + 2; } } END_REGISTER REGISTER_CMD("jump", MOD) { vm.ip += vm.bc[vm.ip+1] + 1; } END_REGISTER // register storage/load commands REGISTER_CMD("store", STO) { if(vm.sp < 1) { err = EINSUFFOP; goto term; } char idx = vm.bc[vm.ip+1]; char x = vm.stack[--vm.sp]; vm.regs[(size_t)idx] = x; NEXT(2) } END_REGISTER REGISTER_CMD("load", LOAD) { if(vm.sp == vm.stack_size) { // readjust the stack stack_t tmp = vm.stack; vm.stack = realloc(vm.stack, vm.stack_size + 100); if(!vm.stack) { vm.stack = tmp; err = ENOMEM; goto term; } vm.stack_size += 100; } vm.stack[vm.sp++] = vm.regs[(size_t)vm.bc[vm.ip + 1]]; NEXT(2) } END_REGISTER // special command // (CISC instruction set! yayy!) REGISTER_CMD("print", BAN) { while(vm.sp && vm.stack[--vm.sp] != '\0') { printf("%c", vm.stack[vm.sp]); } puts(""); NEXT(1) } END_REGISTER REGISTER_CMD("nprint", BLK) { printf("%d\n", vm.stack[--vm.sp]); NEXT(1) } END_REGISTER END_EXEC_SWITCH } while(1); term: if(vm.stack) free(vm.stack); vm.stack = NULL; vm.ip = 0; vm.sp = 0; return err; } void disassemble(char *bc, size_t n) { int err; struct slvm_s vm; const char *fmt_zero = "%02x %-4s\n"; const char *fmt_one = "%02x %02x %-4s %02x\n"; const char *fmt_two = "%02x %02x %02x %-4s %02x %02x\n"; const char *fmt_ip = "+%04x "; err = init_vm(&vm, bc); if(err != 0) return; // execution loop do { printf(fmt_ip, vm.ip); EXEC_SWITCH REGISTER_CMD("halt", HALT) { printf(fmt_zero, HALT, "HALT"); NEXT(1) } END_REGISTER // elementary stack operations REGISTER_CMD("push", PUSH) { printf(fmt_one, PUSH, vm.bc[vm.ip+1], "PUSH", vm.bc[vm.ip + 1]); NEXT(2) } END_REGISTER REGISTER_CMD("pop", POP) { printf(fmt_zero, POP, "POP"); NEXT(1) } END_REGISTER // on stack arithmetics REGISTER_CMD("add", ADD) { printf(fmt_zero, ADD, "ADD"); NEXT(1) } END_REGISTER REGISTER_CMD("sub", SUB) { printf(fmt_zero, SUB, "SUB"); NEXT(1) } END_REGISTER REGISTER_CMD("mul", MUL) { printf(fmt_zero, MUL, "MUL"); NEXT(1) } END_REGISTER REGISTER_CMD("idiv_rem", DIV) { printf(fmt_zero, DIV, "IDIV"); NEXT(1) } END_REGISTER REGISTER_CMD("duplicate", DUP) { printf(fmt_zero, DUP, "DUP"); NEXT(1) } END_REGISTER // (un-)conditional jumps REGISTER_CMD("compare", CMP) { printf(fmt_two, CMP, (unsigned char)vm.bc[vm.ip+1], (unsigned char)vm.bc[vm.ip+2], "CMP", (unsigned char)vm.bc[vm.ip+1], (unsigned char)vm.bc[vm.ip+2]); NEXT(3) } END_REGISTER REGISTER_CMD("jump", MOD) { printf(fmt_one, MOD, (unsigned char) vm.bc[vm.ip+1], "JMP", (unsigned char) vm.bc[vm.ip+1]); NEXT(2) } END_REGISTER // register storage/load REGISTER_CMD("store", STO) { printf(fmt_one, STO, vm.bc[vm.ip+1], "STO", vm.bc[vm.ip+1]); NEXT(2) } END_REGISTER REGISTER_CMD("load", LOAD) { printf(fmt_one, LOAD, vm.bc[vm.ip+1], "LOAD", vm.bc[vm.ip+1]); NEXT(2) } END_REGISTER // special command // (CISC instruction set! yayy!) REGISTER_CMD("print", BAN) { printf(fmt_zero, BAN, "PRNT"); NEXT(1) } END_REGISTER REGISTER_CMD("nprint", BLK) { printf(fmt_zero, BLK, "NPRT"); NEXT(1) } END_REGISTER END_EXEC_SWITCH } while(vm.ip < n); if(vm.stack) free(vm.stack); vm.stack = NULL; vm.ip = 0; vm.sp = 0; }

Collatz in SL Lang