How to pass around the spaghetti stack activation record for a rich call stack?

I am in the process of implementing a toy language and am on the step of implementing the call stack (ideally with async-ness, closures, continuation, etc.).

I have divided it into 3 types of functions:

1. The native / VM functions.
2. The simple functions.
3. The complex functions.

The native / VM functions are the lowest-level. They are the syscalls so to speak. They don't require managing a call-stack, because they are at the lowest level. You simply stack inputs, and flush basically.

The next level above the VM functions are the "simple" functions. These are things like memory allocation and other fundamental things that everything requires. These functions are implemented using a basic call-stack that has a pretty limited size. You can limit the size because (a) you know the structure of the functions using it, and (b) the functions don't nest arbitrarily deep or have tons of local variables. They are relatively simple higher-level functions, which use a simple call stack where you just make a syscall to adjust the stack pointer and that is "creating a new activation record".

The final level are the "complex" functions. These are your main app functions. Complex functions can contain other complex functions, and on-and-on. They also can contain simple functions and directly call VM functions.

I am going to ask about the complex functions, how to implement a spaghetti / cactus stack with them.

So basically, every complex function, when it is invoked, creates a "complex activation record", which is part of a cactus stack, a tree if you will, a non-contiguous tree. To create an activation record at this level is much more complex of a procedure than the simple "move a stack pointer" single step of the simple functions. First, it must allocate memory, which means an algorithm for searching for free memory. Then it must fill those areas of memory with values, potentially from all over the place. Then finally, it jumps to the next function.

My question that I have been struggling with is, how do you pass around these complex activation records? The way I keep track of the simple activation records is by having a dedicated register so-to-speak, which stores where the top of the stack is. From there, no matter where we are in the code I can easily get access to the call stack activation record desired.

But when the activation record is more complex (in my case, each record is a nested tree where each node can only have max 16 elements), it's hard to tell how to (a) create it, and (b) more specifically, how to pass it around.

How do you pass around the complex activation record?

What I am imagining so far is this:

callComplexFunction1a(a, b)    callComplexFunction2a(a)      callComplexFunction3a(x)    callComplexFunction2b(z)  callComplexFunction1b(a)    callComplexFunction2d(b)  callComplexFunction1c(z)  

That each one of those converted into something like this:

createComplexActivationRecord() // a "simple" function  insert a into activation record slot // a simple function  insert b as well // a simple function, composed of many simple functions + VM functions  jumpTo next one  

But the trick is, when you "jump to the next one", you start fresh, referencing the current/last activation record, to find your input values. How do I get access to this activation record?

// this is an involved tree of simple + vm function calls  // resulting in storage in a specific place, which let's say we  // store that at a specific known address in memory.  createComplexActivationRecord()    storedAt(x)  // now we are at the next simple call stack usage,  // inserting some values near x  insert(a, x)  

But even here, when insert is called, it is converted in reality to a set of simpler functions:

createSimpleActivationRecord()  store(0, a)  store(1, x)  

I just can't seem to pinpoint how this x is passed around under the hood. Can you please help me demonstrate with some pseudocode?

const STACK_TOP = 0  const STORE = new Uint32Array(65536)    function createSimpleActivationRecord(size) {    STORE[STACK_TOP] += size  }    function store(index, value) {    STORE[STACK_TOP + index] = value  }  

See, it's easy to implement this at the VM level.

But how do you do it at the higher more complex level?

https://stackoverflow.com/questions/66485288/how-to-pass-around-the-spaghetti-stack-activation-record-for-a-rich-call-stack March 05, 2021 at 09:06AM