Abstract
A fundamental scientific question today is how to construct complex systems from simple parts. Science today seems mostly to analyze limited pieces of the puzzle; the combination of these pieces to form a whole is left for later or others. The lack of efficient methods to deal with the combination problem is likely the main reason. How to combine individual results is a dominant question in cognitive science or geography, where phenomena are studied from individuals and at different scales, but the results cannot be brought together. This paper proposes to use parameterized algebras much the same way that we use functional abstraction (procedures in programming languages) to create abstract building blocks which can be combined later. Algebras group operations (which are functional abstractions) and can be combined to construct more complex algebras. Algebras operate therefore at a higher level of abstraction. A table shows the parallels between procedural abstraction and the abstraction by parameterized algebras. This paper shows how algebras can be combined to form more complex pieces and compares the steps to the combination of procedures in programming. The novel contribution is to parameterize algebras and make them thus ready for reuse. The method is first explained with the familiar construction of vector space and then applied to a larger example, namely the description of geometric operations for GIS, as proposed in the current draft standard document ISO 15046 Part 7: Spatial Schema. It is shown how operations can be grouped, reused, and combined, and useful larger systems built from the pieces. The paper compares the method to combine algebras — which are independent of an implementation — with the current use of object-orientation in programming languages (and in the UML notation often used for specification). The widely used’ structural’ (or subset) polymorphism is justified by implementation considerations, but not appropriate for theory development and abstract specifications for standardization. Parametric polymorphism used for algebras avoids the contravariance of function types (which its semantically confusing consequences). Algebraic methods relate cleanly to the mathematical category theory and the method translates directly to modern functional programming or Java.
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
Abadi, M., and L. Cardelli, A Theory of Objects. Monographs in Computer Science. Springer-Verlag, New York (1996).
Asperti, A., and G. Longo, Categories, Types and Structures-An Introduction to Category Theory for the Working Computer Scientist. The MIT Press, Cambridge, MA (1991).
Barr, M., and C. Wells, Category Theory for Computing Science. Prentice Hall, London (1990).
Bird, R., and O. de Moore, Algebra of Programming. Prentice Hall, London (1997)
Birkhoff, G., and J.D. Lipson, Heterogeneous Algebras. Journal of Combinatorial Theory (1970) 8: 115–133.
Booch, G., J. Rumbaugh, and I. Jacobson, Unified Modeling Language Semantics and Notation Guide 1.0. Rational Software Corporation, San Jose, CA (1997).
Buehler, K. and L. McKee. (eds), The OpenGIS Guide-An Introduction to Interoperable Geoprocessing. The OGIS Project Technical Committee of the Open GIS Consortium, Wayland, MA (1996).
Ehrich, H.-D., M. Gogolla, and U.W. Lipeck, Algebraische Spezifikation abstrakter Datentypen. (DeLeitföden und Monographien der Informatik), H.-J. Appelrath, et al. (eds). B.G. Teubner, Stuttgart (1989).
Frank, A.U., Formal Models for Cognition-Taxonomy of Spatial Location Description and Frames of Reference. In Spatial Cognition-An Interdisciplinary Approach to Representing and Processing Spatial Knowledge, C. Freksa, C. Habel, and K.F. Wender (eds). Springer-Verlag, Berlin (1998) 293–312.
Frank, A.U., and W. Kuhn, Cell Graph: A Provable Correct Method for the Storage of Geometry. In Second International Symposium on Spatial Data Handling, Seattle, WA, 1986, 411–436.
Frank, A.U., and W. Kuhn, A Specification Language for Interoperable GIS. In Interoperating Geographic Information Systems, M.F. Goodchild, et al. (eds). Kluwer, Norwell, MA (1998).
Frank, A.U., and W. Kuhn, Specifying Open GIS with Functional Languages. In Advances in Spatial Databases (4th Int. Symposium on Large Spatial Databases, SSD’95, in Portland, USA), M.J. Egenhofer and J.R. Herring, (eds). 1995, Springer-Verlag, 184–195.
Guttag, J.V. and J.J. Horning, Larch: Languages and Tools for Formal Specification. Springer-Verlag (1993).
Herring, J., M.J. Egenhofer, and A.U. Frank, Using Category Theory to Model GIS Applications. In 4th International Symposium on Spatial Data Handling, SDH’90, Zurich, Switzerland, 1990, 820–829.
ISO, The EXPRESS Language Reference Manual, ISO TC 184, Technical Report ISO/DIS 10303–11 (1992).
Jones, M.P., Qualified Types: Theory and Practice. Ph.D. Thesis, Programming Research Group, Oxford University. Cambridge University Press (1994).
Levinson, S.C., Frames of Reference and Molyneux’s Question: Crosslinguistic Evidence. In Language and Space, P. Bloom, et al. (eds), MIT Press, Cambridge, MA. (1996) 109–170.
Lin, F.-T., Many Sorted Algebraic Data Models for GIS. IJGIS (1998) 12(8) 765–788.
Loeckx, J., H.-D. Ehrich, and M. Wolf, Specification of Abstract Data Types. Wiley, Teubner (1996).
Peterson, J., et al., Report on the functional programming language Haskell, Version 1.3. In http://haskell.cs.yale.edu/haskell-report/haskell-report.html-Research Report YALEU/-DCS/RR-1106. Yale University (1996).
Reinhardt, F. and H. Soeder, dtv-Atlas zur Mathematik: Grundlagen, Algebra und Geometrie (Band 1). Dtv, Muenchen (1991).
Stroustrup, B., The C++ Programming Language. 2nd edn. Addison-Wesley, Reading, MA (1991).
Walters, R.F.C., Categories and Computer Science. Cambridge Computer Science Texts, Vol. 1. Carslaw Publications, Cambridge, UK (1991).
Wirth, N., Algorithms + Data Structures = Programs. Prentice Hall, Englewood Cliffs, NJ (1976).
Yeh, R.T.-Y. and P.A.B. Ng, Modern Software Engineering: Foundations and Current Perspectives. Van Nostrand Reinhold, New York (1990).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Frank, A.U. (1999). One Step up the Abstraction Ladder: Combining Algebras - From Functional Pieces to a Whole. In: Freksa, C., Mark, D.M. (eds) Spatial Information Theory. Cognitive and Computational Foundations of Geographic Information Science. COSIT 1999. Lecture Notes in Computer Science, vol 1661. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48384-5_7
Download citation
DOI: https://doi.org/10.1007/3-540-48384-5_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66365-2
Online ISBN: 978-3-540-48384-7
eBook Packages: Springer Book Archive