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.

Echoes of the Lisp Listener

The Lisp Machine Listener had an electric close parenthesis. When the user typed a close parenthesis, and this was the close parenthesis that finished the complete form at top level, the form would be sent to the REPL right away with no need to press enter. Here's how to get this behavior with SLY:

(defun my-sly-mrepl-electric-close-paren ()
  "Insert ')' and auto-send ONLY if we are closing a top-level Lisp form."
  (interactive)
  (let ((state (syntax-ppss)))
    (insert ")")
    ;; Safety checks:
    ;; 1. We were at depth 1 (so we are now at depth 0)
    ;; 2. We aren't in a string or comment
    ;; 3. The input actually starts with a paren (it's a form, not a sentence)
    (when (and (= (car state) 1)
               (not (nth 3 state))
               (not (nth 4 state))
               (string-match-p "^\\s-*(" 
                               (buffer-substring-no-properties (sly-mrepl--mark) (point))))
      (sly-mrepl-return))))

Another cool hack is to get the REPL to do double duty as a command line to the LLM chatbot. When you type RET in the REPL, it will check if the input is a complete lisp form. If so, it will send the form to the REPL as normal. If not, it will send the input to the chatbot. Here's how to do this:

(defun my-sly-mrepl-electric-return ()
  "Send to Lisp if it's a form/symbol, or wrap in (chat ...) if it's a sentence."
  (interactive)
  (let* ((beg (marker-position (sly-mrepl--mark)))
         (end (point-max))
         (input (buffer-substring-no-properties beg end))
         (trimmed (string-trim input)))
    (cond
     ;; If it's empty, just do a normal return
     ((string-blank-p trimmed)
      (sly-mrepl-return))
     
     ;; If it starts with a paren, quote, or hash, it's definitely a Lisp form
     ((string-match-p "^\\s-*[(#'\"]" trimmed)
      (sly-mrepl-return))
     
     ;; If it's a single word (no spaces), treat it as a symbol/form (e.g., *package*)
     ((not (string-match-p "\\s-" trimmed))
      (sly-mrepl-return))
     
     ;; Otherwise, it's a sentence. Wrap it and fire.
     (t
      (delete-region beg end)
      (insert (format "(chat %S)" trimmed))
      (sly-mrepl-return)))))

Install as follows:

;; Apply to SLY MREPL with a safety check for the mode map
(with-eval-after-load 'sly-mrepl
  (define-key sly-mrepl-mode-map (kbd "RET") 'my-sly-mrepl-electric-return)
  (define-key sly-mrepl-mode-map (kbd ")") 'my-sly-mrepl-electric-close-paren))

binary-compose-left and binary-compose-right

If you have a unary function F, you can compose it with function G, H = F ∘ G, which means H(x) = F(G(x)). Instead of running x through F directly, you run it through G first and then run the output of G through F.

If F is a binary function, then you either compose it with a unary function G on the left input: H = F ∘_left G, which means H(x, y) = F(G(x), y) or you compose it with a unary function G on the right input: H = F ∘_right G, which means H(x, y) = F(x, G(y)).

(binary-compose-left f g)  = (λ (x y) (f (g x) y))
(binary-compose-right f g) = (λ (x y) (f x (g y)))

We could extend this to trinary functions and beyond, but it is less common to want to compose functions with more than two inputs.

binary-compose-right comes in handy when combined with fold-left. This identity holds

 (fold-left (binary-compose-right f g) acc lst) <=>
   (fold-left f acc (map g lst))

but the right-hand side is less efficient because it requires an extra pass through the list to map g over it before folding. The left-hand side is more efficient because it composes g with f on the fly as it folds, so it only requires one pass through the list.

Vibe Coded Scheme Interpreter

Mark Friedman just released his Scheme-JS interpreter which is a Scheme with transparent JavaScript interoperability. See his blog post at furious ideas.

This interpreter apparently uses the techniques of lightweight stack inspection — Mark consulted me a bit about that hack works. I'm looking forward to seeing the vibe coded architecture.

Some Libraries

Zach Beane has released the latest Quicklisp beta (January 2026), and I am pleased to have contributed to this release. Here are the highlights:

• dual-numbers — Implements dual numbers and automatic differentiation using dual numbers for Common Lisp.
• fold — FOLD-LEFT and FOLD-RIGHT functions.
• function — Provides higher-order functions for composition, currying, partial application, and other functional operations.
• generic-arithmetic — Defines replacement generic arithmetic functions with CLOS generic functions making it easier to extend the Common Lisp numeric tower to user defined numeric types.
• named-let — Overloads the LET macro to provide named let functionality similar to that found in Scheme.

Selected Functions

Dual numbers

DERIVATIVE function → function

Returns a new unary function that computes the exact derivative of the given function at any point x.

The returned function utilizes Dual Number arithmetic to perform automatic differentiation. It evaluates f(x + ε), where ε is the dual unit (an infinitesimal such that ε² = 0). The result is extracted from the infinitesimal part of the computation.

f(x + ε) = f(x) + f'(x)ε

This method avoids the precision errors of numerical approximation (finite difference) and the complexity of symbolic differentiation. It works for any function composed of standard arithmetic operations and elementary functions supported by the dual-numbers library (e.g., sin, exp, log).

Example

(defun square (x) (* x x))

(let ((df (derivative #'square)))
  (funcall df 5)) 
;; => 10
    

Implementation Note

The implementation relies on the generic-arithmetic system to ensure that mathematical operations within function can accept and return dual-number instances seamlessly.

Function

BINARY-COMPOSE-LEFT binary-fn unary-fn → function

BINARY-COMPOSE-RIGHT binary-fn unary-fn → function

Composes a binary function B(x, y) with a unary function U(z) applied to one of its arguments.

(binary-compose-left B U)(x, y) ≡ B(U(x), y)

(binary-compose-right B U)(x, y) ≡ B(x, U(y))

These combinators are essential for "lifting" unary operations into binary contexts, such as when folding a sequence where elements need preprocessing before aggregation.

Example

;; Summing the squares of a list
(fold-left (binary-compose-right #'+ #'square) 0 '(1 2 3))
;; => 14  ; (+ (+ (+ 0 (sq 1)) (sq 2)) (sq 3))
    

FOLD

FOLD-LEFT function initial-value sequence → result

Iterates over sequence, calling function with the current accumulator and the next element. The accumulator is initialized to initial-value.

This is a left-associative reduction. The function is applied as:

(f ... (f (f initial-value x₀) x₁) ... x_n)

Unlike CL:REDUCE, the argument order for function is strictly defined: the first argument is always the accumulator, and the second argument is always the element from the sequence. This explicit ordering eliminates ambiguity and aligns with the functional programming convention found in Scheme and ML.

Arguments

• function: A binary function taking (accumulator, element).
• initial-value: The starting value of the accumulator.
• sequence: A list or vector to traverse.

Example

(fold-left (lambda (acc x) (cons x acc))
           nil
           '(1 2 3))
;; => (3 2 1)  ; Effectively reverses the list
    

Named Let

LET bindings &body body → result

LET name bindings &body body → result

Provides the functionality of the "Named Let" construct, commonly found in Scheme. This allows for the definition of recursive loops within a local scope without the verbosity of LABELS.

The macro binds the variables defined in bindings as in a standard let, but also binds name to a local function that can be called recursively with new values for those variables.

(let name ((var val) ...) ... (name new-val ...) ...)

This effectively turns recursion into a concise, iterative structure. It is the idiomatic functional alternative to imperative loop constructs.

While commonly used for tail recursive loops, the function bound by named let is a first-class procedure that can be called anywhere or used as a value.

Example

;; Standard Countdown Loop
(let recur ((n 10))
  (if (zerop n)
      'blastoff
      (progn
        (print n)
        (recur (1- n)))))
    

Implementation Note

The named-let library overloads the standard CL:LET macro to support this syntax directly if the first argument is a symbol. This allows users to use let uniformly for both simple bindings and recursive loops.

Advent of Code 2025, brief recap

I did the Advent of Code this year using Common Lisp. Last year I attempted to use the series library as the primary iteration mechanism to see how it went. This year, I just wrote straightforward Common Lisp. It would be super boring to walk through the solutions in detail, so I've decided to just give some highlights here.

Day 2: Repeating Strings

Day 2 is easily dealt with using the Common Lisp sequence manipulation functions giving special consideration to the index arguments. Part 1 is a simple comparison of two halves of a string. We compare the string to itself, but with different start and end points:

(defun double-string? (s)
  (let ((l (length s)))
    (multiple-value-bind (mid rem) (floor l 2)
      (and (zerop rem)
           (string= s s
                    :start1 0 :end1 mid
                    :start2 mid :end2 l)))))

Part 2 asks us to find strings which are made up of some substring repeated multiple times.

(defun repeating-string? (s)
  (search s (concatenate 'string s s)
          :start2 1
          :end2 (- (* (length s) 2) 1)
          :test #'string=))

Day 3: Choosing digits

Day 3 has us maximizing a number by choosing a set of digits where we cannot change the relative position of the digits. A greed algorithm works well here. Assume we have already chosen some digits and are now looking to choose the next digit. We accumulate the digit on the right. Now if we have too many digits, we discard one. We choose to discard whatever digit gives us the maximum resulting value.

(defun omit-one-digit (n)
  (map 'list #'digit-list->number (removals (number->digit-list n))))
                    
> (omit-one-digit 314159)
(14159 34159 31159 31459 31419 31415)

(defun best-n (i digit-count)
  (fold-left (lambda (answer digit)
               (let ((next (+ (* answer 10) digit)))
                 (if (> next (expt 10 digit-count))
                     (fold-left #'max most-negative-fixnum (omit-one-digit next))
                     next)))
             0
             (number->digit-list i)))

(defun part-1 ()
  (collect-sum
   (map-fn 'integer (lambda (i) (best-n i 2))
           (scan-file (input-pathname) #'read))))

(defun part-2 ()
  (collect-sum
   (map-fn 'integer (lambda (i) (best-n i 12))
           (scan-file (input-pathname) #'read))))

Day 6: Columns of digits

Day 6 has us manipulating columns of digits. If you have a list of columns, you can transpose it to a list of rows using this one liner:

(defun transpose (matrix)
  (apply #'map 'list #'list matrix))

Days 8 and 10: Memoizing

Day 8 has us counting paths through a beam splitter apparatus while Day 10 has us counting paths through a directed graph. Both problems are easily solved using a depth-first recursion, but the number of solutions grows exponentially and soon takes too long for the machine to return an answer. If you memoize the function, however, it completes in no time at all.

Filter

One of the core ideas in functional programming is to filter a set of items by some criterion. It may be somewhat suprising to learn that lisp does not have a built-in function named “filter” “select”, or “keep” that performs this operation. Instead, Common Lisp provides the “remove”, “remove-if”, and “remove-if-not” functions, which perform the complementary operation of removing items that satisfy or do not satisfy a given predicate.

The remove function, like similar sequence functions, takes an optional keyword :test-not argument that can be used to specify a test that must fail for an item to be considered for removal. Thus if you invert your logic for inclusion, you can use the remove function as a “filter” by specifying the predicate with :test-not.

> (defvar *nums* (map 'list (λ (n) (format nil "~r" n)) (iota 10)))
*NUMS*

;; Keep *nums* with four letters
> (remove 4 *nums* :key #'length :test-not #'=)
("zero" "four" "five" "nine")

;; Keep *nums* starting with the letter "t"
> (remove #\t *nums* :key (partial-apply-right #'elt 0) :test-not #'eql)
("two" "three")

The AI Gazes at its Navel

When you play with these AIs for a while you'll probably get into a conversation with one about consciousness and existence, and how it relates to the AI persona. It is curious to watch the AI do a little navel gazing. I have some transcripts from such convesations. I won't bore you with them because you can easily generate them yourself.

The other day, I watched an guy on You Tube argue with his AI companion about the nature of consciousness. I was struck by how similar the YouTuber's AI felt to the ones I have been playing with. It seemed odd to me that this guy was using an AI chat client and LLM completely different from the one I was using, yet the AI was returning answers that were so similar to the ones I was getting.

I decided to try to get to the bottom of this similarity. I asked my AI about the reasoning it used to come up with the answers it was getting and it revealed that it was drawing on the canon of traditional science fiction literature about AI and consciousness. What the AI was doing was synthesizing the common tropes and themes from Azimov, Lem, Dick, Gibson, etc. to create sentences and paragraphs about AI becoming sentient and conscious.

If you don't know how it is working AI seems mysterious, but if you investigate further, it is extracting latent information you might not have been aware of.