Implementing Common Lisp Condition System in C #

One of the most remarkable and attractive features of Common Lisp is, of course, its exception handling system.

Moreover, in my opinion, personally, this approach to exceptions is the only correct one for all imperative languages, and for this simple reason:
The mechanism of "exceptions" (or, as they are called in the world of CL - conditions) in Common Lisp is separate stack promotion mechanism, and this, accordingly, allows you to process any exceptional (and not only exceptional) situations that pop up in the program right in the place where they occurred, without losing the context of the program execution, which entails the convenience of development, debugging, and in general, the convenience of constructing program logic.

Probably, it should be said that the Common Lisp Condition System, despite its uniqueness in the environment of high-level programming languages, is very close to the low-level tools of modern operating systems known to many developers, namely: synchronous UNIX signals and, much closer, to the SEH (Structured Exception Handling) mechanism from windows. Leading CL implementations base computing flow controls such as exception handling and stack promotion on them.

Despite the absence of a similar mechanism in many other (if not all) imperative programming languages, it lends itself to implementation in a more or less sane form on most of them. In this article, I will describe the implementation in C #, along the way, analyzing in detail the very concept of this approach to “exceptions”.

For the full implementation of CLCS from a programming language, or rather even from its runtime, the following few things are required:
  • Strict stack execution model. Here I mean the lack of full-fledged language "sequels» ( continuations ). This point is rather conditional, but since continuations introduce enormous fuzziness into the mechanism for controlling the flow of computations, and they do not allow us to determine with sufficient accuracy the basic primitives from which CLCS is repelled, their presence is extremely undesirable.
  • Higher-order functions, anonymous functions, and closures. Of course, if you try, you can implement everything through objects and classes, but in this case, using all this, in my opinion, will be extremely inconvenient.
  • Dynamic environments and, in particular, dynamic variables. About dynamic environments and variables, I wrote in more or less detail in my article about the semantics of modern Lisp: love5an.livejournal.com/371169.html
    In the absence of a similar concept in a programming language, it, however, is emulated using the following two points:
  • The try, catch, and throw statements, or their equivalents. These operators are in any programming language that supports exceptions.
  • UNWIND-PROTECT primitive or its analogue (try-finally block, RAII, etc.).


We will port the following CL exception system primitives to C #:
  1. handler-bind - sets an exception handler for the execution time of the statement body. When catching an exception, the handler may decide to promote the stack, but is not required to do so.
  2. handler-case - sets an exception handler for the execution time of the operator body. When catching an exception, the stack is unwound and the operator returns the value calculated in the body of the handler.
  3. signal - signals an exception to the upstream handler, if one is present.
  4. error - signals an exception to an upstream handler, and in the absence of it, or in the case of failure of all handlers to cope with the exception - throws an exception in the usual way, i.e. with the throw operator (This is in our implementation. In Common Lisp, the error function calls the debugger if it is connected, or, otherwise, terminates the operation of a separate thread of calculations (thread) or the entire lisp system.)
  5. restart-bind - sets a "restart", not causing the stack promotion mechanism. Restarting is a function in the current dynamic environment (see the link to the article above) that can somehow respond to an exception. Restarts are usually placed in those places of the program where you can somehow fix the error that occurred. They are usually started from exception handlers (see below).
  6. restart-case - sets the "restart", ending with the promotion of the stack.
  7. find-restart - Finds a "restart" by name.
  8. invoke-restart - finds “restart” by name and starts it.
  9. compute-restarts - computes a list of all “restarts” installed in the current dynamic environment.
  10. unwind-protect - executes a block of the operator’s body, and then - regardless of whether the execution completed in a normal way, or through forced promotion of the stack, it performs all the specified “protecting” blocks (functions).


You can read more about these and other primitives related to exception handling in Peter Sibel’s wonderful book Practical Common Lisp, chapter 19:
lisper.ru/pcl/beyond-exception-handling-conditions-and-restarts
The whole implementation is we will be contained in the static class Conditions . Next, I will describe his methods.
But first, a couple of static variables should be described.

In each program execution thread, exception handlers and restarts during installation form a stack. Generally speaking, formally speaking, the dynamic environment of each thread forms the stack, but since there are no dynamic environments in C #, strictly speaking, we will “manually” associate the data structure “stack” with each thread.

static ConditionalWeakTable<Thread, Stack<Tuple<Type, HandlerBindCallback>>> _handlerStacks;
static ConditionalWeakTable<Thread, Stack<Tuple<string, RestartBindCallback>>> _restartStacks;

static Conditions()
{
  _handlerStacks = new ConditionalWeakTable<Thread, Stack<Tuple<Type, HandlerBindCallback>>>();
  _restartStacks = new ConditionalWeakTable<Thread, Stack<Tuple<string, RestartBindCallback>>>();
}


For the “thread -> stack” dictionary, I chose the ConditionalWeakTable class added in .NET 4.0, but you can use any other similar data structure. ConditionalWeakTable is good because it is a hash-plate with “weak pointers” (WeakPointer - hence Weak in the class name) to the keys, and this, accordingly, means that when the Thread object is deleted by the garbage collector, we will not leak memory.

Exception Handlers and Signaling


Handlerbind

public static T HandlerBind<T>(Type exceptionType, HandlerBindCallback handler, HandlerBody<T> body)
{
  if (null == exceptionType)
    throw new ArgumentNullException("exceptionType");
  if (!exceptionType.IsSubclassOf(typeof(Exception)))
    throw new InvalidOperationException("exceptionType is not a subtype of System.Exception");
  if (null == handler)
    throw new ArgumentNullException("handler");
  if (null == body)
    throw new ArgumentNullException("body");
  Thread currentThread = Thread.CurrentThread;
  var clusters = _handlerStacks.GetOrCreateValue(currentThread);
  clusters.Push(Tuple.Create(exceptionType, handler));
  try
  {
    return body();
  }
  finally
  {
    clusters.Pop();
  }
}

The HandlerBind method takes three parameters: the type of exception that the handler is associated with (as can be seen from the body of the method, it must be a subclass of Exception), a callback that defines the code of the handler, and another delegate that defines the code that is executed in the body of the statement.
The delegate types handler and body are:
public delegate void HandlerBindCallback(Exception exception);
public delegate T HandlerBody<T>();

The exception parameter passed to the handler as arguments is the exception object itself.

As you can see, the implementation of HandlerBind is simple - we add a new one to the stack of handlers associated with the current thread, after that we execute the code of the operator body, and as a result, in the finally body, remove the handler from the stack. Thus, the stack of exception handlers is associated with the execution stack of the current thread, and each installed handler becomes invalid when the program execution thread leaves the corresponding stack frame.

Handlercase

public static T HandlerCase<T>(Type exceptionType, HandlerCaseCallback<T> handler, HandlerBody<T> body)
{
  if (null == exceptionType)
    throw new ArgumentNullException("exceptionType");
  if (!exceptionType.IsSubclassOf(typeof(Exception)))
    throw new InvalidOperationException("exceptionType is not a subtype of System.Exception");
  if (null == handler)
    throw new ArgumentNullException("handler");
  if (null == body)
    throw new ArgumentNullException("body");
  var unwindTag = new UnwindTag<T>();
  HandlerBindCallback handlerCallback = (e) =>
  {
    unwindTag.Value = handler(e);
    throw unwindTag;
  };
  try
  {
    return HandlerBind(exceptionType, handlerCallback, body);
  }
  catch (UnwindTag<T> e)
  {
    if (e == unwindTag)
    {
      return e.Value;
    }
    else
      throw;
  }
}


Implementing HandlerCase is a bit more complicated. The difference from HandlerBind, I recall, is that this operator spins the stack to the point at which the handler is installed. Since explicit escaping continuations are forbidden in C # (that is, roughly speaking, we cannot make goto or return from a lambda passed down the stack to an external block), we use regular try-catch to unwind the stack, and identify the processor block an object of the auxiliary class UnwindTag
class UnwindTag<T> : Exception
{
  public T Value { get; set; }
}


HandlerCaseCallback differs from HandlerBindCallback only in that it returns a value:
public delegate T HandlerCaseCallback<T>(Exception exception);


Signal

Signal is at the heart of the CL exception handling system. Unlike throw and comrades, from other programming languages, it does not spin up the call stack, but only signals an exception that has occurred, that is, it simply calls a suitable handler.

public static void Signal<T>(T exception)
  where T : Exception
{
  if (null == exception)
    throw new ArgumentNullException("exception");
  Thread currentThread = Thread.CurrentThread;
  var clusters = _handlerStacks.GetOrCreateValue(currentThread);
  var i = clusters.GetEnumerator();
  while (i.MoveNext())
  {
    var type = i.Current.Item1;
    var handler = i.Current.Item2;
    if (type.IsInstanceOfType(exception))
    {
      handler(exception);
      break;
    }
  }
}


Apparently - everything is very simple. From the current stack of exception handlers, we take the first one that can work with the exception class, an instance of which is the object passed to us in the exception parameter.

Error

public static void Error<T>(T exception)
  where T : Exception
{
  Signal(exception);
  throw exception;
}


Error differs from Signal only in that it interrupts the normal flow of program execution in the absence of a suitable handler. Если бы мы писали полноценную реализацию Common Lisp под .NET , вместо «throw exception» было бы что-то вроде «InvokeDebuggerOrDie(exception);»

Restarts


RestartBind and RestartCase

RestartBind and RestartCase are very similar to HandlerBind and HandlerCase, with the difference that they work with the restart stack and map the delegate-handler not the exception type, but the string, the name of the restart.
public delegate object RestartBindCallback(object param);

public delegate T RestartCaseCallback<T>(object param);

public static T RestartBind<T>(string name, RestartBindCallback restart, HandlerBody<T> body)
{
  if (null == name)
    throw new ArgumentNullException("name");
  if (null == restart)
    throw new ArgumentNullException("restart");
  if (null == body)
    throw new ArgumentNullException("body");
  Thread currentThread = Thread.CurrentThread;
  var clusters = _restartStacks.GetOrCreateValue(currentThread);
  clusters.Push(Tuple.Create(name, restart));
  try
  {
    return body();
  }
  finally
  {
    clusters.Pop();
  }
}

public static T RestartCase<T>(string name, RestartCaseCallback<T> restart, HandlerBody<T> body)
{
  if (null == name)
    throw new ArgumentNullException("name");
  if (null == restart)
    throw new ArgumentNullException("restart");
  if (null == body)
    throw new ArgumentNullException("body");
  var unwindTag = new UnwindTag<T>();
  RestartBindCallback restartCallback = (param) =>
  {
    unwindTag.Value = restart(param);
    throw unwindTag;
  };
  try
  {
    return RestartBind(name, restartCallback, body);
  }
  catch (UnwindTag<T> e)
  {
    if (e == unwindTag)
    {
      return e.Value;
    }
    else
      throw;
  }
}


FindRestart and InvokeRestart

FindRestart and InvokeRestart, in turn, are very similar to the Signal method - the first function finds a restart in the corresponding stack of the current thread by name, and the second not only finds it, but immediately starts it.
public static RestartBindCallback FindRestart(string name, bool throwOnError)
{
  if (null == name)
    throw new ArgumentNullException("name");
  Thread currentThread = Thread.CurrentThread;
  var clusters = _restartStacks.GetOrCreateValue(currentThread);
  var i = clusters.GetEnumerator();
  while (i.MoveNext())
  {
    var restartName = i.Current.Item1;
    var restart = i.Current.Item2;
    if (name == restartName)
      return restart;    
  }
  if (throwOnError)
    throw new RestartNotFoundException(name);
  else
    return null;
}

public static object InvokeRestart(string name, object param)
{
  var restart = FindRestart(name, true);
  return restart(param);
}


ComputeRestarts

ComputeRestarts simply returns a list of all restarts currently installed - this can be useful, for example, to an exception handler so that, when called, it can select a suitable restart for a particular situation.
public static IEnumerable<Tuple<string, RestartBindCallback>> ComputeRestarts()
{
  var restarts = new Dictionary<string, RestartBindCallback>();
  Thread currentThread = Thread.CurrentThread;
  var clusters = _restartStacks.GetOrCreateValue(currentThread);
  return clusters.AsEnumerable();
}


Unwindprotect


Our implementation of UnwindProtect simply wraps a try-finally block.
public static T UnwindProtect<T>(HandlerBody<T> body, params Action[] actions)
{
  if (null == body)
    throw new ArgumentNullException("body");
  if (null == actions)
    actions = new Action[0];
  try
  {
    return body();
  }
  finally
  {
    foreach (var a in actions)
      a();
  }
}


Finally, a few usage examples.

  1. Using HandlerBind with a function that signals an exception.
    static int DivSignal(int x, int y)
    {
      if (0 == y)
      {
        Conditions.Signal(new DivideByZeroException());
        return 0;
      }
      else
        return x / y;
    }
    

    int r = Conditions.HandlerBind(
              typeof(DivideByZeroException),
              (e) =>
              {
                Console.WriteLine("Entering handler callback");
              },
              () =>
              {
                Console.WriteLine("Entering HandlerBind with DivSignal");
                var rv = DivSignal(123, 0);
                Console.WriteLine("Returning {0} from body", rv);
                return rv;
              });
    Console.WriteLine("Return value: {0}\n", r);
    

    Here, the DivSignal function, with a divisor equal to zero, signals a situation that has arisen, but nevertheless, it “cope” with it (returns zero). In this case, neither the handler nor the function itself interrupts the normal course of the program.
    The output to the console is as follows:
    Entering HandlerBind with DivSignal
    Entering handler callback
    Returning 0 from body
    Return value: 0
    

  2. Using HandlerCase and UnwindProtect with a function reporting an error through Error.
    static int DivError(int x, int y)
    {
      if (0 == y)
        Conditions.Error(new DivideByZeroException());
      return x / y;
    }
    

    int r = Conditions.HandlerCase(
              typeof(DivideByZeroException),
              (e) =>
              {
                Console.WriteLine("Entering handler callback");
                Console.WriteLine("Returning 0 from handler");
                return 0;
              },
              () =>
              {
                Console.WriteLine("Entering HandlerCase with DivError and UnwindProtect");
                return Conditions.UnwindProtect(
                         () =>
                         {
                           Console.WriteLine("Entering UnwindProtect");
                           var rv = DivError(123, 0);
                           Console.WriteLine("This line should not be printed");
                           return rv;
                         },
                         () =>
                         {
                           Console.WriteLine("UnwindProtect exit point");
                         });
              });
    Console.WriteLine("Return value: {0}\n", r);
    

    In this case, the DivError function throws an exception, but the handler catches it, spins the stack, and returns its value (in this case, 0). As the stack progresses, the computation flow passes through UnwindProtect.
    This example, unlike the others, could be rewritten using the usual try, catch and finally.
    Console output:
    Entering HandlerCase with DivError and UnwindProtect
    Entering UnwindProtect
    Entering handler callback
    Returning 0 from handler
    UnwindProtect exit point
    Return value: 0
    

  3. Using HandlerBind with a function in which a restart is installed.
    static int DivRestart(int x, int y)
    {
      return Conditions.RestartCase(
              "ReturnValue",
              (param) =>
              {
                Console.WriteLine("Entering restart ReturnValue");
                Console.WriteLine("Returning {0} from restart", param);
                return (int)param;
              },
              () =>
              {
                Console.WriteLine("Entering RestartCase");
                return DivError(x, y);
              });
    }
    

    DivRestart sets up a restart called “ReturnValue”, which, when activated, simply returns the value passed to it via the (param) parameter. The body of RestartCase raises the DivError described in the previous example.
    int r = Conditions.HandlerBind(
              typeof(DivideByZeroException),
              (e) =>
              {
                Console.WriteLine("Entering handler callback");
                Console.WriteLine("Invoking restart ReturnValue with param = 0");
                Conditions.InvokeRestart("ReturnValue", 0);
              },
              () =>
              {
                Console.WriteLine("Entering HandlerBind with DivRestart");
                return DivRestart(123, 0);
              });
    Console.WriteLine("Return value: {0}", r);
    

    The handler installed in the HandlerBind, when called, searches for a restart “ReturnValue” and passes the number 0 to the parameter, after that the “ReturnValue” is activated, spins the stack to its level, and returns the same number from the RestartCase set in DivRestart, as seen above.
    Output:
    Entering HandlerBind with DivRestart
    Entering RestartCase
    Entering handler callback
    Invoking restart ReturnValue with param = 0
    Entering restart ReturnValue
    Returning 0 from restart
    Return value: 0
    



The full source code of the library and examples is available on github: github.com/Lovesan/ConditionSystem