lambda.y

   1 %define parse.error verbose
   2 %{
   3 #include "lambda.h"
   4 #include "lambda.tab.h"
   5 #include "lambda.yy.h"
   6 #include "mem.h"
   7 #include "print.h"
   8 #include "reduce.h"
   9
  10 struct decllist *decls = NULL;
  11 extern int yylex();
  12
  13 int yydebug=1;
  14 void yyerror(const char *str)
  15 {
  16         fprintf(stderr, "parse error: %s\n", str);
  17 }
  18
  19 int yywrap()
  20 {
  21         struct decllist *t;
  22         while(decls != NULL){
  23                 free(decls->ident);
  24                 lambda_free(decls->value);
  25                 t = decls->next;
  26                 free(decls);
  27                 decls = t;
  28         }
  29         return 1;
  30 }
  31
  32 struct lambda *make_lambda()
  33 {
  34         return malloc(sizeof (struct lambda));
  35 }
  36
  37 struct lambda *make_ident(char *i)
  38 {
  39         struct lambda *r = make_lambda();
  40         r->which = lambda_ident;
  41         r->data.identifier.ident = strdup(i);
  42         r->data.identifier.binding = NULL;
  43         return r;
  44 }
  45
  46 void lambda_bind(struct lambda *tob, struct lambda *binding, char *ident)
  47 {
  48         switch(tob->which){
  49         case lambda_ident:
  50                 if(strcmp(ident, tob->data.identifier.ident) == 0 && tob->data.identifier.binding == NULL)
  51                         tob->data.identifier.binding = binding;
  52                 break;
  53         case lambda_abs:
  54                 lambda_bind(tob->data.abstraction.expr, binding, ident);
  55                 break;
  56         case lambda_app:
  57                 lambda_bind(tob->data.application.expr1, binding, ident);
  58                 lambda_bind(tob->data.application.expr2, binding, ident);
  59                 break;
  60         }
  61 }
  62
  63 struct lambda *make_abstraction(char *i, bool strict, struct lambda *t)
  64 {
  65         struct lambda *r = make_lambda();
  66         r->which = lambda_abs;
  67         r->data.abstraction.ident = strdup(i);
  68         r->data.abstraction.strict = strict;
  69         r->data.abstraction.expr = t;
  70         lambda_bind(t, r, i);
  71         return r;
  72 }
  73
  74 struct lambda *make_application(struct lambda *t1, struct lambda *t2)
  75 {
  76         struct lambda *r = make_lambda();
  77         r->which = lambda_app;
  78         r->data.application.expr1 = t1;
  79         r->data.application.expr2 = t2;
  80         return r;
  81 }
  82
  83 struct lambda *make_numeral(unsigned int i)
  84 {
  85         struct lambda *body = make_ident("x");
  86         while(i-- > 0)
  87                 body = make_application(make_ident("f"), body);
  88         return make_abstraction("f", false, make_abstraction("x", false, body));
  89 }
  90
  91 struct lambda *make_bool(bool b)
  92 {
  93         return b
  94                 ? make_abstraction("a", false, make_abstraction("b", false, make_ident("a")))
  95                 : make_abstraction("a", false, make_abstraction("b", false, make_ident("b")));
  96 }
  97
  98 void decls_prepend(char *ident, struct lambda *value)
  99 {
 100         struct decllist *head = malloc(sizeof (struct decllist));
 101         head->next = decls;
 102         head->ident = strdup(ident);
 103         head->value = value;
 104         decls = head;
 105 }
 106
 107 struct lambda *decls_lookup(char *ident)
 108 {
 109         struct decllist *c = decls;
 110         while(c != NULL){
 111                 if(strcmp(c->ident, ident) == 0)
 112                         return copy(c->value);
 113                 c = c->next;
 114         }
 115         return make_ident(ident);
 116 }
 117
 118 int main()
 119 {
 120         setbuf(stdout, NULL);
 121         int r = yyparse();
 122         yylex_destroy();
 123         return r;
 124 }
 125
 126 %}
 127
 128 %token LAMBDA DOT OBRACE CBRACE IDENT FUNC SEMICOLON ASSIGN LITERAL BANG
 129
 130 %%
 131
 132 program
 133         :
 134         | lambda SEMICOLON program
 135 lambda
 136         : FUNC func
 137                 {
 138                         decls_prepend($1->data.identifier.ident, $2);
 139                         printf("%s = ", $1->data.identifier.ident);
 140                         lambda_print($2, NULL);
 141                         putchar('\n');
 142                         lambda_free($1);
 143                 }
 144         | term
 145                 {
 146                         struct lambda *t = $1;
 147                         printf("     ");
 148                         for(unsigned int i = 0; i<999; i++)
 149                                 if(!lambda_reduce(&t, &t, true))
 150                                         break;
 151                         lambda_print(t, NULL);
 152                         putchar('\n');
 153                         lambda_free(t);
 154                 }
 155 func
 156         : ASSIGN term
 157                 { $$ = $2; }
 158         | BANG IDENT func
 159                 {
 160                         $$ = make_abstraction($2->data.identifier.ident, true, $3);
 161                         lambda_free($2);
 162                 }
 163         | IDENT func
 164                 {
 165                         $$ = make_abstraction($1->data.identifier.ident, false, $2);
 166                         lambda_free($1);
 167                 }
 168 term
 169         : term appterm
 170                 { $$ = make_application($1, $2); }
 171         | appterm
 172                 { $$ = $1; }
 173 appterm
 174         : LITERAL
 175                 { $$ = $1; }
 176         | FUNC
 177                 {
 178                         $$ = decls_lookup($1->data.identifier.ident);
 179                         lambda_free($1);
 180                 }
 181         | IDENT
 182                 { $$ = $1; }
 183         | LAMBDA abstraction
 184                 { $$ = $2; }
 185         | OBRACE term CBRACE
 186                 { $$ = $2; }
 187 abstraction
 188         : BANG IDENT abstraction
 189                 {
 190                         $$ = make_abstraction($2->data.identifier.ident, true, $3);
 191                         lambda_free($2);
 192                 }
 193         | IDENT abstraction
 194                 {
 195                         $$ = make_abstraction($1->data.identifier.ident, false, $2);
 196                         lambda_free($1);
 197                 }
 198         | DOT term
 199                 { $$ = $2; }