reduce.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include "lambda.h"
   5 #include "print.h"
   6 #include "mem.h"
   7
   8 struct lambda *copy(struct lambda *t)
   9 {
  10         struct lambda *c = malloc(sizeof (struct lambda));
  11         c->which = t->which;
  12         switch(t->which){
  13         case lambda_ident:
  14                 c->data.identifier = strdup(t->data.identifier);
  15                 break;
  16         case lambda_abs:
  17                 c->data.abstraction.ident = strdup(t->data.abstraction.ident);
  18                 c->data.abstraction.expr = copy(t->data.abstraction.expr);
  19                 break;
  20         case lambda_app:
  21                 c->data.application.expr1 = copy(t->data.application.expr1);
  22                 c->data.application.expr2 = copy(t->data.application.expr2);
  23                 break;
  24         }
  25         return c;
  26 }
  27
  28 void subst(char *ident, struct lambda *t1, struct lambda *t2, struct lambda *total)
  29 {
  30         struct lambda cpy;
  31         switch(t1->which){
  32         case lambda_ident:
  33                 if(strcmp(t1->data.identifier, ident) == 0){
  34                         cpy = *copy(t2);
  35                         free(t1->data.identifier);
  36                         if(total == t1)
  37                                 *total = cpy;
  38                         *t1 = cpy;
  39                 }
  40                 break;
  41         case lambda_abs:
  42                 if(strcmp(t1->data.abstraction.ident, ident) != 0)
  43                         subst(ident, t1->data.abstraction.expr, t2, total);
  44                 break;
  45         case lambda_app:
  46                 subst(ident, t1->data.application.expr1, t2, total);
  47                 subst(ident, t1->data.application.expr2, t2, total);
  48                 break;
  49         }
  50
  51 }
  52
  53 void lambda_reduce(struct lambda *t, struct lambda *total, int *maxdepth)
  54 {
  55         if(*maxdepth == 0)
  56                 return;
  57         struct lambda *t1, *t2;
  58         switch(t->which){
  59         case lambda_ident:
  60                 break;
  61         case lambda_abs:
  62                 lambda_reduce(t->data.abstraction.expr, total, maxdepth);
  63                 break;
  64         case lambda_app:
  65                 //If the first argument is an abstraction, we apply
  66                 t1 = t->data.application.expr1;
  67                 t2 = t->data.application.expr2;
  68                 lambda_reduce(t1, total, maxdepth);
  69                 lambda_reduce(t2, total, maxdepth);
  70                 if(t1->which == lambda_abs){
  71                         subst(t1->data.abstraction.ident, t1->data.abstraction.expr, t2, total);
  72                         (*maxdepth)--;
  73                         if(total == t)
  74                                 *total = *t1->data.abstraction.expr;
  75                         printf("-> ");
  76                         lambda_print(total);
  77                         lambda_reduce(t, total, maxdepth);
  78                 }
  79                 break;
  80         }
  81 }