FORP(1)FORP(1)

## NAME

forp – formula prover

## SYNOPSIS

`forp``-m`*file*

## DESCRIPTION

*Forp*

*Forp*`-m`*forp*`?`,

The input file consists of statements terminated by semicolons and comments using C syntax (using
`//``/* */ `

Variable definitions, roughly:
*type**var*`;`

Expressions (including assignments):
*expr*`;`

Assertions:
`obviously`*expr*`;`

Assumptions:
`assume`*expr*`;`

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``bit``signed`.`int``bit``signed`.

bit a, b[4], c[8]; signed bit d[3]; signed e[16];

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.
*Forp*

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`

`:`] to address

*n**n*bits with the least-significant bit at

*idx*. Omiting

`:`addresses a single bit.

*n*`!`,

`~`,

`+`,

`-`

(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.

`+`,

`-`

Addition, subtraction.

`<<`,

`>>`

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.

`&`

Bitwise "and".

`^`

Bitwise "xor".

`|`

Bitwise "or".

`&&`

Logical "and"

`||`

Logical "or".

`<=>`,

`=>`

Logical equivalence and logical implication (equivalent to
`(a != 0) == (b != 0) ``!a || b` ,

`?:`

Ternary operator (`a?b:c` equals `b` if `a` is true and `c` otherwise).

`=`

Assignment.

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.

## EXAMPLES

We know that, mathematically, *a* + *b* ≥ *a* if *b* ≥ 0 (which is always true for an unsigned number).
We can ask
*forp*

bit a[32], b[32]; obviously a + b >= a;

*Forp*

bit a[32], b[32], c[32]; c = a + b; obviously c >= a;

Given this,
*forp*

a = 10000000000000000000000000000000 b = 10000000000000000000000000000000 c = 00000000000000000000000000000000

Can we use *c* < *a* to check for overflow?
We can ask
*forp*

bit a[32], b[32], c[32]; 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)".

## SOURCE

`/sys/src/cmd/forp`

## SEE ALSO

## BUGS

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.
*Forp*

## HISTORY

*Forp*