Fibonacci generator in C with Y-Combinator powered memoization.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// Fibonacci generator in C with Y-Combinator powered memoization. | |
// | |
// Written by Kenneth Ballenegger in 2013 | |
// | |
#include <stdlib.h> | |
#include <stdio.h> | |
#include <Block.h> | |
#ifdef LOG_VERBOSE | |
#define log(...) printf(__VA_ARGS__) | |
#else | |
#define log(...) /* do nothing */ | |
#endif | |
// Implement Auto-Releasing... | |
typedef struct autorelease_pool_t *autorelease_pool; | |
typedef struct autorelease_pool_t { | |
void *p; | |
void(*fn)(void*); | |
autorelease_pool next; | |
} autorelease_pool_t; | |
typedef struct autorelease_pool_stack_t *autorelease_pool_stack; | |
typedef struct autorelease_pool_stack_t { | |
autorelease_pool head; | |
autorelease_pool_stack parent; | |
} autorelease_pool_stack_t; | |
static autorelease_pool_stack current_pool = NULL; | |
void push_autorelease_pool() { | |
autorelease_pool_stack new_pool = malloc(sizeof(autorelease_pool_stack_t)); | |
new_pool->parent = current_pool; | |
new_pool->head = NULL; | |
current_pool = new_pool; | |
} | |
void autorelease(void *p, void(*fn)(void*)) { | |
// If there is no current pool, we leak memory. | |
if (current_pool == NULL) return; | |
autorelease_pool head = malloc(sizeof(autorelease_pool_t)); | |
head->p = p; | |
head->fn = fn; | |
head->next = current_pool->head;; | |
current_pool->head = head; | |
} | |
void flush_autorelease_pool() { | |
while (current_pool->head != NULL) { | |
(*current_pool->head->fn)(current_pool->head->p); | |
autorelease_pool next = current_pool->head->next; | |
free(current_pool->head); | |
current_pool->head = next; | |
} | |
autorelease_pool_stack parent = current_pool->parent; | |
free(current_pool); | |
current_pool = parent; | |
} | |
// Actual Implementation | |
typedef unsigned long long ull; | |
typedef enum {false = 0, true = 1} bool; | |
// B-trees for ints | |
typedef struct cache_node_t *cache_node; | |
typedef struct cache_node_t { | |
bool is_leaf; | |
union { | |
struct { | |
cache_node one; | |
cache_node zero; | |
} node; | |
ull leaf; | |
} self; | |
} cache_node_t; | |
cache_node cache_tree_new() { | |
return calloc(1, sizeof(cache_node_t)); | |
} | |
void cache_tree_free(cache_node node) { | |
if (!node->is_leaf) { | |
if (node->self.node.one != NULL) cache_tree_free(node->self.node.one); | |
if (node->self.node.zero != NULL) cache_tree_free(node->self.node.zero); | |
} | |
free(node); | |
} | |
void cache_tree_store(cache_node root, int key, ull value) { | |
cache_node node = root; | |
for (size_t i = 0; i < sizeof(int) * 8; i++) { | |
bool direction = (bool)((key >> i) & (unsigned int)1); | |
if (direction == 1) { | |
if (node->self.node.one == NULL) { | |
node->self.node.one = calloc(1, sizeof(cache_node_t)); | |
// calloc makes sure is_leaf is zero, as well as the node in | |
// the union and the two children | |
} | |
node = node->self.node.one; | |
} else { | |
if (node->self.node.zero == NULL) { | |
node->self.node.zero = calloc(1, sizeof(cache_node_t)); | |
// calloc makes sure is_leaf is zero, as well as the node in | |
// the union and the two children | |
} | |
node = node->self.node.zero; | |
} | |
} | |
// the last node should be a leaf, if it isn't, we just created it | |
if (!node->is_leaf) { | |
node->is_leaf = true; | |
} | |
node->self.leaf = value; | |
} | |
ull cache_tree_lookup(cache_node root, int key, bool *found) { | |
cache_node node = root; | |
for (size_t i = 0; i < sizeof(int) * 8; i++) { | |
if (node == NULL || node->is_leaf) { | |
if (found) *found = false; | |
return 0; | |
} | |
bool direction = (bool)((key >> i) & (unsigned int)1); | |
if (direction == 1) { | |
node = node->self.node.one; | |
} else { | |
node = node->self.node.zero; | |
} | |
} | |
if (node == NULL || !node->is_leaf) { | |
if (found) *found = false; | |
return 0; | |
} | |
if (found) *found = true; | |
return node->self.leaf; | |
} | |
// wrapping in a union so it may refer to itself | |
typedef union _l_t *_l; | |
typedef union _l_t { | |
ull(^function_f)(int); | |
ull(^wrapper_f)(_l, int); | |
_l(^generator_f)(_l); | |
_l(^combiner_f)(_l); | |
} _l_t; | |
_l function(ull(^f)(int)) { | |
_l data = malloc(sizeof(_l_t)); | |
data->function_f = Block_copy(f); | |
autorelease(data->function_f, (void(*)(void*))&_Block_release); | |
autorelease(data, &free); | |
return data; | |
} | |
_l wrapper(ull(^f)(_l, int)) { | |
_l data = malloc(sizeof(_l_t)); | |
data->wrapper_f = Block_copy(f); | |
autorelease(data->wrapper_f, (void(*)(void*))&_Block_release); | |
autorelease(data, &free); | |
return data; | |
} | |
_l generator(_l(^f)(_l)) { | |
_l data = malloc(sizeof(_l_t)); | |
data->generator_f = Block_copy(f); | |
autorelease(data->generator_f, (void(*)(void*))&_Block_release); | |
autorelease(data, &free); | |
return data; | |
} | |
_l combiner(_l(^f)(_l)) { | |
_l data = malloc(sizeof(_l_t)); | |
data->combiner_f = Block_copy(f); | |
autorelease(data->combiner_f, (void(*)(void*))&_Block_release); | |
autorelease(data, &free); | |
return data; | |
} | |
// The Y-Combinator | |
_l y_combine(_l fn) { | |
_l x = combiner(^_l(_l recur) { | |
return function(^ull(int n) { | |
_l resp = recur->combiner_f(recur); | |
ull sol = fn->generator_f(resp)->function_f(n); | |
return sol; | |
}); | |
}); | |
return x->combiner_f(x); | |
} | |
_l wrap(_l fn, _l wrap_with) { | |
return generator(^_l(_l recur) { | |
return function(^ull(int n) { | |
_l fn_ = function(^ull(int n) { | |
return fn->generator_f(recur)->function_f(n); | |
}); | |
_l wrapped = function(^ull(int n) { | |
return wrap_with->wrapper_f(fn_, n); | |
}); | |
return wrapped->function_f(n); | |
}); | |
}); | |
} | |
int main(int argc, char **argv) { | |
push_autorelease_pool(); | |
// And this is our code that uses this... | |
_l log_wrapper = wrapper(^ull(_l f, int n) { | |
printf("About to generate # %d\n", n); | |
return f->function_f(n); | |
}); | |
_l(^new_memoizer)() = ^_l { | |
// caching in 256 word pages | |
cache_node root = cache_tree_new(); | |
autorelease(root, (void(*)(void*))&cache_tree_free); | |
return wrapper(^ull(_l f, int n) { | |
bool found; | |
ull cached = cache_tree_lookup(root, n, &found); | |
if (found == true) { | |
return cached; | |
} else { | |
ull value = f->function_f(n); | |
cache_tree_store(root, n, value); | |
return value; | |
} | |
}); | |
}; | |
_l fib_generator = generator(^_l(_l recur) { | |
return function(^ull(int n) { | |
if (n <= 2) | |
return 1; | |
log("Evaluating fib # %d...\n", n); | |
return recur->function_f(n-1) + recur->function_f(n-2); | |
}); | |
}); | |
_l fac_generator = generator(^_l(_l recur) { | |
return function(^ull(int n) { | |
if (n <= 1) return 1; | |
return n * recur->function_f(n-1); | |
}); | |
}); | |
// And here comes the actual code | |
_l fibonacci = y_combine(wrap(wrap(fib_generator, log_wrapper), new_memoizer())); | |
/*_l fibonacci = y_combine(wrap(fib_generator, log_wrapper));*/ | |
_l factorial = y_combine(wrap(fac_generator, new_memoizer())); | |
int upto = 20; | |
if (argc >= 2) upto = strtol(argv[1], NULL, 10); | |
printf("Do it up to fib # %d...\n", upto); | |
push_autorelease_pool(); | |
ull fib = fibonacci->function_f(upto); | |
flush_autorelease_pool(); | |
printf("Fibonacci number %d is %llu.\n", upto, fib); | |
push_autorelease_pool(); | |
ull fac = factorial->function_f(upto); | |
flush_autorelease_pool(); | |
printf("Factorial of %d is %llu.\n", upto, fac); | |
flush_autorelease_pool(); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment