Polymorphic First-Class Environments
cs.PL
Submitted: 2026-10-27
Updated: 2026-10-27
License: http://creativecommons.org/licenses/by/4.0/
The gist: First-class environments expose runtime environments as ordinary values and support a substitution-free, environment-based operational semantics.
Abstract
First-class environments expose runtime environments as ordinary values and support a substitution-free, environment-based operational semantics. They also support applications such as first-class modules, dynamic composition of environment fragments, and sandboxing via local environments. Existing environment-based calculi, however, are mostly studied in a simply typed setting and stop short of System F and polymorphism. We present F E, a polymorphic calculus with first-class environments that conservatively extends System F with a small-step environment semantics. F E eliminates all forms of substitution in System F. Term and type abstractions evaluate to closures, boxes run code under local environments, and box types expose the local typing assumptions of both. Manifest types, together with a two-sided type equivalence, play a dual role: they model type-level instantiation, and enable transparent type components in environments and modules. We prove type soundness, normalization, decidability, and standard properties of type equivalence, and conservativity over System F. The metatheory of F E is based on instantiation lemmas rather than substitution lemmas. This foundation supports polymorphic first-class modules with dynamic composition and sandboxing. We study F E in two forms. Our main presentation is an explicit, type-passing calculus that follows conventional System F. We also develop an implicitly-typed variant aligned with the semantics of polymorphic functional languages. All metatheory is mechanized in the Rocq theorem prover.
Related papers
- Formal Verification of an Out-of-Order Multiprocessor against an In-Order Weak-Memory ISA
- Fuss-free cumulative universes: theory and practice
- High-Level Synthesis of Efficient Pipelines with Visibility Control
- Model Checking Probabilistic Multiparty Session Types
- A Type System for Communication-Safe Hardware Design
- RECURSUM: Automated Code Generation for Recurrence Relations Exceeds Expert Optimization via LayeredCodegen