0
$\begingroup$

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.

$\endgroup$
  • 4
    $\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 supports Monica 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
  • 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 supports Monica 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
  • 2
    $\begingroup$ ... 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. $\endgroup$ – Marzio De Biasi Apr 28 at 20:40
2
$\begingroup$

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);
    }
};
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.