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         struct lambda *t = malloc(sizeof (struct lambda));
  35         t->refcount = 1;
  36         return t;
  37 }
  38
  39 struct lambda *make_ident(char *i)
  40 {
  41         struct lambda *r = make_lambda();
  42         r->which = lambda_ident;
  43         r->data.identifier.ident = strdup(i);
  44         r->data.identifier.revision = 0;
  45         return r;
  46 }
  47
  48 struct lambda *make_abstraction(char *i, bool strict, struct lambda *t)
  49 {
  50         struct lambda *r = make_lambda();
  51         r->which = lambda_abs;
  52         r->data.abstraction.ident = strdup(i);
  53         r->data.abstraction.revision = 0;
  54         r->data.abstraction.strict = strict;
  55         r->data.abstraction.expr = t;
  56         return r;
  57 }
  58
  59 struct lambda *make_application(struct lambda *t1, struct lambda *t2)
  60 {
  61         struct lambda *r = make_lambda();
  62         r->which = lambda_app;
  63         r->data.application.expr1 = t1;
  64         r->data.application.expr2 = t2;
  65         return r;
  66 }
  67
  68 struct lambda *make_numeral(unsigned int i)
  69 {
  70         struct lambda *body = make_ident("x");
  71         while(i-- > 0)
  72                 body = make_application(make_ident("f"), body);
  73         return make_abstraction("f", false, make_abstraction("x", false, body));
  74 }
  75
  76 struct lambda *make_bool(bool b)
  77 {
  78         return b
  79                 ? make_abstraction("a", false, make_abstraction("b", false, make_ident("a")))
  80                 : make_abstraction("a", false, make_abstraction("b", false, make_ident("b")));
  81 }
  82
  83 void decls_prepend(char *ident, struct lambda *value)
  84 {
  85         struct decllist *head = malloc(sizeof (struct decllist));
  86         head->next = decls;
  87         head->ident = strdup(ident);
  88         head->value = value;
  89         decls = head;
  90 }
  91
  92 struct lambda *decls_lookup(char *ident)
  93 {
  94         struct decllist *c = decls;
  95         while(c != NULL){
  96                 if(strcmp(c->ident, ident) == 0)
  97                         return copy(c->value);
  98                 c = c->next;
  99         }
 100         return make_ident(ident);
 101 }
 102
 103 int main()
 104 {
 105         int r = yyparse();
 106         yylex_destroy();
 107         return r;
 108 }
 109
 110 %}
 111
 112 %token LAMBDA DOT OBRACE CBRACE IDENT FUNC SEMICOLON ASSIGN LITERAL BANG
 113
 114 %%
 115
 116 program
 117         :
 118         | lambda SEMICOLON program
 119 lambda
 120         : term
 121                 {
 122                         int maxdepth = 1000;
 123                         printf("     ");
 124                         lambda_reduce(&$1, &$1, &maxdepth);
 125                         lambda_print($1, NULL);
 126                         lambda_free($1);
 127                 }
 128         | FUNC func
 129                 {
 130                         decls_prepend($1->data.identifier.ident, $2);
 131                         printf("%s = ", $1->data.identifier.ident);
 132                         lambda_print($2, NULL);
 133                         lambda_free($1);
 134                 }
 135 func
 136         : ASSIGN term
 137                 { $$ = $2; }
 138         | BANG IDENT func
 139                 {
 140                         $$ = make_abstraction($2->data.identifier.ident, true, $3);
 141                         lambda_free($2);
 142                 }
 143         | IDENT func
 144                 {
 145                         $$ = make_abstraction($1->data.identifier.ident, false, $2);
 146                         lambda_free($1);
 147                 }
 148 term
 149         : term appterm
 150                 { $$ = make_application($1, $2); }
 151         | appterm
 152                 { $$ = $1; }
 153 appterm
 154         : LITERAL
 155                 { $$ = $1; }
 156         | FUNC
 157                 {
 158                         $$ = decls_lookup($1->data.identifier.ident);
 159                         lambda_free($1);
 160                 }
 161         | IDENT
 162                 { $$ = $1; }
 163         | LAMBDA abstraction
 164                 { $$ = $2; }
 165         | OBRACE term CBRACE
 166                 { $$ = $2; }
 167 abstraction
 168         : BANG IDENT abstraction
 169                 {
 170                         $$ = make_abstraction($2->data.identifier.ident, true, $3);
 171                         lambda_free($2);
 172                 }
 173         | IDENT abstraction
 174                 {
 175                         $$ = make_abstraction($1->data.identifier.ident, false, $2);
 176                         lambda_free($1);
 177                 }
 178         | DOT term
 179                 { $$ = $2; }