Started basic beta shift

1 files changed, 22 insertions, 17 deletions

diff --git a/src/term.c b/src/term.c
index caea6f1..7756bdc 100644
--- a/src/term.c
+++ b/src/term.c
@@ -20,7 +20,7 @@ static void term_destroy_parent(void *item)
 // this is needed to destroy possibly multiple parents
 void term_destroy_head(struct term *term, char including_parents)
 {
-	debug("destroying head of %lx\n", term->hash);
+	debug("destroying head of %lx\n", term->hash & HASH_MASK);
 
 	map_delete(map_all_terms(), term);
 
@@ -60,24 +60,23 @@ char term_is_beta_redex(struct term *term)
 	return term->type == APP && term->u.app.lhs->type == ABS;
 }
 
-void term_print(struct term *term)
+size_t term_print(struct term *term)
 {
 	switch (term->type) {
 	case ABS:
 		fprintf(stderr, "[");
-		term_print(term->u.abs.term);
+		size_t t = term_print(term->u.abs.term);
 		fprintf(stderr, "]");
-		break;
+		return 2 + t;
 	case APP:
 		fprintf(stderr, "(");
-		term_print(term->u.app.lhs);
+		size_t l = term_print(term->u.app.lhs);
 		fprintf(stderr, " ");
-		term_print(term->u.app.rhs);
+		size_t r = term_print(term->u.app.rhs);
 		fprintf(stderr, ")");
-		break;
+		return 3 + l + r;
 	case VAR:
-		fprintf(stderr, "%ld", term->u.var.index);
-		break;
+		return fprintf(stderr, "%ld", term->u.var.index);
 	default:
 		fatal("invalid type %d\n", term->type);
 	}
@@ -85,7 +84,8 @@ void term_print(struct term *term)
 
 struct term *term_rehash_abs(struct term *head, struct term *term)
 {
-	debug("rehashing abs %lx\n", head->hash);
+	debug("rehashing abs %lx (%lx)\n", head->hash & HASH_MASK,
+	      term->hash & HASH_MASK);
 	hash_t res =
 		hash((uint8_t *)&head->type, sizeof(head->type), term->hash);
 
@@ -94,11 +94,13 @@ struct term *term_rehash_abs(struct term *head, struct term *term)
 
 	struct term *match = map_get(map_all_terms(), res);
 	if (match) { // already exists
+		// TODO: something different if match->u.abs.term == term)?
 		term_refer_head(match, head->depth);
 		term_deref_head(head, 1);
 		return match;
 	} else { // create new
 		struct term *new = term_new(ABS, res, head->depth);
+		// TODO: Clone parents
 		new->u.abs.term = term;
 		map_set(map_all_terms(), new);
 		map_set(term->parents, new);
@@ -107,10 +109,12 @@ struct term *term_rehash_abs(struct term *head, struct term *term)
 	}
 }
 
+// ok main problem is reparenting substitution tickle-up
 struct term *term_rehash_app(struct term *head, struct term *lhs,
 			     struct term *rhs)
 {
-	debug("rehashing app %lx\n", head->hash);
+	debug("rehashing app %lx (%lx, %lx)\n", head->hash & HASH_MASK,
+	      lhs->hash & HASH_MASK, rhs->hash & HASH_MASK);
 	hash_t res =
 		hash((uint8_t *)&head->type, sizeof(head->type), lhs->hash);
 	res = hash((uint8_t *)&res, sizeof(res), rhs->hash);
@@ -125,6 +129,7 @@ struct term *term_rehash_app(struct term *head, struct term *lhs,
 		return match;
 	} else { // create new
 		struct term *new = term_new(APP, res, head->depth);
+		// TODO: Clone parents
 		new->u.app.lhs = lhs;
 		new->u.app.rhs = rhs;
 		map_set(map_all_terms(), new);
@@ -137,7 +142,7 @@ struct term *term_rehash_app(struct term *head, struct term *lhs,
 
 struct term *term_rehash_var(struct term *head, size_t index)
 {
-	debug("rehashing var %lx\n", head->hash);
+	debug("rehashing var %lx (%lu)\n", head->hash & HASH_MASK, index);
 	hash_t res = hash((uint8_t *)&head->type, sizeof(head->type), index);
 
 	if (res == head->hash)
@@ -149,7 +154,8 @@ struct term *term_rehash_var(struct term *head, size_t index)
 		term_deref(head, 1);
 		return match;
 	} else { // create new
-		struct term *new = term_new(APP, res, head->depth);
+		struct term *new = term_new(VAR, res, head->depth);
+		// TODO: Clone parents
 		new->u.var.index = index;
 		map_set(map_all_terms(), new);
 		term_deref_head(head, 1);
@@ -171,12 +177,11 @@ struct term *term_rehash(struct term *term)
 	fatal("invalid type %d\n", term->type);
 }
 
-// returns the direct parent
 void term_rehash_parents(struct term *term)
 {
 	if (!term->parents)
 		return;
-	debug("rehashing parents of %lx\n", term->hash);
+	debug("rehashing parents of %lx\n", term->hash & HASH_MASK);
 
 	// we need to convert the parent hashmap to a list
 	// so we can replace the rehashed elements while looping
@@ -223,7 +228,7 @@ void term_rehash_parents(struct term *term)
 
 void term_refer_head(struct term *term, size_t depth)
 {
-	debug("referring head of %lx\n", term->hash);
+	debug("referring head of %lx\n", term->hash & HASH_MASK);
 	term->refs++;
 	if (depth < term->depth) // lower depths are more important
 		term->depth = depth;
@@ -243,7 +248,7 @@ void term_refer(struct term *term, size_t depth)
 
 char term_deref_head(struct term *term, char destroy_parents)
 {
-	debug("dereferring head of %lx\n", term->hash);
+	debug("dereferring head of %lx\n", term->hash & HASH_MASK);
 
 	assert(term->refs);
 	term->refs--;