Merge "init attribute-based encryption"

10 files changed, 2507 insertions, 0 deletions

diff --git a/moon-abe/pbc-0.5.14/pbc/bilinear.test b/moon-abe/pbc-0.5.14/pbc/bilinear.test
new file mode 100644
index 00000000..956c792e
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/pbc/bilinear.test
@@ -0,0 +1,50 @@
+define test_element_order(group) {
+  a := random(group);
+  o := order(group);
+  b := a^o;
+  CHECK(b == group(0));
+}
+
+define test_group_order() {
+  CHECK(order(G1) == order(G2));
+  CHECK(order(G2) == order(GT));
+  a := pairing(random(G1), random(G2));
+  o := order(GT);
+  b := a^o;
+  CHECK(b == GT(0));
+}
+
+define test_pairing_with_zero() {
+  CHECK(GT(0) == GT(1));
+  CHECK(pairing(G1(0), random(G2)) == GT(0));
+  CHECK(pairing(random(G1), G2(0)) == GT(0));
+  CHECK(pairing(G1(0), G2(0)) == GT(0));
+}
+
+define test_bilinear() {
+  a1 := random(G1);
+  b1 := random(G2);
+  x := random(Zr);
+  y := random(Zr);
+  CHECK(pairing(a1^x, b1) == pairing(a1, b1^x));
+  CHECK(pairing(a1^x, b1) == pairing(a1, b1)^x);
+  CHECK(pairing(a1, b1^x) == pairing(a1, b1)^x);
+  CHECK(pairing(a1^x, b1^y) == pairing(a1, b1)^(x*y));
+}
+
+define test(initfn) {
+  initfn();
+  test_element_order(G1);
+  test_element_order(G2);
+  test_element_order(GT);
+  test_group_order();
+  test_pairing_with_zero();
+  test_bilinear();
+}
+
+test(init_pairing_a);
+test(init_pairing_d);
+test(init_pairing_e);
+test(init_pairing_f);
+test(init_pairing_g);
+test(init_pairing_i);
diff --git a/moon-abe/pbc-0.5.14/pbc/g2_test.pbc b/moon-abe/pbc-0.5.14/pbc/g2_test.pbc
new file mode 100644
index 00000000..892660f9
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/pbc/g2_test.pbc
@@ -0,0 +1,37 @@
+# Exercises a bug found by Zhang Ye.
+
+define test_cmp_0(initfn) {
+  initfn();
+  CHECK(random(G2) != G2(0));
+  CHECK(G2(0) != random(G2));
+  CHECK(G2(0) == G2(0));
+  CHECK(random(G1) != G1(0));
+  CHECK(G1(0) != random(G1));
+  CHECK(G1(0) == G1(0));
+}
+
+test_cmp_0(init_pairing_a);
+test_cmp_0(init_pairing_d);
+test_cmp_0(init_pairing_e);
+test_cmp_0(init_pairing_f);
+test_cmp_0(init_pairing_g);
+test_cmp_0(init_pairing_i);
+
+# Exercises a bug found by Mario Di Raimondo.
+
+define test_g2_cmp(initfn) {
+  initfn();
+  a := rnd(G2);
+  m := rnd(Zr);
+  n := rnd(Zr);
+  CHECK((a^m)^n == a^(m*n));
+  CHECK(a != a^m);
+  CHECK(a != a^n);
+}
+
+test_g2_cmp(init_pairing_a);
+test_g2_cmp(init_pairing_d);
+test_g2_cmp(init_pairing_e);
+test_g2_cmp(init_pairing_f);
+test_g2_cmp(init_pairing_g);
+test_g2_cmp(init_pairing_i);
diff --git a/moon-abe/pbc-0.5.14/pbc/oldpbc.c b/moon-abe/pbc-0.5.14/pbc/oldpbc.c
new file mode 100644
index 00000000..525fe8f2
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/pbc/oldpbc.c
@@ -0,0 +1,1221 @@
+// Pairing-Based Calculator.
+// Mainly for demonstration purposes.
+//
+// It's times like these I wish C had garbage collection.
+
+#include <string.h>
+#include <ctype.h>
+#include <stdarg.h>
+#include <unistd.h> //for getopt
+#include "pbc.h"
+#include "pbc_z.h"
+#include "pbc_fp.h"
+
+#include "misc/darray.h"
+#include "misc/symtab.h"
+
+char *pbc_getline(const char *);
+
+enum {
+  t_none = 0,
+  t_id,
+  t_int,
+  t_string,
+  t_comma,
+  t_lparen,
+  t_rparen,
+  t_add,
+  t_sub,
+  t_mul,
+  t_div,
+  t_set,
+  t_pow,
+  t_unk,
+  t_function,
+  t_pairing,
+  t_element,
+  t_field,
+  t_err,
+};
+
+enum {
+  pe_expect_factor = 100,
+  pe_expect_rparen,
+  pe_arglist,
+  re_varnotfound = 200,
+  re_badlvalue,
+  re_funnotfound,
+  re_unimplemented,
+  re_badargcount,
+  re_badarg,
+  re_fieldmismatch,
+};
+
+static int option_echo = 0;
+
+static field_t Z;
+
+static int tok_type;
+//TODO: dynamic allocation:
+static char word[1024];
+
+struct id_s {
+  char *data;
+  int alloc;
+};
+typedef struct id_s *id_ptr;
+
+id_ptr id_new(char *id) {
+  id_ptr res = pbc_malloc(sizeof(struct id_s));
+  res->alloc = strlen(id) + 1;
+  res->data = pbc_malloc(res->alloc);
+  strcpy(res->data, id);
+  return res;
+}
+
+void id_delete(id_ptr id) {
+  pbc_free(id->data);
+  pbc_free(id);
+}
+
+struct tree_s {
+  int type;
+  void *data;
+  darray_t child;
+};
+typedef struct tree_s *tree_ptr;
+
+tree_ptr tree_new(int type, void *data) {
+  tree_ptr res = pbc_malloc(sizeof(struct tree_s));
+  res->type = type;
+  res->data = data;
+  darray_init(res->child);
+  return res;
+}
+
+static void delete_child(void *p) {
+  tree_delete(p);
+}
+
+void tree_delete(tree_ptr t) {
+  darray_forall(t->child, delete_child);
+  darray_clear(t->child);
+  switch(t->type) {
+    case t_id:
+    case t_string:
+    case t_function:
+    case t_int:
+      id_delete(t->data);
+      break;
+  }
+  pbc_free(t);
+}
+
+static char *currentline;
+static char *lexcp;
+
+
+static void lex(void) {
+  char c;
+  if (!lexcp) {
+    tok_type = t_none;
+    return;
+  }
+  c = *lexcp++;
+  skipwhitespace:
+  for (;;) {
+    if (!strchr(" \t\r\n", c)) break;
+    if (!c) {
+      tok_type = t_none;
+      return;
+    }
+    c = *lexcp++;
+  }
+
+  //comments start with '#' and end at a newline
+  if (c == '#') {
+    for (;;) {
+      c = *lexcp++;
+      if (!c) {
+        tok_type = t_none;
+        return;
+      }
+      if (c == '\n') break;
+    }
+    goto skipwhitespace;
+  }
+
+  //strings
+  if (c == '"') {
+    tok_type = t_string;
+    int i = 0;
+    for (;;) {
+      c = *lexcp++;
+      if (!c) {
+        //string continues on next line
+        word[i++] = '\n';
+        pbc_free(currentline);
+        currentline = pbc_getline(NULL);
+        if (!currentline) break;
+        if (option_echo) puts(currentline);
+        lexcp = currentline;
+        c = *lexcp++;
+      }
+      if (c == '"') {
+        break;
+      }
+      word[i++] = c;
+    }
+    word[i] = '\0';
+    return;
+  }
+
+  if (isdigit(c)) {
+    tok_type = t_int;
+    word[0] = c;
+
+    int i = 1;
+    for (;;) {
+      c = *lexcp++;
+      if (isdigit(c)) {
+        word[i++] = c;
+      } else {
+        word[i] = '\0';
+        lexcp--;
+        break;
+      }
+    }
+    return;
+  }
+
+  if (isalpha(c) || c == '_') {
+    tok_type = t_id;
+    word[0] = c;
+
+    int i = 1;
+    for (;;) {
+      c = *lexcp++;
+      if (isalnum(c) || c == '_') {
+        word[i++] = c;
+      } else {
+        word[i] = '\0';
+        lexcp--;
+        break;
+      }
+    }
+    return;
+  }
+
+  switch(c) {
+    case ',':
+      tok_type = t_comma;
+      break;
+    case '=':
+      tok_type = t_set;
+      break;
+    case '^':
+      tok_type = t_pow;
+      break;
+    case '*':
+      tok_type = t_mul;
+      break;
+    case '/':
+      tok_type = t_div;
+      break;
+    case '+':
+      tok_type = t_add;
+      break;
+    case '-':
+      tok_type = t_sub;
+      break;
+    case '(':
+      tok_type = t_lparen;
+      break;
+    case ')':
+      tok_type = t_rparen;
+      break;
+    default:
+      tok_type = t_unk;
+      break;
+  }
+}
+
+static int lastparseerror;
+static void setparseerror(int i) {
+  lastparseerror = i;
+}
+
+static tree_ptr parsesetexpr(void);
+
+static tree_ptr parseexprlist(tree_ptr t) {
+  tree_ptr c;
+  lex(); // expect lparen
+  if (tok_type == t_rparen) {
+    lex();
+    return t;
+  }
+  c = parsesetexpr();
+  if (!c) return NULL;
+  darray_append(t->child, c);
+  for (;;) {
+    if (tok_type == t_rparen) {
+      lex();
+      return t;
+    }
+    if (tok_type != t_comma) {
+      setparseerror(pe_arglist);
+      return NULL;
+    }
+    lex(); //expect comma
+    c = parsesetexpr();
+    if (!c) return NULL;
+    darray_append(t->child, c);
+  }
+}
+
+static tree_ptr parseprimitive(void) {
+  tree_ptr t;
+  switch(tok_type) {
+    id_ptr id;
+    case t_id:
+      id = id_new(word);
+      lex();
+      if (tok_type == t_lparen) {
+        if (parseexprlist(t = tree_new(t_function, id))) {
+          return t;
+        }
+        tree_delete(t);
+        return NULL;
+      } else {
+        return tree_new(t_id, id);
+      }
+    case t_string:
+      lex();
+      return tree_new(t_string, id_new(word));
+    case t_lparen:
+      lex();
+      t = parsesetexpr();
+      if (!t) return NULL;
+      if (tok_type != t_rparen) {
+        tree_delete(t);
+        setparseerror(pe_expect_rparen);
+        return NULL;
+      }
+      lex();
+      return t;
+    case t_int:
+      id = id_new(word);
+      lex();
+      return tree_new(t_int, id);
+    default:
+      setparseerror(pe_expect_factor);
+      return NULL;
+  }
+}
+
+static tree_ptr parsepow(void) {
+  tree_ptr t1;
+  t1 = parseprimitive();
+  if (tok_type == t_pow) {
+    tree_ptr t2, res;
+    lex();
+    t2 = parseprimitive();
+    if (!t2) {
+      tree_delete(t1);
+      return NULL;
+    }
+    res = tree_new(t_function, id_new("pow"));
+    darray_append(res->child, t1);
+    darray_append(res->child, t2);
+    return res;
+  }
+  return t1;
+}
+
+static tree_ptr parsefactor(void) {
+  tree_ptr t;
+  if (tok_type == t_sub) {
+    lex();
+    t = parsefactor();
+    if (!t) return NULL;
+    tree_ptr t1 = tree_new(t_function, id_new("neg"));
+    darray_append(t1->child, t);
+    return t1;
+  }
+
+  t = parsepow();
+  return t;
+}
+
+static tree_ptr parseterm(void) {
+  tree_ptr t1, t2, res;
+  res = parsefactor();
+  if (!res) return NULL;
+  for (;;) {
+    switch(tok_type) {
+      case t_mul:
+        lex();
+        t2 = parsefactor();
+        if (!t2) {
+          tree_delete(res);
+          return NULL;
+        }
+        t1 = tree_new(t_function, id_new("mul"));
+        darray_append(t1->child, res);
+        darray_append(t1->child, t2);
+        res = t1;
+        break;
+      case t_div:
+        lex();
+        t2 = parsefactor();
+        if (!t2) {
+          tree_delete(res);
+          return NULL;
+        }
+        t1 = tree_new(t_function, id_new("div"));
+        darray_append(t1->child, res);
+        darray_append(t1->child, t2);
+        res = t1;
+        break;
+      default:
+        return res;
+    }
+  }
+}
+
+static tree_ptr parseexpr(void) {
+  tree_ptr t1, t2, res;
+  res = parseterm();
+  if (!res) {
+    return NULL;
+  }
+  for (;;) {
+    switch(tok_type) {
+      case t_add:
+        lex();
+        t2 = parseterm();
+        if (!t2) {
+          tree_delete(res);
+          return NULL;
+        }
+        //t1 = tree_new(t_add, NULL);
+        t1 = tree_new(t_function, id_new("add"));
+        darray_append(t1->child, res);
+        darray_append(t1->child, t2);
+        res = t1;
+        break;
+      case t_sub:
+        lex();
+        t2 = parseterm();
+        if (!t2) {
+          tree_delete(res);
+          return NULL;
+        }
+        //t1 = tree_new(t_sub, NULL);
+        t1 = tree_new(t_function, id_new("sub"));
+        darray_append(t1->child, res);
+        darray_append(t1->child, t2);
+        res = t1;
+        break;
+      default:
+        return res;
+    }
+  }
+}
+
+static tree_ptr parsesetexpr(void) {
+  tree_ptr t1, t2, res;
+  t1 = parseexpr();
+  if (!t1) return NULL;
+  if (tok_type == t_set) {
+    lex();
+    t2 = parsesetexpr();
+    if (!t2) {
+      tree_delete(t1);
+      return NULL;
+    }
+    res = tree_new(t_set, NULL);
+    darray_append(res->child, t1);
+    darray_append(res->child, t2);
+    return res;
+  }
+  return t1;
+}
+
+static void print_tree(tree_ptr t) {
+  id_ptr id;
+  int i;
+  if (!t) {
+    printf("NULL");
+    return;
+  }
+  switch (t->type) {
+    case t_set:
+      print_tree(t->child->item[0]);
+      printf(" = ");
+      print_tree(t->child->item[1]);
+      break;
+    case t_id:
+      id = t->data;
+      printf("%s", id->data);
+      break;
+    case t_function:
+      id = t->data;
+      printf("%s(", id->data);
+      for (i=0; i<t->child->count; i++) {
+        print_tree(t->child->item[i]);
+        if (i < t->child->count - 1) printf(", ");
+      }
+      printf(")");
+      break;
+    default:
+      printf("?!?");
+      break;
+  }
+}
+
+static symtab_t var;
+static symtab_t builtin;
+
+struct val_s {
+  int type;
+  void *data;
+};
+typedef struct val_s *val_ptr;
+
+static int lastruntimeerror;
+static val_ptr newruntimeerror(int i) {
+  val_ptr res = pbc_malloc(sizeof(struct val_s));
+  lastruntimeerror = i;
+  res->type = t_err;
+  res->data = int_to_voidp(i);
+  return res;
+}
+
+val_ptr val_new(int type, void *data) {
+  val_ptr res = pbc_malloc(sizeof(struct val_s));
+  res->type = type;
+  res->data = data;
+  return res;
+}
+
+static void val_print(val_ptr v) {
+  pairing_ptr pairing;
+  field_ptr field;
+  element_ptr e;
+  switch (v->type) {
+    case t_element:
+      e = v->data;
+      element_out_str(stdout, 0, e);
+      printf("\n");
+      break;
+    case t_pairing:
+      pairing = v->data;
+      printf("pairing: G1bits=%d G2bits=%d GTbits=%d\n",
+          pairing_length_in_bytes_x_only_G1(pairing) * 8,
+          pairing_length_in_bytes_x_only_G2(pairing) * 8,
+          pairing_length_in_bytes_GT(pairing) * 8);
+      break;
+    case t_field:
+      field = v->data;
+      field_out_info(stdout, field);
+      break;
+    case t_string:
+      printf("%s", (char *) v->data);
+      break;
+    default:
+      printf("val type %d unknown\n", v->type);
+      break;
+  }
+}
+
+val_ptr val_copy(val_ptr v) {
+  val_ptr res = pbc_malloc(sizeof(struct val_s));
+  res->type = v->type;
+  if (v->type == t_element) {
+    //current policy: always clear elements, always copy elements
+    res->data = pbc_malloc(sizeof(element_t));
+    element_ptr e = v->data;
+    element_init(res->data, e->field);
+    element_set(res->data, e);
+  } else if (v->type == t_string) {
+    res->data = pbc_strdup(v->data);
+  } else {
+    res->data = v->data;
+  }
+
+  return res;
+}
+
+void val_delete(val_ptr v) {
+  switch(v->type) {
+    case t_element:
+      //current policy: always clear elements, always copy elements
+      element_clear(v->data);
+      pbc_free(v->data);
+      break;
+    case t_string:
+      pbc_free(v->data);
+      break;
+    case t_err:
+      break;
+    case t_pairing:
+      break;
+    case t_field:
+      break;
+    default:
+      printf("val_delete: case %d not handled: memory leak\n", v->type);
+      break;
+  }
+  pbc_free(v);
+}
+
+struct fun_s {
+  val_ptr (*f)(darray_ptr);
+  int arity;
+  int type[32]; //TODO: replace with darray? who needs more than 32 args?
+};
+
+typedef val_ptr (*fun)(darray_ptr);
+
+static val_ptr check_arg(darray_ptr arg, int n, ...) {
+  va_list ap;
+  int i;
+  val_ptr res = NULL;
+
+  va_start(ap, n);
+  if (arg->count != n) {
+    printf("expect %d argument(s)\n", n);
+    res = newruntimeerror(re_badargcount);
+  } else for (i=0; i<n; i++) {
+    int t = va_arg(ap, int);
+    val_ptr vp = arg->item[i];
+    if (vp->type != t) {
+      printf("arg not type %d\n", t);
+      return newruntimeerror(re_badarg);
+      break;
+    }
+  }
+
+  va_end(ap);
+  return res;
+}
+
+static val_ptr f_pairing_get_group(
+    field_ptr (*get_group)(pairing_ptr p), darray_ptr arg) {
+  val_ptr res;
+  res = check_arg(arg, 1, t_pairing);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  pairing_ptr pairing = a0->data;
+  res = val_new(t_field, get_group(pairing));
+  return res;
+}
+
+static val_ptr f_pairing_G1(darray_ptr arg) {
+  field_ptr getG1(pairing_ptr p) { return p->G1; }
+  return f_pairing_get_group(getG1, arg);
+}
+
+static val_ptr f_pairing_G2(darray_ptr arg) {
+  field_ptr getG2(pairing_ptr p) { return p->G2; }
+  return f_pairing_get_group(getG2, arg);
+}
+
+static val_ptr f_pairing_GT(darray_ptr arg) {
+  field_ptr getGT(pairing_ptr p) { return p->GT; }
+  return f_pairing_get_group(getGT, arg);
+}
+
+static val_ptr f_pairing_Zr(darray_ptr arg) {
+  field_ptr getZr(pairing_ptr p) { return p->Zr; }
+  return f_pairing_get_group(getZr, arg);
+}
+
+static val_ptr f_random(darray_ptr arg) {
+  val_ptr res;
+  res = check_arg(arg, 1, t_field);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  field_ptr f = a0->data;
+  element_ptr e = pbc_malloc(sizeof(element_t));
+  element_init(e, f);
+  element_random(e);
+  res = val_new(t_element, e);
+  return res;
+}
+
+static val_ptr f_order(darray_ptr arg) {
+  val_ptr res;
+  res = check_arg(arg, 1, t_field);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  field_ptr f = a0->data;
+
+  element_ptr e = pbc_malloc(sizeof(element_t));
+  element_init(e, Z);
+  element_set_mpz(e, f->order);
+  res = val_new(t_element, e);
+  return res;
+}
+
+static val_ptr f_unary(
+    void (*unary)(element_ptr, element_ptr), darray_ptr arg) {
+  val_ptr res;
+  res = check_arg(arg, 1, t_element);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  element_ptr e0 = a0->data;
+  element_ptr e = pbc_malloc(sizeof(element_t));
+  element_init(e, e0->field);
+  unary(e, e0);
+  res = val_new(t_element, e);
+  return res;
+}
+
+static val_ptr f_bin_op(
+    void (*binop)(element_ptr, element_ptr, element_ptr),
+    darray_ptr arg) {
+  val_ptr res;
+  res = check_arg(arg, 2, t_element, t_element);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  val_ptr a1 = arg->item[1];
+  element_ptr e0 = a0->data;
+  element_ptr e1 = a1->data;
+  if (e0->field != e1->field) {
+    printf("field mismatch!\n");
+    return newruntimeerror(re_fieldmismatch);
+  }
+  element_ptr e = pbc_malloc(sizeof(element_t));
+  element_init(e, e0->field);
+  binop(e, e0, e1);
+  res = val_new(t_element, e);
+  return res;
+}
+
+
+static val_ptr f_add(darray_ptr arg) {
+  return f_bin_op(element_add, arg);
+}
+
+static val_ptr f_mul(darray_ptr arg) {
+  return f_bin_op(element_mul, arg);
+}
+
+static val_ptr f_sub(darray_ptr arg) {
+  return f_bin_op(element_sub, arg);
+}
+
+static val_ptr f_div(darray_ptr arg) {
+  return f_bin_op(element_div, arg);
+}
+
+static val_ptr f_inv(darray_ptr arg) {
+  return f_unary(element_invert, arg);
+}
+
+static val_ptr f_neg(darray_ptr arg) {
+  return f_unary(element_neg, arg);
+}
+
+static val_ptr f_pow(darray_ptr arg) {
+  val_ptr res;
+  res = check_arg(arg, 2, t_element, t_element);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  val_ptr a1 = arg->item[1];
+  element_ptr e0 = a0->data;
+  element_ptr e1 = a1->data;
+  element_ptr e = pbc_malloc(sizeof(element_t));
+  mpz_t z;
+  mpz_init(z);
+  element_to_mpz(z, e1);
+  element_init(e, e0->field);
+  element_pow_mpz(e, e0, z);
+  res = val_new(t_element, e);
+  mpz_clear(z);
+  return res;
+}
+
+static pairing_ptr current_pairing;
+static val_ptr f_pairing(darray_ptr arg) {
+  val_ptr res;
+  if (arg->count != 2) {
+    printf("expect two arguments\n");
+    return newruntimeerror(re_badargcount);
+  }
+  val_ptr a0 = arg->item[0];
+  val_ptr a1 = arg->item[1];
+  if (a0->type != t_element) {
+    printf("arg 1 not element!\n");
+    return newruntimeerror(re_badarg);
+  }
+  if (a1->type != t_element) {
+    printf("arg 2 not element!\n");
+    return newruntimeerror(re_badarg);
+  }
+  pairing_ptr p;
+  element_ptr e0 = a0->data;
+  element_ptr e1 = a1->data;
+  p = e0->field->pairing;
+  if (e0->field != p->G1) {
+    printf("arg 1 not from G1!\n");
+    return newruntimeerror(re_badarg);
+  }
+  if (e1->field != p->G2) {
+    printf("arg 2 not from G2!\n");
+    return newruntimeerror(re_badarg);
+  }
+  element_ptr e = pbc_malloc(sizeof(element_t));
+  element_init(e, p->GT);
+  pairing_apply(e, e0, e1, p);
+  res = val_new(t_element, e);
+  return res;
+}
+
+static val_ptr execute_tree(tree_ptr t) {
+  darray_t arg;
+  id_ptr id;
+  fun fn;
+  int i;
+  val_ptr res, v;
+  tree_ptr t1, t2;
+
+  switch (t->type) {
+    case t_id:
+      id = t->data;
+      v = symtab_at(var, id->data);
+      if (!v) {
+        return newruntimeerror(re_varnotfound);
+      }
+      return val_copy(v);
+    case t_set:
+      t1 = t->child->item[0];
+      if (t1->type != t_id) {
+        return newruntimeerror(re_badlvalue);
+      }
+      t2 = t->child->item[1];
+      v = execute_tree(t2);
+      if (v->type == t_err) return v;
+      id = t1->data;
+      // clear what's there first
+      if ((res = symtab_at(var, id->data))) {
+        val_delete(res);
+      }
+      symtab_put(var, v, id->data);
+      v = symtab_at(var, id->data);
+      return val_copy(v);
+    case t_function:
+      id = t->data;
+      fn = symtab_at(builtin, id->data);
+      if (!fn) {
+        return newruntimeerror(re_funnotfound);
+      }
+      darray_init(arg);
+      for (i=0; i<t->child->count; i++) {
+        v = execute_tree(t->child->item[i]);
+        if (v->type == t_err) {
+          darray_forall(arg, (void (*)(void *)) val_delete);
+          return v;
+        }
+        darray_append(arg, v);
+      }
+      res = fn(arg);
+      for (i=0; i<arg->count; i++) {
+        val_delete(arg->item[i]);
+      }
+      darray_clear(arg);
+      return res;
+    case t_int:
+      id = t->data;
+      char *cp;
+      mpz_t z;
+      mpz_init(z);
+      for (cp = id->data; *cp; cp++) {
+        mpz_mul_ui(z, z, 10);
+        mpz_add_ui(z, z, *cp - '0');
+      }
+      element_ptr e = pbc_malloc(sizeof(element_t));
+      element_init(e, Z);
+      element_set_mpz(e, z);
+      mpz_clear(z);
+      return val_new(t_element, e);
+    case t_string:
+      id = t->data;
+      return val_new(t_string, pbc_strdup(id->data));
+    default:
+      return newruntimeerror(re_unimplemented);
+  }
+}
+
+static void parseline(void) {
+  val_ptr v;
+
+  tree_ptr t;
+  lex();
+  if (tok_type == t_none) return;
+  t = parsesetexpr();
+  if (0) {
+    print_tree(t);
+    printf("\n");
+  }
+  if (t) {
+    v = execute_tree(t);
+    if (v) {
+      if (v->type == t_err) {
+        printf("runtime error (error code = %d)\n", lastruntimeerror);
+      } else {
+        if (t->type != t_set) val_print(v);
+      }
+      val_delete(v);
+    }
+    tree_delete(t);
+  } else {
+    printf("parse error (error code = %d)\n", lastparseerror);
+  }
+}
+
+static char *aparam =
+"type a\n"
+"q 8780710799663312522437781984754049815806883199414208211028653399266475630880222957078625179422662221423155858769582317459277713367317481324925129998224791\n"
+"h 12016012264891146079388821366740534204802954401251311822919615131047207289359704531102844802183906537786776\n"
+"r 730750818665451621361119245571504901405976559617\n"
+"exp2 159\n"
+"exp1 107\n"
+"sign1 1\n"
+"sign0 1\n";
+
+static char *dparam =
+"type d\n"
+"q 625852803282871856053922297323874661378036491717\n"
+"n 625852803282871856053923088432465995634661283063\n"
+"h 3\n"
+"r 208617601094290618684641029477488665211553761021\n"
+"a 581595782028432961150765424293919699975513269268\n"
+"b 517921465817243828776542439081147840953753552322\n"
+"k 6\n"
+"nk 60094290356408407130984161127310078516360031868417968262992864809623507269833854678414046779817844853757026858774966331434198257512457993293271849043664655146443229029069463392046837830267994222789160047337432075266619082657640364986415435746294498140589844832666082434658532589211525696\n"
+"hk 1380801711862212484403205699005242141541629761433899149236405232528956996854655261075303661691995273080620762287276051361446528504633283152278831183711301329765591450680250000592437612973269056\n"
+"coeff0 472731500571015189154958232321864199355792223347\n"
+"coeff1 352243926696145937581894994871017455453604730246\n"
+"coeff2 289113341693870057212775990719504267185772707305\n"
+"nqr 431211441436589568382088865288592347194866189652\n";
+
+static char *eparam =
+"type e\n"
+"q 7245986106510086080714203333362098431608853335867425877960916928496629182991629664903654100214900946450053872786629995869445693724001299041657434948257845644905153122838458864000479326695430719258600053239930483226650953770354174712511646273516974069245462534034085895319225452125649979474047163305307830001\n"
+"r 730750862221594424981965739670091261094297337857\n"
+"h 13569343110918781839835249021482970252603216587988030044836106948825516930173270978617489032334001006615524543925753725725046733884363846960470444404747241287743773746682188521738728797153760275116924829183670000\n"
+"a 7130970454025799000067946137594446075551569949583815943390108723282396973737794273397246892274981883807989525599540630855644968426794929215599380425269625872763801485968007136000471718335185787206876242871042697778608875139078711621836858237429403052273312335081163896980825048123655535355411494046493419999\n"
+"b 7169309004853894693616698536183663527570664411678352588247044791687141043489072737232715961588288238022010974661903752526911876859197052490952065266265699130144252031591491045333807587788600764557450846327338626261289568016170532652061787582791926724597362401398804563093625182790987016728290050466098223333\n"
+"exp2 159\n"
+"exp1 135\n"
+"sign1 1\n"
+"sign0 1\n";
+
+static char *fparam =
+"type f\n"
+"q 205523667896953300194896352429254920972540065223\n"
+"r 205523667896953300194895899082072403858390252929\n"
+"b 40218105156867728698573668525883168222119515413\n"
+"beta 115334401956802802075595682801335644058796914268\n"
+"alpha0 191079354656274778837764015557338301375963168470\n"
+"alpha1 71445317903696340296199556072836940741717506375\n";
+
+static char *gparam =
+"type g\n"
+"q 503189899097385532598615948567975432740967203\n"
+"n 503189899097385532598571084778608176410973351\n"
+"h 1\n"
+"r 503189899097385532598571084778608176410973351\n"
+"a 465197998498440909244782433627180757481058321\n"
+"b 463074517126110479409374670871346701448503064\n"
+"k 10\n"
+"nk 1040684643531490707494989587381629956832530311976146077888095795458709511789670022388326295177424065807612879371896982185473788988016190582073591316127396374860265835641044035656044524481121528846249501655527462202999638159773731830375673076317719519977183373353791119388388468745670818193868532404392452816602538968163226713846951514831917487400267590451867746120591750902040267826351982737642689423713163967384383105678367875981348397359466338807\n"
+"hk 4110127713690841149713310614420858884651261781185442551927080083178682965171097172366598236129731931693425629387502221804555636704708008882811353539555915064049685663790355716130262332064327767695339422323460458479884756000782939428852120522712008037615051139080628734566850259704397643028017435446110322024094259858170303605703280329322675124728639532674407\n"
+"coeff0 67343110967802947677845897216565803152319250\n"
+"coeff1 115936772834120270862756636148166314916823221\n"
+"coeff2 87387877425076080433559927080662339215696505\n"
+"coeff3 433223145899090928132052677121692683015058909\n"
+"coeff4 405367866213598664862417230702935310328613596\n"
+"nqr 22204504160560785687198080413579021865783099\n";
+
+static pairing_t pairing_A, pairing_D, pairing_E, pairing_F, pairing_G;
+
+static void set_pairing_groups(pairing_ptr p) {
+  symtab_put(var, val_new(t_field, p->G1), "G1");
+  symtab_put(var, val_new(t_field, p->G2), "G2");
+  symtab_put(var, val_new(t_field, p->GT), "GT");
+  symtab_put(var, val_new(t_field, p->Zr), "Zr");
+  symtab_put(var, val_new(t_pairing, p), "current_pairing");
+  current_pairing = p;
+}
+
+static val_ptr f_init_pairing(darray_ptr arg) {
+  val_ptr res;
+
+  res = check_arg(arg, 1, t_pairing);
+  if (res) return res;
+
+  val_ptr a0 = arg->item[0];
+  pairing_ptr p = a0->data;
+  set_pairing_groups(p);
+  return NULL;
+}
+
+static val_ptr f_nextprime(darray_ptr arg) {
+  mpz_t p;
+  val_ptr res;
+
+  res = check_arg(arg, 1, t_element);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  element_ptr e0 = a0->data;
+  if (e0->field != Z) {
+    printf("arg not integer!\n");
+    return newruntimeerror(re_badarg);
+  }
+  element_ptr e = pbc_malloc(sizeof(element_t));
+  element_init(e, Z);
+  mpz_init(p);
+  element_to_mpz(p, e0);
+  mpz_nextprime(p, p);
+  element_set_mpz(e, p);
+  res = val_new(t_element, e);
+  mpz_clear(p);
+  return res;
+}
+
+static val_ptr f_brute_force_dlog(darray_ptr arg) {
+  val_ptr res;
+  res = check_arg(arg, 2, t_element, t_element);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  val_ptr a1 = arg->item[1];
+  element_ptr e0 = a0->data;
+  element_ptr e1 = a1->data;
+  if (e0->field != e1->field) {
+    printf("arg field mismatch!\n");
+    return newruntimeerror(re_badarg);
+  }
+  element_ptr e = pbc_malloc(sizeof(element_t));
+  element_init(e, Z);
+  element_dlog_brute_force(e, e0, e1);
+  res = val_new(t_element, e);
+  return res;
+}
+static val_ptr f_pollard_rho(darray_ptr arg) {
+  val_ptr res;
+  res = check_arg(arg, 3, t_element, t_element, t_field);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  val_ptr a1 = arg->item[1];
+  val_ptr a2 = arg->item[2];
+  element_ptr e0 = a0->data;
+  element_ptr e1 = a1->data;
+  if (e0->field != e1->field) {
+    printf("arg field mismatch!\n");
+    return newruntimeerror(re_badarg);
+  }
+  field_ptr f = a2->data;
+  element_ptr e = pbc_malloc(sizeof(element_t));
+  element_init(e, f);
+  element_dlog_pollard_rho(e, e0, e1);
+  res = val_new(t_element, e);
+  return res;
+}
+
+static val_ptr f_zz(darray_ptr arg) {
+  mpz_t p;
+  val_ptr res;
+  res = check_arg(arg, 1, t_element);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  element_ptr e0 = a0->data;
+  if (e0->field != Z) {
+    printf("arg not integer!\n");
+    return newruntimeerror(re_badarg);
+  }
+  field_ptr f = pbc_malloc(sizeof(field_t));
+  mpz_init(p);
+  element_to_mpz(p, e0);
+  field_init_fp(f, p);
+  res = val_new(t_field, f);
+  mpz_clear(p);
+  return res;
+}
+
+static val_ptr f_gen_A(darray_ptr arg) {
+  mpz_t rbits, qbits;
+  pairing_ptr p;
+  val_ptr res;
+  res = check_arg(arg, 2, t_element, t_element);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  val_ptr a1 = arg->item[1];
+  element_ptr e0 = a0->data;
+  if (e0->field != Z) {
+    printf("arg not integer!\n");
+    return newruntimeerror(re_badarg);
+  }
+  element_ptr e1 = a1->data;
+  if (e1->field != Z) {
+    printf("arg not integer!\n");
+    return newruntimeerror(re_badarg);
+  }
+  mpz_init(rbits);
+  mpz_init(qbits);
+  element_to_mpz(rbits, e0);
+  element_to_mpz(qbits, e1);
+  //TODO: check rbits and qbits aren't too big
+  pbc_param_t param;
+  pbc_param_init_a_gen(param, mpz_get_ui(rbits), mpz_get_ui(qbits));
+  p = pbc_malloc(sizeof(pairing_t));
+  pairing_init_pbc_param(p, param);
+  res = val_new(t_pairing, p);
+  mpz_clear(rbits);
+  mpz_clear(qbits);
+  pbc_param_clear(param);
+  return res;
+}
+
+static val_ptr f_fromZZ(darray_ptr arg) {
+  val_ptr res;
+  res = check_arg(arg, 2, t_element, t_field);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  val_ptr a1 = arg->item[1];
+  element_ptr e = a0->data;
+  field_ptr f = a1->data;
+  if (e->field != Z) {
+    printf("arg not integer!\n");
+    return newruntimeerror(re_badarg);
+  }
+  element_ptr e1 = pbc_malloc(sizeof(element_t));
+  element_init(e1, f);
+  element_set_mpz(e1, e->data);
+  res = val_new(t_element, e1);
+  return res;
+}
+
+static val_ptr f_fromstr(darray_ptr arg) {
+  val_ptr res;
+  res = check_arg(arg, 2, t_string, t_field);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  val_ptr a1 = arg->item[1];
+  field_ptr f = a1->data;
+  element_ptr e1 = pbc_malloc(sizeof(element_t));
+  element_init(e1, f);
+  element_set_str(e1, a0->data, 0);
+  res = val_new(t_element, e1);
+  return res;
+}
+
+/* I'll probably never finish this :(
+static val_ptr f_index_calculus(darray_ptr arg) {
+  val_ptr res;
+  res = check_arg(arg, 2, t_element, t_element);
+  if (res) return res;
+  val_ptr a0 = arg->item[0];
+  val_ptr a1 = arg->item[1];
+  element_ptr e0 = a0->data;
+  element_ptr e1 = a1->data;
+  element_ptr e = pbc_malloc(sizeof(element_t));
+  mpz_t x, g, h, q1;
+
+  //TODO: check e0, e1 are from an integer mod ring
+  mpz_init(x);
+  mpz_init(g);
+  mpz_init(h);
+  mpz_init(q1);
+
+  mpz_sub_ui(q1, e0->field->order, 1);
+
+  element_init(e, Z);
+  element_to_mpz(g, e0);
+  element_to_mpz(h, e1);
+  pbc_mpz_index_calculus(x, g, h, q1);
+  element_set_mpz(e, x);
+  res = val_new(t_element, e);
+  mpz_clear(x);
+  mpz_clear(g);
+  mpz_clear(h);
+  mpz_clear(q1);
+  return res;
+}
+*/
+
+int main(int argc, char **argv) {
+  for (;;) {
+    int c = getopt(argc, argv, "e");
+    if (c == -1) break;
+    switch (c) {
+      case 'e':
+        option_echo = 1;
+        break;
+      default:
+        fprintf(stderr, "unrecognized option: %c\n", c);
+        break;
+    }
+  }
+
+  symtab_init(var);
+  symtab_init(builtin);
+
+  pairing_init_set_str(pairing_A, aparam);
+  pairing_init_set_str(pairing_D, dparam);
+  pairing_init_set_str(pairing_E, eparam);
+  pairing_init_set_str(pairing_F, fparam);
+  pairing_init_set_str(pairing_G, gparam);
+  symtab_put(var, val_new(t_pairing, pairing_A), "A");
+  symtab_put(var, val_new(t_pairing, pairing_D), "D");
+  symtab_put(var, val_new(t_pairing, pairing_E), "E");
+  symtab_put(var, val_new(t_pairing, pairing_F), "F");
+  symtab_put(var, val_new(t_pairing, pairing_G), "G");
+
+  set_pairing_groups(pairing_A);
+
+  symtab_put(builtin, f_init_pairing, "init_pairing");
+  symtab_put(builtin, f_pairing_G1, "get_G1");
+  symtab_put(builtin, f_pairing_G2, "get_G2");
+  symtab_put(builtin, f_pairing_GT, "get_GT");
+  symtab_put(builtin, f_pairing_Zr, "get_Zr");
+  symtab_put(builtin, f_random, "random");
+  symtab_put(builtin, f_random, "rand");
+  symtab_put(builtin, f_random, "rnd");
+  symtab_put(builtin, f_order, "order");
+  symtab_put(builtin, f_order, "ord");
+  symtab_put(builtin, f_neg, "neg");
+  symtab_put(builtin, f_sub, "sub");
+  symtab_put(builtin, f_add, "add");
+  symtab_put(builtin, f_pow, "pow");
+  symtab_put(builtin, f_mul, "mul");
+  symtab_put(builtin, f_inv, "inv");
+  symtab_put(builtin, f_inv, "invert");
+  symtab_put(builtin, f_div, "div");
+  symtab_put(builtin, f_pairing, "pairing");
+  symtab_put(builtin, f_nextprime, "nextprime");
+  symtab_put(builtin, f_brute_force_dlog, "element_dlog_brute_force");
+  symtab_put(builtin, f_pollard_rho, "element_dlog_pollard_rho");
+  //symtab_put(builtin, f_index_calculus, "index_calculus");
+  symtab_put(builtin, f_zz, "ZZ");
+  symtab_put(builtin, f_gen_A, "gen_A");
+  symtab_put(builtin, f_fromZZ, "fromZZ");
+  symtab_put(builtin, f_fromstr, "fromstr");
+
+  field_init_z(Z);
+
+  fprintf(stderr, "pbc\n");
+
+  for (;;) {
+    currentline = pbc_getline(NULL);
+    if (!currentline) break;
+    if (option_echo) puts(currentline);
+    lexcp = currentline;
+    parseline();
+    free(currentline);
+  }
+  return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/pbc/pairing_test.pbc b/moon-abe/pbc-0.5.14/pbc/pairing_test.pbc
new file mode 100644
index 00000000..c57189f7
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/pbc/pairing_test.pbc
@@ -0,0 +1,21 @@
+# Tests sample type A pairing.
+
+g := G1([2382389466570123849673299401984867521337122094157231907755149435707124249269394670242462497382963719723036281844079382411446883273020125104982896098602669, 2152768906589770702756591740710760107878949212304343787392475836859241438597588807103470081101790991563152395601123682809718038151417122294066319979967168]);
+
+h := G2([5832612417453786541700129157230442590988122495898645678468800815872828277169950107203266157735206975228912899931278160262081308603240860553459187732968543, 5825590786822892934138376868455818413990615826926356662470129700411774690868351658310187202553513693344017463065909279569624651155563430675084173630054336]);
+
+a := 171583727262251826931173602797951212789946235851;
+b := 233634857565210859330459959563397971304462340857;
+
+CHECK(pairing(g, h) == GT([1352478452661998164151215014828915385601138645645403926287105573769451214277485326392786454433874957123922454604362337349978217917242114505658729401276644, 2809858014072341042857607405424304552357466023841122154308055820747972163307396014445308786731013691659356362568425895483877936945589613445697089590886519]));
+
+CHECK(g^a == G1([3727290142167731134589933003026410141163353118002821914170365887139605219852868537686435214464927363733592858325260588072422405672197113236445369761687270, 8313413520789037477320458888316489483781506373846006723006557775349684878102042826049292521482530556981023752851151672326421296204733037418468523296005577]));
+
+CHECK(h^b == G2([302169045606583472168811217560382970305157511680176350745436990853463473855962841196184541109617397027480204774682450915021848512168573082843355648090809, 7428193877404140917518137438384425427600294220905786853638038223349096573857683866658575603565175187399696035468569929483731011292133989973187846752806084]));
+
+res := GT([5401677742232403160612802517983583823254857216272776607059355607024091426935935872461700304196658606704085604766577186374528948004140797833341187234647180, 4255900207739859478558185000995524505026245539159946661271849714832846423204570340979120001638894488614502770175520505048836617405342161594891740961421000]);
+
+CHECK(res == pairing(g^a, h^b));
+CHECK(res == pairing(g, h)^(Zr(a)*Zr(b)));
+CHECK(res == pairing(g^a, h)^b);
+CHECK(res == pairing(g, h^b)^a);
diff --git a/moon-abe/pbc-0.5.14/pbc/parser.lex b/moon-abe/pbc-0.5.14/pbc/parser.lex
new file mode 100644
index 00000000..1d0b9f23
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/pbc/parser.lex
@@ -0,0 +1,56 @@
+%{
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdint.h> // for intptr_t
+#include <gmp.h>
+#include "pbc_utils.h"
+#include "pbc_field.h"
+
+#include "pbc_tree.h"
+#define YYSTYPE tree_ptr
+#include "parser.tab.h"
+
+extern int option_easy;
+
+%}
+
+%option nounput noinput
+
+%x COMMENT
+%%
+\/\*                    BEGIN(COMMENT);  // Open C-style comment.
+<COMMENT>\*\/           BEGIN(0);        // Close C-style comment.
+<COMMENT>.              // Within a C-style comment.
+<COMMENT>\n             // Within a C-style comment.
+#.*$                    // Comment.
+[ \t\r]*                // Whitespace.
+
+define                  return DEFINE;
+[0-9]+                  yylval = tree_new_z(yytext);  return NUM;
+[a-zA-Z_][a-zA-Z0-9_]*  yylval = tree_new_id(yytext); return ID;
+:=                      return ASSIGN;
+==                      return EQ;
+!=                      return NE;
+\<                      return LT;
+\>                      return T_GT;
+\<=                     return LE;
+\>=                     return GE;
+\+                      return PLUS;
+-                       return MINUS;
+\/                      return DIVIDE;
+\*                      return TIMES;
+\^                      return POW;
+;                       return TERMINATOR;
+\,                      return COMMA;
+\?                      return QUESTION;
+:                       return COLON;
+\(                      return LPAR;
+\)                      return RPAR;
+\[                      return LSQU;
+\]                      return RSQU;
+\{                      return LBRACE;
+\}                      return RBRACE;
+\n                      if (option_easy) return TERMINATOR;
+=                       return option_easy ? ASSIGN : UNKNOWN;
+.                       return UNKNOWN;
+%%
diff --git a/moon-abe/pbc-0.5.14/pbc/parser.y b/moon-abe/pbc-0.5.14/pbc/parser.y
new file mode 100644
index 00000000..d51cebcc
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/pbc/parser.y
@@ -0,0 +1,112 @@
+%{
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdint.h> // for intptr_t
+#include <gmp.h>
+#include "pbc_utils.h"
+#include "pbc_field.h"
+
+#include "pbc_tree.h"
+#define YYSTYPE tree_ptr
+void yyerror(const char *s);
+int yylex(void);
+
+#define YY_NO_INPUT
+#define YY_NO_UNPUT
+
+extern int option_easy;
+%}
+
+%error-verbose
+%token DEFINE
+%token TERMINATOR
+%token NUM ID
+%token LPAR RPAR LSQU RSQU LBRACE RBRACE COMMA
+%right QUESTION COLON
+%left EQ NE LT T_GT LE GE
+%right ASSIGN
+%left PLUS MINUS
+%left DIVIDE TIMES
+%right UMINUS
+%right POW
+%token UNKNOWN
+%token END 0 "end of file"
+%%
+input
+  : // Empty.
+  | input stmt { tree_eval_stmt($2); }
+  ;
+
+stmt
+  : expr TERMINATOR
+  | DEFINE ID LPAR parms RPAR LBRACE stmtlist RBRACE {
+      $$ = tree_new_define($2, $4, $7);
+    }
+  ;
+
+stmtlist
+  : { $$ = tree_new_empty_stmt_list(); }  // Empty.
+  | stmtlist stmt { tree_append($1, $2); }
+  ;
+
+parms
+  : { $$ = tree_new_empty_parms(); }  // Empty.
+  | parms1
+  ;
+
+parms1
+  : ID { $$ = tree_new_empty_parms(); tree_append($$, $1); }
+  | parms1 COMMA ID { tree_append($1, $3); }
+  ;
+
+expr
+  : multinomial
+  | ID ASSIGN expr   { $$ = tree_new_assign($1, $3); }
+  | expr QUESTION expr COLON expr  { $$ = tree_new_ternary($1, $3, $5); }
+  | molecule
+  | molecule LSQU expr RSQU  { $$ = tree_new_item($1, $3); }
+  | expr EQ expr     { $$ = tree_new_eq($1, $3); }
+  | expr NE expr     { $$ = tree_new_ne($1, $3); }
+  | expr LE expr     { $$ = tree_new_le($1, $3); }
+  | expr GE expr     { $$ = tree_new_ge($1, $3); }
+  | expr LT expr     { $$ = tree_new_lt($1, $3); }
+  | expr T_GT expr   { $$ = tree_new_gt($1, $3); }
+  | expr PLUS expr   { $$ = tree_new_add($1, $3); }
+  | expr MINUS expr  { $$ = tree_new_sub($1, $3); }
+  | expr TIMES expr  { $$ = tree_new_mul($1, $3); }
+  | expr DIVIDE expr { $$ = tree_new_div($1, $3); }
+  | expr POW expr    { $$ = tree_new_pow($1, $3); }
+  | MINUS expr %prec UMINUS  { $$ = tree_new_neg($2); }
+  ;
+
+// Not quite atoms.
+molecule
+  : molecule LPAR exprlist RPAR  { $$ = $3; tree_set_fun($$, $1); }
+  | LPAR expr RPAR               { $$ = $2; }
+  | ID
+  ;
+
+exprlist
+  : { $$ = tree_new_funcall(); }  // Empty.
+  | nonemptyexprlist
+  ;
+
+nonemptyexprlist
+  : expr   { tree_append($$ = tree_new_funcall(), $1); }
+  | nonemptyexprlist COMMA expr { tree_append($1, $3); }
+  ;
+
+multinomial
+  : NUM
+  | numlist
+  ;
+
+numlist
+  : LSQU sequence RSQU { $$ = $2; }
+  ;
+
+sequence
+  : expr { $$ = tree_new_list($1); }
+  | sequence COMMA expr { tree_append($1, $3); }
+  ;
+%%
diff --git a/moon-abe/pbc-0.5.14/pbc/pbc.c b/moon-abe/pbc-0.5.14/pbc/pbc.c
new file mode 100644
index 00000000..6fb76046
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/pbc/pbc.c
@@ -0,0 +1,953 @@
+// Pairing-Based Calculator.
+
+// TODO: Garbage collection.
+// TODO: Recursion (stack frames), anonymous functions.
+
+#include <unistd.h>  // For getopt.
+
+#include "pbc.h"
+#include "pbc_fp.h"
+#include "pbc_z.h"
+#include "pbc_multiz.h"
+#include "pbc_poly.h"
+
+#include "misc/darray.h"
+#include "misc/symtab.h"
+
+#include "pbc_tree.h"
+
+#include "lex.yy.h"
+#include "parser.tab.h"
+
+int option_easy = 0;
+const char *option_prompt;
+
+char *pbc_getline(const char *prompt);
+
+void yyerror(char *s) { fprintf(stderr, "%s\n", s); }
+int yyparse(void);
+
+// Symbol table holding built-in functions and variables.
+static symtab_t reserved;
+// Symbol table holding user-defined variable and function names.
+static symtab_t tab;
+
+static field_t M;
+static field_t Z;
+static pairing_t pairing;
+
+struct val_s;
+typedef struct val_s *val_ptr;
+
+struct fun_s;
+typedef struct fun_s *fun_ptr;
+
+// Syntax tree node.
+struct tree_s {
+  // Evaluates this node.
+  val_ptr (*eval)(tree_ptr);
+  union {
+    const char *id;
+    element_ptr elem;
+    // Built-in function.
+    fun_ptr fun;
+    // Child nodes.
+    darray_ptr child;
+  };
+};
+
+enum {
+  ARITY_VARIABLE = -1,
+};
+
+// The interface of a val_ptr shared amongst many val_ptr objects.
+// Analog of C++ class.
+struct val_type_s {
+  // One of element, field, function, error.
+  char *name;
+  // Print out current value.
+  void (*out_str)(FILE *, val_ptr);
+  // Called when a variable is evaluated, e.g. "foo;".
+  val_ptr (*eval)(val_ptr);
+  // Called when a variable is used as a function, e.g. "foo();".
+  val_ptr (*funcall)(val_ptr, tree_ptr);
+};
+
+// Functions plus type checking data.
+struct fun_s {
+  const char *name;
+  val_ptr (*run)(val_ptr[]);
+  int arity;
+  const struct val_type_s **sig;
+};
+typedef struct fun_s fun_t[1];
+
+// When interpreting, each node of the syntax tree recursively evaluates
+// its children then returns a val_ptr.
+struct val_s {
+  struct val_type_s *type;
+  union {
+    element_ptr elem;
+    // User-defined function.
+    tree_ptr def;
+    // Built-in function.
+    fun_ptr fun;
+    field_ptr field;
+    const char *msg;
+  };
+};
+
+static val_ptr val_new_element(element_ptr e);
+static val_ptr val_new_field(field_ptr e);
+static val_ptr val_new_error(const char *msg, ...);
+
+// Evaluates syntax tree node.
+static val_ptr tree_eval(tree_ptr t) {
+  return t->eval(t);
+}
+
+static void v_elem_out(FILE* stream, val_ptr v) {
+  element_out_str(stream, 0, v->elem);
+}
+
+static val_ptr v_elem_eval(val_ptr v) {
+  element_ptr e = pbc_malloc(sizeof(*e));
+  element_init_same_as(e, v->elem);
+  element_set(e, v->elem);
+  return val_new_element(e);
+}
+
+static void v_builtin_out(FILE* stream, val_ptr v) {
+  // TODO: Print types of arguments.
+  fprintf(stream, "built-in function %s, arity %d",
+      v->fun->name, v->fun->arity);
+}
+
+static void v_define_out(FILE* stream, val_ptr v) {
+  fprintf(stream, "user-defined function %s",
+      ((tree_ptr) darray_at(v->def->child, 0))->id);
+}
+
+static val_ptr v_builtin(val_ptr v, tree_ptr t) {
+  fun_ptr fun = v->fun;
+  int n = fun->arity;
+  if (1 + n != darray_count(t->child)) {
+    return val_new_error("%s: wrong number of arguments", fun->name);
+  }
+  val_ptr arg[n];
+  int i;
+  for(i = 0; i < n; i++) {
+    arg[i] = tree_eval(darray_at(t->child, i));
+    if (fun->sig[i] && arg[i]->type != fun->sig[i]) {
+      return val_new_error("%s: argument %d type mismatch", fun->name, i + 1);
+    }
+  }
+  return fun->run(arg);
+}
+
+static void eval_stmt(void *ptr) {
+  tree_eval(ptr);
+}
+
+static val_ptr v_def_call(val_ptr v, tree_ptr t) {
+  int i;
+  const char* name = ((tree_ptr) darray_at(v->def->child, 0))->id;
+  darray_ptr parm = ((tree_ptr) darray_at(v->def->child, 1))->child;
+  int n = darray_count(parm);
+  if (1 + n != darray_count(t->child)) {
+    return val_new_error("%s: wrong number of arguments", name);
+  }
+  for(i = 0; i < n; i++) {
+    const char *id = ((tree_ptr) darray_at(parm, i))->id;
+    val_ptr v1 = tree_eval(darray_at(t->child, i));
+    // TODO: Stack frames for recursion.
+    symtab_put(tab, v1, id);
+  }
+  // Evaluate function body.
+  darray_ptr a = ((tree_ptr) darray_at(v->def->child, 2))->child;
+  darray_forall(a, eval_stmt);
+  return NULL;
+}
+
+static val_ptr v_field_cast(val_ptr v, tree_ptr t) {
+  // TODO: Check args, x is an element.
+  val_ptr x = tree_eval(darray_at(t->child, 0));
+  element_ptr e = x->elem;
+  if (e->field == M) {
+    if (v->field == M) return x;
+    element_ptr e2 = element_new(v->field);
+    if (element_is0(e)) // if 'set0' is not 'set1' in base field of GT, but we hope 'GT(0)' calls 'set1', we may directly call 'element_set0' here
+      element_set0(e2);
+    else if (element_is1(e)) // reason is same as above
+      element_set1(e2);
+    else
+      element_set_multiz(e2, e->data);
+    x->elem = e2;
+    return x;
+  }
+  if (v->field == M) {
+    // Map to/from integer. TODO: Map to/from multiz instead.
+    mpz_t z;
+    mpz_init(z);
+    element_to_mpz(z, e);
+    element_clear(e);
+    element_init(e, v->field);
+    element_set_mpz(e, z);
+    mpz_clear(z);
+  }
+  return x;
+}
+
+static void v_field_out(FILE* stream, val_ptr v) {
+  field_out_info(stream, v->field);
+}
+
+static val_ptr v_self(val_ptr v) {
+  return v;
+}
+
+static void v_err_out(FILE* stream, val_ptr v) {
+  fprintf(stream, "%s", v->msg);
+}
+
+static val_ptr v_errcall(val_ptr v, tree_ptr t) {
+  UNUSED_VAR(t);
+  return v;
+}
+
+static struct val_type_s
+  // TODO: Replace NULL with get_coeff.
+  v_elem[1]  = {{  "element",    v_elem_out, v_elem_eval, NULL }},
+  v_field[1] = {{    "field",   v_field_out,      v_self, v_field_cast }},
+  v_fun[1]   = {{  "builtin", v_builtin_out,      v_self, v_builtin }},
+  v_def[1]   = {{ "function",  v_define_out,      v_self, v_def_call }},
+  v_error[1] = {{    "error",     v_err_out,      v_self, v_errcall }};
+
+// Function signature constants for type checking.
+const struct val_type_s *sig_field[] = { v_field };
+const struct val_type_s *sig_elem[] = { v_elem };
+const struct val_type_s *sig_any[] = { NULL };
+const struct val_type_s *sig_elem_elem[] = { v_elem, v_elem };
+const struct val_type_s *sig_field_elem[] = { v_field, v_elem };
+
+static val_ptr val_new_element(element_ptr e) {
+  val_ptr v = pbc_malloc(sizeof(*v));
+  v->type = v_elem;
+  v->elem = e;
+  return v;
+}
+
+static val_ptr val_new_field(field_ptr f) {
+  val_ptr v = pbc_malloc(sizeof(*v));
+  v->type = v_field;
+  v->field = f;
+  return v;
+}
+
+static val_ptr val_new_error(const char *msg, ...) {
+  va_list params;
+  char buf[80];
+
+  va_start(params, msg);
+  vsnprintf(buf, 80, msg, params);
+  va_end(params);
+
+  val_ptr v = pbc_malloc(sizeof(*v));
+  v->type = v_error;
+  v->msg = pbc_strdup(buf);
+  return v;
+}
+
+static val_ptr val_new_fun(fun_ptr fun) {
+  val_ptr v = pbc_malloc(sizeof(*v));
+  v->type = v_fun;
+  v->fun = fun;
+  return v;
+}
+
+static val_ptr fun_bin(
+    void (*binop)(element_ptr, element_ptr, element_ptr),
+    val_ptr v[]) {
+  binop(v[0]->elem, v[0]->elem, v[1]->elem);
+  return v[0];
+}
+
+static val_ptr run_add(val_ptr v[]) { return fun_bin(element_add, v); }
+static val_ptr run_sub(val_ptr v[]) { return fun_bin(element_sub, v); }
+static val_ptr run_mul(val_ptr v[]) { return fun_bin(element_mul, v); }
+static val_ptr run_div(val_ptr v[]) { return fun_bin(element_div, v); }
+static val_ptr run_pow(val_ptr v[]) { return fun_bin(element_pow_zn, v); }
+
+static fun_t fun_add = {{ "add", run_add, 2, sig_elem_elem }};
+static fun_t fun_sub = {{ "sub", run_sub, 2, sig_elem_elem }};
+static fun_t fun_mul = {{ "mul", run_mul, 2, sig_elem_elem }};
+static fun_t fun_div = {{ "div", run_div, 2, sig_elem_elem }};
+static fun_t fun_pow = {{ "pow", run_pow, 2, sig_elem_elem }};
+
+static val_ptr fun_cmp(val_ptr v[], int (*fun)(int)) {
+  int i = element_cmp(v[0]->elem, v[1]->elem);
+  element_ptr e = pbc_malloc(sizeof(*e));
+  element_init(e, M);
+  element_set_si(e, fun(i));
+  v[0]->elem = e;
+  return v[0];
+}
+
+static int is0(int i) {
+  return i == 0;
+}
+
+static int isnot0(int i) {
+  return i != 0;
+}
+
+static int isle(int i) {
+  return i <= 0;
+}
+
+static int isge(int i) {
+  return i >= 0;
+}
+
+static int islt(int i) {
+  return i < 0;
+}
+
+static int isgt(int i) {
+  return i > 0;
+}
+
+static val_ptr run_eq(val_ptr v[]) {
+  return fun_cmp(v, is0);
+}
+
+static val_ptr run_ne(val_ptr v[]) {
+  return fun_cmp(v, isnot0);
+}
+
+static val_ptr run_le(val_ptr v[]) {
+  return fun_cmp(v, isle);
+}
+
+static val_ptr run_ge(val_ptr v[]) {
+  return fun_cmp(v, isge);
+}
+static val_ptr run_lt(val_ptr v[]) {
+  return fun_cmp(v, islt);
+}
+static val_ptr run_gt(val_ptr v[]) {
+  return fun_cmp(v, isgt);
+}
+
+static fun_t fun_eq = {{ "==", run_eq, 2, sig_elem_elem }};
+static fun_t fun_ne = {{ "!=", run_ne, 2, sig_elem_elem }};
+static fun_t fun_le = {{ "<=", run_le, 2, sig_elem_elem }};
+static fun_t fun_ge = {{ ">=", run_ge, 2, sig_elem_elem }};
+static fun_t fun_lt = {{ "<", run_lt, 2, sig_elem_elem }};
+static fun_t fun_gt = {{ ">", run_gt, 2, sig_elem_elem }};
+
+static val_ptr eval_elem(tree_ptr t) {
+  // TODO: Write element_clone(), or at least element_new().
+  element_ptr e = pbc_malloc(sizeof(*e));
+  element_init_same_as(e, t->elem);
+  element_set(e, t->elem);
+  return val_new_element(e);
+}
+
+static val_ptr eval_list(tree_ptr t) {
+  element_ptr e = NULL;
+  int n = darray_count(t->child);
+  int i;
+  for(i = 0; i < n; i++) {
+    val_ptr x = tree_eval(darray_at(t->child, i));
+    // TODO: Also check x is a multiz.
+    if (v_error == x->type) {
+      return x;
+    }
+    if (v_elem != x->type) {
+      return val_new_error("element expected in list");
+    }
+    if (!i) e = multiz_new_list(x->elem);
+    else multiz_append(e, x->elem);
+  }
+  return val_new_element(e);
+}
+
+static val_ptr eval_ternary(tree_ptr t) {
+  val_ptr x = tree_eval(darray_at(t->child, 0));
+  if (v_error == x->type) {
+    return x;
+  }
+  if (x->type != v_elem) {
+    return val_new_error("element expected in ternary operator");
+  }
+  if (!element_is0(x->elem)) {
+    return tree_eval(darray_at(t->child, 1));
+  }
+  return tree_eval(darray_at(t->child, 2));
+}
+
+static val_ptr eval_id(tree_ptr t) {
+  val_ptr x = symtab_at(reserved, t->id);
+  if (!x) x = symtab_at(tab, t->id);
+  if (!x) {
+    return val_new_error("undefined variable %s", t->id);
+  }
+  return x->type->eval(x);
+}
+
+static val_ptr eval_funcall(tree_ptr t) {
+  val_ptr x = tree_eval(darray_last(t->child));
+  return x->type->funcall(x, t);
+}
+
+static val_ptr eval_fun(tree_ptr t) {
+  return val_new_fun(t->fun);
+}
+
+static val_ptr run_neg(val_ptr v[]) {
+  element_neg(v[0]->elem, v[0]->elem);
+  return v[0];
+}
+static fun_t fun_neg = {{ "neg", run_neg, 1, sig_elem }};
+
+static val_ptr eval_assign(tree_ptr t) {
+  tree_ptr tid = darray_at(t->child, 0);
+  val_ptr v = tree_eval(darray_at(t->child, 1));
+  if (symtab_at(reserved, tid->id)) {
+    return val_new_error("%s is reserved", tid->id);
+  }
+  symtab_put(tab, v, tid->id);
+  return v;
+}
+
+static void assign_field(field_ptr f, const char* s) {
+  symtab_put(tab, val_new_field(f), s);
+}
+
+tree_ptr tree_new(val_ptr (*eval)(tree_ptr)) {
+  tree_ptr res = pbc_malloc(sizeof(*res));
+  res->eval = eval;
+  return res;
+}
+
+tree_ptr tree_new_z(const char* s) {
+  element_ptr e = pbc_malloc(sizeof(*e));
+  element_init(e, M);
+  element_set_str(e, s, 0);
+  tree_ptr t = tree_new(eval_elem);
+  t->elem = e;
+  return t;
+}
+
+static val_ptr eval_err(tree_ptr t) {
+  UNUSED_VAR(t);
+  pbc_die("BUG: shouldn't reach here!");
+}
+
+tree_ptr tree_new_empty_stmt_list() {
+  tree_ptr t = tree_new(eval_err);
+  t->child = darray_new();
+  return t;
+}
+
+tree_ptr tree_new_empty_parms() {
+  tree_ptr t = tree_new(eval_err);
+  t->child = darray_new();
+  return t;
+}
+
+static val_ptr eval_define(tree_ptr t) {
+  val_ptr v = pbc_malloc(sizeof(*v));
+  v->type = v_def;
+  v->def = t;
+  symtab_put(tab, v, ((tree_ptr) darray_at(t->child, 0))->id);
+  return v;
+}
+
+tree_ptr tree_new_define(tree_ptr id, tree_ptr parm, tree_ptr body) {
+  tree_ptr t = tree_new(eval_define);
+  t->child = darray_new();
+  darray_append(t->child, id);
+  darray_append(t->child, parm);
+  darray_append(t->child, body);
+  return t;
+}
+
+tree_ptr tree_new_list(tree_ptr first) {
+  tree_ptr t = tree_new(eval_list);
+  t->child = darray_new();
+  darray_append(t->child, first);
+  return t;
+}
+
+tree_ptr tree_new_ternary(tree_ptr cond, tree_ptr t1, tree_ptr t2) {
+  tree_ptr t = tree_new(eval_ternary);
+  t->child = darray_new();
+  darray_append(t->child, cond);
+  darray_append(t->child, t1);
+  darray_append(t->child, t2);
+  return t;
+}
+
+tree_ptr tree_new_id(const char* s) {
+  tree_ptr t = tree_new(eval_id);
+  t->id = pbc_strdup(s);
+  return t;
+}
+
+tree_ptr tree_new_funcall(void) {
+  tree_ptr t = tree_new(eval_funcall);
+  t->child = darray_new();
+  return t;
+}
+
+static tree_ptr tree_new_fun(fun_ptr fun) {
+  tree_ptr t = tree_new(eval_fun);
+  t->fun = fun;
+  return t;
+}
+
+void tree_set_fun(tree_ptr f, tree_ptr src) {
+  darray_append(f->child, src);
+}
+
+void tree_append(tree_ptr f, tree_ptr p) {
+  darray_append(f->child, p);
+}
+
+tree_ptr tree_new_binary(fun_ptr fun, tree_ptr x, tree_ptr y) {
+  tree_ptr t = tree_new_funcall();
+  tree_append(t, x);
+  tree_append(t, y);
+  tree_set_fun(t, tree_new_fun(fun));
+  return t;
+}
+
+static tree_ptr tree_new_unary(fun_ptr fun, tree_ptr x) {
+  tree_ptr t = tree_new_funcall();
+  tree_append(t, x);
+  tree_set_fun(t, tree_new_fun(fun));
+  return t;
+}
+
+tree_ptr tree_new_neg(tree_ptr t) {
+  return tree_new_unary(fun_neg, t);
+}
+tree_ptr tree_new_add(tree_ptr x, tree_ptr y) {
+  return tree_new_binary(fun_add, x, y);
+}
+tree_ptr tree_new_sub(tree_ptr x, tree_ptr y) {
+  return tree_new_binary(fun_sub, x, y);
+}
+tree_ptr tree_new_mul(tree_ptr x, tree_ptr y) {
+  return tree_new_binary(fun_mul, x, y);
+}
+tree_ptr tree_new_div(tree_ptr x, tree_ptr y) {
+  return tree_new_binary(fun_div, x, y);
+}
+tree_ptr tree_new_pow(tree_ptr x, tree_ptr y) {
+  return tree_new_binary(fun_pow, x, y);
+}
+tree_ptr tree_new_eq(tree_ptr x, tree_ptr y) {
+  return tree_new_binary(fun_eq, x, y);
+}
+tree_ptr tree_new_ne(tree_ptr x, tree_ptr y) {
+  return tree_new_binary(fun_ne, x, y);
+}
+tree_ptr tree_new_le(tree_ptr x, tree_ptr y) {
+  return tree_new_binary(fun_le, x, y);
+}
+tree_ptr tree_new_ge(tree_ptr x, tree_ptr y) {
+  return tree_new_binary(fun_ge, x, y);
+}
+tree_ptr tree_new_lt(tree_ptr x, tree_ptr y) {
+  return tree_new_binary(fun_lt, x, y);
+}
+tree_ptr tree_new_gt(tree_ptr x, tree_ptr y) {
+  return tree_new_binary(fun_gt, x, y);
+}
+
+static val_ptr run_item(val_ptr v[]) {
+  mpz_t z;
+  mpz_init(z);
+  element_to_mpz(z, v[1]->elem);
+  int i = mpz_get_si(z);
+  mpz_clear(z);
+  element_ptr a = element_item(v[0]->elem, i);
+  element_ptr e = pbc_malloc(sizeof(*e));
+  element_init_same_as(e, a);
+  element_set(e, a);
+  return val_new_element(e);
+}
+static fun_t fun_item = {{ "item", run_item, 2, sig_elem_elem }};
+tree_ptr tree_new_item(tree_ptr x, tree_ptr y) {
+  return tree_new_binary(fun_item, x, y);
+}
+
+tree_ptr tree_new_assign(tree_ptr l, tree_ptr r) {
+  // TODO: Check l's type.
+  tree_ptr t = tree_new(eval_assign);
+  t->child = darray_new();
+  darray_append(t->child, l);
+  darray_append(t->child, r);
+  return t;
+}
+
+// Evaluate statement.
+void tree_eval_stmt(tree_ptr stmt) {
+  val_ptr v = tree_eval(stmt);
+  if (v && v_error == v->type) {
+    v->type->out_str(stdout, v);
+    putchar('\n');
+  } else if (stmt->eval != eval_assign && v) {
+    v->type->out_str(stdout, v);
+    putchar('\n');
+  }
+}
+
+static val_ptr run_nextprime(val_ptr v[]) {
+  element_ptr e = v[0]->elem;
+  mpz_t z;
+  mpz_init(z);
+  element_to_mpz(z, e);
+  mpz_nextprime(z, z);
+  element_set_mpz(e, z);
+  return v[0];
+}
+static fun_t fun_nextprime = {{ "nextprime", run_nextprime, 1, sig_elem }};
+
+static val_ptr run_order(val_ptr v[]) {
+  field_ptr f = v[0]->field;
+  element_ptr e = pbc_malloc(sizeof(*e));
+  element_init(e, M);
+  element_set_mpz(e, f->order);
+  return val_new_element(e);
+}
+static fun_t fun_ord = {{ "ord", run_order, 1, sig_field }};
+static fun_t fun_order = {{ "order", run_order, 1, sig_field }};
+
+static val_ptr run_random(val_ptr v[]) {
+  element_ptr e = pbc_malloc(sizeof(*e));
+  element_init(e, v[0]->field);
+  element_random(e);
+  return val_new_element(e);
+}
+static fun_t fun_rnd = {{ "rnd", run_random, 1, sig_field }};
+static fun_t fun_random = {{ "random", run_random, 1, sig_field }};
+
+static val_ptr run_sqrt(val_ptr v[]) {
+  // TODO: Check v[0] is square.
+  element_sqrt(v[0]->elem, v[0]->elem);
+  return v[0];
+}
+static fun_t fun_sqrt = {{ "sqrt", run_sqrt, 1, sig_elem }};
+
+static val_ptr run_invert(val_ptr v[]) {
+  // TODO: Check v[0] is invertible.
+  element_invert(v[0]->elem, v[0]->elem);
+  return v[0];
+}
+static fun_t fun_inv = {{ "inv", run_invert, 1, sig_elem }};
+
+static val_ptr run_type(val_ptr v[]) {
+  puts(v[0]->type->name);
+  return v[0];
+}
+static fun_t fun_type = {{ "type", run_type, 1, sig_any }};
+
+static val_ptr run_pairing(val_ptr v[]) {
+  element_ptr x = v[0]->elem;
+  element_ptr e = element_new(x->field->pairing->GT);
+  element_pairing(e, x, v[1]->elem);
+  return val_new_element(e);
+}
+static fun_t fun_pairing = {{ "pairing", run_pairing, 2, sig_elem_elem }};
+
+static val_ptr run_zmod(val_ptr v[]) {
+  element_ptr e = v[0]->elem;
+  mpz_t z;
+  mpz_init(z);
+  element_to_mpz(z, e);
+  field_ptr f = pbc_malloc(sizeof(*f));
+  field_init_fp(f, z);
+  mpz_clear(z);
+  return val_new_field(f);
+}
+static fun_t fun_zmod = {{ "zmod", run_zmod, 1, sig_elem }};
+
+static val_ptr run_poly(val_ptr v[]) {
+  field_ptr f = pbc_malloc(sizeof(*f));
+  field_init_poly(f, v[0]->field);
+  return val_new_field(f);
+}
+static fun_t fun_poly = {{ "poly", run_poly, 1, sig_field }};
+
+static val_ptr run_polymod(val_ptr v[]) {
+  // TODO: Check v[0] is a poly.
+  field_ptr f = pbc_malloc(sizeof(*f));
+  field_init_polymod(f, v[0]->elem);
+  return val_new_field(f);
+}
+static fun_t fun_polymod = {{ "polymod", run_polymod, 1, sig_elem }};
+
+static val_ptr run_extend(val_ptr v[]) {
+  // TODO: Check v[1] is multiz poly.
+  field_ptr fx = pbc_malloc(sizeof(*fx));
+  field_init_poly(fx, v[0]->field);
+  element_ptr poly = element_new(fx);
+  element_set_multiz(poly, v[1]->elem->data);
+  field_ptr f = pbc_malloc(sizeof(*f));
+  field_init_polymod(f, poly);
+  element_free(poly);
+  return val_new_field(f);
+}
+static fun_t fun_extend = {{ "extend", run_extend, 1, sig_field_elem }};
+
+static void init_pairing(const char *s) {
+  pairing_init_set_str(pairing, s);
+  assign_field(pairing->G1, "G1");
+  assign_field(pairing->G2, "G2");
+  assign_field(pairing->GT, "GT");
+  assign_field(pairing->Zr, "Zr");
+}
+
+static val_ptr run_exit(val_ptr v[]) {
+  mpz_t z;
+  mpz_init(z);
+  element_to_mpz(z, v[0]->elem);
+  exit(mpz_get_si(z));
+}
+static fun_t fun_exit = {{ "exit", run_exit, 1, sig_elem }};
+
+static val_ptr run_CHECK(val_ptr v[]) {
+  if (element_is0(v[0]->elem)) {
+    pbc_die("CHECK failed");
+  }
+  return v[0];
+}
+static fun_t fun_CHECK = {{ "CHECK", run_CHECK, 1, sig_elem }};
+
+static char *aparam =
+"type a\n"
+"q 8780710799663312522437781984754049815806883199414208211028653399266475630880222957078625179422662221423155858769582317459277713367317481324925129998224791\n"
+"h 12016012264891146079388821366740534204802954401251311822919615131047207289359704531102844802183906537786776\n"
+"r 730750818665451621361119245571504901405976559617\n"
+"exp2 159\n"
+"exp1 107\n"
+"sign1 1\n"
+"sign0 1\n";
+
+static char *dparam =
+"type d\n"
+"q 625852803282871856053922297323874661378036491717\n"
+"n 625852803282871856053923088432465995634661283063\n"
+"h 3\n"
+"r 208617601094290618684641029477488665211553761021\n"
+"a 581595782028432961150765424293919699975513269268\n"
+"b 517921465817243828776542439081147840953753552322\n"
+"k 6\n"
+"nk 60094290356408407130984161127310078516360031868417968262992864809623507269833854678414046779817844853757026858774966331434198257512457993293271849043664655146443229029069463392046837830267994222789160047337432075266619082657640364986415435746294498140589844832666082434658532589211525696\n"
+"hk 1380801711862212484403205699005242141541629761433899149236405232528956996854655261075303661691995273080620762287276051361446528504633283152278831183711301329765591450680250000592437612973269056\n"
+"coeff0 472731500571015189154958232321864199355792223347\n"
+"coeff1 352243926696145937581894994871017455453604730246\n"
+"coeff2 289113341693870057212775990719504267185772707305\n"
+"nqr 431211441436589568382088865288592347194866189652\n";
+
+static char *eparam =
+"type e\n"
+"q 7245986106510086080714203333362098431608853335867425877960916928496629182991629664903654100214900946450053872786629995869445693724001299041657434948257845644905153122838458864000479326695430719258600053239930483226650953770354174712511646273516974069245462534034085895319225452125649979474047163305307830001\n"
+"r 730750862221594424981965739670091261094297337857\n"
+"h 13569343110918781839835249021482970252603216587988030044836106948825516930173270978617489032334001006615524543925753725725046733884363846960470444404747241287743773746682188521738728797153760275116924829183670000\n"
+"a 7130970454025799000067946137594446075551569949583815943390108723282396973737794273397246892274981883807989525599540630855644968426794929215599380425269625872763801485968007136000471718335185787206876242871042697778608875139078711621836858237429403052273312335081163896980825048123655535355411494046493419999\n"
+"b 7169309004853894693616698536183663527570664411678352588247044791687141043489072737232715961588288238022010974661903752526911876859197052490952065266265699130144252031591491045333807587788600764557450846327338626261289568016170532652061787582791926724597362401398804563093625182790987016728290050466098223333\n"
+"exp2 159\n"
+"exp1 135\n"
+"sign1 1\n"
+"sign0 1\n";
+
+static char *fparam =
+"type f\n"
+"q 205523667896953300194896352429254920972540065223\n"
+"r 205523667896953300194895899082072403858390252929\n"
+"b 40218105156867728698573668525883168222119515413\n"
+"beta 115334401956802802075595682801335644058796914268\n"
+"alpha0 191079354656274778837764015557338301375963168470\n"
+"alpha1 71445317903696340296199556072836940741717506375\n";
+
+static char *gparam =
+"type g\n"
+"q 503189899097385532598615948567975432740967203\n"
+"n 503189899097385532598571084778608176410973351\n"
+"h 1\n"
+"r 503189899097385532598571084778608176410973351\n"
+"a 465197998498440909244782433627180757481058321\n"
+"b 463074517126110479409374670871346701448503064\n"
+"k 10\n"
+"nk 1040684643531490707494989587381629956832530311976146077888095795458709511789670022388326295177424065807612879371896982185473788988016190582073591316127396374860265835641044035656044524481121528846249501655527462202999638159773731830375673076317719519977183373353791119388388468745670818193868532404392452816602538968163226713846951514831917487400267590451867746120591750902040267826351982737642689423713163967384383105678367875981348397359466338807\n"
+"hk 4110127713690841149713310614420858884651261781185442551927080083178682965171097172366598236129731931693425629387502221804555636704708008882811353539555915064049685663790355716130262332064327767695339422323460458479884756000782939428852120522712008037615051139080628734566850259704397643028017435446110322024094259858170303605703280329322675124728639532674407\n"
+"coeff0 67343110967802947677845897216565803152319250\n"
+"coeff1 115936772834120270862756636148166314916823221\n"
+"coeff2 87387877425076080433559927080662339215696505\n"
+"coeff3 433223145899090928132052677121692683015058909\n"
+"coeff4 405367866213598664862417230702935310328613596\n"
+"nqr 22204504160560785687198080413579021865783099\n";
+
+static char *iparam =
+"type i\n"
+"m 97\n"
+"t 12\n"
+"n 2726865189058261010774960798134976187171462721\n"
+"n2 7\n";
+
+static val_ptr run_init_pairing_a(val_ptr v[]) {
+  UNUSED_VAR(v);
+  init_pairing(aparam);
+  return NULL;
+}
+static fun_t fun_init_pairing_a = {{
+    "init_pairing_a", run_init_pairing_a, 0, NULL
+    }};
+
+static val_ptr run_init_pairing_d(val_ptr v[]) {
+  UNUSED_VAR(v);
+  init_pairing(dparam);
+  return NULL;
+}
+static fun_t fun_init_pairing_d = {{
+    "init_pairing_d", run_init_pairing_d, 0, NULL
+    }};
+
+static val_ptr run_init_pairing_e(val_ptr v[]) {
+  UNUSED_VAR(v);
+  init_pairing(eparam);
+  return NULL;
+}
+static fun_t fun_init_pairing_e = {{
+    "init_pairing_e", run_init_pairing_e, 0, NULL
+    }};
+
+static val_ptr run_init_pairing_f(val_ptr v[]) {
+  UNUSED_VAR(v);
+  init_pairing(fparam);
+  return NULL;
+}
+static fun_t fun_init_pairing_f = {{
+    "init_pairing_f", run_init_pairing_f, 0, NULL
+    }};
+
+static val_ptr run_init_pairing_g(val_ptr v[]) {
+  UNUSED_VAR(v);
+  init_pairing(gparam);
+  return NULL;
+}
+static fun_t fun_init_pairing_g = {{
+    "init_pairing_g", run_init_pairing_g, 0, NULL
+    }};
+
+static val_ptr run_init_pairing_i(val_ptr v[]) {
+  UNUSED_VAR(v);
+  init_pairing(iparam);
+  return NULL;
+}
+static fun_t fun_init_pairing_i = {{
+    "init_pairing_i", run_init_pairing_i, 0, NULL
+    }};
+
+static void builtin(fun_ptr fun) {
+  symtab_put(reserved, val_new_fun(fun), fun->name);
+}
+
+int end_of_input;
+
+int yywrap_return1(void) { return 1; }
+
+int yywrap_readline(void) {
+  static char *currentline;
+  static YY_BUFFER_STATE st;
+  yy_delete_buffer(st);
+  free(currentline);
+  currentline = pbc_getline(option_prompt);
+  if (!currentline) {
+    end_of_input = 1;
+    return 1;
+  }
+  int n = strlen(currentline);
+  currentline = realloc(currentline, n + 2);
+  currentline[n] = '\n';
+  currentline[n + 1] = '\0';
+  st = yy_scan_string(currentline);
+  //if (option_echo) puts(currentline);
+  return 0;
+}
+
+static int (*yywrapfun)(void);
+int yywrap(void) {
+  return yywrapfun();
+}
+
+int main(int argc, char **argv) {
+  for (;;) {
+    int c = getopt(argc, argv, "y");
+    if (c == -1) break;
+    switch (c) {
+      case 'y':
+        option_easy = 1;
+        option_prompt = "> ";
+        break;
+      default:
+        fprintf(stderr, "unrecognized option: %c\n", c);
+        break;
+    }
+  }
+
+  field_init_z(Z);
+  field_init_multiz(M);
+  symtab_init(tab);
+
+  builtin(fun_rnd);
+  builtin(fun_random);
+  builtin(fun_ord);
+  builtin(fun_order);
+  builtin(fun_nextprime);
+  builtin(fun_sqrt);
+  builtin(fun_inv);
+  builtin(fun_type);
+  builtin(fun_pairing);
+  builtin(fun_zmod);
+  builtin(fun_poly);
+  builtin(fun_polymod);
+  builtin(fun_extend);
+  builtin(fun_exit);
+  builtin(fun_CHECK);
+  builtin(fun_init_pairing_a);
+  builtin(fun_init_pairing_d);
+  builtin(fun_init_pairing_e);
+  builtin(fun_init_pairing_f);
+  builtin(fun_init_pairing_g);
+  builtin(fun_init_pairing_i);
+  run_init_pairing_a(NULL);
+  symtab_put(reserved, val_new_field(M), "M");
+  symtab_put(reserved, val_new_field(Z), "Z");
+
+  if (argc > optind) {
+    FILE *fp = fopen(argv[optind], "r");
+    if (!fp) pbc_die("fopen failed on %s", argv[optind]);
+    YY_BUFFER_STATE st = yy_create_buffer(fp, YY_BUF_SIZE);
+    yy_switch_to_buffer(st);
+    yywrapfun = yywrap_return1;
+    yyparse();
+    yy_delete_buffer(st);
+  } else {
+    yywrapfun = yywrap_readline;
+    yywrap();
+    while (!end_of_input) {
+      if (2 == yyparse()) pbc_die("parser out of memory");
+    }
+    putchar('\n');
+  }
+
+  symtab_clear(tab);
+  field_clear(M);
+  return 0;
+}
diff --git a/moon-abe/pbc-0.5.14/pbc/pbc_getline.c b/moon-abe/pbc-0.5.14/pbc/pbc_getline.c
new file mode 100644
index 00000000..dc44cc40
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/pbc/pbc_getline.c
@@ -0,0 +1,17 @@
+#include <stdio.h>
+#include <string.h>
+
+#include "pbc_memory.h"
+
+char *pbc_getline(const char *prompt) {
+  char s[1024];
+  if (prompt) fputs(prompt, stdout);
+  if (!fgets(s, 1024, stdin)) return NULL;
+  if (feof(stdin)) return NULL;
+  /* use strdup rather than pbc_strdup. because
+   * 1. readline version of this function uses malloc.
+   * 2. pbc_malloc called by pbc_strdup may differ from malloc.
+   * here we keep consistency.
+   */
+  return strdup(s);
+}
diff --git a/moon-abe/pbc-0.5.14/pbc/pbc_getline.readline.c b/moon-abe/pbc-0.5.14/pbc/pbc_getline.readline.c
new file mode 100644
index 00000000..8d5e8f5a
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/pbc/pbc_getline.readline.c
@@ -0,0 +1,10 @@
+#include <stdio.h>
+#include <readline/readline.h>
+#include <readline/history.h>
+
+char *pbc_getline(const char *prompt)
+{
+    char *line = readline(prompt);
+    if (line && *line) add_history(line);
+    return line;
+}
diff --git a/moon-abe/pbc-0.5.14/pbc/pbc_tree.h b/moon-abe/pbc-0.5.14/pbc/pbc_tree.h
new file mode 100644
index 00000000..2526ab61
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/pbc/pbc_tree.h
@@ -0,0 +1,30 @@
+// Requires:
+// * field.h
+struct tree_s;
+typedef struct tree_s *tree_ptr;
+tree_ptr tree_new_z(const char* s);
+tree_ptr tree_new_empty_stmt_list(void);
+tree_ptr tree_new_empty_parms(void);
+tree_ptr tree_new_define(tree_ptr id, tree_ptr parm, tree_ptr body);
+tree_ptr tree_new_list(tree_ptr t);
+tree_ptr tree_new_id(const char* s);
+tree_ptr tree_new_assign(tree_ptr l, tree_ptr r);
+tree_ptr tree_new_funcall(void);
+void tree_append(tree_ptr f, tree_ptr p);
+void tree_set_fun(tree_ptr dst, tree_ptr src);
+void tree_eval_stmt(tree_ptr t);
+
+tree_ptr tree_new_neg(tree_ptr t);
+tree_ptr tree_new_add(tree_ptr x, tree_ptr y);
+tree_ptr tree_new_sub(tree_ptr x, tree_ptr y);
+tree_ptr tree_new_mul(tree_ptr x, tree_ptr y);
+tree_ptr tree_new_div(tree_ptr x, tree_ptr y);
+tree_ptr tree_new_pow(tree_ptr x, tree_ptr y);
+tree_ptr tree_new_eq(tree_ptr x, tree_ptr y);
+tree_ptr tree_new_ne(tree_ptr x, tree_ptr y);
+tree_ptr tree_new_le(tree_ptr x, tree_ptr y);
+tree_ptr tree_new_ge(tree_ptr x, tree_ptr y);
+tree_ptr tree_new_lt(tree_ptr x, tree_ptr y);
+tree_ptr tree_new_gt(tree_ptr x, tree_ptr y);
+tree_ptr tree_new_ternary(tree_ptr cond, tree_ptr t1, tree_ptr t2);
+tree_ptr tree_new_item(tree_ptr x, tree_ptr y);