Create a gist now

Instantly share code, notes, and snippets.

Fibonacci generator in C with Y-Combinator powered memoization.
//
// 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