Skip to content

Example of a formal DSL

The Joy of Coding

Communications of the ACM, August 2001 Volume 44, Number 8, p 12-13.

Henry Liebermann and Christopher Fry (“Will Software Ever Work,” CACM, Mar. 2001, p. 122) suggest users ought to be able to fix software bugs. Although they only hint at a possible mechanism, implying artificial intelligence, they do not give details. One suggestion they make is to provide a better coding language, as C and C++ are not suitable for debugging, at least by users.

We believe no new language for coding can ever provide the desired results. On the contrary users should rarely write or interact with code. Most of the problems in large-scale software arise from the impenetrability of the code, particularly, the control flow of that code. Real-world problems have to take account of all the errors that may be encountered, so software for seemingly simple tasks becomes complex and eventually unmanageable.

For more than 10 years, an alternative software design approach (F. Wagner, “VFSM Executable Specification” In Proceedings of the IEEE International Conference on Computer Systems and Software Engineering,” 1992) has been used, in a wide variety of projects. It formalizes the control flow into a hierarchy of finite state machines and isolates all numerical calculations (including input-output routines) into separate, small, easily tested code modules. The control flow is prepared in a formal manner, by means of state-transition tables that can call on numerical or other procedures on entry to or on exit from, each state. This control flow specification is then transformed into a special format, but “code” is not generated; the specification is interpreted by a runtime “executor” program, which in a sense understands the specification and fulfills the intentions of the system designer.

The latest versions of this technology include a real-time database that facilitates the communications between many state machines, supports distributed systems, and formalizes access to input-output services, even for the most complex control-system applications.

When these techniques are fully supported, they turn software development into something resembling engineering design. Such software can be developed by engineers in close touch with the needs of the user, perhaps even by the users themselves. Although some conventional coding is still required, it does not require the high level of skill needed for conventional methods. When, perhaps in the testing phase, users need to change the operation of a part of the system, they are obliged to alter the formal specification and can make changes with a high degree of confidence. Typically, when a large project is implemented this way, up to three months of bug hunting is replaced by about a week of tuning-up.

These techniques have been applied to semiconductor production lines, complex measuring instruments, and in telecommunications (A.R. Flora-Holmquist et al., “The Virtual State-Machine Design and Implementation Paradigm” Bell Labs Technical Journal, Winter 1997). We assert they ought to be used in all cases where human safety is an issue. Their foundation - the executor program module - has never had to be altered in its 12 years of use.

The resulting software is very reliable in use and needs little maintenance. A number of available products can generate code from a formal specification in state-diagram or transition table format, but we believe such products do not provide a really good solution. Their users know they will be able to work with the resulting code and therefore do not feel obliged to create a 100% accurate specification at the design stage.

We find it difficult to spread our message, as the academic world, having tried and failed in the past, is convinced what we do is impossible. Moreover, and this may be the real problem, programmers enjoy coding.