Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-21T23:38:07.489Z Has data issue: false hasContentIssue false
  • English
  • Français

A categorical manifesto†

Published online by Cambridge University Press:  04 March 2009

Joseph A. Goguen
Joseph A. Goguen
Affiliation:
Programming Research Group, University of Oxford, SRI International, Menlo Park CA, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper tries to explain why and how category theory is useful in computing science, by giving guidelines for applying seven basic categorical concepts: category, functor, natural transformation, limit, adjoint, colimit and comma category. Some examples, intuition, and references are given for each concept, but completeness is not attempted. Some additional categorical concepts and some suggestions for further research are also mentioned. The paper concludes with some philosophical discussion.

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 1 , Issue 1 , March 1991 , pp. 49 - 67
Copyright
Copyright © Cambridge University Press 1991

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aczel, P. (1988) Non-well-founded Sets. Center for the Study of Language and Information, Stanford University, CSLI Lecture Notes, Vol. 14.Google Scholar
Barr, M. and Wells, C. (1984) Toposes, Triples and Theories, Grundlehren der mathematischen Wissenschafter, Vol. 278, Springer.Google Scholar
Barr, M. and Wells, C. (1988) The formal description of data types using sketches. In: Michael Main, A. Melton, Michael Mislove and D. Schmidt, eds, Mathematical Foundations of Programming Language Semantics. Springer Lecture Notes in Computer Science 298.Google Scholar
Brouwer, L. E. J. (1928) Intuitionistische betrachtungen über den formalismus. Koninklijke Akademie van wetenschappen te Amsterdam, Proc. Section of Sciences 31 374–9 In: From Frege to Gödel, ed. Jean van Heijenort, Harvard University Press, 1967, pp. 490–2Google Scholar
Burstall, R. (1972) An algebraic description of programs with assertions, verification, and simulation. In: Adams, J. Mack, Johnston, John and Stark, Richard, eds, Proc. Conference on Proving Assertions about Programs, Association for Computing Machinery, pp. 7–14CrossRefGoogle Scholar
Burstall, R. and Goguen, J. (1977) Putting theories together to make specifications. In:Reddy, Raj, ed., Proc. Fifth Int. Joint Conf. on Artificial Intelligence, Department of Computer Science, Carnegie-Mellon University, pp. 1045–58Google Scholar
Burstall, R. and Goguen, J. (1980) The semantics of Clear, a specification language. In: Dines Bjorner, ed., Proc. 1979 Copenhagen Winter School on Abstract Software Specification, Springer Lecture Notes in Computer Science 86 pp. 292–332 Based on unpublished notes handed out at the Symposium on Algebra and Applications, Stefan Banach Center, Warsaw, Poland.Google Scholar
Curien, P.-L. (1986) Categorical Combinators, Sequential Algorithms, and Functional Programming, Pitman and Wiley. Research Notes in Theoretical Computer Science.Google Scholar
Ehrich, H.-D. (1982) On the theory of specification, implementation and parameterization of abstract data types. J. Assoc. Comput. Mach. 29 206–27CrossRefGoogle Scholar
Ehrig, H. (1979) Introduction to the algebraic theory of graph grammars. In: V. Claus, Hartmut Ehrig and Gregor Rozenberg, eds, Graph Gramars and their Application to Computer Science and Biology, Springer Lecture Notes in Computer Science 73 pp. 1–69Google Scholar
Eilenberg, S. and MacLane, S. (1945) General theory of natural equivalences. Trans. Amer. Math. Soc. 58 231–94CrossRefGoogle Scholar
Ferrari, G. L. (1990) Unifying models of concurrency. PhD thesis, University of Pisa.Google Scholar
Futatsugi, K.Goguen, J.Jouannaud, J.-P. and Meseguer, J. (1985) Principles of OBJ2. In:Reid, Brian, ed., Proc. Twelfth ACM Symp. on Principles of Programming Languages, Association for Computing Machinery, pp. 52–66Google Scholar
Futatsugi, K.Goguen, J.Meseguer, J. and Okada, K. (1987) Parameterized programming in OBJ2. In:Balzer, Robert, ed., Proc. Ninth Int. Conf. on Software Engineering, IEEE Computer Society Press, pp. 51–60Google Scholar
Glauert, J. R. W.Hammond, K.Kennaway, J. R.Papadopoulos, G.A. and Sleep, M. R. (1988) DACTL: Some introductory papers. Technical Report SYS-C88–08, School of Information Systems, University of East Anglia.Google Scholar
Goguen, J. (1971) Mathematical representation of hierarchically organized systems. In:Attinger, E., ed., Global Systems Dynamics, S. Karger, pp. 112–28Google Scholar
Goguen, J. (1972) Minimal realization of machines in closed categories. Bull. Amer. Math. Soc. 78(5) 777–83CrossRefGoogle Scholar
Goguen, J. (1973) Realization is universal. Math. Sys. Theory 6 359–74CrossRefGoogle Scholar
Goguen, J. (1974) On homomorphisms, correctness, termination, unfoldments and equivalence of flow diagram programs. J. Comput. Sys. Sci. 8 333–65 Original version in: Proc. 1972 IEEE Symp. On Switching and Automata, pp. 52–60; contains an additional section on program schemes.CrossRefGoogle Scholar
Goguen, J. (1975) Semantics of computation. In:Manes, Ernest G., ed., Proc. First Int. Symp. on Category Theory Applied to Computation and Control, University of Massachusetts at Amherst, pp. 234–49 Also in Springer Lecture Notes in Computer Science 25 151–63Google Scholar
Goguen, J. (1986) Reusing and interconnecting software components. Computer 19(2) 16–28 Reprinted in Tutorial: Software Reusability, Peter Freeman, ed., IEEE Computer Society Press, 1987, pp. 251–63CrossRefGoogle Scholar
Goguen, J. (1988) What is unification? A categorical view of substitution, equation and solution. In:Nivat, Maurice and Aït-Kaci, Hassan, eds, Resolution of Equations in Algebraic Structures, Vol. 1: Algebraic Techniques, Academic Press, pp. 217–61 Also Technical Report SRI-CSL-88–2R2, SRI International, Computer Science Laboratory.Google Scholar
Goguen, J. (1990) Types as theories. To appear in: Proc. Symp. on General Topology and Applications, Oxford, June 1989, Oxford University Press.Google Scholar
Goguen, J. and Burstall, R. (1980) CAT, a system for the structured elaboration of correct programs from structured specifications. Technical Report CSL-118, SRI Computer Science Laboratory.Google Scholar
Goguen, J. and Brustall, R. (1984a) Some fundamental algebraic tools for the semantics of computation, part 1: Comma categories, colimits, signatures and theories. Theoret. Comput. Sci. 31(2) 175–209CrossRefGoogle Scholar
Goguen, J. and Ginali, S. (1984b) Some fundamental algebraic tools for the semantics of computation, part 2: Signed and abstract theories. Theoret. Comput. Sci. 31(3) 263–95CrossRefGoogle Scholar
Goguen, J. and Ginali, S. (1978) A categorical approach to general systems theory. In:Klir, George, ed., Applied General Systems Research, Plenum, pp. 257–70Google Scholar
Goguen, J.Kirchner, C.Kirchner, H.Mégrelis, A. and Meseguer, J. (1988) An introduction to OBJ3. In: Jean-Pierre Jouannaud and Stephane Kaplan, eds, Proc. Conf. on Conditional Term Rewriting, Springer Lecture Notes in Computer Science 308 pp. 258–63Google Scholar
Goguen, J. and Meseguer, J. (1983) Correctness of recursive parallel non-deterministic flow programs. J. Comput. Sys. Sci. 27(2) 268–90 Earlier version in Proc. Conf. on Mathematical Foundations of Computer Science, 1977, Springer Lecture Notes in Computer Science 53 pp. 580–95CrossRefGoogle Scholar
Goguen, J. (1987a) Models and equality for logical programming. In: Hartmut Ehrig, Giorgio Levi, Robert Kowalski and Ugo Montanari, eds, Proc. 1987 TAPSOFT, Springer Lecture Notes in Computer Science 250 pp. 1–22Google Scholar
Goguen, J. (1987b) Unifying functional, object-oriented and relational programming, with logical semantics. In: Bruce Shriver and Peter Wegner, eds, Research Directions in Object-Oriented Programming, MIT Press, pp. 417–77 Preliminary version in SIGPLAN Notices 21(10) 153–62Google Scholar
Goguen, J. (1988) Software for the rewrite rule machine. In: Proc. Int. Conf. on Fifth Generation Computer Systems 1988, Institute for New Generation Computer Technology (ICOT), pp. 628–37Google Scholar
Goguen, J.Thatcher, J. and Wagner, E. (1976) An initial algebra approach to the specification, correctness and implementation of abstract data types. Technical Report RC 6487, IBM T. J. Watson Research Center. In: Current Trends in Programming Methodology, IV,Yeh, Raymond, ed., Prentice-Hall, pp. 80–149Google Scholar
Goguen, J.Thatcher, J.Wagner, E. and Wright, J. (1973) A junction between computer science and category theory, I: Basic concepts and examples (part 1). Technical Report, IBM Watson Research Center, Yorktown Heights, NY. Research Report RC 4526.Google Scholar
Goguen, J. (1977) Initial algebra semantics and continuous algebras. J. Assoc. Comput. Machinery 24(1) 68–95 An early version appears as ‘Initial Algebra Semantics’, with James Thatcher, IBM T. J. Watson Research Center Report RC 4865, May 1974.CrossRefGoogle Scholar
Goldblatt, R. (1979) Topoi, the Categorial Analysis of Logic, North-Holland.Google Scholar
Hatcher, W. S. (1982) The Logical Foundations of Mathematics, Pergamon.Google Scholar
Herbrand, J. (1930) Recherches sur la theorie de la demonstration. Travaux de la Sociétédes Sciences et des Lettres de Varsovie, Classe III 33(128).Google Scholar
Herrlich, H. and Strecker, G. (1973) Category Theory. Allyn and Bacon.Google Scholar
Hoare, C. A. E. and He, J. (1988) Natural transformations and data refinement. Programming Research Group, Oxford University.Google Scholar
Hoffmann, B. and Plump, D. (1988) Jungle evaluation for efficient term rewriting. Technical Report 4/88, Fachbereich Mathematik und Informatik, Universität Bremen.Google Scholar
Hyland, M. (1982) The effective topos. In:Troelstra, A.S. and Dalen, van, eds, The Brouwer Symposium, North-Holland.Google Scholar
Keller, R. and Fasel, J. eds (1987) Proc. Graph Reduction Workshop, Springer Lecture Notes in Computer Science, 279.Google Scholar
Kennaway, R. (1987) On ‘On graph rewritings’. Theoret. Comput. Sci. 52 37–58CrossRefGoogle Scholar
Lambek, J. and Scott, P. (1986) Introduction to Higher Order Categorical Logic. Cambridge Studies in Advanced Mathematics, Volume 7, Cambridge University Press.Google Scholar
MacLane, S. (1948) Duality for groups. Proc. Nat. Acad. Sci. USA 34 263–7CrossRefGoogle ScholarPubMed
MacLane, S. (1971) Categories for the Working Mathematician, Springer.Google Scholar
MacLane, S. (1988) To the greater health of mathematics. Math. Intelligencer 10(3) 17–20 See also Math. Inteligencer 5(4) (1983) 53–5CrossRefGoogle Scholar
Lawvere, F. W. (1963) Functorial semantics of algebraic theories. Proc. Nat. Acad. Sci. USA 50 869–72 Summary of PhD Thesis, Columbia University.CrossRefGoogle ScholarPubMed
Maturana, H. and Varela, F. (1987) The Tree of Knowledge, Shambhala.Google Scholar
Meseguer, J. and Goguen, J. (1985) Initiality, induction and computability. In:Nivat, M. and Reynolds, J., eds, Algebraic Methods in Semantics. Cambridge University Press, pp. 459–541Google Scholar
Meseguer, J. and Montanari, U. (1988) Petri nets are monoids: A new algebraic foundation for net theory. In: Proc. Symp. on Logic in Computer Science, IEEE. Full version in Technical Report SRICSL-88–3, Computer Science Laboratory, SRI International, January 1988; Informat. Computat. Submitted.Google Scholar
Milner, R. (1971) An algebraic definition of simulation between programs. Technical Report CS-205, Stanford University, Computer Science Department.Google Scholar
Milner, R. (1980) A Calculus of Communicating Systems, Springer Lecture Notes in Computer Science, 92.Google Scholar
Moggi, E. (1988) Computational lambda-calculus and monads. Technical Report ECS-LFCS-88–66, Laboratory for Foundations of Computer Science, University of Edinburgh.Google Scholar
Moggi, E. (1989) A category-theoretic account of program modules. Laboratory for Foundations of Computer Science, University of Edinburgh.Google Scholar
Paré, R. and Johnstone, P. (1978) Indexed Categories and their Applications, Springer Lecture Notes in Mathematics, 661.Google Scholar
Raoult, J. C. (1984) On graph rewritings. Theoret. Comput. Sci. 32 1–24CrossRefGoogle Scholar
Scott, D. (1972) Continuous lattices. In: Proc. Dalhousie Conf, Springer Lecture Notes in Mathematics, 274, pp. 97–136CrossRefGoogle Scholar
Shieber, S. (1986) An Introduction to Unification-Based Approaches to Grammar, Center for the Study of Language and Information.Google Scholar
Smyth, M. and Plotkin, G. (1982) The category-theoretic solution of recursive domain equations. SIAM J. Comput. 11 761–83 Also Technical Report D.A.I. 60, University of Edinburgh, Department of Artificial Intelligence, December 1978.CrossRefGoogle Scholar
Tarlecki, A.Burstall, R. and Goguen, J. (1989) Some fundamental algebraic tools for the semantics of computation, part 3: Indexed categories. Technical Report PRG-77, Programming Research Group, Oxford University. Theoret. Comput. Sci. to appear.Google Scholar
Tracz, W. J. (1990) Formal specification of parameterized programs in LILLEANNA. PhD thesis, Stanford University, to appear.Google Scholar
Whitehead, A. N. (1969) Process and Reality, Free Press.Google Scholar