Added parent hashmaps

9 files changed, 73 insertions, 99 deletions

diff --git a/inc/map.h b/inc/map.h
index 53b0c98..b389bfa 100644
--- a/inc/map.h
+++ b/inc/map.h
@@ -6,14 +6,16 @@
 
 #include <lib/hash.h>
 #include <lib/pqueue.h>
+#include <lib/hashmap.h>
 
-struct term *map_get(hash_t hash);
-void map_set(struct term *term, hash_t hash);
-void map_delete(struct term *term);
+struct hashmap *map_all_terms(void);
+struct term *map_get(struct hashmap *map, hash_t hash);
+void map_set(struct hashmap *map, struct term *term, hash_t hash);
+void map_delete(struct hashmap *map, struct term *term);
 void map_initialize(void);
-void map_destroy(void);
-void map_dump(void); // TODO: remove
-struct pqueue *map_to_pqueue(pqueue_cmp_pri_f cmppri, pqueue_get_pri_f getpri,
-			     pqueue_set_pos_f set_pos);
+void map_destroy(struct hashmap *map);
+void map_dump(struct hashmap *map); // TODO: remove
+struct pqueue *map_to_pqueue(struct hashmap *map, pqueue_cmp_pri_f cmppri,
+			     pqueue_get_pri_f getpri, pqueue_set_pos_f set_pos);
 
 #endif
diff --git a/inc/reduce.h b/inc/reduce.h
index 9856075..4fff82f 100644
--- a/inc/reduce.h
+++ b/inc/reduce.h
@@ -6,6 +6,6 @@
 
 #include <term.h>
 
-struct term *reduce(struct term *term);
+void reduce(struct term *term);
 
 #endif
diff --git a/inc/term.h b/inc/term.h
index c94894d..3216e4a 100644
--- a/inc/term.h
+++ b/inc/term.h
@@ -5,12 +5,14 @@
 #define CALM_TERM_H
 
 #include <lib/hash.h>
+#include <lib/hashmap.h>
 
 typedef enum { INV, ABS, APP, VAR } term_type_t;
 
 struct term {
 	term_type_t type;
 	hash_t hash;
+	struct hashmap *parents;
 	size_t refs;
 	size_t depth;
 	union {
diff --git a/src/main.c b/src/main.c
index 47e88a9..af1b164 100644
--- a/src/main.c
+++ b/src/main.c
@@ -60,17 +60,17 @@ int main(int argc, char *argv[])
 
 	term_print(handle.term);
 	fprintf(stderr, "\n");
-	struct term *new = reduce(handle.term);
+	reduce(handle.term->u.abs.term);
 	fprintf(stderr, "after\n");
-	term_print(new);
+	term_print(handle.term);
 	fprintf(stderr, "\n");
 
-	map_dump();
+	map_dump(map_all_terms());
 
 	/* schedule_init(); */
 	/* schedule(); */
 	/* schedule_destroy(); */
 
-	map_destroy();
+	map_destroy(map_all_terms());
 	return 0;
 }
diff --git a/src/map.c b/src/map.c
index c0a2f97..57394ee 100644
--- a/src/map.c
+++ b/src/map.c
@@ -15,17 +15,22 @@ static void hashmap_free_term(void *item)
 	free(term);
 }
 
-struct term *map_get(hash_t hash)
+struct hashmap *map_all_terms(void)
 {
-	struct term **handle = hashmap_get(all_terms, hash);
+	return all_terms;
+}
+
+struct term *map_get(struct hashmap *map, hash_t hash)
+{
+	struct term **handle = hashmap_get(map, hash);
 	if (!handle)
 		return 0;
 	return *handle;
 }
 
-void map_set(struct term *term, hash_t hash)
+void map_set(struct hashmap *map, struct term *term, hash_t hash)
 {
-	hashmap_set(all_terms, &term, hash);
+	hashmap_set(map, &term, hash);
 }
 
 void map_initialize(void)
@@ -33,22 +38,22 @@ void map_initialize(void)
 	all_terms = hashmap_new(sizeof(struct term *), 0, hashmap_free_term);
 }
 
-void map_delete(struct term *term)
+void map_delete(struct hashmap *map, struct term *term)
 {
-	hashmap_delete(all_terms, term->hash);
+	hashmap_delete(map, term->hash);
 }
 
-void map_destroy(void)
+void map_destroy(struct hashmap *map)
 {
-	hashmap_free(all_terms);
+	hashmap_free(map);
 }
 
-void map_dump(void)
+void map_dump(struct hashmap *map)
 {
 	fprintf(stderr, "\n---\nMap dump:\n");
 	size_t iter = 0;
 	void *iter_val;
-	while (hashmap_iter(all_terms, &iter, &iter_val)) {
+	while (hashmap_iter(map, &iter, &iter_val)) {
 		struct term *term = *(struct term **)iter_val;
 		fprintf(stderr, "%d ", term->type);
 		term_print(term);
@@ -57,17 +62,17 @@ void map_dump(void)
 	fprintf(stderr, "---\n\n");
 }
 
-struct pqueue *map_to_pqueue(pqueue_cmp_pri_f cmppri, pqueue_get_pri_f getpri,
-			     pqueue_set_pos_f setpos)
+struct pqueue *map_to_pqueue(struct hashmap *map, pqueue_cmp_pri_f cmppri,
+			     pqueue_get_pri_f getpri, pqueue_set_pos_f setpos)
 {
-	size_t size = hashmap_count(all_terms) + 42;
+	size_t size = hashmap_count(map) + 42;
 	struct pqueue *queue = pqueue_init(size, cmppri, getpri, setpos);
 
 	size_t iter = 0;
 	void *iter_val;
-	while (hashmap_iter(all_terms, &iter, &iter_val)) {
+	while (hashmap_iter(map, &iter, &iter_val)) {
 		struct term *term = *(struct term **)iter_val;
-		if (term->type == APP) {
+		if (term->type == APP && term->u.app.lhs->type == ABS) {
 			pqueue_insert(queue, term);
 		}
 	}
diff --git a/src/parse.c b/src/parse.c
index 730ef44..d25034e 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -17,14 +17,15 @@ static struct term_handle abs_blc(char **term, size_t depth)
 	hash_t res = hash((uint8_t *)&res_type, sizeof(res_type), inner.hash);
 
 	struct term *res_term;
-	if ((res_term = map_get(res))) {
+	if ((res_term = map_get(map_all_terms(), res))) {
 		term_refer_head(res_term, depth);
 	} else {
 		res_term = term_new(res_type, res, depth);
 		res_term->u.abs.term = inner.term;
-		map_set(res_term, res);
+		map_set(map_all_terms(), res_term, res);
 	}
 
+	map_set(res_term->u.abs.term->parents, res_term, res_term->hash);
 	return (struct term_handle){ .term = res_term, .hash = res };
 }
 
@@ -38,15 +39,18 @@ static struct term_handle app_blc(char **term, size_t depth)
 	res = hash((uint8_t *)&res, sizeof(res), rhs.hash);
 
 	struct term *res_term;
-	if ((res_term = map_get(res))) {
+	if ((res_term = map_get(map_all_terms(), res))) {
 		term_refer_head(res_term, depth);
 	} else {
 		res_term = term_new(res_type, res, depth);
 		res_term->u.app.lhs = lhs.term;
 		res_term->u.app.rhs = rhs.term;
-		map_set(res_term, res);
+		map_set(map_all_terms(), res_term, res);
 	}
 
+	map_set(res_term->u.app.lhs->parents, res_term, res_term->hash);
+	map_set(res_term->u.app.rhs->parents, res_term, res_term->hash);
+
 	return (struct term_handle){ .term = res_term, .hash = res };
 }
 
@@ -56,12 +60,12 @@ static struct term_handle var_blc(int index, size_t depth)
 	hash_t res = hash((uint8_t *)&res_type, sizeof(res_type), index);
 
 	struct term *res_term;
-	if ((res_term = map_get(res))) {
+	if ((res_term = map_get(map_all_terms(), res))) {
 		term_refer_head(res_term, depth);
 	} else {
 		res_term = term_new(res_type, res, depth);
 		res_term->u.var.index = index;
-		map_set(res_term, res);
+		map_set(map_all_terms(), res_term, res);
 	}
 
 	return (struct term_handle){ .term = res_term, .hash = res };
diff --git a/src/reduce.c b/src/reduce.c
index f179ec4..1cfb520 100644
--- a/src/reduce.c
+++ b/src/reduce.c
@@ -6,14 +6,11 @@
 #include <term.h>
 #include <reduce.h>
 #include <log.h>
+#include <assert.h>
 
 static struct term *substitute(struct term *term, struct term *substitution,
 			       size_t level)
 {
-	/* term_print(term); */
-	/* fprintf(stderr, " <- "); */
-	/* term_print(substitution); */
-	/* fprintf(stderr, " @ %ld\n", level); */
 	if (term->type == VAR && term->u.var.index == level) {
 		return substitution;
 	} else if (term->type == ABS) {
@@ -21,9 +18,9 @@ static struct term *substitute(struct term *term, struct term *substitution,
 			substitute(term->u.abs.term, substitution, level + 1);
 		if (term->u.abs.term->hash == substitution->hash)
 			return term;
-		term_deref(term->u.abs.term);
+		/* term_deref(term->u.abs.term); */
 		struct term *rehashed = term_rehash_abs(term, new);
-		term_deref_head(term);
+		/* term_deref_head(term); */
 		return rehashed;
 	} else if (term->type == APP) {
 		struct term *lhs =
@@ -33,54 +30,23 @@ static struct term *substitute(struct term *term, struct term *substitution,
 		if (term->u.app.lhs->hash == substitution->hash &&
 		    term->u.app.rhs->hash == substitution->hash)
 			return term;
-		if (term->u.app.lhs->hash != substitution->hash)
-			term_deref(term->u.app.lhs);
-		if (term->u.app.rhs->hash != substitution->hash)
-			term_deref(term->u.app.rhs);
+		/* if (term->u.app.lhs->hash != substitution->hash) */
+		/* 	term_deref(term->u.app.lhs); */
+		/* if (term->u.app.rhs->hash != substitution->hash) */
+		/* 	term_deref(term->u.app.rhs); */
 		struct term *rehashed = term_rehash_app(term, lhs, rhs);
-		term_deref_head(term);
+		/* term_deref_head(term); */
 		return rehashed;
 	}
 	fatal("invalid type %d\n", term->type);
 }
 
-// APP: reduction of application
+// reduction of application
 // ([X],Y) -> X/Y
-//  (X,Y)  -> (RED(X),RED(Y))
-static struct term *reduce_app(struct term *term)
+void reduce(struct term *term)
 {
-	if (term->u.app.lhs->type == ABS) {
-		struct term *new = substitute(term->u.app.lhs->u.abs.term,
-					      term->u.app.rhs, -1);
-		term_deref_head(term);
-		return new;
-	} else {
-		struct term *lhs = reduce(term->u.app.lhs);
-		struct term *rhs = reduce(term->u.app.rhs);
-		return term_rehash_app(term, lhs, rhs);
-	}
-}
-
-// ABS: reduction of abstractions
-// [X] -> [RED(X)]
-static struct term *reduce_abs(struct term *term)
-{
-	struct term *inner = reduce(term->u.abs.term);
-	return term_rehash_abs(term, inner);
-}
+	assert(term->type == APP);
+	assert(term->u.app.lhs->type == ABS);
 
-// RED: main reduction
-// (X,Y) -> APP((X,Y))
-//  [X]  -> ABS([X])
-//   X   -> X
-struct term *reduce(struct term *term)
-{
-	if (term->type == APP) {
-		return reduce_app(term);
-	} else if (term->type == ABS) {
-		return reduce_abs(term);
-	} else if (term->type == VAR) {
-		return term;
-	}
-	fatal("invalid type %d\n", term->type);
+	substitute(term->u.app.lhs->u.abs.term, term->u.app.rhs, 0);
 }
diff --git a/src/schedule.c b/src/schedule.c
index dda08f3..3465752 100644
--- a/src/schedule.c
+++ b/src/schedule.c
@@ -6,10 +6,13 @@
 #include <stdlib.h>
 
 #include <schedule.h>
+#include <reduce.h>
 #include <lib/pqueue.h>
+#include <log.h>
 #include <parse.h>
 #include <map.h>
 
+// queue of beta-redexes: ([X], Y)
 static struct pqueue *queue;
 
 static pqueue_pri_t get_pri(void *a)
@@ -40,16 +43,18 @@ static size_t choose_position(void)
 void schedule(void)
 {
 	while (pqueue_size(queue) > 0) {
+		// TODO: check finished programs
 		size_t position = choose_position();
 		struct term *term = pqueue_pop_at(queue, position);
-		// TODO: reduce term
+		reduce(term);
 	}
+	debug("no more redexes!\n");
 }
 
 void schedule_init(void)
 {
 	srand(time(0));
-	queue = map_to_pqueue(cmp_pri, get_pri, set_pos);
+	queue = map_to_pqueue(map_all_terms(), cmp_pri, get_pri, set_pos);
 }
 
 void schedule_destroy(void)
diff --git a/src/term.c b/src/term.c
index 1479134..a240312 100644
--- a/src/term.c
+++ b/src/term.c
@@ -18,6 +18,7 @@ struct term *term_new(term_type_t type, hash_t hash, size_t depth)
 	term->refs = 1;
 	term->hash = hash;
 	term->depth = depth;
+	term->parents = hashmap_new(sizeof(struct term *), 0, 0);
 	return term;
 }
 
@@ -46,20 +47,18 @@ void term_print(struct term *term)
 
 struct term *term_rehash_abs(struct term *head, struct term *term)
 {
-	/* assert(head->u.abs.term->hash != term->hash); */
-
 	hash_t res =
 		hash((uint8_t *)&head->type, sizeof(head->type), term->hash);
 
 	assert(res != head->hash);
 
-	struct term *match = map_get(res);
+	struct term *match = map_get(map_all_terms(), res);
 	if (match) { // already exists
 		return match;
 	} else { // create new
 		struct term *new = term_new(ABS, res, head->depth);
 		new->u.abs.term = term;
-		map_set(new, res);
+		map_set(map_all_terms(), new, res);
 		return new;
 	}
 }
@@ -67,30 +66,20 @@ struct term *term_rehash_abs(struct term *head, struct term *term)
 struct term *term_rehash_app(struct term *head, struct term *lhs,
 			     struct term *rhs)
 {
-	/* assert(head->u.app.lhs->hash != lhs->hash || */
-	/*        head->u.app.rhs->hash != rhs->hash); */
-
 	hash_t res =
 		hash((uint8_t *)&head->type, sizeof(head->type), lhs->hash);
 	res = hash((uint8_t *)&res, sizeof(res), rhs->hash);
 
 	assert(res != head->hash);
 
-	struct term *match = map_get(res);
+	struct term *match = map_get(map_all_terms(), res);
 	if (match) { // already exists
-		/* term_refer(match, head->depth); */
-		/* term_deref(head); */
 		return match;
 	} else { // create new
 		struct term *new = term_new(APP, res, head->depth);
 		new->u.app.lhs = lhs;
 		new->u.app.rhs = rhs;
-		/* if (head->u.app.lhs->hash != lhs->hash) */
-		/* 	term_refer(lhs, head->depth + 1); */
-		/* if (head->u.app.rhs->hash != rhs->hash) */
-		/* 	term_refer(rhs, head->depth + 1); */
-		/* term_deref(head); */
-		map_set(new, res);
+		map_set(map_all_terms(), new, res);
 		return new;
 	}
 }
@@ -118,7 +107,8 @@ void term_deref_head(struct term *term)
 {
 	term->refs--;
 	if (term->refs == 0) {
-		map_delete(term);
+		map_delete(map_all_terms(), term);
+		map_destroy(term->parents);
 		free(term);
 	}
 }