Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Generate rewrite relation #4745

Open
wants to merge 16 commits into
base: develop
Choose a base branch
from
Open

Generate rewrite relation #4745

wants to merge 16 commits into from

Conversation

tothtamas28
Copy link
Contributor

Closes #4728

Generates an inductive type Rewrites : GeneratedTopCell -> GeneratedTopCell -> Prop where each constructor (except for the first one which expresses transitivity) encodes a K rewrite rule.

Each constructor has the following signature:

  • An implicit binder for each free variable.
  • An explicit binder for each function application which expresses definedness of the function over the arguments.
  • An explicit binder for the requires clause.
  • The type Rewrites <lhs> <rhs>.

@rv-jenkins rv-jenkins changed the base branch from master to develop January 22, 2025 16:19
@tothtamas28 tothtamas28 force-pushed the rewrite-relation branch 3 times, most recently from b2c798c to ea1e82e Compare January 24, 2025 10:51
@tothtamas28 tothtamas28 changed the base branch from develop to update-deps January 24, 2025 10:51
@tothtamas28 tothtamas28 changed the base branch from update-deps to develop January 24, 2025 10:51
@tothtamas28
Copy link
Contributor Author

The Rewrites type definition generated for evm-semantics.llvm compiles in about 20 mins (after imports, patching ite and setting set_option maxHeartbeats 10000000).

Rewrite.txt

@tothtamas28 tothtamas28 self-assigned this Jan 24, 2025
@tothtamas28 tothtamas28 requested a review from JuanCoRo January 24, 2025 11:35
@tothtamas28 tothtamas28 marked this pull request as ready for review January 24, 2025 11:35
@JuanCoRo
Copy link
Member

Where do the names of rewrite rules such as _43a65b8 come from?

@JuanCoRo
Copy link
Member

Where do the names of rewrite rules such as _43a65b8 come from?

I guess from unnamed rules. But maybe it's better to have something like ruleN where N is the counter of how many rules there are. Otherwise proving things with this can get more convoluted.

A related question: Even if we named all rules in K definitions, will there be generated rules by the compiler that we cannot name?

@tothtamas28
Copy link
Contributor Author

tothtamas28 commented Jan 24, 2025

Where do the names of rewrite rules such as _43a65b8 come from?

It's a prefix of the UNIQUE-ID generated by the frontend for each rule.

But maybe it's better to have something like ruleN where N is the counter of how many rules there are.

I can make that change, but that'll make it significantly harder to manually trace back and forth between K and Lean source. Right now you can look up the source and UNIQUE-ID attributes from compiled.txt or definition.kore, which provides the mapping. And it's easier to search for a unique string in those files then to navigate to the n-th match of a regex identifying rule axioms.

A related question: Even if we named all rules in K definitions, will there be generated rules by the compiler that we cannot name?

The only frontend-generated rules I can think of are heating-cooling rules, but they seem to have a label. Still, it's possible there are unlabeled generated rules.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Generate rewrite rules
2 participants