From 4ace8342fb3044a122aa29a55c5a2e43ab733bf8 Mon Sep 17 00:00:00 2001 From: Marvin Borner Date: Mon, 20 Feb 2023 18:33:35 +0100 Subject: Moved tests to seperate file --- src/test.c | 274 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 274 insertions(+) create mode 100644 src/test.c (limited to 'src/test.c') diff --git a/src/test.c b/src/test.c new file mode 100644 index 0000000..c9023ea --- /dev/null +++ b/src/test.c @@ -0,0 +1,274 @@ +// Copyright (c) 2023, Marvin Borner + +#ifdef TEST +#ifndef NTESTS +#define NTESTS 6 +#endif + +#ifndef STARTTEST +#define STARTTEST 0 +#endif + +#define TESTDIR "./tests/" + +#include +#include +#include +#include +#include + +#include +#include +#include +#include + +struct test { + struct term *in; + struct term *res; + struct term *red; + char *trans; + struct { + int alpha; + int trans; + } equivalency; +}; + +static int name_generator(void) +{ + static int current = 0xbadbad; + return current++; +} + +static void *church(int n, void(*f(void *, int)), void *x, int name) +{ + if (n == 0) + return x; + return church(n - 1, f, f(x, name), name); +} + +static void *church_numeral_builder(void *x, int name) +{ + struct term *app = new_term(APP); + app->u.app.lhs = new_term(VAR); + app->u.app.lhs->u.var.name = name; + app->u.app.lhs->u.var.type = BARENDREGT_VARIABLE; + app->u.app.rhs = x; + return app; +} + +static struct term *church_numeral(int n) +{ + struct term *abs = new_term(ABS); + abs->u.abs.name = name_generator(); + abs->u.abs.term = new_term(ABS); + + struct term *var = new_term(VAR); + var->u.var.name = name_generator(); + var->u.var.type = BARENDREGT_VARIABLE; + + abs->u.abs.term->u.abs.name = var->u.var.name; + abs->u.abs.term->u.abs.term = + church(n, church_numeral_builder, var, abs->u.abs.name); + + return abs; +} + +static struct term *identity(void) +{ + struct term *abs = new_term(ABS); + abs->u.abs.name = name_generator(); + abs->u.abs.term = new_term(VAR); + abs->u.abs.term->u.var.name = abs->u.abs.name; + abs->u.abs.term->u.var.type = BARENDREGT_VARIABLE; + return abs; +} + +static struct term *omega(void) +{ + struct term *abs = new_term(ABS); + abs->u.abs.name = name_generator(); + abs->u.abs.term = new_term(APP); + abs->u.abs.term->u.app.lhs = new_term(VAR); + abs->u.abs.term->u.app.lhs->u.var.name = abs->u.abs.name; + abs->u.abs.term->u.app.lhs->u.var.type = BARENDREGT_VARIABLE; + abs->u.abs.term->u.app.rhs = new_term(VAR); + abs->u.abs.term->u.app.rhs->u.var.name = abs->u.abs.name; + abs->u.abs.term->u.app.rhs->u.var.type = BARENDREGT_VARIABLE; + return abs; +} + +static void counter_callback(int i, char ch, void *data) +{ + (void)ch; + *(int *)data = i; +} + +static void test_church_transitions(void) +{ + const int limit = 18; + + int deviations = 0; + double time = 0; + + for (int n = 1; n <= limit; n++) { + struct term *app = new_term(APP); + app->u.app.lhs = new_term(APP); + app->u.app.lhs->u.app.lhs = church_numeral(n); + app->u.app.lhs->u.app.rhs = church_numeral(2); + app->u.app.rhs = identity(); + int counter; + + clock_t begin = clock(); + struct term *red = reduce(app, counter_callback, &counter); + clock_t end = clock(); + time += (double)(end - begin) / CLOCKS_PER_SEC; + + free_term(red); + free_term(app); + + int expected = 10 * (2 << (n - 1)) + n * 5 + 5; + if (counter + 1 != expected) + deviations++; + } + + printf("Test church ((n 2) I) with n<=%d: %.5fs, %d transition deviations\n", + limit, time, deviations); +} + +static void test_explode(void) +{ + const int limit = 23; + + int deviations = 0; + double time = 0; + + for (int n = 1; n <= limit; n++) { + struct term *abs = new_term(ABS); + abs->u.abs.name = name_generator(); + abs->u.abs.term = new_term(APP); + abs->u.abs.term->u.app.lhs = new_term(APP); + abs->u.abs.term->u.app.lhs->u.app.lhs = church_numeral(n); + abs->u.abs.term->u.app.lhs->u.app.rhs = omega(); + abs->u.abs.term->u.app.rhs = new_term(VAR); + abs->u.abs.term->u.app.rhs->u.var.name = abs->u.abs.name; + abs->u.abs.term->u.app.rhs->u.var.type = BARENDREGT_VARIABLE; + + int counter; + + clock_t begin = clock(); + struct term *red = reduce(abs, counter_callback, &counter); + clock_t end = clock(); + time += (double)(end - begin) / CLOCKS_PER_SEC; + + free_term(red); + free_term(abs); + + int expected = 9 * n + 15; + if (counter + 1 != expected) + deviations++; + } + + printf("Test explode ((n ω) x) with n<=%d: %.5fs, %d transition deviations\n", + limit, time, deviations); +} + +static char *read_file(const char *path) +{ + FILE *f = fopen(path, "rb"); + if (!f) { + fprintf(stderr, "Can't open file %s: %s\n", path, + strerror(errno)); + return 0; + } + fseek(f, 0, SEEK_END); + long fsize = ftell(f); + fseek(f, 0, SEEK_SET); + + char *string = malloc(fsize + 1); + int ret = fread(string, fsize, 1, f); + fclose(f); + + if (ret != 1) { + fprintf(stderr, "Can't read file %s: %s\n", path, + strerror(errno)); + return 0; + } + + string[fsize] = 0; + return string; +} + +static void callback(int i, char ch, void *data) +{ + struct test *test = data; + if (ch != test->trans[i]) { + fprintf(stderr, "Transition deviation at index %d!\n", i); + test->equivalency.trans = 0; + } + /* fprintf(stderr, "\n%d: %c\n", i, ch); */ +} + +int main(void) +{ + GC_INIT(); + GC_enable_incremental(); + + struct test tests[NTESTS] = { 0 }; + + char in_template[] = TESTDIR "x.in"; + char red_template[] = TESTDIR "x.red"; + char trans_template[] = TESTDIR "x.trans"; + int offset = strlen(TESTDIR); + for (int i = 0; i < NTESTS; i++) { + char ch = '0' + i + 1 + STARTTEST; + in_template[offset] = ch; + red_template[offset] = ch; + trans_template[offset] = ch; + tests[i].trans = read_file(trans_template); + + char *in = read_file(in_template); + tests[i].in = parse(in); + free(in); + + char *red = read_file(red_template); + tests[i].red = parse(red); + to_bruijn(tests[i].red); + free(red); + + tests[i].equivalency.trans = 1; + } + + clock_t begin = clock(); + for (int i = 0; i < NTESTS; i++) { + tests[i].res = reduce(tests[i].in, callback, &tests[i]); + printf("Test %d done\n", i + 1 + STARTTEST); + } + clock_t end = clock(); + + for (int i = 0; i < NTESTS; i++) { + to_bruijn(tests[i].res); + tests[i].equivalency.alpha = + alpha_equivalency(tests[i].res, tests[i].red); + free_term(tests[i].res); + free_term(tests[i].red); + free(tests[i].trans); + } + + printf("\n=== REDUCTION SUMMARY ===\n"); + printf("Reduced tests in %.5fs\n", + (double)(end - begin) / CLOCKS_PER_SEC); + for (int i = 0; i < NTESTS; i++) { + if (tests[i].equivalency.alpha && tests[i].equivalency.trans) + continue; + printf("Test %d: [failed]\n\talpha-equivalency: %d\n\ttrans-equivalency: %d\n", + i + 1 + STARTTEST, tests[i].equivalency.alpha, + tests[i].equivalency.trans); + } + + printf("\n=== OTHER TESTS ===\n"); + test_church_transitions(); + test_explode(); +} +#else +static int no_testing; +#endif -- cgit v1.2.3