Lazy Evaluation with Just in Time Compiled Thunks

lazy.c

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>

typedef struct list_data (*list)();

struct list_data {
  long head;
  list tail;
};

struct thunk {
  char mov_register1[2];
  void *register1;
  char mov_register2[2];
  void *register2;
  char finish[2];
  void *data;
} __attribute__((packed));

void lazy(struct thunk *thunk, void *data,
          struct list_data function(struct thunk *)) {
  thunk->data = data;
  thunk->mov_register1[0] = 0x48;
  thunk->mov_register1[1] = 0xb8;
  thunk->register1 = function;
  thunk->mov_register2[0] = 0x48;
  thunk->mov_register2[1] = 0xbf;
  thunk->register2 = thunk;
  thunk->finish[0] = 0xff;
  thunk->finish[1] = 0xe0;
}

void strict(struct thunk *thunk, struct list_data result) {
  thunk->mov_register1[0] = 0x48;
  thunk->mov_register1[1] = 0xb8;
  thunk->register1 = (void *)result.head;
  thunk->mov_register2[0] = 0x48;
  thunk->mov_register2[1] = 0xba;
  thunk->register2 = result.tail;
  thunk->finish[0] = 0xc3;
  thunk->finish[1] = 0x90;
}

void *rwx_mem;
void *rwx_mem_end;

list allocate_lazy(struct list_data function(struct thunk *), void *data) {
  assert(rwx_mem < rwx_mem_end);

  struct thunk *thunk = rwx_mem;
  lazy(thunk, data, function);
  rwx_mem += sizeof(struct thunk);
  return (list)thunk;
}

list fibonacci;

struct fibonacci {
  list x;
  list y;
};

struct fibonacci *fibonacci_context(list x, list y) {
  struct fibonacci *context = malloc(sizeof(struct fibonacci));
  context->x = x;
  context->y = y;
  return context;
}

struct list_data fibonacci_go(struct thunk *thunk) {
  struct fibonacci *context = thunk->data;
  list x = context->x;
  list y = context->y;
  free(context);

  struct list_data result = {
      x().head + y().head,
      allocate_lazy(fibonacci_go, fibonacci_context(x().tail, y().tail))};
  strict(thunk, result);
  return result;
}

struct list_data fibonacci_1(struct thunk *thunk) {
  struct list_data result = {
      1, allocate_lazy(fibonacci_go,
                       fibonacci_context(fibonacci, fibonacci().tail))};
  strict(thunk, result);
  return result;
}

struct list_data fibonacci_0(struct thunk *thunk) {
  struct list_data result = {0, allocate_lazy(fibonacci_1, 0)};
  strict(thunk, result);
  return result;
}

int main() {
  rwx_mem = mmap(0, 4096, PROT_EXEC | PROT_WRITE | PROT_READ,
                 MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
  assert(rwx_mem != MAP_FAILED);
  rwx_mem_end = rwx_mem + 4096;

  fibonacci = allocate_lazy(fibonacci_0, 0);

  list numbers;

  numbers = fibonacci;
  for (int i = 0; i < 10; i++) {
    printf("%li\n", numbers().head);
    numbers = numbers().tail;
  }

  numbers = fibonacci;
  for (int i = 0; i < 10; i++) {
    printf("%li\n", numbers().head);
    numbers = numbers().tail;
  }

  return 0;
}