4 ms·
> Specialisation involves a deep commitment to a narrow selection of presentation, reasoning methods, paradigm, language and application area, or even a particu
by pron 11y ago
> Specialisation involves a deep commitment to a narrow selection of presentation, reasoning methods, paradigm, language and application area, or even a particular application. The whole point of the specialisation in formal methods is to restrict the notational framework as far as necessary to achieve some formal goal, but nevertheless to show that the restrictions do not prevent successful application to a surprisingly wide range of problems. This is the reason why specialist research into formal methods can run the risk of being very divisive. An individual researcher, or even a whole community of researchers, becomes wholly committed to a particular selection of specialisations along each of the axes: say an operational or an algebraic presentation of semantics, bisimulation or term rewriting as a proof method, … The attraction of such a choice can be well illustrated in certain applications, such as the analysis of the alternating bit protocol or the definition of the stack as an abstract data type. The perfectly proper challenge of the research is to push outwards as far as possible the frontiers of the convenient application of the particular chosen formalism. But that is also the danger: the rush to colonise as much of the available territory can lead to imperialist claims that deny to other specialisms their right to existence. Any suggestion of variation of standard dogma is treated as akin to treason. This tendency can be reinforced by the short-sightedness of funding agencies which encourage exaggerated claims to the universal superiority of a single notation and technique.
> The consequences of the fragmentation of research into rival schools is inevitable: the theorists become more and more isolated, both from each other and from the world of practice, where one thing is absolutely certain: that there is no single cure for all diseases. There is no single theory for all stages of the development of the software, or for all components even of a single application program. Ideas, concepts, methods, and calculations will have to be drawn from a wide range of theories, and they are going to have to work together consistently, with no risk of misunderstanding, inconsistency or error creeping in at the interfaces. One effective way to break formal barriers is for the best theorists to migrate regularly between the research schools, in the hope that results obtained in one research specialisation can be made useful in a manner acceptable by the other. The interworking of theories and paradigms can also be explored from the practical end by means of the case study, chosen as a simplified version of some typical application. In my view, a case study that constructs a link between two or more theories, used for different purposes at different levels of abstraction, will be more valuable than one which merely presents a single formalisation, in the hope that its merits, compared with rival formalisations, will be obvious. They usually are, but unfortunately only to the author.
- lmm 11y ago> There is no single theory for all stages of the development of the software, or for all components even of a single application program. Ideas, concepts, methods, and calculations will have to be drawn from a wide range of theories, and they are going to have to work together consistently, with no risk of misunderstanding, inconsistency or error creeping in at the interfaces. I'm not convinced. I remain hopeful that one or other technique will show itself adequate for complete coverage of real-world programs. Compare programming languages - naïvely one would think different languages have different specializations and it's important for programmers to be fluent in a wide variety of them and good at interfacing between different languages. But I'm increasingly coming to believe that good general-purpose languages are possible and that better systems are built in a single language, by programmers specialized to that language.
- pron 11y agoAh, but there's a difference between formal verification and programming languages. The problem of general formal verification (known in general as the model-checking problem[1], regardless of the approach used which could be model-theoretic or proof-theoretic) is literally the hardest problem in all of computer science. Any computational problem can be reduced in polynomial time to program verification (i.e. model checking). In fact, all NP-complete and PSPACE-complete problems are trivially reduced. Finding a general tractable solution (even if it includes human intelligence) is therefore a mathematical impossibility. The best we hope for is a solution that is applicable to programs people write. The question is then whether there is one well defined "class" of programs humans write to which an efficient algorithm (again -- even one involving humans in the loop) applies. So far results from decades of verification research show that this is not the case, and there are at least several such classes, but maybe the classes aren't general enough. If humans are part of the algorithm (e.g. interactive proofs, manual dependent types), the class might be wide, but our experience has shown that verifying programs in this way takes tremendous effort, even for small programs, and even when the programs are kept especially simple for the sake of verification. Even if there is a solution that is applicable to most (I'll settle for most) programs, it is so far nowhere in sight. Most efforts are directed at finding partial solutions for specific domains. [1]: Called that because it is the problem of checking whether a given program is a satisfying theory -- i.e. a model -- for the given logical property.