Tutorial :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!


Solution:1

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?


Solution:2

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?


Solution: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.


Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »