Formal Computer Science / Languages & logic

Kenton Labs / Languages & logic

Type systems

Reconstruct a typing judgment from syntax, annotations, and context. Separate the validity of one judgment from the soundness of a language.

The vocabulary.

These definitions state the objects and properties used by the dataset. The complete instance specification remains the authority for each result.

Context
A map assigning types to variables currently in scope.
Arrow type
A function domain and codomain, written A → B.
Application rule
A function may be applied only to an argument matching its domain type.

How the dataset works.

Three deterministic instances define this family. Each includes its input model, a checked result, evidence, and an acceptance procedure. Download the complete dataset JSON ↘ or the area’s readable source ↘.

Acceptance procedure

  1. Walk the term recursively from an empty context.
  2. Extend the context when entering an annotated lambda.
  3. Construct arrow types for abstractions.
  4. At each application, check the argument type and return the codomain.

Cost and scope

The syntax-directed checker visits each term node; context lookup and type comparison add implementation-dependent cost.

A common failure

Being well typed is not, by itself, a proof of preservation or progress.

Worked records.

Three instances expose concrete claims and the artifacts that establish or refute them. Expand a record for the problem, checker reasoning, formal payload, and verification metadata.

KL-FCS-004
Type systemsType a Boolean identity applicationExact type reconstruction · 1 judgment

The problem

Reconstruct the type of (λx:Bool. x) true in the simply typed lambda fragment.

The checked result

Reconstructed type: Bool.

The abstraction has type Bool → Bool. Its argument has type Bool, so application produces Bool. The checker reconstructs these types from syntax and an initially empty context.

Why the checker accepts it

  1. Walk the term recursively from an empty context.
  2. Extend the context when entering an annotated lambda.
  3. Construct arrow types for abstractions.
  4. At each application, check the argument type and return the codomain.

Formal specification

{
  "term": [
    "app",
    [
      "lam",
      "x",
      "Bool",
      [
        "var",
        "x"
      ]
    ],
    [
      "bool",
      true
    ]
  ],
  "rules": "Boolean literals have Bool; variables use the context; abstractions form arrows; applications require an exact domain match."
}

Claim and evidence

{
  "claim": {
    "type": "Bool"
  },
  "witness": {
    "method": "syntax-directed reconstruction"
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 1 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

The syntax-directed checker visits each term node; context lookup and type comparison add implementation-dependent cost.

A single typing judgment; no proof of type soundness, normalization, or full language implementation.

A boundary to investigate

Being well typed is not, by itself, a proof of preservation or progress. Add independently checked derivation trees and a broader type grammar.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-018 ↘Related KL-FCS-019 ↘
KL-FCS-018
Type systemsThe Boolean identity functionExact syntax-directed typing judgment

The problem

Reconstruct the type under Boolean binders and lexical scope.

The checked result

Reconstructed type: ["arrow", "Bool", "Bool"].

The binder extends the context for its body. The inner lambda preserves access to outer bindings, and the resulting type records each input separately.

Why the checker accepts it

  1. Walk the term recursively from an empty context.
  2. Extend the context when entering an annotated lambda.
  3. Construct arrow types for abstractions.
  4. At each application, check the argument type and return the codomain.

Formal specification

{
  "term": [
    "lam",
    "x",
    "Bool",
    [
      "var",
      "x"
    ]
  ],
  "rules": "Boolean literals, contextual variables, annotated lambdas, and exact-domain applications."
}

Claim and evidence

{
  "claim": {
    "type": [
      "arrow",
      "Bool",
      "Bool"
    ]
  },
  "witness": {
    "method": "syntax-directed reconstruction"
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 1 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

The syntax-directed checker visits each term node; context lookup and type comparison add implementation-dependent cost.

Only the declared lambda fragment is checked; no inference of polymorphic or dependent types occurs.

A boundary to investigate

Being well typed is not, by itself, a proof of preservation or progress. Add independently checked derivation trees and a broader type grammar.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-004 ↘Related KL-FCS-019 ↘
KL-FCS-019
Type systemsA curried constant functionExact syntax-directed typing judgment

The problem

Reconstruct the type under Boolean binders and lexical scope.

The checked result

Reconstructed type: ["arrow", "Bool", ["arrow", "Bool", "Bool"]].

The binder extends the context for its body. The inner lambda preserves access to outer bindings, and the resulting type records each input separately.

Why the checker accepts it

  1. Walk the term recursively from an empty context.
  2. Extend the context when entering an annotated lambda.
  3. Construct arrow types for abstractions.
  4. At each application, check the argument type and return the codomain.

Formal specification

{
  "term": [
    "lam",
    "x",
    "Bool",
    [
      "lam",
      "y",
      "Bool",
      [
        "var",
        "x"
      ]
    ]
  ],
  "rules": "Boolean literals, contextual variables, annotated lambdas, and exact-domain applications."
}

Claim and evidence

{
  "claim": {
    "type": [
      "arrow",
      "Bool",
      [
        "arrow",
        "Bool",
        "Bool"
      ]
    ]
  },
  "witness": {
    "method": "syntax-directed reconstruction"
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 1 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

The syntax-directed checker visits each term node; context lookup and type comparison add implementation-dependent cost.

Only the declared lambda fragment is checked; no inference of polymorphic or dependent types occurs.

A boundary to investigate

Being well typed is not, by itself, a proof of preservation or progress. Add independently checked derivation trees and a broader type grammar.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-004 ↘Related KL-FCS-018 ↘

Go further.

Add independently checked derivation trees and a broader type grammar.

Questions to investigate

  1. Being well typed is not, by itself, a proof of preservation or progress.
  2. Which assumption in the specification can be changed to make the current evidence insufficient?
  3. Add independently checked derivation trees and a broader type grammar.

Conceptual references

These sources explain the surrounding theory. The linked material was not imported as a dataset, and these records do not claim checking by the source’s software.

Primary conceptual reference ↗

Related areas

AutomataProgramming-language semanticsSAT / SMTFormal languagesTerm rewriting