question on stacks in general

[digitaladdictions]

It appears the whole "stack" methodology is purely an abstract notion. The HACK hardware could care the less if we use a stack. (Other than our assembler hard coding some addresses for use in writing stack based logic). Indeed using the stack adds substantial overhead in terms of the number of instructions required for simple operations. The earlier projects in the first half of the book such as manipulating the display on when a key is being held down did not use stack based logic.  

I understand why we would implement a stack based virtual machine since we need a common target to compile our high-level language too for portability. But using a VM such as the JVM or the CLR always did come at a bit of a performance hit. At least early on. I know they are pretty well optimized now. But there was a good reason to accept that performance hit.

What I don't understand is why native programs that run on our regular computers can be decompiled into stack based assembly code. Or why we use stack based logic when writing programs in x86 assembly.  There should be no VM machine in play. Why are we not programming in a way that more directly achieves our ends with fewer clock cycles?

Is the x86 architecture designed at the hardware level to take advantage of this? Is it just the only way that we can express our programs in a way that we can turn into machine code any sort of methodological manner? Said another way, Would it just be too hard of a problem to try to express complex programs in any other way? Does it have something to do with the operating system?  When we talk about optimization as a compiler feature is substituting long series of stack based instructions for fewer "direct" instructions what we are speaking of?  Am I just getting ahead of myself and these questions will be answered in the book?

Thanks

-- Justin

[ybakos]

The virtual machine architecture provides a single intermediate target for any number of languages to compile to, resulting in m + n translations for different hardware platforms, rather than m * n. See slide 4 here: http://www.nand2tetris.org/lectures/PDF/lecture%2007%20virtual%20machine%20I.pdf

[cadet1620]

Modern computers are hybrid architectures that have built in hardware assisted stack operations as well as the more common register/register, register/memory and memory/memory operations.

The VM's stack machine is just an abstraction that simplifies the design of the compiler and supplies a common point to select between code generators for different target processors.

There is no requirement for the generated code to adhere to the stack model. Here are some examples from my optimizing VM translator. The comments show the Jack source code and the VM code that was generated by my Jack compiler. The generated ASM for these source line completely ignore the stack.

    /// 38:              let iterations = 31;
// push constant 31
// pop static 0                     //    iterations
    @31
    D=A
    @Cordic.0
    M=D

    /// 151:             let i = i+1;
// push local 0                       //    i
// push constant 1
// add
// pop local 0                        //    i
    @LCL
    A=M
    M=M+1

    /// 461:             let msw = msw|MSB;
// push this 0                        //    msw
// push static 0                      //    MSB
// or
// pop this 0                         //    msw
    @Float.0
    D=M
    @THIS
    A=M
    M=M|D

My translator does this sort of optimization by preprocessing the VM code into a somewhat smarter VM code that includes commands like "move constant 31 static 0".


As to why we use stack based programming, it naturally fits the concept of breaking down larger jobs down into smaller and smaller subtasks, and keeping track of the data required for all the subtasks.

Part of the confusion is the overloading of the term VM.  It's used as this intermediate abstraction that doesn't exist outside a compiler, as a cross-platform portability aid as in the JVM, as a way to run working but no longer supported MS operating systems on modern broken MS OSes (ahem!), as one of many protected environments running on a host server...

--Mark