government / SPEC.md

@ src/v0.1.0 | history


# GOVERNMENT Technical Specification

This document specifies the GOVERNMENT file format and language as they are
implemented. It gives what you need to write your own compiler: the source
language, how source becomes a tree, how the tree becomes certificates, and the
checks that the interpreter applies before it runs a program.

Where this document says a thing "must" be true, the interpreter refuses a file
in which it is not true. Where it describes "the reference compiler", it
describes what `government compile` does in a place where a compiler has a free
choice. A compiler that makes a different choice still makes valid programs.

## Overview

A program is a tree of expressions. Each node of the tree is one certificate
policy OID. A `.gov` file holds a chain of X.509 certificates: a trust anchor,
then one certificate for each depth of the tree. Certificate 1 lists the
top-level forms as its policies. Each list node has a policy mapping to each of
its elements, in the certificate at the list's depth.

To run a program, the interpreter does these steps in order:

1. **Load.** Read the PEM blocks as certificates.
2. **Order.** Put the certificates in chain order, starting at the anchor.
3. **Ratify.** Check signatures, CA constraints, extensions, validity dates and
   CRLs.
4. **Process policies.** Build the RFC 9618 valid policy graph from the chain.
5. **Strict check.** Make sure that policy processing did not drop any part of
   the program.
6. **Decode.** Turn the graph into a tree of expressions.
7. **Evaluate.** Evaluate the top-level forms in order.

## Terms

| Term      | Meaning                                                                                                                                               |
| --------- | ----------------------------------------------------------------------------------------------------------------------------------------------------- |
| GovLisp   | The source language. Source files use the extension `.gov.lisp`.                                                                                      |
| `GOV`     | The root OID arc, `2.25.9665536045854453410170579537759926404`.                                                                                       |
| Node      | One expression of the program: a list or an atom. Each node has one OID.                                                                              |
| List node | A node whose children are the elements of a non-empty list.                                                                                           |
| Atom      | Any node that is not a list node.                                                                                                                     |
| Depth     | A top-level form has depth 1. A list's elements have the list's depth plus 1. In the chain, the anchor has depth 0 and certificate *i* has depth *i*. |
| *n*       | The depth of the deepest node. The chain has *n* certificates below the anchor.                                                                       |
| Copy      | A node that the validator creates under an atom, with the atom's own OID, to carry the atom down to depth *n*. Decoding ignores copies.               |
| Note      | A source comment, stored in a certificate as a user notice.                                                                                           |
| Ratify    | Pass every check before evaluation. A program that ratifies is "lawful".                                                                              |
| Repeal    | Revoke a program with a certificate revocation list (CRL).                                                                                            |

## Source language

GovLisp source is UTF-8 text. Invalid UTF-8 is a syntax error.

### Tokens

| Token      | Syntax                                                                                                   |
| ---------- | -------------------------------------------------------------------------------------------------------- |
| Whitespace | Any character for which Unicode `White_Space` is true. It separates tokens and is otherwise ignored.     |
| `(` `)`    | List delimiters.                                                                                         |
| `'`        | Quote. `'d` reads as `(quote d)`. A `'` must be followed by a datum.                                     |
| String     | `"` to the next unescaped `"`. See Strings.                                                              |
| Comment    | `;` to the end of the line.                                                                              |
| Atom       | A run of characters up to the next delimiter. The delimiters are whitespace, `(`, `)`, `'`, `"` and `;`. |
| Dot        | An atom that is exactly `.`. It is only valid inside a list.                                             |

### Atoms

The reader classifies each atom in this order:

1. `T` is boolean true and `F` is boolean false.
2. Text that matches `-?(0|[1-9][0-9]*)` is an integer. It must fit in a signed
   64-bit integer.
3. Text that matches `-?[0-9]+\.[0-9]+([eE][-+]?[0-9]+)?` is a float. It must be
   finite as an IEEE 754 double. There must be digits on both sides of the dot.
4. Any other text that matches `[-+]?\.?[0-9]` at its start is a malformed
   number, which is a syntax error. So `+1`, `.5`, `1.` and `01` are errors.
5. Everything else is a symbol. Symbols are case-sensitive.

### Strings

A string can hold any character except an unescaped `"` or `\`. It can span
lines. These escapes are valid:

| Escape  | Character                                                                                                       |
| ------- | --------------------------------------------------------------------------------------------------------------- |
| `\"`    | `"`                                                                                                             |
| `\\`    | `\`                                                                                                             |
| `\n`    | Line feed                                                                                                       |
| `\t`    | Tab                                                                                                             |
| `\u{X}` | The code point X, written as 1 to 6 hex digits. It must be a Unicode scalar value, so surrogates are not valid. |

Any other escape is a syntax error.

### Lists and dotted pairs

`(a b c)` is a list. `()` is the empty list.

`(a b . c)` is a dotted pair. A dotted list must have at least one datum before
the `.`, exactly one datum after it, and only one `.`. If the datum after the
`.` is a list, the result is one longer list: `(a . (b c))` reads as `(a b c)`,
and `(a . ())` reads as `(a)`.

### Comments and notes

Each comment becomes a note on one datum. The note's text is the comment without
its leading `;` characters, without one space after them, and without trailing
spaces, tabs and carriage returns.

The reader attaches each comment as follows:

1. If one or more datums end on the comment's line before the comment, the
   comment attaches to the one that ends last. If several end at that same
   place, it attaches to the outermost.
2. Otherwise, the comment attaches to the first datum, in pre-order, that starts
   after the comment. This is the outermost datum that starts next.
3. Otherwise, the comment is dropped.

When several comments attach to one datum, their texts are joined in source
order with a line feed between them.

The reference compiler's `--no-comments` option drops every note.

### Reserved names

The names of the special forms and builtin functions are reserved: codes 10 and
up in the builtin table (see OIDs). A reserved name cannot be defined or used as
a lambda parameter. In source, a reserved name reads as a symbol, and the
compiler gives it namespace 0.

## The program tree

The compiler turns each datum into one node:

| Datum                               | Node                                                                           |
| ----------------------------------- | ------------------------------------------------------------------------------ |
| A non-empty list                    | A list node (builtin code 1). Its children are the list's elements, in order.  |
| The empty list                      | The builtin constant `()` (code 5).                                            |
| `T` and `F`                         | The builtin constants `T` (code 3) and `F` (code 4).                           |
| A symbol with a reserved name       | The builtin with that name, in namespace 0.                                    |
| Any other symbol                    | A symbol node, namespace 1.                                                    |
| An integer                          | An integer node, namespace 2.                                                  |
| A float                             | A float node, namespace 3.                                                     |
| A string                            | A string node, namespace 4.                                                    |
| `(a b . c)` where `c` is not a list | A list node with the children `a`, `b`, the dot builtin `.` (code 2), and `c`. |

`'d` is the list `(quote d)`. It has no node of its own.

A program must have at least one top-level form.

### Node ids

Every node has an id, a positive integer. In a program, the distinct nodes must
have exactly the ids 1 to N, with no gaps and no repeats. The children of a
node, and the top-level forms, are in ascending id order. So ids record argument
order, which a set of policies cannot.

The reference compiler gives ids in pre-order, starting at 1. In `(+ 1 (* 2 3))`
the outer list is 1, `+` is 2, `1` is 3, the inner list is 4, `*` is 5, `2` is 6
and `3` is 7.

### Shared nodes

One node can have more than one parent, because RFC 9618's policy graph allows
this. Every parent of a shared node must be at the same depth. A shared node is
one value in the decoded program, so a compiler can write a repeated
subexpression once.

Sharing must not change the program:

- One node cannot be two children of the same parent, because a certificate's
  policies are a set. In `(+ (f) (f))` the two `(f)` lists must stay two nodes.
- The ids must give the correct order of children in every parent at once. If
  `(a (g) (h))` and `(b (h) (g))` are at the same depth, `(g)` and `(h)` cannot
  both be shared.

The reference compiler shares by default, and `--no-share` turns sharing off. It
shares only lists, never atoms. Two lists are equal if they have the same
structure, the same atoms and the same notes. The k-th of several equal siblings
is shared only with other k-th copies. Before it shares a list, the compiler
checks that the order of children stays consistent, and keeps a separate list if
it does not. Then it numbers the nodes 1 to N with a topological sort of the
required orders, and breaks ties by pre-order id. So a program with nothing to
share has the same ids, and the same bytes, with or without sharing.

## OIDs

Every node OID has the form:

```
GOV.<namespace>.<id>.<payload>
```

`GOV` is `2.25.9665536045854453410170579537759926404`, a UUID arc under `2.25`
(ITU-T X.667). The UUID is `074583b8-3bb7-4179-8669-827877697884`. Tools print
the prefix as `GOV`.

### Namespaces

| Namespace | Kind    | Payload                                             | Source | OID                    |
| --------- | ------- | --------------------------------------------------- | ------ | ---------------------- |
| 0         | Builtin | One arc: the builtin's code                         | `+`    | `GOV.0.7.21`           |
| 1         | Symbol  | The name's code points, one arc each                | `foo`  | `GOV.1.8.102.111.111`  |
| 2         | Integer | The decimal text's code points                      | `-42`  | `GOV.2.9.45.52.50`     |
| 3         | Float   | The decimal text's code points                      | `3.14` | `GOV.3.10.51.46.49.52` |
| 4         | String  | The string's code points, after escapes are decoded | `"hi"` | `GOV.4.11.104.105`     |

Payload rules:

- A code point arc must be a Unicode scalar value: 0 to 0x10FFFF, with no
  surrogates.
- A symbol payload must not be empty, must not be a builtin name, and must not
  read as a number (rule 2, 3 or 4 of Atoms).
- An integer payload must match the integer grammar and fit in 64 bits.
- A float payload must match the float grammar and be finite.
- A string payload can be empty. Then the OID ends with the id arc.

The reference compiler writes integers in plain decimal, with no `-` on zero. It
writes floats in the shortest form that reads back as the same double, always
with a dot. Magnitudes below 1e-6 or at or above 1e21 use an exponent:
`1.0e+21`, `1.5e-07`. The decoder accepts any text that matches the grammar.

### Builtins

Each builtin has a fixed code, which is its whole payload. A namespace 0 OID
must have exactly one payload arc, and that arc must be a code in this table.

| Code | Name     | Kind                          | Operands                              |
| ---- | -------- | ----------------------------- | ------------------------------------- |
| 1    | `(...)`  | Structure: list node          | At least 1 child                      |
| 2    | `.`      | Structure: dotted pair marker |                                       |
| 3    | `T`      | Constant                      |                                       |
| 4    | `F`      | Constant                      |                                       |
| 5    | `()`     | Constant                      |                                       |
| 10   | `quote`  | Special form                  | 1                                     |
| 11   | `if`     | Special form                  | 2 or 3                                |
| 12   | `define` | Special form                  | 2                                     |
| 13   | `lambda` | Special form                  | Parameters, then 1 or more body forms |
| 14   | `and`    | Special form                  | 0 or more                             |
| 15   | `or`     | Special form                  | 0 or more                             |
| 20   | `not`    | Function                      | 1                                     |
| 21   | `+`      | Function                      | 0 or more                             |
| 22   | `-`      | Function                      | 1 or more                             |
| 23   | `*`      | Function                      | 0 or more                             |
| 24   | `/`      | Function                      | 1 or more                             |
| 25   | `<`      | Function                      | 2                                     |
| 26   | `>`      | Function                      | 2                                     |
| 27   | `<=`     | Function                      | 2                                     |
| 28   | `>=`     | Function                      | 2                                     |
| 29   | `==`     | Function                      | 2                                     |
| 30   | `!=`     | Function                      | 2                                     |
| 31   | `cons`   | Function                      | 2                                     |
| 32   | `car`    | Function                      | 1                                     |
| 33   | `cdr`    | Function                      | 1                                     |
| 34   | `strlen` | Function                      | 1                                     |
| 35   | `strcat` | Function                      | 0 or more                             |
| 36   | `str?`   | Function                      | 1                                     |

## The `.gov` file

A `.gov` file is text that holds PEM blocks.

- Every block must be of type `CERTIFICATE`, with no PEM headers, and must parse
  as a DER X.509 certificate.
- Every line that starts with `-----BEGIN ` must start a block that can be read.
- There must be at least 2 certificates: the anchor and certificate 1.
- Text outside the blocks is ignored.
- The certificates can be in any order. The reference compiler writes the anchor
  first, then certificates 1 to *n*.

With `--source`, the reference compiler writes the source above the first block.
It indents every non-blank line by 4 spaces, keeps blank lines empty, and adds
one blank line after the source. Because of the indent, no source line can start
a PEM block.

## Certificates

### Profile

All certificates are X.509 v3.

| Field                       | Anchor (depth 0)                            | Certificate *i*, 1 ≤ *i* < *n*         | Certificate *n*                        |
| --------------------------- | ------------------------------------------- | -------------------------------------- | -------------------------------------- |
| Serial number               | 1                                           | *i*+1                                  | *n*+1                                  |
| Issuer                      | Its own subject                             | Subject of certificate *i*−1           | Subject of certificate *n*−1           |
| Subject                     | `CN=<author>, O=<program>`                  | `CN=GOVERNMENT Depth <i>, O=<program>` | `CN=GOVERNMENT Depth <n>, O=<program>` |
| Signed by                   | Its own key                                 | The key of certificate *i*−1           | The key of certificate *n*−1           |
| Validity                    | `notBefore` to `notAfter`                   | Same                                   | Same                                   |
| basicConstraints (critical) | CA:TRUE                                     | CA:TRUE                                | CA:FALSE                               |
| keyUsage (critical)         | keyCertSign, cRLSign                        | keyCertSign, cRLSign                   | digitalSignature                       |
| subjectKeyIdentifier        | First 20 bytes of SHA-256 of the public key | Same                                   | Same                                   |
| authorityKeyIdentifier      | Its own key identifier                      | The issuer's key identifier            | The issuer's key identifier            |
| subjectAltName              | The author's email, if there is one         | Absent                                 | Absent                                 |
| certificatePolicies         | Absent                                      | See Policies                           | See Policies                           |
| policyMappings (critical)   | Absent                                      | See Mappings                           | Must be absent                         |

If *n* is 1, certificate 1 is also certificate *n*: it is not a CA and has no
mappings.

Reference compiler values:

- `<program>` is the `--name` option, or `program` by default.
- `<author>` is the name from `--author`, or `GOVERNMENT Anchor` by default.
  `--author` takes `Name <email>`, a name, or an email. With only an email, the
  email is also the name.
- The validity is the same on every certificate: `--not-before` and
  `--not-after`, or 2000-01-01T00:00:00Z and 9999-12-31T23:59:59Z by default.
  `notBefore` must be before `notAfter`.
- The interpreter only needs each subject to be distinct. It does not read the
  names.

### Keys

All signatures are Ed25519, and so are deterministic. One 32-byte seed makes
every key:

- The anchor's key is the Ed25519 key for the seed itself.
- The key of certificate *i* is the Ed25519 key for SHA-256(seed ‖ `GOVERNMENT`
  ‖ *i*), where `GOVERNMENT` is ASCII and *i* is the decimal digits of *i*, with
  no separators.

The seed comes from one of these:

- `--key`: a PKCS#8 `PRIVATE KEY` PEM file for an Ed25519 key. The seed is that
  key's seed.
- `--seed`: 64 hex digits.
- The default: SHA-256 of the ASCII text `GOVERNMENT`. This seed is public, so
  anyone can make or repeal programs with it. `government verify` names this
  ratifier as `Public (Default Key)`.

The interpreter does not check how keys were made. It only checks the
signatures.

### Policies

Each certificate lists the nodes at its depth as follows:

- **Certificate 1** lists every node at depth 1, with that node's note if it has
  one. It must not list `anyPolicy`.
- **Certificates 2 to *n*** list `anyPolicy` (`2.5.29.32.0`), then each node at
  that depth that has a note, with the note. They must list `anyPolicy`.

Other nodes below depth 1 are not listed. The validator makes them from the
mappings, because each certificate asserts `anyPolicy` (see Policy processing).
A node that has a note is listed, because the listed entry gives the node its
note.

The extension is DER:

```
certificatePolicies ::= SEQUENCE OF PolicyInformation

PolicyInformation ::= SEQUENCE {
    policyIdentifier   OBJECT IDENTIFIER,
    policyQualifiers   SEQUENCE OF PolicyQualifierInfo OPTIONAL }

PolicyQualifierInfo ::= SEQUENCE {
    policyQualifierId  OBJECT IDENTIFIER,  -- id-qt-unotice, 1.3.6.1.5.5.7.2.2
    qualifier          UserNotice }

UserNotice ::= SEQUENCE {
    explicitText       UTF8String }
```

A node without a note has no `policyQualifiers`. RFC 5280 limits `explicitText`
to 200 characters, so the reference compiler splits a longer note into chunks of
200 code points, one qualifier per chunk, in order. The reference compiler does
not mark the extension critical.

To read a note, the interpreter joins, in order, the `explicitText` of every
`id-qt-unotice` qualifier on the entry. It accepts UTF8String, IA5String,
VisibleString and BMPString. It ignores `noticeRef` and other qualifiers.

The reference compiler lists nodes in ascending id order. The interpreter does
not care about the order.

### Mappings

Each edge from a list node at depth *i* to one of its children is one mapping in
certificate *i*:

```
policyMappings ::= SEQUENCE OF SEQUENCE {
    issuerDomainPolicy   OBJECT IDENTIFIER,  -- the list node
    subjectDomainPolicy  OBJECT IDENTIFIER } -- the child
```

The reference compiler marks the extension critical, as RFC 5280 recommends.
Neither side may be `anyPolicy`. Certificate *n* must not have mappings, because
RFC 5280 never processes them. A certificate with no edges has no policyMappings
extension.

The reference compiler sorts mappings by the parent's id, then the child's id.

### Size

The certificates hold one policy entry for each top-level form and each node
that has a note, and one mapping for each edge. A shared node costs one mapping
for each parent, but its own subtree is written once.

## Ratification

The interpreter checks a file in this order. The first failure stops the program
with exit code 2.

1. **Load** the file as in The `.gov` file. Failure: `E-MALFORMED`.
2. **Order** the certificates. Exactly one certificate must be self-issued: its
   issuer name equals its subject name. That is the anchor. No two certificates
   may have the same subject, and no two may have the same issuer. Starting at
   the anchor, each next certificate is the one whose issuer is the current
   subject. Every certificate must be on that path. Failure: `E-CHAIN`.
3. **Pin.** With `--anchor`, the anchor's SubjectPublicKeyInfo must equal the
   pinned one. `--anchor` takes a `PUBLIC KEY` PEM, a certificate, or a `.gov`
   file, whose anchor is used. Failure: `E-FOREIGN`.
4. **Signatures.** The anchor must verify with its own key, and each other
   certificate with its issuer's key. The issuer must have basicConstraints
   CA:TRUE and, if it has keyUsage, keyCertSign. Failure: `E-TAMPERED` for a bad
   signature, `E-CHAIN` for a CA constraint.
5. **Extensions.** No certificate may have an unknown critical extension, a
   policyConstraints extension or an inhibitAnyPolicy extension, critical or
   not. Failure: `E-CHAIN`.
6. **Validity.** The program is in force from the latest `notBefore` to the
   earliest `notAfter` of all the certificates, the anchor included. The check
   time (`--at`, default now) must be in that window. Failure: `E-NOT-IN-FORCE`
   before it, `E-LAPSED` after it or if the window is empty.
7. **Repeals.** Each CRL from `--crl` is checked. See Repeal.
8. **Policies.** Policy processing and the strict check must pass. Failure:
   `E-POLICY`, or `E-TOO-LARGE` for a graph over the node budget.
9. **Decode.** The graph must decode to a tree. Failure: `E-DECODE`.

## Policy processing

The interpreter runs RFC 5280 section 6.1 policy processing in the graph form of
RFC 9618, on the path of certificates 1 to *n*. The anchor is the trust anchor,
not part of the path. The inputs are fixed:

| Input                          | Value         |
| ------------------------------ | ------------- |
| user-initial-policy-set        | {`anyPolicy`} |
| initial-explicit-policy        | true          |
| initial-policy-mapping-inhibit | false         |
| initial-any-policy-inhibit     | false         |

Because policyConstraints and inhibitAnyPolicy are refused, the RFC's three
counters never reach 0, so they have no effect.

The graph starts with one root node, `anyPolicy`, at depth 0, which expects
{`anyPolicy`}. For each certificate *i*, from 1 to *n*:

1. If the certificate has no certificatePolicies extension, processing fails.
2. For each policy P in the certificate that is not `anyPolicy` (RFC 9618 step
   d.1): make a node P at depth *i* under every depth *i*−1 node that expects P.
   If no node expects P, make it under each `anyPolicy` node at depth *i*−1. If
   there is none, drop P. A listed node gets the note from its entry.
3. If the certificate lists `anyPolicy` (step d.2): for each policy that some
   depth *i*−1 node expects and that has no node at depth *i* yet, make that
   node, under every node that expects it.
4. Prune: delete every node above depth *i* that has no children, until there
   are none.
5. If depth *i* has no nodes, processing fails.
6. If *i* < *n*, apply the certificate's mappings: each node at depth *i* whose
   policy is an issuerDomainPolicy now expects the set of subjectDomainPolicy
   values mapped from it. A node with no mappings expects only its own policy. A
   mapping with `anyPolicy` on either side fails processing.

Each node expects either its mapped children or itself, so step 3 makes both the
children of each list node and the copy of each atom. An atom at depth *d* gets
a copy at each depth from *d*+1 to *n*, so pruning keeps it. A list node expects
only its children, so it gets no copy.

Policy processing failures are `E-POLICY`.

### Node budget

The graph may make at most `--max-nodes` nodes, 1,000,000 by default. Copies
count. The root does not. The interpreter checks the budget each time it makes a
node, so a small file cannot make it do a large amount of work. Past the budget:
`E-TOO-LARGE`.

## Strict check

Plain policy processing drops a policy or a mapping that does not fit, without
an error. The strict check makes each of those cases an error, `E-POLICY`:

- Certificate 1 must not list `anyPolicy`. Certificates 2 to *n* must list it.
- Certificate *n* must not have mappings.
- Each policy that certificate *i* lists, other than `anyPolicy`, must be a node
  at depth *i* in the final graph.
- Each mapping in certificate *i*, for *i* < *n*, must be an edge in the final
  graph: its issuerDomainPolicy must be a node at depth *i*, with a child that
  is its subjectDomainPolicy.
- Every node OID must be under `GOV` and must decode as in OIDs.
- Two different OIDs must not have the same id. A copy has its atom's OID, so it
  does not count.
- The ids must be exactly 1 to N, where N is the largest id. A gap means that a
  subtree was lost.

## Decoding

The interpreter turns the graph into a tree:

1. The root's children, in id order, are the top-level forms. A top-level `.` is
   an error.
2. A child with the same OID as its parent is a copy. The decoder skips it. A
   copy may only have copies below it.
3. A list node's other children, in id order, are its elements. It must have at
   least one.
4. An atom must have no children other than its copy.
5. `.` may only be the second-to-last element of a list with at least 3
   elements. `(a . b)` decodes as a pair with car `a` and cdr `b`. If `b` is a
   list, the result is the longer list, as in the reader.
6. A node with several parents stays one node, and is one shared value in the
   decoded program.

A failure is `E-DECODE`, and names the OID and depth.

## Worked example

The program `(+ 1 (* 2 3))` has depth 3, so its file holds the anchor and 3
certificates.

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

Policy processing makes this graph. A `'` marks a copy:

```
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
```

Certificate 1's policy attaches to the root. In certificate 2, `anyPolicy` makes
the three nodes that #1 expects. In certificate 3, it makes the three nodes that
#4 expects, and copies `+` and `1`, which expect only themselves. Nothing is
pruned. Decoding skips the copies and gives `(+ 1 (* 2 3))`, which evaluates to
`7`.

## Repeal

A repeal is an X.509 v2 CRL in a PEM block of type `X509 CRL`. CRLs are always
separate files, given with `--crl`, which can be repeated. A CRL file can hold
several blocks.

The interpreter checks each CRL as follows:

1. Its issuer name must be the subject of a certificate in the program. Failure:
   `E-FOREIGN`.
2. Its signature must verify with that certificate's key. Failure: `E-TAMPERED`.
3. The check time must not be after its nextUpdate. Failure: `E-STALE-REPEALS`.
4. If the issuer is at depth *d* < *n*, look for an entry with the serial number
   of certificate *d*+1. If its revocation time is at or before the check time,
   the program is repealed. Failure: `E-REPEALED`.

Notes on these rules:

- The interpreter does not compare the check time with thisUpdate. A newer CRL
  can still answer whether a program was in force at an earlier time.
- A revocation time after the check time is a scheduled repeal: the program runs
  until that time. RFC 5280 does not give a future revocation time this meaning,
  and OpenSSL does not.
- A CRL from certificate *n* is checked, but it cannot revoke anything.

The reference compiler's `government repeal` always revokes certificate 1, with
a CRL signed by the anchor's key. The seed must make the anchor's public key.
The CRL holds:

| Field                  | Value                                                                       |
| ---------------------- | --------------------------------------------------------------------------- |
| thisUpdate             | `--last-update`, default now                                                |
| nextUpdate             | `--next-update`, default 9999-12-31T23:59:59Z. It must be after thisUpdate. |
| cRLNumber              | thisUpdate as Unix seconds                                                  |
| authorityKeyIdentifier | The anchor's key identifier                                                 |
| Entry                  | Serial number 2, revocation time `--at` (default now), reason `--reason`    |

The reasons are the RFC 5280 CRLReason names: `unspecified`, `keyCompromise`,
`cACompromise`, `affiliationChanged`, `superseded`, `cessationOfOperation`,
`certificateHold`, `removeFromCRL`, `privilegeWithdrawn` and `aACompromise`.

## Language semantics

GovLisp is a strict, lexically scoped Lisp-1. All values are immutable.

### Values

| Type       | Range                             | Printed as                                         |
| ---------- | --------------------------------- | -------------------------------------------------- |
| Integer    | Signed 64 bits                    | `-42`                                              |
| Float      | IEEE 754 double, always finite    | `3.25`, `1.0`, `1.0e+21`, as in OIDs               |
| String     | A sequence of Unicode code points | `"a\"b"`, with `"`, `\`, line feed and tab escaped |
| Boolean    | `T` or `F`                        | `T`, `F`                                           |
| Symbol     | A name                            | `foo`                                              |
| Pair       | A car and a cdr                   | `(1 2 3)`, `(1 . 2)`                               |
| Empty list | One value                         | `()`                                               |
| Function   | A closure or a builtin function   | `#<lambda sq>`, `#<lambda>`, `#<builtin +>`        |

A list is a chain of pairs that ends in `()`. Only `F` is false. Every other
value is true, including `0`, `0.0`, `""` and `()`.

### Evaluation

- Integers, floats, strings, `T`, `F` and `()` evaluate to themselves.
- A symbol evaluates to its binding in the current scope. An unbound symbol is
  `E-UNBOUND`.
- A builtin function name evaluates to that function, so `(define add +)` works.
- A special form name in any place other than the head of a list is
  `E-SPECIAL-FORM`.
- A list whose head is a special form follows the rule for that form. An
  improper list is `E-SYNTAX`.
- In any other list, the head and then the arguments are evaluated from left to
  right, and the head's value is called. If it is not a function:
  `E-NOT-A-FUNCTION`.
- A call in tail position uses no extra stack. The tail positions are the last
  expression of a lambda body, the branches of `if`, and the last operand of
  `and` and `or`.

### Special forms

The wrong number of operands is `E-SYNTAX`.

- `(quote d)` returns `d` without evaluating it. A builtin node becomes the
  symbol with that name, so `'+` is the symbol `+`. `T`, `F` and `()` stay
  constants.
- `(if c a b)` evaluates `c`. If it is not `F`, it evaluates `a`, otherwise `b`.
  `(if c a)` gives `()` when `c` is `F`.
- `(define name expr)` binds `name` to the value of `expr` and returns the
  symbol `name`. `name` must be a symbol that is not reserved. If `expr` is a
  `lambda` written directly in the `define`, the closure takes `name` for
  printing and errors.
- `(lambda (p1 … pk) body…)` makes a closure over the current scope. The
  parameters must be distinct symbols that are not reserved. `(lambda () …)`
  takes none. The body is zero or more `define` forms, then one or more
  expressions. The value of the last expression is the result. A call with a
  different number of arguments than parameters is `E-ARITY`.
- `(and x…)` evaluates from left to right and returns `F` at the first `F`.
  Otherwise it returns the last value. `(and)` is `T`.
- `(or x…)` evaluates from left to right and returns the first value that is not
  `F`. Otherwise it returns `F`. `(or)` is `F`.

### Definitions and scope

- `define` is valid at the top level and at the start of a lambda body. Anywhere
  else it is `E-SYNTAX`.
- Definitions are sequential. Each `define` sees the definitions before it and
  itself, and never the ones after it, even from inside a lambda. So a function
  can call itself, but two functions cannot call each other.
- A name used inside its own definition before the definition has a value, as in
  `(define x (+ x 1))`, is `E-UNBOUND`.
- A name can be defined only once in a scope. A second `define` is
  `E-IMMUTABLE`.
- The `define` forms at the start of a lambda body make a new scope inside the
  parameters' scope. So they can shadow a parameter. A parameter or an inner
  `define` can shadow an outer name.

### Builtin functions

A wrong number of arguments is `E-ARITY`. An argument of the wrong type is
`E-TYPE`.

| Function          | Result                                                                                              |
| ----------------- | --------------------------------------------------------------------------------------------------- |
| `+` `*`           | The sum or product. `(+)` is 0 and `(*)` is 1.                                                      |
| `-` `/`           | The first argument minus, or divided by, each later one. `(- x)` is `-x`, and `(/ x)` is `(/ 1 x)`. |
| `<` `>` `<=` `>=` | Compare two numbers.                                                                                |
| `==` `!=`         | Compare any two values.                                                                             |
| `not`             | `T` if the argument is `F`, otherwise `F`.                                                          |
| `cons`            | A new pair of the two arguments.                                                                    |
| `car` `cdr`       | The car or cdr of a pair. Any other argument, `()` included, is `E-TYPE`.                           |
| `strlen`          | The number of code points in a string.                                                              |
| `strcat`          | The strings joined in order. `(strcat)` is `""`.                                                    |
| `str?`            | `T` if the argument is a string, otherwise `F`.                                                     |

Arithmetic goes from left to right, one argument at a time. Two integers give an
integer. If either is a float, the result is a float. Integer `/` truncates
toward zero. Integer overflow, division by zero, and a float result that is not
finite are `E-ARITH`.

Comparisons can mix integers and floats, and compare them exactly. For `==` and
`!=`, numbers compare by value, so `(== 1 1.0)` is `T`. Pairs compare by
structure. Other values are equal only if they have the same type and value. A
function in either argument is `E-TYPE`.

### Output and errors

The interpreter evaluates the top-level forms in order. It prints the value of
each form that is not a `define`, one per line.

A runtime error stops the program with exit code 1. The message gives the error
code, the OID and depth of the node that failed, and the nearest note. For a
shared node, the note comes from the first parent that has one.

| Runtime error      | Cause                                                                |
| ------------------ | -------------------------------------------------------------------- |
| `E-UNBOUND`        | A symbol is not bound, or is used before its definition is complete. |
| `E-SYNTAX`         | A special form or a call is malformed.                               |
| `E-SPECIAL-FORM`   | A special form's name is used as a value.                            |
| `E-NOT-A-FUNCTION` | The head of a call is not a function.                                |
| `E-ARITY`          | A call has the wrong number of arguments.                            |
| `E-TYPE`           | An argument has the wrong type.                                      |
| `E-ARITH`          | Overflow, division by zero, or a float result that is not finite.    |
| `E-IMMUTABLE`      | A name is defined twice in the same scope.                           |

## Determinism

The reference compiler gives the same `.gov` bytes for the same source and
options. It does this with Ed25519, which signs deterministically, keys derived
from one seed, fixed default dates and serial numbers, and a fixed order of ids,
policies and mappings. A compiler that fixes all of these gets the same result.

A repeal CRL is deterministic only when `--at` and `--last-update` are given,
because both default to now.

## References

- [RFC 5280](https://www.rfc-editor.org/rfc/rfc5280.html), section 6.1:
  certification path validation and policy processing.
- [RFC 9618](https://www.rfc-editor.org/rfc/rfc9618.html): the policy graph that
  replaces RFC 5280's policy tree.
- [RFC 8410](https://www.rfc-editor.org/rfc/rfc8410.html): Ed25519 in X.509.
- [ITU-T X.667](https://www.itu.int/rec/T-REC-X.667): UUID-based OIDs under
  `2.25`.