Implementing arrays using a stack

Question

My programming language has no arrays, no lists, no pointers, no eval and no variable variables. All it has:

• Ordinary variables like you know them from most programming languages: They all have an exact name and a value.

• One stack. Functions provided are: push (add element to top), pop (remove element from top, get value) and empty (check if stack is empty)

My language is turing-complete. (Basic arithmetics, conditional jumps, etc implemented) That means, it must be possible to implement some sort of list or array, right?

But I have no idea how...

What I want to achieve: Create a function which can retrieve and/or change an element x of the stack.

I could easily add this function in the implementation of my language, in the interpreter, but I want to do it in my programming language.

• "Solution" one (Accessing an element x, counting from the stack top)

Create a loop. Pop off the element from the stack top x times. The last element popped of is element number x. I end up with a destroyed stack.

• Solution two:

Do the same as above, but store all popped off values in a second stack. Then you could move all elements back after you are done. But you know what? I don't have a second stack!

Answer 1

Do you have procedure calls and recursion? Then you do have a second stack, the call stack. If not, are you sure it's Turing complete, and not just a PDA?

Answer 2

Sounds like a homework question, as it flexing random bits of Computer Science...

I think you would want to use recursion to do this. Say I have something like this..

Queue globalQueue = new Queue();

Then I could have code that got element X like this

public Object findElement(stepsToTake s) {

    if (queue.empty()) {
        throw new EmptyQueueYouFailException();
    }

    Object o = queue.pop();


   if (s == 0) {
        queue.push(o);
        return o;
    }

    Object actualResult = findElement( s - 1 );
    //restore this element to the stack
    queue.push(o);
    //return actual result
    return actualResult;
}

So more likely than not I made some bug... have not thought through it super well. Especially worried that I will reorder the stack because of the order of my calls..

Hopefully this can get you thinking along the right lines to get a solution?

Answer 3

If you have only one stack, this is equivalent to a pushdown automaton, which can recognize context-free languages, and is not Turing-complete. Your proof of Turing completeness should inform how you can implement freeform memory access.

In general, to prove Turing-completeness, you must be able to show how your language can move left to right over a tape (or indirectly simulate this process), which corresponds roughly to a single higher-level array.