Where does a C-like language without heaps belong in the automata hierarchy?

Question

Assume that the language C', unlike C, has well-defined semantics, but has similar features: pointers and manual memory management through malloc and free. Assume that C'' is the same as C' without malloc and free; thus,the concept of a heap is absent in C''. Is C'' fundamentally weaker than C'? (I have a sense that this is the case because I cannot create lists and trees in C'', but can't be sure.) Can we map C' and C'' to deterministic TM and PDA, or some other automata, respectively?

Is there a work(s) that explores the computational powers associated with different language features? Roughly speaking, the answer I am trying to get at from the above paragraph is how important is the heap in the design of C.

Answer 1

Assuming we have an unbounded stack and pointers, it's a Turing machine. Since the stack is unbounded, we can get by very easily using a CPS-like style. Whenever we need to allocate memory, we'll just do it on a stack frame, then continue with the computation on the next. If our stack frames were bounded in size, of course we'd be a finite state machine. Here's a little example machine with no imports whatsoever (including no malloc). Of course on a real computer we'll eventually get a stack overflow with this. This model could be easily adjusted to have correct space usage, by adding a new stack frame only once we need to allocate.

#define NULL 0

typedef enum {
    ZERO,
    ONE,
} symbol;

typedef struct tape {
    struct tape* left;
    symbol sym;
    struct tape* right;
} tape;

typedef enum {
    A, B, DONE
} state;


int handle(tape* tape, state state);
int move_right(tape* tape, state state);
int move_left(tape* tape, state state);

int main() {
    tape start = {NULL, ZERO, NULL};
    return handle(&start, A);
}

int handle(tape* tape, state state) {
    // do some stuff
    switch (state) {
        case B:
            switch(tape->sym) {
                case ZERO:
                    return move_left(tape, DONE);
                case ONE:
                    tape->sym=ONE;
                    return move_left(tape, A);
            }
            break;
        case A:
            switch(tape->sym) {
                case ZERO:
                    tape->sym=ONE;
                    return move_right(tape, B);
                case ONE:
                    tape->sym=ZERO;
                    return move_right(tape, B);
            }
            return move_right(tape, state);
        case DONE:
            return tape->sym;
    };
};

int move_right(tape* tape0, state state) {
    tape new_tape;

    if (tape0->right == NULL) {
        new_tape = (tape){tape0, ZERO, NULL};
        tape0->right = &new_tape;
        return handle(&new_tape, state);
    } else {
        return handle(tape0->right, state);
    }
};

int move_left(tape* tape0, state state) {
    tape new_tape;

    if (tape0->left == NULL) {
        new_tape = (tape){NULL, ZERO, tape0};
        tape0->left = &new_tape;
        return handle(&new_tape, state);
    } else {
        return handle(tape0->left, state);
    }
};