vm.c

#include <stdio.h>
#include <stdlib.h>
enum expr_type { END, ERR, VAL, VAR, BIN, TRI, LET, };

enum bin_op { MUL, ADD, LT, };
static const char* const bin_op_name[] = {
   [MUL] = "*",
   [ADD] = "+",
   [LT]  = "<",
};

struct expr;
struct bin {
   int op;
   const struct expr *left, *right;
};
struct tri {
   const struct expr *cond, *left, *right;
};
struct let_bind {
   const struct expr *left, *right;
   const struct let_bind *next;
};
struct let {
   const struct let_bind *bind;
   const struct expr *in;
};
struct expr {
   int type;
   union {
      int val;
      int var; // index to var array
      struct bin bin;
      struct tri tri;
      struct let let;
   };
};

static const struct expr a = {
   .type = VAL,
   .val  = 6,
}, b = {
   .type = VAL,
   .val  = 7,
}, e0 = {
   .type = BIN,
   .bin = { MUL, &a, &b, }, // 6 * 7
}, c = {
   .type = VAL,
   .val  = 1,
}, d = {
   .type = VAL,
   .val  = 2,
}, e = {
   .type = VAL,
   .val  = 3,
}, f = {
   .type = BIN,
   .bin = { MUL, &d, &e, }, // 2 * 3
}, e1 = {
   .type = BIN,
   .bin = { ADD, &c, &f, }, // 1 + 2 * 3
}, g = {
   .type = BIN,
   .bin = { LT, &a, &b, }, // 6 < 7
}, e2 = {
   .type = TRI,
   .tri = { &g, &a, &b, }, // max(6, 7) = if (6 < 7) then 6 else 7
}, h = {
   .type = TRI,
   .tri = { &g, &f, &e1, }, // if (6 < 7) then (2 * 3) else (1 + 2 * 3)
}, e3 = {
   .type = BIN,
   .bin = { ADD, &c, &h, }, // 1 + (if (6 < 7) then (2 * 3) else (1 + 2 * 3))
}, i = {
   .type = VAR,
   .var = 0,
}, e4 = {
   .type = TRI,
   .tri = { &g, &c, &i, }, // if (6 < 7) then (1) else (a)
}, j = {
   .type = VAR,
   .var = 1,
}, k = {
   .type = BIN,
   .bin = { MUL, &i, &j, }, // 2 * 3
}, ee = {
   .type = END,
};
static const struct let_bind
   lb_a = { &i, &b, NULL, },
   lb_b = { &j, &b, NULL, },
   lb_c = { &i, &a, &lb_b, };
static const struct expr e5 = {
   .type = LET,
   .let = { .bind = &lb_a, .in = &e4, }
}, e6 = {
   .type = LET,
   .let = { .bind = &lb_c, .in = &k, }
};

static const struct expr x[] = {
   e0, e1, e2, e3, e4, e5, e6, ee,
};

static const struct expr err = { .type = ERR, };

static void
die(const char *s)
{
   printf("die: %s\n", s);
   exit(1);
}

static const struct let_bind *var = NULL;
static void
set_var(const struct let_bind *bind)
{
   struct let_bind *t = malloc(sizeof *t);
   if (!t) die("malloc");
   *t = *bind;
   t->next = var;
   var = t;

//   for (const struct let_bind *i = var; i; i = i->next) {
//      if (i->left->type != VAR) continue;
//      printf("set_var: %c = %d\n", 'a' + i->left->var, i->right->val); }
}
static void
del_var(void)
{
// printf("del_var: %c = %d\n", 'a' + var->left->var, var->right->val);
   if (!var) die("del_var");
   struct let_bind *t = (struct let_bind *)var;
   var = var->next;
   free(t);
}
static struct expr
ref_var(const struct expr e)
{
   if (e.type != VAR) return err;
   for (const struct let_bind *i = var; i; i = i->next) {
      if (i->left->type != VAR) continue;
// printf("ref_var: %c = %d\n", 'a' + i->left->var, i->right->val);
      if (i->left->var != e.var) continue;
      return *i->right; }
}

static const struct expr
bincalc(const int bin, const struct expr a, const struct expr b)
{
   struct expr r;

   if (a.type != VAL || b.type != VAL) {
      r.type = ERR; return r; }

   switch (bin) {
   case MUL: r.type = VAL; r.val = a.val * b.val; break;
   case ADD: r.type = VAL; r.val = a.val + b.val; break;
   case LT:  r.type = VAL; r.val = a.val < b.val; break;
   default:  r.type = ERR;
   }
   return r;
}

static const struct expr eval(struct expr e);

static const struct expr
eval_eager(const struct expr e)
{
   const struct expr r = eval(e);

   if (r.type == VAL) return r;
   if (r.type == ERR) return r;

   return eval_eager(r);
}

static int n_indent;
static void indent(void) { n_indent++; }
static void dedent(void) { n_indent--; }
static void put_indent(void) {
   for (int i = 0; i < n_indent; i++) {
      putchar(' ');
      putchar(' ');
      putchar(' '); }
}

static const struct expr
eval(const struct expr e)
{
   struct expr r, t0, t1;
   indent();

   switch (e.type) {
   case VAL:
      put_indent(); printf("VAL: %d\n", e.val);
      r = e; break;
   case VAR:
      put_indent(); printf("VAR %c\n", 'a' + e.var);
      r = ref_var(e);
      put_indent(); printf("VAR: %d\n", r.val);
      break;
   case BIN:
      put_indent(); printf("BIN %s\n", bin_op_name[e.bin.op]);
      t0 = eval_eager(*e.bin.left);
      t1 = eval_eager(*e.bin.right);
      r = bincalc(e.bin.op, t0, t1);
      put_indent(); printf("BIN: %d\n", r.val);
      break;
   case TRI:
      put_indent(); puts("TRI");
      t0 = eval_eager(*e.tri.cond);
      if (t0.type != VAL) { r = err; break; }
      put_indent(); printf("TRI: %s\n", t0.val ? "LEFT" : "RIGHT");
      r = t0.val ? *e.bin.left: *e.bin.right; break;
   case LET: {
      int n_let = 0;
      put_indent(); puts("LET");
      for (const struct let_bind *i = e.let.bind; i; i = i->next) {
         set_var(i);
         n_let++; }
      r = eval_eager(*e.let.in);
      for (int i = 0; i < n_let; i++) del_var();
      put_indent(); puts("LET:");
      break; }
   default:
      put_indent(); puts("ERR");
      r = err; break; }

   dedent();
   return r;
}

static void
show(const struct expr e)
{
   switch (e.type) {
   case VAL:
      printf("%d", e.val); break;
   case VAR:
      printf("%c", 'a' + e.var); break;
   case BIN:
      printf("(");
      show(*e.bin.left);
      printf(" %s ", bin_op_name[e.bin.op]);
      show(*e.bin.right);
      printf(")"); break;
   case TRI:
      printf("(if ");
      show(*e.tri.cond);
      printf(" then ");
      show(*e.tri.left);
      printf(" else ");
      show(*e.tri.right);
      printf(")"); break;
   case LET:
      printf("(let ");
      for (const struct let_bind *i = e.let.bind; i; i = i->next) {
         show(*i->left);
         printf(" = ");
         show(*i->right);
         if (i->next) printf(", "); }
      printf(" in ");
      show(*e.let.in);
      printf(")"); break;
   default:
      printf(" *** ERR *** "); }
}

int
main(void)
{
   for (const struct expr *p = x; p->type != END; p++) {
      show(*p); putchar('\n');
      const struct expr y = eval_eager(*p);
      if (y.type == VAL) printf("==> VAL %d\n", y.val);
      if (y.type == ERR) printf("==> ERR\n"); }
   return 0;
}