CLRHack: signal and error

Implementation of SIGNAL and ERROR in CLRHack

In CLRHack, the condition signaling system is implemented in the Lisp.HandlerControl class within the LispBase library. It leverages .NET's [ThreadStatic] storage to maintain a per-thread dynamic stack of active condition handlers.

SIGNAL Implementation

The Signal(object condition) method performs the following logic:

1. Retrieval: It fetches the activeHandlers list for the current thread. This list is a chain of [LispBase]Lisp.Handler objects maintained by handler-bind.
2. Iteration: It iterates linearly through the list from the most recently bound handler to the oldest.
3. Type Matching: For each handler, it calls IsType(condition, handler.ConditionType).
   • If the condition is a symbol, it checks for symbol equality (supporting simple symbol-based conditions).
   • If the condition is a .NET object, it checks if the handler's type is assignable from the condition's runtime type (supporting interop with system exceptions).
   • It treats the symbols T or EXCEPTION as catch-all types.
4. Handler Invocation: If a match is found:
   • Recursive Signal Protection: Before calling the handler function, the current handler list is temporarily shadowed. activeHandlers is set to cell.rest (the handlers bound outside the current one). This ensures that if the handler itself calls signal, it won't trigger itself recursively.
   • Execution: The handler's Closure is invoked with the condition object as its argument.
   • Restoration: A finally block ensures the original activeHandlers list is restored if the handler returns normally.

ERROR Implementation

The Error(object condition) method build upon Signal:

1. Signaling Pass: It first invokes Signal(condition). If a handler performs a non-local exit (e.g., via handler-case), the Error method never returns.
2. Debugger Entry: If Signal returns normally (meaning all handlers declined), Error calls EnterDebugger(condition).
3. Interactive Debugging: The debugger:
   • Prints the condition and a list of available restarts (retrieved via RestartControl.GetActiveRestarts()).
   • Provides a prompt for the user to select a restart, launch the system-level debugger (Visual Studio/Rider), or abort.
   • If a restart is selected, it is invoked interactively (potentially gathering arguments from the user).
4. Final Fallback: If the debugger is exited without invoking a restart, Error throws a C# Exception to ensure that execution does not continue on an invalid path.

Notable Implementation Decisions and Edge Cases

• Handler Shadowing: The decision to pop the handler list during invocation is critical for maintaining Common Lisp semantics. It prevents infinite loops and ensures that "outer" handlers can handle errors raised within "inner" handlers.
• Unified Exception Model: CLRHack attempts to unify Lisp conditions and .NET exceptions. IsType allows Lisp handlers to catch C# exceptions by their class name or Type object.
• Thread Isolation: By using [ThreadStatic] for activeHandlers, CLRHack ensures that condition signaling is thread-safe. One thread signaling an error will not interfere with the handler state of another thread.
• Debugger Capability: The SYSTEM-DEBUGGER option in EnterDebugger is a bridge to the underlying .NET environment, allowing developers to use professional IDE tools to inspect the state of the Lisp VM when an unhandled error occurs.

signal and error complete the Common Lisp condition system implementation for CLRHack

CLRHack: restarts

In the CLRHack compiler, restart-bind is a primitive form that manages the dynamic lifecycle of Common Lisp restarts by manipulating a thread-local stack of active restart objects.

Handling of restart-bind

When the compiler encounters a restart-bind form, it generates CIL code that performs the following steps:

1. Capture Previous State: It calls Lisp.RestartControl::GetActiveRestarts() to retrieve the current list of active restarts and stores it in a frame-local variable.
2. Construct New List: For each binding, it evaluates the restart name, handler function, and optional keyword arguments (:report-function, :interactive-function, :test-function). It then instantiates a new [LispBase]Lisp.Restart object and conses it onto the existing list.
3. Install New State: It calls Lisp.RestartControl::SetActiveRestarts(new_list) to update the dynamic environment.
4. Protected Execution: The body of the restart-bind is wrapped in a CIL .try block.
5. Restoration: A finally block is emitted that restores the previously saved restart list using SetActiveRestarts, ensuring that restarts are properly uninstalled even if the body performs a non-local exit.

Lexical Non-Local Exits

The CLRHack compiler supports lexical non-local exits (e.g., return-from or go) through an exception-based mechanism. During the analyze-environment pass, the compiler identifies if a return-from target block is "non-local" (i.e., the return occurs within a nested closure). If so:

• The target block is wrapped in a try/catch for [LispBase]Lisp.BlockExitException.
• The block is assigned a unique string ID.
• The return-from form is compiled into a throw of a BlockExitException, which carries the target ID, the return value, and a captured array of multiple return values (retrieved via Lisp.Values::CaptureValues()).
• The catch handler verifies the target ID. If it matches, it restores any captured multiple values and resumes normal execution; otherwise, it rethrows the exception.

Restart Search

The search for an applicable restart is handled at runtime by Lisp.RestartControl::FindRestart. It performs a linear search through the current thread's activeRestarts list (stored in a [ThreadStatic] field). It can accept either a symbol name or a Restart object itself. If a name is provided, the search respects shadowing, returning the innermost (most recently bound) restart with that name.

Dynamic Tags

Dynamic tags are required for the catch and throw forms used in non-local control flow. In CLRHack, a dynamic tag is simply a fresh object (typically a ListCell or a new System.Object) used as a unique token. This ensures that a throw only matches the specific catch frame it was intended for, avoiding collisions between different invocations of the same function or different restart-case blocks.

restart-case as an Extension of restart-bind

In CLRHack, restart-case is implemented as a macro that expands into a combination of block, catch, and restart-bind. It extends the basic binding functionality by providing a built-in mechanism to jump back to the site of the restart-case when a restart is invoked.

The implementation details are as follows:

• Exit Block: The entire expansion is wrapped in a (block exit_tag ...) to allow normal completion of the expression.
• Dynamic Tag: A unique dynamic tag is created (e.g., (let ((tag (list nil))) ...)).
• Catch Frame: A (catch tag ...) is established around the restart-bind and the expression.
• Binding: The restart-bind creates restarts whose handler functions are closures. When invoked, these closures capture their arguments into local variables, set a unique clause ID, and then throw to the dynamic tag.
• Dispatch: When the throw is caught, the restart-case body executes a cond or case statement. This dispatcher checks the clause ID set by the handler and executes the corresponding forms provided in the restart-case clause, eventually returning the result from the exit_tag block.

Dynamic Variables in Go

Dynamic binding is an evaluation rule for free variables. The rule is that the value of a free variable in a lambda expression is the value bound in the nearest dynamically enlosing scope. This is in contrast to static binding, where the value is the value bound in the nearest lexically enclosing scope. A naive interpreter that saves variable bindings in a stack frame will usually end up implementing dynamic binding.

In general, static binding is preferred because it is easier to reason about. However, dynamic binding is sometimes very useful in handling context. Lisp provides both static and dynamic binding, with the default being static binding.

Golang provides lexical binding, but not dynamic binding. But you can mimic the effect of dynamic binding by saving the variable's value, assigning it a new value, then restoring the old value in a defer statement. But this trick won't work in a multi-threaded environment. Each thread has to manage its own value of the variable that is separate from the values in other threads.

But what if the implementation doesn't tightly bind continuations to threads? What if the implementation uses a thread pool, and the same thread is used for different goroutines at different times? In that case, the trick of saving and restoring the value of a variable won't work. The value of the variable will be shared among different goroutines, and the value will be unpredictable. To make things work, your dynamic variables should be continuation-local.

But golang doesn't provide continuation-local variables, and it seems to go out of its way to keep code from inspecting the current continuation. There is a trick that you can use.

We need a way to allocate synthetic continuation IDs and bind them to the chain of pending calls. We also need a way that a subroutine can inspect the current chain of pending calls and determine the synthetic continuation ID.

Allocating a synthetic continuation ID is easy enough by maintaining a bitmap of free continuation IDs. When we need a continuation ID, we grab a mutex and search the bitmap for an unused continuation ID. We set the bit to allocate the ID and free the mutex. To free the continuation ID, we reset the bit. Any time you want to use dynamic variables, you need to allocate a synthetic continuation ID early on. This will be used as an index into a value table for each dynamic variable.

var (
	continuationIdInUse [MaxContinuations]bool = [MaxContinuations]bool{}
	continuationIdMutex sync.Mutex       = sync.Mutex{}
)

func AllocateContinuationId[T any](receiver func(tid uint8) T) T {
	continuationIdMutex.Lock()

	for tid, inUse := range continuationIdInUse {
		if (tid > 0) && !inUse {
			continuationIdInUse[tid] = true
			continuationIdMutex.Unlock()
			return DeallocatingContinuationId(uint8(tid), receiver)
		}
	}

	panic("No available continuation ids")
}

func DeallocateContinuationId(tid uint8) {
	continuationIdInUse[tid] = false
}

func DeallocatingContinuationId[T any](tid uint8, receiver func(tid uint8) T) T {
	defer DeallocateContinuationId(tid)
	return receiver(tid)
}

Golang doesn’t offer much in the way of stack introspection or manipulation, but you can easily get a backtrace of the names of the pending function calls. So we’ll encode the synthetic continuation ID as a nested set of function calls. When we need to read the current continuation ID, we get a backtrace of the stack and look for the special nested set of function calls and decode them.

func Mark0[T any](count int, value uint8, thunk func() T) T {
	if count == 0 {
		return thunk()
	} else if value%2 == 0 {
		return Mark0(count-1, value/2, thunk)
	} else {
		return Mark1(count-1, (value-1)/2, thunk)
	}
}

func Mark1[T any](count int, value uint8, thunk func() T) T {
	if count == 0 {
		return thunk()
	} else if value%2 == 0 {
		return Mark0(count-1, value/2, thunk)
	} else {
		return Mark1(count-1, (value-1)/2, thunk)
	}
}

func MarkByte[T any](value uint8, thunk func() T) T {
	if value%2 == 0 {
		return Mark0(7, value/2, thunk)
	} else {
		return Mark1(7, (value-1)/2, thunk)
	}
}

When we call MarkByte on a byte, we’ll make a series of eight nested function calls to Mark0 or Mark1 depending on the bits in the byte. We can use the golang backtrace mechanism to find the nested function calls and determine what the byte was:

func ReadMark() int {
	pc := make([]uintptr, 256)
	n := runtime.Callers(0, pc)

	frames := runtime.CallersFrames(pc[:n])
	value := 0
	for {
		frame, more := frames.Next()
		if !more {
			break
		}

		if strings.Contains(frame.Function, "Mark0") {
			value *= 2
		} else if strings.Contains(frame.Function, "Mark1") {
			value = value*2 + 1
		}
	}
	return value
}

Now when we spin off a goroutine that will use dynamic variables, we must be careful to call WithThread some time early on in the goroutine:

func MakeMyGoroutineEntry () func () {
        return func () {
                _ = WithThread(func () int {
                        // There are 8 pending calls to Mark[0,1]
                        // And we can use ReadMark() to get the
                        // represented value
                        
                        // ... body of callback ...
                   })
         }
}

  // ... some code somewhere ...
  myGoroutine := MakeMyGoroutineEntry()
  go myGoroutine()

Now we can use the continuation ID to index into a table of values:

type GlVal[T any] struct {
	values [MaxThreads]T
}

func NewGlVal[T any]() *GlVal[T] {
	return &GlVal[T]{}
}

We read the goroutine local variable by indexing into the table:

func GlValGet[T any](g *GlVal[T]) T {
	return g.values[ReadMark()]
}

We write the golang local variable by writing to the table. We return the old value so that we can restore it later. Note, no mutex is needed because the value is thread-local:

func GlValSet[T any](g *GlVal[T], value T) T {
	mark := ReadMark()
	oldValue := g.values[mark]
	g.values[mark] = value
	return oldValue
}

When we want to dynamically bind the variable, we save the old value to a frame local variable, set the new value, and defer a function to restore the old value:

func GlValBind[T, U any](g *GlVal[T], value T, thunk func() U) U {
	oldValue := GlValSet(g, value)
	defer GlValSet(g, oldValue)
	return thunk()
}

This technique seems reasonably robust despite using the debugging support for its implementation. It will fail if they ever make golang tail-recursive, but I doubt that will happen any time soon.