change printing

[lambda.git] / reduce.c

diff --git a/reduce.c b/reduce.c
index 7335bfd..12914bf 100644 (file)
--- a/reduce.c
+++ b/reduce.c
@@ -1,3 +1,4 @@
+#include <stdbool.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
@@ -5,58 +6,54 @@
 #include "print.h"
 #include "mem.h"
 
-void subst(char *ident, struct lambda *t1, struct lambda *t2, struct lambda *total)
+#define lhs(t) (*t)->data.application.expr1
+#define rhs(t) (*t)->data.application.expr2
+#define bdy(t) (*t)->data.abstraction.expr
+
+void lambda_beta(struct lambda *binding, struct lambda **body, struct lambda *target, struct lambda *total)
 {
-       struct lambda cpy;
-       switch(t1->which){
+       switch((*body)->which){
        case lambda_ident:
-               if(strcmp(t1->data.identifier, ident) == 0){
-                       cpy = *copy(t2);
-                       free(t1->data.identifier);
-                       if(total == t1)
-                               *total = cpy;
-                       *t1 = cpy;
+               if((*body)->data.identifier.binding == binding){
+                       lambda_free(*body);
+                       *body = copy(target);
                }
                break;
        case lambda_abs:
-               if(strcmp(t1->data.abstraction.ident, ident) != 0)
-                       subst(ident, t1->data.abstraction.expr, t2, total);
+               lambda_beta(binding, &bdy(body), target, total);
                break;
        case lambda_app:
-               subst(ident, t1->data.application.expr1, t2, total);
-               subst(ident, t1->data.application.expr2, t2, total);
+               lambda_beta(binding, &lhs(body), target, total);
+               lambda_beta(binding, &rhs(body), target, total);
                break;
        }
-
 }
 
-void lambda_reduce(struct lambda *t, struct lambda *total, int *maxdepth)
+bool lambda_reduce(struct lambda **t, struct lambda **total, bool applicative)
 {
-       if(*maxdepth == 0)
-               return;
-       struct lambda *t1, *t2;
-       switch(t->which){
-       case lambda_ident:
-               break;
-       case lambda_abs:
-               lambda_reduce(t->data.abstraction.expr, total, maxdepth);
-               break;
-       case lambda_app:
-               //If the first argument is an abstraction, we apply
-               t1 = t->data.application.expr1;
-               t2 = t->data.application.expr2;
-               if(t1->which == lambda_abs){
-                       subst(t1->data.abstraction.ident, t1->data.abstraction.expr, t2, total);
-                       (*maxdepth)--;
-                       if(total == t)
-                               *total = *t1->data.abstraction.expr;
-                       *t = *t1->data.abstraction.expr;
-                       printf("-> ");
-                       lambda_print(total);
-                       lambda_reduce(t, total, maxdepth);
+       if((*t)->which == lambda_app){
+               if(applicative)
+                       if(lambda_reduce(&rhs(t), total, applicative))
+                               return true;
+               if(lhs(t)->which != lambda_abs){
+                       return lambda_reduce(&lhs(t), total, applicative);
+               } else {
+                       if(lhs(t)->data.abstraction.strict)
+                               lambda_reduce(&rhs(t), total, true);
+
+                       //In this abstraction we substitute the result with the rhs
+                       lambda_print(*total, *t);
+                       lambda_beta(lhs(t), &lhs(t)->data.abstraction.expr, rhs(t), *total);
+
+                       struct lambda *newt = copy(lhs(t)->data.abstraction.expr);
+                       lambda_free(*t);
+                       *t = newt;
+
+                       printf("β -> ");
+                       return true;
                }
-               lambda_reduce(t1, total, maxdepth);
-               lambda_reduce(t, total, maxdepth);
-               break;
+       } else if ((*t)->which == lambda_abs) {
+               return lambda_reduce(&bdy(t), total, applicative);
        }
+       return false;
 }