Blog › ICP guides

Shen developer on retainer: sequent calculus type declarations, type variable scope in datatype rules, bootstrapped type checker errors, and Shen-Prolog logic programming on monthly retainer

October 1, 2026 · ~15 min read

A Shen developer was building a typed lookup library using Shen’s optional sequent calculus type system. They declared a lookup-result datatype to type-check a function that searches an association list and returns a Maybe result: (datatype lookup-result X : string; H : (list (pair string string)); __________________ (lookup X H) : (maybe A);). The type variable A appears in the conclusion (maybe A) but is never introduced in any premise. Shen’s bootstrapped type checker — which is itself a Shen program using the same sequent calculus machinery — rejected the rule: unbound type variable A in the conclusion with no hypothesis to derive it from. Type errors: 2. The developer restructured the declaration to introduce A through the type of the second argument: (datatype lookup-result X : string; H : (list (pair string A)); __________________ (lookup X H) : (maybe A);). Now A is a type variable introduced by H : (list (pair string A)) in the premises and used in the conclusion. The type checker accepted the rule. Type errors: 2 → 0.

The work log entry read “fixed type variable in datatype rule, 5h.” It names the result and the duration. It cannot explain why unbound type variables in Shen’s sequent calculus rules cause errors unlike Haskell’s implicit universally-quantified type variables: in Haskell, writing f :: a -> Maybe a introduces a implicitly as a universally-quantified variable at the outermost scope; in Shen, type variables in sequent calculus rules are not implicitly quantified but instead must be explicitly introduced through the premises of the rule before they can appear in the conclusion; if A appears in the conclusion without appearing in any premise, the type checker has no way to derive what A should be unified with when the rule is applied to a concrete expression, because Shen’s type checker works by applying rules from the premises down to the conclusion and unifying the types at each step. It cannot explain why the bootstrapped nature of Shen’s type checker makes diagnosing type errors more difficult: the type checker is a Shen program defined using the same (datatype ...) machinery as user programs; when a user’s type rule fails, the error may be reported in terms of the internal Shen type rules rather than the user’s rule, because the bootstrapped checker applies its own sequent calculus rules to validate the user’s sequent calculus rules; a user who does not know that the checker is bootstrapped will look for the error in their own rule, fail to find it in the expected form, and spend time chasing errors that are actually reports from the internal checker’s rules failing to apply to the user-defined rule structure. It cannot explain why the fix required restructuring the premises rather than adding an explicit quantifier: Shen has no forall keyword or type-level lambda for universal quantification in sequent calculus rules; the only mechanism for introducing a type variable is for it to appear in a premise type where the checker can derive its value from the type of the actual argument; the premise H : (list (pair string A)) introduces A by unifying A with the second component of the pair type in the actual list argument. Five hours of sequent calculus rule restructuring, bootstrapped checker tracing, and type variable scoping analysis are invisible in a diff showing three changed lines.

Shen type system: sequent calculus rules, datatype declarations, type variable binding, and the bootstrapped type checker

Shen is a functional language designed by Mark Tarver and first released in 2012, available under a proprietary but freely usable license. Unlike most languages with optional static typing — which layer type inference over a core language in a separate pass — Shen’s type system is an integral part of the language design: it uses sequent calculus, the formal logical framework for derivation rules, as the mechanism for specifying and checking types. The type system is entirely optional ((tc +) enables it, (tc -) disables it), and programs can freely run in untyped mode. Shen compiles to KL (Kernel Language), a minimal subset of Shen that all backends must implement; from KL, programs are compiled to Common Lisp (via SBCL or ECL) or JavaScript (via Node.js). The Lisp backend is the most mature: loading a Shen program in SBCL looks like (shen.load "program.shen") in the REPL; the JavaScript backend is invoked as node shen.js -l program.shen.

The type system’s central construct is the (datatype ...) block, which defines sequent calculus rules for type-checking expressions. A sequent calculus rule has the form: zero or more premises separated by semicolons, followed by a horizontal bar of underscores (__________________), followed by the conclusion with a trailing semicolon. The horizontal bar is a visual representation of the sequent inference rule: the premises are the hypotheses, and the conclusion is what can be derived from them. When the type checker encounters an expression that matches the conclusion pattern, it checks whether the premises are satisfiable; if they are, the expression is well-typed. Multiple rules can appear in a single (datatype ...) block, separated by their own horizontal bars, and each rule is matched independently via unification against the expression being typed.

The critical difference between Shen’s sequent calculus type variables and Haskell’s polymorphic type variables is the scoping mechanism. In Haskell, a type variable appearing in a type signature like f :: a -> [a] is implicitly universally quantified over the entire signature: a can be any type, and the compiler treats it as a fresh skolem variable during type inference. In Shen, type variables in sequent calculus rules must obey the scoping discipline of sequent calculus: a type variable in the conclusion of a rule must have been introduced — given a concrete binding — through the premises of that rule. The premises are the hypotheses; the conclusion is what follows from them. If A appears in the conclusion (lookup X H) : (maybe A) but never appears in any premise, the type checker cannot determine what A should be unified with when it tries to apply the rule to a concrete expression. The application of the rule requires unifying the conclusion pattern against the actual expression and its expected type; if the conclusion contains an unbound variable A, that unification leaves A as a free variable with no constraint, which Shen’s type checker treats as an error.

The premise H : (list (pair string A)) introduces A in the correct way: when the type checker applies this rule to a concrete call (lookup X H) where H has type (list (pair string integer)), for example, it unifies H : (list (pair string A)) against the known type of H, binding A to integer; then when the conclusion is checked, (maybe A) becomes (maybe integer) because A is now bound. The type rule is genuinely polymorphic in A: the same rule applies whether H is a list of string-integer pairs, string-string pairs, or any other pair type, because A is bound by the actual type of H at each call site. This mechanism is structurally identical to how sequent calculus rules work in proof theory: the type variable is a logical variable bound by the proof context, not an implicit universal quantifier in a type signature.

Shen’s type checker is bootstrapped: it is itself a Shen program, written in Shen and using the same (datatype ...) machinery that user programs use for type-checking. This has a profound implication for error diagnosis. When a user writes a malformed sequent calculus rule, the error is reported by the bootstrapped checker applying its own internal rules to validate the user’s rule structure. The error message may reference internal type rules with names like shen.typecheck or shen.sequent rather than the user’s rule names, because the bootstrapped checker is itself a Shen program that can fail its own type checks when presented with an invalid user rule. A developer who does not know that the checker is bootstrapped will look for the error in their own lookup-result datatype and find the rule syntactically correct; the error message naming internal Shen rules appears to be a bug in Shen itself rather than a bug in the user’s rule. Understanding that the checker is bootstrapped is the key to reading these error messages correctly: they are reports from the checker’s own internal sequent calculus rules failing to apply to the user’s rule structure, which in turn means the user’s rule structure is invalid.

The (define ...) form defines multi-rule pattern-matching functions, analogous to Haskell’s pattern-matching function definitions. Each rule has the form name pattern -> result, and rules are tried in order from top to bottom. Patterns match via structural comparison against the actual argument: the pattern [H | T] matches a non-empty list with head H and tail T; the pattern [] matches the empty list; literal values match by equality. The (defun ...) form defines a simple single-clause function without pattern matching. Both forms are fully curried: every function in Shen takes exactly one argument and returns a result, which may itself be a function, enabling full partial application in the same style as Haskell or ML. Type-checking for (define ...) functions under (tc +) requires that each rule’s pattern and result are consistent with any type annotations provided, and the sequent calculus rules in (datatype ...) blocks govern what counts as a well-typed function body.

Multiple rule blocks in one (datatype ...) form allow a single datatype to specify a set of type rules for different expression shapes. Each rule block is separated from the next by its own horizontal bar line; the type checker tries all rules in a datatype block when typing an expression, applying the first rule whose conclusion unifies with the expression being checked. Unification in Shen’s type checker is first-order: type variables unify with any type, but cycles are not permitted; the unification is the same mechanism that drives Prolog’s unification of logical terms, which is not a coincidence given that Shen’s Prolog integration uses the same machinery.

Shen-Prolog integration, pattern matching, error handling, and typical retainer work

Shen’s most distinctive feature beyond its type system is the (prolog-> Goal1 Goal2 ...) construct, which embeds Prolog-style logic programming directly inside Shen functions. Within a (prolog-> ...) block, Prolog goals are written as s-expressions and evaluated using Shen’s built-in Prolog engine. Variables in Prolog goals are written as atoms starting with ?: ?X, ?Result, ?List. These variables are unified against Shen data structures using first-order unification. The (prolog-> ...) form succeeds if all its goals succeed and returns the value of the last expression that was evaluated, or fails if any goal fails. A typical use pattern is to use Prolog goals to perform relational lookup or constraint solving and then return a Shen value derived from the unified variables: (define lookup-assoc X Assoc -> (prolog-> (assoc ?X ?V Assoc) (return ?V))) would look up key X in the association list Assoc using the Prolog assoc/3 relation and return the found value.

The Prolog engine in Shen operates over the same data structures as Shen: lists, pairs, atoms, and numbers. Prolog goals unify ?-prefixed variables against the actual Shen data passed into the goal. The boundary between Prolog and Shen is seamless at the data level but requires care at the control level: Prolog’s backtracking search is not visible outside the (prolog-> ...) form; if a goal fails, the failure propagates as a Shen error or produces a specific failure value depending on how the surrounding Shen code handles it. This means that Prolog goal failures are often silent inside Shen functions — there is no stack trace from the Prolog engine, and the failure appears as a Shen exception or a missing return value, depending on how the (prolog-> ...) form is structured. Debugging Prolog goal failures is therefore a distinct skill from debugging Shen type errors, and both appear regularly in Shen retainer work.

Exception handling in Shen uses (trap-error expr (fn E -> handler)), which evaluates expr and, if it raises an error, binds the error value to E and evaluates handler. This is Shen’s equivalent of a try/catch block. The fn form creates an anonymous function: (fn X -> (* X 2)) is a lambda that doubles its argument, analogous to \x -> x * 2 in Haskell or (lambda (x) (* x 2)) in Lisp. Shen has full higher-order functions: functions are first-class values, partial application is supported by the curried calling convention, and passing functions as arguments or returning them from functions is idiomatic. The combination of higher-order functions, pattern matching, optional static typing, and embedded Prolog makes Shen a notably multi-paradigm language: functional, logic, and optionally typed, all in a single coherent system.

The @p constructor creates pairs: (@p 1 "hello") creates a pair with first component 1 and second component "hello". The (fst x) and (snd x) functions extract the pair components. Pairs are the primary product type in Shen; the type system uses (pair A B) in type annotations to refer to pairs of type A and type B. Association lists (lists of pairs) are a common Shen data structure, and the interaction between pair types and the sequent calculus type system — specifically, how type variables in pair component types flow through datatype rules — is one of the most frequent sources of type errors in Shen retainer work. Utility forms: (shen.version) returns a string describing the Shen version; (load "file.shen") loads a Shen source file; (read-file "data.txt") reads a file as a list of S-expressions.

KL (Kernel Language) is Shen’s intermediate representation. Every Shen program compiles to KL before being compiled to the target backend (Common Lisp or JavaScript). KL is a minimal subset of Shen: it has lambda, let, cond, do, freeze, thaw, trap-error, and a small set of primitive functions. KL is what all Shen backends must implement, and it defines the portability boundary for Shen programs. KL-level errors appear when a Shen construct that is syntactically valid produces a KL form that the backend rejects — for example, a (define ...) that compiles to a KL lambda with an unexpected structure, or a (prolog-> ...) that compiles to a KL call that mismatches the backend’s Prolog engine interface. Diagnosing KL-level errors requires reading the KL output (which Shen can print if asked) and understanding the correspondence between Shen surface syntax and KL forms. This is a specialized skill that appears in retainer work when backends behave differently: the Common Lisp and JavaScript backends have slightly different implementations of KL primitives, and programs that work on one backend may fail on the other due to backend-specific behavior of edge cases in trap-error, string operations, or numeric precision.

Typical Shen retainer work divides into four categories. The first is type system work: writing and debugging (datatype ...) blocks, ensuring type variable introduction discipline, tracing bootstrapped type checker errors, and designing polymorphic type rules for data structures that use pairs, lists, and user-defined types. The second is Prolog integration work: debugging (prolog-> ...) goal sequences, tracing unification failures, converting between Prolog and Shen representations of the same data structure, and handling backtracking boundary issues at the interface between Prolog goals and Shen functions. The third is backend engineering: diagnosing KL-level compilation errors, working through backend-specific behavior differences between Common Lisp and JavaScript, and optimizing programs that work correctly but perform poorly on a specific backend due to how KL forms are compiled to that backend’s native representation. The fourth is pattern matching and function design: structuring (define ...) rules to correctly cover all input patterns, handling partial functions safely using (trap-error ...), and designing accumulator-style functions to avoid performance problems on large inputs.

How HourTab tracks Shen developer retainer hours

Shen retainer work carries the invisible-hours problem in a particularly concentrated form. The type system work described above — diagnosing unbound type variables in sequent calculus rules, restructuring datatype declarations, tracing the bootstrapped type checker — produces a diff of three lines and a commit message that reads “fixed type variable in datatype rule, 5h.” The five hours are invisible in the diff because they were spent not writing code but understanding the semantics of sequent calculus rules in Shen’s specific implementation: why Haskell’s implicit universal quantification does not apply, why the bootstrapped checker produces error messages that appear to reference Shen internals, and how to restructure premise sets to introduce type variables correctly. The correct fix is three changed characters; the understanding required to arrive at that fix took five hours.

The diagnosis path for the lookup-result error illustrates the structure of Shen type system retainer work. The developer initially suspected a syntax error in the (datatype ...) block because the error message referenced an internal Shen rule rather than the user’s lookup-result rule. Investigating the internal rule required understanding that Shen’s type checker is bootstrapped: the checker itself is a Shen program using (datatype ...), and when it encounters a user rule with an unbound type variable, it fails to apply its own rule for well-formed sequent calculus conclusions, producing an error that names its own rule rather than the user’s. The second phase of diagnosis required understanding sequent calculus hypothesis scoping: not just knowing that type variables must be introduced in premises, but understanding why — that the sequent rule application works by unifying the conclusion pattern against the actual expression and its expected type, and that an unbound variable in the conclusion means the unification leaves a free variable with no constraint. The third phase was identifying which premise should be modified to introduce A and verifying that the modified premise correctly threads A through the conclusion in all cases. Each phase appears trivial in retrospect. None of them appears in the diff.

HourTab gives Shen developers a public retainer-hours URL they send to clients — typically programming languages researchers working on theorem-proving environments, academics studying logic-functional language integration, and engineers who need a Lisp with optional static typing for domain-specific language projects. Shen is a niche language: its user community is concentrated in programming languages research, academic theorem proving environments, and by developers who want a Lisp with optional static typing backed by a formal type system rather than type inference. This means Shen retainer clients are typically technically sophisticated and understand that type system work is not measured in lines of code, but they still need a work log that explains what was investigated and why a five-hour engagement on a three-line change was reasonable. HourTab’s categorized log format — sequent-calculus category (which rule, which variable, which premise was modified), bootstrapped-checker category (which internal Shen rule produced the error, what it indicated about the user rule structure), Prolog category (which goal, which unification, whether the failure was a logic error or a data structure mismatch), KL category (which KL form, which backend, what the backend-specific error indicated) — gives clients who funded the work a record of what was actually investigated.

For cross-reference context: SASL developer retainers are the closest historical parallel — SASL was designed by David Turner, who also designed Miranda and whose work on combinator reduction and lazy evaluation is part of the same functional programming research lineage that Shen participates in. SASL retainer work focuses on lazy evaluation and infinite stream handling; Shen retainer work focuses on the optional type system and logic programming integration. The two are complementary in the sense that both involve deeply non-obvious semantics that require understanding the language’s formal foundations to debug correctly. Curry developer retainers are also related: Curry integrates functional and logic programming via encapsulated search, where non-deterministic functions are evaluated by search over possible values; Shen integrates functional and logic programming via (prolog-> ...), which embeds Prolog goals directly in functional code. Both require understanding the boundary between the two paradigms and how data flows across it; the specific debugging patterns differ (Curry’s encapsulated search failures vs Shen’s Prolog goal unification failures), but the diagnostic mindset is similar. HourTab’s work log format for Shen retainers makes the type system analysis, Prolog boundary debugging, and KL-level backend tracing visible to clients who would otherwise see only the symptom — a program that fails to type-check with an error message referencing Shen internals — and not understand why the fix required understanding sequent calculus hypothesis scoping, the bootstrapped architecture of Shen’s type checker, and the unification mechanism that drives both type-checking and Prolog goal evaluation in the same language.

HourTab’s work log format for Shen retainers makes the sequent calculus debugging, bootstrapped checker tracing, and Prolog boundary work visible to clients who would otherwise see only the symptom — a type error count that should be zero but is two — and not understand why the fix required: reading the bootstrapped type checker error messages and recognizing they refer to internal Shen rules not user rules, understanding that Shen type variables are not implicitly universally quantified, tracing through the sequent calculus rule application to identify which variable was unbound, determining which premise to modify and how to structure it to introduce the type variable correctly, verifying that the modified premise threads the type variable through correctly for all possible instantiations of the type variable in caller contexts, and running (tc +) again to confirm the type error count dropped to zero. The log entry “fixed type variable in datatype rule, 5h” is correct and complete as a time record; it is incomplete as a value record. HourTab’s categorized log — sequent-calculus category (rule: lookup-result rule 1; variable: A; appeared unbound in conclusion; premise modified: H from (list (pair string string)) to (list (pair string A))); bootstrapped-checker category (error referenced: internal shen.typecheck rule; interpretation: conclusion contained unbound variable A; no user rule syntax error); type-error count (before: 2; after: 0) — gives the client the value record alongside the time record.

FAQ: Shen developer retainers