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 make_abstraction("a", false,
  94                 make_abstraction("b", false, make_ident(b ? "a" : "b")));
  95 }
  96
  97 void decls_prepend(char *ident, struct lambda *value)
  98 {
  99         struct decllist *head = malloc(sizeof (struct decllist));
 100         head->next = decls;
 101         head->ident = strdup(ident);
 102         head->value = value;
 103         decls = head;
 104 }
 105
 106 struct lambda *decls_lookup(char *ident)
 107 {
 108         for(struct decllist *c = decls; c != NULL; c = c->next)
 109                 if(strcmp(c->ident, ident) == 0)
 110                         return copy(c->value);
 111         return make_ident(ident);
 112 }
 113
 114 int main()
 115 {
 116         int r = yyparse();
 117         yylex_destroy();
 118         return r;
 119 }
 120
 121 %}
 122
 123 %token LAMBDA DOT OBRACE CBRACE IDENT FUNC SEMICOLON ASSIGN LITERAL BANG
 124
 125 %%
 126
 127 program
 128         :
 129         | lambda SEMICOLON program
 130 lambda
 131         : FUNC func
 132                 {
 133                         decls_prepend($1->data.identifier.ident, $2);
 134                         printf("%s = ", $1->data.identifier.ident);
 135                         lambda_print($2, NULL);
 136                         lambda_free($1);
 137                 }
 138         | term
 139                 {
 140                         struct lambda *t = $1;
 141                         printf("     ");
 142                         for(unsigned int i = 0; i<999; i++)
 143                                 if(!lambda_reduce(&t, &t, false))
 144                                         break;
 145                         lambda_print(t, NULL);
 146                         lambda_free(t);
 147                 }
 148 func
 149         : ASSIGN term
 150                 { $$ = $2; }
 151         | BANG IDENT func
 152                 {
 153                         $$ = make_abstraction($2->data.identifier.ident, true, $3);
 154                         lambda_free($2);
 155                 }
 156         | IDENT func
 157                 {
 158                         $$ = make_abstraction($1->data.identifier.ident, false, $2);
 159                         lambda_free($1);
 160                 }
 161 term
 162         : term appterm
 163                 { $$ = make_application($1, $2); }
 164         | appterm
 165                 { $$ = $1; }
 166 appterm
 167         : LITERAL
 168                 { $$ = $1; }
 169         | FUNC
 170                 {
 171                         $$ = decls_lookup($1->data.identifier.ident);
 172                         lambda_free($1);
 173                 }
 174         | IDENT
 175                 { $$ = $1; }
 176         | LAMBDA abstraction
 177                 { $$ = $2; }
 178         | OBRACE term CBRACE
 179                 { $$ = $2; }
 180 abstraction
 181         : BANG IDENT abstraction
 182                 {
 183                         $$ = make_abstraction($2->data.identifier.ident, true, $3);
 184                         lambda_free($2);
 185                 }
 186         | IDENT abstraction
 187                 {
 188                         $$ = make_abstraction($1->data.identifier.ident, false, $2);
 189                         lambda_free($1);
 190                 }
 191         | DOT term
 192                 { $$ = $2; }