IntersectMBO / IntersectMBO/formal-ledger-specifications

[Property tracking] improved design: replace prose marker with typechecked statement-proof pair

Open
#1,311 0 comments 0 reactions 0 assignees View on GitHub
🛠️ infrastructure documentation
Dominant language
Agda
Stars
52
Forks
20
Avg merge
6d 14h
Merged PRs (30d)
7

Description

## Context

PR #1226 (issue #1225) introduced the property catalog (`build-tools/scripts/property-tracking/properties.yaml`), the scanner (`build-tools/scripts/property-tracking/scan_properties.py`), and the generated dashboard.

**Status** of each property is derived, never declared:

+ no module → `idea`;
+ module named but module file absent → `planned`;
+ module file exists and contains the phrase "coming soon" → `stated`;
+ otherwise → `proved`.

The Agda `--safe` typecheck in the main CI guarantees that whatever Agda exists has no holes or postulates; the scanner guarantees the bookkeeping matches the files.

## Problem

The `stated`/`proved` distinction rests entirely on a prose marker. A module could formally state a property as an uninhabited type definition (e.g. `pp-wellFormed-invariant : Type` in `src/Ledger/Conway/Specification/Chain/Properties/PParamsWellFormed.lagda.md`), which typechecks cleanly. If the `*Proof*. (coming soon)` line is dropped or forgotten, the dashboard reports the property as ✅ proved with every CI job green: a false positive in the dangerous direction, caught by nothing automated. Some of the currently-stated Conway properties have this shape.

## Proposed re-design

Make the statement and the proof separately named artifacts, record both names in the catalog, and let the typechecker, not prose, certify the relationship between them.

### Catalog

In the `properties.yaml` catalog,

+ each record represents a single property;
+ rename `defs` to `def`; this field will contain a single value instead of a list; it is the name of the **type** that defines the property.
+ add a field called `proof`; it contains a single value: the name of the inhabitant of the type named in `def`.

Each entry continues to describe exactly one property. Replace `defs` (a list, currently decorative) with two scalar fields, as in the following example:

```yaml
- id: conway-ledger-pov
title: "LEDGER preserves value"
era: conway
sts: LEDGER
module: Ledger.Conway.Specification.Ledger.Properties.PoV
anchor: thm:LEDGER-PoV
def: LEDGER-pov # the property, stated as a type
proof: LEDGER-pov-proof # the inhabitant of that type
issues: [1238]
notes: ""
```

`def` names the property definition **as a type**; supporting lemmas stay out of the catalog; where a module proves several, the entry names the headline theorem only (though we should be able to have multiple yaml records for a single module).

### New rules for determining status

+ `module` field empty → `idea`;
+ `module` field nonempty but module file absent → `planned`;
+ module file exists but `def` field is empty → `planned`;
+ module file exists, `def` field nonempty →
+ `proof` field empty → `stated`
+ `proof` field non-empty it names an inhabitant of the type named in `def` → `proved`

### Module convention

Each property module states the property as a type definition and proves it with a literal one-line ascription; for example, instead of what we have now:

```agda
LEDGER-pov : {Γ : LEnv} {s s' : LState}
→ txId ∉ mapˢ proj₁ (dom (UTxOOf s))
→ Γ ⊢ s ⇀⦇ tx ,LEDGER⦈ s' → getCoin s ≡ getCoin s'

LEDGER-pov
{s = s}
{s' = s'}
h (LEDGER-V {utxoSt' = utxoSt''} ( valid , UTXOW⇒UTXO st@(UTXO-induction r) , h' , _ )) =
-- abridged --
```

we would change the Ledger PoV type/proof to the following format:

```agda
LEDGER-pov : Type
LEDGER-pov = {Γ : LEnv} {s s' : LState}
→ txId ∉ mapˢ proj₁ (dom (UTxOOf s))
→ Γ ⊢ s ⇀⦇ tx ,LEDGER⦈ s' → getCoin s ≡ getCoin s'

LEDGER-pov-proof : LEDGER-pov
LEDGER-pov-proof
{s = s}
{s' = s'}
h (LEDGER-V {utxoSt' = utxoSt''} ( valid , UTXOW⇒UTXO st@(UTXO-induction r) , h' , _ )) =
-- abridged ---
```

That way, the `scan_properties` script really only has to check that the line `LEDGER-pov-proof : LEDGER-pov` appears to confirm that the property is proved.

More generally, if a yaml record has

```yaml
- id: conway-ledger-property
def: PropertyType
proof: PropertyProof
```

Then the scanner must find a line containing the string `PropertyProof : PropertyType`.

Contributor guide

Open the contributing guide

Research direction

Read build-tools/scripts/property-tracking/properties.yaml and build-tools/scripts/property-tracking/scan_properties.py, then inspect the example module src/Ledger/Conway/Specification/Chain/Properties/PParamsWellFormed.lagda.md. Update catalog records and property modules to use scalar def/proof names, and make the scanner recognize a proof line such as `PropertyProof : PropertyType`; done means statuses are derived from these typechecked statement-proof pairs rather than prose markers.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
build-system, tooling
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.