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

Incomplete reasoning about exponentiation: 2^^h + 2^^h - 2^^h does not always simplify to 2^^h #1812

Open
RyanGlScott opened this issue Feb 24, 2025 · 0 comments · May be fixed by #1824
Open
Assignees
Labels
feature request Asking for new or improved functionality typechecker Issues related to type-checking Cryptol code.

Comments

@RyanGlScott
Copy link
Contributor

Consider:

// See if Cryptol knows that 2^^h + (2^^h - 2^^h) == 2^^h

f : {h} (fin h) => [2^^h + (2^^h - 2^^h)]
f = g`{h}

g : {h} (fin h) => [2^^h]
g = zero

// See if Cryptol knows that (2^^h + 2^^h) - 2^^h == 2^^h

ff : {h} (fin h) => [(2^^h + 2^^h) - 2^^h]
ff = gg`{h}

gg : {h} (fin h) => [2^^h]
gg = zero

This is seeing if Cryptol can successfully conclude that 2^^h + 2^^h - 2^^h == 2^^h with different groupings of the (+) operator. Surprisingly, Cryptol succeeds in the first case (2^^h + (2^^h - 2^^h) == 2^^h), but fails in the second case ((2^^h + 2^^h) - 2^^h == 2^^h):

[error] at Bug.cry:12:1--12:12:
  Failed to validate user-specified signature.
    in the definition of 'Main::ff', at Bug.cry:12:1--12:3,
    we need to show that
      for any type h
      assuming
        • fin h
      the following constraints hold:
        • 2 ^^ (1 + h) - 2 ^^ h == 2 ^^ h
            arising from
            matching types
            at Bug.cry:12:6--12:8

Normally, Cryptol's typechecker has no problem concluding that (x + x) - x == x. As the error message above indicates, however, I think Cryptol's typechecker is getting confused because it first rewrites (2^^h + 2^^h) to 2 ^^ (1 + h), which imperils the typechecker's ability to cancel out 2^^h terms.

@RyanGlScott RyanGlScott added bug Something not working correctly typechecker Issues related to type-checking Cryptol code. labels Feb 24, 2025
@yav yav added feature request Asking for new or improved functionality and removed bug Something not working correctly labels Feb 24, 2025
danmatichuk added a commit that referenced this issue Mar 7, 2025
this allows for the subtraction cancellation rule
to still apply after some exponent simplification
steps have already occurred

fixes #1812
@danmatichuk danmatichuk self-assigned this Mar 7, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
feature request Asking for new or improved functionality typechecker Issues related to type-checking Cryptol code.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants