government / DESIGN.md

@ 26a72779eff9f25b53bae86607e9e4f6cd54934d | history


# GOVERNMENT Language Design Document

Nov 14, 2026

## Overview

GOVERNMENT is a minimal, lexically scoped Lisp whose programs are X.509 certificate chains. The interpreter validates the chain, computes the X.509 policy tree, and evaluates that tree as the program's AST.

A `.gov` file is a real, standards-conformant certificate path: `openssl x509 -text` will happily print it, and every expression in the program is a certificate policy OID. Parentheses are policy mappings. Nesting depth is chain length.

**Goals**

- Use genuine RFC 5280 / RFC 9618 path-validation semantics, not a look-alike. A program that does not validate does not run.
- Implement the minimal Lisp core from the brief: 5 atom types, pairs, closures, 4 special forms, 2 short-circuit forms, 17 builtin functions.
- Reproducible builds: the same Lisp source always transpiles to byte-identical `.gov` output.
- Human-readable tests: every language test is a plain Lisp file run through a Lisp-to-GOVERNMENT transpiler.

**Non-goals (v1):** I/O, mutation, macros, string operations beyond length, append and type test, performance, and interoperability with the public Web PKI.

**Pipeline**

1. **Load:** decode the PEM blocks into certificates.
2. **Ratify:** validate the path (name chaining, signatures, validity, CA constraints).
3. **Policy processing:** build the valid policy tree per RFC 5280 §6.1.3–6.1.4 as updated by RFC 9618.
4. **Decode:** turn the tree into an AST (skip the validator's copies, order children, decode OIDs into atoms).
5. **Evaluate:** evaluate each top-level form in order.

Terminology used in this doc: *GOV* is the language's root OID arc; *red tape* is the copies of a leaf that the validator itself generates, through `anyPolicy`, to keep every leaf at the same depth; *ratify* means "pass path validation".

## Source format

A `.gov` file is one UTF-8 text file of concatenated PEM `CERTIFICATE` blocks: a trust anchor and one certificate per tree depth. The compiler writes them anchor first, top-down; the interpreter accepts them in any order.

- **The trust anchor** is the one self-signed certificate. It carries no policies.
- **The certification path** is every other certificate. The certificate at depth *i* is issued by the one at depth *i−1* and carries every node at depth *i* of the tree. So *n* equals the program's AST depth.
- **Order.** The interpreter recovers each certificate's depth from the certificates themselves: it starts at the anchor and follows issuer links down. Every link is pinned by a signature, so the order cannot be forged, and a shuffled file runs exactly like the ordered one. A file that is not one clean chain (no anchor, two certificates issued by the same parent, a missing depth, an unrelated certificate) is an error.
- Text outside PEM blocks is ignored, as PEM allows. The compiler writes nothing there by default (the program's name is already in every subject as `O=`). With `--source` it writes the original Lisp source, indented so no line of it can start a PEM block. The source is opt-in because the certs alone are the program, and the source may hold comments or code the author does not want to publish.
- Any non-`CERTIFICATE` PEM block is an error.
- The compiler writes anchor first so that reading the file top to bottom reads the tree top to bottom (conventional PEM bundles are leaf-first). This is for human readers only.

**Trust.** By default a program is self-ratified: the interpreter trusts the anchor inside the file, so validation checks internal consistency only. `government run --anchor gov-ca.pem prog.gov` additionally requires the anchor to match a given certificate, which gives code signing for free: only run programs ratified by your government.

### Certificate profile

| Field | Trust anchor | Cert *i* (1 ≤ i < n) | Cert *n* |
| --- | --- | --- | --- |
| Version | v3 | v3 | v3 |
| Serial | 1 | i + 1 | n + 1 |
| Signature | Ed25519 (author key) | Ed25519 (key of cert i−1) | Ed25519 (key of cert n−1) |
| Subject | `CN=<author or GOVERNMENT Anchor>, O=<program>` | `CN=GOVERNMENT Depth i, O=<program>` | `CN=GOVERNMENT Depth n, O=<program>` |
| subjectAltName | author email, if given | absent | absent |
| Validity | `--effective` to `--expires` (default 2000-01-01 to 9999-12-31) | same | same |
| basicConstraints (critical) | CA:TRUE | CA:TRUE | CA:FALSE |
| keyUsage (critical) | keyCertSign, cRLSign | keyCertSign, cRLSign | digitalSignature |
| certificatePolicies | absent | cert 1: the top-level node OIDs; certs 2..n−1: `anyPolicy` only, plus any node that carries notes | `anyPolicy` only, plus any node that carries notes |
| policyMappings (critical) | absent | one entry per parent→child edge | must be absent |
| SKI / AKI | present | present | present |

Notes:

- 9999-12-31 is RFC 5280's "no well-defined expiration" date. Effective dates, repeal, notes and authorship are covered in Civic features.
- Ed25519 signatures are deterministic, so fixed keys plus fixed dates give byte-identical output.
- Mappings in cert *n* are rejected because RFC 5280 never processes them (§6.1.4 runs only for certs 1..n−1); allowing them would hide transpiler bugs.
- Any unrecognized critical extension is rejected, per RFC 5280.

**Size.** A locally built prototype cert with 1 policy and 3 mappings was 525 bytes DER. Only cert 1 lists nodes; every other node costs just its incoming mapping, so expect roughly 350 bytes per depth plus about 50 bytes per node, before PEM's 4/3 base64 overhead.

A program whose forms are all atoms has depth 1: its single cert is both cert 1 and cert n, and lists the top-level nodes.

## The policy tree as AST

The valid policy tree has exactly the shape of a Lisp AST once four quirks are designed around: uniform leaf depth, unordered children, per-OID (not per-node) mappings, and silent dropping.

### How the tree is built

RFC 5280 §6.1 builds the tree one certificate at a time:

1. **Init:** the root is a single `anyPolicy` (`2.5.29.32.0`) node at depth 0, expecting `{anyPolicy}`.
2. **Policies of cert i:** for each policy P in the cert, every depth *i−1* node whose `expected_policy_set` contains P gets a child P. If none matches, P attaches to a depth *i−1* `anyPolicy` node, which exists only at depth 0. So cert 1's policies become the root's children: the top-level forms.
3. **anyPolicy in cert i** (RFC 9618 step d.2): for every policy that some depth-*i−1* node expects but that has no node at depth *i* yet, create that node, with every node that expects it as a parent. Certs 2..n assert only `anyPolicy`, so this one rule creates every node below depth 1: a mapped node's children, and, for a node with no mappings, a copy of itself.
4. **Prune:** any node at depth *i−1* or less with no children is deleted, repeatedly.
5. **Mappings of cert i:** for every depth-*i* node whose policy is an `issuerDomainPolicy`, its `expected_policy_set` becomes the set of mapped `subjectDomainPolicy` values. An unmapped node expects only itself, which is why step 3 copies it.

RFC 9618 (2024) updates this: it replaces the tree with a `valid_policy_graph`, a DAG where a node may have several parents, to avoid exponential growth. When every node has one parent, the graph and the tree are the same structure.

**Validation inputs:** `user-initial-policy-set = {anyPolicy}`, `initial-policy-mapping-inhibit = false`, `initial-explicit-policy = true`, `initial-any-policy-inhibit = false`. Explicit policy makes an empty tree a validation failure. `anyPolicy` must not be inhibited, because certs 2..n depend on it; for the same reason the `inhibitAnyPolicy` extension is rejected.

### Constraints and design responses

| # | Constraint from RFC 5280 / 9618 | Consequence for a Lisp AST | GOVERNMENT's response |
| --- | --- | --- | --- |
| 1 | Pruning deletes every leaf above depth n | `(+ 1 (* 2 3))` would lose `+` and `1` | **Red tape**: certs 2..n assert `anyPolicy`, so the validator copies every unmapped leaf down to depth n. Nothing is written for it |
| 2 | A cert's policies are a set (no duplicates, no order) | `(+ 1 1)` cannot have two `1` children; argument order is lost | A **node-id arc** in every OID makes siblings distinct and gives their order |
| 3 | Mappings key on the OID, not the node | Two equal-OID nodes at one depth would get identical children | Node ids are **unique across the whole program**, so every OID is unique |
| 4 | An unmapped node expects only its own OID | A missing mapping silently drops a subtree: nodes below depth 1 exist only through mappings | A list node (code 1) must have at least one element, and the empty list is its own constant (code 5). **Strict check**: node ids must be exactly 1..N, so a lost subtree leaves a gap. Only losing the subtree with the highest ids goes unnoticed; signatures rule out tampering, so that case can only be a transpiler bug, which round-trip tests catch |
| 5 | A policy matching no parent at depth ≥ 2 is silently dropped | An explicitly listed node (one carrying notes) with a wrong OID would vanish | **Strict check**: every explicitly asserted policy must appear in the final tree |
| 6 | Mappings in cert n are never processed | Dead data | Rejected |
| 7 | `anyPolicy` must not be mapped | — | Certs 2..n must assert `anyPolicy`; cert 1 must not (it would create an `anyPolicy` node under the root); it may never be mapped |
| 8 | An empty tree fails explicit-policy validation | The empty program cannot exist | A program needs ≥ 1 top-level form |
| 9 | One child OID mapped from several parents gets several parents (9618) or is duplicated (5280) | Shared subexpressions | Allowed; evaluated directly on the DAG, never unfolded (decided) |

**Strict check.** Plain RFC processing forgives mistakes by deleting code. After policy processing, the interpreter also verifies that certs 2..n assert `anyPolicy` and cert 1 does not, that every explicitly asserted policy in cert *i* is a node at depth *i*, that every mapping in cert *i* produced an edge, and that the program's distinct node ids are exactly 1..N with no gaps. A failure is a ratification error naming the orphaned OID. This turns silent data loss into a compile-style error.

**Denial-of-service guard.** Policy processing has caused real DoS bugs, e.g. Go's CVE-2026-32281 (inefficient policy validation, fixed in Go 1.25.9 / 1.26.2). The graph form keeps work linear in mappings, and the interpreter caps nodes (`--max-nodes`, default 1,000,000).

## OID encoding

Every node OID is `GOV.<namespace>.<node-id>.<payload…>`. For a builtin the payload is one arc, its fixed code from the builtin table. For every other node it is the Unicode code points of the node's text, one arc each (so ASCII `A` is arc 65).

**Root arc.** `GOV = 2.25.9665536045854453410170579537759926404`. The `2.25` arc takes a UUID as an integer and needs no registration (ITU-T X.667); this one is UUID `074583b8-3bb7-4179-8669-827877697884`. Go's `x509.ParseOID` handles the 128-bit arc. Tools print `GOV` as shorthand.

**Node id.** A positive integer, unique across the whole program, assigned in pre-order by the transpiler. Siblings are ordered by ascending id. Uniqueness is what makes constraints 2 and 3 above go away.

**Payload.** For symbols, numbers and strings: Unicode code points 0–0x10FFFF, excluding surrogates. ASCII is the common case. Verified locally: an arc of 128512 (😀) survives a create/parse round trip.

### Namespaces

| ns | Kind | Payload | Source | OID |
| --- | --- | --- | --- | --- |
| 0 | builtin | one arc, the builtin's code | `+` | `GOV.0.7.21` |
| 1 | symbol | symbol name (non-empty) | `foo` | `GOV.1.8.102.111.111` |
| 2 | integer | decimal text | `-42` | `GOV.2.9.45.52.50` |
| 3 | float | decimal text | `3.14` | `GOV.3.10.51.46.49.52` |
| 4 | string | the string's characters, unescaped (may be empty) | `"hi"` | `GOV.4.11.104.105` |

Separating builtins (ns 0) from symbols (ns 1) means a user symbol can never shadow a builtin by accident: the transpiler maps the reserved names in the next section to ns 0, and everything else to ns 1.

**Payload grammars**

- Integer: `-?(0|[1-9][0-9]*)`, range of int64.
- Float: `-?[0-9]+\.[0-9]+([eE][-+]?[0-9]+)?`. A dot is required; NaN and infinities are not literals.
- Symbol: any non-empty code point sequence that is not a reserved name and does not parse as a number.

**Why text for numbers.** It is uniform with strings and symbols, follows your ASCII-arc idea, round-trips floats exactly as written, and is readable in an `openssl` dump with a one-line decoder. The alternative (a sign arc plus a magnitude arc for integers, IEEE-754 bits for floats) is shorter but opaque.

## Builtin symbol table

There are 28 builtins, all in namespace 0. Package `builtin` holds this table; the OID encoding and the evaluator both read it, and the evaluator refuses to start if a builtin there has no implementation. Each has a fixed numeric code, which is its whole payload: one arc. `<id>` is the node's own id. Names are case-sensitive.

Codes are grouped with room to grow: structure 1–2, constants 3–5, special forms 10–15, functions 20 and up. A code is permanent: it is never reused or renumbered, and a new builtin takes the next free code in its group.

| Code | Name | Kind | OID | Arity / note |
| --- | --- | --- | --- | --- |
| 1 | `(…)` | structural | `GOV.0.<id>.1` | List node; its children are the elements; at least one |
| 2 | `.` | structural | `GOV.0.<id>.2` | Dotted-pair marker inside a quoted list |
| 3 | `T` | constant | `GOV.0.<id>.3` | Boolean true |
| 4 | `F` | constant | `GOV.0.<id>.4` | Boolean false |
| 5 | `()` | constant | `GOV.0.<id>.5` | The empty list |
| 10 | `quote` | special form | `GOV.0.<id>.10` | 1 operand |
| 11 | `if` | special form | `GOV.0.<id>.11` | 2 or 3 operands |
| 12 | `define` | special form | `GOV.0.<id>.12` | 2 operands |
| 13 | `lambda` | special form | `GOV.0.<id>.13` | params + 1 or more body forms |
| 14 | `and` | short-circuit form | `GOV.0.<id>.14` | 0+ operands |
| 15 | `or` | short-circuit form | `GOV.0.<id>.15` | 0+ operands |
| 20 | `not` | function | `GOV.0.<id>.20` | 1 arg |
| 21 | `+` | function | `GOV.0.<id>.21` | 0+ args |
| 22 | `-` | function | `GOV.0.<id>.22` | 1+ args |
| 23 | `*` | function | `GOV.0.<id>.23` | 0+ args |
| 24 | `/` | function | `GOV.0.<id>.24` | 1+ args |
| 25 | `<` | function | `GOV.0.<id>.25` | 2 args |
| 26 | `>` | function | `GOV.0.<id>.26` | 2 args |
| 27 | `<=` | function | `GOV.0.<id>.27` | 2 args |
| 28 | `>=` | function | `GOV.0.<id>.28` | 2 args |
| 29 | `==` | function | `GOV.0.<id>.29` | 2 args |
| 30 | `!=` | function | `GOV.0.<id>.30` | 2 args |
| 31 | `cons` | function | `GOV.0.<id>.31` | 2 args |
| 32 | `car` | function | `GOV.0.<id>.32` | 1 arg |
| 33 | `cdr` | function | `GOV.0.<id>.33` | 1 arg |
| 34 | `strlen` | function | `GOV.0.<id>.34` | 1 arg |
| 35 | `strcat` | function | `GOV.0.<id>.35` | 0+ args |
| 36 | `str?` | function | `GOV.0.<id>.36` | 1 arg |

A ns-0 OID whose code is not in this table, or that does not have exactly one payload arc, is a decode error. Adding a builtin later is backward compatible: it is a new code in the same namespace.

Fixed codes keep every builtin OID to one payload arc (spelling names in ASCII took up to six), at the cost of `openssl` dumps no longer showing builtin names; `government tree` decodes them.

A non-empty list is one list node whose children, in id order, are the list's elements, rather than separate open and close tokens. The tree already encodes nesting, so this needs no matching of parentheses, makes unbalanced lists impossible to encode, and keeps depth equal to nesting depth. Quote sugar (`'x`) has no node; the transpiler expands it to `(quote x)`.

## Tree to AST decoding

Decoding skips red tape (the validator's copies), sorts each node's children by id, and reads every OID as an atom or a list.

**Rules**

1. The root (`anyPolicy`) is the program. Its children, in id order, are the top-level forms.
2. A child with the same OID as its parent is a copy made by the validator. The decoder skips it. A copy may only have a copy below it.
3. A list node (code 1) is a list. Its other children, in id order, are its elements, and it must have at least one. The empty list is the constant `()` (code 5), an atom.
4. Every other node is an atom. Its only child may be its copy.
5. `.` may appear only as the second-to-last element of a list. It builds a dotted pair and is only meaningful under `quote`.
6. Anything else is a decode error that names the offending OID and depth.

### Worked example: `(+ 1 (* 2 3))`

The AST is 3 deep, so the file holds an anchor plus 3 certs. Ids are given in pre-order. This is `government tree`'s output for it; a trailing `'` marks a copy the validator makes:

```
depth 0  anyPolicy
depth 1  `-- (...)#1       GOV.0.1.1
depth 2      |-- +#2       GOV.0.2.21
depth 3      |   `-- +#2'  copy
depth 2      |-- 1#3       GOV.2.3.49
depth 3      |   `-- 1#3'  copy
depth 2      `-- (...)#4   GOV.0.4.1
depth 3          |-- *#5   GOV.0.5.23
depth 3          |-- 2#6   GOV.2.6.50
depth 3          `-- 3#7   GOV.2.7.51
```

| Cert | certificatePolicies | policyMappings |
| --- | --- | --- |
| 1 | `GOV.0.1.1` | `GOV.0.1.1 → GOV.0.2.21`, `→ GOV.2.3.49`, `→ GOV.0.4.1` |
| 2 | `anyPolicy` | `GOV.0.4.1 → GOV.0.5.23`, `→ GOV.2.6.50`, `→ GOV.2.7.51` |
| 3 | `anyPolicy` | none |

Policy processing reproduces the tree above. Cert 1's policy attaches to the root. In cert 2, `anyPolicy` creates the three nodes #1 expects. In cert 3, it creates the three nodes #4 expects, and copies `+#2` and `1#3`, which expect only themselves. Nothing is pruned, because every branch reaches depth 3. Decoding skips the copies and yields `(+ 1 (* 2 3))`, which evaluates to `7`.

This was checked with a prototype chain against two independent implementations, OpenSSL 3.0 and Go 1.24's `x509.Verify`: a shallow atom survives to the last cert only when the certs below it assert `anyPolicy`, mapping targets need not be listed, and inhibiting `anyPolicy` makes the chain fail.

## Language semantics

GOVERNMENT is a strict, lexically scoped, purely functional Lisp-1 with Scheme-style truthiness (only F is false) and immutable bindings.

### Values

| Type | Representation | Printed as |
| --- | --- | --- |
| Integer | int64; overflow is an error | `-42` |
| Float | float64; NaN or infinity results are errors | `3.14`, `1.0` (always has a dot) |
| String | immutable sequence of code points | `"hello"`, with `\"`, `\\`, `\n`, `\t` escaped |
| Boolean | `T` or `F` | `T`, `F` |
| Symbol | interned name | `foo` |
| Pair | immutable (car, cdr) | `(1 2 3)`, `(1 . 2)` |
| Empty list | unique value | `()` |
| Function | closure or builtin | `#<lambda fact>`, `#<lambda>`, `#<builtin +>` |

Lists are pairs ending in `()`.

### Evaluation

- Integers, floats, strings, `T`, `F` and `()` evaluate to themselves.
- A symbol evaluates to its lexical binding; unbound is an error.
- A builtin function name (`+`, `car`, …) evaluates to that function, so builtins are first-class: `(define add +)` works.
- A special-form name in a non-head position is an error. `(define my-if if)` is rejected.
- A non-empty list whose head is a special form follows that form's rule. Otherwise the head and then the arguments are evaluated left to right, and the head must be a function.
- Tail calls (function bodies and `if` branches) are proper, so recursive loops run in constant Go stack.

### Special forms

- **Truthiness.** As in Scheme, `F` is the only false value. Everything else is true, including `0`, `0.0`, `""` and `()`.
- **`(quote d)`** returns `d` as data, unevaluated. Atoms become their values. Builtin nodes become symbols of the same name (`'+` is the symbol `+`), except `T`/`F` (booleans) and `()` (lists).
- **`(if c a b)`** evaluates `a` unless `c` is `F`, in which case it evaluates `b`. **`(if c a)`** returns `()` when `c` is `F`. Only the selected branch is evaluated.
- **`(define name expr)`** is allowed at top level and at the start of a lambda body, before any expression. It returns the symbol `name`. When the value is a `lambda` written directly in the `define`, the closure takes `name` for printing and error messages (`#<lambda fact>`, `fact takes 1 argument, got 2`); binding it again later does not rename it. Scoping rules are below.
- **`(lambda (p1 … pk) body…)`** creates a closure over the current environment. It takes a fixed number of parameters (no variadic lambdas), which must be distinct symbols. The body is zero or more `define`s followed by one or more expressions; the last expression's value is returned. Calling with the wrong number of arguments is an error.
- **`(and x…)`** evaluates left to right and returns `F` at the first `F`; otherwise it returns the last value. `(and)` is `T`.
- **`(or x…)`** evaluates left to right and returns the first value that is not `F`; otherwise `F`. `(or)` is `F`.
- `and` and `or` are special forms, so they are not first-class.

### Definitions and scope

Definitions are sequential, like Scheme's `let*`: each `define` sees the definitions before it and itself, never the ones after it. So self-recursion works and mutual recursion does not.

```lisp
(lambda (x)
  (define y (+ x 1))   ; sees x
  (define z (+ y 1))   ; sees x, y
  z)
```

- The environment is a chain of single, immutable bindings. Each `define` extends the chain; nothing is ever changed in place.
- The new binding is visible inside its own `expr`, so `(define fact (lambda (n) … (fact …)))` works. Using it before it has a value, as in `(define x (+ x 1))`, is an error.
- Any reference to a name defined later in the same scope is an unbound-symbol error, even from inside a lambda. That is what rules out mutual recursion.
- The same rule applies at top level, so top-level functions cannot be mutually recursive either.
- Defining a name twice in the same scope is an error (immutable bindings). As in Scheme, the `define`s at the start of a lambda body form their own scope inside the parameters' scope, so a `define` may shadow a parameter. A lambda parameter or an inner `define` may shadow an outer name.

### Builtin functions

- **Arithmetic.** `+` and `*` take 0+ args (`(+)` is 0, `(*)` is 1). `-` and `/` take 1+ (`(- x)` negates; `(/ x)` is `(/ 1 x)`). Int with int stays int; any float makes the result float. Integer `/` truncates toward zero. Division by zero is an error.
- **Ordering.** `<` `>` `<=` `>=` take exactly two numbers (ints and floats mix).
- **Equality.** `==` `!=` take any two values. Numbers compare numerically (`(== 1 1.0)` is `T`). Strings, symbols and booleans compare by value; pairs compare structurally. Comparing functions is an error.
- **Boolean.** `not` takes one value of any type and returns T only for F.
- **Strings.** `strlen` returns the number of code points as an integer. `strcat` takes 0+ strings and returns their concatenation (`(strcat)` is `""`). `str?` takes any value and returns `T` if it is a string, else `F`. Non-string arguments to `strlen` or `strcat` are errors.
- **Lists.** `cons` takes any two values. `car` and `cdr` require a pair; `(car '())` is an error.

### Program output and errors

`government run` evaluates top-level forms in order and prints the value of each non-`define` form, one per line.

A runtime error stops the program with exit code 1. Every error names its source location, which is an OID: `E-UNBOUND: no statute for symbol x at GOV.1.12.120 (depth 4)`. Ratification and decode errors use exit code 2.

## Interpreter architecture

The interpreter is a pure-Go, standard-library-only module that needs Go 1.24 or later. It uses `crypto/x509` for parsing and signatures, and implements path and policy processing itself.

### Go facts verified locally (go1.24.7)

- `x509.OID` and `x509.ParseOID` handle arcs beyond 64 bits, including the 128-bit `GOV` arc.
- `Certificate.Policies` and `Certificate.PolicyMappings` are populated by `ParseCertificate`, and a critical policyMappings extension is not listed as unhandled.
- **`CreateCertificate` does not emit `PolicyMappings` in 1.24.** It silently drops the field. The transpiler must DER-encode the extension itself and pass it through `ExtraExtensions`. A ~15-line hand encoder was enough in the prototype. The same is true of `policyConstraints`.
- Ed25519 certificate signing is byte-for-byte deterministic.

**Why not `x509.Verify`?** It builds its own paths (we need exactly the path in the file), it does not expose the policy tree, and it is built around system-root semantics. `CheckSignatureFrom` gives us signatures plus the parent's CA and keyCertSign checks.

### Packages

| Package | Responsibility |
| --- | --- |
| `cmd/government` | CLI |
| `ratify` | PEM loading; path validation (§6.1.3 a–c, 6.1.4 k–n); critical-extension check |
| `policy` | RFC 9618 policy graph; strict check; node budget |
| `ast` | Graph to AST: skipping copies, ordering, OID decoding, structural errors |
| `program` | The whole load path: ratify, policy graph, decode; maps runtime errors back to node OIDs |
| `builtin` | The one table of builtins: name, OID code, kind and operand count, read by `ast` and `eval` |
| `eval` | Values, environments, special forms, builtins, trampoline for tail calls |
| `sexpr` | Lisp reader and printer, shared by the transpiler, decompiler and tests |
| `lisp2gov` | Transpiler: s-expressions to `.gov` |
| `gov2lisp` | Decompiler: AST back to Lisp text |

### Ratification steps

1. Parse every PEM block (an unreadable file is `E-MALFORMED`). Order the certs: the anchor is the only self-issued cert, every other cert's issuer must be the subject of exactly one cert in the file, and no two certs may share a parent (else `E-CHAIN`). The anchor must be self-signed. With `--anchor`, its public key must match the pinned one (else `E-FOREIGN`).
2. For each cert at depth *i*: `CheckSignatureFrom(cert at depth i−1)` passes (else `E-TAMPERED`); the check time (`--at`, default now) is inside its validity (else `E-NOT-IN-FORCE` or `E-LAPSED`).
3. Certs at depths 0..n−1 are CAs allowed to sign certs (basicConstraints CA:TRUE and keyCertSign); no cert but the anchor is self-issued, since that would change `policy_mapping` counting (else `E-CHAIN`).
4. No unknown critical extensions; no `policyConstraints` or `inhibitAnyPolicy`, rejected in v1 to keep the counters trivial (else `E-CHAIN`).
5. With `--crl`: verify each CRL and reject any path cert it revokes (`E-REPEALED`, `E-STALE-REPEALS`).
6. Run policy processing with the inputs in "The policy tree as AST", then the strict check (else `E-POLICY`; a graph past the `--max-nodes` budget is `E-TOO-LARGE`).

### CLI

| Command | Does |
| --- | --- |
| `government run prog.gov` | Ratify, decode, evaluate, print results |
| `government prog.gov` | Same as `government run prog.gov`, as with `python prog.py`. A command name always wins over a file of the same name, and an argument that is neither a file nor a `.gov` name is reported as an unknown command |
| `government verify prog.gov` | Ratify and decode only; print the certificate of ratification; exit 0 if the program is lawful |
| `government tree prog.gov` | Print the policy tree, with `GOV` abbreviated, payloads decoded and notes shown |
| `government decompile prog.gov` | Print equivalent Lisp source, notes restored as comments |
| `government compile prog.gov.lisp -o prog.gov` | Run the transpiler (`--key`, `--author`, `--seed`, `--effective`, `--expires`, `--name`, `--source`) |
| `government repeal prog.gov -o repeal.crl` | Write a CRL repealing the program (`--key` or `--seed`, `--reason`, `--at`, `--issued`, `--next-update`; `--next-update` defaults to 9999-12-31, a permanent repeal) |

Shared flags: `--at <RFC 3339 time>`, `--anchor <cert or public key PEM>`, `--crl <file>` (repeatable), `--max-nodes <n>`.

The CLI is built on [cobra](https://github.com/spf13/cobra), so flags follow GNU style: long flags take two dashes, `-o` is short for `--output`, flags may come before or after the file name, and `government <command> --help` lists a command's flags.

GOVERNMENT's Lisp source files use the extension `.gov.lisp`. A second command, `govlisp`, runs Lisp source directly, with no certificates: `govlisp` alone is a REPL (multi-line forms, errors reported without ending the session; on a terminal, line editing and history via [ergochat/readline](https://github.com/ergochat/readline), kept in `~/.govlisp_history`, Tab completion of names in scope, and Ctrl-C to discard the form being typed), and `govlisp prog.gov.lisp` runs a file, printing each non-`define` value and reporting the first error at its source line and column.

## Transpiler and test suite

Every language test is a plain `.gov.lisp` file with expected results in comments; the runner transpiles it to `.gov` bytes and runs the full interpreter pipeline on them.

### `lisp2gov` pipeline

1. **Read** Lisp: integers, floats, strings (escapes `\"` `\\` `\n` `\t` `\u{…}`), symbols, `T`/`F`, `'x`, `;` comments (kept as notes), dotted pairs.
2. **Classify**: reserved names go to ns 0, other symbols to ns 1, literals to ns 2–4. Expand `'x` to `(quote x)`. Attach each comment to its form.
3. **Number** nodes in pre-order, starting at 1.
4. **Layer**: compute n = max depth and each node's depth. No padding is written: `anyPolicy` makes the validator copy shallow leaves down.
5. **Assign**: cert 1 lists the top-level nodes; certs 2..n list `anyPolicy`, plus any node that carries notes; each parent→child edge becomes a mapping in the parent's cert.
6. **Sign**: take the author key (or the default seed), derive one Ed25519 key per depth, build the anchor and certs 1..n, and hand-encode certificatePolicies and policyMappings.
7. **Emit** PEM, with the original source above the first block if `--source` is given.

The same source and flags always give the same bytes.

### Test file format

After a top-level form, `;=> value` asserts its printed value, and `;=! text` asserts an error whose message contains `text`. In test mode, an error ends only that form, so one file can hold many error cases.

```lisp
; testdata/scoping.gov.lisp  (lexical, not dynamic)
(define x 1)
(define f (lambda () x))
(define g (lambda (x) (f)))
(g 2)                 ;=> 1
(define x 2)          ;=! immutable
((lambda (x) (define y (+ x 1)) (define z (+ y 1)) z) 1)   ;=> 3
((lambda () (define a (lambda () (b))) (define b (lambda () 1)) (a)))   ;=! unbound

; testdata/truthiness.gov.lisp
(and F (car '()))     ;=> F
(or F 7)              ;=> 7
(if 0 'true 'false)   ;=> true
(if F 1)              ;=> ()
(not 0)               ;=> F

; testdata/strings.gov.lisp
(strlen "héllo")        ;=> 5
(strcat "gov" "ern" "ment")   ;=> "government"
(str? "")             ;=> T
(str? 'foo)           ;=> F
```

### Test categories

| Category | Form | Checks |
| --- | --- | --- |
| Language | `testdata/*.gov.lisp` | All semantics: arithmetic, comparisons, truthiness, `if`, `quote`, lists, `define`, closures, scoping, recursion, higher-order functions, strings and Unicode |
| Shape stress | `testdata/*.gov.lisp` | 200-deep nesting (201 certs), 1,000-argument calls, wide `quote`d lists, shared subexpressions |
| Round trip | Go test over every `testdata` file | `gov2lisp(lisp2gov(src))` equals the normalized source, comments included |
| Ratification | Go table test that mutates a valid chain | Flipped signature byte, reordered certs, dropped mapping, orphaned policy, mapping in cert n, `anyPolicy` missing from a cert 2..n or asserted in cert 1, a list node with no elements, unknown critical extension; each expects a specific error |
| Civic | Go table test | Runs before, inside and after an `--effective`/`--expires` window; repeal of each depth; scheduled repeal; stale CRL; CRL signed by the wrong key; `--anchor` pin across a re-ratified version; notes over 200 characters; default-key warning |
| Golden | One checked-in `.gov` | Byte equality, proving determinism |
| External oracle (optional) | `openssl verify -policy_check -explicit_policy -policy 2.5.29.32.0`, plus `-crl_check` | OpenSSL accepts every valid program, rejects broken ones, and agrees on repeals. Without `-policy 2.5.29.32.0` OpenSSL treats the acceptable set as empty |

Ratification tests are Go rather than Lisp because a Lisp source cannot express a broken certificate.

## Civic features

Four X.509 features carry over into the language: effective dates, repeal by revocation, notes attached to clauses, and authorship. None of them changes evaluation; they decide whether a program may run, and what it says about itself.

### Effective dates

A program is in force only between its start and end dates.

- `government compile --effective 2027-01-01 --expires 2027-12-31` sets `notBefore` and `notAfter` on every cert. The defaults are 2000-01-01 and 9999-12-31 (no expiry).
- The interpreter checks every cert's window at the check time (`--at`, default now). The program's window is the overlap of all of them.
- Before the window: `E-NOT-IN-FORCE: takes effect 2027-01-01T00:00:00Z`. After it: `E-LAPSED: expired 2027-12-31T00:00:00Z`. Both exit with code 2.

### Repeal (revocation)

A signed certificate revocation list (CRL) can strike down a ratified program after it has shipped.

- Revoking any cert of the chain breaks it, so revoking one cert repeals the whole program.
- Per RFC 5280, a cert's revocation is published by its issuer. `government repeal` always revokes depth 1, so its CRL is signed by the anchor, with the author's own key: the author strikes down what they ratified.
- `government repeal prog.gov --reason superseded -o repeal.crl` writes that CRL. It needs the program's signing key (see Authorship). The reason is any RFC 5280 CRLReason, e.g. `superseded` or `cessationOfOperation`.
- The checker accepts a CRL from any cert of the chain, as RFC 5280 path validation does, so a hand-made CRL for depth *i*, signed by cert *i−1*, repeals the program too. Every CA cert therefore gets `cRLSign` as well as `keyCertSign`.
- `government run --crl repeal.crl prog.gov` loads one or more CRL PEM blocks (the flag repeats; `verify`, `tree` and `decompile` take it too). For each CRL it checks that its issuer is a cert of this program (else `E-FOREIGN`), its signature (`RevocationList.CheckSignatureFrom`, else `E-TAMPERED`), and that the check time is not past `nextUpdate`. A check time before `thisUpdate` is allowed: each entry's revocation time already says when the repeal applies, so a newer list can still answer whether the program was in force at an earlier `--at`.
- A path cert listed with a revocation time at or before the check time fails: `E-REPEALED: depth 1 repealed 2027-03-01 (superseded)`.
- A CRL past its `nextUpdate` is `E-STALE-REPEALS`. This is a deliberate GOVERNMENT rule: an outdated repeal list fails closed.
- A future revocation time gives a scheduled repeal. RFC 5280 treats that field as when revocation occurred, so honoring a future time is a GOVERNMENT-specific reading, noted as such.
- CRLs are always external files. A `.gov` file may still contain only certificates.

### Notes

Comments in the Lisp source travel inside the certs as notes on the clauses they describe, so a `.gov` file documents itself.

- **Encoding.** Each policy entry may carry RFC 5280 user-notice qualifiers (`id-qt-unotice`, `1.3.6.1.5.5.7.2.2`) whose `explicitText` is a UTF8String. RFC 5280 caps `explicitText` at 200 characters, so a longer note is split across several qualifiers and joined back in order. A node below depth 1 is normally created through `anyPolicy` and would take its (empty) qualifiers, so a node with a note is also listed explicitly in its cert; the explicit entry wins, because RFC 9618 step d.1 runs before d.2, which skips policies already present.
- **Attachment.** The transpiler attaches a `;` comment to the form it trails on the same line, or else to the next form that begins after it. Consecutive comments on one form are joined with line breaks. Every comment is a note: the test runner's `;=>` and `;=!` annotations are a convention of the test suite, not part of the language.
- **Semantics.** Qualifiers do not affect policy processing or evaluation; RFC 5280 only carries them along.
- **Display.** `government tree` prints notes beside nodes. Errors print the note of the innermost noted node, e.g. `E-UNBOUND: no statute for symbol z … (note: "compute the total")`. `government decompile` restores notes as comments, so the round-trip test also covers comments.
- **Go.** `x509.Certificate.Policies` holds OIDs only and has no qualifier support. The transpiler hand-encodes the whole certificatePolicies extension (as it already does for policyMappings), and the interpreter decodes qualifiers from the raw extension bytes.

### Authorship

A program is signed by its author's key, which records who ratified it and lets only that person amend or repeal it.

- `government compile --key author.pem --author "Ada Lovelace <ada@example.com>"` takes an Ed25519 PKCS#8 key. The anchor is self-signed with it, with subject `CN=Ada Lovelace, O=<program>` and the email in subjectAltName.
- The keys for certs 1..n are derived from the author key: seed for depth *i* = SHA-256(author seed ‖ "GOVERNMENT" ‖ i). Output stays byte-for-byte deterministic, and the key holder alone can rebuild the chain or sign repeals.
- Any changed byte breaks a signature: `E-TAMPERED: clause at depth 2 fails signature check`. Amending a program means re-ratifying it.
- `--anchor` pins a public key, not a whole cert. It accepts a cert or a public key PEM and compares SubjectPublicKeyInfo. A re-ratified program with new dates or text still matches its author's pin.
- `government verify` prints a certificate of ratification: author, key fingerprint (SHA-256 of the SPKI), window in force, depth and node count.
- Without `--key`, the default seed is public, so anyone can forge, amend or repeal. `verify` says so: `ratified by nobody in particular (default key)`.

## Design decisions

Every question raised in review is decided. The doc's sections above already reflect each decision.

| Question | Decision | Affects |
| --- | --- | --- |
| What counts as true? | Scheme-style: only `F` is false | Semantics |
| Number size? | 64 bits: int64 (overflow is an error) and float64 | Semantics |
| What does a program output? | Value of every non-`define` top-level form | Semantics, tests |
| Shared subexpressions? | Allowed; evaluated on the DAG without unfolding | Policy tree |
| `define` in lambda bodies? | Allowed at the start of the body; sequential, no mutual recursion | Semantics |
| Who is trusted? | The file's own anchor (`--anchor` optional) | Source format |
| Should programs expire? | Only when built with `--expires` | Civic features |
| Cert order in the file? | Written anchor first, top-down; read in any order | Source format |
| OID root? | UUID arc under `2.25` | OID encoding |
| v1 extras? | No variadic lambdas; `if` without else returns `()`; add `strlen`, `strcat`, `str?` | Semantics, builtin table |
| Which X.509 extras? | Effective dates, repeal by CRL, notes, authorship | Civic features |
| Padding? | Generated by the validator: certs 2..n assert `anyPolicy`, which copies unmapped leaves down. Verified against OpenSSL and Go | Policy tree, encoding |

## Sources

- [RFC 9618: Updates to X.509 Policy Validation](https://www.rfc-editor.org/rfc/rfc9618.html) (replaces the policy tree with a graph)
- [Go `crypto/x509` documentation](https://pkg.go.dev/crypto/x509@go1.27.0)
- [CVE-2026-32281: inefficient policy validation in Go crypto/x509](https://fieldguide.lutrasecurity.com/CVE-2026-32281)
- RFC 5280 §6.1 (Certification Path Validation), as summarized via RFC 9618 and reference implementations
- Local prototype against go1.24.7 (OID arcs, PolicyMappings marshaling, Ed25519 determinism)