Fibonacci generator in C with Y-Combinator powered memoization.

fib.c

//
// 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;
}