Stack disciplines

1) Internal pointers

The machine will keep pointers to the TOS, IVAR, and PVAR bases. There would be no storage of Vars or Stack in the machine. It will do a memory reference every time it needs to access the stack or a variable. A typical binary opcode would do 2 fetches, an ALU operation, and a memory store. This is very similar to the way the existing machines work currently.

Issues:

Complexity - This will be simple. The amount of control required is small. It is all done by the main PLA.

Size - There will no large register files, therefore the data path size would be small. The PLA may be much larger.

Functionality - It is easy to implement everything in LISP. It would require few restrictions or special case in the language. It would be tempting to first build a machine like this and then increase the performance by using another scheme. This would mean that 2 iterations on the Lisp software would be required.

Performance - The speed would be well below (factor of 4) the speed of the other methods but still better than a DLion. Many memory references are required to access the stack and VARS. Most operations will require several PLA cycles.

Sequences - Sequences will likely be required. The PLA can not handle all the opcodes.

2) Full frames

The machine will keep several (4) full frames in the machine. Each frame will maintain one function invocation. At function call time, an empty frame will be created by writting out an internal frame. Then the arguments from the calling frame will be moved to the new frame. If the number of Vars exceed the maximum aloted amount, then the extras must be kept in dynamically allocated storage. Likewise if the size of the stack for this frame is too large, the compiler will have too emit code to write out parts of the stack.

Issues:

Performance - The speed will be fast (perhaps equal to a Dorado). Almost all stack and VAR references will be internal. There would be pathological cases which would significantly slow the machine if they occured often.

Functionality - There will be many special cases needed to deal with the fixed length restrictions of the frames.

Frame Allocation - Stack Frames would have to be dynamically allocated and deallocated.

Paging - It is possible that stack space would not have to be locked down. Individual frames might have to be but not the whole stack space.

Special Cases:

#Args - If the number of args exceed 8, then an external block must be assigned and the variables accessed through that block.

Stack Overflow - The maximum size of a frame is calculated by the compiler. If it exceeds the size of the stack buffer, then the compiler emits code to save the bottom part of the stack in an external block of storage.

Spaghetti stack - It is not clear how to implement spaghetti stack functions.

FVar lookup - Any free variable lookup must take into account that some frames will not be in the machine’s internal memory.

3) Stack Tip with Cached Vars

This uses a fifo type stack for most of the frames. There would be two forms for stack frames. The first form would be created by function call. The second would be used when some spagetti stack function was called.

Issues:

Speed - Most Var and Stack references would be in the machine. The stack frames would be small allowing fast reading and writing of frames.

Quadword alignment - To operate quickly, the start of the frame would want to be quadword aligned. This requiures the compiler to adjust the stack before pushing arguments.

Complexity - The control mechanisms in the machine would be complex. The stack tip control is included.

Stack Overflow - It is not yet clear how to handle this.

UFNs - Having fast UFNs are hard with this scheme. Because the header precedes the arguments, the arguments would have to be moved. Doing the quadword alignment would be hard.

4) Dragon

This uses a ring buffer of frames and a ring buffer of pointers to the start of the frames.

Issues:

Performance - Fast.

Complexity - Large.

Philosopical Questions

CommonLisp: To what extent should Tamarin support CommonLisp?

Multiple Software Revisions: Tamarin is designed to be an evolvable processor going through several versions of hardware, each with better performance. Major software revisions must occur once. Can they occur with more than one version.

Spaghetti Stacks: Does InterLisp need to continue to support spaghetti stacks? Can the branching in spaghetti stacks be reduced to just branches combining at the top level? If not, can IVars and PVars both be put in the basic frame?

Problem Areas

UFNs:UFNs are a critical part of the existing system. They provide a convenient and efficient way to escape out of complicated opcodes. They must be fast.

Stack Overflow: Overflow must be detected.

Lambda Nospread: These calls have a variable number of arguments. They are hard to handle in schemes that have limits on the size of stack frames.

Apply, Apply*: These cause problems because they make the number of arguments to a function unknown at compile time.

ExprApply: If a function is undefined, the function name is pushed on the stack and expreApply is called. This causes slight problems because it makes the FNCALL opcodes non-restartable.

Number of args > k (8): Some schemes make large number of arguments harder.

CommonLisp Arguments: This is different than InterLisp. Lambda nospread are just a list (&REST), etc.

CommonLisp Closures: This is new to CommonLisp and will require extra opcodes, etc.

CommonLisp Multiple Return Values: What is required for this?

Spaghetti Stacks: The branching stack structure prevents having a simple stack oriented discipline. Having both Basic frames and Frame extensions create complexity. Can we do away with Spaghetti stacks. Otherwise, Can we move PVars into the basic frame?

Stack Pointers: A low-cost stack pointer is a must. The ability to point at a given frame occurs all the time. The high-cost overhead of usecounts and copying stacks doesn’t want to occur until that frame starts to run.