CLRHack: unwind-protect and catch-throw

Handling of unwind-protect

The CLRHack compiler maps Lisp unwind-protect semantics directly onto the Structured Exception Handling (SEH) infrastructure of the .NET Common Language Runtime (CLR). Specifically, it utilizes the try...finally construct provided by the Common Intermediate Language (CIL).

Lisp semantics require that the cleanup forms in an unwind-protect block be executed regardless of how control leaves the protected form—whether via normal return, a non-local throw, or a lexical exit like return-from. The CLR guarantees that a finally block will execute during stack unwinding, which is exactly the hook required for Lisp. The implementation details are as follows:

• Protected Form: The compiler generates the code for the protected form inside a CIL try block. Upon successful completion, the primary return value is stored in a local variable, and a leave instruction is used to exit the try block, which automatically triggers the transition to the finally block.
• Side-Channel Preservation: A unique challenge in Lisp is that unwind-protect must return the values of the protected form, but cleanup forms may themselves perform operations that alter the Multiple Return Value (MRV) side-channel. CLRHack exploits method-local variables to save the ReturnCount and the contents of Value1 through Value63 at the very beginning of the finally block and restore them at the very end.
• Unwinding: If a throw or other exception occurs within the try block, the CLR stack walker identifies the finally block and executes it before propagating the exception further. This ensures Lisp's "cleanup guarantee" is maintained even during catastrophic or non-local control transfers.

Handling of catch and throw

Lisp's catch and throw are implemented as a Dynamic Non-Local Exit system built on top of .NET's exception propagation mechanism. While CLR exceptions are typically filtered by type, Lisp requires filtering by a dynamic "tag" object (compared via eq).

The throw Mechanism

When a (throw tag value) is evaluated, CLRHack does not simply perform a jump. Instead, it performs the following steps:

1. Evaluates the tag and the primary value.
2. Captures the current state of the MRV side-channel into an object[].
3. Instantiates a specialized exception class: [LispBase]Lisp.CatchThrowException. This object acts as a carrier for the tag, the primary value, and the captured MRV array.
4. Executes the CIL throw instruction. This initiates the CLR's SEH stack walk.

The catch Mechanism

The (catch tag body) form is compiled into a try...catch block where the catch handler specifically targets CatchThrowException:

1. Tag Setup: The catch tag is evaluated and stored in a method-local variable.
2. Body Execution: The body forms are executed within a try block.
3. The Catch Handler: When a CatchThrowException is intercepted, the handler performs a "Dynamic Filter":
   • It extracts the tag from the exception object and compares it to the local catch tag using System.Object.Equals (simulating Lisp's eq for reference types).
   • Match: If the tags match, the handler "claims" the exception. It extracts the primary value and the MRV array from the exception, restores them to the thread-local side-channel, and resumes normal execution after the catch block.
   • Mismatch: If the tags do not match, the handler executes the CIL rethrow instruction. This allows the exception to continue up the stack to find a matching catch tag in a higher frame.

Exploiting SEH for Lisp Semantics

CLRHack exploits the CLR's SEH in three fundamental ways to bridge the gap between .NET and Lisp:

• Automatic Stack Unwinding: By using throw and try...catch, the compiler delegates the complex task of cleaning up stack frames, registers, and intermediate states to the highly optimized .NET runtime.
• Guaranteed Cleanup: The finally block is the "silicon reality" of Lisp's unwind-protect. The CLR ensures it runs even if an exception is re-thrown multiple times or if a thread is being terminated.
• Payload-Heavy Exceptions: Unlike standard .NET exceptions which often carry only metadata, CatchThrowException is exploited as a transport mechanism. It carries the entire "return state" of a Lisp expression (primary value + MRV side-channel) across an arbitrary number of stack frames, allowing a throw to behave exactly like a multi-valued return to a dynamic point.

CLRHack: Multiple return values

Multiple Return Value Implementation in CLRHack

The CLRHack compiler implements Multiple Return Values (MRV) by extending the single-value limitation of the .NET Common Intermediate Language (CIL) stack through a thread-local side-channel. This allows Lisp forms to communicate multiple values (up to 64) across function boundaries.

1. The Side-Channel Storage

Because a CIL method can only return a single object on the stack, CLRHack utilizes a static class [LispBase]Lisp.Values. This class contains [ThreadStatic] fields that act as a secondary communication channel:

• Primary Value: Always resides on the CIL evaluation stack.
• ReturnCount: An int32 field indicating the total number of values returned (including the primary one).
• Value1 through Value63: Object fields that store the second through sixty-fourth return values.

2. Producing Multiple Values (The Staging Logic)

To prevent corruption during evaluation, the values form uses a Stage-and-Commit strategy. This is necessary because the side-channel is global to the thread; if a sub-expression inside a values form itself returns multiple values, it would overwrite the global fields before the outer values form is finished.

The compilation process for (values form1 form2 ... formN) follows these steps:

1. Evaluation: Each form is evaluated in order.
2. Local Staging: The result of form1 is kept on the stack. The results of form2 through formN are immediately stored into method-local variables (temporaries). This ensures that if form3 calls a function that returns multiple values, the result of form2 is safely tucked away in a local variable and cannot be overwritten.
3. Commitment: After all forms are evaluated, the compiler generates code to move the values from the local temporaries into the global Value1...ValueN fields.
4. Finalization: The ReturnCount is set to N.

3. Preservation across Control Flow

Certain Lisp constructs must evaluate sub-forms without allowing those sub-forms to interfere with the return values of the primary form. This is handled by a Save-Restore pattern.

Multiple-Value-Prog1

The multiple-value-prog1 form evaluates its first form, then saves the entire side-channel state (the primary value, the ReturnCount, and all ValueN fields) into local variables. It then evaluates the subsequent forms. After they finish, it restores the side-channel state from its locals, ensuring the values of the first form are what the caller receives.

Unwind-Protect

In unwind-protect, the protected form is evaluated and its primary result is stored in a local variable. Crucially, the finally block (cleanup) must not destroy the side-channel state produced by the protected form. The compiler generates code at the start of the finally block to save ReturnCount and Value1...63 into locals. Once the cleanup forms complete, the state is restored from these locals before the method returns.

4. Nested Multiple Values (The Re-entrancy Problem)

The fundamental problem with a global side-channel is re-entrancy. If the compiler were to store form2 directly into the global Value1 field, and then form3 involved a function call like (some-func), that function might execute its own (values ...) logic. This would overwrite the global Value1 that was just set for the outer form.

By enforcing the use of method-local temporaries during the production of values, CLRHack ensures that the global side-channel is only updated at the last possible moment ("atomically" relative to the Lisp expression), effectively shielding the return values from being corrupted by nested evaluations.

CLRHack: Tail Recursion

Tail-Call Handling in CLRHack

I decided to make proper tail recursion a fundamental requirement in CLRHack. This prevents stack overflow errors during standard recursive patterns and ensures the runtime remains stable regardless of recursion depth. Technically, Common Lisp isn't required to be tail recursive, but I want mine to be.

1. Tail Position Identification

The compiler performs a structural analysis of the Abstract Syntax Tree (AST) to identify "tail positions." An expression is in a tail position if its value is the final result of the function, meaning no further work remains to be done in the current frame after the call returns. The generate-step2 walker propagates a tail-p flag through the following logic:

• Functions/Lambdas: The final expression in the body is in the tail position.
• Conditionals (IF): Both the "then" and "else" branches are in the tail position.
• Sequences (PROGN/LET): Only the very last form in the sequence is in the tail position.
• Blocks: The last form of a BLOCK is in the tail position, provided the block is not the target of a RETURN-FROM.

2. CIL Instruction Emission

To implement proper tail-call semantics, the compiler utilizes the native tail. prefix in the Common Intermediate Language (CIL). When a function call is detected in a tail position, the compiler applies the following mandatory transformation:

1. The Prefix: It prepends the tail. opcode to the call or callvirt instruction.
2. The Return: It immediately follows the call with a ret (return) instruction.

The tail. prefix instructs the .NET Just-In-Time (JIT) compiler to discard the current method's stack frame before jumping to the target function. This ensures that the call consumes zero additional stack space, turning the recursive call into a semantic jump.

3. Safety and Context Constraints

The implementation of tail-calls is subject to specific safety rules imposed by the Common Language Runtime (CLR) to maintain execution integrity:

• Protected Regions: The CLR prohibits tail. calls inside try, catch, or finally blocks. Because Lisp constructs such as unwind-protect and handler-case rely on these CIL features, tail-call elimination is suspended within these specific scopes to ensure cleanup handlers and error recovery mechanisms function correctly.
• Frame Cleanup: The compiler ensures that all local resources are in a valid state before the tail. prefix is issued, allowing the CLR to safely deallocate the current frame.

Example CIL Output

Consider a recursive counter that must be able to run indefinitely:

  (defun count-down (n)
    (if (= n 0)
        "Done"
        (count-down (- n 1))))
  

The compiled CIL for the recursive branch is transformed to ensure stack neutrality:

      ; ... code to calculate (- n 1) ...
      tail.
      call object Program::'COUNT-DOWN'(object)
      ret
  

By strictly enforcing this pattern, CLRHack guarantees that recursive programs can execute with constant stack space, fulfilling my core requirement of tail recursion.

CLRHack Lexical Variables

Lexical Closures in CLRHack

CLRHack implements lexical closures by transforming dynamic Lisp environments into static CIL class structures. Since the .NET Common Language Runtime (CLR) does not have a native concept of "nesting" functions within the lexical scope of another function's local variables, the compiler employs Lambda Lifting and Explicit Closure Conversion.

1. Lambda Lifting

Every lambda expression (including those generated by flet and labels) is extracted from its nesting site. The compiler generates a unique, standalone CIL class for each lambda. These classes inherit from the base [LispBase]Lisp.Closure class.

2. The Closure Class Structure

The generated class acts as a container for both the code (the lambda body) and the environment (the captured variables). It consists of:

• Environment Fields: For every "free variable" (a variable referenced in the lambda but defined in an outer scope), the compiler adds a public field to the class.
• The Constructor: A constructor is generated that accepts the values (or references) of these free variables and stores them in the class fields.
• The Invoke Methods: The class overrides the virtual Invoke methods of the base Closure class. The body of the Lisp lambda is compiled into these methods.

3. Environment Capture

At the point in the code where the lambda is defined, the compiler emits a newobj instruction. It passes the current values of the required local variables into the closure's constructor. This "closes" over the variables, creating a persistent instance of the environment that lives on the heap.

  ; Lisp Source
  (let ((factor 10))
    (lambda (x) (* x factor)))

  ; Conceptual CIL Transformation
  .class private Lambda_1 extends [LispBase]Lisp.Closure {
      .field public object factor_captured

      .method public hidebysig specialname rtspecialname void .ctor(object f) {
          ldarg.0
          ldarg.1
          stfld object Lambda_1::factor_captured
          ret
      }

      .method public virtual object Invoke(object x) {
          ldarg.0
          ldfld object Lambda_1::factor_captured
          ldarg.1
          ; ... multiplication logic ...
      }
  }
  

4. Shared Mutability via ValueCells

Common Lisp requires that if an outer variable is mutated (via setq), all closures capturing that variable must see the change. To support this, CLRHack uses Indirection Cells:

• If the compiler detects that a captured variable is mutated, it "boxes" that variable.
• Instead of storing a raw value (like an integer) on the stack, it creates a [LispBase]Lisp.ValueCell object.
• The closure captures the reference to this ValueCell.
• Both the parent function and the closure access the variable by reading from or writing to the Value field of the cell. This ensures that all parties share the same mutable state.

5. Invocation

When a closure is invoked (e.g., via funcall), the Invoke method is called. Inside this method, the this pointer (ldarg.0 in CIL) provides the code with access to the captured environment fields. This allows the lifted function to behave as if it were still sitting inside its original lexical scope.

CLRHack argument passing

Common Lisp Argument Passing in CLRHack

The CLRHack engine translates the dynamic, flexible argument-passing semantics of Common Lisp into the static, strongly-typed environment of the .NET Common Language Runtime (CLR). It achieves this through a combination of CIL method overloading, sentinel-based defaulting, and runtime list construction.

1. The Overloading Architecture

Since CIL methods have a fixed arity (number of arguments), but Common Lisp functions support variable arguments, the compiler generates multiple entry points for every defined function.

• Public Overloads: For every function, the compiler generates a set of public static methods (typically from 0 to 8 arguments). These serve as the "API" for both direct calls and closure invocation.
• The Body Method: The actual logic of the Lisp function is compiled into a single private static method named [FunctionName]_Body. All valid public overloads normalize their arguments and delegate to this method.
• Arity Enforcement: Overloads representing invalid argument counts (e.g., calling a 2-arg function with 5 args) are generated to throw a Lisp.WrongNumberOfArgumentsException.

2. Parameter Type Implementation

Required Parameters

Required parameters are the simplest. They map directly to the leading object arguments in both the public overloads and the internal body method.

Optional Parameters (&optional)

Handling &optional involves a "Sentinel Pattern":

• Sentinels: If a caller uses an overload that provides fewer than the maximum number of optional arguments, the compiler passes a special global constant: Lisp.Undefined::Value.
• Late Defaulting: Inside the _Body method, the engine generates CIL code to check if the argument is EQ to the Undefined sentinel. If the check passes, the code evaluates the Lisp default expression and stores the result back into the parameter using starg.
• Supplied-p: If the Lisp code defines a "supplied-p" variable, an extra boolean parameter is added to the _Body method, which is set to true or false based on the presence of the argument in the specific overload.

Rest Parameters (&rest)

Rest parameters are handled by runtime list construction:

• In the public overloads, any arguments provided beyond the required/optional count are bundled into a linked list using Lisp.List/ListCell.
• The _Body method receives this list as a single object argument.

Keyword Parameters (&key)

Keyword parameters are implemented as a transformation over the &rest mechanism:

1. Trailing arguments are gathered into a "rest" list.
2. The _Body method defines local variables for every keyword parameter, initialized to their Lisp default values.
3. The Keyword Loop: At the start of the function, the engine emits a loop that scans the rest list in pairs. It uses Object.Equals to compare each key against the pre-interned keyword symbols (e.g., :TEST). When a match is found, the corresponding local variable is updated with the value following the key.

3. The Calling Mechanism

Direct Calls

When the compiler identifies a call to a known defun in the same assembly, it emits a direct call to the public overload that exactly matches the number of provided arguments. This provides near-native performance for fixed-arity calls.

Indirect Calls (Closures & Funcall)

All Lisp functions are instances of the Lisp.Closure class. This class provides virtual Invoke methods. When a closure is created, it captures its environment and provides overrides for these Invoke methods that jump into the appropriate Program static overloads.

4. Multiple Return Values

Note: Argument passing is only half the story; return values use a side-channel.

Because .NET methods return only one value, CLRHack uses a Thread-Static Side-Channel in the Lisp.Values class:

• The first value is returned normally as the method's return value.
• Additional values are stored in [ThreadStatic] fields (Value1, Value2, ... up to Value63).
• A ReturnCount field is updated to tell the caller how many values are waiting in the buffer.

Example CIL Generation

; Lisp: (defun add-optional (x &optional (y 5)) (+ x y))

; Overload for 1 arg
.method public static object 'ADD-OPTIONAL'(object x) {
    ldarg 0
    ldsfld object [LispBase]Lisp.Undefined::Value
    tail. call object Program::'ADD-OPTIONAL_Body'(object, object)
    ret
}

; The Body Method
.method private static object 'ADD-OPTIONAL_Body'(object x, object y) {
    ; Defaulting logic for Y
    ldarg 1
    ldsfld object [LispBase]Lisp.Undefined::Value
    bne.un SKIP_DEFAULT
    ldc.i4 5
    box int32
    starg 1
SKIP_DEFAULT:
    ; ... rest of function ...
}
    

CLRHack: FibBenchmark

The first thing to look at is the Fibonacci benchmark. The source code is here:

(in-package "CLRHACK")

(progn
  (defun fib (n)
    (if (< n 2)
        n
        (+ (fib (- n 1))
           (fib (- n 2)))))
  (defun main ()
    (print "Fibonacci of 10:")
    (print (fib 10)))
  (main))

And it compiles to this IL code: (commentary after the code)

.assembly extern mscorlib {}
.assembly extern LispBase {}

.assembly 'FibBenchmark' {}
.module 'FibBenchmark.exe'

.class public auto ansi beforefieldinit Program
       extends [mscorlib]System.Object
{
    .field public static class [LispBase]Lisp.Symbol 'SYM_G545'

.method public static hidebysig specialname rtspecialname void '.cctor'() cil managed
{
    .maxstack 8
    ldsfld class [LispBase]Lisp.Package [LispBase]Lisp.Package::CommonLisp
    ldstr "T"
    callvirt instance class [LispBase]Lisp.Symbol [LispBase]Lisp.Package::'Intern'(string)
    stsfld class [LispBase]Lisp.Symbol Program::'SYM_G545'
    ret
}

.method public static hidebysig object 'FIB'(object) cil managed
{
    .maxstack 8
    .locals (object TEMP_B)
    ldarg 0
    ldc.i4 2
    box int32
    stloc TEMP_B
    unbox.any int32
    ldloc TEMP_B
    unbox.any int32
    clt
    brtrue TRUE543
    ldnull
    br END544
TRUE543:
    nop
    ldsfld class [LispBase]Lisp.Symbol Program::'SYM_G545'
END544:
    nop
    ldnull
    ceq
    brtrue ELSE546
    ldarg 0
    ret
ELSE546:
    nop
    ldarg 0
    ldc.i4 1
    box int32
    stloc TEMP_B
    unbox.any int32
    ldloc TEMP_B
    unbox.any int32
    sub
    box int32
    call object Program::'FIB'(object)
    ldarg 0
    ldc.i4 2
    box int32
    stloc TEMP_B
    unbox.any int32
    ldloc TEMP_B
    unbox.any int32
    sub
    box int32
    call object Program::'FIB'(object)
    stloc TEMP_B
    unbox.any int32
    ldloc TEMP_B
    unbox.any int32
    add
    box int32
    ret
BLOCK_END_FIB_532:
    nop
    ret
}

.method public static hidebysig object 'MAIN'() cil managed
{
    .maxstack 8
    ldstr "Fibonacci of 10:"
    call void [mscorlib]System.Console::'WriteLine'(object)
    ldnull
    pop
    ldc.i4 10
    box int32
    call object Program::'FIB'(object)
    call void [mscorlib]System.Console::'WriteLine'(object)
    ldnull
    ret
BLOCK_END_MAIN_536:
    nop
    ret
}

.method public static hidebysig void 'Main'() cil managed
{
    .entrypoint
    .maxstack 8
    call object Program::'MAIN'()
    pop
    ret
}

} // end of class Program

The first thing the fib program does is compare argument x to the literal number 2. The compiler pushes argument 0 on to the stack, and then the compiler pushes a integer 2 on to the stack and boxes it.

Next, the compiler has to perform the compare. In order to do this it must unbox both arguments. One argument is on top of the stack, so it is put into a local TEMP_B so we can get to the other argument. We unbox it. We then restore TEMP_B to the top of stack and unbox it. Finally we compare the two unboxed values for less than.

This pattern of unboxing a pair of elements from the top of stack by way of a temporary local is repeated several places in the compiled code as FIB rather inefficiently subtracts 1 or 2 from the argument and makes the recursive call.

This example shows that the compiler basically treats everything as a .NET object. It unboxes numbers at the last moment and boxes the results as soon as they are generated. It is not efficient code.

I Wrote a Compiler

I was bored so I wrote a compiler. I'm lazy so I vibe coded it. It compiles Lisp to .NET IL (the byte code that the .NET runtime executes). The IL is then JIT compiled to machine code and executed. You can use the dotnet runtime from Microsoft or the open source mono runtime as the runtime for the compiled code.

The basic idea of the compiler is to map lambda expressions to .NET classes. The lexical variables are stored as fields in the class. The body of the lambda is compiled to a method in the class. We use lambda lifting to flatten any nested lambdas. We use cell conversion to handle mutable variables and we simply copy the values of immutable variables into the lifted lambdas when they are closed over.

Although I `vibe coded` the compiler, I leveraged my experience with writing compilers to break down the problem into passes that were simple enough that `vibe coding` was possible. For instance, in order to implement lambda lifting, I first wrote a pass that determined the free variables of each lambda. That's a pretty simple operation that I could easily `vibe code`. In order to emit the correct IL, I first wrote a pass that segregated the variables into arguments, lexicals, and globals. Again, that's a simple operation that I could easily `vibe code`.

The trickiest part was the code generator. I had decided to implement tail recursion by using the `tail.` prefix in the IL. This is a hint to the JIT compiler that the call is a tail call and that it can optimize it by reusing the current stack frame. However, the JIT compiler is a bit picky about when it will actually perform the tail calls, and the other parts of the code generator kept moving the tail calls around so that they were no longer in tail position. I eventually had to add a pre-pass to the code generator that tracked the continuations in order to ensure that there was enough information later on to enforce tail position on the tail calls.

It... works? It compiles a number of the Gabriel Benchmarks, and some test programs that demonstrate lexical scoping, mutable variables, and tail recursion. It is most definitely a Lisp compiler, but if you look under the hood, well, be forewarned. It isn't pretty.

The compiler itself was vibe coded. The only restriction on the output code was that it had to implement what the input code specified. It did not have to conform to any particular notion of how to implement lisp features on the .NET runtime beyond the requirement that the output was correct. Choices that are typically made by a Lisp architect, such as how to deal with integers, the implementation of the standard library, etc., were all left up to the vibe coding process. I provided a couple of runtime libraries: a cell library for implementing mutable variables, and a List library for implementing singly linked lists. These were written in C#. The vibe coding process was allowed to modify the C# code in these libraries as well and it did so in a couple of places.

I started with one a simple benchmark and got it to compile and run. From there, I added more benchmarks and each time told the compiler to fix any errors that came up. I also added some test programs that were not part of the benchmarks in order to test specific features of the compiler. As I added more and more test programs, the `vibe coding process` added more and more features to the compiler. This ended up producing more and more complex compiler output code.

I'm going to devote a few blog posts to this compiler, so if it isn't up your alley, skip ahead a few posts.