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

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.

• If recursion is still allowed, you have access to an unbounded stack, and using pointers to local variables you can simulate malloc and free on the stack. – Emil Jeřábek supports Monica Apr 28 at 6:56
• Recursion is allowed. Stack (and heap for C') is unbounded. I can kinda see how to create a list on the stack using recursion but the recursive function would have to not return, and somehow pass control back to the initial caller. Deleting a node of this list seems even trickier. – A. Singh Apr 28 at 7:56
• @A.Singh There is one important caveat: all of the above only makes sense for a modified version of the language that allows unbounded pointers. In the actual C language, as defined by the standard, there are various syntactic and semantic features that force all integer and pointer types to have fixed finite domain. This effectively makes the program almost a finite automaton. However, it is apparently possible (in principle) for a conforming implementation to have a truly unbounded recursion stack (if you do not create pointers to its entries). This increases the theoretical power of C ... – Emil Jeřábek supports Monica Apr 28 at 12:31
• In C'': with two unbounded variables (integers) you already have a Turing complete language even without functions/recursion (see counter machine ). If variables are bounded (bitvectors) then with the recursion stack you have a simple Pushdown Automata (no way to emulate a list or a double stack). – Marzio De Biasi Apr 28 at 18:32
• ... I think that with unbounded pointers a possible solution can be: define a structure for an element of the list: struct listel { listel *first, listel *next, listel *last, int value } and use recursion: void rec( listel *tape_right, listel *tape_left, int currstate) then use a local variable to eventaully extend tape_right or tape_left according to currstate and symbol read (or modify tape_right, tape_left), then call rec again for the next Turing machine step. – Marzio De Biasi Apr 28 at 20:40

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);
}
};