sys/man/1/forp

   1 .TH FORP 1
   2 .SH NAME
   3 forp \- formula prover
   4 .SH SYNOPSIS
   5 .B forp
   6 [
   7 .B -m
   8 ]
   9 [
  10 .I file
  11 ]
  12 .SH DESCRIPTION
  13 .I Forp
  14 is a tool for proving formulae involving finite-precision arithmetic.
  15 Given a formula it will attempt to find a counterexample; if it can't find one the formula has been proven correct.
  16 .PP
  17 .I Forp
  18 is invoked on an input file with the syntax as defined below.
  19 If no input file is provided, standard input is used instead.
  20 The
  21 .B -m
  22 flag instructs
  23 .I forp
  24 to produce a table of all counterexamples rather than report just one.
  25 Note that counterexamples may report bits as
  26 .BR ? ,
  27 meaning that either value will lead to a counterexample.
  28 .PP
  29 The input file consists of statements terminated by semicolons and comments using C syntax (using
  30 .B //
  31 or
  32 .B "/* */"
  33 syntax).
  34 Valid statements are
  35 .IP
  36 Variable definitions, roughly:
  37 .I type
  38 .I var
  39 .B ;
  40 .br
  41 Expressions (including assignments):
  42 .I expr
  43 .B ;
  44 .br
  45 Assertions:
  46 .B obviously
  47 .I expr
  48 .B ;
  49 .br
  50 Assumptions:
  51 .B assume
  52 .I expr
  53 .B ;
  54 .PP
  55 Assertions are formulae to be proved.
  56 If multiple assertions are given, they are effectively "and"-ed together.
  57 Each input file must have at least one assertion to be valid.
  58 Assumptions are formulae that are assumed, i.e. counterexamples that would violate assumptions are never considered.
  59 Exercise care with them, as contradictory assumptions will lead to any formula being true (the logician's principle of explosion).
  60 .PP
  61 Variables can be defined with C notation, but the only types supported are
  62 .B bit
  63 and 1D arrays of
  64 .B bit
  65 (corresponding to machine integers of the specified size).
  66 Signed integers are indicated with the keyword
  67 .BR signed .
  68 Like
  69 .B int
  70 in C, the
  71 .B bit
  72 keyword can be omitted in the presence of
  73 .BR signed .
  74 For example,
  75 .PP
  76 .EX
  77         bit a, b[4], c[8];
  78         signed bit d[3];
  79         signed e[16];
  80 .EE
  81 .PP
  82 is a set of valid declarations.
  83 .PP
  84 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.
  85 .I Forp
  86 tries to find assignments for all input variables that render the assertions invalid.
  87 .PP
  88 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.
  89 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.
  90 .TP "\w'\fL<\fR, \fL<=\fR, \fL>\fR, \fL>=\fR  'u"
  91 \fL[]\fR
  92 Array indexing. The syntax is \fIvar\fL[\fIidx\fL:\fIn\fR] to address \fIn\fR bits with the least-significant bit at \fIidx\fR.
  93 Omiting \fL:\fIn\fR addresses a single bit.
  94 .TP
  95 \fL!\fR, \fL~\fR, \fL+\fR, \fL-\fR
  96 (Unary operators) Logical and bitwise "not", unary plus (no-op), arithmetic negation. Because of promotion, \fL~\fR and \fL-\fR operate beyond the width of variables.
  97 .TP
  98 \fL*\fR, \fL/\fR, \fL%\fR
  99 Multiplication, division, modulo.
 100 Division and modulo add an assumption that the divisor is non-zero.
 101 .TP
 102 \fL+\fR, \fL-\fR
 103 Addition, subtraction.
 104 .TP
 105 \fL<<\fR, \fL>>\fR
 106 Left shift, arithmetic right shift. Because of promotion, this is effectively a logical right shift on unsigned variables.
 107 .TP
 108 \fL<\fR, \fL<=\fR, \fL>\fR, \fL>=\fR
 109 Less than, less than or equal to, greater than, greather than or equal to.
 110 .TP
 111 \fL==\fR, \fL!=\fR
 112 Equal to, not equal to.
 113 .TP
 114 \fL&\fR
 115 Bitwise "and".
 116 .TP
 117 \fL^\fR
 118 Bitwise "xor".
 119 .TP
 120 \fL|\fR
 121 Bitwise "or".
 122 .TP
 123 \fL&&\fR
 124 Logical "and"
 125 .TP
 126 \fL||\fR
 127 Logical "or".
 128 .TP
 129 \fL<=>\fR, \fL=>\fR
 130 Logical equivalence and logical implication (equivalent to
 131 .B "(a != 0) == (b != 0)"
 132 and
 133 .BR "!a || b" ,
 134 respectively).
 135 .TP
 136 \fL?:\fR
 137 Ternary operator (\fLa?b:c\fR equals \fLb\fR if \fLa\fR is true and \fLc\fR otherwise).
 138 .TP
 139 \fL=\fR
 140 Assignment.
 141 .PP
 142 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.
 143 Note that the values reported as the counterexample are always the values given by the last assignment.
 144 .SH EXAMPLES
 145 We know that, mathematically, \fIa\fR + \fIb\fR ≥ \fIa\fR if \fIb\fR ≥ 0 (which is always true for an unsigned number).
 146 We can ask
 147 .I forp
 148 to prove this using
 149 .PP
 150 .EX
 151         bit a[32], b[32];
 152         obviously a + b >= a;
 153 .EE
 154 .PP
 155 .I Forp
 156 will report "Proved", since it cannot find a counterexample for which this is not true.
 157 In C, on the other hand, we know that this is not necessarily true.
 158 The reason is that, depending on the types involved, results are truncated.
 159 We can emulate this by writing
 160 .PP
 161 .EX
 162         bit a[32], b[32], c[32];
 163         c = a + b;
 164         obviously c >= a;
 165 .EE
 166 .PP
 167 Given this,
 168 .I forp
 169 will now report it as incorrect by providing a counterexample, for example
 170 .PP
 171 .EX
 172         a = 10000000000000000000000000000000
 173         b = 10000000000000000000000000000000
 174         c = 00000000000000000000000000000000
 175 .EE
 176 .PP
 177 Can we use \fIc\fR < \fIa\fR to check for overflow?
 178 We can ask
 179 .I forp
 180 to confirm this using
 181 .PP
 182 .EX
 183         bit a[32], b[32], c[32];
 184         c = a + b;
 185         obviously c < a <=> c != a+b;
 186 .EE
 187 .PP
 188 Here the statement to be proved is "\fIc\fR is less than \fIa\fR if and only if \fIc\fR does not equal the mathematical sum \fIa\fR + \fIb\fR (i.e. overflow has occured)".
 189 .SH SOURCE
 190 .B /sys/src/cmd/forp
 191 .SH "SEE ALSO"
 192 .IR spin (1)
 193 .SH BUGS
 194 Any proof is only as good as the assumptions made, in particular care has to be taken with respect to truncation of intermediate results.
 195 .PP
 196 Array indices must be constants.
 197 .PP
 198 Left shifting can produce a huge number of intermediate bits.
 199 .I Forp
 200 will try to identify the minimum needed number but it may be a good idea to help it by assigning the result of a left shift to a variable.
 201 .SH HISTORY
 202 .I Forp
 203 first appeared in 9front in March, 2018.