forp – formula prover
The input file consists of statements terminated by semicolons and comments using C syntax (using
Variable definitions, roughly:
Expressions (including assignments):
Assertions are formulae to be proved. If multiple assertions are given, they are effectively "and"-ed together. Each input file must have at least one assertion to be valid. Assumptions are formulae that are assumed, i.e. counterexamples that would violate assumptions are never considered. Exercise care with them, as contradictory assumptions will lead to any formula being true (the logician’s principle of explosion).
Variables can be defined with C notation, but the only types supported are
bit a, b, c; signed bit d; signed e;
is a set of valid declarations.
Unlike a programming language, it is perfectly legitimate to use a variable before it is assigned value; this means the variable is an "input" variable.
Expressions can be formed just as in C, however when used in an expression, all variables are automatically promoted to an infinite size signed type. The valid operators are listed below, in decreasing precedence. Note that logical operations treat all non-zero values as 1, whereas bitwise operators operate on all bits independently.
Array indexing. The syntax is var[idx:n] to address n bits with the least-significant bit at idx. Omiting :n addresses a single bit.
(Unary operators) Logical and bitwise "not", unary plus (no-op), arithmetic negation. Because of promotion, ~ and - operate beyond the width of variables.
Multiplication, division, modulo. Division and modulo add an assumption that the divisor is non-zero.
Left shift, arithmetic right shift. Because of promotion, this is effectively a logical right shift on unsigned variables.
Less than, less than or equal to, greater than, greather than or equal to.
Equal to, not equal to.
Logical equivalence and logical implication (equivalent to
Ternary operator (a?b:c equals b if a is true and c otherwise).
One subtle point concerning assignments is that they forcibly override any previous values, i.e. expressions use the value of the latest assignments preceding them. Note that the values reported as the counterexample are always the values given by the last assignment.
We know that, mathematically, a + b ≥ a if b ≥ 0 (which is always true for an unsigned number).
We can ask
bit a, b; obviously a + b >= a;
bit a, b, c; c = a + b; obviously c >= a;
a = 10000000000000000000000000000000 b = 10000000000000000000000000000000 c = 00000000000000000000000000000000
Can we use c < a to check for overflow?
We can ask
bit a, b, c; c = a + b; obviously c < a <=> c != a+b;
Here the statement to be proved is "c is less than a if and only if c does not equal the mathematical sum a + b (i.e. overflow has occured)".
Any proof is only as good as the assumptions made, in particular care has to be taken with respect to truncation of intermediate results.
Array indices must be constants.
Left shifting can produce a huge number of intermediate bits.