Skip to content

[Merged by Bors] - feat: some tactics to transform hypotheses and goals to defeq expressions#5717

Closed
kmill wants to merge 12 commits intomasterfrom
kmill_defeq_tactics
Closed

[Merged by Bors] - feat: some tactics to transform hypotheses and goals to defeq expressions#5717
kmill wants to merge 12 commits intomasterfrom
kmill_defeq_tactics

Conversation

@kmill
Copy link
Copy Markdown
Contributor

@kmill kmill commented Jul 4, 2023

This provides a function to create a tactic from any Expr → MetaM Expr that maps expresions to defeq expressions. The tactic handles the standard location processing.

Also provides some tactics: whnf, beta_reduce, reduce, unfold_let, unfold_projs, eta_reduce, and eta_expand. Some of these (like whnf) are more useful in high-level tactic scripts or for exploration than in actual finished proofs. The unfold_let tactic is useful for finer-grained zeta reduction (a.k.a. substituting in the values of let-bound hypotheses) and for providing a working alternative to unfold for local bindings.


Open in Gitpod

@kmill kmill added awaiting-review t-meta Tactics, attributes or user commands labels Jul 4, 2023
@PatrickMassot
Copy link
Copy Markdown
Member

Is it a good opportunity to implement change ... at ...?

@kmill
Copy link
Copy Markdown
Contributor Author

kmill commented Jul 5, 2023

@PatrickMassot I added change ... at ... a few months ago. It didn't seem worth trying to unify it into this defeq tactics framework, so I left it alone.

@jeremysalwen
Copy link
Copy Markdown

Here's another tactic for applying eta reduction for structures.

def etaStructAtom (e: Expr): MetaM (Option Expr) := do
  let (declName, declArgs) := e.getAppFnArgs
  match (← getEnv).find? declName with
  | ConstantInfo.ctorInfo ctorInfo =>
    match (← getEnv).find? ctorInfo.induct with
    | ConstantInfo.inductInfo indInfo =>
      if indInfo.ctors.length == 1 
        && ctorInfo.numFields > 0
        && declArgs.size == ctorInfo.numParams + ctorInfo.numFields then
        match declArgs.get? ctorInfo.numParams with
        | some (Expr.proj _ _ arg) =>
          if ←  isDefEq e arg then
            pure (some arg)
          else
            pure none
        | some a =>
          match (a).getAppArgs'.back? with
          | some arg =>
              if ←  isDefEq e arg then
                pure (some arg)
              else
                pure none
          | none => pure none
        | _ => pure none
      else
        pure none
    | _ => pure none
  | _ =>
    pure none


 def etaStruct (e: Expr): MetaM Expr := do
  Meta.transform e (post:= fun n => do
    match (← etaStructAtom n) with
    | some t => pure (TransformStep.done t)
    | none => pure TransformStep.continue 
  )

/--
`eta_struct at loc` applies eta reduction for structures to all sub-expressions at the given location.
This also exists as a `conv`-mode tactic.

For example, if `x` is a Prod, `Prod.mk x.1 x.2` becomes `x` after eta reduction for structures.
-/
elab (name := etaStructStx) "eta_struct" loc?:(ppSpace Parser.Tactic.location)? : tactic =>
  runDefeqTactic etaStruct loc? "eta_struct"

@[inherit_doc etaStructStx]
elab "eta_struct" : conv => runDefeqConvTactic etaStruct

@kmill
Copy link
Copy Markdown
Contributor Author

kmill commented Jul 5, 2023

@jeremysalwen Added eta_struct

@jeremysalwen
Copy link
Copy Markdown

Wow thanks! I learned a lot from reading your code too!

@alexjbest
Copy link
Copy Markdown
Member

LGTM

I guess at a later date we could add eta expansion for structures (that isn't already covered here right?) i.e. x -> (x.1, x.2)

@kmill kmill dismissed thorimur’s stale review August 8, 2023 19:39

Addressed requests

@kim-em
Copy link
Copy Markdown
Contributor

kim-em commented Aug 24, 2023

bors d+

@bors
Copy link
Copy Markdown

bors bot commented Aug 24, 2023

✌️ kmill can now approve this pull request. To approve and merge a pull request, simply reply with bors r+. More detailed instructions are available here.

@github-actions github-actions bot added delegated This pull request has been delegated to the PR author (or occasionally another non-maintainer). and removed awaiting-review labels Aug 24, 2023
@kmill
Copy link
Copy Markdown
Contributor Author

kmill commented Aug 24, 2023

bors r+

@github-actions github-actions bot added the ready-to-merge This PR has been sent to bors. label Aug 24, 2023
bors bot pushed a commit that referenced this pull request Aug 24, 2023
…ions (#5717)

This provides a function to create a tactic from any `Expr → MetaM Expr` that maps expresions to defeq expressions. The tactic handles the standard location processing.

Also provides some tactics: `whnf`, `beta_reduce`, `reduce`, `unfold_let`, `unfold_projs`, `eta_reduce`, and `eta_expand`. Some of these (like `whnf`) are more useful in high-level tactic scripts or for exploration than in actual finished proofs. The `unfold_let` tactic is useful for finer-grained zeta reduction (a.k.a. substituting in the values of let-bound hypotheses) and for providing a working alternative to `unfold` for local bindings.
@bors
Copy link
Copy Markdown

bors bot commented Aug 24, 2023

Build failed:

  • Build

@kmill
Copy link
Copy Markdown
Contributor Author

kmill commented Aug 24, 2023

bors r+

bors bot pushed a commit that referenced this pull request Aug 24, 2023
…ions (#5717)

This provides a function to create a tactic from any `Expr → MetaM Expr` that maps expresions to defeq expressions. The tactic handles the standard location processing.

Also provides some tactics: `whnf`, `beta_reduce`, `reduce`, `unfold_let`, `unfold_projs`, `eta_reduce`, and `eta_expand`. Some of these (like `whnf`) are more useful in high-level tactic scripts or for exploration than in actual finished proofs. The `unfold_let` tactic is useful for finer-grained zeta reduction (a.k.a. substituting in the values of let-bound hypotheses) and for providing a working alternative to `unfold` for local bindings.
@bors
Copy link
Copy Markdown

bors bot commented Aug 24, 2023

Pull request successfully merged into master.

Build succeeded!

The publicly hosted instance of bors-ng is deprecated and will go away soon.

If you want to self-host your own instance, instructions are here.
For more help, visit the forum.

If you want to switch to GitHub's built-in merge queue, visit their help page.

@bors bors bot changed the title feat: some tactics to transform hypotheses and goals to defeq expressions [Merged by Bors] - feat: some tactics to transform hypotheses and goals to defeq expressions Aug 24, 2023
@bors bors bot closed this Aug 24, 2023
@bors bors bot deleted the kmill_defeq_tactics branch August 24, 2023 16:07
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

delegated This pull request has been delegated to the PR author (or occasionally another non-maintainer). ready-to-merge This PR has been sent to bors. t-meta Tactics, attributes or user commands

Projects

None yet

Development

Successfully merging this pull request may close these issues.

6 participants