purpose
This page exists only to motivate designs of stacks for async events described on the aelig page. Material mainly surveys applicable tech descriptions of callstacks to provide context for æ designs. So this is basically a tech appendix.
I mainly quote callstack content from elsewhere, since this is basic stuff, and you're expected to get ideas from hints alone — or you can supplement with your own research. Connecting remarks between quotes only aim to improve flow.
We use a lot of different synonyms for a callstack:
In computer science, a call stack is a dynamic stack data structure which stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, function stack, or run-time stack, and is often shortened to just "the stack".
The event stack described on aelig is just a callstack structured as a heap-based spaghetti stack, because æ events are just async functions.
For activation records (aka call frames) C typically uses stack based memory allocation:
Because the data is added and removed in a last-in-first-out manner, stack allocation is very simple and typically faster than heap allocation. Another advantage is that memory on the stack is automatically reclaimed when the function exits, which can be convenient for the programmer.
Unlike the C style model described above, æ activation records are refcounted and heap-based, and are not automatically reclaimed on return. Event frames remain alive as long as a handle reference still remains to the frame, or to another event spaghetti stack still using that frame.
This is the same solution as the one described for solving the upwards funarg problem:
One solution to the upwards funarg problem is to simply allocate all activation records from the heap instead of the stack, and rely on some form of garbage collection or reference counting to deallocate the activation records when they are no longer needed. Managing activation records on the heap is much less efficient than on the stack, so this strategy may significantly degrade performance. Moreover, because most functions in typical programs do not create upwards funargs, much of this overhead is unnecessary.
As described under the return section in the right column, the upward funarg problem doesn't affect æ event frames because returning does not free event frame references. An event stack only unwinds when an event receiver explicitly chooses to release handles to event frames.
The local refcounting† description using handles in C++ smartrefs is a technique avoiding unnecessary transient refcount updates. This tactic corresponds to a method noted below on Wikipedia's Reference_counting page:
The Deutsch-Bobrow method of reference counting capitalizes on the fact that most reference count updates are in fact generated by references stored in local variables. It ignores these references, only counting references in data structures, but before an object with reference count zero can be deleted, the system must verify with a scan of the stack and registers that no other reference to it still exists.
Readers are assumed already familiar with both assembly language and commonplace representations of call frames in programming languages. In other words, you should already understand typical language runtimes. The idea of content here is to mention technology related to æ designs you already know, to focus your prior familiarity on mechanisms useful to async events. So this is review.
You need not already grasp heap-based spaghetti stacks common to languages like Scheme. If you only know C style monolithic stacks, that's good enough to start.
If I'm lucky, I'll find everything I need on Wikipedia, with a few substantiating quotes from elsewhere.
Because æ event stacks uses them, this section quotes a large percentage of Wikipedia's spaghetti stack:
The term spaghetti stack is closely associated with implementations of programming languages that support continuations. Spaghetti stacks are used to implement the actual run-time stack containing variable bindings and other environmental features. When continuations must be supported, a function's local variables cannot be destroyed when that function returns: a saved continuation may later re-enter into that function, and will expect not only the variables there to be intact, but it will also expect the entire stack to be there, so it can return again!
Each æ event resembles the call frame of a heap-based continuation, where a reply-to queue is a return address when one is present. (Events without reply-to queues are just one-way async messages.)
To resolve this problem, stack frames can be dynamically allocated in a spaghetti stack structure, and simply left behind to be garbage collected when no continuations refer to them any longer. This type of structure also solves both the upward and downward funarg problems, so first-class lexical closures are readily implemented in that substrate also.
Gc for æ events is done with refcounting†, so event frames are reclaimed when refs hit zero.
The most odd behavior of æ events happens on return. Replying to an event is like calling a continuation via explicit CPS, aka continuation passing style:
Instead of "returning" values as in the more familiar direct style, a function written in CPS takes an explicit continuation argument which is meant to receive the result of the computation performed within the function. When a subroutine is invoked within a CPS function, the calling function is required to supply a procedure to be invoked with the subroutine's "return" value.
What's the odd thing æ does on return? Replying makes a stack deeper. A reply event winds a stack deeper the same way an original request event does. This has an effect of sending original requests back to original senders, as next event in the stack under a reply event. This makes it possible to keep request events immutable, since they need not be updated to return a value, when a return value can simply go in the reply event instead.
(Although the model says returns are always new events chaining on the top of old stacks, actual event stack implementations might use another, more complex tactic when coping with out-of-resource situations.)
callstacks « Þ
