Add translation mode and statisticsHEADmain

9 files changed, 362 insertions, 15 deletions

diff --git a/src/abs.c b/src/impl/abs.c
index a6aa76d..a6aa76d 100644
--- a/src/abs.c
+++ b/src/impl/abs.c
diff --git a/src/impl/abs_app_right.c b/src/impl/abs_app_right.c
new file mode 100644
index 0000000..a346013
--- /dev/null
+++ b/src/impl/abs_app_right.c
@@ -0,0 +1,104 @@
+// Copyright (c) 2024, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#include <log.h>
+#include <impl.h>
+
+// my blc 3 for now!
+
+static void encode(Term *term, FILE *fp)
+{
+	switch (term->type) {
+	case ABS:
+		while (1) {
+			fprintf(fp, "0");
+			if (term->u.abs.body->type != ABS)
+				break;
+			term = term->u.abs.body;
+		}
+		fprintf(fp, "10");
+		encode(term->u.abs.body, fp);
+		break;
+	case APP:;
+		Term *stack[128] = { 0 }; // TODO: HEAP!
+		int stacked = 0;
+
+		while (1) {
+			fprintf(fp, "0");
+			stack[stacked++] = term->u.app.rhs;
+			term = term->u.app.lhs;
+			if (term->type != APP)
+				break;
+		}
+
+		fprintf(fp, "11");
+		encode(term, fp);
+		for (int i = stacked - 1; i >= 0; i--)
+			encode(stack[i], fp);
+		break;
+	case IDX:
+		for (size_t i = 0; i <= term->u.index; i++)
+			fprintf(fp, "1");
+		fprintf(fp, "0");
+		break;
+	default:
+		fatal("invalid type %d\n", term->type);
+	}
+}
+
+static Term *decode(FILE *fp)
+{
+	Term *res = 0;
+
+	char a = getc(fp);
+
+	if (a == '0') {
+		size_t count = 0;
+		while (getc(fp) == '0')
+			count++;
+
+		char b = getc(fp);
+
+		if (b == '0') {
+			Term *head = term_new(ABS);
+
+			res = head;
+			for (size_t i = 0; i < count; i++) {
+				res->u.abs.body = term_new(ABS);
+				res = res->u.abs.body;
+			}
+			res->u.abs.body = decode(fp);
+			res = head;
+		} else if (b == '1') {
+			res = term_new(APP);
+			res->u.app.lhs = decode(fp);
+			res->u.app.rhs = decode(fp);
+
+			for (size_t i = 0; i < count; i++) {
+				Term *prev = res;
+				res = term_new(APP);
+				res->u.app.lhs = prev;
+				res->u.app.rhs = decode(fp);
+			}
+		}
+	} else if (a == '1') {
+		res = term_new(IDX);
+		res->u.index = 0;
+		while (getc(fp) == '1')
+			res->u.index++;
+	}
+
+	if (!res)
+		fatal("invalid parsing state!\n");
+
+	return res;
+}
+
+Impl impl_abs_app_left(void)
+{
+	return (Impl){
+		.name = "abs_app_left",
+		.encode = encode,
+		.decode = decode,
+	};
+}
diff --git a/src/impl/app_both.c b/src/impl/app_both.c
new file mode 100644
index 0000000..47f78aa
--- /dev/null
+++ b/src/impl/app_both.c
@@ -0,0 +1,112 @@
+// Copyright (c) 2024, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#include <log.h>
+#include <impl.h>
+
+static void encode(Term *term, FILE *fp)
+{
+	switch (term->type) {
+	case ABS:
+		fprintf(fp, "01");
+		encode(term->u.abs.body, fp);
+		break;
+	case APP:
+		fprintf(fp, "0");
+
+		Term *stack[128] = { 0 }; // TODO: HEAP!
+		int stacked = 0;
+
+		// TODO: there's probably something here about finding optimal
+		//       left/right folds but this is ok for now
+
+		int fold_right = term->u.app.rhs->type == APP;
+
+		while (1) {
+			fprintf(fp, "0");
+			stack[stacked++] =
+				fold_right ? term->u.app.lhs : term->u.app.rhs;
+			term = fold_right ? term->u.app.rhs : term->u.app.lhs;
+			if (term->type != APP)
+				break;
+		}
+
+		fprintf(fp, "1%d", fold_right);
+		if (fold_right) {
+			for (int i = 0; i < stacked; i++)
+				encode(stack[i], fp);
+			encode(term, fp);
+		} else {
+			encode(term, fp);
+			for (int i = stacked - 1; i >= 0; i--)
+				encode(stack[i], fp);
+		}
+		break;
+	case IDX:
+		for (size_t i = 0; i <= term->u.index; i++)
+			fprintf(fp, "1");
+		fprintf(fp, "0");
+		break;
+	default:
+		fatal("invalid type %d\n", term->type);
+	}
+}
+
+static Term *decode(FILE *fp)
+{
+	Term *res = 0;
+
+	char a = getc(fp);
+
+	if (a == '0') {
+		size_t count = 0;
+		while (getc(fp) == '0')
+			count++;
+
+		if (count == 0) {
+			res = term_new(ABS);
+			res->u.abs.body = decode(fp);
+		} else if (getc(fp) == '1') { // fold right
+			Term *head = term_new(APP);
+			res = head;
+			for (size_t i = 0; i < count - 1; i++) {
+				res->u.app.lhs = decode(fp);
+				res->u.app.rhs = term_new(APP);
+				res = res->u.app.rhs;
+			}
+			res->u.app.lhs = decode(fp);
+			res->u.app.rhs = decode(fp);
+			res = head;
+		} else { // fold left
+			res = term_new(APP);
+			res->u.app.lhs = decode(fp);
+			res->u.app.rhs = decode(fp);
+
+			for (size_t i = 0; i < count - 1; i++) {
+				Term *prev = res;
+				res = term_new(APP);
+				res->u.app.lhs = prev;
+				res->u.app.rhs = decode(fp);
+			}
+		}
+	} else if (a == '1') {
+		res = term_new(IDX);
+		res->u.index = 0;
+		while (getc(fp) == '1')
+			res->u.index++;
+	}
+
+	if (!res)
+		fatal("invalid parsing state!\n");
+
+	return res;
+}
+
+Impl impl_app_both(void)
+{
+	return (Impl){
+		.name = "app_both",
+		.encode = encode,
+		.decode = decode,
+	};
+}
diff --git a/src/app.c b/src/impl/app_left.c
index cc7eda9..dcc62cd 100644
--- a/src/app.c
+++ b/src/impl/app_left.c
@@ -79,10 +79,10 @@ static Term *decode(FILE *fp)
 	return res;
 }
 
-Impl impl_app(void)
+Impl impl_app_left(void)
 {
 	return (Impl){
-		.name = "app",
+		.name = "app_left",
 		.encode = encode,
 		.decode = decode,
 	};
diff --git a/src/impl/app_right.c b/src/impl/app_right.c
new file mode 100644
index 0000000..2583741
--- /dev/null
+++ b/src/impl/app_right.c
@@ -0,0 +1,89 @@
+// Copyright (c) 2024, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#include <log.h>
+#include <impl.h>
+
+static void encode(Term *term, FILE *fp)
+{
+	switch (term->type) {
+	case ABS:
+		fprintf(fp, "01");
+		encode(term->u.abs.body, fp);
+		break;
+	case APP:
+		fprintf(fp, "0");
+
+		Term *stack[128] = { 0 }; // TODO: HEAP!
+		int stacked = 0;
+
+		while (1) {
+			fprintf(fp, "0");
+			stack[stacked++] = term->u.app.lhs;
+			term = term->u.app.rhs;
+			if (term->type != APP)
+				break;
+		}
+
+		fprintf(fp, "1");
+		for (int i = 0; i < stacked; i++)
+			encode(stack[i], fp);
+		encode(term, fp);
+		break;
+	case IDX:
+		for (size_t i = 0; i <= term->u.index; i++)
+			fprintf(fp, "1");
+		fprintf(fp, "0");
+		break;
+	default:
+		fatal("invalid type %d\n", term->type);
+	}
+}
+
+static Term *decode(FILE *fp)
+{
+	Term *res = 0;
+
+	char a = getc(fp);
+
+	if (a == '0') {
+		size_t count = 0;
+		while (getc(fp) == '0')
+			count++;
+
+		if (count == 0) {
+			res = term_new(ABS);
+			res->u.abs.body = decode(fp);
+		} else {
+			Term *head = term_new(APP);
+			res = head;
+			for (size_t i = 0; i < count - 1; i++) {
+				res->u.app.lhs = decode(fp);
+				res->u.app.rhs = term_new(APP);
+				res = res->u.app.rhs;
+			}
+			res->u.app.lhs = decode(fp);
+			res->u.app.rhs = decode(fp);
+			res = head;
+		}
+	} else if (a == '1') {
+		res = term_new(IDX);
+		res->u.index = 0;
+		while (getc(fp) == '1')
+			res->u.index++;
+	}
+
+	if (!res)
+		fatal("invalid parsing state!\n");
+
+	return res;
+}
+
+Impl impl_app_right(void)
+{
+	return (Impl){
+		.name = "app_right",
+		.encode = encode,
+		.decode = decode,
+	};
+}
diff --git a/src/impl/merged_abs.c b/src/impl/merged_abs.c
deleted file mode 100644
index e69de29..0000000
--- a/src/impl/merged_abs.c
+++ /dev/null
diff --git a/src/impl/merged_app.c b/src/impl/merged_app.c
deleted file mode 100644
index e69de29..0000000
--- a/src/impl/merged_app.c
+++ /dev/null
diff --git a/src/impl/merged_both.c b/src/impl/merged_both.c
deleted file mode 100644
index e69de29..0000000
--- a/src/impl/merged_both.c
+++ /dev/null
diff --git a/src/main.c b/src/main.c
index 75dbb6a..9609142 100644
--- a/src/main.c
+++ b/src/main.c
@@ -5,13 +5,15 @@
 #include <stdio.h>
 #include <dirent.h>
 #include <sys/stat.h>
+#include <string.h>
 
 #include <term.h>
 #include <parse.h>
+#include <log.h>
 #include <print.h>
 #include <impl.h>
 
-#define N_IMPLS 5
+#define N_IMPLS 8
 
 static size_t file_size(FILE *fp)
 {
@@ -36,6 +38,8 @@ static size_t test_impl(Impl impl, Term *term, FILE *out)
 
 static void test_all(Impl impls[N_IMPLS], const char *dir_path, FILE *out)
 {
+	double results[N_IMPLS] = { 0 };
+
 	char path[1024];
 	struct dirent *dir_entry;
 	DIR *dir = opendir(dir_path);
@@ -44,7 +48,7 @@ static void test_all(Impl impls[N_IMPLS], const char *dir_path, FILE *out)
 			continue;
 
 		sprintf(path, "%s/%s", dir_path, dir_entry->d_name);
-		printf("%s\n", path);
+		debug("%s\n", path);
 
 		FILE *fp = fopen(path, "rb");
 
@@ -53,33 +57,71 @@ static void test_all(Impl impls[N_IMPLS], const char *dir_path, FILE *out)
 		for (Impl *impl = impls; impl != impls + N_IMPLS; impl++) {
 			size_t prev = file_size(fp);
 			size_t after = test_impl(*impl, term, out);
-			printf("%s: %lu -> %lu (%f%% reduction)\n", impl->name,
-			       prev, after,
-			       (double)((long)prev - (long)after) /
-				       (double)prev * 100);
+			double change = (double)((long)prev - (long)after) /
+					(double)prev * 100;
+			debug("%s: %lu -> %lu (%f%% reduction)\n", impl->name,
+			      prev, after, change);
+			results[impl - impls] += change;
+			results[impl - impls] /= 2.0;
 		}
 
 		term_free(term);
 		fclose(fp);
 
-		printf("\n");
+		debug("\n");
 	}
 	closedir(dir);
+
+	printf("\n--- %s ---\n", dir_path);
+	for (size_t i = 0; i < N_IMPLS; i++)
+		printf("%s: avg. %f%% reduction\n", impls[i].name, results[i]);
 }
 
-int main(void)
+static void test(Impl impls[N_IMPLS])
 {
-	Impl impls[N_IMPLS] = { impl_blc(), impl_blc2(), impl_closed(),
-				impl_abs(), impl_app() };
-
 	FILE *out = tmpfile();
 
 	const char *dir_path = "test/small";
 	test_all(impls, dir_path, out);
 	dir_path = "test/medium";
 	test_all(impls, dir_path, out);
-	/* dir_path = "test/large"; */
-	/* test_all(impls, dir_path, out); */
+	dir_path = "test/large";
+	test_all(impls, dir_path, out);
 
 	fclose(out);
 }
+
+static Impl find_impl(const char *impl, Impl impls[N_IMPLS])
+{
+	for (int i = 0; i < N_IMPLS; i++) {
+		if (!strcmp(impl, impls[i].name))
+			return impls[i];
+	}
+	fatal("encoding '%s' not found!\n", impl);
+}
+
+int main(int argc, char *argv[])
+{
+#ifdef DEBUG
+	debug_enable(DEBUG);
+#endif
+	Impl impls[N_IMPLS] = { impl_blc(),	 impl_blc2(),
+				impl_closed(),	 impl_abs(),
+				impl_app_left(), impl_app_right(),
+				impl_app_both(), impl_abs_app_left() };
+	if (argc == 1) {
+		test(impls);
+		return 0;
+	}
+
+	if (argc != 3) {
+		fatal("invalid arguments, please use `blc2blc <from> <to>`\n");
+	}
+
+	Impl from = find_impl(argv[1], impls);
+	Impl to = find_impl(argv[2], impls);
+	Term *term = from.decode(stdin);
+	to.encode(term, stdout);
+
+	return 0;
+}