Abstract
The refinement calculus is a well-established theory for formal development of imperative program code and is supported by a number of automated tools. Via a detailed case study, this article shows how refinement theory and tool support can be extended for a program with real-time constraints. The approach adapts a timed variant of the refinement calculus and makes corresponding enhancements to a theorem-prover based refinement tool.
Similar content being viewed by others
References
Abadi, M, Lamport, L.: An old-fashioned recipe for real time. ACM Transactions on Programming Language and Systems, 16(5), 1543–1571, September 1994
Back, R.-J., von Wright, J.: Refinement Calculus: A Systematic Introduction. Springer-Verlag, 1998
Bicarregui, J.C. et al.: Formal methods in practice: Case studies in the application of the B method. IEE Proceedings — Software Engineering, 144(2), 119–133, April 1997
Butler, M., Grundy, J., Långbacka, T., Ruks̆ėnas, R., von Wright, J.: The refinement calculator: Proof support for program refinement. In Groves, L, Reeves, S., editors, Formal Methods Pacific ’97, Springer, 1997, pp. 40–61
Carrington, D., Hayes, I., Nickson, R., Watson, G., Welsh, J.: A program refinement tool. Formal Aspects of Computing, 10(2), 97–124 (1998)
Davies, J, Schneider, S.: A brief history of Timed CSP. Theoretical Computer Science, 138(2), 243–271, February 1995
Fidge, C.J., Hayes, I.J., Watson, G.: The deadline command. IEE Proceedings—Software, 146(2), 104–111, April 1999. Special Issue on Real-Time Systems
Grundon, S., Hayes, I.J., Fidge, C.J.: Timing constraint analysis. In McDonald, C., editor, Computer Science ’98: Proc. 21st Australasian Computer Science Conference, Springer-Verlag, 1998, pp. 575–586
Hayes, I.J.: Separating timing and calculation in real-time refinement. In Grundy, J., Schwenke, M., Vickers, T., editors, International Refinement Workshop & Formal Methods Pacific ’98, Discrete Mathematics and Theoretical Computer Science, Springer-Verlag, 1998, pp. 1–16
Hayes, I.J, Utting, M.: Coercing real-time refinement: A transmitter. In Duke, D.J, Evans, A.S., editors, BCS-FACS Northern Formal Methods Workshop, 1996, Electronic Workshops in Computing. Springer-Verlag, 1997. http://www.ewic.org.uk/ewic/
Hayes, I.J, Utting, M.: Deadlines are termination. In Gries, D., de Roever, W.-P. editors, IFIP International Conference on Programming Concepts and Methods (PROCOMET ’98), Chapman and Hall, 1998, pp. 186–204
Hooman, J.: Assertional specification and verification. In Joseph, M., editor, Real-Time Systems: Specification, Verification and Analysis, chapter 5, Prentice-Hall, 1996, pp. 97–146
Mahony, B.P.: The refinement calculus and data-flow processes. In Proc. Second Australasian Refinement Workshop, Brisbane, September 1992, pp. 1–28
Mahony, B.P.: The Specification and Refinement of Timed Processes. PhD thesis, Department of Computer Science, University of Queensland, 1992
Mahony, B.P, Hayes, I.J.: A case study in timed refinement: A mine pump. IEEE Transactions on Software Engineering, 18(9), 817–826, September 1992
Morgan, C.: Programming from Specifications. Prentice-Hall, second edition, 1994
Nickson, R, Hayes, I.J.: Supporting contexts in program refinement. Science of Computer Programming, 29(3), 279–302 (1997)
Schenke, M.: Transformational design of real-time systems. part II: From program specifications to programs. Acta Informatica, 36, 67–96, January 1999
Schenke, M, Olderog, E.-R.: Transformational design of realtime systems. Part I: From requirements to program specifications. Acta Informatica, 36, 1–65, January 1999
Scholefield, D., Zedan, H., Jifeng, H.: A specification-oriented semantics for the refinement of real-time systems. Theoretical Computer Science, 131, 219–241 (1994)
Skakkebæk. J.U.: A Verification Assistant for a Real-Time Logic. PhD thesis, Department of Computer Science, Technical University of Denmark, November 1994. ID-TR 1994-150
Toyn, I, McDermid, J.A.: CADiZ: An architecture for Z tools and its implementation. Software—Practice & Experience, 25(3), 305–330, March 1995
Utting, M, Fidge, C.J.: A real-time refinement calculus that changes only time. In Jifeng, H., Cooke, J., Wallis, P., editors, BCS-FACS Seventh Refinement Workshop, Electronic Workshops in Computing. Springer-Verlag, 1996. http://www.ewic.org.uk/ewic/
Utting, M, Fidge, C.J.: Refinement of infeasible real-time programs. In Groves, L, Reeves, S., editors, Formal Methods Pacific ’97, Springer-Verlag, 1997, pp. 243-262
Vickers, T.: An overview of a refinement editor. In Proceedings of the Fifth Australian Software Engineering Conference (ASWEC’90), 1990, pp. 39–44
Wabenhorst, A.: A model of real-time distributed systems. In Gries, D., de Roever, W.-P., editors, IFIP International Conference on Programming Concepts and Methods (PROCOMET’98), Chapman and Hall, 1998, pp. 462–481
Wildman, L, Hayes, I.: Supporting contexts in the sequential real-time refinement calculus. In Grundy, J., Schwenke, M., Vickers, T., editors, International Refinement Workshop & Formal Methods Pacific ’98, Discrete Mathematics and Theoretical Computer Science, Springer-Verlag, 1998, pp. 352–369
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Wildman, L., Fidge, C. & Carrington, D. Computer-aided development of a real-time program. Software - Concepts & Tools 19, 190–202 (2000). https://doi.org/10.1007/s003780000006
Published:
Issue Date:
DOI: https://doi.org/10.1007/s003780000006