1 files changed, 113 insertions, 1 deletions

diff --git a/src/term.c b/src/term.c
index d13ec9f..52f606b 100644
--- a/src/term.c
+++ b/src/term.c
@@ -1,8 +1,94 @@
 #include <stdlib.h>
+#include <assert.h>
 #include <stdio.h>
 
 #include <term.h>
 
+static int name_generator(void)
+{
+	static int current = 0x424242; // TODO: idk?
+	return current++;
+}
+
+#define MAX_CONVERSION_VARS 256
+static void to_barendregt_helper(struct term *term, int *vars, int size)
+{
+	assert(size < MAX_CONVERSION_VARS);
+	switch (term->type) {
+	case ABS:
+		vars[size] = name_generator();
+		term->u.abs.name = vars[size];
+		to_barendregt_helper(term->u.abs.term, vars, size + 1);
+		break;
+	case APP:
+		to_barendregt_helper(term->u.app.lhs, vars, size);
+		to_barendregt_helper(term->u.app.rhs, vars, size);
+		break;
+	case VAR:
+		if (term->u.var.type == BARENDREGT_VARIABLE)
+			break;
+		int ind = size - term->u.var.name - 1;
+		if (ind < 0) {
+			fprintf(stderr, "Unbound variable %d\n",
+				term->u.var.name);
+			term->u.var.name = name_generator();
+		} else {
+			term->u.var.name = vars[size - term->u.var.name - 1];
+		}
+		term->u.var.type = BARENDREGT_VARIABLE;
+		break;
+	default:
+		fprintf(stderr, "Invalid type %d\n", term->type);
+	}
+}
+
+static void to_bruijn_helper(struct term *term, int *vars, int size)
+{
+	assert(size < MAX_CONVERSION_VARS);
+	switch (term->type) {
+	case ABS:
+		vars[size] = term->u.abs.name;
+		to_bruijn_helper(term->u.abs.term, vars, size + 1);
+		term->u.abs.name = 0;
+		break;
+	case APP:
+		to_bruijn_helper(term->u.app.lhs, vars, size);
+		to_bruijn_helper(term->u.app.rhs, vars, size);
+		break;
+	case VAR:
+		if (term->u.var.type == BRUIJN_INDEX)
+			break;
+		int ind = -1;
+		for (int i = 0; i < size; i++) {
+			if (vars[i] == term->u.var.name) {
+				ind = i;
+				break;
+			}
+		}
+		if (ind < 0) {
+			fprintf(stderr, "Unbound variable %d\n",
+				term->u.var.name);
+		}
+		term->u.var.name = size - ind - 1;
+		term->u.var.type = BRUIJN_INDEX;
+		break;
+	default:
+		fprintf(stderr, "Invalid type %d\n", term->type);
+	}
+}
+
+void to_barendregt(struct term *term)
+{
+	int vars[MAX_CONVERSION_VARS] = { 0 };
+	to_barendregt_helper(term, vars, 0);
+}
+
+void to_bruijn(struct term *term)
+{
+	int vars[MAX_CONVERSION_VARS] = { 0 };
+	to_bruijn_helper(term, vars, 0);
+}
+
 struct term *new_term(term_type type)
 {
 	struct term *term = calloc(1, sizeof(*term));
@@ -38,7 +124,10 @@ void print_term(struct term *term)
 {
 	switch (term->type) {
 	case ABS:
-		printf("[{%d} ", term->u.abs.name);
+		if (term->u.abs.name)
+			printf("[{%d} ", term->u.abs.name);
+		else
+			printf("[");
 		print_term(term->u.abs.term);
 		printf("]");
 		break;
@@ -56,3 +145,26 @@ void print_term(struct term *term)
 		fprintf(stderr, "Invalid type %d\n", term->type);
 	}
 }
+
+void print_scheme(struct term *term)
+{
+	switch (term->type) {
+	case ABS:
+		printf("(*lam \"%d\" ", term->u.abs.name);
+		print_scheme(term->u.abs.term);
+		printf(")");
+		break;
+	case APP:
+		printf("(*app ");
+		print_scheme(term->u.app.lhs);
+		printf(" ");
+		print_scheme(term->u.app.rhs);
+		printf(")");
+		break;
+	case VAR:
+		printf("(*var \"%d\")", term->u.var.name);
+		break;
+	default:
+		fprintf(stderr, "Invalid type %d\n", term->type);
+	}
+}