<p>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.</p>

<pre><code>#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(&amp;start, A);
}

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

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

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

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

    if (tape0-&gt;left == NULL) {
        new_tape = (tape){NULL, ZERO, tape0};
        tape0-&gt;left = &amp;new_tape;
        return handle(&amp;new_tape, state);
    } else {
        return handle(tape0-&gt;left, state);
    }
};
</code></pre>

CC BY-SA 4.0
2019-11-05T20:54:22.253Z
2019-11-05T20:54:22.253Z
Jason Carr
<p>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?</p>

<p>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.</p>

CC BY-SA 4.0
2019-04-28T06:56:25.367Z
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
CC BY-SA 4.0
2019-04-28T07:56:24.100Z
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.
Abhishek
CC BY-SA 4.0
2019-04-28T12:17:51.477Z
@A.Singh Note that  malloc, realloc, calloc, free are *library functions* in C. So C is in some sense already your C''. See e.g. the Wikipedia article [C dynamic memory allocation](https://en.wikipedia.org/wiki/C_dynamic_memory_allocation).
Martin Berger
CC BY-SA 4.0
2019-04-28T12:19:32.823Z
Yes, it’s a bit tricky, but doable. What I would envision is to first rewrite the program so that it consists of only one function that executes an endless loop, where each iteration of the loop performs one statement, modifying some sort of internal state. Then to implement malloc() on the stack, one would keep a linked list of free entries to be used; whenever it runs out of space, the function would call itself and augment the list with a pointer to a local variable in the new stack frame. (None of these calls would ever return.)
Emil Jeřábek
CC BY-SA 4.0
2019-04-28T12:24:22.490Z
@MartinBerger This does not answer the question. Normally the library functions are not implemented by language primitives, but using syscalls that ask the operating system to increase the amount of memory allocated for the process.
Emil Jeřábek
CC BY-SA 4.0
2019-04-28T12:28:32.513Z
@EmilJeřábek Sure, but calls to the OS are a bit magic, indeed induce concurrency, and will certainly give you Turing completeness, so I feel that OS-calls are not in the spirit of C''. As you point out yourself, one way of implementing a heap in a C-like language with arbitrary-size arrays, is to allocate an array at startup (in "main") and deallocate it upon termination.
Martin Berger
CC BY-SA 4.0
2019-04-28T12:31:04.873Z
@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
CC BY-SA 4.0
2019-04-28T12:32:03.973Z
... from regular to context-free languages. There was a quite detailed answer somewhere that spells this out, but I can’t find it at the moment. Here again, the result is the same even if you disallow all dynamic memory allocation features.
Emil Jeřábek
CC BY-SA 4.0
2019-04-28T15:49:51.100Z
@MartinBerger I can’t figure out what is it you are arguing for. On the one hand, you say that OS calls are a bit magic and not in the spirit of C''. (I absolutely agree.) On the other hand, in your previous comment, you seemed to argue that “C without malloc and free” is just C, because malloc and free are only library functions, and therefore can be implemented in the rest of the language. Your two comments seem to directly contradict each other. (And, of course, you cannot implement a heap just by allocating an array at startup, as you don’t know the needed size in advance.)
Emil Jeřábek
CC BY-SA 4.0
2019-04-28T16:49:39.707Z
I can see how this question can be seen as being poorly defined. If one views C as just assembly with macros, indeed malloc and free can be implemented within it. But I meant to say C' is a C-like language which has malloc and free as primitives; inline assembly is also not allowed in C'. Note that classic pointer analyses like points-to often deal with a c-like language with features like pointer arithmetic, dereferences, malloc, and free.
Abhishek
CC BY-SA 4.0
2019-04-28T16:58:02.430Z
@EmilJeřábek Thanks for the answer. I will try to construct such a function, and see how it goes. Since the function just keeps increasing the amount of memory allocated, I am assuming you will also keep a map in this pseudo-heap, which will tell you which regions are currently valid in the program. I will try to create a linked list implementation on top of such a function and let you know how it goes.
Abhishek
CC BY-SA 4.0
2019-04-28T17:01:15.940Z
Since I am a first time poster, I would appreciate it if the downvoter could explain how I could improve the question, or maybe if this type of question was not suited to this forum :).
Abhishek
CC BY-SA 4.0
2019-04-28T17:04:26.503Z
@EmilJeřábek I didn't realise that the question was looking for an *unbounded* heap.
Martin Berger
CC BY-SA 4.0
2019-04-28T17:33:22.183Z
@EmilJeřábek When I said unbounded stack and heap are allowed, I assumed that the datatypes involved in the language are integers, as opposed to bitvectors, again a major deviation from standard C.
Abhishek
CC BY-SA 4.0
2019-04-28T18:32:59.543Z
In C'': with two unbounded variables (integers) you already have a Turing complete language even without functions/recursion (see [counter machine](https://en.wikipedia.org/wiki/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
CC BY-SA 4.0
2019-04-28T19:00:47.460Z
@MarzioDeBiasi Thanks for the counter machine link. The problem I am faced with is that I do not want unbounded variables, but do want unbounded stack and heap. But this means involving unbounded pointers, which, with casts, leads to unbounded variables :). So, lets say we have integer pointers, no casts, all non-pointer variables are bitvectors. I think this is the language between the bounded and unbounded extremes that Emil tried to address. Do you think a list could be emulated in such a language?
Abhishek
CC BY-SA 4.0
2019-04-28T19:19:22.920Z
@MarzioDeBiasi It is a little hard for me to see that C'' (bounded) with pointers and recursion has the same powers as a PDA. In a PDA, you can only see the top of the stack, while that is not true in C''. Can C'' (bounded) not correspond to some intermediate automata, more powerful than PDA but less than TM?
Abhishek
CC BY-SA 4.0
2019-04-28T20:40:47.727Z
... 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
CC BY-SA 4.0
2019-04-28T23:09:14.227Z
@MarzioDeBiasi I like this solution and can't see anything wrong with it. I can also see how this relates to what Emil was suggesting. Thanks all!
Abhishek
CC BY-SA 4.0
2019-05-03T03:51:04.487Z
If you have recursion and loops, you can easily write an Turing machine simulator, even without using `malloc`, no?
xrq
CC BY-SA 4.0
2019-05-05T05:12:03.210Z
@xuq01 such a simulation is suggested in the last comment by Marzio.
Abhishek
<automata-theory><pl.programming-languages>
Where does a C-like language without heaps belong in the automata hierarchy?
Abhishek
# Where does a C-like language without heaps belong in the automata hierarchy?

(Asked by: username_0 on 2019-04-28)

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.

**Tags:** automata-theory, pl.programming-languages
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: @A.Singh Note that  malloc, realloc, calloc, free are *library functions* in C. So C is in some sense already your C''. See e.g. the Wikipedia article [C dynamic memory allocation](https://en.wikipedia.org/wiki/C_dynamic_memory_allocation).  
> **username_1**: Yes, it’s a bit tricky, but doable. What I would envision is to first rewrite the program so that it consists of only one function that executes an endless loop, where each iteration of the loop performs one statement, modifying some sort of internal state. Then to implement malloc() on the stack, one would keep a linked list of free entries to be used; whenever it runs out of space, the function would call itself and augment the list with a pointer to a local variable in the new stack frame. (None of these calls would ever return.)  
> **username_1**: @MartinBerger This does not answer the question. Normally the library functions are not implemented by language primitives, but using syscalls that ask the operating system to increase the amount of memory allocated for the process.  
> **username_2**: @EmilJeřábek Sure, but calls to the OS are a bit magic, indeed induce concurrency, and will certainly give you Turing completeness, so I feel that OS-calls are not in the spirit of C''. As you point out yourself, one way of implementing a heap in a C-like language with arbitrary-size arrays, is to allocate an array at startup (in "main") and deallocate it upon termination.  
> **username_1**: @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 ...  
> **username_1**: ... from regular to context-free languages. There was a quite detailed answer somewhere that spells this out, but I can’t find it at the moment. Here again, the result is the same even if you disallow all dynamic memory allocation features.  
> **username_1**: @MartinBerger I can’t figure out what is it you are arguing for. On the one hand, you say that OS calls are a bit magic and not in the spirit of C''. (I absolutely agree.) On the other hand, in your previous comment, you seemed to argue that “C without malloc and free” is just C, because malloc and free are only library functions, and therefore can be implemented in the rest of the language. Your two comments seem to directly contradict each other. (And, of course, you cannot implement a heap just by allocating an array at startup, as you don’t know the needed size in advance.)  
> **username_0**: I can see how this question can be seen as being poorly defined. If one views C as just assembly with macros, indeed malloc and free can be implemented within it. But I meant to say C' is a C-like language which has malloc and free as primitives; inline assembly is also not allowed in C'. Note that classic pointer analyses like points-to often deal with a c-like language with features like pointer arithmetic, dereferences, malloc, and free.  
> **username_0**: @EmilJeřábek Thanks for the answer. I will try to construct such a function, and see how it goes. Since the function just keeps increasing the amount of memory allocated, I am assuming you will also keep a map in this pseudo-heap, which will tell you which regions are currently valid in the program. I will try to create a linked list implementation on top of such a function and let you know how it goes.  
> **username_0**: Since I am a first time poster, I would appreciate it if the downvoter could explain how I could improve the question, or maybe if this type of question was not suited to this forum :).  
> **username_2**: @EmilJeřábek I didn't realise that the question was looking for an *unbounded* heap.  
> **username_0**: @EmilJeřábek When I said unbounded stack and heap are allowed, I assumed that the datatypes involved in the language are integers, as opposed to bitvectors, again a major deviation from standard C.  
> **username_3**: In C'': with two unbounded variables (integers) you already have a Turing complete language even without functions/recursion (see [counter machine](https://en.wikipedia.org/wiki/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).  
> **username_0**: @MarzioDeBiasi Thanks for the counter machine link. The problem I am faced with is that I do not want unbounded variables, but do want unbounded stack and heap. But this means involving unbounded pointers, which, with casts, leads to unbounded variables :). So, lets say we have integer pointers, no casts, all non-pointer variables are bitvectors. I think this is the language between the bounded and unbounded extremes that Emil tried to address. Do you think a list could be emulated in such a language?  
> **username_0**: @MarzioDeBiasi It is a little hard for me to see that C'' (bounded) with pointers and recursion has the same powers as a PDA. In a PDA, you can only see the top of the stack, while that is not true in C''. Can C'' (bounded) not correspond to some intermediate automata, more powerful than PDA but less than TM?  
> **username_3**: ... 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.  
> **username_0**: @MarzioDeBiasi I like this solution and can't see anything wrong with it. I can also see how this relates to what Emil was suggesting. Thanks all!  
> **username_4**: If you have recursion and loops, you can easily write an Turing machine simulator, even without using `malloc`, no?  
> **username_0**: @xuq01 such a simulation is suggested in the last comment by Marzio.  

---

## 1 answers

### Answer by username_5 on 2019-11-05. Score: 2 | Accepted answer

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


---

