How is an async stack implemented?

Question

I am working on creating a simple VM sort of thing in JS:

let sp = 0 // stack pointer
let m = [] // memory

initialize:
  sp = 0
invoke:
  m[sp] = m[sp - 1] // position in stack
  m[sp + 1] = input[m[sp]] // method
  m[sp + 2] = m[m[sp + 1]] // size
  m[sp + 3] = 0 // link iterator
  sp = sp + m[sp + 2] // new stack pointer
load_input:
  if (m[sp + 3] < m[sp + 2]) {
    m[sp] = input[m[sp + 3 + j]]
    // do I need to push the stack for these types of things?
    continue load_input
  } else {
    continue invoke
  }

Not close to working yet, but I'm messing around with it. If you have any tips would love to know, but I'm trying to only use an array not any other programming language constructs.

But my question... If you have events in the application, or things are otherwise asynchronous, then how does the call stack work? You would be 10 layers deep on one "path", waiting for some response. Then the code would continue evaluating somewhere else, and might be 20 layers deep there, also waiting for a response. Then you have a third layer 5 layers deep, etc. So how is this implemented generally? Thinking about the code example above and how to try to make a call stack, I am stuck wondering what I would do when async comes around.

Answer 1

If I understand correctly, you are trying to implement fibers in JavaScript. If I am wrong, then you just need to look how the JavaScript event loop works. Instead of fibers, you can have promises.

---

As you might expect, you need to partition the stack, so you can preserve the multiple "paths". That is, you need to preserve the execution call stack for each fiber.

Thus, each fiber will have its own stack, and will have a state. The state could be waiting on a signal, running, or ready to run. The fiber, upon creation will be in the ready to run state. You make a state machine for that.

And you need a scheduler, which will pick a fiber that is in the ready to run state, change the state to running, and execute.

Eventually, the fiber yields or wants to wait on a signal. In either case, it returns controls to the scheduler, the state is changed to ready to run (in case of yield) or waiting on the signal. And the scheduler goes to pick another fiber to continue.

By the way, I am assuming, since you VM, that you have JavaScript code that reads and executes opcodes. That is, you are not transpiring to JavaScript (at least not ahead of time), instead you are emulating in JavaScript, if that makes sense.

As per the scheduler, the simplest way to implement it is round robin. You might also be interested in Multilevel queue, and, of course, there are other solutions.

Of course, a fiber can create other fibers.

And about that signal... there will be some operation that causes the signal. You can either check when the fiber yields, or you can have the scheduler take control when the signal is set, update the states, and return. I suggest to do both: When a fiber sets a signal, it yields, the scheduler takes control, and updates the state of any fibers waiting on that signal, then goes to pick a fiber to continue.

You can have direct support for composite signals (all of a set, and any of a set).

As you can see, you will have a set a fibers, each one has a stack. When the scheduler wants to continue the execution, the scheduler need to set the stack of the fiber as current. The scheduler also needs to know where execution should resume, and execute that. Which means that when a fiber yields or wants to wait on a signal, that position has to be stored.

The position where execution should resume, might or might not be in the stack. However, be aware that it is not a call. That is, there will not be a return that pops it. Instead, you need to push it when returning control to the scheduler, and pop it when the scheduler continues the execution of the fiber.

By the way, you can make it so when a fiber does a call, it also yields.

---

Let us say you want to store all the stacks (for all the fibers) in the same structure. Sure, you can do that. However, each fiber will have a pointer, and the stack will not be continous. You will simply be allocating nodes in the array. You will probably want to keep track of which are freed so you can reuse them... I suppose that is more like a special heap, maybe?

---

In JavaScript, you only have one thread to work with, thus you do not really have threading problems with any of what I describe above. In an environment with multiple thread, you can have a scheduler (and its fibers) per thread that is devoted to fibers.

---

The following is not what the question is about. But what I first understood from the title, instead. So, for the people who may come here looking for how to implement a thread-safe stack (for multiple threads using the same stack, but not a call stack), I suggest to do the following implementations first: a fixed size thread-safe stack based on an array, with all operations atomic. And thread-safe stack based on a singly linked list (which has a race condition which you can solve by spinning). Then, do one based on a singly linked list of arrays, so you minimize the frequency of the race condition by making the array longer, which also reduce the number of allocations... which you reduce further by pooling the arrays.