# The Boolean identity function

KL-FCS-018 · Type systems · version 1.0.0

## Problem

Reconstruct the type under Boolean binders and lexical scope.

## Context

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

## Definitions

- **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.

## 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.

## Checker reasoning

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.

## Dataset construction

{
  "family": "type-systems",
  "task": "Reconstruct the type under Boolean binders and lexical scope.",
  "input_encoding": "Structured JSON; field meanings are stated in the specification.",
  "coverage": "Exact syntax-directed typing judgment",
  "acceptance": [
    "Walk the term recursively from an empty context.",
    "Extend the context when entering an annotated lambda.",
    "Construct arrow types for abstractions.",
    "At each application, check the argument type and return the codomain."
  ],
  "generation": "Deterministic finite fixture; full enumeration or witness replay as stated.",
  "split_policy": "Reference corpus for exposition and reproduction; no train/test evaluation split is claimed."
}

## Formal payload

```json
{
  "specification": {
    "term": [
      "lam",
      "x",
      "Bool",
      [
        "var",
        "x"
      ]
    ],
    "rules": "Boolean literals, contextual variables, annotated lambdas, and exact-domain applications."
  },
  "claim": {
    "type": [
      "arrow",
      "Bool",
      "Bool"
    ]
  },
  "witness": {
    "method": "syntax-directed reconstruction"
  }
}
```

## Complexity

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

## Limits

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

## Common error and further work

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

Add independently checked derivation trees and a broader type grammar.

## Verification

Exact syntax-directed typing judgment. 1 checker units.
Replay with `python3 tools/verify.py`. Mechanical status: checked; human review
has not yet been recorded. Custom Python verification, not a proof-assistant
claim. Checker 1.0.0 and exact source hashes are in `verification.json`.

## Provenance and references

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

- [Conceptual reference](https://softwarefoundations.cis.upenn.edu/plf-current/Stlc.html)