Implementing arrays using a stack
- by Zack
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!
