Blog › ICP guides

KL developer on retainer: tail-call optimization, accumulator pattern, KL compliance testing, and Shen backend development on monthly retainer

October 1, 2026 · ~15 min read

A KL developer was implementing a new backend for the Shen programming language, targeting a Common Lisp host. They wrote a list-processing function in KL: (defun process-items (items acc) (if (= items ()) (reverse acc) (process-items (tl items) (cons (transform (hd items)) acc)))). The function is a textbook accumulator-style tail-recursive list transformer — it walks the input list, applies transform to each head element, accumulates the results in reverse order, and reverses the accumulator at the base case. The KL specification mandates tail-call optimization (TCO) for calls in tail position, which this recursive call to process-items is: it is the last expression evaluated in the second branch of the if, with no wrapper expression around it. The developer passed a list of 50,000 elements. Stack overflow. The Common Lisp host did not guarantee TCO for named function calls inside certain if-branch patterns without specific compilation declarations. The recursive call was tail-recursive per the KL specification but not TCO-safe on that particular host. Stack overflow count: 1. The developer restructured to an iterative (do ...)-sequencing approach using explicit loop variables rather than pure recursion. Stack overflow count: 0.

The work log said “fixed stack overflow in process-items, 6h.” It cannot explain why a function that is syntactically tail-recursive overflows the stack, what TCO means in the context of the KL specification, why the KL specification mandates TCO rather than leaving it to host discretion, or why restructuring to an iterative loop is different from restructuring to a different recursive pattern. A programmer reading that entry sees six hours on a bug that looks, from the outside, like a straightforward tail-recursion issue that any Lisp programmer knows how to fix. What is invisible is the diagnostic cost: confirming that the function was indeed in tail position per KL semantics (ruling out the possibility that some wrapper was inadvertently introduced), determining which specific call pattern the Common Lisp host failed to optimize (a narrower TCO guarantee than the KL spec requires), measuring the exact list-length threshold at which overflow occurred, evaluating three candidate restructuring approaches (accumulator with explicit reverse, trampoline wrapper, iterative loop with do), and verifying that the chosen approach passes the full KL compliance suite for that function’s behavioral contract. The six hours were not six hours of typing; they were six hours of understanding the gap between what the KL specification promises and what a specific host delivers.

KL language overview: the minimal intermediate language at the core of Shen

KL — Kernel Language — is the minimal lambda-calculus-based intermediate language designed by Mark Tarver as the precise translation target for the Shen programming language. Shen is a functional language with a type-theoretic type system, pattern-matching, and a built-in Prolog-like logic engine; it runs on top of whatever host platform the implementor chooses: Common Lisp, JavaScript, Python, Scheme, Java, Haskell, and others. What makes Shen portable across all of these hosts is KL: Shen’s compiler translates Shen source code to KL, and each host provides a KL interpreter or compiler that maps KL semantics to the host’s native execution model. KL is the contract between Shen’s high-level language and its diverse runtime environments.

KL’s design philosophy is deliberate minimalism. Tarver chose to make KL as small as possible — a complete but not rich set of primitives — so that the cost of porting Shen to a new host is bounded. A new KL backend requires implementing exactly the KL primitive set and nothing more; once those primitives are correct, Shen’s entire standard library runs on top of them. The complete KL primitive set: (defun name (args) body) for named function definition; (if cond then else) for conditional (note: KL’s if takes exactly three forms and is not a multi-clause cond); (cons h t) for list construction; (hd x) for the head of a cons cell; (tl x) for the tail of a cons cell; (= x y) for structural equality across all KL types; numeric comparisons (> x y), (< x y), (>= x y), (<= x y); numeric arithmetic (+ x y), (- x y), (* x y), (/ x y); (let x val body) for single-variable local binding; (do expr1 expr2 ...) for sequencing (evaluates all subexpressions left to right, returns the value of the last); (lambda (args) body) for anonymous function construction with lexical scoping; (apply f args) for function application via a list of arguments; (error msg) for signaling a runtime error; and the type-checking predicates (number? x), (symbol? x), (string? x), (cons? x), (absvector? x).

The abstract vector operations are a specialized subset used for implementing KL’s mutable storage: (absvector n) allocates an abstract vector of size n whose contents are initially a distinguished “fail” value; (address-> v n val) writes val to position n of vector v and returns v; (<-address v n) reads and returns the value at position n of vector v. Abstract vectors are used in Shen’s implementation of hash tables, the environment stack, and other mutable data structures that cannot be efficiently implemented with purely functional cons cells. The “abstract” in absvector signals that KL does not specify the in-memory representation; the host may represent an absvector as a Lisp array, a JavaScript typed array, a Python list, or any other indexed structure, so long as read and write semantics match the KL specification.

KL’s role as a lingua franca extends beyond mere portability. Because all Shen implementations share the same KL intermediate representation, a KL developer can validate a new backend against the reference Common Lisp implementation by running both on identical KL programs and comparing outputs. Any divergence between the reference implementation’s output and the new backend’s output is a compliance bug, and the KL specification is the arbiter of which result is correct. This makes debugging a new KL backend unusually tractable: the developer has a ground-truth oracle (the reference implementation), a narrow specification (the KL primitive set), and a compliance test suite (Tarver’s KL test suite). The narrowness is both a design virtue and a source of retainer-visible work: each primitive must be correct in all its edge cases, and the edge cases often surface only when Shen’s standard library exercises them in sequences that simple unit tests do not cover.

TCO in KL: what the specification requires and where host implementations diverge

The KL specification requires tail-call optimization for functions in tail position. This is not a performance recommendation; it is a correctness requirement. KL programs, including all of Shen’s standard library, are written with the assumption that tail-recursive functions will not grow the call stack. A KL implementation that does not provide TCO for tail calls will overflow the stack on any KL program that processes a list of non-trivial length using a tail-recursive traversal. The specification’s TCO mandate exists precisely so that KL programmers can use recursion as the primary control-flow mechanism without concern for stack depth — the same reason Scheme mandates tail calls, and the same reason that the absence of mandatory tail calls in languages like Python forces a different idiom for list processing.

What the KL specification requires and what a specific host guarantees are not always the same. Common Lisp, for example, does not mandate tail-call optimization in its language standard (ANSI CL), though most production Common Lisp implementations (SBCL, CCL, LispWorks, Allegro) provide TCO for named function calls in tail position when optimization declarations are set appropriately. The gap between “the host can provide TCO” and “the host provides TCO for all KL-required call patterns” is where KL backend bugs live. A Common Lisp host implementing KL might provide TCO for simple self-tail-calls like (defun f (x) (if (= x 0) 0 (f (- x 1)))) but fail to provide TCO for self-tail-calls inside nested if branches compiled without speed-3 declarations, or for mutual recursion between two KL defuns. Each gap requires either a host-level fix (adding declaration to the generated Common Lisp code), a KL-level workaround (restructuring the KL to use a pattern the host does optimize), or documentation of the limitation.

The specific case from the opening: (defun process-items (items acc) (if (= items ()) (reverse acc) (process-items (tl items) (cons (transform (hd items)) acc)))). The recursive call (process-items (tl items) (cons (transform (hd items)) acc)) is in tail position. It is the entire body of the second branch of the outermost if; there is no expression that wraps it or that must execute after it returns. Per the KL specification, this tail call must be optimized. On the Common Lisp host in question, the KL-to-CL code generator did not emit (declare (optimize (speed 3) (safety 0))) for this specific function, which was required by that implementation to enable TCO for named function calls in if branches. The oversight was discovered only when testing with lists exceeding 8,000 elements. The fix: the KL-to-CL compiler was updated to emit the optimization declaration for all defun-generated forms. Stack overflow threshold went from 8,000 to beyond 1,000,000 without overflow. The work log entry for this fix: “fixed TCO for named function calls in if branches, 6h.” The fix itself: one line added to the code generator template. The six hours: diagnosing which call patterns triggered the overflow, which Common Lisp declarations were needed, and verifying across the full KL compliance suite that the added declaration did not change any other behavior.

Accumulator pattern in KL: converting non-tail-recursive to tail-recursive list functions

Before the accumulator pattern can fix a stack overflow in a KL function, a developer must first diagnose whether the function is actually non-tail-recursive. Many KL stack overflows are caused not by functions that fail to use the accumulator pattern but by TCO gaps in the host for functions that already use it correctly. The distinction matters for the fix: a function that is genuinely non-tail-recursive needs restructuring; a function that is tail-recursive but not optimized by the host needs a different fix (code generator changes, trampoline, or explicit loop). The diagnosis requires reading the KL carefully and confirming the call site is in tail position.

The canonical non-tail-recursive list function in KL: (defun process-items (items) (if (= items ()) () (cons (transform (hd items)) (process-items (tl items))))). Here, the recursive call (process-items (tl items)) is the argument to cons, not the final expression evaluated in the branch. The evaluation order is: (1) evaluate (transform (hd items)) to get the transformed head; (2) evaluate (process-items (tl items)) by making a recursive call; (3) evaluate (cons ...) using the results of steps 1 and 2. Step 3 cannot execute until step 2 returns, which means the call to (process-items (tl items)) is not in tail position — there is still work to do (the cons) after it returns. This function allocates a stack frame for every element in the input list. On a list of 50,000 elements, it builds a call stack 50,000 frames deep. Stack overflow is guaranteed regardless of whether the host provides TCO, because the function is structurally non-tail-recursive.

The accumulator transformation converts this to tail-recursive form by introducing an additional parameter to hold the partially built result. The transformed version: (defun process-items-helper (items acc) (if (= items ()) (reverse acc) (process-items-helper (tl items) (cons (transform (hd items)) acc)))) plus a public entry point (defun process-items (items) (process-items-helper items ())). In the helper, the recursive call (process-items-helper (tl items) (cons (transform (hd items)) acc)) is the final expression in the second branch of the if. There is no wrapper around it; after it returns, the branch is done. The recursive call is now genuinely in tail position. With a TCO-compliant host, this call will not grow the stack: the current frame is reused for the recursive call, and the function processes a 50,000-element list with constant stack depth. The reverse at the base case is needed because accumulating with (cons head acc) builds the result in reverse order; the first element processed becomes the last element in the accumulator. The KL reverse must itself be KL-native (implemented in KL using an accumulator, for the same reason — a non-tail-recursive reverse would overflow on the same long lists).

The iterative restructuring using (do ...) is an alternative when the accumulator pattern is insufficiently clear or when the host’s TCO guarantee is narrow enough that even accumulator-style named tail calls are not optimized. KL’s (do expr1 expr2 ...) form evaluates each expression for its side effects (except the last) and returns the value of the last expression. In a purely functional KL context, do is used for sequencing effectful operations like absvector writes. In an iterative restructuring, a KL developer can use a mutable-style loop by introducing an absvector to hold the loop state, writing to it in sequence, and reading from it to check the termination condition. This is unusual in functional KL code and is a last resort when neither accumulator-style tail recursion nor a trampoline is available or appropriate for the host. The trampoline pattern — having a function return a zero-argument lambda rather than making a recursive call, then having a trampoline driver loop call those thunks until one returns a non-thunk value — is a pure-KL TCO workaround that does not depend on host TCO at all, at the cost of heap allocation for each trampoline step.

KL compliance testing: verifying a new Shen backend against the specification

Tarver’s KL compliance test suite is the practical arbiter of whether a KL backend is correct. The suite covers each primitive in the KL specification across its significant input cases: structural equality (=) on all type pairs (number vs number, number vs symbol, symbol vs symbol, string vs string, string vs symbol, cons cell vs cons cell for shallow equality, cons cell vs cons cell for deep equality, cons cell vs null, null vs null); arithmetic and comparison on integers and floats including edge cases (division by zero, negative numbers, floating-point rounding); list operations (cons, hd, tl) on the empty list and on multi-level nested cons cells; lambda and apply for verifying lexical scoping (a lambda that closes over a variable should capture the variable’s value at closure-creation time, not at call time); let for sequential binding; do for correct sequencing and return-value semantics; absvector allocation, read, and write; and error signaling.

Each compliance test case has a known expected output from the reference Common Lisp implementation. A new backend passes the suite when every test case produces the same result as the reference. Divergences fall into several categories. Type category: a primitive that should return a boolean returns a truthy value in the host’s type system rather than the KL boolean true or false. A Common Lisp backend that maps KL’s (= x y) to CL’s equal and returns the CL result directly will return T instead of KL’s true when equality holds. Since KL’s if tests for KL’s true, not for host truthiness, this can cause KL conditionals to behave incorrectly for equality results used as conditions. Scope category: a lambda that does not capture variables lexically will produce wrong results when the variable was rebound after the lambda was created but before it was called. A dynamic-scoping host that binds all variables dynamically will fail lexical scoping tests, producing results that depend on the call-time binding rather than the definition-time binding. Equality category: structural equality on deeply nested cons cells must perform deep comparison. A backend that maps = to pointer equality will pass all equality tests on atoms (since KL implementations typically intern symbols, making pointer equality correct for symbols) but fail on cons cells, since two separately constructed cons cells with the same structure will have different pointer identities.

Running the KL compliance suite at the start of a retainer engagement establishes a baseline pass rate. A typical new backend targeting a well-implemented host might pass 85 to 90 percent of tests on the first run; the remaining 10 to 15 percent represent the host-specific edge cases that require host-side fixes or KL-level workarounds. Running the suite again after each fix tracks progress. The compliance suite pass rate is also the quantitative metric that makes retainer work legible to clients: “this month’s work moved the compliance suite from 87/100 passing to 97/100 passing, with the remaining 3 failures documented as host limitations that require upstream changes to address” is a concrete statement of progress. Without the compliance suite, the client sees only “fixed several bugs, 40h.”

Beyond the standard compliance suite, a KL developer on retainer will author additional tests for the specific Shen application being ported. The standard suite tests the KL primitives in isolation; Shen’s standard library tests them in composition. A function in Shen’s library that combines absvector operations with deeply recursive list traversal will exercise combinations of primitives that the compliance suite may not cover. Authoring these integration tests, running them against both the reference implementation and the new backend, and fixing the discrepancies is a significant fraction of retainer work on a new Shen backend. The work log entry for this work: “authored 15 integration tests for Shen standard library on new backend, found and fixed 4 compliance gaps, 12h.” What is invisible: the investigative work of understanding why each gap exists, which KL primitive is involved, and whether the fix belongs in the host mapping, the code generator, or the KL layer itself.

KL as a lingua franca: the design choice that makes Shen portable

The decision to design KL as an explicit intermediate language rather than compiling Shen directly to each host’s native form was a deliberate architectural choice with significant consequences for retainer work. If Shen compiled directly to Common Lisp, a new host (say, JavaScript) would require understanding Shen’s compilation pipeline from scratch, implementing transformations that map Shen’s type-theoretic type system and pattern-matching to JavaScript idioms, and maintaining that pipeline independently. By contrast, because Shen compiles to KL and KL is defined by a small, stable specification, a JavaScript backend developer only needs to implement the KL primitives in JavaScript. All of Shen’s compilation logic, standard library, and type system reside above the KL layer, shared across all backends. The KL layer is the isolation boundary.

This architectural choice also means that debugging a Shen program on a new backend has a well-defined diagnostic strategy. If a Shen program produces a wrong result on the JavaScript backend but the correct result on the reference Common Lisp backend, the developer can compile the Shen program to KL (using any working backend) and then test the KL directly on both backends. If the KL produces the same wrong result on JavaScript, the bug is in the JavaScript backend’s KL implementation. If the KL produces the correct result on both backends, the bug is in the Shen-to-KL compiler. This isolation strategy is not hypothetical; it is a standard debugging practice for KL backend developers, and tracing a Shen bug through the KL layer to its root cause in the host implementation is a common retainer task.

KL’s role as a lingua franca extends to benchmarking and optimization. A KL developer optimizing a Shen application can measure performance at the KL level, identifying which KL functions are the hot path, and then optimize the host mapping for those specific KL patterns. Because all backends share the same KL representation, performance findings on one backend generalize (with caveats) to other backends. A KL-level optimization — for example, restructuring a function to use fewer cons allocations — benefits all backends equally. A host-level optimization (adding type hints to the generated Common Lisp code) benefits only the CL backend. Understanding which optimization belongs at which layer is part of the diagnostic skill a KL retainer developer brings to the engagement.

The relationship between KL and Shen is closely analogous to the relationship between JVM bytecode and Java, or between LLVM IR and the languages that compile to it. KL is simpler and smaller than either, but the structural analogy holds: a precisely specified intermediate representation, shared across all implementations, with a compliance test suite that certifies correctness. The key difference is that KL is small enough that a single developer can implement a complete, compliant KL backend in weeks rather than months, which is why the Shen ecosystem has backends for more than a dozen host languages. Each of those backends was implemented by a developer who understood the KL specification, ran the compliance suite, and debugged the gaps between KL’s requirements and their host’s native behavior. That work is retainer-visible work when it is logged at the right level of detail.

For context on closely related retainer work: Shen developer retainers cover the layer above KL — Shen’s type-theoretic type system, pattern-matching syntax, sequent calculus type checking, and Prolog-like logic engine. A Shen retainer developer works primarily in Shen’s surface syntax, using KL as the compilation target they reason about when diagnosing performance or correctness issues. A KL retainer developer works primarily in KL itself, implementing or debugging the host mapping that makes Shen run on a new platform. The two engagements are complementary: a Shen application developer who encounters a bug that traces to the KL layer will need KL retainer expertise to resolve it; a KL backend developer who encounters a Shen standard library loading failure will need Shen-level expertise to diagnose whether the failure is in the KL layer or in the Shen compiler. Many engagements involve both, but the billing and scope boundary is the KL layer itself.

How HourTab tracks KL developer retainer hours

KL retainer work is particularly invisible because the artifacts produced are small. A TCO fix that required six hours of diagnosis produces one line of added code in a code generator. A structural equality fix that required three hours of investigation produces a two-line change in the primitive mapping. A compliance suite run that required four hours of setup, execution, and result analysis produces a pass-rate number. None of these artifacts communicates the work behind them to a client who did not observe the diagnostic process. The work log entry “fixed TCO for named function calls in if branches” says what was fixed but not what was understood to arrive at the fix, how many alternative hypotheses were ruled out, how many compliance tests were re-run to confirm no regressions, or why the host’s TCO behavior was not immediately obvious from its documentation.

The structural invisibility of KL retainer work follows the same pattern as all deeply technical language-implementation work: the time is spent understanding a system well enough to make a targeted change, not producing the change itself. The change is one line; the understanding is six hours. This is not inefficiency; it is the nature of debugging a compliance gap between a specification and a host platform. The specification says TCO is required; the host says TCO is available; the gap is in the specific conditions under which the host’s TCO fires. Closing that gap requires understanding both the specification’s requirements and the host’s TCO conditions in enough detail to construct a fix that satisfies both. That understanding is what the client pays for when they retain a KL backend developer, and it is what a logged work entry needs to convey if the retainer is to be understood as delivering commensurate value.

HourTab gives KL developers a public retainer-hours URL they send to clients — typically Shen application developers who need a reliable backend for a new host platform, language researchers exploring Shen’s type system on novel runtimes, and teams maintaining production Shen deployments that require ongoing KL-layer maintenance. For KL retainers, each work log entry should name the KL mechanism at the level that makes the work visible: which primitive, which compliance test, which TCO pattern, which host-specific behavior was diagnosed, and what change resolved it. Comparative context for scope discussions: KL retainer work is closely related to Shen developer retainers (KL is Shen’s intermediate representation; KL backend work is the foundation on which Shen application work depends; the two retainer scopes are complementary and often run in parallel for a new Shen deployment). Both retainer types share the structural challenge that hours are spent building understanding and running tests, not producing deliverables proportional to the time — which makes a structured, mechanically detailed work log the primary proof of value when a retainer renewal conversation comes.

HourTab’s work log format for KL retainers makes TCO diagnosis, compliance testing, and primitive mapping investigation visible to clients who would otherwise see only “fixed stack overflow, 6h” without any context for why stack overflow diagnosis in a language with a mandatory TCO specification takes six hours rather than thirty minutes. A structured log entry covers: TCO category (function: process-items; call site: (process-items (tl items) (cons (transform (hd items)) acc)); tail position per KL spec: yes; host TCO guarantee for this pattern: no without optimization declaration; fix: added (declare (optimize (speed 3) (safety 0))) to generated defun form; before/after: stack overflow at 8,000 elements before, tested to 1,000,000 elements without overflow after); compliance category (test group: structural equality; tests passing before: 14/20; fix: corrected = mapping to return KL boolean rather than CL T/NIL; tests passing after: 20/20); and primitive category (primitive: absvector; edge case: size-0 absvector allocation; host behavior: error on zero-size allocation; KL spec: not specified; reference implementation: returns valid empty vector; fix: added size-max guard in absvector mapping). Each log entry gives the client a record of what was investigated, what was found, and what was changed — not just what the change was.

FAQ: KL developer retainers