mes.c

   1 /* -*-comment-start: "//";comment-end:""-*-
   2  * Mes --- Maxwell Equations of Software
   3  * Copyright © 2016 Jan Nieuwenhuizen <janneke@gnu.org>
   4  *
   5  * This file is part of Mes.
   6  *
   7  * Mes is free software; you can redistribute it and/or modify it
   8  * under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 3 of the License, or (at
  10  * your option) any later version.
  11  *
  12  * Mes is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Mes.  If not, see <http://www.gnu.org/licenses/>.
  19  */
  20
  21 #define _GNU_SOURCE
  22 #include <assert.h>
  23 #include <ctype.h>
  24 #include <limits.h>
  25 #include <stdio.h>
  26 #include <string.h>
  27 #include <stdlib.h>
  28 #include <stdbool.h>
  29
  30 #define DEBUG 0
  31 #define QUASIQUOTE 1
  32 //#define QUASISYNTAX 0
  33
  34 enum type {CHAR, MACRO, NUMBER, PAIR, SCM, STRING, SYMBOL, REF, VALUES, VECTOR,
  35            FUNCTION0, FUNCTION1, FUNCTION2, FUNCTION3, FUNCTIONn};
  36 struct scm_t;
  37 typedef struct scm_t* (*function0_t) (void);
  38 typedef struct scm_t* (*function1_t) (struct scm_t*);
  39 typedef struct scm_t* (*function2_t) (struct scm_t*, struct scm_t*);
  40 typedef struct scm_t* (*function3_t) (struct scm_t*, struct scm_t*, struct scm_t*);
  41 typedef struct scm_t* (*functionn_t) (struct scm_t*);
  42
  43 typedef struct scm_t {
  44   enum type type;
  45   union {
  46     char const *name;
  47     struct scm_t* string;
  48     struct scm_t* car;
  49     struct scm_t* ref;
  50     int length;
  51   };
  52   union {
  53     int value;
  54     function0_t function0;
  55     function1_t function1;
  56     function2_t function2;
  57     function3_t function3;
  58     functionn_t functionn;
  59     struct scm_t* cdr;
  60     struct scm_t* macro;
  61     struct scm_t* vector;
  62     int hits;
  63   };
  64 } scm;
  65
  66 #include "define.environment.h"
  67 #include "lib.environment.h"
  68 #include "math.environment.h"
  69 #include "mes.environment.h"
  70 #include "posix.environment.h"
  71 #include "quasiquote.environment.h"
  72 #include "string.environment.h"
  73 #include "type.environment.h"
  74
  75 scm *display_ (FILE* f, scm *x);
  76 scm *display_helper (FILE*, scm*, bool, char const*, bool);
  77
  78 scm scm_nil = {SCM, "()"};
  79 scm scm_dot = {SCM, "."};
  80 scm scm_f = {SCM, "#f"};
  81 scm scm_t = {SCM, "#t"};
  82 scm scm_undefined = {SCM, "*undefined*"};
  83 scm scm_unspecified = {SCM, "*unspecified*"};
  84 scm scm_closure = {SCM, "*closure*"};
  85 scm scm_circular = {SCM, "*circular*"};
  86 #if BOOT
  87 scm scm_label = {
  88   SCM, "label"};
  89 #endif
  90 scm scm_begin = {SCM, "begin"};
  91
  92 scm symbol_lambda = {SYMBOL, "lambda"};
  93 scm symbol_begin = {SYMBOL, "begin"};
  94 scm symbol_if = {SYMBOL, "if"};
  95 scm symbol_define = {SYMBOL, "define"};
  96 scm symbol_define_macro = {SCM, "define-macro"};
  97 scm symbol_set_x = {SYMBOL, "set!"};
  98
  99 scm symbol_quote = {SYMBOL, "quote"};
 100 scm symbol_quasiquote = {SYMBOL, "quasiquote"};
 101 scm symbol_unquote = {SYMBOL, "unquote"};
 102 scm symbol_unquote_splicing = {SYMBOL, "unquote-splicing"};
 103
 104 scm symbol_sc_expand = {SYMBOL, "sc-expand"};
 105 scm symbol_expand_macro = {SYMBOL, "expand-macro"};
 106 scm symbol_sc_expander_alist = {SYMBOL, "*sc-expander-alist*"};
 107 scm symbol_noexpand = {SYMBOL, "noexpand"};
 108 scm symbol_syntax = {SYMBOL, "syntax"};
 109 scm symbol_quasisyntax = {SYMBOL, "quasisyntax"};
 110 scm symbol_unsyntax = {SYMBOL, "unsyntax"};
 111 scm symbol_unsyntax_splicing = {SYMBOL, "unsyntax-splicing"};
 112
 113 scm symbol_call_with_values = {SYMBOL, "call-with-values"};
 114 scm symbol_current_module = {SYMBOL, "current-module"};
 115
 116
 117 scm char_nul = {CHAR, .name="nul", .value=0};
 118 scm char_backspace = {CHAR, .name="backspace", .value=8};
 119 scm char_tab = {CHAR, .name="tab", .value=9};
 120 scm char_newline = {CHAR, .name="newline", .value=10};
 121 scm char_vt = {CHAR, .name="vt", .value=11};
 122 scm char_page = {CHAR, .name="page", .value=12};
 123 scm char_return = {CHAR, .name="return", .value=13};
 124 scm char_space = {CHAR, .name="space", .value=32};
 125
 126 // PRIMITIVES
 127
 128 scm *
 129 car (scm *x)
 130 {
 131   assert (x->type == PAIR);
 132   return x->car;
 133 }
 134
 135 scm *
 136 cdr (scm *x)
 137 {
 138   assert (x->type == PAIR);
 139   return x->cdr;
 140 }
 141
 142 scm *
 143 alloc (int n)
 144 {
 145   return (scm*)malloc (n * sizeof (scm));
 146 }
 147
 148 scm *
 149 make_cell (scm *type, scm *car, scm *cdr)
 150 {
 151   scm *x = alloc (1);
 152   assert (type->type == NUMBER);
 153   x->type = type->value;
 154   if (type->value == CHAR || type->value == NUMBER) {
 155     if (car) x->car = car->car;
 156     if (cdr) x->cdr = cdr->cdr;
 157   } else {
 158     x->car = car;
 159     x->cdr = cdr;
 160   }
 161   return x;
 162 }
 163
 164 scm *
 165 cons (scm *x, scm *y)
 166 {
 167   scm t = {NUMBER, .value=PAIR};
 168   return make_cell (&t, x, y);
 169 }
 170
 171 scm *
 172 eq_p (scm *x, scm *y)
 173 {
 174   return (x == y
 175           || (x->type == CHAR && y->type == CHAR
 176               && x->value == y->value)
 177           || (x->type == NUMBER && y->type == NUMBER
 178               && x->value == y->value))
 179     ? &scm_t : &scm_f;
 180 }
 181
 182 scm *
 183 set_car_x (scm *x, scm *e)
 184 {
 185   assert (x->type == PAIR);
 186   x->car = e;
 187   return &scm_unspecified;
 188 }
 189
 190 scm *
 191 set_cdr_x (scm *x, scm *e)
 192 {
 193   assert (x->type == PAIR);
 194   cache_invalidate (x->cdr);
 195   x->cdr = e;
 196   return &scm_unspecified;
 197 }
 198
 199 scm *
 200 set_env_x (scm *x, scm *e, scm *a)
 201 {
 202   cache_invalidate (x);
 203   scm *p = assq (x, a);
 204   if (p->type != PAIR)
 205     {
 206       fprintf (stderr, "set!: unbound variable:");
 207       display_ (stderr, x);
 208       fprintf (stderr, "\n");
 209       assert (!"unbound variable");
 210     }
 211   return set_cdr_x (p, e);
 212 }
 213
 214 scm *
 215 quote (scm *x)
 216 {
 217   return cons (&symbol_quote, x);
 218 }
 219
 220 scm *
 221 quasiquote (scm *x)
 222 {
 223   return cons (&symbol_quasiquote, x);
 224 }
 225
 226 scm *
 227 quasisyntax (scm *x)
 228 {
 229   return cons (&symbol_quasisyntax, x);
 230 }
 231
 232 scm *
 233 pairlis (scm *x, scm *y, scm *a)
 234 {
 235   if (x == &scm_nil)
 236     return a;
 237   if (pair_p (x) == &scm_f)
 238     return cons (cons (x, y), a);
 239   return cons (cons (car (x), car (y)),
 240                pairlis (cdr (x), cdr (y), a));
 241 }
 242
 243 scm *
 244 assq (scm *x, scm *a)
 245 {
 246   while (a != &scm_nil && eq_p (x, a->car->car) == &scm_f) a = a->cdr;
 247   return a != &scm_nil ? a->car : &scm_f;
 248 }
 249
 250 #define ENV_CACHE 1
 251 #define CACHE_SIZE 30
 252 #define ENV_HEAD 15
 253
 254 #if !ENV_CACHE
 255 scm *
 256 assq_ref_cache (scm *x, scm *a)
 257 {
 258   x = assq (x, a);
 259   if (x == &scm_f) return &scm_undefined;
 260   return x->cdr;
 261 }
 262 scm*cache_invalidate (scm*x){}
 263 scm*cache_invalidate_range (scm*p,scm*a){}
 264 scm*cache_save (scm*p){}
 265 scm*cache_lookup (scm*x){}
 266
 267 #else // ENV_CACHE
 268
 269 scm *env_cache_cars[CACHE_SIZE];
 270 scm *env_cache_cdrs[CACHE_SIZE];
 271 int cache_threshold = 0;
 272 scm *
 273 cache_save (scm *p)
 274 {
 275   int n = p->car->hits;
 276   if (n < cache_threshold) return &scm_unspecified;
 277   int j = -1;
 278   for (int i=0; i < CACHE_SIZE; i++) {
 279     if (!env_cache_cars[i]) {
 280       j = i;
 281       break;
 282     }
 283     if (env_cache_cars[i] == p->car) return &scm_unspecified;
 284     if (n > env_cache_cars[i]->hits) {
 285       n = env_cache_cars[i]->hits;
 286       j = i;
 287     }
 288   }
 289   if (j >= 0) {
 290     cache_threshold = p->car->hits;
 291     env_cache_cars[j] = p->car;
 292     env_cache_cdrs[j] = p->cdr;
 293   }
 294   return &scm_unspecified;
 295 }
 296
 297 scm *
 298 cache_lookup (scm *x)
 299 {
 300   for (int i=0; i < CACHE_SIZE; i++) {
 301     if (!env_cache_cars[i]) break;
 302     if (env_cache_cars[i] == x) return env_cache_cdrs[i];
 303   }
 304   return &scm_undefined;
 305 }
 306
 307 scm *
 308 cache_invalidate (scm *x)
 309 {
 310   for (int i=0; i < CACHE_SIZE; i++) {
 311     if (env_cache_cars[i] == x) {
 312       env_cache_cars[i] = 0;
 313       break;
 314     }
 315   }
 316   return &scm_unspecified;
 317 }
 318
 319 scm *
 320 cache_invalidate_range (scm *p, scm *a)
 321 {
 322   do {
 323     cache_invalidate (p->car->car);
 324     p = p->cdr;
 325   } while (p != a);
 326   return &scm_unspecified;
 327 }
 328
 329 scm *
 330 assq_ref_cache (scm *x, scm *a)
 331 {
 332   x->hits++;
 333   scm *c = cache_lookup (x);
 334   if (c != &scm_undefined) return c;
 335   int i = 0;
 336   while (a != &scm_nil && x != a->car->car) {i++;a = a->cdr;}
 337   if (a == &scm_nil) return &scm_undefined;
 338   if (i>ENV_HEAD) cache_save (a->car);
 339   return a->car->cdr;
 340 }
 341 #endif // ENV_CACHE
 342
 343 scm *
 344 evlis_env (scm *m, scm *a)
 345 {
 346   if (m == &scm_nil) return &scm_nil;
 347   if (m->type != PAIR) return builtin_eval (m, a);
 348   scm *e = builtin_eval (car (m), a);
 349   return cons (e, evlis_env (cdr (m), a));
 350 }
 351
 352 scm *
 353 apply_env (scm *fn, scm *x, scm *a)
 354 {
 355   if (fn->type != PAIR)
 356     {
 357       if (fn == &scm_car) return x->car->car;
 358       if (fn == &scm_cdr) return x->car->cdr;
 359       if (builtin_p (fn) == &scm_t)
 360         return call (fn, x);
 361       if (eq_p (fn, &symbol_call_with_values) == &scm_t)
 362         return call (&scm_call_with_values_env, append2 (x, cons (a, &scm_nil)));
 363       if (fn == &symbol_current_module) return a;
 364     }
 365   else if (fn->car == &symbol_lambda) {
 366     scm *p = pairlis (cadr (fn), x, a);
 367     cache_invalidate_range (p, a->cdr);
 368     scm *r = begin_env (cddr (fn), cons (cons (&scm_closure, p), p));
 369     cache_invalidate_range (p, a->cdr);
 370     return r;
 371   }
 372   else if (fn->car == &scm_closure) {
 373     scm *args = caddr (fn);
 374     scm *body = cdddr (fn);
 375     a = cdadr (fn);
 376     a = cdr (a);
 377     scm *p = pairlis (args, x, a);
 378     cache_invalidate_range (p, a->cdr);
 379     scm *r = begin_env (body, cons (cons (&scm_closure, p), p));
 380     cache_invalidate_range (p, a->cdr);
 381     return r;
 382   }
 383 #if BOOT
 384   else if (fn->car == &scm_label)
 385     return apply_env (caddr (fn), x, cons (cons (cadr (fn), caddr (fn)), a));
 386 #endif
 387   scm *efn = builtin_eval (fn, a);
 388   if (efn == &scm_f || efn == &scm_t) assert (!"apply bool");
 389   if (efn->type == NUMBER) assert (!"apply number");
 390   if (efn->type == STRING) assert (!"apply string");
 391   if (efn == &scm_unspecified) assert (!"apply *unspecified*");
 392   return apply_env (efn, x, a);
 393 }
 394
 395 scm *
 396 builtin_eval (scm *e, scm *a)
 397 {
 398   if (builtin_p (e) == &scm_t) return e;
 399   if (e->type == SCM) return e;
 400
 401   e = expand_macro_env (e, a);
 402
 403   if (e->type == SYMBOL) {
 404     scm *y = assq_ref_cache (e, a);
 405     if (y == &scm_undefined) {
 406       fprintf (stderr, "eval: unbound variable:");
 407       display_ (stderr, e);
 408       fprintf (stderr, "\n");
 409       assert (!"unbound variable");
 410     }
 411     return y;
 412   }
 413   else if (e->type != PAIR)
 414     return e;
 415   else if (e->car->type != PAIR)
 416     {
 417       if (e->car->type == STRING && string_to_symbol (e->car) == &symbol_noexpand)
 418         e = cadr (e);
 419       else
 420         e = sc_expand_env (e, a);
 421       if (e->car == &symbol_quote)
 422         return cadr (e);
 423 #if QUASISYNTAX
 424       if (e->car == &symbol_syntax)
 425         return e;
 426 #endif
 427       if (e->car == &symbol_begin)
 428         return begin_env (e, a);
 429       if (e->car == &symbol_lambda)
 430         return make_closure (cadr (e), cddr (e), assq (&scm_closure, a));
 431       if (e->car == &scm_closure)
 432         return e;
 433       if (e->car == &symbol_if)
 434         return builtin_if (cdr (e), a);
 435 #if !BOOT
 436       if (e->car == &symbol_define)
 437         return define_env (e, a);
 438       if (e->car == &symbol_define_macro)
 439         return define_env (e, a);
 440 #else
 441       if (e->car == &symbol_define) {
 442         fprintf (stderr, "C DEFINE: ");
 443         display_ (stderr,
 444                   e->cdr->car->type == SYMBOL
 445                   ? e->cdr->car->string
 446                   : e->cdr->car->car->string);
 447         fprintf (stderr, "\n");
 448       }
 449       assert (e->car != &symbol_define);
 450       assert (e->car != &symbol_define_macro);
 451 #endif
 452       if (e->car == &symbol_set_x)
 453         return set_env_x (cadr (e), builtin_eval (caddr (e), a), a);
 454 #if QUASIQUOTE
 455       if (e->car == &symbol_unquote)
 456         return builtin_eval (cadr (e), a);
 457       if (e->car == &symbol_quasiquote)
 458         return eval_quasiquote (cadr (e), add_unquoters (a));
 459 #endif //QUASIQUOTE
 460 #if QUASISYNTAX
 461       if (e->car == &symbol_unsyntax)
 462         return builtin_eval (cadr (e), a);
 463       if (e->car == &symbol_quasisyntax)
 464         return eval_quasisyntax (cadr (e), add_unsyntaxers (a));
 465 #endif //QUASISYNTAX
 466     }
 467   return apply_env (e->car, evlis_env (e->cdr, a), a);
 468 }
 469
 470 scm *
 471 expand_macro_env (scm *e, scm *a)
 472 {
 473   scm *macro;
 474   if (e->type == PAIR
 475       && (macro = lookup_macro (e->car, a)) != &scm_f)
 476     return expand_macro_env (apply_env (macro, e->cdr, a), a);
 477   return e;
 478 }
 479
 480 scm *
 481 sc_expand_env (scm *e, scm *a)
 482 {
 483   scm *expanders;
 484   scm *macro;
 485   if (e->type == PAIR
 486     && car (e)->type == SYMBOL
 487
 488     && car (e) != &symbol_lambda
 489     && car (e) != &symbol_set_x
 490     && car (e) != &symbol_if
 491     && car (e) != &symbol_begin
 492     && car (e) != &symbol_define
 493
 494     && car (e) != &symbol_quasiquote
 495     && car (e) != &symbol_quote
 496     && car (e) != &symbol_unquote
 497     && car (e) != &symbol_unquote_splicing
 498     && ((expanders = assq_ref_cache (&symbol_sc_expander_alist, a)) != &scm_undefined)
 499     && ((macro = assq (car (e), expanders)) != &scm_f))
 500     {
 501       scm *sc_expand = assq_ref_cache (&symbol_expand_macro, a);
 502       if (sc_expand != &scm_undefined && sc_expand != &scm_f)
 503         {
 504           e = apply_env (sc_expand, cons (e, &scm_nil), a);
 505           return expand_macro_env (e, a);
 506         }
 507     }
 508   return e;
 509 }
 510
 511 scm *
 512 begin_env (scm *e, scm *a)
 513 {
 514   scm *r = &scm_unspecified;
 515   while (e != &scm_nil) {
 516     r = builtin_eval (e->car, a);
 517     e = e->cdr;
 518   }
 519   return r;
 520 }
 521
 522 scm *
 523 builtin_if (scm *e, scm *a)
 524 {
 525   if (builtin_eval (car (e), a) != &scm_f)
 526     return builtin_eval (cadr (e), a);
 527   if (cddr (e) != &scm_nil)
 528     return builtin_eval (caddr (e), a);
 529   return &scm_unspecified;
 530 }
 531
 532 //Helpers
 533
 534 scm *
 535 display (scm *x) ///((args . n))
 536 {
 537   scm *e = car (x);
 538   scm *p = cdr (x);
 539   int fd = 1;
 540   if (p->type == PAIR && p->car->type == NUMBER) fd = p->car->hits;
 541   FILE *f = fd == 1 ? stdout : stderr;
 542   return display_helper (f, e, false, "", false);
 543 }
 544
 545 scm *
 546 display_ (FILE* f, scm *x)
 547 {
 548   return display_helper (f, x, false, "", false);
 549 }
 550
 551 scm *
 552 call (scm *fn, scm *x)
 553 {
 554   if (fn->type == FUNCTION0)
 555     return fn->function0 ();
 556   if (x != &scm_nil && x->car->type == VALUES)
 557     x = cons (x->car->cdr->car, x->cdr);
 558   if (fn->type == FUNCTION1)
 559     return fn->function1 (car (x));
 560   if (x != &scm_nil && x->cdr->car->type == VALUES)
 561     x = cons (x->car, cons (x->cdr->car->cdr->car, x->cdr));
 562   if (fn->type == FUNCTION2)
 563     return fn->function2 (car (x), cadr (x));
 564   if (fn->type == FUNCTION3)
 565     return fn->function3 (car (x), cadr (x), caddr (x));
 566   if (fn->type == FUNCTIONn)
 567     return fn->functionn (x);
 568   return &scm_unspecified;
 569 }
 570
 571 scm *
 572 append2 (scm *x, scm *y)
 573 {
 574   if (x == &scm_nil) return y;
 575   assert (x->type == PAIR);
 576   return cons (car (x), append2 (cdr (x), y));
 577 }
 578
 579 scm *
 580 append (scm *x) ///((args . n))
 581  {
 582   if (x == &scm_nil) return &scm_nil;
 583   return append2 (car (x), append (cdr (x)));
 584  }
 585
 586 scm *
 587 make_char (int x)
 588 {
 589   scm t = {NUMBER, .value=CHAR};
 590   scm n = {NUMBER, .value=x};
 591   return make_cell (&t, &n, &n);
 592 }
 593
 594 scm *
 595 make_macro (scm *name, scm *x)
 596 {
 597   scm t = {NUMBER, .value=MACRO};
 598   return make_cell (&t, name->string, x);
 599 }
 600
 601 scm *
 602 make_number (int x)
 603 {
 604   scm t = {NUMBER, .value=NUMBER};
 605   scm n = {NUMBER, .value=x};
 606   return make_cell (&t, &n, &n);
 607 }
 608
 609 scm *
 610 make_ref (scm *x)
 611 {
 612   scm t = {NUMBER, .value=REF};
 613   return make_cell (&t, x, x);
 614 }
 615
 616 scm *
 617 make_string (scm *x)
 618 {
 619   scm t = {NUMBER, .value=STRING};
 620   return make_cell (&t, x, 0);
 621 }
 622
 623 scm *
 624 cstring_to_list (char const* s)
 625 {
 626   scm *p = &scm_nil;
 627   while (s && *s)
 628     p = append2 (p, cons (make_char (*s++), &scm_nil));
 629   return p;
 630 }
 631
 632 scm *symbols = 0;
 633
 634 scm *
 635 list_of_char_equal_p (scm *a, scm *b)
 636 {
 637   while (a != &scm_nil && b != &scm_nil && a->car->value == b->car->value) {
 638     assert (a->car->type == CHAR);
 639     assert (b->car->type == CHAR);
 640     a = a->cdr;
 641     b = b->cdr;
 642   }
 643   return (a == &scm_nil && b == &scm_nil) ? &scm_t : &scm_f;
 644 }
 645
 646 scm *
 647 internal_lookup_symbol (scm *s)
 648 {
 649   scm *x = symbols;
 650   while (x) {
 651     // .string and .name is the same field; .name is used as a handy
 652     // static field initializer.  A string can only be mistaken for a
 653     // cell with type == PAIR for the one character long, zero-padded
 654     // #\etx.
 655     if (x->car->string->type != PAIR)
 656       x->car->string = cstring_to_list (x->car->name);
 657     if (list_of_char_equal_p (x->car->string, s) == &scm_t) break;
 658     x = x->cdr;
 659   }
 660   if (x) x = x->car;
 661   return x;
 662 }
 663
 664 scm *
 665 internal_make_symbol (scm *s)
 666 {
 667   scm t = {NUMBER, .value=SYMBOL};
 668   scm *x = make_cell (&t, s, 0);
 669   symbols = cons (x, symbols);
 670   return x;
 671 }
 672
 673 scm *
 674 make_symbol (scm *s)
 675 {
 676   scm *x = internal_lookup_symbol (s);
 677   return x ? x : internal_make_symbol (s);
 678 }
 679
 680 scm *
 681 make_vector (scm *n)
 682 {
 683   scm t = {NUMBER, .value=VECTOR};
 684   scm *v = alloc (n->value);
 685   scm *x = make_cell (&t, (scm*)(long)n->value, v);
 686   for (int i=0; i<n->value; i++) x->vector[i] = *vector_entry (&scm_unspecified);
 687   return x;
 688 }
 689
 690 scm *
 691 values (scm *x) ///((args . n))
 692 {
 693   scm *v = cons (0, x);
 694   v->type = VALUES;
 695   return v;
 696 }
 697
 698 scm *
 699 call_with_values_env (scm *producer, scm *consumer, scm *a)
 700 {
 701   scm *v = apply_env (producer, &scm_nil, a);
 702   if (v->type == VALUES)
 703     v = v->cdr;
 704   return apply_env (consumer, v, a);
 705 }
 706
 707 scm *
 708 vector_length (scm *x)
 709 {
 710   assert (x->type == VECTOR);
 711   return make_number (x->length);
 712 }
 713
 714 scm *
 715 vector_ref (scm *x, scm *i)
 716 {
 717   assert (x->type == VECTOR);
 718   assert (i->value < x->length);
 719   scm *e = &x->vector[i->value];
 720   if (e->type == REF) e = e->ref;
 721   if (e->type == CHAR) e = make_char (e->value);
 722   if (e->type == NUMBER) e = make_number (e->value);
 723   return e;
 724 }
 725
 726 scm *
 727 vector_entry (scm *x) {
 728   if (x->type == PAIR || x->type == SCM || x->type == STRING || x->type == SYMBOL || x->type == VECTOR) x = make_ref (x);
 729   return x;
 730 }
 731
 732 scm *
 733 vector_set_x (scm *x, scm *i, scm *e)
 734 {
 735   assert (x->type == VECTOR);
 736   assert (i->value < x->length);
 737   x->vector[i->value] = *vector_entry (e);
 738   return &scm_unspecified;
 739 }
 740
 741 scm *
 742 lookup (scm *s, scm *a)
 743 {
 744   if (isdigit (s->car->value) || (s->car->value == '-' && s->cdr != &scm_nil)) {
 745     scm *p = s;
 746     int sign = 1;
 747     if (s->car->value == '-') {
 748       sign = -1;
 749       p = s->cdr;
 750     }
 751     int n = 0;
 752     while (p != &scm_nil && isdigit (p->car->value)) {
 753       n *= 10;
 754       n += p->car->value - '0';
 755       p = p->cdr;
 756     }
 757     if (p == &scm_nil) return make_number (n * sign);
 758   }
 759
 760   scm *x = internal_lookup_symbol (s);
 761   if (x) return x;
 762
 763   if (s->cdr == &scm_nil) {
 764     if (s->car->value == '\'') return &symbol_quote;
 765     if (s->car->value == '`') return &symbol_quasiquote;
 766     if (s->car->value == ',') return &symbol_unquote;
 767   }
 768   else if (s->cdr->cdr == &scm_nil) {
 769     if (s->car->value == ',' && s->cdr->car->value == '@') return &symbol_unquote_splicing;
 770     if (s->car->value == '#' && s->cdr->car->value == '\'') return &symbol_syntax;
 771     if (s->car->value == '#' && s->cdr->car->value == '`') return &symbol_quasisyntax;
 772     if (s->car->value == '#' && s->cdr->car->value == ',') return &symbol_unsyntax;
 773   }
 774   else if (s->cdr->cdr->cdr == &scm_nil) {
 775     if (s->car->value == '#' && s->cdr->car->value == ',' && s->cdr->cdr->car->value == '@') return &symbol_unsyntax_splicing;
 776     if (s->car->value == 'E' && s->cdr->car->value == 'O' && s->cdr->cdr->car->value == 'F') {
 777       fprintf (stderr, "mes: got EOF\n");
 778       return &scm_nil; // `EOF': eval program, which may read stdin
 779     }
 780   }
 781
 782   return internal_make_symbol (s);
 783 }
 784
 785 scm *
 786 lookup_char (int c, scm *a)
 787 {
 788   return lookup (cons (make_char (c), &scm_nil), a);
 789 }
 790
 791 scm *
 792 list_to_vector (scm *x)
 793 {
 794   scm n = {NUMBER, .value=length (x)->value};
 795   scm *v = make_vector (&n);
 796   scm *p = v->vector;
 797   while (x != &scm_nil)
 798     {
 799       *p++ = *vector_entry (car (x));
 800       x = cdr (x);
 801     }
 802   return v;
 803 }
 804
 805 scm *
 806 newline (scm *p) ///((args . n))
 807 {
 808   int fd = 1;
 809   if (p->type == PAIR && p->car->type == NUMBER) fd = p->car->value;
 810   FILE *f = fd == 1 ? stdout : stderr;
 811   fputs ("\n", f);
 812   return &scm_unspecified;
 813 }
 814
 815 scm *
 816 force_output (scm *p) ///((args . n))
 817 {
 818   int fd = 1;
 819   if (p->type == PAIR && p->car->type == NUMBER) fd = p->car->value;
 820   FILE *f = fd == 1 ? stdout : stderr;
 821   fflush (f);
 822 }
 823
 824 scm *
 825 display_helper (FILE* f, scm *x, bool cont, char const *sep, bool quote)
 826 {
 827   scm *r;
 828   fprintf (f, "%s", sep);
 829   if (x->type == CHAR && x->value == char_nul.value) fprintf (f, "#\\%s", char_nul.name);
 830   else if (x->type == CHAR && x->value == char_backspace.value) fprintf (f, "#\\%s", char_backspace.name);
 831   else if (x->type == CHAR && x->value == char_tab.value) fprintf (f, "#\\%s", char_tab.name);
 832   else if (x->type == CHAR && x->value == char_newline.value) fprintf (f, "#\\%s", char_newline.name);
 833   else if (x->type == CHAR && x->value == char_vt.value) fprintf (f, "#\\%s", char_vt.name);
 834   else if (x->type == CHAR && x->value == char_page.value) fprintf (f, "#\\%s", char_page.name);
 835   else if (x->type == CHAR && x->value == char_return.value) fprintf (f, "#\\%s", char_return.name);
 836   else if (x->type == CHAR && x->value == char_space.value) fprintf (f, "#\\%s", char_space.name);
 837   else if (x->type == CHAR) fprintf (f, "#\\%c", x->value);
 838   else if (x->type == MACRO) {
 839     fprintf (f, "(*macro* ");
 840     display_helper (f, x->macro, cont, sep, quote);
 841     fprintf (f, ")");
 842   }
 843   else if (x->type == NUMBER) fprintf (f, "%d", x->value);
 844   else if (x->type == PAIR) {
 845     if (car (x) == &scm_circular) {
 846       fprintf (f, "(*circ* . #-1#)");
 847       return &scm_unspecified;
 848     }
 849     if (car (x) == &scm_closure) {
 850       fprintf (f, "(*closure* . #-1#)");
 851       return &scm_unspecified;
 852     }
 853     if (car (x) == &scm_quote) {
 854       fprintf (f, "'");
 855       return display_helper (f, car (cdr (x)), cont, "", true);
 856     }
 857     if (!cont) fprintf (f, "(");
 858     display_ (f, car (x));
 859     if (cdr (x)->type == PAIR)
 860       display_helper (f, cdr (x), true, " ", false);
 861     else if (cdr (x) != &scm_nil) {
 862       fprintf (f, " . ");
 863       display_ (f, cdr (x));
 864     }
 865     if (!cont) fprintf (f, ")");
 866   }
 867   else if (x->type == VECTOR) {
 868     fprintf (f, "#(", x->length);
 869     for (int i = 0; i < x->length; i++) {
 870       if (x->vector[i].type == VECTOR
 871           || (x->vector[i].type == REF
 872               && x->vector[i].ref->type == VECTOR))
 873         fprintf (f, "%s#(...)", i ? " " : "");
 874       else
 875         display_helper (f, &x->vector[i], false, i ? " " : "", false);
 876     }
 877     fprintf (f, ")");
 878   }
 879   else if (x->type == REF) display_helper (f, x->ref, cont, "", true);
 880   else if (builtin_p (x) == &scm_t) fprintf (f, "#<procedure %s>", x->name);
 881   else if (x->type != PAIR && x->string) {
 882     scm *p = x->string;
 883     assert (p);
 884     while (p != &scm_nil) {
 885       assert (p->car->type == CHAR);
 886       fputc (p->car->value, f);
 887       p = p->cdr;
 888     }
 889   }
 890   else if (x->type != PAIR && x->name) fprintf (f, "%s", x->name);
 891
 892   return &scm_unspecified;
 893 }
 894
 895 // READ
 896
 897 FILE *g_stdin;
 898 int
 899 getchar ()
 900 {
 901   return getc (g_stdin);
 902 }
 903
 904 int
 905 ungetchar (int c)
 906 {
 907   return ungetc (c, g_stdin);
 908 }
 909
 910 int
 911 peekchar ()
 912 {
 913   int c = getchar ();
 914   ungetchar (c);
 915   return c;
 916 }
 917
 918 scm *
 919 peek_char ()
 920 {
 921   return make_char (peekchar ());
 922 }
 923
 924 scm *
 925 read_char ()
 926 {
 927   return make_char (getchar ());
 928 }
 929
 930 scm *
 931 write_char (scm *x) ///((args . n))
 932 {
 933   scm *c = car (x);
 934   scm *p = cdr (x);
 935   int fd = 1;
 936   if (p->type == PAIR && p->car->type == NUMBER) fd = p->car->value;
 937   FILE *f = fd == 1 ? stdout : stderr;
 938   assert (c->type == NUMBER || c->type == CHAR);
 939   fputc (c->value, f);
 940   return c;
 941 }
 942
 943 scm *
 944 unget_char (scm *c)
 945 {
 946   assert (c->type == NUMBER || c->type == CHAR);
 947   ungetchar (c->value);
 948   return c;
 949 }
 950
 951 int
 952 readcomment (int c)
 953 {
 954   if (c == '\n') return c;
 955   return readcomment (getchar ());
 956 }
 957
 958 int
 959 readblock (int c)
 960 {
 961   if (c == '!' && peekchar () == '#') return getchar ();
 962   return readblock (getchar ());
 963 }
 964
 965 scm *
 966 readword (int c, scm *w, scm *a)
 967 {
 968   if (c == EOF && w == &scm_nil) return &scm_nil;
 969   if (c == '\n' && w == &scm_nil) return readword (getchar (), w, a);
 970   if (c == '\n' && w->car->value == '.' && w->cdr == &scm_nil) return &scm_dot;
 971   if (c == EOF || c == '\n') return lookup (w, a);
 972   if (c == ' ') return readword ('\n', w, a);
 973   if (c == '"' && w == &scm_nil) return readstring ();
 974   if (c == '"') {ungetchar (c); return lookup (w, a);}
 975   if (c == '(' && w == &scm_nil) return readlist (a);
 976   if (c == '(') {ungetchar (c); return lookup (w, a);}
 977   if (c == ')' && w == &scm_nil) {ungetchar (c); return &scm_nil;}
 978   if (c == ')') {ungetchar (c); return lookup (w, a);}
 979   if (c == ',' && peekchar () == '@') {getchar (); return cons (lookup (symbol_unquote_splicing.string, a),
 980                                                                    cons (readword (getchar (), w, a),
 981                                                                          &scm_nil));}
 982   if ((c == '\''
 983        || c == '`'
 984        || c == ',')
 985       && w == &scm_nil) {return cons (lookup_char (c, a),
 986                                      cons (readword (getchar (), w, a),
 987                                            &scm_nil));}
 988   if (c == '#' && peekchar () == ',' && w == &scm_nil) {
 989     getchar ();
 990     if (peekchar () == '@'){getchar (); return cons (lookup (symbol_unsyntax_splicing.string, a),
 991                                                      cons (readword (getchar (), w, a),
 992                                                            &scm_nil));}
 993     return cons (lookup (symbol_unsyntax.string, a), cons (readword (getchar (), w, a), &scm_nil));
 994   }
 995   if (c == '#' && (peekchar () == '\'' || peekchar () == '`') && w == &scm_nil) {
 996     c = getchar ();
 997     return cons (lookup (cons (make_char ('#'), cons (make_char (c), &scm_nil)), a),
 998                  cons (readword (getchar (), w, a), &scm_nil));}
 999   if (c == ';') {readcomment (c); return readword ('\n', w, a);}
1000   if (c == '#' && peekchar () == 'x') {getchar (); return read_hex ();}
1001   if (c == '#' && peekchar () == '\\') {getchar (); return read_character ();}
1002   if (c == '#' && w == &scm_nil && peekchar () == '(') {getchar (); return list_to_vector (readlist (a));}
1003   if (c == '#' && peekchar () == '(') {ungetchar (c); return lookup (w, a);}
1004   if (c == '#' && peekchar () == '!') {getchar (); readblock (getchar ()); return readword (getchar (), w, a);}
1005   return readword (getchar (), append2 (w, cons (make_char (c), &scm_nil)), a);
1006 }
1007
1008 scm *
1009 read_hex ()
1010 {
1011   int n = 0;
1012   int c = peekchar ();
1013   while ((c >= '0' && c <= '9')
1014          || (c >= 'A' && c <= 'F')
1015          || (c >= 'a' && c <= 'f')) {
1016     n <<= 4;
1017     if (c >= 'a') n += c - 'a' + 10;
1018     else if (c >= 'A') n += c - 'A' + 10;
1019     else n+= c - '0';
1020     getchar ();
1021     c = peekchar ();
1022   }
1023   return make_number (n);
1024 }
1025
1026 scm *
1027 read_character ()
1028 {
1029   int c = getchar ();
1030   if (c >= '0' && c <= '7'
1031       && peekchar () >= '0' && peekchar () <= '7') {
1032     c = c - '0';
1033     while (peekchar () >= '0' && peekchar () <= '7') {
1034       c <<= 3;
1035       c += getchar () - '0';
1036     }
1037   }
1038   else if (c >= 'a' && c <= 'z'
1039       && peekchar () >= 'a' && peekchar () <= 'z') {
1040     char buf[10];
1041     char *p = buf;
1042     *p++ = c;
1043     while (peekchar () >= 'a' && peekchar () <= 'z') {
1044       *p++ = getchar ();
1045     }
1046     *p = 0;
1047     if (!strcmp (buf, char_nul.name)) c = char_nul.value;
1048     else if (!strcmp (buf, char_backspace.name)) c = char_backspace.value;
1049     else if (!strcmp (buf, char_tab.name)) c = char_tab.value;
1050     else if (!strcmp (buf, char_newline.name)) c = char_newline.value;
1051     else if (!strcmp (buf, char_vt.name)) c = char_vt.value;
1052     else if (!strcmp (buf, char_page.name)) c = char_page.value;
1053     else if (!strcmp (buf, char_return.name)) c = char_return.value;
1054     else if (!strcmp (buf, char_space.name)) c = char_space.value;
1055     else {
1056       fprintf (stderr, "char not supported: %s\n", buf);
1057       assert (!"char not supported");
1058     }
1059   }
1060   return make_char (c);
1061 }
1062
1063 scm *
1064 append_char (scm *x, int i)
1065 {
1066   return append2 (x, cons (make_char (i), &scm_nil));
1067 }
1068
1069 scm *
1070 readstring ()
1071 {
1072   scm *p = &scm_nil;
1073   int c = getchar ();
1074   while (true) {
1075     if (c == '"') break;
1076     if (c == '\\' && peekchar () == '"') p = append_char (p, getchar ());
1077     else if (c == '\\' && peekchar () == 'n') {getchar (); p = append_char (p, '\n');}
1078     else if (c == EOF) assert (!"EOF in string");
1079     else p = append_char (p, c);
1080     c = getchar ();
1081   }
1082   return make_string (p);
1083 }
1084
1085 int
1086 eat_whitespace (int c)
1087 {
1088   while (c == ' ' || c == '\t' || c == '\n') c = getchar ();
1089   if (c == ';') return eat_whitespace (readcomment (c));
1090   if (c == '#' && peekchar () == '!') {getchar (); readblock (getchar ()); return eat_whitespace (getchar ());}
1091   return c;
1092 }
1093
1094 scm *
1095 readlist (scm *a)
1096 {
1097   int c = getchar ();
1098   c = eat_whitespace (c);
1099   if (c == ')') return &scm_nil;
1100   scm *w = readword (c, &scm_nil, a);
1101   if (w == &scm_dot)
1102     return car (readlist (a));
1103   return cons (w, readlist (a));
1104 }
1105
1106 scm *
1107 read_env (scm *a)
1108 {
1109   return readword (getchar (), &scm_nil, a);
1110 }
1111
1112 scm *
1113 add_environment (scm *a, char const *name, scm *x)
1114 {
1115   return cons (cons (make_symbol (cstring_to_list (name)), x), a);
1116 }
1117
1118 scm *
1119 mes_environment () ///((internal))
1120 {
1121   scm *a = &scm_nil;
1122
1123   #include "mes.symbols.i"
1124
1125 #if BOOT
1126   symbols = cons (&scm_label, symbols);
1127   a = cons (cons (&scm_label, &scm_t), a);
1128 #endif
1129   a = cons (cons (&symbol_begin, &scm_begin), a);
1130
1131 #include "posix.environment.i"
1132 #include "string.environment.i"
1133 #include "math.environment.i"
1134 #include "lib.environment.i"
1135 #include "mes.environment.i"
1136 //#include "quasiquote.environment.i"
1137 #include "define.environment.i"
1138 #include "type.environment.i"
1139
1140   a = add_environment (a, "sc-expand", &scm_f);
1141
1142   a = cons (cons (&scm_closure, a), a);
1143   return a;
1144 }
1145
1146 scm *
1147 make_lambda (scm *args, scm *body)
1148 {
1149   return cons (&symbol_lambda, cons (args, body));
1150 }
1151
1152 scm *
1153 make_closure (scm *args, scm *body, scm *a)
1154 {
1155   return cons (&scm_closure, cons (cons (&scm_circular, a), cons (args, body)));
1156 }
1157
1158 scm *
1159 lookup_macro (scm *x, scm *a)
1160 {
1161   if (x->type != SYMBOL) return &scm_f;
1162   scm *m = assq_ref_cache (x, a);
1163   if (macro_p (m) == &scm_t) return m->macro;
1164   return &scm_f;
1165 }
1166
1167 scm *
1168 read_input_file_env (scm *e, scm *a)
1169 {
1170   if (e == &scm_nil) return e;
1171   return cons (e, read_input_file_env (read_env (a), a));
1172 }
1173
1174 scm *
1175 load_env (scm *a)
1176 {
1177   return begin_env (read_input_file_env (read_env (a), a), a);
1178 }
1179
1180 #include "type.c"
1181 #include "define.c"
1182 #include "lib.c"
1183 #include "math.c"
1184 #include "posix.c"
1185 #include "quasiquote.c"
1186 #include "string.c"
1187
1188 int
1189 main (int argc, char *argv[])
1190 {
1191   if (argc > 1 && !strcmp (argv[1], "--help")) return puts ("Usage: mes < FILE\n");
1192   if (argc > 1 && !strcmp (argv[1], "--version")) return puts ("Mes 0.1\n");
1193   g_stdin = stdin;
1194   scm *a = mes_environment ();
1195   display_ (stderr, load_env (a));
1196   fputs ("", stderr);
1197   return 0;
1198 }