Abstract
Four well-known methods for presenting semantics of a programming language are: denotational, deductive, operational, and algebraic. This essay presents algebraic laws for the structural features of a class of imperative programming languages which provide both sequential and concurrent composition; and it illustrates the way in which the laws are consistent with the other three semantic presentations of the same language. The exposition combines simplicity with generality by postponing consideration of the possibly more complex basic commands of particular programming languages. The proofs are given only as hints, but they are easily reconstructed, even with the aid of a machine.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Stoy, J.E.: Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory. MIT Press (1977)
Hoare, C.A.R.: An axiomatic basis for computer programming. Communications of the ACM 12(10), 576–580 (1969)
O’Hearn, P.W.: Resources, concurrency and local reasoning. In: Gardner, P., Yoshida, N. (eds.) CONCUR 2004. LNCS, vol. 3170, pp. 49–67. Springer, Heidelberg (2004)
Plotkin, G.D.: A structural approach to operational semantics. Technical Report DAIMI FN-19, Aarhus University (1981)
Milner, R.: A Calculus of Communication Systems. LNCS, vol. 92. Springer, Heidelberg (1980)
Hennessy, M.: Algebraic Theory of Processes. MIT Press (1988)
Baeten, J., Basten, T., Reniers, M.A.: Process Algebra: Equational Theories of Communicating Processes. Cambridge Tracts in Theoretical Computer Science, vol. 50. Cambridge University Press (2009)
Dijkstra, E.W.: A Discipline of Programming. Prentice Hall, Englewood Cliffs (1976)
Back, R.J., Wright, J.: Refinement calculus: a systematic introduction. Springer (1998)
Morgan, C.: Programming from specifications. Prentice-Hall, Inc. (1990)
Pratt, V.R.: Action logic and pure induction. In: van Eijck, J. (ed.) JELIA 1990. LNCS, vol. 478, pp. 97–120. Springer, Heidelberg (1991)
Hoare, C.A.R., Hayes, I.J., He, J., Morgan, C., Roscoe, A.W., Sanders, J.W., Sørensen, I.H., Spivey, J.M., Sufrin, B.: Laws of programming. Commun. ACM 30(8), 672–686 (1987)
Hoare, C.A.R., Jifeng, H.: Unifying Theories of Programming. Prentice Hall (1998)
Wehrman, I., Hoare, C.A.R., O’Hearn, P.W.: Graphical models of separation logic. Inf. Process. Lett. 109(17), 1001–1004 (2009)
Hoare, T., Wickerson, J.: Unifying models of data flow. In: Software and Systems Safety - Specification and Verification, pp. 211–230 (2011)
Hoare, C.A.R., Hussain, A., Möller, B., O’Hearn, P.W., Petersen, R.L., Struth, G.: On locality and the exchange law for concurrent processes. In: Katoen, J.-P., König, B. (eds.) CONCUR 2011. LNCS, vol. 6901, pp. 250–264. Springer, Heidelberg (2011)
Hoare, T., Möller, B., Struth, G., Wehrman, I.: Concurrent Kleene algebra and its foundations. J. Log. Algebr. Program. 80(6), 266–296 (2011)
Hoare, T., van Staden, S.: The laws of programming unify process calculi. In: Gibbons, J., Nogueira, P. (eds.) MPC 2012. LNCS, vol. 7342, pp. 7–22. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Hoare, T. (2013). Unifying Semantics for Concurrent Programming. In: Coecke, B., Ong, L., Panangaden, P. (eds) Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky. Lecture Notes in Computer Science, vol 7860. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38164-5_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-38164-5_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38163-8
Online ISBN: 978-3-642-38164-5
eBook Packages: Computer ScienceComputer Science (R0)