Modular Composition of Inductive Types Using Lean Meta-programming
Ramy Shahin
cs.PL
Sep 21, 2026 · v1
cs.LO cs.SE
TL;DR
Presents Lean meta-programming algorithms and syntactic extensions for modular composition, reuse, and extension of inductive type and function definitions.
Abstract
Inductive types are ubiquitous building blocks in many programming and theorem proving languages. An inductive type is a closed set of constructors from which values of the type can be created. That set cannot be extended though once a type is defined. This limits extensibility, reuse, and modular separation of concerns when defining types and functions operating over their values. This limitation is manifested in the expression problem, where extending an expression language with new syntactic constructors without having to modify or re-compile existing ones is a challenge in almost all programming languages. This paper presents inductive type and function implementation composition algorithms based on meta-programming. In addition, a set of syntactic extensions to the Lean proof assistant implementing those algorithms are presented. This framework allows for modular reuse, composition, and extension of a subset of Lean type and function definitions. In addition, semantic subtyping relations between component and composite types are discussed both at the type theoretic and implementation levels. The framework is demonstrated on a case study, involving the composition of syntactic and semantic artifacts of three sublanguages into one language. The case study highlights both the features and limitations of the composition framework.
Problem
Inductive types have a fixed set of constructors that cannot be extended after definition, limiting extensibility, reuse, and modular separation of concerns. This is manifested in the expression problem, where adding new syntactic constructors without modifying existing code is difficult.
Approach
The work presents algorithms for composing inductive type definitions and functions operating over them based on meta-programming. A set of syntactic extensions to the Lean proof assistant implementing these algorithms is provided. Semantic subtyping relations between component and composite types are discussed at both the type-theoretic and implementation levels.
Results
The framework is demonstrated on a case study composing syntactic and semantic artifacts of three sublanguages into one language, highlighting both features and limitations of the composition approach.