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.

  • 3
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Apr 28 at 6:56
  • $\begingroup$ 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. $\endgroup$ – A. Singh Apr 28 at 7:56
  • $\begingroup$ @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. $\endgroup$ – Martin Berger Apr 28 at 12:17
  • 2
    $\begingroup$ @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 ... $\endgroup$ – Emil Jeřábek Apr 28 at 12:31
  • 1
    $\begingroup$ 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). $\endgroup$ – Marzio De Biasi Apr 28 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.