Modeling various high level language features in C

adt.c

#include <stdint.h>
#include <stdio.h>

enum bop {
    BOP_PLUS,
    BOP_MINUS,
    BOP_TIMES,
};

typedef struct ast_exp ast_exp;
struct ast_exp {
    enum {
        AST_INT,
        AST_VAR,
        AST_LAM,
        AST_APP,
        AST_BOP,
        AST_IF
    } type;

    // Unnamed structs/unions supported in C11, not C99 without extensions.
    union {
        int32_t intt;
        char *var;
        struct {
            char *var;
            ast_exp *body;
        } lam;
        struct {
            ast_exp *fn;
            ast_exp *param;
        } app;
        struct {
            enum bop bop;
            ast_exp *lhs;
            ast_exp *rhs;
        } bop;
        struct {
            ast_exp *cond;
            ast_exp *thenn;
            ast_exp *elsee;
        } iff;
    };
};

void print_ast_exp(ast_exp *exp)
{
    // gcc gives warning if not exhaustive
    switch (exp->type) {
    case AST_INT:
        printf("%d", exp->intt);
        break;
    case AST_VAR:
        printf("%s", exp->var);
        break;
    case AST_LAM:
        printf("(\\%s -> ", exp->lam.var);
        print_ast_exp(exp->lam.body);
        printf(")");
        break;
    case AST_APP:
        printf("(");
        print_ast_exp(exp->app.fn);
        printf(" ");
        print_ast_exp(exp->app.param);
        printf(")");
        break;
    case AST_BOP: {
        const char *bop;
        switch (exp->bop.bop) {
        case BOP_PLUS:
            bop = "+";
            break;
        case BOP_MINUS:
            bop = "-";
            break;
        case BOP_TIMES:
            bop = "*";
            break;
        }

        print_ast_exp(exp->bop.lhs);
        printf(" %s ", bop);
        print_ast_exp(exp->bop.rhs);
        break;
    }
    case AST_IF:
        printf("if ");
        print_ast_exp(exp->iff.cond);
        printf(" then ");
        print_ast_exp(exp->iff.thenn);
        printf(" else ");
        print_ast_exp(exp->iff.elsee);
        break;
    }
}

// gcc -std=c11 -Wall -Wextra -Wpedantic -fsanitize=address,undefined adt.c
int main()
{
    ast_exp lhs = {AST_INT, .intt = 2};
    ast_exp rhs = {AST_INT, .intt = 3};
    ast_exp exp = {AST_BOP, .bop = {BOP_PLUS, &lhs, &rhs}};
    print_ast_exp(&exp);
    printf("\n");
}

arena.c

#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

typedef struct arena {
    char *begin;
    char *end;
} arena;

void *arena_alloc(arena *arena, ptrdiff_t size, ptrdiff_t alignment,
                  ptrdiff_t count)
{
    // a & (b - 1) == a % b
    // begin % alignment == # of bytes from last aligned address
    // - for inverse (padding is space to next aligned address,
    // not space from last aligned address)
    ptrdiff_t padding = -(uintptr_t)arena->begin & (alignment - 1);
    ptrdiff_t available = arena->end - arena->begin - padding;
    if (available < 0 || count > available / size) {
        return NULL;
    }

    void *ptr = arena->begin + padding;
    arena->begin += padding + size * count;
    return ptr;
}

arena arena_get(void)
{
    static char buf[1 << 28];
    arena arena = {0};
    arena.begin = buf;
    __asm__("" : "+r"(arena.begin)); // launder the pointer arena.begin
    arena.end = arena.begin + sizeof(buf) / sizeof(*buf);
    return arena;
}

#define SIZE 100

typedef struct person {
    char *name;
    int32_t age;
} person;

// gcc -std=c11 -Wall -Wextra -Wpedantic -fsanitize=address,undefined arena.c
int main()
{
    arena arena = arena_get();
    person *people =
        arena_alloc(&arena, sizeof(person), _Alignof(person), SIZE);
    assert(people != NULL && "allocation failed");

    for (int32_t i = 0; i < SIZE; ++i) {
        people[i].name = "bob";
        people[i].age = i;
        printf("Person: %s %d\n", people[i].name, people[i].age);
    }
}

closure.c

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct fresh_closure fresh_closure;
struct fresh_closure {
    int32_t (*call)(fresh_closure *);
};

struct my_fresh_closure {
    int32_t (*call)();
    // C Standard: All identifiers that begin with an underscore and either
    // an uppercase letter or another underscore are always reserved for any
    // use. Also any global is not allowed to begin with an underscore. This
    // is an underscore with a lowercase letter inside a struct so it should
    // be ok.
    int32_t _counter;
};

struct my_fresh_closure2 {
    int32_t (*call)();
    int32_t _incrementer;
    int32_t _counter;
};

static int32_t fresh_impl(struct my_fresh_closure *clos)
{
    return clos->_counter++;
}

static int32_t fresh_impl2(struct my_fresh_closure2 *clos)
{
    clos->_counter += clos->_incrementer++;
    return clos->_counter;
}

fresh_closure *global_fresh = (fresh_closure *)&(struct my_fresh_closure){
    .call = fresh_impl,
    ._counter = 0,
};

fresh_closure *fresh_alloc(void)
{
    struct my_fresh_closure2 *clos = malloc(sizeof(*clos));
    if (clos == NULL) {
        return NULL;
    }
    clos->_incrementer = 1;
    clos->_counter = 0;
    clos->call = fresh_impl2;
    // This should be ok because the C Standard says that there cannot
    // be any padding before the first element of the struct, and the
    // only usage of fresh_closure is its first element call.
    return (fresh_closure *)clos;
}

int32_t fresh(void)
{
    return global_fresh->call(global_fresh);
}

void print_fresh(const char *desc, fresh_closure *clos)
{
    printf("%s fresh: %d\n", desc, clos->call(clos));
    printf("%s fresh: %d\n", desc, clos->call(clos));
    printf("%s fresh: %d\n", desc, clos->call(clos));
}

// gcc -std=c11 -Wall -Wextra -Wpedantic -fsanitize=address,undefined closure.c
int main()
{
    print_fresh("global", global_fresh);

    fresh_closure *my_fresh = fresh_alloc();
    assert(my_fresh != NULL && "allocation failed");
    print_fresh("local", my_fresh);
    free(my_fresh);
}

closure2.c

#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

void add(int32_t a, int32_t b, void (*k)(void *, int32_t result), void *ctx)
{
    k(ctx, a + b);
}

void sub(int32_t a, int32_t b, void (*k)(void *, int32_t result), void *ctx)
{
    k(ctx, a - b);
}

void mul(int32_t a, int32_t b, void (*k)(void *, int32_t result), void *ctx)
{
    k(ctx, a * b);
}

typedef struct k3_clos {
    int32_t c;
    int32_t d;
} k3_clos;

void k3(void *ctx, int32_t result)
{
    k3_clos *clos = ctx;
    printf("Result: %d\n", result + clos->c * clos->d);
}

void k2(void *ctx, int32_t d)
{
    int32_t c = *(int32_t *)ctx;
    k3_clos *clos = malloc(sizeof(*clos));
    assert(clos != NULL && "allocation failed");
    *clos = (k3_clos){.c = c, .d = d};
    sub(d, c, &k3, clos);
    free(clos);
}

void k1(void *ctx, int32_t c)
{
    (void)ctx;
    mul(c, 3, &k2, &c);
}

// gcc -std=c11 -Wall -Wextra -Wpedantic -fsanitize=address,undefined closure2.c
int main()
{
    // c=3 d=9
    // (d-c)+c*d=6+27=33
    add(1, 2, &k1, NULL);
}

oop.c

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

struct person_vtable {
    char *(*get_name)(void *);
    int32_t (*get_age)(void *);
};

typedef struct person {
    const struct person_vtable *vtable;
    char *name;
    int32_t age;
} person;

char *person_get_name(void *ctx)
{
    return ((person *)ctx)->name;
}

int32_t person_get_age(void *ctx)
{
    return ((person *)ctx)->age;
}

typedef struct student {
    // student can be safely casted to person because there is guaranteed
    // to not be any padding between the start of the struct
    // and the first element.
    person parent;
    char grade;
} student;

int32_t student_get_age(void *ctx)
{
    student *student = ctx;
    // Can call student's data and vtable functions inside method.
    printf("Student with name %s and grade: %c\n",
           ((person *)student)->vtable->get_name(student), student->grade);
    return student->parent.age;
}

// Add comma after last field so clangformat doesn't put everything in one line.
const struct person_vtable person_vtable = {
    .get_name = person_get_name,
    .get_age = person_get_age,
};

const struct person_vtable student_vtable = {
    .get_name = person_get_name,
    .get_age = student_get_age,
};

person *person_alloc(char *name, int32_t age)
{
    person *p = malloc(sizeof(person));
    if (p == NULL) {
        return NULL;
    }
    *p = (person){&person_vtable, name, age};
    return p;
}

void print_person(person *person)
{
    printf("Name: %s\n", person->vtable->get_name(person));
    printf("Age: %d\n", person->vtable->get_age(person));
}

// gcc -std=c11 -Wall -Wextra -Wpedantic -fsanitize=address,undefined oop.c
int main()
{
    person bob = {&person_vtable, .name = "bob", .age = 21};
    student jane = {{&student_vtable, .name = "jane", .age = 19}, .grade = 'A'};
    print_person(&bob);
    print_person((person *)&jane);

    person *joe = person_alloc("joe", 30);
    assert(joe != NULL && "allocation failed");
    print_person(joe);
    free(joe);
}

template.c

#include "arena.h"
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node node;
struct node {
    void *data;
    node *left;
    node *right;
};

#define TEMPLATE_print_node(T, PRINT)                                          \
    void print_node_##T(const node *node)                                      \
    {                                                                          \
        if (!node) {                                                           \
            return;                                                            \
        }                                                                      \
        T data = (T)(intptr_t)node->data;                                      \
        PRINT;                                                                 \
        print_node_##T(node->left);                                            \
        print_node_##T(node->right);                                           \
    }                                                                          \
    void print_node_##T(const node *node)

TEMPLATE_print_node(int32_t, printf("%d\n", data));
TEMPLATE_print_node(int64_t, printf("%ld\n", data));

node *node_alloc(void *data)
{
    node *node = malloc(sizeof(*node));
    if (!node) {
        return NULL;
    }
    *node = (struct node){.data = data};
    return node;
}

void node_free(node *node)
{
    if (node->left) {
        node_free(node->left);
    }
    if (node->right) {
        node_free(node->right);
    }
    free(node);
}

// clang-format off
// gcc -std=c11 -Wall -Wextra -Wpedantic -fsanitize=address,undefined test.c arena.c
// clang-format on
int main()
{
    // Individual allocations through malloc
    {
        node *root = node_alloc((void *)1);
        node *left = node_alloc((void *)2);
        node *right = node_alloc((void *)3);
        assert(root && left && right && "allocation failed");
        root->left = left;
        root->right = right;
        print_node_int32_t(root);
        node_free(root); // root owns left and right
    }

    // Stack allocation
    {
        node nodes[] = {
            {.data = (void *)1}, {.data = (void *)2}, {.data = (void *)3}};
        nodes[0].left = &nodes[1];
        nodes[0].right = &nodes[2];
        print_node_int32_t(&nodes[0]);
    }

    // Arena allocation
    {
        arena r = arena_get();
        node *root = arena_alloc(&r, sizeof(node), _Alignof(node), 1);
        node *left = arena_alloc(&r, sizeof(node), _Alignof(node), 1);
        node *right = arena_alloc(&r, sizeof(node), _Alignof(node), 1);
        assert(root && left && right && "allocation failed");
        *root = (node){.data = (void *)1, .left = left, .right = right};
        *left = (node){.data = (void *)2};
        *right = (node){.data = (void *)3};
        print_node_int32_t(root);
    }
}

vector.c

#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct intvec {
    int32_t *data;
    size_t size;
    size_t capacity;
} intvec;

#define vec_append(v, a)                                                       \
    do {                                                                       \
        if ((v).size >= (v).capacity) {                                        \
            if ((v).capacity == 0) {                                           \
                (v).capacity = 256;                                            \
            } else {                                                           \
                size_t old = (v).capacity * sizeof(*(v).data);                 \
                (v).capacity *= 2;                                             \
                assert(((v).capacity * sizeof(*(v).data)) / 2 == old &&        \
                       "vector capacity overflow");                            \
            }                                                                  \
            (v).data = realloc((v).data, (v).capacity * sizeof(*(v).data));    \
            assert((v).data != NULL && "reallocation failed");                 \
        }                                                                      \
        (v).data[(v).size++] = (a);                                            \
    } while (0)

// gcc -std=c11 -Wall -Wextra -Wpedantic -fsanitize=address,undefined vector.c
int main()
{
    // intvec v = {0};
    intvec *v = malloc(sizeof(*v));
    assert(v != NULL && "allocation failed");
    *v = (intvec){0};
    for (size_t i = 0; i < 100000; ++i) {
        vec_append(*v, i);
    }

    for (size_t i = 0; i < v->size; ++i) {
        printf("i: %d\n", v->data[i]);
    }

    free(v->data);
    free(v);
}