Dear Marc & Gambiteers,

I was hoping to write a short email about a simple way to support
asynchronously aborting threads, as per
https://github.com/gambit/gambit/issues/275
Then I realized that the problem was (Faré's PhD thesis)-complete, and
what I ended up writing was a statement of intent for the non-trivial
hacking of Gambit that I need to achieve to complete my thesis at
https://j.mp/FarePhD
It's all connected, but I'll include copious background, so if you
have time not to skip this message, go grab yourself some
tea/coffee/etc.


I'm enjoying actor programming on Gambit Scheme (actually using Gerbil
Scheme as a layer on top of it). But, especially so after I noticed an
actor going crazy and busy looping with 100% of CPU, I realized that I
*really* wanted to be able to develop robust actor systems in the
style of Erlang — except on top of Gambit.

Erlang allows programmers to build extremely robust systems by being
based on the principle that errors, failures and mistakes WILL happen,
and that the system should as mattter of course easily recover from
them — by killing and restarting the failed subsystems. To elucidate
the paradigm shift in this approach to software, see notably the great
2017 paper by Tomas Petricek "Miscomputation in software Learning to
live with errors" http://tomasp.net/academic/papers/failures/ or his
much shorter 2015 blog post: http://tomasp.net/blog/2015/failures/

One key mechanism to achieving this very robust style of developing
distributed systems based on actors (that Erlang calls "processes") is
Erlang's ability to safely kill a process at any point in time. There
are many reasons why a process may fail: its execution may hit a
software bug; it may hit a hardware bug; it may be hit by cosmic rays
or outer forces; it may fall victim to some "wrench" thrown by
software like Chaos Monkey
https://blog.codinghorror.com/working-with-the-chaos-monkey/ that
deliberately introduces random failures into the system to ensure that
robustness issues are found and addressed earlier rather than later;
it may be targetted by some denial-of-service attack; it may exceed
some resource threshhold; it may otherwise enter a state where it
fails to correct respond to queries, especially so to semi-random
semi-periodic probing queries by its supervisor. Whatever the reason,
inasmuch as the supervisor can detect failure, it can safely kill the
failing process, and restart a new one to replace it. The process will
be unregistered from whatever service broker it was subscribed to, and
the incoming request traffic will be picked up by its healthy
registered peers until the replacement is fully operational.

Because interesting services are made of many actors (or "processes"
in Erlang parlance) that act in concert and have mutually-dependent
state, when a process dies (whether of natural or super-natural
causes), all the processes linked to it (parents and children) are in
turn sent a signal to shutdown graciously. They can explicitly catch
and handle this signal if they really care to survive or to cleanup
something before they die; but by default, the linked process just
dies immediately, freeing all its resources; when it dies, so will a
graceful shutdown signal be sent to its own linked processes,
recursively, in a tree of related processes. In Erlang, this ability
to safely kill entire process trees is essential to build an extremely
robust architecture where large services made of many coordinated
actors automatically restart in a coherent way when errors (or regular
system upgrades) happen.


I have long dreamed to have this Erlang-style robustness in a Lisp —
rather than building a Lisp on top of Erlang, like LFE, that while
robust would miss a lot of the system programming tradition of Lisp
and its performant compilers. And Gambit is oh so close to it, yet I
realize still so far.

Importantly, in Erlang, the actor shutdown signal works
asynchronously, at least by default, for regular actors that don't
explicitly catch and handle these signals. This means that a regular
process may die in the middle of whatever the hell it is doing. This
works well in Erlang, because of its programming model where processes
are made of pure functions and communicate exclusively via message
passing. The model ensures by construction that there is precious
little shared state that may be left in an invalid state when an
asynchronous signal happens, only the message mailbox and a shared
buffer extension sometimes used for performance reasons. And the
system implementation ensures that accesses to this shared state are
atomic with respect to asynchronous signal delivery, so the rest of
the process is all private state and can be released without any
resource leak.

Now, in Scheme (and most other languages, except maybe Haskell), there
can be a LOT more shared state that may be left in disarray if a
thread is interrupted in the middle of random operations. Stateful
data structures are a common thing to use; if anything, making system
calls or using libraries often involves a lot of state; the language
implementation's runtime environment itself has plenty of shared
state, and was never designed to play well with asynchronous
interrupts. Which means that, if an asynchronous interrupt happens (a
signal in Unix parlance), it must be expected that some this shared
data will be in some intermediate state, and that killing the current
thread would leave the program unstable and unable to operate
correctly: a lock may be held that will never be released; the state
protected by that lock may violate necessary invariants to its
operation; some resource borrowed from another thread such as a
handler granted by a server may never be released or otherwise
complete its usage cycle the program may be experience a deadlocked or
livelock; some distributed protocol that was previously initiated
(e.g. voting, partaking in some transaction, etc.) may never complete;
another thread waiting on a spinlock may spin the CPU forever in a
tight loop; if a low-level invariant is broken, the program may crash
in ugly low-level ways, or worst of all, it may return wrong answers
and do the wrong thing to your system — which can conceivably cause
death and/or loss of millions of dollars.

On the other hand, if you fail to interrupt the thread when it is
failing, then it might keep running in a zombie state that eats all
your CPU or holds onto critical resources (shared data structures,
sheer amount of memory, file handles, etc.) that blocks the other
computations from successfully making progress. Or its known failing
state may lead to corruption of critical data. In this case too,
costly or deadly failure may happen.


Therefore, in Scheme, as in most languages, at least at present, the
limited solutions to providing an ersatz of Erlang-style robustness
are as follow:
 1- Do NOT allow for asynchronous killing at all at the Scheme level.
Have only synchronous killing at the Scheme level.
 2- Socially enforce a convention that all actors should regularly go
back to the message loop, and that there should never be a deadlock,
live lock, non-terminating computation or runaway code execution
between two consecutive calls home to the message handling loop.
 3- If some algorithm require indefinitely long computations, their
implementation must maintain a discipline of "cooperative
multitasking", like in the bad old days of the 1980s, whereby these
long-lived computations will be specially modified to periodically
"yield" execution and give the message loop process the opportunity to
process any synchronous shutdown message while the program is in a
stable state.
 4- Consider Scheme as a replacement not for Erlang, but for the
lower-level language in which the Erlang VM is implemented (i.e. C),
that has to deal with all the ugly synchronization details, without
being able to fully abstract over them.
 5- Build further abstractions over this lower-level language, and
stick to them by social convention. A regular Scheme cannot enforce
these social conventions and prevent users from breaking the
abstractions and reaching into the implementation details; however,
Gerbil allows you to build and enforce a full abstraction for module,
thanks to its Racket-like #lang feature, that impose global (rather
than merely local) restrictions on what a module can express.
 6- If you really want a group of actors that live and die together,
put them in a same Operating System level process (and either use OS
process groups to implement trees of related processes, or implement
yourself that notion using some kind of supervisor process). Then you
can kill and restart the entire process (or set of processes). Unlike
Erlang processes or Gambit threads, It's heavy weight; but it works,
and sometimes that's what's exactly needed.
 7- In general, as much as possible, use pure functional style and/or
restrict side-effects to local state that is private (not shared),
thus reducing issues related to shared state for processes that use
this style. However, because the Scheme implementation's runtime and
the available libraries were never designed for asynchronous
interrupts, their own use of shared resources can still cause
catastrophic failures in case of asynchronous aborts.

This strategy of course works, but leads to code that is awkward,
inefficient, not modular, tiresome and error-prone to write,
impractical except at a small scale, and still fragile. It is not
satisfactory to only provide fragile constructs that will explode if
users fail to respect non-trivial coding conventions and maintain them
as the software evolves. This issue really calls for some robust
abstraction mechanism that will automatically enforce any invariant
though coherent automated code generation rather than manual
discipline. Well, at least, Scheme is not worst than any other random
language. The only languages that stand out for their robustness are
those based on the Erlang VM, BEAM, i.e. Erlang itself, Elixier, LFE,
Efene, Joxa, and whatever Erlang flavor of the day.


Now, what I would really like is to enhance Gambit Scheme with basic
mechanisms to really allow safe asynchronous killing of threads. I
told vyzo and he opened issue
https://github.com/gambit/gambit/issues/275 on asynchronous aborts. My
first reflex was to think that if you somehow have a notion of
pseudo-atomic code blocks and you can ensure that asynchronous signals
are deferred until the end of current code block, then everything will
be fine. Cleanup forms in "finally" clauses or dynamic-wind forms may
have to be considered atomic, or at least start with interrupts
disabled. But otherwise, it should be pretty much a straightforward
extension of what the GVM already supports for the sake of e.g.
garbage collection, right? Nope.

It actually takes a whole lot to make proper asynchronous interrupts
work in presence of shared state. After thinking about the issue a bit
more, I realized that it's actually the very same problem that plagued
me for years, and that I have solved in theory my (incomplete) PhD
thesis, but that still requires a practical implementation. And I also
realized that my thesis has a solid argument why there is no shortcut
to the complete solution proposed in my thesis, of a general protocol
for declaring "observability" of computations.

Indeed, for each level of abstraction that you (or your users) care
about, there will be high-level invariants on the shared state that,
if broken, leave the entire program unable to make progress at that
level of abstraction, even though the state may be perfectly fine at
lower-levels of abstractions. Solving the problem at a low-level of
abstraction can never be enough to solve the issue at higher levels of
abstraction, that the lower-levels are only a means to support. Thus,
you can never safely kill any thread in any existing language, with
the exception of Erlang.

Yet, Erlang does it for all programs. And if you look carefully,
you'll see that each and every programming language with preemptive
user-level threads or a garbage collector supports pseudo-atomic
blocks and properly deferred asynchronous signal delivery to suitable
"safe points", so the invariants of its own virtual machine are
enforced before a context switch may proceed without the asynchronous
signal handler interfering with low-level implementation details of
the language's virtual machine. In the case of Gambit, quite
remarkably, asynchronous signal handling by the system is compatible
since 2015 with migrating processes from one GVM to another, e.g. C to
JS to PHP — by making sure the signal to migrate is only processed at
safe points relative to the GVM.


To find a general solution to the issue, you must first step back and
look at the bigger picture: software can be seen as a "semantic
tower", where each layer is the implementation of some more abstract
computation A using some more concrete computation C. For instance,
your program implements a user abstraction U on top of your
programming language abstraction P; the compiler you use implement
this abstraction P in terms of a lower-level virtual machine V. Then a
lower layer expresses V in terms of a low-level view O of the system
as provided by the operating system. The operating system itself
implements O in terms of the documented CPU and chipset semantics C. C
may include microcode that realize the CPU abstraction in terms of a
digital circuit D. D is implemented as transistors in terms of analog
electrical circuits E. E is implemented in terms of quantum mechanics
Q. Q is implemented by God in terms of his own digital physics
computer a la Ed Fredkin. Many more abstraction levels may exist
above, below, or in the middle, that were omitted in this list, yet
may be added when observing the semantic tower from a wider point of
view or with a finer resolution of details.

>From this point of view, the issue of asynchronous signal handling is
then that at each layer of implementation, a low-level asynchronous
interrupt signals may be received at a safe point for the lower level
of abstraction, but that the implementation may want to deliver a
higher-level asynchronous signal, to be handled at a safe point for
the higher level of abstraction. Each level of abstraction thus has
its own notion of safe point, with its own restrictive invariants,
that its implementation must express in terms of the lower
abstraction's level of safe-point, using the language in which it is
written, that is expressed in terms of that lower abstraction's state
and its laxer invariants. The general architecture of this semantic
tower must therefore support "lifting" the notion of safe point, so
that a higher-level safe point may be recovered from a lower-level
safe point. In my thesis I call the corresponding property of
implementations that can lift this notion of safe-point
"observability". The developer in charge of providing an abstraction
level must make sure it can never be caught "with its pants down" (to
reuse the metaphor by ITS hackers, as narrated by Alan Bawden in his
great article on PCLSRing, an early documented instance of the notion
of observability, in an 1960s operating system). And he must for that
use on the lower-level system provided by the programming language he
uses, that he may hopefully rely on itself never being caught with
their pants down, but only observed in stable states.

Therefore, when an asynchronous signal is received for which a handler
is registered at a given level of abstraction A, the system must
somehow synchronize to a safe point for A before to run the handler,
and in general this level may be higher than that of Gambit's virtual
machine. Furthermore, in the case of aborting a thread, this level of
abstraction is the highest at which this thread matters to anyone
(user, or supervisor program that knows how to rebuild higher
abstractions).

In simple cases, recovering a safe point for a level of abstraction A
is simply a case of letting the code run, and checking at each safe
point reached whether an interrupt was received that requires
processing at that level of abstraction (or one below). But for many
reasons may require to support less simple cases: there may be ongoing
transactions that need to be rolled back (aborted) or rolled forward
(eagerly completed, or maybe partially completed but with some clean
stable state register that will cause a follow up transaction); the
abstract state may be a composite of the states of several concurrent
systems, that may each have to be stopped and synchronized to an
observable state; performance may require shortcuts to be taken in the
regular case that have to be compensated for when an interrupt is
caught. In the most general case, whichever programmer is specifying
the abstraction level A is himself using a programming language
providing a more concrete level of abstraction C. When specifying a
handler of asynchronous signals to recover a stable state at level A,
the programmer necessarily needs to express it the language he is
using, in terms of the state at level C. Therefore, for that handler
to run and synchronize to a safe point for A, the platform should
first be able not just to synchronize to a safe point for C, but also
to let the handler observe (recover, extract, reconstruct, inspect)
the state at level C. Now, since there may be an even higher
abstraction level H on top of A, it is not enough to synchronize to a
safe point for A, the platform must also support observing (recoving,
extracting, reconstructing, inspecting) the state at the level A so
the handler of the implementation of H with A can itself specify how
to synchronize to a safe point for H and let yet higher levels of
abstractions observe the state at level H.

Now, a naive understanding of "recovering the state at level A" can be
expensive: you don't want to serialize the entire state of the virtual
machine (potentially gigabytes of memory or more) every time you
process an asynchronous interrupt handler. You want this recovery to
be lazy, so only the bits of state actually required by the handler
need to be partially reified at the required level of abstraction. A
naive implementation of safe points would create a closure to express
this recovery, at every safe point. A slightly less naive
implementation would only create that closure *if* an interrupt was
caught at that safe point. Therefore, the general protocol for a safe
point is therefore to have some kind of special form (safe-point level
state), where level is some kind of object identifying the level of
abstraction of the safe point (if possible known at compile-time,
usually implicit when discussing safe points of a well-identified
layer of the semantic tower), and state is a form only evaluated when
an interrupt is caught at said level, that permits recovery of the
state at specified abstraction level, if possible lazily.

The compiler hopefully knows how to merge safe-points between levels
of abstractions, so that tests for asynchronous interrupts at higher
level safe-point and creation of corresponding higher-level state
objects only happen if an asynchronous interrupt was already caught at
the corresponding lower-level safe-point, yet wasn't handled already
by a lower-level handler. An even better compiler would eliminate
redundant consecutive safe point checking, so e.g. check points are
only checked at the beginning of functions or loops (just like the
implementation already does for its own lower-level checkpoints).

Now, it is not enough to have compiler support. The runtime library
must also be written in a way that supports asynchronous interrupts,
and the programming language must provide suitable abstractions.
Notably, when allocating *any* kind of resource that an asynchronous
interrupt may necessitate to release, the atomic operation with
respect to interrupts should be not merely allocating the resource,
but allocating it AND atomically binding some variable to it; only
then may a "finally" clause properly release the resource without a
leak should an asynchronous abort be received. (The "finally" clause
will also handle synchronous exceptions or regular exit). Potentially
long-running library functions, and especially higher-order functions,
may also have their own issues with respect to declaring safe-points
for higher levels of abstraction within the dynamic extent of their
function call. When an abstraction level reexports such functionality
from lower levels, it may have to subtly wrap this functionality in
variants that suitably handle safe-points. And the compiler may have
to be able to suitably optimize away most wrappers.

There is also the case when a thread receives a further asynchronous
abort in the middle of processing an existing one; or when it gets
stuck while executing cleanup forms in general. My understanding is
that asynchronous aborts are specified with a target level of
abstraction. By default, an abort signal (as a Unix kill -TERM) works
at the highest level of abstraction that the programmer cares about,
and should run all the cleanup forms. If the operator gets impatient,
he may send signals with lower levels of target abstraction (down to a
Unix kill -KILL), at which point levels of abstractions higher than
the target level are invalidated, their cleanup forms are eschewed,
and all linked processes at this level of abstraction are killed (and
hopefully restarted by their supervisor). It is therefore possible to
"lose" a layer of abstraction -- if there was a bug in the
implementation of this layer of abstraction, at which point, well,
that is exactly what "having a bug" means.

All in all, it's a lot of non-trivial work, especially since I need to
modify the Gambit compiler to itself follow the protocol for the
layers between Scheme and the GVM (it already follows it for the
layers below the GVM, yay Marc!). But the result might be worth it,
because, as I argue in my thesis (incomplete, but you can already read
141 pages worth of it), successfully enforcing this protocol unlocks
an entire world of further cool features. I solved it all in theory.
But since this is computing, not mathematics, theory is not enough and
now I need to work on the implementation.

—♯ƒ • François-René ÐVB Rideau •Reflection&Cybernethics• http://fare.tunes.org
Happiness is a journey, not a destination; happiness is to be found along the
way not at the end of the road, for then the journey is over and it's too
late. The time for happiness is today not tomorrow.  — Paul H. Dunn
_______________________________________________
Gambit-list mailing list
Gambit-list@iro.umontreal.ca
https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list