2 * Mes --- Maxwell Equations of Software
3 * Copyright © 2016 Jan Nieuwenhuizen <janneke@gnu.org>
5 * This file is part of Mes.
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.
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.
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/>.
21 // (setq comment-start "//")
22 // (setq comment-end "")
24 * The Maxwell Equations of Software -- John McCarthy page 13
25 * http://www.softwarepreservation.org/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf
45 enum type {CHAR, NUMBER, PAIR, STRING, SYMBOL, VALUES, VECTOR,
46 FUNCTION0, FUNCTION1, FUNCTION2, FUNCTION3, FUNCTIONn};
48 typedef struct scm_t* (*function0_t) (void);
49 typedef struct scm_t* (*function1_t) (struct scm_t*);
50 typedef struct scm_t* (*function2_t) (struct scm_t*, struct scm_t*);
51 typedef struct scm_t* (*function3_t) (struct scm_t*, struct scm_t*, struct scm_t*);
52 typedef struct scm_t* (*functionn_t) (struct scm_t*);
54 typedef struct scm_t {
63 function0_t function0;
64 function1_t function1;
65 function2_t function2;
66 function3_t function3;
67 functionn_t functionn;
69 struct scm_t** vector;
76 scm *display_helper (scm*, bool, char*, bool);
78 symbol_eq (scm *x, char *s)
80 return x->type == SYMBOL && !strcmp (x->name, s);
83 scm scm_nil = {SYMBOL, "()"};
84 scm scm_dot = {SYMBOL, "."};
85 scm scm_t = {SYMBOL, "#t"};
86 scm scm_f = {SYMBOL, "#f"};
87 scm scm_lambda = {SYMBOL, "lambda"};
88 scm scm_label = {SYMBOL, "label"};
89 scm scm_unspecified = {SYMBOL, "*unspecified*"};
90 scm scm_symbol_cond = {SYMBOL, "cond"};
91 scm scm_symbol_quote = {SYMBOL, "quote"};
93 scm scm_symbol_quasiquote = {SYMBOL, "quasiquote"};
94 scm scm_symbol_unquote = {SYMBOL, "unquote"};
97 scm scm_macro = {SYMBOL, "*macro*"};
100 scm scm_symbol_EOF = {SYMBOL, "EOF"};
101 scm scm_symbol_EOF2 = {SYMBOL, "EOF2"};
102 scm scm_symbol_call_with_values = {SYMBOL, "call-with-values"};
103 scm scm_symbol_current_module = {SYMBOL, "current-module"};
104 scm scm_symbol_define = {SYMBOL, "define"};
105 scm scm_symbol_define_macro = {SYMBOL, "define-macro"};
106 scm scm_symbol_eval = {SYMBOL, "eval"};
107 scm scm_symbol_loop2 = {SYMBOL, "loop2"};
108 scm scm_symbol_set_x = {SYMBOL, "set!"};
109 scm scm_symbol_values = {SYMBOL, "values"};
116 return x->type == PAIR ? &scm_f : &scm_t;
122 assert (x->type == PAIR);
129 assert (x->type == PAIR);
134 cons (scm *x, scm *y)
136 scm *p = malloc (sizeof (scm));
144 eq_p (scm *x, scm *y)
147 || (x->type == CHAR && y->type == CHAR
148 && x->value == y->value)
149 || (x->type == NUMBER && y->type == NUMBER
150 && x->value == y->value)
151 // FIXME: alist lookup symbols
152 || (atom_p (x) == &scm_t
159 && atom_p (y) == &scm_t
160 && !strcmp (x->name, y->name)))
167 return eq_p (x, &scm_nil);
173 return x->type == PAIR ? &scm_t : &scm_f;
177 set_cdr_x (scm *x, scm *e)
179 assert (x->type == PAIR);
181 return &scm_unspecified;
185 set_x (scm *x, scm *e, scm *a)
187 return set_cdr_x (assq (x, a), e);
191 set_env_x (scm *x, scm *e, scm *a)
193 return set_cdr_x (assq (x, a), e);
199 return cons (&scm_symbol_quote, x);
206 return cons (&scm_symbol_unquote, x);
212 return cons (&scm_symbol_quasiquote, x);
218 // Derived, non-primitives
219 scm *caar (scm *x) {return car (car (x));}
220 scm *cadr (scm *x) {return car (cdr (x));}
221 scm *cdar (scm *x) {return cdr (car (x));}
222 scm *cddr (scm *x) {return cdr (cdr (x));}
223 scm *caadr (scm *x) {return car (car (cdr (x)));}
224 scm *caddr (scm *x) {return car (cdr (cdr (x)));}
225 scm *cdadr (scm *x) {return cdr (car (cdr (x)));}
226 scm *cadar (scm *x) {return car (cdr (car (x)));}
227 scm *cddar (scm *x) {return cdr (cdr (car (x)));}
228 scm *cdddr (scm *x) {return cdr (cdr (cdr (x)));}
231 pairlis (scm *x, scm *y, scm *a)
234 printf ("pairlis x=");
242 if (atom_p (x) == &scm_t)
243 return cons (cons (x, y), a);
244 return cons (cons (car (x), car (y)),
245 pairlis (cdr (x), cdr (y), a));
249 assq (scm *x, scm *a)
253 printf ("alist miss: %s\n", x->name);
257 if (eq_p (caar (a), x) == &scm_t)
259 return assq (x, cdr (a));
263 apply_env_ (scm *fn, scm *x, scm *a)
266 printf ("apply_env fn=");
272 if (atom_p (fn) != &scm_f)
274 if (fn == &scm_symbol_current_module) // FIXME
276 if (eq_p (fn, &scm_symbol_call_with_values) == &scm_t)
277 return call (&scm_call_with_values_env, append2 (x, cons (a, &scm_nil)));
278 if (builtin_p (fn) == &scm_t)
280 return apply_env (eval (fn, a), x, a);
282 else if (car (fn) == &scm_lambda)
283 return begin_env (cddr (fn), pairlis (cadr (fn), x, a));
284 else if (car (fn) == &scm_label)
285 return apply_env (caddr (fn), x, cons (cons (cadr (fn), caddr (fn)), a));
286 return &scm_unspecified;
290 begin_env (scm *body, scm *a)
292 if (body == &scm_nil) return &scm_unspecified;
293 scm *result = eval (car (body), a);
294 if (cdr (body) == &scm_nil)
296 return begin_env (cdr (body), a);
300 eval_ (scm *e, scm *a)
309 else if (e->type == NUMBER)
311 else if (e->type == STRING)
313 else if (e->type == VECTOR)
315 else if (atom_p (e) == &scm_t) {
316 scm *y = assq (e, a);
318 printf ("eval: no such symbol: %s\n", e->name);
323 if (builtin_p (e) == &scm_t)
325 else if (atom_p (car (e)) == &scm_t)
330 if (car (e) == &scm_symbol_quote)
332 if (car (e) == &scm_lambda)
334 if (car (e) == &scm_symbol_set_x)
335 return set_env_x (cadr (e), eval (caddr (e), a), a);
337 else if (car (e) == &scm_symbol_unquote)
338 return eval (cadr (e), a);
339 else if (car (e) == &scm_symbol_quasiquote) {
345 display (eval_quasiquote (cadr (e), a));
348 return eval_quasiquote (cadr (e), a);
351 else if (car (e) == &scm_symbol_cond)
352 return evcon (cdr (e), a);
354 else if ((macro = assq (car (e), cdr (assq (&scm_macro, a)))) != &scm_f)
355 return eval (apply_env_ (cdr (macro), cdr (e), a), a);
357 return apply_env (car (e), evlis (cdr (e), a), a);
359 return apply_env (car (e), evlis (cdr (e), a), a);
363 evcon_ (scm *c, scm *a)
366 printf ("evcon_ clause=");
370 if (c == &scm_nil) return &scm_unspecified;
371 if (eval (caar (c), a) != &scm_f) {
373 //if (fn != &scm_display && fn != &scm_call)
374 //if (fn != &scm_call)
375 printf ("#t clause=");
379 printf (" nil=%d", cddar (c) == &scm_nil);
382 if (cddar (c) == &scm_nil)
383 return eval (cadar (c), a);
385 return evcon_ (cons (cons (&scm_t, cddar (c)), &scm_nil), a);
387 return evcon_ (cdr (c), a);
391 evcon (scm *c, scm *a)
394 printf ("\n****evcon=");
398 return evcon_ (c, a);
402 evlis (scm *m, scm *a)
411 scm *e = eval (car (m), a);
412 return cons (e, evlis (cdr (m), a));
420 return (x->type == FUNCTION0
421 || x->type == FUNCTION1
422 || x->type == FUNCTION2
423 || x->type == FUNCTION3
424 || x->type == FUNCTIONn)
431 return x->type == CHAR ? &scm_t : &scm_f;
437 return x->type == NUMBER ? &scm_t : &scm_f;
443 return x->type == STRING ? &scm_t : &scm_f;
449 //TODO: #f,#t,nil also `symbols' atm
450 return x->type == SYMBOL ? &scm_t : &scm_f;
456 return x->type == VECTOR ? &scm_t : &scm_f;
462 return display_helper (x, false, "", false);
466 call (scm *fn, scm *x)
469 //if (fn != &scm_display && fn != &scm_call)
470 //if (fn != &scm_call)
472 printf ("\ncall fn=");
479 if (fn->type == FUNCTION0)
480 return fn->function0 ();
481 if (x->car->type == VALUES)
482 x = cons (x->car->cdr->car, &scm_nil);
483 if (fn->type == FUNCTION1)
484 return fn->function1 (car (x));
485 if (fn->type == FUNCTION2)
486 return fn->function2 (car (x), cadr (x));
487 if (fn->type == FUNCTION3)
488 return fn->function3 (car (x), cadr (x), caddr (x));
489 if (fn->type == FUNCTIONn)
490 return fn->functionn (x);
491 return &scm_unspecified;
495 append2 (scm *x, scm *y)
497 if (x == &scm_nil) return y;
498 assert (x->type == PAIR);
499 return cons (car (x), append2 (cdr (x), y));
503 append (scm *x/*...*/)
505 if (x == &scm_nil) return &scm_nil;
506 return append2 (car (x), append (cdr (x)));
512 scm *p = malloc (sizeof (scm));
521 scm *p = malloc (sizeof (scm));
528 make_string (char const *s)
530 scm *p = malloc (sizeof (scm));
532 p->name = strdup (s);
537 make_symbol (char const *s)
539 // TODO: alist lookup symbols
540 scm *p = malloc (sizeof (scm));
542 p->name = strdup (s);
549 scm *p = malloc (sizeof (scm));
552 p->vector = malloc (n * sizeof (scm*));
557 string (scm *x/*...*/)
561 while (x != &scm_nil)
564 assert (s->type == CHAR);
568 return make_string (buf);
572 string_append (scm *x/*...*/)
576 while (x != &scm_nil)
579 assert (s->type == STRING);
580 strcat (buf, s->name);
583 return make_string (buf);
587 string_length (scm *x)
589 assert (x->type == STRING);
590 return make_number (strlen (x->name));
597 while (x != &scm_nil)
602 return make_number (n);
607 builtin_list (scm *x/*...*/) // int
613 vector (scm *x/*...*/) // int
615 return list_to_vector (x);
620 values (scm *x/*...*/)
622 scm *v = cons (0, x);
628 call_with_values_env (scm *producer, scm *consumer, scm *a)
630 scm *v = apply_env_ (producer, &scm_nil, a);
631 if (v->type == VALUES)
633 return apply_env_ (consumer, v, a);
637 vector_length (scm *x)
639 assert (x->type == VECTOR);
640 return make_number (x->length);
644 vector_ref (scm *x, scm *i)
646 assert (x->type == VECTOR);
647 assert (i->value < x->length);
648 return x->vector[i->value];
652 vector_set_x (scm *x, scm *i, scm *e)
654 assert (x->type == VECTOR);
655 assert (i->value < x->length);
656 x->vector[i->value] = e;
657 return &scm_unspecified;
661 lookup (char *x, scm *a)
663 if (isdigit (*x) || (*x == '-' && isdigit (*(x+1))))
664 return make_number (atoi (x));
665 if (*x == '\'') return &scm_symbol_quote;
667 if (!strcmp (x, scm_unspecified.name)) return &scm_unspecified;
668 if (!strcmp (x, scm_symbol_cond.name)) return &scm_symbol_cond;
669 if (!strcmp (x, scm_symbol_quote.name)) return &scm_symbol_quote;
670 if (!strcmp (x, scm_lambda.name)) return &scm_lambda;
671 if (!strcmp (x, scm_label.name)) return &scm_label;
672 if (!strcmp (x, scm_nil.name)) return &scm_nil;
673 if (!strcmp (x, scm_symbol_set_x.name)) return &scm_symbol_set_x;
676 if (*x == '`') return &scm_symbol_quasiquote;
677 if (*x == ',') return &scm_symbol_unquote;
678 if (!strcmp (x, scm_symbol_unquote.name)) return &scm_symbol_unquote;
679 if (!strcmp (x, scm_symbol_quasiquote.name)) return &scm_symbol_quasiquote;
682 return make_symbol (x);
686 lookup_char (int c, scm *a)
691 return lookup (buf, a);
695 list2str (scm *l) // char*
697 static char buf[256];
699 while (l != &scm_nil) {
701 assert (c->type == NUMBER);
710 list_to_vector (scm *x)
712 int n = length (x)->value;
713 scm *v = make_vector (n);
715 while (x != &scm_nil)
724 number_to_string (scm *x)
726 assert (x->type == NUMBER);
728 sprintf (buf,"%d", x->value);
729 return make_string (buf);
733 string_to_symbol (scm *x)
735 assert (x->type == STRING);
736 return make_symbol (x->name);
740 symbol_to_string (scm *x)
742 assert (x->type == SYMBOL);
743 return make_string (x->name);
747 vector_to_list (scm *v)
750 for (int i = 0; i < v->length; i++)
751 x = append2 (x, cons (v->vector[i], &scm_nil));
756 builtin_lookup (scm *l, scm *a)
758 return lookup (list2str (l), a);
762 cossa (scm *x, scm *a)
764 if (a == &scm_nil) return &scm_f;
765 if (eq_p (cdar (a), x) == &scm_t)
767 return cossa (x, cdr (a));
774 return &scm_unspecified;
778 display_helper (scm *x, bool cont, char *sep, bool quote)
782 if (x->type == CHAR && x->value == 10) printf ("#\\%s", "newline");
783 else if (x->type == CHAR && x->value == 32) printf ("#\\%s", "space");
784 else if (x->type == CHAR) printf ("#\\%c", x->value);
785 else if (x->type == NUMBER) printf ("%d", x->value);
786 else if (x->type == PAIR) {
788 if (car (x) == &scm_quote) {
790 return display_helper (car (cdr (x)), cont, "", true);
793 if (car (x) == &scm_quasiquote) {
795 return display_helper (car (cdr (x)), cont, "", true);
797 if (car (x) == &scm_unquote) {
799 return display_helper (car (cdr (x)), cont, "", true);
803 if (!cont) printf ("(");
805 if (cdr (x)->type == PAIR)
806 display_helper (cdr (x), true, " ", false);
807 else if (cdr (x) != &scm_nil) {
811 if (!cont) printf (")");
813 else if (x->type == VECTOR) {
815 for (int i = 0; i < x->length; i++)
816 display_helper (x->vector[i], true, i ? " " : "", false);
819 else if (atom_p (x) == &scm_t) printf ("%s", x->name);
821 return &scm_unspecified;
827 ungetchar (int c) //int
829 return ungetc (c, stdin);
843 return make_number (getchar ());
849 return make_number (peekchar ());
853 builtin_ungetchar (scm *c)
855 assert (c->type == NUMBER);
856 ungetchar (c->value);
863 if (c == '\n') return c;
864 return readcomment (getchar ());
870 if (c == '!' && peekchar () == '#') return getchar ();
871 return readblock (getchar ());
875 readword (int c, char* w, scm *a)
877 if (c == EOF && !w) return &scm_nil;
878 if (c == '\n' && !w) return readword (getchar (), w, a);
879 if (c == '\n' && *w == '.' && w[1] == 0) return &scm_dot;
880 if (c == EOF || c == '\n') return lookup (w, a);
881 if (c == ' ') return readword ('\n', w, a);
882 if (c == '"' && !w) return readstring ();
883 if (c == '"') {ungetchar (c); return lookup (w, a);}
884 if (c == '(' && !w) return readlist (a);
885 if (c == '(') {ungetchar (c); return lookup (w, a);}
886 if (c == ')' && !w) {ungetchar (c); return &scm_nil;}
887 if (c == ')') {ungetchar (c); return lookup (w, a);}
894 && !w) {return cons (lookup_char (c, a),
895 cons (readword (getchar (), w, a),
897 if (c == ';') {readcomment (c); return readword ('\n', w, a);}
898 if (c == '#' && peekchar () == '\\') {getchar (); return readchar ();}
899 if (c == '#' && !w && peekchar () == '(') {getchar (); return list_to_vector (readlist (a));}
900 if (c == '#' && peekchar () == '(') {ungetchar (c); return lookup (w, a);}
901 if (c == '#' && peekchar () == '!') {getchar (); readblock (getchar ()); return readword (getchar (), w, a);}
904 return readword (getchar (), strncat (w ? w : buf, &ch, 1), a);
911 if (c >= '0' && c <= '7'
912 && peekchar () >= '0' && peekchar () <= '7') {
914 while (peekchar () >= '0' && peekchar () <= '7') {
916 c += getchar () - '0';
919 else if (c >= 'a' && c <= 'z'
920 && peekchar () >= 'a' && peekchar () <= 'z') {
924 while (peekchar () >= 'a' && peekchar () <= 'z') {
928 if (!strcmp (buf, "newline")) c = 10;
929 else if (!strcmp (buf, "space")) c = 32;
931 printf ("char not supported: %s", buf);
932 assert (!"char not supported");
935 return make_char (c);
947 if (c == '\\' && peekchar () == '"') *p++ = getchar ();
948 if (c == EOF) assert (!"EOF in string");
952 return make_string (buf);
956 eat_whitespace (int c)
958 while (c == ' ' || c == '\n') c = getchar ();
959 if (c == ';') return eat_whitespace (readcomment (c));
960 if (c == '#' && peekchar () == '!') {getchar (); readblock (getchar ()); return eat_whitespace (getchar ());}
968 c = eat_whitespace (c);
969 if (c == ')') return &scm_nil;
970 scm *w = readword (c, 0, a);
972 return car (readlist (a));
973 return cons (w, readlist (a));
979 return readword (getchar (), 0, a);
982 // Extras to make interesting program
987 puts ("c: hello world");
988 return &scm_unspecified;
992 less_p (scm *a, scm *b)
994 assert (a->type == NUMBER);
995 assert (b->type == NUMBER);
996 return a->value < b->value ? &scm_t : &scm_f;
1000 minus (scm *x/*...*/)
1003 assert (a->type == NUMBER);
1008 while (x != &scm_nil)
1010 assert (x->car->type == NUMBER);
1014 return make_number (n);
1018 plus (scm *x/*...*/)
1021 while (x != &scm_nil)
1023 assert (x->car->type == NUMBER);
1027 return make_number (n);
1031 divide (scm *x/*...*/)
1034 while (x != &scm_nil)
1036 assert (x->car->type == NUMBER);
1040 return make_number (n);
1044 multiply (scm *x/*...*/)
1047 while (x != &scm_nil)
1049 assert (x->car->type == NUMBER);
1053 return make_number (n);
1057 is_p (scm *a, scm *b)
1059 assert (a->type == NUMBER);
1060 assert (b->type == NUMBER);
1061 return a->value == b->value ? &scm_t : &scm_f;
1066 eval_quasiquote (scm *e, scm *a)
1069 printf ("\nc:eval_quasiquote e=");
1071 if (pair_p (e) == &scm_t) {
1072 printf ("\ncar (e)=");
1075 display (atom_p (car (e)));
1079 if (e == &scm_nil) return e;
1080 else if (atom_p (e) == &scm_t) return e;
1081 else if (atom_p (car (e)) == &scm_t)
1082 return cons (car (e), eval_quasiquote (cdr (e), a));
1083 else if (eq_p (caar (e), &scm_symbol_unquote) == &scm_t)
1084 return cons (eval (cadar (e), a), &scm_nil);
1085 else if (eq_p (caar (e), &scm_symbol_quote) == &scm_t)
1086 return cons (cadar (e), &scm_nil);
1087 else if (eq_p (caar (e), &scm_symbol_quasiquote) == &scm_t)
1089 return cons (car (e), eval_quasiquote (cdr (e), a));
1094 add_environment (scm *a, char *name, scm *x)
1096 return cons (cons (make_symbol (name), x), a);
1104 a = add_environment (a, "()", &scm_nil);
1105 a = add_environment (a, "#t", &scm_t);
1106 a = add_environment (a, "#f", &scm_f);
1107 a = add_environment (a, "*unspecified*", &scm_unspecified);
1108 a = add_environment (a, "label", &scm_label);
1109 a = add_environment (a, "lambda", &scm_lambda);
1110 a = add_environment (a, "*macro*", &scm_nil);
1111 a = add_environment (a, "*dot*", &scm_dot);
1112 a = add_environment (a, "current-module", &scm_symbol_current_module);
1114 a = add_environment (a, "'", &scm_quote);
1116 a = add_environment (a, ",", &scm_unquote);
1117 a = add_environment (a, "`", &scm_quasiquote);
1120 #include "environment.i"
1126 define_lambda (scm *x)
1128 return cons (caadr (x), cons (&scm_lambda, cons (cdadr (x), cddr (x))));
1132 define (scm *x, scm *a)
1134 if (atom_p (cadr (x)) != &scm_f)
1135 return cons (cadr (x), eval (caddr (x), a));
1136 return define_lambda (x);
1140 define_macro (scm *x, scm *a)
1143 printf ("\nc:define_macro a=");
1144 scm *aa =cons (&scm_macro,
1145 cons (define_lambda (x),
1146 cdr (assq (&scm_macro, a))));
1150 if (atom_p (cadr (x)) != &scm_f)
1151 return cons (&scm_macro,
1152 cons (cons (cadr (x), eval (caddr (x), a)),
1153 cdr (assq (&scm_macro, a))));
1154 return cons (&scm_macro,
1155 cons (define_lambda (x),
1156 cdr (assq (&scm_macro, a))));
1160 loop (scm *r, scm *e, scm *a)
1163 printf ("\nc:loop e=");
1169 else if (eq_p (e, &scm_symbol_EOF) == &scm_t)
1170 return apply_env (cdr (assq (&scm_symbol_loop2, a)),
1171 cons (&scm_unspecified, cons (&scm_t, cons (a, &scm_nil))), a);
1172 else if (eq_p (e, &scm_symbol_EOF2) == &scm_t)
1174 else if (atom_p (e) == &scm_t)
1175 return loop (eval (e, a), readenv (a), a);
1176 else if (eq_p (car (e), &scm_symbol_define) == &scm_t)
1177 return loop (&scm_unspecified,
1179 cons (define (e, a), a));
1180 else if (eq_p (car (e), &scm_symbol_define_macro) == &scm_t)
1181 return loop (&scm_unspecified,
1183 cons (define_macro (e, a), a));
1184 else if (eq_p (car (e), &scm_symbol_set_x) == &scm_t)
1185 return loop (set_env_x (cadr (e), eval (caddr (e), a), a), readenv (a), a);
1186 return loop (eval (e, a), readenv (a), a);
1190 main (int argc, char *argv[])
1192 scm *a = mes_environment ();
1193 display (loop (&scm_unspecified, readenv (a), a));
1199 apply_env (scm *fn, scm *x, scm *a)
1202 printf ("\nc:apply_env fn=");
1208 if (fn == &scm_apply_env_)
1209 return eval_ (x, a);
1210 return apply_env_ (fn, x, a);
1213 bool evalling_p = false;
1216 eval (scm *e, scm *a)
1219 printf ("\nc:eval e=");
1224 scm *eval__ = assq (&scm_symbol_eval, a);
1225 assert (eval__ != &scm_f);
1226 eval__ = cdr (eval__);
1227 if (builtin_p (eval__) == &scm_t
1229 return eval_ (e, a);
1231 scm *r = apply_env (eval__, cons (e, cons (a, &scm_nil)), a);