diff options
| -rw-r--r-- | src/main.c | 135 | ||||
| -rw-r--r-- | src/test.c | 274 |
2 files changed, 286 insertions, 123 deletions
@@ -1,26 +1,33 @@ // Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +#ifndef TEST #include <stdio.h> +#define GC_PRINT_STATS 1 + #include <parse.h> -#include <term.h> #include <reducer.h> #include <gc.h> -#ifndef TEST static void callback(int i, char ch, void *data) { - printf("%d: %c\n", i, ch); + (void)i; + (void)ch; + (void)data; + /* printf("%d: %c\n", i, ch); */ } int main(void) { + GC_INIT(); + GC_enable_incremental(); + // Benchmarking test for memory leaks and stack overflows, will probably not return: "([(((0 [[((0 1) 0)]]) [(0 0)]) 0)] [[(1 (1 0))]])" struct term *term = parse("([(((0 [[((0 1) 0)]]) [(0 0)]) 0)] [[(1 (1 0))]])"); printf("\nReduced:\n"); - struct term *reduced = reduce(term, callback); + struct term *reduced = reduce(term, callback, 0); to_bruijn(reduced); print_term(reduced); printf("\n"); @@ -29,123 +36,5 @@ int main(void) return 0; } #else - -#ifndef NTESTS -#define NTESTS 6 -#endif - -#ifndef STARTTEST -#define STARTTEST 0 -#endif - -#define TESTDIR "./tests/" - -#include <stdlib.h> -#include <string.h> -#include <errno.h> -#include <time.h> - -struct test { - struct term *in; - struct term *res; - struct term *red; - char *trans; - struct { - int alpha; - int trans; - } equivalency; -}; - -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(int argc, char **argv) -{ - GC_INIT(); - - 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("=== 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); - } -} +static int testing; #endif 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 <dev@marvinborner.de> + +#ifdef TEST +#ifndef NTESTS +#define NTESTS 6 +#endif + +#ifndef STARTTEST +#define STARTTEST 0 +#endif + +#define TESTDIR "./tests/" + +#include <stdlib.h> +#include <string.h> +#include <errno.h> +#include <stdio.h> +#include <time.h> + +#include <gc.h> +#include <parse.h> +#include <term.h> +#include <reducer.h> + +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 |