3 ms·
Basically yes. The question is what exactly it buys you. In general, the proving power of Haskell's type system is that of a finite-state-machine/regular expres
by pron 11y ago
Basically yes. The question is what exactly it buys you. In general, the proving power of Haskell's type system is that of a finite-state-machine/regular expression (i.e. you can verify behavior of an FSM), and the proving power of Idris is that of a full Turing Machine, but in general we know that verifying a program property has a lower complexity bound of Ω(# of program states), i.e. exponential in the size of the source code, regardless of the language used (actually, the more expressive the language, the harder the problem becomes, but just by a bit). The question is, then, given that all approaches are bound by the same complexity bounds for complete proof, which approach is cheaper in practice based on property type, program type and required confidence? Sadly, we don't have the answer to that question, but answering it would require some expensive empirical studies.