Abstract
This paper introduces the metaphorism pattern of relational specification and addresses how specification following this pattern can be refined into recursive programs.
Metaphorisms express input-output relationships which preserve relevant information while at the same time some intended optimization takes place. Text processing, sorting, representation changers, etc., are examples of metaphorisms.
The kind of metaphorism refinement proposed in this paper is a strategy known as change of virtual data structure. It gives sufficient conditions for such implementations to be calculated using relation algebra and illustrates the strategy with the derivation of quicksort as example.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bird, R., de Moor, O.: Algebra of Programming. Series in Computer Science. Prentice-Hall International (1997)
Doornbos, H., Backhouse, R., van der Woude, J.: A calculational approach to mathematical induction. TCS 179(1–2), 103–135 (1997)
Freyd, P.J., Scedrov, A.: Categories, Allegories. Mathematical Library, vol. 39. North-Holland (1990)
Henglein, F.: What is a sorting function? J. Logic and Algebraic Programming (JLAP) 78(5), 381–401 (2009)
Hutton, G., Meijer, E.: Back to basics: Deriving representation changers functionally. Journal of Functional Programming 6(1), 181–188 (1996)
Knuth, D.E.: The Art of Computer Programming, 2nd edn. Addison/Wesley (1997/1998); 3 volumes. First edition’s dates: 1968 (volume 1), 1969 (volume 2) and 1973 (volume 3)
Kozen, D.: Kleene algebra with tests. ACM Trans. Program. Lang. Syst. 19(3), 427–443 (1997)
Lakoff, G., Johnson, M.: Metaphors we live by. University of Chicago Press, Chicago (1980)
Mu, S.-C., Oliveira, J.N.: Programming from Galois connections. JLAP 81(6), 680–704 (2012)
Oliveira, J.N.: Extended Static Checking by Calculation using the Pointfree Transform. In: Bove, A., Barbosa, L.S., Pardo, A., Pinto, J.S. (eds.) LerNet 2008. LNCS, vol. 5520, pp. 195–251. Springer, Heidelberg (2009)
Oliveira, J.N.: On the ‘A’ that links the ‘M’s of maths, music and maps. Contributed talk to the 2013 CEHUM Autumn Colloquium XV(Maths and Comp. Science Panel), U. Minho, Braga, November 21-23 (2013)
Oliveira, J.N.: A relation-algebraic approach to the “Hoare logic” of functional dependencies. JLAP 83(2), 249–262 (2014)
Oliveira, J.N., Ferreira, M.A.: Alloy meets the algebra of programming: A case study. IEEE Trans. Soft. Eng. 39(3), 305–326 (2013)
Richards, I.A.: The Philosophy of Rhetoric. Oxford University Press (1936)
Swierstra, D., de Moor, O.: Virtual data structures. In: Möller, B., Partsch, H., Schuman, S. (eds.) Formal Program Development. LNCS, vol. 755, pp. 355–371. Springer, Heidelberg (1993)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Oliveira, J.N. (2015). Metaphorisms in Programming. In: Kahl, W., Winter, M., Oliveira, J. (eds) Relational and Algebraic Methods in Computer Science. RAMICS 2015. Lecture Notes in Computer Science(), vol 9348. Springer, Cham. https://doi.org/10.1007/978-3-319-24704-5_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-24704-5_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-24703-8
Online ISBN: 978-3-319-24704-5
eBook Packages: Computer ScienceComputer Science (R0)