Abstract
We study a relationship between logic and computation via concurrent constraint programming. In previous papers it has been shown that concurrent constraint programs can be modeled by closure operators. In the present paper we show that the programming interpretation via closure operators is intimately related to the logic of the constraints. More precisely, we show how the usual hyperdoctrinal description of first order logic can be functorially related to another hyperdoctrine built out of closure operators. The logical connectives map onto constructions on closure operators that turn out to model programming constructs, specifically conjunction becomes parallel composition and existential quantification becomes hiding of local variables.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K.R Apt and M.H. van Emden. Contributions to the theory of logic programming. JACM, 29(3):841–862, 1982.
M. Barr and C. Wells. Category Theory for Computing Science. prentice-Hall, 1990.
G. Berry and G. Boudol. The chemical abstract machine. In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, pages 81–94. ACM, 1990.
G. Boudol. Towards a lambda-calculus for concurrent and communicating systems. In J. Diaz, editor, TAPSOFT 89, Lecture Notes in Computer Science 351, pages 149–161. Springer-Verlag, 1989.
G. Gierz, K.H. Hoffman, K. Keimel, J.D.Lawson, M.Mislove, and D.S.Scott, editors. A compendium of continuous lattices. Springer-Verlag Berlin Heidelberg New York, 1980.
Leon Henkin, J. Donald Monk, and Alfred Tarski. Cylindric Algebras (Part I). North Holland Publishing Company, 1971.
J. M. E. Hyland and A. M. Pitts. The theory of constructions: Categorical semantics and topos-theoretic models. In Categories in Computer Science and Logic, pages 137–199. AMS, 1987. AMS Contemporary Mathematics Series 92.
B. Jacobs. Fibrations. Submitted to Mathematical Structures in Computer Science, 1991.
R. Jagadeesan and P. Panangaden. A domain-theoretic model of a higher-order process calculus. In M. Paterson, editor, Proceedings of the 17th International Colloquium on Automata Languages and Programming, pages 181–194. Springer-Verlag, 1990. Lecture Notes in Computer Science 443.
R. Jagadeesan, P. Panangaden, and K. Pingali. A fully abstract semantics for a functional language with logic variables. In Proceedings of IEEE Symposium on Logic in Computer Science, pages 294–303, 1989.
R. Jagadeesan and K. Pingali. A higher order functional language with logic variables. In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Programming Languages, 1992.
Peter Johnstone. Stone Spaces, volume 3 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, 1982.
G. Kahn. The semantics of a simple language for parallel programming. In Information Processing 74, pages 993–998. North-Holland, 1977. [14] R.A. Kowalski and M.H. van Emden. The semantics of predicate logic as a programming language. Journal of the ACM, 23(4):733-742, 1976.
F. W. Lawvere. Functorial semantics of algebraic theories. Proc. Nat. Acad. Sci. U.S.A., 50:869–872, 1963.
D. Pavlović. Predicates and Fibrations. PhD thesis, University of Amsterdam, 1991.
V. Saraswat. Concurrent Constraint Programming Languages. PhD thesis, Carnegie-Mellon University, 1989. To appear Doctoral Dissertation Award and Logic Programming Series, MIT Press.
V. Saraswat. The category of constraint systems is cartesian closed. In Seventh Annual IEEE Symposium On Logic In Computer Science, 1992.
Vijay Saraswat and Martin Rinard. Concurrent constraint programming. In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, pages 232–245, 1990.
Vijay Saraswat, Martin Rinard, and Prakash Panangaden. Semantic foundations of concurrent constraint programming. In Proceedings of the Eighteenth Annual ACM Symposium on Principles of Programming Languages, 1991.
D. Scott. Data types as lattices. SIAM Journal of Computing, 5(3):522–587, 1976.
D. S. Scott. Domains for denotational semantics. In Ninth International Colloquium On Automata Languages And Programming. Springer-Verlag, 1982. Lecture Notes In Computer Science 140.
R. A. G. Seely. Hyperdoctrines, natural deduction and the beck conditions. Zeitschr. f. math. Logik und Grundlagen d. Math., 29:505–542, 1983.
R. A. G. Seely. Categorical semantics for higher-order polymorphic lambda calculus. J. Symb. Logic, 52(4):969–989, 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Panangaden, P., Saraswat, V., Scott, P.J., Seely, R.A.G. (1993). A hyperdoctrinal view of concurrent constraint programming. In: de Bakker, J.W., de Roever, W.P., Rozenberg, G. (eds) Semantics: Foundations and Applications. REX 1992. Lecture Notes in Computer Science, vol 666. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56596-5_44
Download citation
DOI: https://doi.org/10.1007/3-540-56596-5_44
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56596-3
Online ISBN: 978-3-540-47595-8
eBook Packages: Springer Book Archive