Internal stack

[cardillan]

Currently, the stack for recursive functions has to be stored in memory banks/memory cells. That has the limitation that only numerical values can be stored on stack. While Mindcode's optimizations are capable of removing unneeded variables from being stored on stack, it requires plenty of attention from the programmer and still makes many algorithms impossible to implement.

There are two possible approaches to implement an internal stack:

• Lookup arrays. The downside to this is that both push and pop require four instructions each, twice as many as an external stack.Makes the code both slower and larger.
• Specific stack-handling routines for each level of call nesting. This requires, at a first glance, 2 * (n + 2) instructions per call, where n is the number of variables stored on the stack. However, when more than one chain of recursive functions is implemented, the compiler needs to distribute the available instruction space between them – not an easy task. Help from the programmer might be required.

Both of the above approaches can be combined, though. When data types get implemented, it will be possible to further combine internal and external stacks, making the best of all approaches.

Current goal

The current goal is to implement an internal stack using stack-handling routines ("stack frames"). Lookup arrays will be reserved for storing local arrays. While functions return addresses could be stored in an external stack, the first iteration won't use them.

Basic principles:

• The internal stack will be generated when the allocate stack clause is not present in the program.
• There will be a compiler option stack-depth (default value perhaps 5 or 10). Can be set locally (at function declaration) to specify different stack depths for different functions.
• The effective instruction limit will be computed by subtracting current stack requirements from the configured limit. The effective limit may change as optimizations reduce stack size requirements.
• The code will be compiled as usual. The CALLREC and RETURNREC instructions will be resolved specifically in the final instruction resolution phase.
• The compiler stores old variables on the stack before making a recursive function call. This principle will be maintained in the new solution as well.
• List of variables to store on the stack for a given function will be obtained as a set of all variables in push instructions within the function.
• The stack frames will be implemented as decoration routines encapsulating the function itself.
• A call to a recursive function will call the current stack frame. The stack frame stores values of all variables and calls the function body.
• The function updates (increases/decreases) the stack frame index or address, avoiding the need to do so in the stack frames themselves.
• Recursive call may require modifying function parameters, however the previous value needs to be stored on the stack. Current values of the function parameters will be therefore copied to intermediate variables, and from these stored onto the stack. Parameters are restored from the stack directly, without the intermediate variables.
• Return from the function body is implemented as a jump into the current stack frame, avoiding the need to keep a separate return address.
• The last stack frame may contain error handling for the stack overflow.