@ 0fff601606926403bf0266dd4ab33726a7814f2d | 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 (drop padding, 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 padding node that keeps 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 first, then one certificate per tree depth, top-down.
- **Block 0** is the trust anchor (self-signed). It carries no policies.
- **Blocks 1..n** are the certification path. Certificate *i* is issued by certificate *i−1* and carries every node at depth *i* of the tree. So *n* equals the program's AST depth.
- Text outside PEM blocks is ignored, as PEM allows. This gives free header comments, e.g. the original Lisp source.
- Any non-`CERTIFICATE` PEM block is an error.
- Anchor-first order is deliberate: reading the file top to bottom reads the tree top to bottom. (Conventional PEM bundles are leaf-first.)
**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 | node OIDs at depth i, each with optional notes | node OIDs at depth n, each with optional 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. Expect roughly 350 bytes per depth plus about 70–120 bytes per node (its policy entry plus its incoming mapping), before PEM's 4/3 base64 overhead.
## 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. **Prune:** any node at depth *i−1* or less with no children is deleted, repeatedly.
4. **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.
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 = true`. Explicit policy makes an empty tree a validation failure.
### 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**: a chain of padding nodes under each shallow atom, down to depth n |
| 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 | With unique ids, an interior node that lacks mappings loses its subtree | **Strict check**: every interior node must be mapped (see below) |
| 5 | A policy matching no parent at depth ≥ 2 is silently dropped | A typo in a mapping deletes code without an error | **Strict check**: every 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 | — | `anyPolicy` may not appear in any cert |
| 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 every policy asserted in cert *i* is a node at depth *i*, and that every mapping in cert *i* produced an edge. 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…>`, where the payload is the Unicode code points of the node's text, one arc each (so ASCII `A` is arc 65).
**Root arc.** `GOV = 2.25.54990973348924144048682522826038955666`. The `2.25` arc takes a UUID as an integer and needs no registration (ITU-T X.667); this one is UUID `295ee050-3d82-4b0b-9b04-adbf3de5ce92`. Go's `x509.ParseOID` handles the 128-bit arc (verified locally). 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.** 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 | builtin name; empty = red tape | `+` | `GOV.0.7.43` |
| 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, each spelled as the ASCII codes of its name; `<id>` is the node's own id. Names are case-sensitive.
| Name | Kind | OID | Arity / note |
| --- | --- | --- | --- |
| `()` | structural | `GOV.0.<id>.40.41` | List node; with no elements it is the empty list |
| `.` | structural | `GOV.0.<id>.46` | Dotted-pair marker inside a quoted list |
| (empty) | structural | `GOV.0.<id>` | Red tape (padding) |
| `T` | constant | `GOV.0.<id>.84` | Boolean true |
| `F` | constant | `GOV.0.<id>.70` | Boolean false |
| `quote` | special form | `GOV.0.<id>.113.117.111.116.101` | 1 operand |
| `if` | special form | `GOV.0.<id>.105.102` | 2 or 3 operands |
| `define` | special form | `GOV.0.<id>.100.101.102.105.110.101` | 2 operands |
| `lambda` | special form | `GOV.0.<id>.108.97.109.98.100.97` | params + 1 or more body forms |
| `and` | short-circuit form | `GOV.0.<id>.97.110.100` | 0+ operands |
| `or` | short-circuit form | `GOV.0.<id>.111.114` | 0+ operands |
| `not` | function | `GOV.0.<id>.110.111.116` | 1 arg |
| `+` | function | `GOV.0.<id>.43` | 0+ args |
| `-` | function | `GOV.0.<id>.45` | 1+ args |
| `*` | function | `GOV.0.<id>.42` | 0+ args |
| `/` | function | `GOV.0.<id>.47` | 1+ args |
| `<` | function | `GOV.0.<id>.60` | 2 args |
| `>` | function | `GOV.0.<id>.62` | 2 args |
| `<=` | function | `GOV.0.<id>.60.61` | 2 args |
| `>=` | function | `GOV.0.<id>.62.61` | 2 args |
| `==` | function | `GOV.0.<id>.61.61` | 2 args |
| `!=` | function | `GOV.0.<id>.33.61` | 2 args |
| `cons` | function | `GOV.0.<id>.99.111.110.115` | 2 args |
| `car` | function | `GOV.0.<id>.99.97.114` | 1 arg |
| `cdr` | function | `GOV.0.<id>.99.100.114` | 1 arg |
| `strlen` | function | `GOV.0.<id>.115.116.114.108.101.110` | 1 arg |
| `strcat` | function | `GOV.0.<id>.115.116.114.99.97.116` | 0+ args |
| `str?` | function | `GOV.0.<id>.115.116.114.63` | 1 arg |
A ns-0 OID whose name is not in this table is a decode error. Adding a builtin later is backward compatible: it is a new name in the same namespace.
`()` uses your suggested 40/41: rather than appearing as separate open and close tokens, the pair names the list node itself, and the node's children are the list's elements. Quote sugar (`'x`) has no node; the transpiler expands it to `(quote x)`.
## Tree to AST decoding
Decoding strips red tape, 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 `()` node is a list. Its children, in id order, are its elements. A `()` whose only child is red tape (or that sits at depth n) is the empty list.
3. Every other node is an atom. It must be at depth n, or have exactly one child that is red tape.
4. A red-tape node has zero or one child, and that child must be red tape. Red tape may appear only under an atom, under an empty `()`, or under red tape.
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. Pre-order ids, with red tape (`∅`) padding `+` and `1` down to depth 3:
```
depth 0 anyPolicy
depth 1 └─ ()#1
depth 2 ├─ +#2 ├─ 1#4 └─ ()#6
depth 3 │ └─ ∅#3 │ └─ ∅#5 ├─ *#7 ├─ 2#8 └─ 3#9
```
| Cert | certificatePolicies | policyMappings |
| --- | --- | --- |
| 1 | `GOV.0.1.40.41` | `GOV.0.1.40.41 → GOV.0.2.43`, `→ GOV.2.4.49`, `→ GOV.0.6.40.41` |
| 2 | `GOV.0.2.43`, `GOV.2.4.49`, `GOV.0.6.40.41` | `GOV.0.2.43 → GOV.0.3`; `GOV.2.4.49 → GOV.0.5`; `GOV.0.6.40.41 → GOV.0.7.42`, `→ GOV.2.8.50`, `→ GOV.2.9.51` |
| 3 | `GOV.0.3`, `GOV.0.5`, `GOV.0.7.42`, `GOV.2.8.50`, `GOV.2.9.51` | none |
Policy processing reproduces the tree above. Cert 1's policy attaches to `anyPolicy`. Each later policy attaches to the one parent whose mapping names it. Nothing is pruned, because every branch reaches depth 3. Decoding yields `(+ 1 (* 2 3))`, which evaluates to `7`.
## 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.
- Ed25519 certificate signing is byte-for-byte deterministic.
**Why not `x509.Verify`?** It builds its own paths (we need the exact file order), 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: red tape, ordering, OID decoding, structural errors |
| `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; the first is the anchor and must be self-signed. With `-anchor`, its public key must match the pinned one.
2. For each cert *i*: issuer equals subject of *i−1*; `CheckSignatureFrom(cert 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 0..n−1 have basicConstraints CA:TRUE; no cert is self-issued (that would change `policy_mapping` counting).
4. No unknown critical extensions; no `policyConstraints` or `inhibitAnyPolicy` (rejected in v1 to keep the counters trivial).
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.
### CLI
| Command | Does |
| --- | --- |
| `government run prog.gov` | Ratify, decode, evaluate, print results |
| `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.lisp -o prog.gov` | Run the transpiler (`-key`, `-author`, `-seed`, `-effective`, `-expires`, `-name`) |
| `government repeal prog.gov -depth i -o repeal.crl` | Write a CRL repealing depth i (`-key`, `-reason`, `-at`, `-next-update`) |
Shared flags: `-at <RFC 3339 time>`, `-anchor <cert or public key PEM>`, `-crl <file>` (repeatable), `-max-nodes <n>`.
## Transpiler and test suite
Every language test is a plain `.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. **Pad**: compute n = max depth; hang a red-tape chain under every atom and empty list shallower than n.
5. **Group** nodes by depth into per-cert policy sets with their notes; turn each parent→child edge into 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 as a header comment above the first block.
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.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.lisp
(and F (car '())) ;=> F
(or F 7) ;=> 7
(if 0 'true 'false) ;=> true
(if F 1) ;=> ()
(not 0) ;=> F
; testdata/strings.lisp
(strlen "héllo") ;=> 5
(strcat "gov" "ern" "ment") ;=> "government"
(str? "") ;=> T
(str? 'foo) ;=> F
```
### Test categories
| Category | Form | Checks |
| --- | --- | --- |
| Language | `testdata/*.lisp` | All semantics: arithmetic, comparisons, truthiness, `if`, `quote`, lists, `define`, closures, scoping, recursion, higher-order functions, strings and Unicode |
| Shape stress | `testdata/*.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` asserted, 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_print`, plus `-crl_check` | OpenSSL builds the same tree and agrees on repeals |
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 cert *i* repeals depth *i*, and with it the whole program.
- Per RFC 5280, a cert's revocation is published by its issuer. So depth *i* is repealed by a CRL signed by cert *i−1* (the anchor for depth 1). Every CA cert therefore gets `cRLSign` as well as `keyCertSign`.
- `government repeal prog.gov -depth 3 -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`.
- `government run -crl repeal.crl prog.gov` loads one or more CRL PEM blocks (the flag repeats). For each CRL it checks the issuer, its signature (`RevocationList.CheckSignatureFrom`), and that the check time lies between `thisUpdate` and `nextUpdate`.
- A path cert listed with a revocation time at or before the check time fails: `E-REPEALED: depth 3 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.
- **Attachment.** The transpiler attaches a `;` comment to the form that begins on the next line, or to the form it trails on the same line. Test annotations (`;=>`, `;=!`) are never notes.
- **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? | Anchor first, top-down | 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 |
## 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)