top | item 31520369

(no title)

mvh | 3 years ago

Why would you even consider using an unsound logic?

I’m a 3rd year PhD student in formal verification and for the life of me I can’t imagine why anyone would choose to use an unsound logic. I must be missing something very obvious. Is it, IDK, “sound as long as you don’t reason about some very specific kind of formula which can be easily avoided”, or something like that?

discuss

order

gnulinux|3 years ago

The usual justification, within PL Design community is that, similar to Russell 's Paradox, it's said that the anomaly caused by the unsound logic does not come up in practical situations. For example, some (and definitely most if not all mainstream) languages admit `Type: Type` i.e. `Type` itself is a type within the formalism. Of course, this is unsound and one common work-around is to use universe polymorphism such as `Type n: Type (level-suc n)`. But this comes with its own design issues as now you may need to pass level to each type (depends on the language, situation etc). So, some decide, since (as per this reasoning) absurd situations implied by "Type: Type" don't come up in practical situations, it's better have a simpler and more understandable yet unsound Type Theory. (But of course, an inconsistent theory can prove any claim, which is a huge problem in and of itself)

I have to note that I personally do not agree with this reasoning, yet afaik this is one of the justifications used to introduce rules to TT of a PL that is known to be unsound.

Realistically, it all depends on what you want to do with the type system. If you want to have a general purpose programming language that is not restricted by logical technicalities not well-understood by programmers, maybe it's better to admit "Type: Type" or similar. If you want to have a dependently typed programming language where any runtime program can potentially be a compile-time program, you may need more guarantees (e.g. you may need to know certain functions will halt).

ivanbakel|3 years ago

Because, as that quoted sentence points out, the logic itself is simpler and the creators think that makes it easier to use for teaching.

Taken to an extreme, if all you want to show off is how proofs are constructed, then whether or not your logic is actually sound doesn't matter. Since the goal of the tool isn't correct proofs, the proofs don't need to have any soundness properties.

practal|3 years ago

When you create a new logic with certain applications in mind, it might be unsound at some intermediate steps, like you can have bugs in a program. But yeah, I don't think there is much use for an unsound logic per se.