3 ms·
> My conclusion every time was that the code itself is the formal spec and the formal spec is the code. Yes you can end up with tautological specs, where it's
by IshKebab 2y ago
> My conclusion every time was that the code itself is the formal spec and the formal spec is the code.
Yes you can end up with tautological specs, where it's more or less a copy of the code. E.g. you aren't going to benefit much from formally verifying `max()`.
But there are many many cases where the formal specification is much much simpler and more obviously correct than the actual code. The classic examples are:
* Any kind of encoding / decoding transformation has the property `decode(encode(x)) == x`.
* Sorting: any sorting algorithm should result in a sorted array (forall i, j: i < j --> array[i] <= array[j])
- ngruhn 2y agoI also think universal quantifiers ("for all ...") are a key distinguishing feature of specs. For example, a spec for a shortest path algorithm can be much simpler than any actual algorithm, largely because we can quantify over all (potentially infinitely many) paths: FORALL paths P from A to B: |shortestPath(A,B)| <= |P|