Transition rules

1 files changed, 140 insertions, 8 deletions

diff --git a/src/reducer.c b/src/reducer.c
index 412dfb3..a2d5746 100644
--- a/src/reducer.c
+++ b/src/reducer.c
@@ -52,6 +52,12 @@ struct conf {
 	} u;
 };
 
+static int name_generator(void)
+{
+	static int current = 0x696969;
+	return current++;
+}
+
 static struct stack *stack_push(struct stack *stack, void *data)
 {
 	struct stack *new = malloc(sizeof(*new));
@@ -83,7 +89,7 @@ static void *store_get(struct store *store, int key)
 	return 0;
 }
 
-static int trans(struct conf *conf)
+static int transition(struct conf *conf)
 {
 	if (conf->type == CLOSURE) {
 		struct term *term = conf->u.econf.term;
@@ -91,6 +97,7 @@ static int trans(struct conf *conf)
 		struct stack *stack = conf->u.econf.stack;
 		switch (term->type) {
 		case APP: // (1)
+			printf("(1)\n");
 			conf->type = CLOSURE;
 			conf->u.econf.term = term->u.app.lhs;
 			struct term *app = new_term(APP);
@@ -102,8 +109,9 @@ static int trans(struct conf *conf)
 			app->u.app.rhs->u.other = closure;
 			conf->u.econf.stack =
 				stack_push(conf->u.econf.stack, app);
-			break;
+			return 0;
 		case ABS: // (2)
+			printf("(2)\n");
 			conf->type = COMPUTED;
 			conf->u.cconf.stack = stack;
 			conf->u.cconf.term = new_term(CACHE);
@@ -118,7 +126,7 @@ static int trans(struct conf *conf)
 			cache->term = new_term(CLO);
 			cache->term->u.other = closure;
 			conf->u.cconf.term = cache;
-			break;
+			return 0;
 		case VAR:
 			box = store_get(store, term->u.var.name);
 			if (!box) {
@@ -127,6 +135,7 @@ static int trans(struct conf *conf)
 				box->data = term;
 			}
 			if (box->state != DONE) { // (3)
+				printf("(3)\n");
 				assert(box->state == TODO &&
 				       ((struct term *)box->data)->type == CLO);
 				closure = ((struct term *)box->data)->u.other;
@@ -138,25 +147,148 @@ static int trans(struct conf *conf)
 				cache->term = new_term(VAR);
 				conf->u.econf.stack =
 					stack_push(conf->u.econf.stack, cache);
+				return 0;
 			} else { // (4)
+				printf("(4)\n");
 				conf->type = COMPUTED;
 				conf->u.cconf.stack = stack;
 				conf->u.cconf.term = box->data;
+				return 0;
 			}
-			break;
 		default:
 			fprintf(stderr, "Invalid type %d\n", term->type);
-			break;
+			return 1;
 		}
 	} else if (conf->type == COMPUTED) {
-		// somewhere return 1
+		struct stack *stack = conf->u.cconf.stack;
+		struct term *term = conf->u.cconf.term;
+		if (!stack || !stack->next || !stack->data)
+			return 1;
+		struct term *peek_term = stack->data;
+		if (peek_term->type == CACHE) { // (5)
+			struct cache *cache = peek_term->u.other;
+			struct term *cache_term = cache->term;
+			if (cache_term->type == VAR &&
+			    !cache_term->u.var.name) {
+				printf("(5)\n");
+				struct box *cache_box = cache->box;
+				cache_box->state = DONE;
+				cache_box->data = term;
+				conf->type = COMPUTED;
+				conf->u.cconf.stack = stack->next;
+				conf->u.cconf.term = term;
+				return 0;
+			}
+		}
+		if (peek_term->type == APP &&
+		    peek_term->u.app.lhs->type == VAR &&
+		    !peek_term->u.app.lhs->u.var.name && term->type == CACHE &&
+		    ((struct cache *)term->u.other)->term->type == CLO) { // (6)
+			struct closure *closure =
+				((struct cache *)term->u.other)->term->u.other;
+			if (closure->term->type == ABS) {
+				printf("(6)\n");
+				struct box *box = malloc(sizeof(*box));
+				box->state = TODO;
+				box->data = peek_term->u.app.rhs;
+				conf->type = CLOSURE;
+				conf->u.econf.store =
+					store_push(closure->store,
+						   closure->term->u.abs.name,
+						   box);
+				conf->u.econf.stack = stack->next;
+				return 0;
+			}
+		}
+		if (term->type == CACHE &&
+		    ((struct cache *)term->u.other)->term->type == CLO) {
+			struct box *box = ((struct cache *)term->u.other)->box;
+			struct closure *closure =
+				((struct cache *)term->u.other)->term->u.other;
+			if (closure->term->type == ABS && box->state == TODO &&
+			    !box->data) { // (7)
+				printf("(7)\n");
+				int x = name_generator();
+				box = malloc(sizeof(*box));
+				box->state = DONE;
+				box->data = new_term(VAR);
+				((struct term *)box->data)->u.var.name = x;
+				conf->type = CLOSURE;
+				conf->u.econf.store =
+					store_push(closure->store,
+						   closure->term->u.abs.name,
+						   box);
+				struct cache *cache = malloc(sizeof(*cache));
+				cache->box = box;
+				cache->term = new_term(VAR);
+				struct term *cache_term = new_term(CACHE);
+				cache_term->u.other = cache;
+				conf->u.econf.stack = stack_push(
+					conf->u.econf.stack, cache_term);
+				struct term *abs = new_term(ABS);
+				abs->u.abs.name = x;
+				abs->u.abs.term = new_term(VAR);
+				conf->u.econf.stack =
+					stack_push(conf->u.econf.stack, abs);
+				return 0;
+			}
+			if (closure->term->type == ABS &&
+			    box->state == DONE) { // (8)
+				printf("(8)\n");
+				conf->type = COMPUTED;
+				conf->u.cconf.stack = stack;
+				conf->u.cconf.term = box->data;
+				return 0;
+			}
+			// TODO: #:when??
+		}
+		if (peek_term->type == APP &&
+		    peek_term->u.app.lhs->type == VAR &&
+		    !peek_term->u.app.lhs->u.var.name &&
+		    peek_term->u.app.rhs->type == CLO) { // (9)
+			printf("(9)\n");
+			struct closure *closure = peek_term->u.app.rhs->u.other;
+			conf->type = CLOSURE;
+			conf->u.econf.term = closure->term;
+			conf->u.econf.store = closure->store;
+			struct term *app = new_term(APP);
+			app->u.app.lhs = term;
+			app->u.app.rhs = new_term(VAR);
+			conf->u.econf.stack = stack_push(stack->next, app);
+			return 0;
+		}
+		if (peek_term->type == APP &&
+		    peek_term->u.app.rhs->type == VAR &&
+		    !peek_term->u.app.rhs->u.var.name) { // (10)
+			printf("(10)\n");
+			struct term *app = new_term(APP);
+			app->u.app.lhs = peek_term->u.app.lhs;
+			app->u.app.rhs = term;
+			conf->type = COMPUTED;
+			conf->u.cconf.stack = stack->next;
+			conf->u.cconf.term = app;
+			return 0;
+		}
+		if (peek_term->type == ABS &&
+		    peek_term->u.app.rhs->type == VAR &&
+		    !peek_term->u.app.rhs->u.var.name) { // (11)
+			printf("(11)\n");
+			struct term *abs = new_term(ABS);
+			abs->u.abs.name = peek_term->u.abs.name;
+			abs->u.abs.term = term;
+			conf->type = COMPUTED;
+			conf->u.cconf.stack = stack->next;
+			conf->u.cconf.term = abs;
+			return 0;
+		}
 	}
-	return 0;
+	fprintf(stderr, "Invalid transition state\n");
+	return 1;
 }
 
 static struct conf *for_each_state(struct conf *conf)
 {
-	int ret = trans(conf);
+	int ret = transition(conf);
 	return ret ? conf : for_each_state(conf);
 }