From 96ecf29e8be977f51f351308ef2c7c492bb829aa Mon Sep 17 00:00:00 2001 From: Ethan Werner Date: Tue, 9 Jun 2026 01:17:41 +0400 Subject: refactor --- example/Makefile | 20 +++ example/ann_xor.c | 41 +++-- example/bin.c | 44 +++-- example/buffer.c | 22 +++ example/build | 6 - example/direct.c | 19 +- example/escape.c | 93 +++++----- example/genetic_ann.c | 102 +++++++---- example/genetic_char.c | 64 ++++--- example/genetic_pushdown_btc.c | 173 ++++++++++++++++++ example/genetic_pushdown_btc.txt | 366 +++++++++++++++++++++++++++++++++++++++ example/pool.c | 18 +- example/pushdown.c | 16 +- example/stack.c | 29 ++-- example/ufo.c | 22 +++ 15 files changed, 880 insertions(+), 155 deletions(-) create mode 100644 example/Makefile mode change 100755 => 100644 example/ann_xor.c mode change 100755 => 100644 example/bin.c create mode 100644 example/buffer.c delete mode 100755 example/build mode change 100755 => 100644 example/escape.c mode change 100755 => 100644 example/genetic_ann.c mode change 100755 => 100644 example/genetic_char.c create mode 100644 example/genetic_pushdown_btc.c create mode 100644 example/genetic_pushdown_btc.txt mode change 100755 => 100644 example/pool.c create mode 100755 example/ufo.c (limited to 'example') diff --git a/example/Makefile b/example/Makefile new file mode 100644 index 0000000..67a7746 --- /dev/null +++ b/example/Makefile @@ -0,0 +1,20 @@ +CC = gcc +CFLAGS = -Wall -Wextra -Werror -pedantic -std=c99 -O2 -D_FORTIFY_SOURCE=2 -fstack-protector-strong -Wformat-security -Wnull-dereference -I ../include +LDFLAGS = -lm + +EXAMPLES = ann_xor buffer bin direct escape genetic_ann genetic_char \ + genetic_pushdown_btc pool pushdown stack ufo + +.PHONY: all clean run + +all: $(EXAMPLES) + +%: %.c + $(CC) $(CFLAGS) -o $@ $< $(LDFLAGS) + +clean: + rm -f $(EXAMPLES) + +run: all + @for ex in $(EXAMPLES); do \ + echo ">>> $$ex"; ./$$ex; echo; done diff --git a/example/ann_xor.c b/example/ann_xor.c old mode 100755 new mode 100644 index a39264c..ac1623e --- a/example/ann_xor.c +++ b/example/ann_xor.c @@ -1,4 +1,4 @@ -// example_xor.c - Example XOR training +// ann_xor.c - Example: training an ANN to solve XOR using backpropagation #define ANN_IMPLEMENTATION #include "../include/ann.h" @@ -10,39 +10,44 @@ int main(void) { srand(time(0)); - ann_t *ann = ann_init(3, (uint_t[]){2, 2, 1}); - ann_set_activation(ann, SIGMOID, SIGMOID); - ann_random(ann); + ann_t ann = {0}; + if (!ann_init(&ann, 3, (u64[]){2, 2, 1})) { + fprintf(stderr, "Failed to init ann\n"); + return 1; + } + ann_set_activation(&ann, SIGMOID, SIGMOID); + ann_random(&ann); - fp_t input[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}}; - fp_t output[4] = {0, 0, 0, 0}; - fp_t expected[4] = {0, 1, 1, 0}; - fp_t error = 0; + f64 input[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}}; + f64 output[4] = {0, 0, 0, 0}; + f64 expected[4] = {0, 1, 1, 0}; - for (int_t iteration = 0; iteration < 100000; iteration++) { - for (int_t training = 0; training < 4; training++) { - ann_propagation_forward(ann, (fp_t const *const)&input[training], + for (i64 iteration = 0; iteration < 100000; iteration++) { + for (i64 training = 0; training < 4; training++) { + ann_propagation_forward(&ann, (f64 const *const)&input[training], &output[training]); - error += ann_error_total(&output[training], &expected[training], - ann->layer_neuron_n[ann->layer_n - 1]); + (void)ann_error_total(&output[training], &expected[training], + ann.layer_neuron_n[ann.layer_n - 1]); // Train using backpropagation - ann_propagation_backward(ann, (fp_t const *const)&input[training], + ann_propagation_backward(&ann, (f64 const *const)&input[training], &output[training], &expected[training], 0.4); // Train using numeric integration - // ann_train_numeric( ann, ( fp_t const * const ) &i[b], &t[b], 0.03 ); + // ann_train_numeric( ann, ( f64 const * const ) &i[b], &t[b], 0.03 ); } } - ann_print_weight(ann); + ann_print_weight(&ann); fputs("------------------------------------------------------------\n\n", stderr); for (int i = 0; i < 4; i++) { - ann_propagation_forward(ann, (fp_t const *const)&input[i], &output[i]); - ann_print_neuron(ann, (fp_t const *const)&input[i], &output[i]); + ann_propagation_forward(&ann, (f64 const *const)&input[i], &output[i]); + ann_print_neuron(&ann, (f64 const *const)&input[i], &output[i]); } + + ann_free(&ann); } diff --git a/example/bin.c b/example/bin.c old mode 100755 new mode 100644 index 40a7f77..7be43c1 --- a/example/bin.c +++ b/example/bin.c @@ -1,47 +1,67 @@ +// bin.c - Example usage of bin.h flat file block storage + +#include +#include #include #include +#include typedef int32_t bin_key_t; +#define BIN_IMPLEMENTATION +#include "../include/bin.h" + #define TEST_LENGTH 10 #define TEST_START -2 -#define TEST_STEP 0.5; struct sample_t { bin_key_t time; double data; }; -#define BIN_IMPLEMENTATION -#include "../include/bin.h" - -int main() { +int main(void) { char const *path = "./test.bin"; FILE *bin = bin_init(path, sizeof(struct sample_t)); + if (!bin) { + fprintf(stderr, "Failed to initialize binary file\n"); + return 1; + } bin_key_t half = (bin_key_t)((TEST_START + TEST_LENGTH) / 2.0); // Insert half of the values using bin_insert() for (bin_key_t i = half - 1; i >= TEST_START; i--) { - bin_insert(bin, 0, &(struct sample_t){.time = i, .data = 2.0 * i}, 1); + struct sample_t sample = {.time = i, .data = 2.0 * i}; + bin_insert(bin, 0, &sample, 1); } // Append half of the values to the end for (bin_key_t i = half; i < TEST_START + TEST_LENGTH; i++) { - bin_append(bin, &(struct sample_t){.time = i, .data = 2.0 * i}, 1); + struct sample_t sample = {.time = i, .data = 2.0 * i}; + bin_append(bin, &sample, 1); } uint64_t l = bin_length(bin); - uint64_t bs = bin_block_size(bin); + (void)bin_block_size(bin); - struct sample_t x[l]; + assert(l < 1000000); + struct sample_t *x = calloc(l, sizeof(struct sample_t)); + if (!x) { + fprintf(stderr, "Failed to allocate memory\n"); + bin_close(bin); + return 1; + } bin_read(bin, 0, x, l); // Test that all values are correct - for (int32_t i = 0; i < TEST_LENGTH; i++) { - bin_key_t key = TEST_START + i; - assert(x[i].time == key && x[i].data == 2.0 * key); + for (uint32_t i = 0; i < TEST_LENGTH; i++) { + bin_key_t key = TEST_START + (int32_t)i; + assert(x[i].time == key); + assert(fabs(x[i].data - 2.0 * key) < 1e-9); } + free(x); bin_close(bin); + remove(path); + return 0; } \ No newline at end of file diff --git a/example/buffer.c b/example/buffer.c new file mode 100644 index 0000000..35237b2 --- /dev/null +++ b/example/buffer.c @@ -0,0 +1,22 @@ +// buffer.c - Example usage of buffer.h dynamic buffer + +#define BUFFER_IMPLEMENTATION +#include "../include/buffer.h" + +#include +#include +#include + +int main(void) { + void *buf = buffer_malloc(10, sizeof(int)); + if (!buf) { + fprintf(stderr, "Failed to allocate buffer\n"); + return 1; + } + + printf("capacity: %" PRIu64 "\n", buffer_capacity(buf)); + printf("size: %" PRIu64 "\n", buffer_count(buf)); + + buffer_free(buf); + return 0; +} diff --git a/example/build b/example/build deleted file mode 100755 index b6c600f..0000000 --- a/example/build +++ /dev/null @@ -1,6 +0,0 @@ -EXAMPLES=$(ls -1 --color=never *.c | sed 's/\.c//') - -for EXAMPLE in $EXAMPLES -do - gcc -g -fno-fast-math -O0 -o $EXAMPLE $EXAMPLE.c -lm -done diff --git a/example/direct.c b/example/direct.c index 102c0c3..29da5d3 100644 --- a/example/direct.c +++ b/example/direct.c @@ -1,7 +1,12 @@ -typedef double value_t; + +// direct.c - Example usage of direct.h computation graph + +#include + +typedef double direct_value_t; + #define DT_IMPLEMENTATION #include "../include/direct.h" -#include int main() { node_t x0 = {.x = 0.0, .function = dt_add}; @@ -20,7 +25,7 @@ int main() { dt_connect(&x3, &x4); dt_connect(&x4, &x5); dt_connect(&x4, &x6); - dt_connect(&x5, &x2); + dt_connect(&x5, &x6); dt_update_trace(&x0); printf("data: %lf\n", x0.x); @@ -29,5 +34,13 @@ int main() { dt_update_trace(&x0); printf("data: %lf\n", x0.x); + dt_clear_edges(&x0); + dt_clear_edges(&x1); + dt_clear_edges(&x2); + dt_clear_edges(&x3); + dt_clear_edges(&x4); + dt_clear_edges(&x5); + dt_clear_edges(&x6); + return 0; } \ No newline at end of file diff --git a/example/escape.c b/example/escape.c old mode 100755 new mode 100644 index c5e71ac..99f686a --- a/example/escape.c +++ b/example/escape.c @@ -1,6 +1,5 @@ // escape.c - Simple test print code - #include #include @@ -9,54 +8,56 @@ #define TEST_STRING "HELLO" -void hsv_rgb( float h, float s, float v, uint8_t *r, uint8_t *g, uint8_t *b ) -{ - float h0 = h * 6.0; +void hsv_rgb(float h, float s, float v, uint8_t *r, uint8_t *g, uint8_t *b) { + float h0 = h * 6.0f; - float k = fmod( 5.0 + h0, 6.0 ); - *r = 255 * ( v - v * s * fmax( 0.0, fmin( k, fmin( 4.0 - k, 1.0 ) ) ) ); + float k = fmodf(5.0f + h0, 6.0f); + *r = (uint8_t)(255.0f * (v - v * s * fmaxf(0.0f, fminf(k, fminf(4.0f - k, 1.0f))))); - k = fmod( 3.0 + h0, 6.0 ); - *g = 255 * ( v - v * s * fmax( 0.0, fmin( k, fmin( 4.0 - k, 1.0 ) ) ) ); + k = fmodf(3.0f + h0, 6.0f); + *g = (uint8_t)(255.0f * (v - v * s * fmaxf(0.0f, fminf(k, fminf(4.0f - k, 1.0f))))); - k = fmod( 1.0 + h0, 6.0 ); - *b = 255 * ( v - v * s * fmax( 0.0, fmin( k, fmin( 4.0 - k, 1.0 ) ) ) ); + k = fmodf(1.0f + h0, 6.0f); + *b = (uint8_t)(255.0f * (v - v * s * fmaxf(0.0f, fminf(k, fminf(4.0f - k, 1.0f))))); } - -int main( void ) -{ - // Clear screen - fputs( ESC_CLEAR_SCREEN, stdout ); - - // Print a rectangle of Xs with positional coordinates - fputs( ESC_CURSOR_POSITION( 1, 1 ), stdout ); fflush( stdout ); - fputs( ESC_CURSOR_POSITION( 3, 2 ) "X", stdout ); fflush( stdout ); - fputs( ESC_CURSOR_POSITION( 10, 2 ) "X", stdout ); fflush( stdout ); - fputs( ESC_CURSOR_POSITION( 10, 4 ) "X", stdout ); fflush( stdout ); - fputs( ESC_CURSOR_POSITION( 3, 4 ) "X", stdout ); fflush( stdout ); - fputs( "\n", stdout ); - - fputs( "\n" ESC_RESET TEST_STRING "\n\n", stdout ); - fputs( ESC_BOLD TEST_STRING ESC_RESET "\n\n", stdout ); - fputs( ESC_OVERLINE TEST_STRING ESC_RESET "\n\n", stdout ); - fputs( ESC_UNDERLINE TEST_STRING ESC_RESET "\n\n", stdout ); - fputs( ESC_STRIKETHROUGH TEST_STRING ESC_RESET "\n\n", stdout ); - fputs( ESC_COLOR_FG_RGB( 0, 128, 128 ) TEST_STRING ESC_RESET "\n\n", stdout ); - fputs( ESC_COLOR_BG_RGB( 128, 0, 128 ) TEST_STRING ESC_RESET "\n\n", stdout ); - fputs( ESC_BLINK TEST_STRING ESC_RESET "\n\n", stdout ); - fputs( ESC_REVERSE TEST_STRING ESC_RESET "\n\n", stdout ); - fputs( ESC_CONCEAL TEST_STRING ESC_REVEAL TEST_STRING ESC_RESET "\n\n", stdout ); - - uint8_t r,g,b; - - for( float i = 0; i < 1; i += 0.01 ) - { - hsv_rgb( i, 1.0, 1.0, &r, &g, &b ); - - esc_color_fg_rgb( r, g, b ); - fputs( "█", stdout ); - } - - fputs( "\n", stdout ); +int main(void) { + // Clear screen + fputs(ESC_CLEAR_SCREEN, stdout); + + // Print a rectangle of Xs with positional coordinates + fputs(ESC_CURSOR_POSITION(1, 1), stdout); + fflush(stdout); + fputs(ESC_CURSOR_POSITION(3, 2) "X", stdout); + fflush(stdout); + fputs(ESC_CURSOR_POSITION(10, 2) "X", stdout); + fflush(stdout); + fputs(ESC_CURSOR_POSITION(10, 4) "X", stdout); + fflush(stdout); + fputs(ESC_CURSOR_POSITION(3, 4) "X", stdout); + fflush(stdout); + fputs("\n", stdout); + + fputs("\n" ESC_RESET TEST_STRING "\n\n", stdout); + fputs(ESC_BOLD TEST_STRING ESC_RESET "\n\n", stdout); + fputs(ESC_OVERLINE TEST_STRING ESC_RESET "\n\n", stdout); + fputs(ESC_UNDERLINE TEST_STRING ESC_RESET "\n\n", stdout); + fputs(ESC_STRIKETHROUGH TEST_STRING ESC_RESET "\n\n", stdout); + fputs(ESC_COLOR_FG_RGB(0, 128, 128) TEST_STRING ESC_RESET "\n\n", stdout); + fputs(ESC_COLOR_BG_RGB(128, 0, 128) TEST_STRING ESC_RESET "\n\n", stdout); + fputs(ESC_BLINK TEST_STRING ESC_RESET "\n\n", stdout); + fputs(ESC_REVERSE TEST_STRING ESC_RESET "\n\n", stdout); + fputs(ESC_CONCEAL TEST_STRING ESC_REVEAL TEST_STRING ESC_RESET "\n\n", + stdout); + + uint8_t r, g, b; + + for (float i = 0; i < 1; i += 0.01f) { + hsv_rgb(i, 1.0, 1.0, &r, &g, &b); + + esc_color_fg_rgb(r, g, b); + fputs("█", stdout); + } + + fputs("\n", stdout); } diff --git a/example/genetic_ann.c b/example/genetic_ann.c old mode 100755 new mode 100644 index 071ccf5..85dd520 --- a/example/genetic_ann.c +++ b/example/genetic_ann.c @@ -1,5 +1,8 @@ +// genetic_ann.c - Example training of an XOR neural network by genetic algorithm + #include #include +#include #include #include @@ -8,7 +11,7 @@ #define POPULATION_N 100 #define RATE_SELECTION 0.2 -#define RATE_MUTATON 10 +#define RATE_MUTATION 0.2 #define MAGNITUDE_MUTATION 0.01 #define ERROR 0.00001 @@ -18,12 +21,12 @@ typedef ann_t *ga_individual_t; #include "../include/genetic.h" double fitness(ann_t *const x, void const *c) { - fp_t *i = *((fp_t **)c); - fp_t *t = *((fp_t **)c + 1); - fp_t o[4]; + f64 *i = *((f64 **)c); + f64 *t = *((f64 **)c + 1); + f64 o[4]; - fp_t e = 0, sum = 0; - for (uint_t b = 0; b < 4; b++) { + f64 e = 0, sum = 0; + for (u64 b = 0; b < 4; b++) { ann_propagation_forward(x, &i[2 * b], &o[b]); e = ann_error_total(&o[b], &t[b], x->layer_neuron_n[x->layer_n - 1]); sum += e; @@ -33,46 +36,76 @@ double fitness(ann_t *const x, void const *c) { } void crossover(ann_t **y, ann_t *x0, ann_t *x1) { - uint32_t i_crossover = rand() % x0->weight_n; - memcpy((*y)->weight, x0->weight, i_crossover * sizeof(fp_t)); - memcpy((*y)->weight + i_crossover, x1->weight + i_crossover, - (x0->weight_n - i_crossover) * sizeof(fp_t)); + if (!y || !x0 || !x1 || !*y) + return; + if (x0->weight_n == 0 || x1->weight_n == 0) + return; + ann_t *child = (ann_t *)*y; + if (child->weight_n == 0) + return; + uint32_t i = rand() % x0->weight_n; + u64 max_copy = child->weight_n < x0->weight_n ? child->weight_n : x0->weight_n; + max_copy = max_copy < x1->weight_n ? max_copy : x1->weight_n; + u64 safe_i = i >= max_copy ? max_copy - 1 : (u64)i; + + memcpy(child->weight, x0->weight, safe_i * sizeof(f64)); + memcpy(child->weight + safe_i, x1->weight + safe_i, (max_copy - safe_i) * sizeof(f64)); + if (child->weight_n > max_copy) { + memset(child->weight + max_copy, 0, (child->weight_n - max_copy) * sizeof(f64)); + } } -void mutate(ann_t *x) { - uint32_t i_mutation = rand() % x->weight_n; - fp_t r = - (2 * (MAGNITUDE_MUTATION * (fp_t)rand() / RAND_MAX)) - MAGNITUDE_MUTATION; - x->weight[i_mutation] += r; +void mutate(ann_t **x) { + if (!x || !*x || (*x)->weight_n == 0) + return; + uint32_t i_mutation = rand() % (*x)->weight_n; + f64 r = + (2 * (MAGNITUDE_MUTATION * (f64)rand() / RAND_MAX)) - MAGNITUDE_MUTATION; + (*x)->weight[i_mutation] += r; } int main(void) { srand(time(0)); - fp_t input[12] = {0, 0, 0, 1, 1, 0, 1, 1}; - fp_t output; - fp_t target[4] = {0, 1, 1, 0}; + f64 input[12] = {0, 0, 0, 1, 1, 0, 1, 1}; + f64 output; + f64 target[4] = {0, 1, 1, 0}; - ann_t **networks = malloc(sizeof(ann_t *) * POPULATION_N); + ann_t *networks[POPULATION_N] = {0}; - for (uint_t i = 0; i < POPULATION_N; i++) { - networks[i] = ann_init(3, (uint_t[]){2, 2, 1}); - ann_set_activation(networks[i], SIGMOID, IDENTITY); - ann_random(networks[i]); + for (u64 i = 0; i < POPULATION_N; i++) { + ann_t *ann = malloc(sizeof(ann_t)); + if (!ann) { + fprintf(stderr, "Failed to allocate ann_t\n"); + for (u64 k = 0; k < i; k++) { ann_free(networks[k]); free(networks[k]); } + exit(1); + } + if (!ann_init(ann, 3, (u64[]){2, 2, 1})) { + free(ann); + fprintf(stderr, "Failed to init ann_t\n"); + for (u64 k = 0; k < i; k++) { ann_free(networks[k]); free(networks[k]); } + exit(1); + } + ann_set_activation(ann, SIGMOID, IDENTITY); + ann_random(ann); + networks[i] = ann; } - fp_t e = ERROR + 1; - uint32_t n = 0, i = 0; - while (e > ERROR) { - e = ga_generation(networks, POPULATION_N, RATE_SELECTION, RATE_MUTATON, - fitness, (fp_t *[2]){input, target}, crossover, mutate); + f64 e = ERROR + 1; + uint32_t n = 0; + uint32_t max_iterations = 1000000; + uint32_t print_counter = 0; + f64 *fitness_data[2] = {input, target}; + while (e > ERROR && n < max_iterations) { + e = ga_generation(networks, POPULATION_N, RATE_SELECTION, RATE_MUTATION, + fitness, fitness_data, crossover, mutate); n++; - i++; + print_counter++; - if (i > 1000) { + if (print_counter > 1000) { printf("\rERROR: %10.5lf", e); - i = 0; + print_counter = 0; } } @@ -81,11 +114,16 @@ int main(void) { for (int i = 0; i < 1; i++) { for (int j = 0; j < 4; j++) { - ann_propagation_forward(networks[i], (fp_t const *const)&input[2 * j], + ann_propagation_forward(networks[i], (f64 const *const)&input[2 * j], &output); ann_print_neuron(networks[i], &input[2 * j], &output); } } printf("\nITERATIONS: %u\n", n); + + for (u64 i = 0; i < POPULATION_N; i++) { + ann_free(networks[i]); + free(networks[i]); + } } diff --git a/example/genetic_char.c b/example/genetic_char.c old mode 100755 new mode 100644 index 7dc24d4..d0b08ae --- a/example/genetic_char.c +++ b/example/genetic_char.c @@ -1,7 +1,8 @@ -// example_string.c - Example training of ann.h ANN, with genetic algorithm +// genetic_char.c - Example: evolving a string to match a target #include #include +#include #include #include @@ -12,7 +13,7 @@ typedef char *ga_individual_t; #define POPULATION_N 100 #define RATE_SELECTION 0.5 -#define RATE_MUTATON 2.0 +#define RATE_MUTATION 0.2 #define ERROR 0 #define TARGET_STRING \ @@ -23,43 +24,58 @@ typedef char *ga_individual_t; #define generate() ((char)(rand() % (127 - 32) + 32)) void crossover(char **y, char *x0, char *x1) { + if (!y || !x0 || !x1) + return; uint32_t lx0 = strlen(x0); uint32_t lx1 = strlen(x1); + if (lx0 == 0 || lx1 == 0) + return; + uint32_t ix0 = rand() % lx0; uint32_t ix1 = rand() % lx1; uint32_t ly = ix0 + (lx1 - ix1); char *sy = malloc(ly + 1); - strncpy(sy, x0, ix0); - strncpy(sy + ix0, x1 + ix1, lx1 - ix1); + if (!sy) { + free(*y); + *y = NULL; + return; + } + memcpy(sy, x0, ix0); + memcpy(sy + ix0, x1 + ix1, lx1 - ix1); sy[ly] = 0; free(*y); *y = sy; } -void mutation(char *x) { - uint32_t l = strlen(x); +void mutation(char **x) { + if (!x || !*x) return; + uint32_t l = strlen(*x); + if (l == 0) return; uint32_t i = rand() % l; - x[i] = generate(); + (*x)[i] = generate(); } double fitness(char *individual, void const *data) { + if (!individual) return 1e30; double error = 0; char const *target = (char const *)data; while (*individual && *target) { - error += abs(*target++ - *individual++); + error += abs((unsigned char)*target - (unsigned char)*individual); + target++; + individual++; } while (*individual) { - error += *individual++; + error += (unsigned char)*individual++; } while (*target) { - error += *target++; + error += (unsigned char)*target++; } return error; @@ -71,10 +87,15 @@ int main(void) { srand(time(0)); - // Initialize poplation + // Initialize population for (uint64_t i = 0; i < POPULATION_N; i++) { uint64_t n = rand() % 5 + 20; char *str = malloc(n + 1); + if (!str) { + fprintf(stderr, "Failed to allocate string\n"); + for (uint64_t k = 0; k < i; k++) free(population[k]); + exit(1); + } str[n] = (uint8_t)0; for (uint64_t j = 0; j < n; j++) { @@ -84,27 +105,28 @@ int main(void) { population[i] = str; } - printf("TARGET: %s\n", TARGET_STRING); + printf("TARGET: %s\n", TARGET_STRING); fflush(stdout); - time_t t0 = clock(); + clock_t t0 = clock(); uint32_t n = 0; - // Conduct opitmization + // Conduct optimization double error = 1; - while (error > ERROR) { - error = - ga_generation(population, POPULATION_N, RATE_SELECTION, RATE_MUTATON, - fitness, (void const *)target, crossover, mutation); + uint32_t max_iterations = 1000000; + while (error > ERROR && n < max_iterations) { + error = + ga_generation(population, POPULATION_N, RATE_SELECTION, RATE_MUTATION, + fitness, (void const *)target, crossover, mutation); n++; + printf("\rSOLUTION: %s", population[0]); } - time_t t1 = clock(); + clock_t t1 = clock(); - printf("\nSOLUTION: %s", population[0]); - printf("\nITERATIONS: %d\nTIME: %f ms\n", n, + printf("\nSOLUTION: %s\nITERATIONS: %u\nTIME: %f ms\n", population[0], n, 1000.0 * (t1 - t0) / CLOCKS_PER_SEC); for (int i = 0; i < POPULATION_N; i++) { diff --git a/example/genetic_pushdown_btc.c b/example/genetic_pushdown_btc.c new file mode 100644 index 0000000..1261413 --- /dev/null +++ b/example/genetic_pushdown_btc.c @@ -0,0 +1,173 @@ +// genetic_pushdown_btc.c - Example training of a pushdown automaton by genetic algorithm + +#include "../include/escape.h" +#include +#include +#include +#include +#include +#include +#include +#include + +typedef double stack_value_t; +#define STACK_IMPLEMENTATION +#include "../include/stack.h" + +typedef stack_value_t pushdown_value_t; +#define PUSHDOWN_IMPLEMENTATION +#include "../include/pushdown.h" + +typedef struct { + size_t size; + pushdown_instruction_t *op; +} program_t; + +typedef program_t ga_individual_t; +#define GENETIC_IMPLEMENTATION +#include "../include/genetic.h" + +#define POPULATION_N 128 +#define RATE_SELECTION 0.25 +#define RATE_MUTATION 0.2 +#define ERROR 1000 + +#define generate() ((pushdown_instruction_t)(rand() % END)) + +void crossover(program_t *y, program_t x0, program_t x1) { + if (!y || x0.size == 0 || x1.size == 0) { + return; + } + + uint32_t x0_crossover = rand() % x0.size; + uint32_t x1_crossover = rand() % x1.size; + + uint32_t size = x0_crossover + (x1.size - x1_crossover); + + pushdown_instruction_t *instructions = + calloc(size + 1, sizeof(pushdown_instruction_t)); + if (!instructions) { + free(y->op); + y->op = NULL; + y->size = 0; + return; + } + memcpy(instructions, x0.op, x0_crossover * sizeof(pushdown_instruction_t)); + memcpy(instructions + x0_crossover, x1.op + x1_crossover, + (x1.size - x1_crossover) * sizeof(pushdown_instruction_t)); + instructions[size] = END; + + free(y->op); + y->op = instructions; + y->size = size; +} + +void mutation(program_t *x) { + if (!x || x->size == 0) { + return; + } + uint32_t i = rand() % x->size; + x->op[i] = generate(); +} + +double BTC[] = { +#include "./genetic_pushdown_btc.txt" +}; + +double fitness(program_t individual, void const *data) { + (void)data; + if (!individual.op) + return DBL_MAX; + + double error = 0; + const uint32_t K = 16; + size_t btc_n = sizeof(BTC) / sizeof(*BTC); + if (btc_n < K) + return 0; + + for (size_t i = 0; i < btc_n - K; i++) { + stack_t input = {0}; + stack_t output = {0}; + + stack_from_array(&input, &BTC[i], K); + stack_init(&output); + pushdown_run(&output, &input, individual.op); + double e = fabs(stack_peek(&output) - BTC[i + K]) + individual.size; + error += e; + + stack_free(&input); + stack_free(&output); + } + + return error; +} + +// void kill(int signal) { (void)signal; } // removed: shadows POSIX kill(2) + +int main(void) { + program_t population[POPULATION_N] = {0}; + + srand(time(0)); + + // Initialize population + for (uint64_t i = 0; i < POPULATION_N; i++) { + uint64_t n = rand() % 10 + 10; + pushdown_instruction_t *program = + calloc(n + 1, sizeof(pushdown_instruction_t)); + if (!program) { + fprintf(stderr, "Failed to allocate program\n"); + for (uint64_t k = 0; k < i; k++) free(population[k].op); + return 1; + } + program[n] = END; + + for (uint64_t j = 0; j < n; j++) { + program[j] = generate(); + } + + population[i].op = program; + population[i].size = n; + } + + uint32_t n = 0; + + double error = ERROR + 1, error_last = 0; + double rate_mutation = RATE_MUTATION; + double rate_selection = RATE_SELECTION; + + // Conduct optimization + uint32_t max_iterations = 1000000; + while (error > ERROR && n < max_iterations) { + error_last = error; + error = ga_generation(population, POPULATION_N, rate_selection, + rate_mutation, fitness, NULL, crossover, mutation); + + if (error == error_last) { + rate_mutation = fmin(1.1 * rate_mutation, 0.95); + } else { + rate_mutation = RATE_MUTATION; + } + + printf("%u\t%zu\t%lf\t%lf\n", n, population[0].size, error, error / POPULATION_N); + n++; + } + + clock_t t1 = clock(); + (void)t1; + + pushdown_instruction_t *op = population[0].op; + if (!op) { + fprintf(stderr, "Best individual has no program\n"); + return 1; + } + while (*op != END) { + printf("%d\n", *op); + op++; + } + + for (uint64_t i = 0; i < POPULATION_N; i++) { + free(population[i].op); + } + + return 0; +} diff --git a/example/genetic_pushdown_btc.txt b/example/genetic_pushdown_btc.txt new file mode 100644 index 0000000..7dfbc2c --- /dev/null +++ b/example/genetic_pushdown_btc.txt @@ -0,0 +1,366 @@ +16625.080000, +16688.470000, +16679.860000, +16863.240000, +16836.740000, +16951.970000, +16955.080000, +17091.140000, +17196.550000, +17446.290000, +17934.900000, +18869.590000, +19909.570000, +20976.300000, +20880.800000, +21169.630000, +21161.520000, +20688.780000, +21086.790000, +22676.550000, +22777.630000, +22720.420000, +22934.430000, +22636.470000, +23117.860000, +23032.780000, +23078.730000, +23031.090000, +23774.570000, +22840.140000, +23139.280000, +23723.770000, +23471.870000, +23449.320000, +23331.850000, +22955.670000, +22760.110000, +23264.290000, +22939.400000, +21819.040000, +21651.180000, +21870.880000, +21788.200000, +21808.100000, +22220.800000, +24307.840000, +23623.470000, +24565.600000, +24641.280000, +24327.640000, +24829.150000, +24436.350000, +24188.840000, +23947.490000, +23198.130000, +23175.380000, +23561.210000, +23522.870000, +23147.350000, +23646.550000, +23475.470000, +22362.680000, +22353.350000, +22435.510000, +22429.760000, +22219.770000, +21718.080000, +20363.020000, +20187.240000, +20632.410000, +22163.950000, +24197.530000, +24746.070000, +24375.960000, +25052.790000, +27423.930000, +26965.880000, +28038.680000, +27767.240000, +28175.820000, +27307.440000, +28333.970000, +27493.290000, +27494.710000, +27994.330000, +27139.890000, +27268.130000, +28348.440000, +28033.560000, +28478.480000, +28411.040000, +28199.310000, +27790.220000, +28168.090000, +28177.980000, +28044.140000, +27925.860000, +27947.790000, +28333.050000, +29652.980000, +30235.060000, +30139.050000, +30399.070000, +30485.700000, +30318.500000, +30315.360000, +29445.040000, +30397.550000, +28822.680000, +28245.990000, +27276.910000, +27817.500000, +27591.380000, +27525.340000, +28307.600000, +28422.700000, +29473.790000, +29340.260000, +29248.490000, +29268.810000, +28091.570000, +28680.540000, +29006.310000, +28847.710000, +29534.380000, +28904.620000, +28454.980000, +27694.270000, +27658.780000, +27621.760000, +27000.790000, +26804.990000, +26784.080000, +26930.640000, +27192.690000, +27036.650000, +27398.800000, +26832.210000, +26890.130000, +27129.590000, +26753.830000, +26851.280000, +27225.730000, +26334.820000, +26476.210000, +26719.290000, +26868.350000, +28085.650000, +27745.880000, +27702.350000, +27219.660000, +26819.970000, +27249.590000, +27075.130000, +27119.070000, +25760.100000, +27238.780000, +26346.000000, +26508.220000, +26480.380000, +25851.240000, +25940.170000, +25902.500000, +25918.730000, +25124.680000, +25576.390000, +26327.460000, +26510.680000, +26336.210000, +26851.030000, +28327.490000, +30027.300000, +29912.280000, +30695.470000, +30548.700000, +30480.260000, +30271.130000, +30688.160000, +30086.250000, +30445.350000, +30477.250000, +30590.080000, +30620.770000, +31156.440000, +30777.580000, +30514.170000, +29909.340000, +30342.270000, +30292.540000, +30171.230000, +30414.470000, +30620.950000, +30391.650000, +31476.050000, +30334.070000, +30295.810000, +30249.130000, +30145.890000, +29856.560000, +29913.920000, +29792.020000, +29908.740000, +29771.800000, +30084.540000, +29176.920000, +29227.390000, +29354.970000, +29210.690000, +29319.250000, +29356.920000, +29275.310000, +29230.110000, +29675.730000, +29151.960000, +29178.680000, +29074.090000, +29042.130000, +29041.860000, +29180.580000, +29765.490000, +29561.490000, +29429.590000, +29397.710000, +29415.960000, +29282.910000, +29408.440000, +29170.350000, +28701.780000, +26664.550000, +26049.560000, +26096.210000, +26189.580000, +26124.140000, +26031.660000, +26431.640000, +26162.370000, +26047.670000, +26008.460000, +26089.690000, +26106.150000, +27727.390000, +27297.270000, +25931.470000, +25800.720000, +25868.800000, +25969.570000, +25812.420000, +25779.980000, +25753.240000, +26240.200000, +25905.650000, +25895.680000, +25832.230000, +25162.650000, +25833.340000, +26228.320000, +26539.670000, +26608.690000, +26568.280000, +26534.190000, +26754.280000, +27211.120000, +27132.010000, +26567.630000, +26579.570000, +26579.390000, +26256.830000, +26298.480000, +26217.250000, +26352.720000, +27021.550000, +26911.720000, +26967.920000, +27983.750000, +27530.790000, +27429.980000, +27799.390000, +27415.910000, +27946.600000, +27968.840000, +27935.090000, +27583.680000, +27391.020000, +26873.320000, +26756.800000, +26862.380000, +26861.710000, +27159.650000, +28519.470000, +28415.750000, +28328.340000, +28719.810000, +29682.950000, +29918.410000, +29993.900000, +33086.230000, +33901.530000, +34502.820000, +34156.650000, +33909.800000, +34089.570000, +34538.480000, +34502.360000, +34667.780000, +35437.250000, +34938.240000, +34732.320000, +35082.200000, +35049.360000, +35037.370000, +35443.560000, +35655.280000, +36693.130000, +37313.970000, +37138.050000, +37054.520000, +36502.360000, +35537.640000, +37880.580000, +36154.770000, +36596.680000, +36585.700000, +37386.550000, +37476.960000, +35813.810000, +37432.340000, +37289.620000, +37720.280000, +37796.790000, +37479.120000, +37254.170000, +37831.090000, +37858.490000, +37712.750000, +38688.750000, +39476.330000, +39978.390000, +41980.100000, +44080.650000, +43746.450000, +43292.660000, +44166.600000, +43725.980000, +43779.700000, +41243.830000, +41450.220000, +42890.740000, +43023.970000, +41929.760000, +42240.120000, +41364.660000, +42623.540000, +42270.530000, +43652.250000, +43869.150000, +43997.900000, +43739.540000, +43016.120000, +43613.140000, +42520.400000, +43442.860000, +42627.860000, +42099.400000, +42156.900000, +42265.190000, +44167.330000, diff --git a/example/pool.c b/example/pool.c old mode 100755 new mode 100644 index 8b1fafd..5c985e4 --- a/example/pool.c +++ b/example/pool.c @@ -1,7 +1,19 @@ +// pool.c - Example usage of pool.h memory pool + #define POOL_IMPLEMENTATION #include "../include/pool.h" -int main() { - pool_t*p = pool_init(10, 100); - pool_print(p); +#include +#include + +int main(void) { + pool_t *p = pool_init(16, 100); + if (!p) { + fprintf(stderr, "Failed to initialize pool\n"); + return 1; + } + printf("capacity: %u\n", pool_capacity(p)); + printf("size: %u\n", pool_size(p)); + pool_fini(&p); + return 0; } \ No newline at end of file diff --git a/example/pushdown.c b/example/pushdown.c index ada8d73..bd34bb8 100644 --- a/example/pushdown.c +++ b/example/pushdown.c @@ -1,13 +1,20 @@ -typedef double pushdown_value_t; +// pushdown.c - Example usage of pushdown.h stack automaton + +#include + +typedef double stack_value_t; #define STACK_IMPLEMENTATION +#include "../include/stack.h" + +typedef double pushdown_value_t; #define PUSHDOWN_IMPLEMENTATION #include "../include/pushdown.h" int main() { pushdown_instruction_t instructions[] = {PUSH, COPY, MUL, END}; - stack_t input = {}; - stack_t output = {}; + stack_t input = {0}; + stack_t output = {0}; stack_init(&input); stack_init(&output); @@ -19,4 +26,7 @@ int main() { while (output.size) { printf("%lf\n", stack_pop(&output)); } + + stack_free(&input); + stack_free(&output); } \ No newline at end of file diff --git a/example/stack.c b/example/stack.c index 93128f4..d5d2e5a 100644 --- a/example/stack.c +++ b/example/stack.c @@ -1,20 +1,27 @@ +// stack.c - Example usage of stack.h dynamic stack + +#include + typedef double stack_value_t; #define STACK_IMPLEMENTATION #include "../include/stack.h" -void main() { - stack_t stack = { .capacity = 10 }; - stack_init(&stack); +int main(void) { + stack_t stack = {0}; + stack.capacity = 10; + stack_init(&stack); + + for (int i = 0; i < 15; i++) { + stack_push(&stack, (stack_value_t)i); + } + + printf("%lf\n", stack_peek(&stack)); + printf("%lf\n", stack_pop(&stack)); - for(int i = 0; i < 15; i++) { - stack_push(&stack, (stack_value_t) i); - } - - printf("%lf\n", stack_peek(&stack)); + for (int i = 0; i < 14; i++) { printf("%lf\n", stack_pop(&stack)); + } - for(int i = 0; i < 15; i++) { - printf("%lf\n", stack_pop(&stack)); - } + stack_free(&stack); } \ No newline at end of file diff --git a/example/ufo.c b/example/ufo.c new file mode 100755 index 0000000..fcd1b5c --- /dev/null +++ b/example/ufo.c @@ -0,0 +1,22 @@ +// ufo.c - Example usage of ufo.h Universal Function Originator + +#define UFO_IMPLEMENTATION +#include "../include/ufo.h" + + +#include +#include + + +int main(void) { + ufo_t *ufo = ufo_init(1, 100); + if (!ufo) { + fprintf(stderr, "Failed to initialize UFO\n"); + return 1; + } + printf("%f\n", ufo_evaluate(ufo, (f64[]){1.0})); + ufo_free(ufo); + + return 0; +} + -- cgit v1.3.1