In this lecture, we will explore the implementation of a variety of stack-based interpreters. The simple architecture described here is sufficient to implement most imperative programming languages.
Stack machine architecture
A generic Von Neumann architecture computer has a processor and memory; a few special-purpose registers are used to implement a stack for function calls and to track the current instruction. A simulator for this architecture might look like the following Java declarations:
Assume that the data/code memory is byte addressable but that the stack is 32-bit word-addressable.
----------------
0: | data memory |
| |
| |
----------------
cp:| code memory | begins right after data
| |
----------------
Instructions are placed in memory relative to a known address; by placing that address in a register instructions are relocatable.
For this discussion assume there are only integer data types. From an interpreter point of view there are only global (stored in memory) and local variables (stored on the stack; parameters are like locals).
Operations all occur on the stack rather than in registers. The stack holds either integers, booleans, or saved registers. You may call functions and use their results in expressions. The stack is word-addressible and always holds an int . There is no "type tag" associated with the stack elements. That means that the result of boolean operation LT ("less than") must be converted to an integer. Instructions are usually provided to do data conversions such as BOOLEAN_TRUE and BOOLEAN_FALSE for this purpose.
Instruction execution
Instructions are encoded in memory as opcodes. Opcodes are 8 bits and their operands are 32-bits. Operands of instructions are either data/code addresses or integer constants. For example, here are three instructions that perform 3+4 :
That is assembly code. In code memory, they are represented by machine code:
where const is opcode 0x0E and its operand as a 32-bit number is 0x00000003 . The opcode for add is 0x01; halt is 0x15.
Execution of a program proceeds by fetching an instruction and then jumping to some code that implements that instruction:
For example, the ADD instruction looks like this:
The Java code will look very much microcode, the "subatomic" instructions used to implement actual machine instructions in many older processors.
Global variable access
Global variable access is a matter of load and store instructions whose operand are addresses in data memory.
would result in:
After execution the memory with look like:
You can see that function f begins at address 4 after the data memory.
Method calls, frames
Most instructions are easy to implement. The function call and return instructions are easy to understand, but difficult to implement. This section describes the information flow from one function to another and back as well as how this information is encoded on the stack.
Simple call/return
To call another function, the program must record where it's at now so that it can return to the same spot upon completion of the subprogram. Pushing the return address on the stack and then doing a branch to the function implements call nicely. The ret (return) instruction can simply pop off the return address and set the instruction pointer to that location. The following C code:
would result in the following instructions:
Ignore the 0 operand for now. Before the call instruction the stack would look like:
| f work space | sp: | ... |
After the call but before the return in method g :
| ... |
----------------
| f+0x05 | (return address; 4 bytes beyond f() start)
sp,fp: | old fp | (saved fp used by f)
----------------
| g work space |
| ... |
To perform the return instruction, the interpreter pops the old frame pointer and sets the instruction pointer to the return address on the stack (popping it off). Ignore the frame pointer for now.
Functions with return values
What about return values? The return value is left on top the stack and then the function call stack activation record is cleaned up and the return value is pushed back on the stack:
would result in the following instructions:
f:
call g
ret 0
g:
const 3
retv 0
After the call but before the return in method g :
| ... |
----------------
| f+0x05 | (return address)
fp: | old fp |
----------------
sp: | 3 |
| ... |
Parameters and local variables
What is a the end of the frame pointer? It is used access local variables and parameters off the stack.
Here is a stack activation record in its full glory for a function call right after the execution of a call instruction:
| ... |
----------------
| arg 1 |
| arg 2 |
| ... |
| arg n |
| ret addr |
fp:| old fp |
| local 1 |
| local 2 |
| ... |
| local m |
----------------
| work space |
| ... |
would result in the following instructions:
Parameters are placed in order on top of the stack before the called is executed. The frame pointer points in to the middle of the stack frameAnd parameters are at positive all sets while local variables or add negative offsets. The first local variable is add negative one. The last parameter is an offset 2, the second to last parameter is an offset 3, and so on.
In general parameter i is at stack[fp+2+(n-i)] since we push args in specified order rather than reverse. Local i is at stack[fp-i] . The compiler is required to compute an integer constant such as 2 that accesses the first argument or -1 that accesses the first local.
call. The call instruction then does the following:
- fetch the target address operand
- save the instruction pointer by pushing on the stack
- save the old frame pointer
- set the frame pointer to point to the current stack top, sp.
- perform a branch to the target address by setting the instruction pointer.
And now the ret and retv instructions operand. The operand indicates how many parameters there are to pop off before pushing the return value (if any). retv will first save the top of stack, since that is the function return value, and then pop the activation record off. After the stack is cleaned up, retv will push the return value back onto the stack.
return. The ret instruction does the following:
- fetch the operator and that indicates how many arguments, n , to pop off
- set the stack pointer to the frame pointer
- pop the frame pointer off the stack; set fp
- pop the return address off the stack; set ip
- pop n arguments off the stack
Complete instruction set
Program Loading and Launching
To execute code one must first loaded into memory at the appropriate spot, which is just after the data memory. The following 2 functions are in the interpreter.
To begin execution, one simulates a call from the operating system to the main program start address.
A generic assembler
An assembler for stack machine is usually very simple. It is a function note a list of instructions and an instruction to opcode mapping. After assembly, the invoking program pulls out the machine code, the data memory size, and the address of the main program:
Inside the interpreter is a set of opcode definitions that are sent to the assembler:
An array of strings representing the names of all valid opcodes is sent to the assembler so that it knows how to assemble. The position in the string array is the opcode. In this way, your assembler/interpeter is easily extendable:
Finally, in order to disassemble code, it is useful to define which opcodes have operands:
As instructions are read, the location in data memory and code memory are incremented:
Here is the assembly grammar, similar to what to build for your project in the grammar marathon.
There are a number of methods triggered by the grammar to implement assembly:
A subclass of the grammar defines them.
Symbol table management
There are three classes of interest: Symbol , CodeSymbol , and DataSymbol . A symbol is just a name with and associated address. For implementation sake, the symbol also knows whether or not it's a forward reference and whether or not it has been defined. This allows us to implement the standard scheme of forward reference and we discussed previously:
The 2 concrete symbol table classes do everything in their constructors:
Byte-code interpreter for C-like language
The above architecture is sufficient for C w/o structs. Here are some relevant questions:# Why not simulate a register machine instead of a stack machine?
- Would your stack be typed (in other words, if you push 34 on the stack would you know it's an int later on)?
- What could you do to make the interpreter more efficient (including reorganizing byte codes)?
- Consider how you might compile the byte code on the fly. In particular, how you would generate and execute the following:
- a threaded interpreter
- native stack code
- register code
Byte-code interpreter with data aggregates
Assuming you have a basic interpreter that handles simple primitives like int and float , how would you add data aggregate support? In other words, how would you translate
Would you need a new instruction?
Byte-code interpreter with pointers
Ok, now add pointers like the following:
- What would the bytecodes look like
- What would the bytecodes for pay->payment=330; look like if pay were a pointer to a payment structure from above Assume pay is at address 0?
Byte-code interpreter with polymorphism
Method calls are pretty simple for a non-object-oriented language like C. If you call function foo() , you can generate the simple:
instruction. What if you want to call method getEmployeeID() on a Payment object defined as follows?
- Is the layout of an object any different in memory than a struct ? Does an object require more memory space for the same list of fields?
- What byte codes would you generate for p.getEmployeeID() for local p ?
- Do you need to have symbol table information around at run-time to implement polymorphism? Do you need type information stored in each object?