Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-01-12T10:47:14.907Z Has data issue: false hasContentIssue false
  • English
  • Français

Reference counting as a computational interpretation of linear logic

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

Jawahar Chirimar ,
Carl A. Gunter  and
Jon G. Riecke
Jawahar Chirimar
Affiliation:
Department of Computer and Information ScienceUniversity of Pennsylvania, Philadelphia, PA 19104, USA
Carl A. Gunter
Affiliation:
Department of Computer and Information ScienceUniversity of Pennsylvania, Philadelphia, PA 19104, USA
Jon G. Riecke
Affiliation:
Bell Laboratories700 Mountain Avenue, Murray Hill, NJ 07974, USA
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We develop an operational model for a language based on linear logic. Our semantics is ‘low-level’ enough to express sharing and copying while still being ‘high-level’ enough to abstract away from details of memory layout, and thus can be used to test potential applications of linear logic for analysis of programs. In particular, we demonstrate a precise relationship between type correctness for the linear-logic-based language and the correctness of a reference-counting interpretation of the primitives, and formulate and prove a result describing the possible run-time reference counts of values of linear type.

Type
Articles
Information
Journal of Functional Programming , Volume 6 , Issue 2 , March 1996 , pp. 195 - 244
Copyright
Copyright © Cambridge University Press 1996

References

Abramsky, S. (1993) Computational interpretations of linear logic. Theoretical Computer Science 111:3–57.CrossRefGoogle Scholar
Abramsky, S. and Hankin, C. (eds.) (1987) Abstract Interpretation of Declarative Languages. Ellis Horwood.Google Scholar
Appel, A. (1992) Compiling with Continuations. Cambridge University Press.Google Scholar
Baker, H. G. (1978) List processing in real time on a serial computer. Communications of the ACM 21(7):11–20.CrossRefGoogle Scholar
Benton, N., Bierman, G., de Paiva, V. and Hyland, M. (1992) Term assignment for intuitionistic linear logic. Technical Report 262, University of Cambridge Computer Laboratory.Google Scholar
Benton, N., Bierman, G., de Paiva, V. and Hyland, M. (1993) A term calculus for intuitionistic linear logic. In Typed Lambda Calculi and Applications: Lecture Notes in Computer Science vol 664, pp. 75–90. Springer-Verlag.CrossRefGoogle Scholar
Bloss, A., Hudak, P. and Young, J. (1988) An optimizing compiler for a modern functional programming language. Computer Journal 31(6).Google Scholar
Breazu-Tannen, V., Gunter, C. and Scedrov, A. (1990) Computing with coercions. Proceedings of the ACM Conference on Lisp and Functional Programming, pp. 44–60.CrossRefGoogle Scholar
Chirimar, J., Gunter, C. A. and Riecke, J. G. (1992) Proving memory management invariants for a language based on linear logic. Proceedings of the ACM Conference on Lisp and Functional Programming, pp. 139–150.CrossRefGoogle Scholar
Collins, G. E. (1960) A method for overlapping and erasure of lists. Communications of the ACM 3(12): 655–657.CrossRefGoogle Scholar
Despeyroux, J. (1986) Proof of translation in natural semantics. Proceedings, Symposium on Logic in Computer Science. IEEE.Google Scholar
Deutsch, L. P. and Bobrow, D. G. (1976) An efficient, incremental, automatic garbage collector. Communications of the ACM 19(9): 522–526.CrossRefGoogle Scholar
Filinski, A. (1992) Linear continuations. Conference Record of the 19th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 27–38. ACM.CrossRefGoogle Scholar
Gabriel, R. P. (1985) Performance and Evaluation of Lisp Systems. MIT Press.CrossRefGoogle Scholar
Girard, J.-Y. (1987) Linear logic. Theoretical Computer Science 50: 1–102.CrossRefGoogle Scholar
Goldberg, B. and Gloger, M. (1992) Polymorphic type reconstruction for garbage collection without tags. Proceedings of the ACM Conference on Lisp and Functional Programming, pp. 53–65. ACM.CrossRefGoogle Scholar
Guzmán, J. C. and Hudak, P. (1990) Single-threaded polymorphic lambda calculus. Proceedings 5th Annual IEEE Symposium on Logic in Computer Science, pp. 333–343.CrossRefGoogle Scholar
Holmström, S. (1988) Linear functional programming. In Implementation of Lazy Functional Languages, Johnsson, T., Peyton-Jones, S. and Karlsson, K. (eds.), pp. 13–32.Google Scholar
Howard, W. A. (1980) The formulae-as-types notion of construction. In To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, Hindley, J. and Seldin, J. (eds.), pp. 479–490. Academic Press.Google Scholar
Hudak, P. (1987) A semantic model of reference counting and its abstraction. In Abstract Interpretation of Declarative Languages, pp. 45–62. Chichester: Ellis Horwood. (Preliminary version appeared in Proceedings 1986 ACM Conference on LISP and Functional Programming, August 1986, pp. 351–363).Google Scholar
Kahn, G. (1987) Natural semantics. Proceedings Symposium on Theoretical Aspects of Computer Science: Lecture Notes in Computer Science vol 247. Springer-Verlag.Google Scholar
Lafont, Y. (1988) The linear abstract machine. Theoretical Computer Science 59: 157–180.CrossRefGoogle Scholar
Launchbury, J. (1993) A natural semantics for lazy evaluation. Conference Record of the 20th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 144–154. ACM.CrossRefGoogle Scholar
Lawall, J. L. and Danvy, O. (1993) Separating stages in the continuation-passing style transformation. Conference Record of the 20th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 124–136. ACM.CrossRefGoogle Scholar
Lincoln, P. and Mitchell, J. C. (1992) Operational aspects of linear lambda calculus. Proceedings 7th Annual IEEE Symposium on Logic in Computer Science, pp. 235–247.CrossRefGoogle Scholar
Mackie, I. (1991) Lilac: A functional programming language based on linear logic. Master's thesis, Imperial College, University of London.Google Scholar
Milner, R. and Tofte, M. (1991) Commentary on Standard ML. MIT Press.Google Scholar
Milner, R., Tofte, M. and Harper, R. (1990) The Definition of Standard ML. MIT Press.Google Scholar
O'Hearn, P. W. (1991) Linear logic and interference control (preliminary report). In Category Theory and Computer Science: Lecture Notes in Computer Science vol 530, Pitt, D. H. (ed.), pp. 74–93. Springer-Verlag.CrossRefGoogle Scholar
Plotkin, G. D. (1975) Call-by-name, call-by-value and the λ-calculus. Theoretical Computer Science 1:125–159.CrossRefGoogle Scholar
Plotkin, G. D. (1977) LCF considered as a programming language. Theoretical Computer Science 5: 223–257.CrossRefGoogle Scholar
Purushothaman, S. and Seaman, J. (1991) An adequate operational semantics of sharing in lazy evaluation. Technical Report PSU-CS-91-18, Pennsylvania State University.Google Scholar
Scott, D. S. (1993) A type theoretical alternative to CUCH, ISWIM, OWHY. Theoretical Computer Science 121: 411–440. (Published version of unpublished manuscript, Oxford University, 1969.)CrossRefGoogle Scholar
Wadler, P. (1990) Linear types can change the world! In Programming Concepts and Methods, Broy, M. and Jones, C. B. (eds.). North Holland.Google Scholar
Wadler, P. (1991) Is there a use for linear logic? Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pp. 255–273. ACM.CrossRefGoogle Scholar
Wadler, P. (1993) A syntax for linear logic. Workshop on Mathematical Foundations of Programming Language Semantics, New Orleans, LA.Google Scholar
Wand, M. and Oliva, D. P. (1992) Proving the correctness of storage representations. In Lisp and Functional Programming, Clinger, W. (ed.), pp. 151–160. ACM.Google Scholar
Wise, D. S., Hess, C., Hunt, W. and Ost, E. (1992) Uniprocessor performance of reference-counting hardware heap. Unpublished manuscript.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.