pbc/pbc.c

   1 // Pairing-Based Calculator.
   2
   3 // TODO: Garbage collection.
   4 // TODO: Recursion (stack frames), anonymous functions.
   5
   6 #include <string.h>
   7
   8 #include "pbc.h"
   9 #include "pbc_fp.h"
  10 #include "pbc_z.h"
  11 #include "pbc_multiz.h"
  12 #include "pbc_poly.h"
  13
  14 #include "misc/darray.h"
  15 #include "misc/symtab.h"
  16
  17 #include "pbc_tree.h"
  18
  19 #include "lex.yy.h"
  20 #include "parser.tab.h"
  21
  22 int option_easy = 0;
  23 const char *option_prompt;
  24
  25 char *pbc_getline(const char *prompt);
  26
  27 void yyerror(char *s) { fprintf(stderr, "%s\n", s); }
  28 int yyparse(void);
  29
  30 // Symbol table holding built-in functions and variables.
  31 static symtab_t reserved;
  32 // Symbol table holding user-defined variable and function names.
  33 static symtab_t tab;
  34
  35 static field_t M;
  36 static field_t Z;
  37 static pairing_t pairing;
  38
  39 struct val_s;
  40 typedef struct val_s *val_ptr;
  41
  42 struct fun_s;
  43 typedef struct fun_s *fun_ptr;
  44
  45 // Syntax tree node.
  46 struct tree_s {
  47   // Evaluates this node.
  48   val_ptr (*eval)(tree_ptr);
  49   union {
  50     const char *id;
  51     element_ptr elem;
  52     // Built-in function.
  53     fun_ptr fun;
  54     // Child nodes.
  55     darray_ptr child;
  56   };
  57 };
  58
  59 enum {
  60   ARITY_VARIABLE = -1,
  61 };
  62
  63 // The interface of a val_ptr shared amongst many val_ptr objects.
  64 // Analog of C++ class.
  65 struct val_type_s {
  66   // One of element, field, function, error.
  67   char *name;
  68   // Print out current value.
  69   void (*out_str)(FILE *, val_ptr);
  70   // Called when a variable is evaluated, e.g. "foo;".
  71   val_ptr (*eval)(val_ptr);
  72   // Called when a variable is used as a function, e.g. "foo();".
  73   val_ptr (*funcall)(val_ptr, tree_ptr);
  74 };
  75
  76 // Functions plus type checking data.
  77 struct fun_s {
  78   const char *name;
  79   val_ptr (*run)(val_ptr[]);
  80   int arity;
  81   const struct val_type_s **sig;
  82 };
  83 typedef struct fun_s fun_t[1];
  84
  85 // When interpreting, each node of the syntax tree recursively evaluates
  86 // its children then returns a val_ptr.
  87 struct val_s {
  88   struct val_type_s *type;
  89   union {
  90     element_ptr elem;
  91     // User-defined function.
  92     tree_ptr def;
  93     // Built-in function.
  94     fun_ptr fun;
  95     field_ptr field;
  96     const char *msg;
  97   };
  98 };
  99
 100 static val_ptr val_new_element(element_ptr e);
 101 static val_ptr val_new_field(field_ptr e);
 102 static val_ptr val_new_error(const char *msg, ...);
 103
 104 // Evaluates syntax tree node.
 105 static val_ptr tree_eval(tree_ptr t) {
 106   return t->eval(t);
 107 }
 108
 109 static void v_elem_out(FILE* stream, val_ptr v) {
 110   element_out_str(stream, 0, v->elem);
 111 }
 112
 113 static val_ptr v_elem_eval(val_ptr v) {
 114   element_ptr e = pbc_malloc(sizeof(*e));
 115   element_init_same_as(e, v->elem);
 116   element_set(e, v->elem);
 117   return val_new_element(e);
 118 }
 119
 120 static void v_builtin_out(FILE* stream, val_ptr v) {
 121   // TODO: Print types of arguments.
 122   fprintf(stream, "built-in function %s, arity %d",
 123       v->fun->name, v->fun->arity);
 124 }
 125
 126 static void v_define_out(FILE* stream, val_ptr v) {
 127   fprintf(stream, "user-defined function %s",
 128       ((tree_ptr) darray_at(v->def->child, 0))->id);
 129 }
 130
 131 static val_ptr v_builtin(val_ptr v, tree_ptr t) {
 132   fun_ptr fun = v->fun;
 133   int n = fun->arity;
 134   if (1 + n != darray_count(t->child)) {
 135     return val_new_error("%s: wrong number of arguments", fun->name);
 136   }
 137   val_ptr* arg = pbc_malloc(n * sizeof(val_ptr));
 138   int i;
 139   for(i = 0; i < n; i++) {
 140     arg[i] = tree_eval(darray_at(t->child, i));
 141     if (fun->sig[i] && arg[i]->type != fun->sig[i]) {
 142       return val_new_error("%s: argument %d type mismatch", fun->name, i + 1);
 143     }
 144   }
 145   val_ptr out = fun->run(arg);
 146   pbc_free(arg);
 147   return out;
 148 }
 149
 150 static void eval_stmt(void *ptr) {
 151   tree_eval(ptr);
 152 }
 153
 154 static val_ptr v_def_call(val_ptr v, tree_ptr t) {
 155   int i;
 156   const char* name = ((tree_ptr) darray_at(v->def->child, 0))->id;
 157   darray_ptr parm = ((tree_ptr) darray_at(v->def->child, 1))->child;
 158   int n = darray_count(parm);
 159   if (1 + n != darray_count(t->child)) {
 160     return val_new_error("%s: wrong number of arguments", name);
 161   }
 162   for(i = 0; i < n; i++) {
 163     const char *id = ((tree_ptr) darray_at(parm, i))->id;
 164     val_ptr v1 = tree_eval(darray_at(t->child, i));
 165     // TODO: Stack frames for recursion.
 166     symtab_put(tab, v1, id);
 167   }
 168   // Evaluate function body.
 169   darray_ptr a = ((tree_ptr) darray_at(v->def->child, 2))->child;
 170   darray_forall(a, eval_stmt);
 171   return NULL;
 172 }
 173
 174 static val_ptr v_field_cast(val_ptr v, tree_ptr t) {
 175   // TODO: Check args, x is an element.
 176   val_ptr x = tree_eval(darray_at(t->child, 0));
 177   element_ptr e = x->elem;
 178   if (e->field == M) {
 179     if (v->field == M) return x;
 180     element_ptr e2 = element_new(v->field);
 181     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
 182       element_set0(e2);
 183     else if (element_is1(e)) // reason is same as above
 184       element_set1(e2);
 185     else
 186       element_set_multiz(e2, e->data);
 187     x->elem = e2;
 188     return x;
 189   }
 190   if (v->field == M) {
 191     // Map to/from integer. TODO: Map to/from multiz instead.
 192     mpz_t z;
 193     mpz_init(z);
 194     element_to_mpz(z, e);
 195     element_clear(e);
 196     element_init(e, v->field);
 197     element_set_mpz(e, z);
 198     mpz_clear(z);
 199   }
 200   return x;
 201 }
 202
 203 static void v_field_out(FILE* stream, val_ptr v) {
 204   field_out_info(stream, v->field);
 205 }
 206
 207 static val_ptr v_self(val_ptr v) {
 208   return v;
 209 }
 210
 211 static void v_err_out(FILE* stream, val_ptr v) {
 212   fprintf(stream, "%s", v->msg);
 213 }
 214
 215 static val_ptr v_errcall(val_ptr v, tree_ptr t) {
 216   UNUSED_VAR(t);
 217   return v;
 218 }
 219
 220 static struct val_type_s
 221   // TODO: Replace NULL with get_coeff.
 222   v_elem[1]  = {{  "element",    v_elem_out, v_elem_eval, NULL }},
 223   v_field[1] = {{    "field",   v_field_out,      v_self, v_field_cast }},
 224   v_fun[1]   = {{  "builtin", v_builtin_out,      v_self, v_builtin }},
 225   v_def[1]   = {{ "function",  v_define_out,      v_self, v_def_call }},
 226   v_error[1] = {{    "error",     v_err_out,      v_self, v_errcall }};
 227
 228 // Function signature constants for type checking.
 229 const struct val_type_s *sig_field[] = { v_field };
 230 const struct val_type_s *sig_elem[] = { v_elem };
 231 const struct val_type_s *sig_any[] = { NULL };
 232 const struct val_type_s *sig_elem_elem[] = { v_elem, v_elem };
 233 const struct val_type_s *sig_field_elem[] = { v_field, v_elem };
 234
 235 static val_ptr val_new_element(element_ptr e) {
 236   val_ptr v = pbc_malloc(sizeof(*v));
 237   v->type = v_elem;
 238   v->elem = e;
 239   return v;
 240 }
 241
 242 static val_ptr val_new_field(field_ptr f) {
 243   val_ptr v = pbc_malloc(sizeof(*v));
 244   v->type = v_field;
 245   v->field = f;
 246   return v;
 247 }
 248
 249 static val_ptr val_new_error(const char *msg, ...) {
 250   va_list params;
 251   char buf[80];
 252
 253   va_start(params, msg);
 254   vsnprintf(buf, 80, msg, params);
 255   va_end(params);
 256
 257   val_ptr v = pbc_malloc(sizeof(*v));
 258   v->type = v_error;
 259   v->msg = pbc_strdup(buf);
 260   return v;
 261 }
 262
 263 static val_ptr val_new_fun(fun_ptr fun) {
 264   val_ptr v = pbc_malloc(sizeof(*v));
 265   v->type = v_fun;
 266   v->fun = fun;
 267   return v;
 268 }
 269
 270 static val_ptr fun_bin(
 271     void (*binop)(element_ptr, element_ptr, element_ptr),
 272     val_ptr v[]) {
 273   binop(v[0]->elem, v[0]->elem, v[1]->elem);
 274   return v[0];
 275 }
 276
 277 static val_ptr run_add(val_ptr v[]) { return fun_bin(element_add, v); }
 278 static val_ptr run_sub(val_ptr v[]) { return fun_bin(element_sub, v); }
 279 static val_ptr run_mul(val_ptr v[]) { return fun_bin(element_mul, v); }
 280 static val_ptr run_div(val_ptr v[]) { return fun_bin(element_div, v); }
 281 static val_ptr run_pow(val_ptr v[]) { return fun_bin(element_pow_zn, v); }
 282
 283 static fun_t fun_add = {{ "add", run_add, 2, sig_elem_elem }};
 284 static fun_t fun_sub = {{ "sub", run_sub, 2, sig_elem_elem }};
 285 static fun_t fun_mul = {{ "mul", run_mul, 2, sig_elem_elem }};
 286 static fun_t fun_div = {{ "div", run_div, 2, sig_elem_elem }};
 287 static fun_t fun_pow = {{ "pow", run_pow, 2, sig_elem_elem }};
 288
 289 static val_ptr fun_cmp(val_ptr v[], int (*fun)(int)) {
 290   int i = element_cmp(v[0]->elem, v[1]->elem);
 291   element_ptr e = pbc_malloc(sizeof(*e));
 292   element_init(e, M);
 293   element_set_si(e, fun(i));
 294   v[0]->elem = e;
 295   return v[0];
 296 }
 297
 298 static int is0(int i) {
 299   return i == 0;
 300 }
 301
 302 static int isnot0(int i) {
 303   return i != 0;
 304 }
 305
 306 static int isle(int i) {
 307   return i <= 0;
 308 }
 309
 310 static int isge(int i) {
 311   return i >= 0;
 312 }
 313
 314 static int islt(int i) {
 315   return i < 0;
 316 }
 317
 318 static int isgt(int i) {
 319   return i > 0;
 320 }
 321
 322 static val_ptr run_eq(val_ptr v[]) {
 323   return fun_cmp(v, is0);
 324 }
 325
 326 static val_ptr run_ne(val_ptr v[]) {
 327   return fun_cmp(v, isnot0);
 328 }
 329
 330 static val_ptr run_le(val_ptr v[]) {
 331   return fun_cmp(v, isle);
 332 }
 333
 334 static val_ptr run_ge(val_ptr v[]) {
 335   return fun_cmp(v, isge);
 336 }
 337 static val_ptr run_lt(val_ptr v[]) {
 338   return fun_cmp(v, islt);
 339 }
 340 static val_ptr run_gt(val_ptr v[]) {
 341   return fun_cmp(v, isgt);
 342 }
 343
 344 static fun_t fun_eq = {{ "==", run_eq, 2, sig_elem_elem }};
 345 static fun_t fun_ne = {{ "!=", run_ne, 2, sig_elem_elem }};
 346 static fun_t fun_le = {{ "<=", run_le, 2, sig_elem_elem }};
 347 static fun_t fun_ge = {{ ">=", run_ge, 2, sig_elem_elem }};
 348 static fun_t fun_lt = {{ "<", run_lt, 2, sig_elem_elem }};
 349 static fun_t fun_gt = {{ ">", run_gt, 2, sig_elem_elem }};
 350
 351 static val_ptr eval_elem(tree_ptr t) {
 352   // TODO: Write element_clone(), or at least element_new().
 353   element_ptr e = pbc_malloc(sizeof(*e));
 354   element_init_same_as(e, t->elem);
 355   element_set(e, t->elem);
 356   return val_new_element(e);
 357 }
 358
 359 static val_ptr eval_list(tree_ptr t) {
 360   element_ptr e = NULL;
 361   int n = darray_count(t->child);
 362   int i;
 363   for(i = 0; i < n; i++) {
 364     val_ptr x = tree_eval(darray_at(t->child, i));
 365     // TODO: Also check x is a multiz.
 366     if (v_error == x->type) {
 367       return x;
 368     }
 369     if (v_elem != x->type) {
 370       return val_new_error("element expected in list");
 371     }
 372     if (!i) e = multiz_new_list(x->elem);
 373     else multiz_append(e, x->elem);
 374   }
 375   return val_new_element(e);
 376 }
 377
 378 static val_ptr eval_ternary(tree_ptr t) {
 379   val_ptr x = tree_eval(darray_at(t->child, 0));
 380   if (v_error == x->type) {
 381     return x;
 382   }
 383   if (x->type != v_elem) {
 384     return val_new_error("element expected in ternary operator");
 385   }
 386   if (!element_is0(x->elem)) {
 387     return tree_eval(darray_at(t->child, 1));
 388   }
 389   return tree_eval(darray_at(t->child, 2));
 390 }
 391
 392 static val_ptr eval_id(tree_ptr t) {
 393   val_ptr x = symtab_at(reserved, t->id);
 394   if (!x) x = symtab_at(tab, t->id);
 395   if (!x) {
 396     return val_new_error("undefined variable %s", t->id);
 397   }
 398   return x->type->eval(x);
 399 }
 400
 401 static val_ptr eval_funcall(tree_ptr t) {
 402   val_ptr x = tree_eval(darray_last(t->child));
 403   return x->type->funcall(x, t);
 404 }
 405
 406 static val_ptr eval_fun(tree_ptr t) {
 407   return val_new_fun(t->fun);
 408 }
 409
 410 static val_ptr run_neg(val_ptr v[]) {
 411   element_neg(v[0]->elem, v[0]->elem);
 412   return v[0];
 413 }
 414 static fun_t fun_neg = {{ "neg", run_neg, 1, sig_elem }};
 415
 416 static val_ptr eval_assign(tree_ptr t) {
 417   tree_ptr tid = darray_at(t->child, 0);
 418   val_ptr v = tree_eval(darray_at(t->child, 1));
 419   if (symtab_at(reserved, tid->id)) {
 420     return val_new_error("%s is reserved", tid->id);
 421   }
 422   symtab_put(tab, v, tid->id);
 423   return v;
 424 }
 425
 426 static void assign_field(field_ptr f, const char* s) {
 427   symtab_put(tab, val_new_field(f), s);
 428 }
 429
 430 tree_ptr tree_new(val_ptr (*eval)(tree_ptr)) {
 431   tree_ptr res = pbc_malloc(sizeof(*res));
 432   res->eval = eval;
 433   return res;
 434 }
 435
 436 tree_ptr tree_new_z(const char* s) {
 437   element_ptr e = pbc_malloc(sizeof(*e));
 438   element_init(e, M);
 439   element_set_str(e, s, 0);
 440   tree_ptr t = tree_new(eval_elem);
 441   t->elem = e;
 442   return t;
 443 }
 444
 445 static val_ptr eval_err(tree_ptr t) {
 446   UNUSED_VAR(t);
 447   pbc_die("BUG: shouldn't reach here!");
 448   return NULL;
 449 }
 450
 451 tree_ptr tree_new_empty_stmt_list() {
 452   tree_ptr t = tree_new(eval_err);
 453   t->child = darray_new();
 454   return t;
 455 }
 456
 457 tree_ptr tree_new_empty_parms() {
 458   tree_ptr t = tree_new(eval_err);
 459   t->child = darray_new();
 460   return t;
 461 }
 462
 463 static val_ptr eval_define(tree_ptr t) {
 464   val_ptr v = pbc_malloc(sizeof(*v));
 465   v->type = v_def;
 466   v->def = t;
 467   symtab_put(tab, v, ((tree_ptr) darray_at(t->child, 0))->id);
 468   return v;
 469 }
 470
 471 tree_ptr tree_new_define(tree_ptr id, tree_ptr parm, tree_ptr body) {
 472   tree_ptr t = tree_new(eval_define);
 473   t->child = darray_new();
 474   darray_append(t->child, id);
 475   darray_append(t->child, parm);
 476   darray_append(t->child, body);
 477   return t;
 478 }
 479
 480 tree_ptr tree_new_list(tree_ptr first) {
 481   tree_ptr t = tree_new(eval_list);
 482   t->child = darray_new();
 483   darray_append(t->child, first);
 484   return t;
 485 }
 486
 487 tree_ptr tree_new_ternary(tree_ptr cond, tree_ptr t1, tree_ptr t2) {
 488   tree_ptr t = tree_new(eval_ternary);
 489   t->child = darray_new();
 490   darray_append(t->child, cond);
 491   darray_append(t->child, t1);
 492   darray_append(t->child, t2);
 493   return t;
 494 }
 495
 496 tree_ptr tree_new_id(const char* s) {
 497   tree_ptr t = tree_new(eval_id);
 498   t->id = pbc_strdup(s);
 499   return t;
 500 }
 501
 502 tree_ptr tree_new_funcall(void) {
 503   tree_ptr t = tree_new(eval_funcall);
 504   t->child = darray_new();
 505   return t;
 506 }
 507
 508 static tree_ptr tree_new_fun(fun_ptr fun) {
 509   tree_ptr t = tree_new(eval_fun);
 510   t->fun = fun;
 511   return t;
 512 }
 513
 514 void tree_set_fun(tree_ptr f, tree_ptr src) {
 515   darray_append(f->child, src);
 516 }
 517
 518 void tree_append(tree_ptr f, tree_ptr p) {
 519   darray_append(f->child, p);
 520 }
 521
 522 tree_ptr tree_new_binary(fun_ptr fun, tree_ptr x, tree_ptr y) {
 523   tree_ptr t = tree_new_funcall();
 524   tree_append(t, x);
 525   tree_append(t, y);
 526   tree_set_fun(t, tree_new_fun(fun));
 527   return t;
 528 }
 529
 530 static tree_ptr tree_new_unary(fun_ptr fun, tree_ptr x) {
 531   tree_ptr t = tree_new_funcall();
 532   tree_append(t, x);
 533   tree_set_fun(t, tree_new_fun(fun));
 534   return t;
 535 }
 536
 537 tree_ptr tree_new_neg(tree_ptr t) {
 538   return tree_new_unary(fun_neg, t);
 539 }
 540 tree_ptr tree_new_add(tree_ptr x, tree_ptr y) {
 541   return tree_new_binary(fun_add, x, y);
 542 }
 543 tree_ptr tree_new_sub(tree_ptr x, tree_ptr y) {
 544   return tree_new_binary(fun_sub, x, y);
 545 }
 546 tree_ptr tree_new_mul(tree_ptr x, tree_ptr y) {
 547   return tree_new_binary(fun_mul, x, y);
 548 }
 549 tree_ptr tree_new_div(tree_ptr x, tree_ptr y) {
 550   return tree_new_binary(fun_div, x, y);
 551 }
 552 tree_ptr tree_new_pow(tree_ptr x, tree_ptr y) {
 553   return tree_new_binary(fun_pow, x, y);
 554 }
 555 tree_ptr tree_new_eq(tree_ptr x, tree_ptr y) {
 556   return tree_new_binary(fun_eq, x, y);
 557 }
 558 tree_ptr tree_new_ne(tree_ptr x, tree_ptr y) {
 559   return tree_new_binary(fun_ne, x, y);
 560 }
 561 tree_ptr tree_new_le(tree_ptr x, tree_ptr y) {
 562   return tree_new_binary(fun_le, x, y);
 563 }
 564 tree_ptr tree_new_ge(tree_ptr x, tree_ptr y) {
 565   return tree_new_binary(fun_ge, x, y);
 566 }
 567 tree_ptr tree_new_lt(tree_ptr x, tree_ptr y) {
 568   return tree_new_binary(fun_lt, x, y);
 569 }
 570 tree_ptr tree_new_gt(tree_ptr x, tree_ptr y) {
 571   return tree_new_binary(fun_gt, x, y);
 572 }
 573
 574 static val_ptr run_item(val_ptr v[]) {
 575   mpz_t z;
 576   mpz_init(z);
 577   element_to_mpz(z, v[1]->elem);
 578   int i = (int)mpz_get_si(z);
 579   mpz_clear(z);
 580   element_ptr a = element_item(v[0]->elem, i);
 581   element_ptr e = pbc_malloc(sizeof(*e));
 582   element_init_same_as(e, a);
 583   element_set(e, a);
 584   return val_new_element(e);
 585 }
 586 static fun_t fun_item = {{ "item", run_item, 2, sig_elem_elem }};
 587 tree_ptr tree_new_item(tree_ptr x, tree_ptr y) {
 588   return tree_new_binary(fun_item, x, y);
 589 }
 590
 591 tree_ptr tree_new_assign(tree_ptr l, tree_ptr r) {
 592   // TODO: Check l's type.
 593   tree_ptr t = tree_new(eval_assign);
 594   t->child = darray_new();
 595   darray_append(t->child, l);
 596   darray_append(t->child, r);
 597   return t;
 598 }
 599
 600 // Evaluate statement.
 601 void tree_eval_stmt(tree_ptr stmt) {
 602   val_ptr v = tree_eval(stmt);
 603   if (v && v_error == v->type) {
 604     v->type->out_str(stdout, v);
 605     putchar('\n');
 606   } else if (stmt->eval != eval_assign && v) {
 607     v->type->out_str(stdout, v);
 608     putchar('\n');
 609   }
 610 }
 611
 612 static val_ptr run_nextprime(val_ptr v[]) {
 613   element_ptr e = v[0]->elem;
 614   mpz_t z;
 615   mpz_init(z);
 616   element_to_mpz(z, e);
 617   mpz_nextprime(z, z);
 618   element_set_mpz(e, z);
 619   return v[0];
 620 }
 621 static fun_t fun_nextprime = {{ "nextprime", run_nextprime, 1, sig_elem }};
 622
 623 static val_ptr run_order(val_ptr v[]) {
 624   field_ptr f = v[0]->field;
 625   element_ptr e = pbc_malloc(sizeof(*e));
 626   element_init(e, M);
 627   element_set_mpz(e, f->order);
 628   return val_new_element(e);
 629 }
 630 static fun_t fun_ord = {{ "ord", run_order, 1, sig_field }};
 631 static fun_t fun_order = {{ "order", run_order, 1, sig_field }};
 632
 633 static val_ptr run_random(val_ptr v[]) {
 634   element_ptr e = pbc_malloc(sizeof(*e));
 635   element_init(e, v[0]->field);
 636   element_random(e);
 637   return val_new_element(e);
 638 }
 639 static fun_t fun_rnd = {{ "rnd", run_random, 1, sig_field }};
 640 static fun_t fun_random = {{ "random", run_random, 1, sig_field }};
 641
 642 static val_ptr run_sqrt(val_ptr v[]) {
 643   // TODO: Check v[0] is square.
 644   element_sqrt(v[0]->elem, v[0]->elem);
 645   return v[0];
 646 }
 647 static fun_t fun_sqrt = {{ "sqrt", run_sqrt, 1, sig_elem }};
 648
 649 static val_ptr run_invert(val_ptr v[]) {
 650   // TODO: Check v[0] is invertible.
 651   element_invert(v[0]->elem, v[0]->elem);
 652   return v[0];
 653 }
 654 static fun_t fun_inv = {{ "inv", run_invert, 1, sig_elem }};
 655
 656 static val_ptr run_type(val_ptr v[]) {
 657   puts(v[0]->type->name);
 658   return v[0];
 659 }
 660 static fun_t fun_type = {{ "type", run_type, 1, sig_any }};
 661
 662 static val_ptr run_pairing(val_ptr v[]) {
 663   element_ptr x = v[0]->elem;
 664   element_ptr e = element_new(x->field->pairing->GT);
 665   element_pairing(e, x, v[1]->elem);
 666   return val_new_element(e);
 667 }
 668 static fun_t fun_pairing = {{ "pairing", run_pairing, 2, sig_elem_elem }};
 669
 670 static val_ptr run_zmod(val_ptr v[]) {
 671   element_ptr e = v[0]->elem;
 672   mpz_t z;
 673   mpz_init(z);
 674   element_to_mpz(z, e);
 675   field_ptr f = pbc_malloc(sizeof(*f));
 676   field_init_fp(f, z);
 677   mpz_clear(z);
 678   return val_new_field(f);
 679 }
 680 static fun_t fun_zmod = {{ "zmod", run_zmod, 1, sig_elem }};
 681
 682 static val_ptr run_poly(val_ptr v[]) {
 683   field_ptr f = pbc_malloc(sizeof(*f));
 684   field_init_poly(f, v[0]->field);
 685   return val_new_field(f);
 686 }
 687 static fun_t fun_poly = {{ "poly", run_poly, 1, sig_field }};
 688
 689 static val_ptr run_polymod(val_ptr v[]) {
 690   // TODO: Check v[0] is a poly.
 691   field_ptr f = pbc_malloc(sizeof(*f));
 692   field_init_polymod(f, v[0]->elem);
 693   return val_new_field(f);
 694 }
 695 static fun_t fun_polymod = {{ "polymod", run_polymod, 1, sig_elem }};
 696
 697 static val_ptr run_extend(val_ptr v[]) {
 698   // TODO: Check v[1] is multiz poly.
 699   field_ptr fx = pbc_malloc(sizeof(*fx));
 700   field_init_poly(fx, v[0]->field);
 701   element_ptr poly = element_new(fx);
 702   element_set_multiz(poly, v[1]->elem->data);
 703   field_ptr f = pbc_malloc(sizeof(*f));
 704   field_init_polymod(f, poly);
 705   element_free(poly);
 706   return val_new_field(f);
 707 }
 708 static fun_t fun_extend = {{ "extend", run_extend, 1, sig_field_elem }};
 709
 710 static void init_pairing(const char *s) {
 711   pairing_init_set_str(pairing, s);
 712   assign_field(pairing->G1, "G1");
 713   assign_field(pairing->G2, "G2");
 714   assign_field(pairing->GT, "GT");
 715   assign_field(pairing->Zr, "Zr");
 716 }
 717
 718 static val_ptr run_exit(val_ptr v[]) {
 719   mpz_t z;
 720   mpz_init(z);
 721   element_to_mpz(z, v[0]->elem);
 722   exit((int)mpz_get_si(z));
 723 }
 724 static fun_t fun_exit = {{ "exit", run_exit, 1, sig_elem }};
 725
 726 static val_ptr run_CHECK(val_ptr v[]) {
 727   if (element_is0(v[0]->elem)) {
 728     pbc_die("CHECK failed");
 729   }
 730   return v[0];
 731 }
 732 static fun_t fun_CHECK = {{ "CHECK", run_CHECK, 1, sig_elem }};
 733
 734 static char *aparam =
 735 "type a\n"
 736 "q 8780710799663312522437781984754049815806883199414208211028653399266475630880222957078625179422662221423155858769582317459277713367317481324925129998224791\n"
 737 "h 12016012264891146079388821366740534204802954401251311822919615131047207289359704531102844802183906537786776\n"
 738 "r 730750818665451621361119245571504901405976559617\n"
 739 "exp2 159\n"
 740 "exp1 107\n"
 741 "sign1 1\n"
 742 "sign0 1\n";
 743
 744 static char *dparam =
 745 "type d\n"
 746 "q 625852803282871856053922297323874661378036491717\n"
 747 "n 625852803282871856053923088432465995634661283063\n"
 748 "h 3\n"
 749 "r 208617601094290618684641029477488665211553761021\n"
 750 "a 581595782028432961150765424293919699975513269268\n"
 751 "b 517921465817243828776542439081147840953753552322\n"
 752 "k 6\n"
 753 "nk 60094290356408407130984161127310078516360031868417968262992864809623507269833854678414046779817844853757026858774966331434198257512457993293271849043664655146443229029069463392046837830267994222789160047337432075266619082657640364986415435746294498140589844832666082434658532589211525696\n"
 754 "hk 1380801711862212484403205699005242141541629761433899149236405232528956996854655261075303661691995273080620762287276051361446528504633283152278831183711301329765591450680250000592437612973269056\n"
 755 "coeff0 472731500571015189154958232321864199355792223347\n"
 756 "coeff1 352243926696145937581894994871017455453604730246\n"
 757 "coeff2 289113341693870057212775990719504267185772707305\n"
 758 "nqr 431211441436589568382088865288592347194866189652\n";
 759
 760 static char *eparam =
 761 "type e\n"
 762 "q 7245986106510086080714203333362098431608853335867425877960916928496629182991629664903654100214900946450053872786629995869445693724001299041657434948257845644905153122838458864000479326695430719258600053239930483226650953770354174712511646273516974069245462534034085895319225452125649979474047163305307830001\n"
 763 "r 730750862221594424981965739670091261094297337857\n"
 764 "h 13569343110918781839835249021482970252603216587988030044836106948825516930173270978617489032334001006615524543925753725725046733884363846960470444404747241287743773746682188521738728797153760275116924829183670000\n"
 765 "a 7130970454025799000067946137594446075551569949583815943390108723282396973737794273397246892274981883807989525599540630855644968426794929215599380425269625872763801485968007136000471718335185787206876242871042697778608875139078711621836858237429403052273312335081163896980825048123655535355411494046493419999\n"
 766 "b 7169309004853894693616698536183663527570664411678352588247044791687141043489072737232715961588288238022010974661903752526911876859197052490952065266265699130144252031591491045333807587788600764557450846327338626261289568016170532652061787582791926724597362401398804563093625182790987016728290050466098223333\n"
 767 "exp2 159\n"
 768 "exp1 135\n"
 769 "sign1 1\n"
 770 "sign0 1\n";
 771
 772 static char *fparam =
 773 "type f\n"
 774 "q 205523667896953300194896352429254920972540065223\n"
 775 "r 205523667896953300194895899082072403858390252929\n"
 776 "b 40218105156867728698573668525883168222119515413\n"
 777 "beta 115334401956802802075595682801335644058796914268\n"
 778 "alpha0 191079354656274778837764015557338301375963168470\n"
 779 "alpha1 71445317903696340296199556072836940741717506375\n";
 780
 781 static char *gparam =
 782 "type g\n"
 783 "q 503189899097385532598615948567975432740967203\n"
 784 "n 503189899097385532598571084778608176410973351\n"
 785 "h 1\n"
 786 "r 503189899097385532598571084778608176410973351\n"
 787 "a 465197998498440909244782433627180757481058321\n"
 788 "b 463074517126110479409374670871346701448503064\n"
 789 "k 10\n"
 790 "nk 1040684643531490707494989587381629956832530311976146077888095795458709511789670022388326295177424065807612879371896982185473788988016190582073591316127396374860265835641044035656044524481121528846249501655527462202999638159773731830375673076317719519977183373353791119388388468745670818193868532404392452816602538968163226713846951514831917487400267590451867746120591750902040267826351982737642689423713163967384383105678367875981348397359466338807\n"
 791 "hk 4110127713690841149713310614420858884651261781185442551927080083178682965171097172366598236129731931693425629387502221804555636704708008882811353539555915064049685663790355716130262332064327767695339422323460458479884756000782939428852120522712008037615051139080628734566850259704397643028017435446110322024094259858170303605703280329322675124728639532674407\n"
 792 "coeff0 67343110967802947677845897216565803152319250\n"
 793 "coeff1 115936772834120270862756636148166314916823221\n"
 794 "coeff2 87387877425076080433559927080662339215696505\n"
 795 "coeff3 433223145899090928132052677121692683015058909\n"
 796 "coeff4 405367866213598664862417230702935310328613596\n"
 797 "nqr 22204504160560785687198080413579021865783099\n";
 798
 799 static char *iparam =
 800 "type i\n"
 801 "m 97\n"
 802 "t 12\n"
 803 "n 2726865189058261010774960798134976187171462721\n"
 804 "n2 7\n";
 805
 806 static val_ptr run_init_pairing_a(val_ptr v[]) {
 807   UNUSED_VAR(v);
 808   init_pairing(aparam);
 809   return NULL;
 810 }
 811 static fun_t fun_init_pairing_a = {{
 812     "init_pairing_a", run_init_pairing_a, 0, NULL
 813     }};
 814
 815 static val_ptr run_init_pairing_d(val_ptr v[]) {
 816   UNUSED_VAR(v);
 817   init_pairing(dparam);
 818   return NULL;
 819 }
 820 static fun_t fun_init_pairing_d = {{
 821     "init_pairing_d", run_init_pairing_d, 0, NULL
 822     }};
 823
 824 static val_ptr run_init_pairing_e(val_ptr v[]) {
 825   UNUSED_VAR(v);
 826   init_pairing(eparam);
 827   return NULL;
 828 }
 829 static fun_t fun_init_pairing_e = {{
 830     "init_pairing_e", run_init_pairing_e, 0, NULL
 831     }};
 832
 833 static val_ptr run_init_pairing_f(val_ptr v[]) {
 834   UNUSED_VAR(v);
 835   init_pairing(fparam);
 836   return NULL;
 837 }
 838 static fun_t fun_init_pairing_f = {{
 839     "init_pairing_f", run_init_pairing_f, 0, NULL
 840     }};
 841
 842 static val_ptr run_init_pairing_g(val_ptr v[]) {
 843   UNUSED_VAR(v);
 844   init_pairing(gparam);
 845   return NULL;
 846 }
 847 static fun_t fun_init_pairing_g = {{
 848     "init_pairing_g", run_init_pairing_g, 0, NULL
 849     }};
 850
 851 static val_ptr run_init_pairing_i(val_ptr v[]) {
 852   UNUSED_VAR(v);
 853   init_pairing(iparam);
 854   return NULL;
 855 }
 856 static fun_t fun_init_pairing_i = {{
 857     "init_pairing_i", run_init_pairing_i, 0, NULL
 858     }};
 859
 860 static void builtin(fun_ptr fun) {
 861   symtab_put(reserved, val_new_fun(fun), fun->name);
 862 }
 863
 864 int end_of_input;
 865
 866 int yywrap_return1(void) { return 1; }
 867
 868 int yywrap_readline(void) {
 869   static char *currentline;
 870   static YY_BUFFER_STATE st;
 871   yy_delete_buffer(st);
 872   free(currentline);
 873   currentline = pbc_getline(option_prompt);
 874   if (!currentline) {
 875     end_of_input = 1;
 876     return 1;
 877   }
 878   size_t n = strlen(currentline);
 879   currentline = realloc(currentline, n + 2);
 880   currentline[n] = '\n';
 881   currentline[n + 1] = '\0';
 882   st = yy_scan_string(currentline);
 883   //if (option_echo) puts(currentline);
 884   return 0;
 885 }
 886
 887 static int (*yywrapfun)(void);
 888 int yywrap(void) {
 889   return yywrapfun();
 890 }
 891
 892 int main(int argc, char **argv) {
 893   for (;;) {
 894     int c = getopt(argc, argv, "y");
 895     if (c == -1) break;
 896     switch (c) {
 897       case 'y':
 898         option_easy = 1;
 899         option_prompt = "> ";
 900         break;
 901       default:
 902         fprintf(stderr, "unrecognized option: %c\n", c);
 903         break;
 904     }
 905   }
 906
 907   field_init_z(Z);
 908   field_init_multiz(M);
 909   symtab_init(tab);
 910
 911   builtin(fun_rnd);
 912   builtin(fun_random);
 913   builtin(fun_ord);
 914   builtin(fun_order);
 915   builtin(fun_nextprime);
 916   builtin(fun_sqrt);
 917   builtin(fun_inv);
 918   builtin(fun_type);
 919   builtin(fun_pairing);
 920   builtin(fun_zmod);
 921   builtin(fun_poly);
 922   builtin(fun_polymod);
 923   builtin(fun_extend);
 924   builtin(fun_exit);
 925   builtin(fun_CHECK);
 926   builtin(fun_init_pairing_a);
 927   builtin(fun_init_pairing_d);
 928   builtin(fun_init_pairing_e);
 929   builtin(fun_init_pairing_f);
 930   builtin(fun_init_pairing_g);
 931   builtin(fun_init_pairing_i);
 932   run_init_pairing_a(NULL);
 933   symtab_put(reserved, val_new_field(M), "M");
 934   symtab_put(reserved, val_new_field(Z), "Z");
 935
 936   if (argc > optind) {
 937     FILE *fp = fopen(argv[optind], "r");
 938     if (!fp) pbc_die("fopen failed on %s", argv[optind]);
 939     YY_BUFFER_STATE st = yy_create_buffer(fp, YY_BUF_SIZE);
 940     yy_switch_to_buffer(st);
 941     yywrapfun = yywrap_return1;
 942     yyparse();
 943     yy_delete_buffer(st);
 944   } else {
 945     yywrapfun = yywrap_readline;
 946     yywrap();
 947     while (!end_of_input) {
 948       if (2 == yyparse()) pbc_die("parser out of memory");
 949     }
 950     putchar('\n');
 951   }
 952
 953   symtab_clear(tab);
 954   field_clear(M);
 955   return 0;
 956 }