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