12

First some terminology (borrowed from here, page 14):

A positive program is a program with an error.

A negative program is a program without an error.


So there are four types of programs:

A positive program, analysed as positive -> true positive (TP).

A positive program, analysed as negative -> false negative (FN).

A negative program, analysed as positive -> false positive (FP).

A negative program, analysed as negative -> true negative (TN).


A system is sound, if it never accepts a positive program.

A system is complete, if it never rejects a negative program.


So judging by what I wrote above:
A complete system accepts FN and TN programs.
A sound system also accepts FN and TN programs.

A colleague told me sound systems also accept FP programs. Can someone confirm this and explain why they do?

0

1 Answer 1

26

The book explains it like this:

Soundness prevents false negatives and completeness prevents false positives.

So in order for the system to be sound, it need not prevent false positives, but only false negatives. To prevent false positives, it must be complete.

The book explains it further by using type systems as an example:

In modern languages, type systems are sound (they prevent what they claim to) but not complete (they reject programs they need not reject). Soundness is important because it lets language users and language implementers rely on X never happening. Completeness would be nice, but hopefully it is rare in practice that a program is rejected unnecessarily and in those cases, hopefully it is easy for the programmer to modify the program such that it type-checks.

Type systems are not complete because for almost anything you might like to check statically, it is impossible to implement a static checker that given any program in your language (a) always terminates, (b) is sound, and (c) is complete. Since we have to give up one, (c) seems like the best option (programmers do not like compilers that may not terminate).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.