rs_mpsl/rs_mpsl.c

   1 /*
   2
   3     Reverse Stack MPSL
   4
   5     Angel Ortega <angel@triptico.com>
   6
   7     This is an experiment of a reverse-stack MPSL.
   8
   9     Also, the executor includes a maximum number of
  10     milliseconds before yielding, with the capability
  11     of restarting where it left in the subsequent call.
  12
  13 */
  14
  15 #include <stdio.h>
  16 #include <mpdm.h>
  17
  18 typedef enum {
  19     OP_LITERAL,
  20     OP_ADD,
  21     OP_SUB,
  22     OP_MUL,
  23     OP_DIV,
  24     OP_EQ,
  25     OP_NEQ,
  26     OP_LT,
  27     OP_LE,
  28     OP_GT,
  29     OP_GE,
  30     OP_PC,
  31     OP_CALL,
  32     OP_PATH,
  33     OP_RETURN,
  34     OP_IF,
  35     OP_IFELSE,
  36     OP_WHILE,
  37     OP_FOREACH,
  38     OP_ASSIGN,
  39     OP_SYMVAL,
  40     OP_APUSH,
  41     OP_HSET,
  42     OP_PRINT,
  43     OP_DUMP
  44 } mpsl_op_t;
  45
  46 #define mpsl_is_true(v) mpdm_ival(v)
  47
  48 void rs_mpsl_reset_machine(mpdm_t machine)
  49 {
  50     mpdm_hset_s(machine, L"stack",      MPDM_A(0));
  51     mpdm_hset_s(machine, L"c_stack",    MPDM_A(0));
  52     mpdm_hset_s(machine, L"pc",         MPDM_I(0));
  53 }
  54
  55
  56 int rs_mpsl_exec1(mpdm_t prg, mpdm_t stack, mpdm_t c_stack, int *ppc)
  57 {
  58     mpsl_op_t opcode;
  59     int pc;
  60     int ret = 1;
  61
  62     pc = *ppc;
  63
  64     /* get the opcode */
  65     opcode = mpdm_ival(mpdm_aget(prg, pc++));
  66
  67     switch (opcode) {
  68     case OP_LITERAL:
  69         /* literal: next thing in pc is the literal */
  70         mpdm_push(stack, mpdm_clone(mpdm_aget(prg, pc++)));
  71         break;
  72
  73     case OP_ADD:
  74     case OP_SUB:
  75     case OP_MUL:
  76     case OP_DIV:
  77         {
  78             double v2   = mpdm_rval(mpdm_pop(stack));
  79             double v1   = mpdm_rval(mpdm_pop(stack));
  80             double r;
  81
  82             switch (opcode) {
  83             case OP_ADD:    r = v1 + v2; break;
  84             case OP_SUB:    r = v1 - v2; break;
  85             case OP_MUL:    r = v1 * v2; break;
  86             case OP_DIV:    r = v1 / v2; break;
  87             }
  88
  89             mpdm_push(stack, MPDM_R(r));
  90         }
  91
  92         break;
  93
  94     case OP_EQ:
  95     case OP_NEQ:
  96     case OP_LT:
  97     case OP_LE:
  98     case OP_GT:
  99     case OP_GE:
 100         {
 101             double v2   = mpdm_rval(mpdm_pop(stack));
 102             double v1   = mpdm_rval(mpdm_pop(stack));
 103             int r;
 104
 105             switch (opcode) {
 106             case OP_EQ:     r = v1 == v2; break;
 107             case OP_NEQ:    r = v1 != v2; break;
 108             case OP_LT:     r = v1 < v2; break;
 109             case OP_LE:     r = v1 <= v2; break;
 110             case OP_GT:     r = v1 > v2; break;
 111             case OP_GE:     r = v1 >= v2; break;
 112             }
 113
 114             mpdm_push(stack, MPDM_I(r));
 115         }
 116
 117         break;
 118
 119     case OP_PC:
 120         /* push the program counter */
 121         mpdm_push(stack, MPDM_I(pc));
 122         break;
 123
 124     case OP_CALL:
 125         /* call the value on the stack */
 126         {
 127             mpdm_t x = mpdm_pop(stack);
 128
 129             /* executable value? arguments are in the stack in an array */
 130             if (MPDM_IS_EXEC(x)) {
 131                 mpdm_t args = mpdm_pop(stack);
 132                 mpdm_push(stack, mpdm_exec(x, args, NULL));
 133             }
 134             else {
 135                 /* "lightweight" call */
 136                 mpdm_push(c_stack, MPDM_I(pc));
 137                 pc = mpdm_ival(x);
 138             }
 139         }
 140
 141         break;
 142
 143     case OP_PATH:
 144         /* new code path */
 145         mpdm_push(stack, MPDM_I(pc));
 146
 147         {
 148             /* move beyond the appropriate return */
 149             int l = 1;
 150
 151             while (l && pc < mpdm_size(prg)) {
 152                 opcode = mpdm_ival(mpdm_aget(prg, pc++));
 153
 154                 if (opcode == OP_PATH)
 155                     l++;
 156                 if (opcode == OP_RETURN)
 157                     l--;
 158             }
 159
 160             /* return not found? error */
 161             if (l)
 162                 ret = -2;
 163         }
 164
 165         break;
 166
 167     case OP_RETURN:
 168         /* if there is a return address, use it;
 169            otherwise, trigger error */
 170         if (mpdm_size(c_stack))
 171             pc = mpdm_ival(mpdm_pop(c_stack));
 172         else
 173             ret = -1;
 174
 175         break;
 176
 177     case OP_IF:
 178         if (mpsl_is_true(mpdm_pop(stack))) {
 179             /* push return address and call */
 180             mpdm_push(c_stack, MPDM_I(pc));
 181             pc = mpdm_ival(mpdm_pop(stack));
 182         }
 183         else
 184             mpdm_adel(stack, -1);
 185
 186         break;
 187
 188     case OP_IFELSE:
 189         /* always push return address */
 190         mpdm_push(c_stack, MPDM_I(pc));
 191
 192         if (mpsl_is_true(mpdm_pop(stack))) {
 193             /* drop false pc */
 194             mpdm_adel(stack, -1);
 195
 196             /* jump to true pc */
 197             pc = mpdm_ival(mpdm_pop(stack));
 198         }
 199         else {
 200             /* jump to false pc */
 201             pc = mpdm_ival(mpdm_pop(stack));
 202
 203             /* drop true pc */
 204             mpdm_adel(stack, -1);
 205         }
 206
 207         break;
 208
 209     case OP_WHILE:
 210         /* in the stack:
 211             <body pc> <condition pc> <condition>
 212         */
 213         if (mpdm_ival(mpdm_pop(stack))) {
 214             /* set the return address to the cond. pc */
 215             mpdm_push(c_stack, mpdm_aget(stack, -1));
 216
 217             /* jump to the body */
 218             pc = mpdm_ival(mpdm_aget(stack, -2));
 219         }
 220         else {
 221             /* drop both pcs */
 222             mpdm_adel(stack, -1);
 223             mpdm_adel(stack, -1);
 224         }
 225
 226         break;
 227
 228     case OP_FOREACH:
 229         /* in the stack:
 230             <body pc> <array> <iterator>
 231         */
 232         {
 233             int i = mpdm_ival(mpdm_pop(stack));
 234             mpdm_t v;
 235
 236             if (mpdm_iterator(mpdm_aget(stack, -1), &i, &v, NULL)) {
 237                 /* another iteration */
 238
 239                 /* push return value back over 'foreach' */
 240                 mpdm_push(c_stack, MPDM_I(pc - 1));
 241
 242                 /* call the body */
 243                 pc = mpdm_ival(mpdm_aget(stack, -2));
 244
 245                 /* stack the iterator back */
 246                 mpdm_push(stack, MPDM_I(i));
 247
 248                 /* stack the element (the body should pick it) */
 249                 mpdm_push(stack, v);
 250             }
 251             else {
 252                 /* clean stack */
 253                 mpdm_adel(stack, -1);
 254                 mpdm_adel(stack, -1);
 255             }
 256         }
 257
 258         break;
 259
 260     case OP_PRINT:
 261         /* prints the value in the stack */
 262         mpdm_write_wcs(stdout, mpdm_string(mpdm_pop(stack)));
 263         break;
 264
 265     case OP_DUMP:
 266         {
 267             mpdm_t v = mpdm_pop(stack);
 268             mpdm_dump(v);
 269             mpdm_void(v);
 270         }
 271         break;
 272
 273     case OP_ASSIGN:
 274         /* assign a value to a symbol */
 275         {
 276             mpdm_t s = mpdm_pop(stack);
 277             mpdm_t v = mpdm_pop(stack);
 278             mpdm_hset(mpdm_root(), s, v);
 279         }
 280         break;
 281
 282     case OP_SYMVAL:
 283         /* get symbol value */
 284         mpdm_push(stack, mpdm_hget(mpdm_root(), mpdm_pop(stack)));
 285         break;
 286
 287     case OP_APUSH:
 288         /* pushes a value into an array on the stack */
 289         {
 290             mpdm_t v = mpdm_pop(stack);
 291             mpdm_push(mpdm_aget(stack, -1), v);
 292         }
 293         break;
 294
 295     case OP_HSET:
 296         /* sets a hash's key/value pair */
 297         {
 298             mpdm_t v = mpdm_pop(stack);
 299             mpdm_t k = mpdm_pop(stack);
 300             mpdm_hset(mpdm_aget(stack, -1), k, v);
 301         }
 302     }
 303
 304     *ppc = pc;
 305
 306     /* got to the end? trigger exit */
 307     if (pc == mpdm_size(prg))
 308         ret = 0;
 309
 310     return ret;
 311 }
 312
 313 #include <time.h>
 314
 315 int rs_mpsl_exec(mpdm_t machine, int msecs)
 316 {
 317     int ret;
 318     mpdm_t prg      = mpdm_hget_s(machine, L"prg");
 319     mpdm_t stack    = mpdm_hget_s(machine, L"stack");
 320     mpdm_t c_stack  = mpdm_hget_s(machine, L"c_stack");
 321     int pc          = mpdm_ival(mpdm_hget_s(machine, L"pc"));
 322     clock_t max;
 323
 324     /* maximum running time */
 325     max = msecs ? (clock() + (msecs * CLOCKS_PER_SEC) / 1000) : 0x7fffffff;
 326
 327     while (
 328         pc < mpdm_size(prg) &&
 329         (ret = rs_mpsl_exec1(prg, stack, c_stack, &pc)) > 0 &&
 330         clock() < max
 331     );
 332
 333     mpdm_hset_s(machine, L"pc", MPDM_I(pc));
 334
 335     return ret;
 336 }
 337
 338
 339 static mpdm_t add_arg(mpdm_t prg, mpdm_t arg)
 340 {
 341     return mpdm_push(prg, arg);
 342 }
 343
 344 static mpdm_t add_ins(mpdm_t prg, mpsl_op_t opcode)
 345 {
 346     return mpdm_push(prg, MPDM_I((int) opcode));
 347 }
 348
 349
 350 int main(int argc, char *argv[])
 351 {
 352     mpdm_t v;
 353     mpdm_t machine, prg;
 354     int ret;
 355     int n;
 356
 357     mpdm_startup();
 358
 359     machine = mpdm_ref(MPDM_H(0));
 360     prg = mpdm_hset_s(machine, L"prg", MPDM_A(0));
 361     rs_mpsl_reset_machine(machine);
 362
 363     add_ins(prg, OP_LITERAL);
 364     add_arg(prg, MPDM_I(1));
 365     add_ins(prg, OP_LITERAL);
 366     add_arg(prg, MPDM_I(2));
 367     add_ins(prg, OP_LT);
 368     add_ins(prg, OP_PRINT);
 369     add_ins(prg, OP_PATH);
 370     add_ins(prg, OP_LITERAL);
 371     add_arg(prg, MPDM_LS(L"true\n"));
 372     add_ins(prg, OP_PRINT);
 373     add_ins(prg, OP_RETURN);
 374     add_ins(prg, OP_PATH);
 375     add_ins(prg, OP_LITERAL);
 376     add_arg(prg, MPDM_LS(L"false\n"));
 377     add_ins(prg, OP_PRINT);
 378     add_ins(prg, OP_RETURN);
 379     add_ins(prg, OP_LITERAL);
 380     add_arg(prg, MPDM_I(1));
 381     add_ins(prg, OP_IFELSE);
 382     add_ins(prg, OP_LITERAL);
 383     add_arg(prg, MPDM_I(2));
 384     add_ins(prg, OP_LITERAL);
 385     add_arg(prg, MPDM_I(3));
 386     add_ins(prg, OP_ADD);
 387     add_ins(prg, OP_PRINT);
 388     add_ins(prg, OP_LITERAL);
 389     add_arg(prg, MPDM_LS(L"!!!\n"));
 390     add_ins(prg, OP_PRINT);
 391     add_ins(prg, OP_LITERAL);
 392     add_arg(prg, MPDM_LS(L"content\n"));
 393     add_ins(prg, OP_LITERAL);
 394     add_arg(prg, MPDM_LS(L"VAR1"));
 395     add_ins(prg, OP_ASSIGN);
 396     add_ins(prg, OP_LITERAL);
 397     add_arg(prg, MPDM_LS(L"VAR1"));
 398     add_ins(prg, OP_SYMVAL);
 399     add_ins(prg, OP_PRINT);
 400     add_ins(prg, OP_LITERAL);
 401     add_arg(prg, MPDM_I(3));
 402     add_ins(prg, OP_LITERAL);
 403     add_arg(prg, MPDM_I(4));
 404     add_ins(prg, OP_ADD);
 405     add_ins(prg, OP_LITERAL);
 406     add_arg(prg, MPDM_LS(L"VAR1"));
 407     add_ins(prg, OP_ASSIGN);
 408     add_ins(prg, OP_LITERAL);
 409     add_arg(prg, MPDM_LS(L"VAR1"));
 410     add_ins(prg, OP_SYMVAL);
 411     add_ins(prg, OP_PRINT);
 412
 413     /* VAR1 = VAR1 + 4 ; print VAR1 */
 414     add_ins(prg, OP_LITERAL);
 415     add_arg(prg, MPDM_LS(L"VAR1"));
 416     add_ins(prg, OP_SYMVAL);
 417     add_ins(prg, OP_LITERAL);
 418     add_arg(prg, MPDM_I(4));
 419     add_ins(prg, OP_ADD);
 420     add_ins(prg, OP_LITERAL);
 421     add_arg(prg, MPDM_LS(L"VAR1"));
 422     add_ins(prg, OP_ASSIGN);
 423     add_ins(prg, OP_LITERAL);
 424     add_arg(prg, MPDM_LS(L"VAR1"));
 425     add_ins(prg, OP_SYMVAL);
 426     add_ins(prg, OP_PRINT);
 427
 428     rs_mpsl_exec(machine, 0);
 429
 430     prg = mpdm_hset_s(machine, L"prg", MPDM_A(0));
 431     rs_mpsl_reset_machine(machine);
 432
 433     /* VAR1 = 0 */
 434     add_ins(prg, OP_LITERAL);
 435     add_arg(prg, MPDM_I(0));
 436     add_ins(prg, OP_LITERAL);
 437     add_arg(prg, MPDM_LS(L"VAR1"));
 438     add_ins(prg, OP_ASSIGN);
 439
 440     /* { print VAR1; print "\n"; VAR1 = VAR1 + 1; } */
 441     add_ins(prg, OP_PATH);
 442     add_ins(prg, OP_LITERAL);
 443     add_arg(prg, MPDM_LS(L"VAR1"));
 444     add_ins(prg, OP_SYMVAL);
 445     add_ins(prg, OP_PRINT);
 446     add_ins(prg, OP_LITERAL);
 447     add_arg(prg, MPDM_LS(L"\n"));
 448     add_ins(prg, OP_PRINT);
 449     add_ins(prg, OP_LITERAL);
 450     add_arg(prg, MPDM_LS(L"VAR1"));
 451     add_ins(prg, OP_SYMVAL);
 452     add_ins(prg, OP_LITERAL);
 453     add_arg(prg, MPDM_I(1));
 454     add_ins(prg, OP_ADD);
 455     add_ins(prg, OP_LITERAL);
 456     add_arg(prg, MPDM_LS(L"VAR1"));
 457     add_ins(prg, OP_ASSIGN);
 458     add_ins(prg, OP_RETURN);
 459
 460     /* | VAR1 < 10 while */
 461     add_ins(prg, OP_PC);
 462     add_ins(prg, OP_LITERAL);
 463     add_arg(prg, MPDM_LS(L"VAR1"));
 464     add_ins(prg, OP_SYMVAL);
 465     add_ins(prg, OP_LITERAL);
 466     add_arg(prg, MPDM_I(10));
 467     add_ins(prg, OP_LT);
 468     add_ins(prg, OP_WHILE);
 469
 470     printf("*\n");
 471     rs_mpsl_exec(machine, 1);
 472     printf("*\n");
 473     rs_mpsl_exec(machine, 0);
 474
 475     prg = mpdm_hset_s(machine, L"prg", MPDM_A(0));
 476     rs_mpsl_reset_machine(machine);
 477
 478     add_ins(prg, OP_LITERAL);
 479     add_arg(prg, MPDM_A(0));
 480     add_ins(prg, OP_LITERAL);
 481     add_arg(prg, MPDM_I(1));
 482     add_ins(prg, OP_APUSH);
 483     add_ins(prg, OP_LITERAL);
 484     add_arg(prg, MPDM_I(2));
 485     add_ins(prg, OP_APUSH);
 486     add_ins(prg, OP_DUMP);
 487
 488     rs_mpsl_exec(machine, 0);
 489
 490     prg = mpdm_hset_s(machine, L"prg", MPDM_A(0));
 491     rs_mpsl_reset_machine(machine);
 492
 493     add_ins(prg, OP_LITERAL);
 494     add_arg(prg, MPDM_H(0));
 495     add_ins(prg, OP_LITERAL);
 496     add_arg(prg, MPDM_LS(L"font_face"));
 497     add_ins(prg, OP_LITERAL);
 498     add_arg(prg, MPDM_LS(L"Courier"));
 499     add_ins(prg, OP_HSET);
 500     add_ins(prg, OP_DUMP);
 501
 502     rs_mpsl_exec(machine, 0);
 503
 504     prg = mpdm_hset_s(machine, L"prg", MPDM_A(0));
 505     rs_mpsl_reset_machine(machine);
 506
 507     /* { + 2 / } "avg" = */
 508     add_ins(prg, OP_PATH);
 509     add_ins(prg, OP_ADD);
 510     add_ins(prg, OP_LITERAL);
 511     add_arg(prg, MPDM_I(2));
 512     add_ins(prg, OP_DIV);
 513     add_ins(prg, OP_RETURN);
 514     add_ins(prg, OP_LITERAL);
 515     add_arg(prg, MPDM_LS(L"avg"));
 516     add_ins(prg, OP_ASSIGN);
 517
 518     /* 3 4 "avg" $ & ? */
 519     add_ins(prg, OP_LITERAL);
 520     add_arg(prg, MPDM_I(3));
 521     add_ins(prg, OP_LITERAL);
 522     add_arg(prg, MPDM_I(4));
 523     add_ins(prg, OP_LITERAL);
 524     add_arg(prg, MPDM_LS(L"avg"));
 525     add_ins(prg, OP_SYMVAL);
 526     add_ins(prg, OP_CALL);
 527     add_ins(prg, OP_PRINT);
 528
 529     rs_mpsl_exec(machine, 0);
 530
 531     prg = mpdm_hset_s(machine, L"prg", MPDM_A(0));
 532     rs_mpsl_reset_machine(machine);
 533
 534     /* { ? } */
 535     add_ins(prg, OP_PATH);
 536     add_ins(prg, OP_PRINT);
 537     add_ins(prg, OP_RETURN);
 538
 539     /* [1..10] 0 foreach */
 540     add_ins(prg, OP_LITERAL);
 541     v = MPDM_A(0);
 542     mpdm_ref(v);
 543     for (n = 10; n < 20; n++)
 544         mpdm_push(v, MPDM_I(n));
 545
 546     add_arg(prg, v);
 547     mpdm_unref(v);
 548
 549     add_ins(prg, OP_LITERAL);
 550     add_arg(prg, MPDM_I(0));
 551     add_ins(prg, OP_FOREACH);
 552
 553     rs_mpsl_exec(machine, 0);
 554
 555     return 0;
 556 }