When two stacks are better than one. Also an introduction to the type annotation syntax which will be introduced in an upcoming version of Cat.
The main role of Cat is to provide an intermediate representation of an arbitrary functional or imperative high-level language which can be:
Mapping Cat to a lower level language like the MSIL poses some particular challenges since the MSIL is based on two stacks:
a variable/argument stack
an evaluation stack
Any straightforward mapping from Cat to MSIL slow and cumbersome because I have to emulate an open-ended stack. Whenever I want to add or subtract two numbers the compiler has to move the values from the Cat stack to the evaulation stack, execute the MSIL opcode, and then move the result back to the Cat stack.
A nice solution to this problem, is to extend Cat with a second stack.
Internally Cat uses a type notation for the purposes of optimization, and to prepare for the fact that upcoming versions will support static typing. The challenge I faced was to express the type of a Cat program in a multi-stack language.
The best way to explain my proposed notation is throught the example of an integer addition function:
add : (a:int, b:int)() => (c:int)()
I would read this as follows: the function add consumes two integer values from the main stack, and no values on the second stack. When add terminates it produces a single integer value on the main stack.
Now since I want to map my dialect of Cat to various byte-codes such as MSIL, there will be no primitive which actually adds values from the top of the main stack. All primitive arithmetic operations occur on the secondary stack. This means that the integer add function will need to be defined as a standard library function in terms of the following primitives:
The type notation for def in future versions will be optional. I want to support dynamic type checking, static type checking, and static type inference (ambitious I know).
So this in of itself hasn't yet solved the problem of frequent moving back and forth of values between stacks, however, there is now potential for the Cat optimization algorithms to be applied intelligently. For example I can write the following optimization rule:
(storeint loadint) = ()
This optimization rule states simply that any-time you have a consecutive storeint and loadint operation you can simply eliminate them both. This becomes useful when you see something like:
This is only the tip of the iceberg of the optimization engine which I have planned for Cat. The ultimate goal is to develop a pattern-matching and rewriting macro language for Cat which is type-aware. What I find amusing is that the type annotations are more complicated than the actual code.
OK, my example of more than one stack wasn't so good. A better example can be found at http://cm.bell-labs.com/cm/cs/who/dmr/clcs.html (the original "how C works on a PDP-11" paper). This paper refers to a stack pointer that points to the next instruction to execute (and where return adresses are stored when calling a function), and a stack to hold arguments passed to the function. I believe these stacks are often merged into one, but they don't have to be.
To be honest, I'm not sure. The book I bought on assembly code was for the Motorola 68000 (yes, it's outdated), and I didn't check it before posting earlier. And although I was positive that the 68000 series had two stacks, Wikipedia says it didn't really ( http://en.wikipedia.org/wiki/Motorola_68000 ).
Well, Wikipedia says there was a second stack pointer for supervisory mode, but it did exactly the same thing as the "regular" stack pointer. When I get home I'll have to check my books to see where I got the "most CPUs have more than one stack" idea from.
The Intel x86 has one hardware stack register, ESP. Function calls place the return address on the stacked pointed to by ESP. There are other opcodes that add/remove data from the stack pointed to by ESP, but they all manipulate the ESP register.
What you might be getting confused by is that each protection ring on the x86 architecture has its own copy of ESP, but that's not a detail that readily inpacts code written.
The Motorola 68000 has one hardware stack register, A7. Like the Intel version, there are various opcodes that manipulate the stack pointed to by A7. And like the Intel, usermode has one copy of A7, and the supervisor mode has a separate copy of A7. Again, not normally a concern.
The only CPU that I know of that has two explicit stacks is the Motorola 6809, an 8-bit CPU that was the precursor to the Motorola 68000. In this CPU, the stacks are registers S and U---S is used for saving return addresses, but other than that, there is no real difference between using the S stack and the U stack (other than realizing that the S stack may have return addresses on it). All opcodes (except those that involve function calls) that manipulate the stack have opcodes that work with S or U. This CPU has no usermode/supervisor mode distinction.
Yes, working with many stacks is always a good idea. Exception handling with "try-catch" blocks is yet another example where stacks are needed / useful. What if you'll need to use a lot of stacks?? A syntax like: add ()()()...(a:int, b:int)()...() => ()()()...(c:int)()...() would be very inappropriate.
Instead, I propose you to:
(1) The majority of the functions will work with the default stack.
(2) There must be two UNARY operators (MOVE / COPY) which moves / copies the top of a given stack to the top of the default one.
(3) There must be a UNARY operator (SET_DEFAULT_STCACK) which does exactly what its name suggests.
This stuff ALWAYS works (can work with dynamic stacks) and it's appropriate for handling as many stacks as nneeded.