Wikipedia has the following definition for a runtime:

A [runtime] primarily implements portions of an execution model.

We know what our execution model is! We talked about it in Part 5 - it’s the lazy graph reduction we’ve specified. Creating and manipulating graph nodes is slightly above hardware level, and all programs in our functional language will rely on such manipulation (it’s how they run!). Furthermore, most G-machine instructions are also above hardware level (especially unwind!).

Push and Slide and other instructions are pretty complex. Most computers aren’t stack machines. We’ll have to implement our own stack, and whenever a graph-building function will want to modify the stack, it will have to call library routines for our stack implementation:

void stack_push(struct stack* s, struct node_s* n);
struct node_s* stack_slide(struct stack* s, size_t c);
/* other stack operations */

Furthermore, we observe that Unwind does a lot of the heavy lifting in our G-machine definition. After we build the graph, Unwind is what picks it apart and performs function calls. Furthermore, Unwind pushes Unwind back on the stack: once you’ve hit it, you’re continuing to Unwind until you reach a function call. This effectively means we can implement Unwind as a loop:

while(1) {
    // Check for Unwind's first rule
    // Check for Unwind's second rule
    // ...
}

In this implementation, Unwind is in charge. We won’t need to insert the Unwind operations at the end of our generated functions, and you may have noticed we’ve already been following this strategy in our implementation of the G-machine compilation.

We can start working on an implementation of the runtime right now, beginning with the nodes:

From runtime.h, lines 4 through 50
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

struct stack;

enum node_tag {
    NODE_APP,
    NODE_NUM,
    NODE_GLOBAL,
    NODE_IND,
    NODE_DATA
};

struct node_base {
    enum node_tag tag;
};

struct node_app {
    struct node_base base;
    struct node_base* left;
    struct node_base* right;
};

struct node_num {
    struct node_base base;
    int32_t value;
};

struct node_global {
    struct node_base base;
    int32_t arity;
    void (*function)(struct stack*);
};

struct node_ind {
    struct node_base base;
    struct node_base* next;
};

struct node_data {
    struct node_base base;
    int8_t tag;
    struct node_base** array;
};

struct node_base* alloc_node();
struct node_app* alloc_app(struct node_base* l, struct node_base* r);
struct node_num* alloc_num(int32_t n);
struct node_global* alloc_global(void (*f)(struct stack*), int32_t a);
struct node_ind* alloc_ind(struct node_base* n);

We have a variety of different nodes that can be on the stack, but without the magic of C++’s vtable and RTTI, we have to take care of the bookkeeping ourselves. We add an enum, node_tag, which we will use to indicate what type of node we’re looking at. We also add a “base class” node_base, which contains the fields that all nodes must contain (only tag at the moment). We then add to the beginning of each node struct a member of type node_base. With this, a pointer to a node struct can be interpreted as a pointer to node_base, which is our lowest common denominator. To go back, we check the tag of node_base, and cast the pointer appropriately. This way, we mimic inheritance, in a very basic manner.

We also add an alloc_node, which allocates a region of memory big enough to be any node. We do this because we sometimes mutate nodes (replacing expressions with the results of their evaluation), changing their type. We then want to be able to change a node without reallocating memory. Since the biggest node we have is node_app, that’s the one we choose.

Finally, to make it easier to create nodes from our generated code, we add helper functions like alloc_num, which allocate a given node type, and set its tag and member fields appropriately. We don’t include such a function for node_data, since this node will be created only in one possible way.

Here’s the implementation:

From runtime.c, lines 6 through 40
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

struct node_base* alloc_node() {
    struct node_base* new_node = malloc(sizeof(struct node_app));
    assert(new_node != NULL);
    return new_node;
}

struct node_app* alloc_app(struct node_base* l, struct node_base* r) {
    struct node_app* node = (struct node_app*) alloc_node();
    node->base.tag = NODE_APP;
    node->left = l;
    node->right = r;
    return node;
}

struct node_num* alloc_num(int32_t n) {
    struct node_num* node = (struct node_num*) alloc_node();
    node->base.tag = NODE_NUM;
    node->value = n;
    return node;
}

struct node_global* alloc_global(void (*f)(struct stack*), int32_t a) {
    struct node_global* node = (struct node_global*) alloc_node();
    node->base.tag = NODE_GLOBAL;
    node->arity = a;
    node->function = f;
    return node;
}

struct node_ind* alloc_ind(struct node_base* n) {
    struct node_ind* node = (struct node_ind*) alloc_node();
    node->base.tag = NODE_IND;
    node->next = n;
    return node;
}

We now move on to implement some stack operations. Let’s list them:

We declare these in a header:

From runtime.h, lines 52 through 68
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

struct stack {
    size_t size;
    size_t count;
    struct node_base** data;
};

void stack_init(struct stack* s);
void stack_free(struct stack* s);
void stack_push(struct stack* s, struct node_base* n);
struct node_base* stack_pop(struct stack* s);
struct node_base* stack_peek(struct stack* s, size_t o);
void stack_popn(struct stack* s, size_t n);
void stack_slide(struct stack* s, size_t n);
void stack_update(struct stack* s, size_t o);
void stack_alloc(struct stack* s, size_t o);
void stack_pack(struct stack* s, size_t n, int8_t t);
void stack_split(struct stack* s, size_t n);

And implement them as follows:

From runtime.c, lines 42 through 116
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

void stack_init(struct stack* s) {
    s->size = 4;
    s->count = 0;
    s->data = malloc(sizeof(*s->data) * s->size);
    assert(s->data != NULL);
}

void stack_free(struct stack* s) {
    free(s->data);
}

void stack_push(struct stack* s, struct node_base* n) {
    while(s->count >= s->size) {
        s->data = realloc(s->data, sizeof(*s->data) * (s->size *= 2));
        assert(s->data != NULL);
    }
    s->data[s->count++] = n;
}

struct node_base* stack_pop(struct stack* s) {
    assert(s->count > 0);
    return s->data[--s->count];
}

struct node_base* stack_peek(struct stack* s, size_t o) {
    assert(s->count > o);
    return s->data[s->count - o - 1];
}

void stack_popn(struct stack* s, size_t n) {
    assert(s->count >= n);
    s->count -= n;
}

void stack_slide(struct stack* s, size_t n) {
    assert(s->count > n);
    s->data[s->count - n - 1] = s->data[s->count - 1];
    s->count -= n;
}

void stack_update(struct stack* s, size_t o) {
    assert(s->count > o + 1);
    struct node_ind* ind = (struct node_ind*) s->data[s->count - o - 2];
    ind->base.tag = NODE_IND;
    ind->next = s->data[s->count -= 1];
}

void stack_alloc(struct stack* s, size_t o) {
    while(o--) {
        stack_push(s, (struct node_base*) alloc_ind(NULL));
    }
}

void stack_pack(struct stack* s, size_t n, int8_t t) {
    assert(s->count >= n);

    struct node_base** data = malloc(sizeof(*data) * n);
    assert(data != NULL);
    memcpy(data, &s->data[s->count - 1 - n], n * sizeof(*data));

    struct node_data* new_node = (struct node_data*) alloc_node();
    new_node->array = data;
    new_node->base.tag = NODE_DATA;
    new_node->tag = t;

    stack_popn(s, n);
    stack_push(s, (struct node_base*) new_node);
}

void stack_split(struct stack* s, size_t n) {
    struct node_data* node = (struct node_data*) stack_pop(s);
    for(size_t i = 0; i < n; i++) {
        stack_push(s, node->array[i]);
    }
}

Let’s now talk about how this will connect to the code we generate. To get a quick example, consider the node_global struct that we have declared above. It has a member function, which is a function pointer to a function that takes a stack and returns void.

When we finally generate machine code for each of the functions we have in our program, it will be made up of sequences of G-machine operations expressed using assembly instructions. These instructions will still have to manipulate the G-machine stack (they still represent G-machine operations!), and thus, the resulting assembly subroutine will take as parameter a stack. It will then construct the function’s graph on that stack, as we’ve already seen. Thus, we express a compiled top-level function as a subroutine that takes a stack, and returns void. A global node holds in it the pointer to the function that it will call.

When our program will start, it will assume that there exists a top-level function f_main that takes 0 parameters. It will take that function, call it to produce the initial graph, and then let the unwind loop take care of the evaluation.

Thus, our program will initially look like this:

From runtime.c, lines 154 through 159
154
155
156
157
158
159

extern void f_main(struct stack* s);

int main(int argc, char** argv) {
    struct node_global* first_node = alloc_global(f_main, 0);
    struct node_base* result = eval((struct node_base*) first_node);
}

As we said, we expect an externally-declared subroutine f_main. We construct a global node for f_main with arity 0, and then start the execution using a function eval. What’s eval, though? It’s the function that will take care of creating a new stack, and evaluating the node that is passed to it using our unwind loop. eval itself is pretty terse:

From runtime.c, lines 144 through 152
144
145
146
147
148
149
150
151
152

struct node_base* eval(struct node_base* n) {
    struct stack program_stack;
    stack_init(&program_stack);
    stack_push(&program_stack, n);
    unwind(&program_stack);
    struct node_base* result = stack_pop(&program_stack);
    stack_free(&program_stack);
    return result;
}

We create a fresh program stack, start it off with whatever node we want to evaluate, and have unwind take care of the rest.

unwind is a direct implementation of the rules from Part 5:

From runtime.c, lines 118 through 142
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

void unwind(struct stack* s) {
    while(1) {
        struct node_base* peek = stack_peek(s, 0);
        if(peek->tag == NODE_APP) {
            struct node_app* n = (struct node_app*) peek;
            stack_push(s, n->left);
        } else if(peek->tag == NODE_GLOBAL) {
            struct node_global* n = (struct node_global*) peek;
            assert(s->count > n->arity);

            for(size_t i = 1; i <= n->arity; i++) {
                s->data[s->count - i]
                    = ((struct node_app*) s->data[s->count - i - 1])->right;
            }

            n->function(s);
        } else if(peek->tag == NODE_IND) {
            struct node_ind* n = (struct node_ind*) peek;
            stack_pop(s);
            stack_push(s, n->next);
        } else {
            break;
        }
    }
}

We can now come up with some simple programs. Let’s try writing out, by hand, main = { 320 + 6 }. We end up with:

From runtime1.c, entire file
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include "../runtime.h"

void f_add(struct stack* s) {
    struct node_num* left = (struct node_num*) eval(stack_peek(s, 0));
    struct node_num* right = (struct node_num*) eval(stack_peek(s, 1));
    stack_push(s, (struct node_base*) alloc_num(left->value + right->value));
}

void f_main(struct stack* s) {
    // PushInt 320
    stack_push(s, (struct node_base*) alloc_num(320));

    // PushInt 6
    stack_push(s, (struct node_base*) alloc_num(6));

    // PushGlobal f_add (the function for +)
    stack_push(s, (struct node_base*) alloc_global(f_add, 2));

    struct node_base* left;
    struct node_base* right;
    
    // MkApp
    left = stack_pop(s);
    right = stack_pop(s);
    stack_push(s, (struct node_base*) alloc_app(left, right));
    
    // MkApp
    left = stack_pop(s);
    right = stack_pop(s);
    stack_push(s, (struct node_base*) alloc_app(left, right));
}

If we add to the bottom of our main the following code:

printf("%d\n", ((struct node_num*) result)->value);

And compile and run our code:

gcc runtime.c examples/runtime1.c
./a.out

We get the output 326, which is exactly correct!

We now have a common set of functions and declarations that serve to support the code we generate from our compiler. Although this time, we wrote out f_main by hand, we will soon use LLVM to generate code for f_main and more. Once we get that going, we be able to compile our code!

Next time, we will start work on converting our G-machine instructions into machine code. We will set up LLVM and get our very first fully functional compiled programs in Part 8 - LLVM.