Computing sum using trampolines and dynamic calls in C

sum.c

// recursive sum function encoded as a dynamically-calling trampoline of continuations returned as thunks
// don't compile with -pedantic, there's lots of bad casts going on in this code
// this program computes the sum of integers 1 to 50,000 (using a lot of heap memory to do so)
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <talloc.h>
#include <dyncall.h>

// global talloc allocation context
void* ctx;

// represent arguments as linked list of tagged unions
struct arg {
  enum {
    PTR, I32
  } tag;
  union {
    void* ptr;
    int32_t i32;
  } as;
  struct arg* next;
};

struct arg* mk_i32_arg(int32_t value, struct arg* next) {
  struct arg* x = talloc(ctx, struct arg);
  x->tag = I32;
  x->as.i32 = value;
  x->next = next;
  return x;
}

struct arg* mk_ptr_arg(void* value, struct arg* next) {
  struct arg* x = talloc(ctx, struct arg);
  x->tag = PTR;
  x->as.ptr = value;
  x->next = next;
  return x;
}

struct closure {
  void* f;
  char env[32]; // avoiding further indirection for this example
};

struct closure* mk_closure(void* target) {
  struct closure* c = talloc(ctx, struct closure);
  c->f = target;
  return c;
}

struct thunk {
  struct closure* f;
  struct arg* args;
};

void next(char* env, int32_t x) {
  struct closure* k = *((struct closure**) env);
  int32_t n = *((int32_t*)(env + sizeof(uintptr_t)));

  void (*f)(char*, int32_t) = k->f;
  f(&k->env[0], n + x); // k(n + x)
}

struct thunk* sum(char* env, int32_t n, struct closure* k) {
  if (n == 0) {
    // { f: k, xs: [0] }
    struct thunk* th = talloc(ctx, struct thunk);
    th->f = k;
    th->args = mk_i32_arg(0, NULL);
    return th;
  }

  // { f: sum, args: [n -1, next] }
  struct thunk* th = talloc(ctx, struct thunk);
  th->f = mk_closure(sum);
  // x => k(n + x)
  struct closure* cls = mk_closure(next);
  // store k and n into environment
  char* e = &cls->env[0];
  *((uintptr_t*) e) = (uintptr_t) k;
  *((int32_t*)(e + sizeof(uintptr_t))) = n;
  th->args = mk_i32_arg(n - 1, mk_ptr_arg(cls, NULL));
  
  return th;
}

// top-level continuation
struct thunk* final(char* env, int32_t result) {
  printf("result = %d\n", result);
  return NULL;
}

int main(void) {
  ctx = talloc_init("sum");

  // sum(50000, final)
  struct thunk start;
  start.f = mk_closure(sum);
  start.args = mk_i32_arg(50000, mk_ptr_arg(mk_closure(final), NULL));

  // seed evaluator with initial thunk
  struct thunk* th = &start;
  while (th) {
    DCCallVM* vm = dcNewCallVM(4096);
    dcMode(vm, DC_CALL_C_DEFAULT);
    dcReset(vm);

    struct closure* f = th->f;

    // first argument is always environment
    dcArgPointer(vm, &f->env[0]);

    // iteratively populate following arguments
    struct arg* next = th->args;
    while (next) {
      switch(next->tag) {
      case I32: {
        dcArgInt(vm, next->as.i32);
        break;
      }
      case PTR: {
        dcArgPointer(vm, next->as.ptr);
        break;
      }
      }
      
      next = next->next;
    }

    // invoke thunk
    th = dcCallPointer(vm, f->f);
    dcFree(vm);
  }
  
  talloc_free(ctx);
}