4 ms·
IIRC, strictly speaking stack machines are not allowed to modify values in place on the stack. Any decent JIT or interpreter is likely to recognize that it can
by Merad 10y ago
IIRC, strictly speaking stack machines are not allowed to modify values in place on the stack. Any decent JIT or interpreter is likely to recognize that it can optimize certain operations by performing them in place, but the bytecode/IL/whatever will always be "pop two values and swap them".
- deleted 10y ago[deleted]
- lacampbell 10y ago> IIRC, strictly speaking stack machines are not allowed to modify values in place on the stack. I am curious as to where you heard this. Modifying the stack in place seems like an implementation detail. I mean even if swap wasn't a primitive (which again seems really far fetched), you are still going to have to modify part of the stack in place eventually. It's just in the naiive way you decrement the stack pointer twice then increment it twice, while in the way I outline you don't bother since the length of the stack is the same after the operation is completed. Probably easier to write less and pseudo code more - I am assuming a downward growing stack here # First approach temp_a = pop(stack) temp_b = pop(stack) push(stack, temp_a) push(stack, temp_b) # second approach temp_a = stack[0] stack[0] = stack[1] stack[1] = temp_a
- deleted 10y ago[deleted]
- topkekz 10y agoA stack is an abstract type having two operations: push(element) and pop(). The implementation can cheat till it's transparent to the user. To quote CLRS, The INSERT operation on a stack is often called PUSH, and the DELETE operation, which does not take an element argument, is often called POP. These names are allusions to physical stacks, such as the spring-loaded stacks of plates used in cafeterias. The order in which plates are popped from the stack is the reverse of the order in which they were pushed onto the stack, since only the top plate is accessible.
- MichaelBurge 10y ago"A stack" is an abstract type, but "The Stack" isn't.
- lacampbell 10y ago"The Stack" of a virtual machine definitely is.
- Merad 10y ago> I am curious as to where you heard this. Modifying the stack in place seems like an implementation detail. You are correct, but as the other reply mentioned, when we're talking about abstract specifications a stack typically doesn't allow reads and writes to arbitrary indices, therefore a stack machine can't perform an in-place swap. The implementation will almost certainly optimize the operation as you're describing, but I'd still expect to see a swap operation defined as "pop pop push push". Likewise I would usually expect to see an add described as popping two arguments and pushing one result, even thought the implementation probably pops one argument, then reads the second and overwrites it with the result. In short, it's the abstract description of the thing vs the actual implementation.
- lacampbell 10y agoI don't see why the abstract specification should mention pushing or popping at all. The abstract specification for swap is simply "swaps the first and second elements of the stack". How that's achieved doesn't seem important, and it seems odd to me to define it in terms of primitive operations it's not actually defined in terms of - unless it's some ultra minimalist Forth thing where swap isn't a primitive.
- frjalex 10y agoI can only partially agree with this - having a stack exposed to modification would virtually make it not a stack.