git.gag.com Git - fw/altos/blob - src/lisp/ao_lisp_eval.c

   1 /*
   2  * Copyright © 2016 Keith Packard <keithp@keithp.com>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  */
  14
  15 #include "ao_lisp.h"
  16
  17 /*
  18  * Non-recursive eval
  19  *
  20  * Plan: walk actuals, construct formals
  21  *
  22  * stack >  save  > actuals > actual_1
  23  *           v         v
  24  *         formals     .    > actual_2
  25  */
  26
  27 static struct ao_lisp_cons      *stack;
  28 static struct ao_lisp_cons      *actuals;
  29 static struct ao_lisp_cons      *formals;
  30 static struct ao_lisp_cons      *formals_tail;
  31 static uint8_t been_here;
  32
  33 #if 0
  34 #define DBG(...) printf(__VA_ARGS__)
  35 #define DBG_CONS(a)     ao_lisp_cons_print(a)
  36 #define DBG_POLY(a)     ao_lisp_poly_print(a)
  37 #else
  38 #define DBG(...)
  39 #define DBG_CONS(a)
  40 #define DBG_POLY(a)
  41 #endif
  42
  43 ao_poly
  44 ao_lisp_eval(ao_poly v)
  45 {
  46         struct ao_lisp_cons     *formal;
  47         int                     cons = 0;
  48
  49         if (!been_here) {
  50                 been_here = 1;
  51                 ao_lisp_root_add(&ao_lisp_cons_type, &stack);
  52                 ao_lisp_root_add(&ao_lisp_cons_type, &actuals);
  53                 ao_lisp_root_add(&ao_lisp_cons_type, &formals);
  54                 ao_lisp_root_add(&ao_lisp_cons_type, &formals_tail);
  55         }
  56         stack = 0;
  57         actuals = 0;
  58         formals = 0;
  59         formals_tail = 0;
  60         for (;;) {
  61
  62         restart:
  63                 /* Build stack frames for each list */
  64                 while (ao_lisp_poly_type(v) == AO_LISP_CONS) {
  65                         if (v == AO_LISP_NIL)
  66                                 break;
  67
  68                         /* Push existing frame on the stack */
  69                         if (cons++) {
  70                                 struct ao_lisp_cons *frame;
  71
  72                                 frame = ao_lisp_cons_cons(ao_lisp_cons_poly(actuals), formals);
  73                                 stack = ao_lisp_cons_cons(ao_lisp_cons_poly(frame), stack);
  74                         }
  75                         actuals = ao_lisp_poly_cons(v);
  76                         formals = NULL;
  77                         formals_tail = NULL;
  78                         v = actuals->car;
  79
  80                         DBG("start: stack"); DBG_CONS(stack); DBG("\n");
  81                         DBG("start: actuals"); DBG_CONS(actuals); DBG("\n");
  82                         DBG("start: formals"); DBG_CONS(formals); DBG("\n");
  83                 }
  84
  85                 /* Evaluate primitive types */
  86
  87                 DBG ("actual: "); DBG_POLY(v); DBG("\n");
  88
  89                 switch (ao_lisp_poly_type(v)) {
  90                 case AO_LISP_INT:
  91                 case AO_LISP_STRING:
  92                         break;
  93                 case AO_LISP_ATOM:
  94                         v = ao_lisp_poly_atom(v)->val;
  95                         break;
  96                 }
  97
  98                 if (!cons)
  99                         break;
 100
 101                 for (;;) {
 102                         DBG("add formal: "); DBG_POLY(v); DBG("\n");
 103
 104                         if (formals == NULL) {
 105                                 if (ao_lisp_poly_type(v) == AO_LISP_BUILTIN) {
 106                                         struct ao_lisp_builtin *b = ao_lisp_poly_builtin(v);
 107                                         switch (b->args) {
 108                                         case AO_LISP_NLAMBDA:
 109                                                 v = ao_lisp_func(b)(ao_lisp_poly_cons(actuals->cdr));
 110                                                 goto done_eval;
 111
 112                                         case AO_LISP_MACRO:
 113                                                 v = ao_lisp_func(b)(ao_lisp_poly_cons(actuals->cdr));
 114                                                 DBG("macro "); DBG_POLY(ao_lisp_cons_poly(actuals));
 115                                                 DBG(" -> "); DBG_POLY(v);
 116                                                 DBG("\n");
 117                                                 if (ao_lisp_poly_type(v) != AO_LISP_CONS) {
 118                                                         ao_lisp_exception |= AO_LISP_INVALID;
 119                                                         return AO_LISP_NIL;
 120                                                 }
 121
 122                                                 /* Reset frame to the new list */
 123                                                 actuals = ao_lisp_poly_cons(v);
 124                                                 v = actuals->car;
 125                                                 goto restart;
 126                                         }
 127                                 }
 128                         }
 129
 130                         formal = ao_lisp_cons_cons(v, NULL);
 131                         if (formals_tail)
 132                                 formals_tail->cdr = ao_lisp_cons_poly(formal);
 133                         else
 134                                 formals = formal;
 135                         formals_tail = formal;
 136                         actuals = ao_lisp_poly_cons(actuals->cdr);
 137
 138                         DBG("formals: ");
 139                         DBG_CONS(formals);
 140                         DBG("\n");
 141                         DBG("actuals: ");
 142                         DBG_CONS(actuals);
 143                         DBG("\n");
 144
 145                         /* Process all of the arguments */
 146                         if (actuals) {
 147                                 v = actuals->car;
 148                                 break;
 149                         }
 150
 151                         v = formals->car;
 152
 153                         /* Evaluate the resulting list */
 154                         if (ao_lisp_poly_type(v) == AO_LISP_BUILTIN) {
 155                                 struct ao_lisp_builtin *b = ao_lisp_poly_builtin(v);
 156
 157                                 v = ao_lisp_func(b) (ao_lisp_poly_cons(formals->cdr));
 158
 159                                 DBG ("eval: ");
 160                                 DBG_CONS(formals);
 161                                 DBG(" -> ");
 162                                 DBG_POLY(v);
 163                                 DBG ("\n");
 164                         } else {
 165                                 ao_lisp_exception |= AO_LISP_INVALID;
 166                         }
 167                         if (ao_lisp_exception)
 168                                 return AO_LISP_NIL;
 169                 done_eval:
 170                         if (--cons) {
 171                                 struct ao_lisp_cons     *frame;
 172
 173                                 /* Pop the previous frame off the stack */
 174                                 frame = ao_lisp_poly_cons(stack->car);
 175                                 actuals = ao_lisp_poly_cons(frame->car);
 176                                 formals = ao_lisp_poly_cons(frame->cdr);
 177                                 formals_tail = NULL;
 178
 179                                 /* Recompute the tail of the formals list */
 180                                 if (formals) {
 181                                         for (formal = formals; formal->cdr != AO_LISP_NIL; formal = ao_lisp_poly_cons(formal->cdr));
 182                                         formals_tail = formal;
 183                                 }
 184
 185                                 stack = ao_lisp_poly_cons(stack->cdr);
 186                                 DBG("stack pop: stack"); DBG_CONS(stack); DBG("\n");
 187                                 DBG("stack pop: actuals"); DBG_CONS(actuals); DBG("\n");
 188                                 DBG("stack pop: formals"); DBG_CONS(formals); DBG("\n");
 189                         } else {
 190                                 DBG("done func\n");
 191                                 break;
 192                         }
 193                 }
 194                 if (!cons)
 195                         break;
 196         }
 197         return v;
 198 }