Skip to content

WIP: Unification Algorithm from Generating Good Generators + Naive Schedules from Testing Theorems#23

Closed
ngernest wants to merge 125 commits intometaprogrammingfrom
ggg
Closed

WIP: Unification Algorithm from Generating Good Generators + Naive Schedules from Testing Theorems#23
ngernest wants to merge 125 commits intometaprogrammingfrom
ggg

Conversation

@ngernest
Copy link
Copy Markdown
Owner

@ngernest ngernest commented Jul 21, 2025

WIP PR which rewrites the Chamelean backend using:

  • the unification algorithm described in Section 4 of Generating Good Generators for Inductive Relations (GGG)
  • the generator schedules in Testing Theorems, Fully Automatically (TT)

Overview:

  • UnificationMonad.lean: The unification monad from Fig. 2 of GGG (called UnifyM in our implementation)
    • UnifyM combines the State, Option and MetaM monads (the latter is Lean's metaprogramming monad, needed for producing terms + error reporting)
  • DeriveSubGenerator.lean: The algorithm in Fig. 4 of GGG for deriving one case of a generator
  • ModeAnalysis.lean: Handles constraint-processing as described in section 3 of Computing Correctly for Inductive Relations (contains types corresponding to CC's notion of compatibility)
  • Schedules.lean: Definitions of generator schedules from TT
  • ScheduleUtils.lean: Functions for manipulating generator schedules
  • GGGTests.lean: Tests corresponding to the example generators in GGG

ngernest added 30 commits July 10, 2025 16:03
@ngernest ngernest changed the title Unification Algorithm from Generating Good Generators + Naive Schedules from Testing Theorems WIP: Unification Algorithm from Generating Good Generators + Naive Schedules from Testing Theorems Aug 1, 2025
@ngernest
Copy link
Copy Markdown
Owner Author

ngernest commented Aug 7, 2025

Closing this PR, as it has been subsumed by #27

@ngernest ngernest closed this Aug 7, 2025
@ngernest ngernest deleted the ggg branch August 7, 2025 15:17
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant