aboutsummaryrefslogtreecommitdiff
path: root/src/test.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/test.c')
-rw-r--r--src/test.c273
1 files changed, 0 insertions, 273 deletions
diff --git a/src/test.c b/src/test.c
deleted file mode 100644
index 9c2ecc3..0000000
--- a/src/test.c
+++ /dev/null
@@ -1,273 +0,0 @@
-// 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 <reduce.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 (λx.((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;
- }
-}
-
-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_bruijn(in);
- free(in);
-
- char *red = read_file(red_template);
- tests[i].red = parse_bruijn(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
-__attribute__((unused)) static int no_testing;
-#endif