“Use-once” variables and linear objects

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

“Use-once” variables and linear objects: storage management, reflection and multi-threading

Full text

Pdf (1.11 MB)

Source

ACM SIGPLAN Notices archive
Volume 30 , Issue 1 (January 1995) table of contents

Pages: 45 - 52

Year of Publication: 1995

ISSN:0362-1340

Author

Henry G. Baker

Nimble Computer Corporation, 16231 Meadow Ridge Way, Encino, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 27, Citation Count: 6

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/199818.199860 What is a DOI?

ABSTRACT

Programming languages should have 'use-once' variables in addition to the usual 'multiple-use' variables. 'Use-once' variables are bound to linear (unshared, unaliased, or singly-referenced) objects. Linear objects are cheap to access and manage, because they require no synchronization or tracing garbage collection. Linear objects can elegantly and efficiently solve otherwise difficult problems of functional/mostly-functional systems---e.g., in-place updating and the efficient initialization of functional objects. Use-once variables are ideal for directly manipulating resources which are inherently linear such as freelists and 'engine ticks' in reflective languages.A 'use-once' variable must be dynamically referenced exactly once within its scope. Unreferenced use-once variables must be explicitly killed, and multiply-referenced use-once variables must be explicitly copied; this duplication and deletion is subject to the constraint that some linear datatypes do not support duplication and deletion methods. Use-once variables are bound only to linear objects, which may reference other linear or non-linear objects. Non-linear objects can reference other non-linear objects, but can reference a linear object only in a way that ensures mutual exclusion.Although implementations have long had implicit use-once variables and linear objects, most languages do not provide the programmer any help for their utilization. For example, use-once variables allow for the safe/controlled use of reified language implementation objects like single-use continuations.Linear objects and use-once variables map elegantly into dataflow models of concurrent computation, and the graphical representations of dataflow models make an appealing visual linear programming language.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Henry Ledgard, Reference Manual for the ADA Programming Language, Springer-Verlag New York, Inc., Secaucus, NJ, 1983
	2	W. F. Appelbe , A. P. Ravn, Encapsulation constructs in systems programming languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.2, p.129-158, April 1984 [doi>10.1145/2993.69615]
	3	Henry C. Baker, Jr. , Carl Hewitt, The incremental garbage collection of processes, ACM SIGPLAN Notices, v.12 n.8, p.55-59, August 1977
	4	Henry G. Baker, Unify and conquer, Proceedings of the 1990 ACM conference on LISP and functional programming, p.218-226, June 27-29, 1990, Nice, France [doi>10.1145/91556.91652]
	5	Baker, H.G. "Cache-conscious copying collectors". OOPSLA'91 GC Workshop, Oct. 1991.
	6	Henry G. Baker, Lively linear Lisp: “look ma, no garbage!”, ACM SIGPLAN Notices, v.27 n.8, p.89-98, Aug. 1992 [doi>10.1145/142137.142162]
	7	Henry G. Baker, Equal rights for functional objects or, the more things change, the more they are the same, ACM SIGPLAN OOPS Messenger, v.4 n.4, p.2-27, Oct. 1993 [doi>10.1145/165593.165596]
	8	Henry G. Baker, The Boyer benchmark meets linear logic, ACM SIGPLAN Lisp Pointers, v.VI n.4, p.3-10, Oct.-Dec. 1993 [doi>10.1145/181889.181890]
	9	Henry G. Baker, Sparse polynomials and linear logic, ACM SIGSAM Bulletin, v.27 n.4, p.10-14, Dec. 1993 [doi>10.1145/182125.182128]
	10	Henry G. Baker, A “linear logic” Quicksort, ACM SIGPLAN Notices, v.29 n.2, p.13-18, Feb. 1994 [doi>10.1145/181748.181750]
	11	Henry G. Baker, Linear logic and permutation stacks—the Forth shall be first, ACM SIGARCH Computer Architecture News, v.22 n.1, p.34-43, March 1994 [doi>10.1145/181993.181999]
	12	Henry G. Baker, Minimizing reference count updating with deferred and anchored pointers for functional data structures, ACM SIGPLAN Notices, v.29 n.9, p.38-43, Sept. 1994 [doi>10.1145/185009.185016]
	13	Alan Bawden, Connection graphs, Proceedings of the 1986 ACM conference on LISP and functional programming, p.258-265, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319868]
	14	Luca Cardelli , Peter Wegner, On understanding types, data abstraction, and polymorphism, ACM Computing Surveys (CSUR), v.17 n.4, p.471-523, Dec. 1985 [doi>10.1145/6041.6042]
	15	Nicholas Carriero , David Gelernter, Linda in context, Communications of the ACM, v.32 n.4, p.444-458, April 1989 [doi>10.1145/63334.63337]
	16	Chikayama, T., and Kimura, Y. "Multiple reference management in flat GHC". In Lassez, J.-L., ed. Logic Programming, Proc. 4th Intl. Conf. MIT Press, Camb., MA, 1987, 276-293.
	17	Jawahar Chirimar , Carl A. Gunter , Jon G. Riecke, Proving memory management invariants for a language based on linear logic, ACM SIGPLAN Lisp Pointers, v.V n.1, p.139-150, Jan. 1992
	18	Clark, D.W., and Green, C.C. "A note on shared list structure in Lisp". Inf. Proc. Lett. 7, 6 (Oct. 1978), 312-315.
	19	George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
	20	Rhys S. Francis, Containment defines a class of recursive data structures, ACM SIGPLAN Notices, v.18 n.4, p.58-64, April 1983 [doi>10.1145/948176.948180]
	21	Friedman, D.P., & Wise, D.S. "Aspects of applicative programming for parallel processing". IEEE Trans. Comput. C-27, 4 (Apr. 1978), 289-296.
	22	Daniel P. Friedman , Mitchell Wand, Reification: Reflection without metaphysics, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.348-355, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802051]
	23	Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
	24	Gabriel, R.P. "The Why of Y". ACM Lisp Pointers 2, 2 (Oct.-Dec. 1988), 15-25.
	25	Jean-Yves Girard, Linear logic, Theoretical Computer Science, v.50 n.1, p.1-102, Jan. 30, 1987 [doi>10.1016/0304-3975(87)90045-4]
	26	Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
	27	Goto, A., et al. "Lazy reference counting: An incremental garbage collection method for parallel inference machines". Proc. Intl. Conf. on Logic Programming, MIT Press, 1988, 1241-1256.
	28	Gudeman, D., et al. " jc: An Efficient and Portable Sequential implementation of Janus". Logic Programming, Proc. Jt. Intl. Conf. & Symp. MIT Press, 1992, 399-413.
	29	Guzmán, J.C., and Hudak, P. "Single-threaded polymorphic lambda calculus". 5th IEEE LICS, 1990, 333-343.
	30	Douglas E. Harms , Bruce W. Weide, Copying and Swapping: Influences on the Design of Reusable Software Components, IEEE Transactions on Software Engineering, v.17 n.5, p.424-435, May 1991 [doi>10.1109/32.90445]
	31	Harper, R., et al. "Standard ML". TR ECS-LFCS-86-2, Comp. Sci. Dept., Edinburgh, UK, Mar. 1986.
	32	Christopher T. Haynes , Daniel P. Friedman, Engines build process abstractions, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.18-24, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802018]
	33	Christopher T. Haynes , Daniel P. Friedman, Embedding continuations in procedural objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.582-598, Oct. 1987 [doi>10.1145/29873.30392]
	34	Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
	35	C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
	36	John Hogg, Islands: aliasing protection in object-oriented languages, ACM SIGPLAN Notices, v.26 n.11, p.271-285, Nov. 1991
	37	Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
	38	A. Imai , E. Tick, Evaluation of Parallel Copying Garbage Collection on a Shared-Memory Multiprocessor, IEEE Transactions on Parallel and Distributed Systems, v.4 n.9, p.1030-1040, September 1993 [doi>10.1109/71.243529]
	39	Inamura, Y., et al. "Optimization techniques using the MRB and their evaluation on the Multi-PSI/V2". In Lusk, E.L., and Overbeek, R.A., eds. Logic Programming, Proc. of North American Conf. MIT Press, 1989, 907-921.
	40	Proceedings of the US/Japan workshop on Parallel Lisp on Parallel Lisp: languages and systems, June 1990
	41	R. R. Kessler , M. R. Swanson, Concurrent scheme, Proceedings of the US/Japan workshop on Parallel Lisp on Parallel Lisp: languages and systems, p.200-234, June 1990, Sendai, Japan
	42	Gregor Kiczales , Jim Des Rivieres, The Art of the Metaobject Protocol, MIT Press, Cambridge, MA, 1991
	43	Richard B. Kieburtz, Programming without pointer variables, Proceedings of the 1976 conference on Data : Abstraction, definition and structure, p.95-107, March 22-24, 1976, Salt Lake City, Utah, United States
	44	Y. Lafont, The linear abstract machine, Theoretical Computer Science, v.59 n.1-2, p.157-180, July 1988 [doi>10.1016/0304-3975(88)90100-4]
	45	Lincoln, P., and Mitchell, J.C. "Operational aspects of linear lambda calculus". Proc. 7th IEEE Logic in CS, 1992.
	46	Andy Lowry, The Hermes language in outline form, ACM SIGPLAN Notices, v.27 n.8, p.51-70, Aug. 1992 [doi>10.1145/142137.142148]
	47	Lucassen, J.M. Types and Effects: Towards the Integration of Functional and Imperative Programming. PhD Thesis, MIT/LCS/TR-408, MIT, Aug. 1987.
	48	Harry G. Mairson, Deciding ML typability is complete for deterministic exponential time, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.382-401, December 1989, San Francisco, California, United States [doi>10.1145/96709.96748]
	49	A. Mendelson , D. K. Pradhan , A. D. Singh, A single cached copy data coherence scheme for multiprocessor systems, ACM SIGARCH Computer Architecture News, v.17 n.6, p.36-49, Dec. 1989 [doi>10.1145/77254.77257]
	50	Kenji Nishida , Yasunori Kimura , Akira Matsumoto , Atsuhiro Goto, Evaluation of MRB garbage collection parallel logic programming architectures, Logic programming, MIT Press, Cambridge, MA, 1990
	51	Martin Odersky, How to make destructive updates less destructive, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-36, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99590]
	52	Elizabeth D. Rather , Donald R. Colburn , Charles H. Moore, The evolution of Forth, ACM SIGPLAN Notices, v.28 n.3, p.177-199, March 1993
	53	Vijay A. Saraswat , Ken Kahn , Jacob Levy, Janus: a step towards distributed constraint programming, Proceedings of the 1990 North American conference on Logic programming, p.431-446, January 1990, Austin, Texas, United States
	54	Steele, G.L. "Data Representations in PDP-10 Maclisp". AI Memo 420, MIT AI Lab., Camb., MA, Sept. 1977.
	55	Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
	56	Guy L. Steele, Jr., Common LISP: the language (2nd ed.), Digital Press, Newton, MA, 1990
	57	W. R. Stoye , T. J. W. Clarke , A. C. Norman, Some practical methods for rapid combinator reduction, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.159-166, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802032]
	58	Rob Strom , Shaula Yemini, The NIL distributed systems programming language: a status report, ACM SIGPLAN Notices, v.20 n.5, May 1985 [doi>10.1145/988327.988333]
	59	R E Strom , S Yemini, Typestate: A programming language concept for enhancing software reliability, IEEE Transactions on Software Engineering, v.12 n.1, p.157-171, Jan. 1986
	60	Taft, S.T., et al. Ada9X Mapping Documents. DoD, Wash., DC, Feb. 1991.
	61	Taft, S.T., et al. Ada9X Reference Manual, v. 5.0. Intermetrics, Inc., Camb., MA, June, 1994.
	62	Philip Wadler, Is there a use for linear logic?, Proceedings of the 1991 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.255-273, June 17-19, 1991, New Haven, Connecticut, United States
	63	David Wakeling , Colin Runciman, Linearity and Laziness, Proceedings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture, p.215-240, August 26-30, 1991
	64	Mitchell Wand, Continuation-based multiprocessing, Proceedings of the 1980 ACM conference on LISP and functional programming, p.19-28, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802786]
	65	Wise, D.S., and Friedman, D.P. "The one-bit reference count". BIT 17, 3 (Sept. 1977), 351-359.
	66	David S. Wise, Stop-and-copy and one-bit reference counting, Information Processing Letters, v.46 n.5, p.243-249, July 9, 1993 [doi>10.1016/0020-0190(93)90103-G]
	67	Taiichi Yuasa, Design and implementation of Kyoto Common Lisp, Journal of Information Processing, v.13 n.3, p.284-295, 1990
	68	T. Yuasa , T. Kawana, PM1 and PMLisp: an experimental machine and its Lisp system for research on MIMD massively parallel computation, Proceedings of the US/Japan workshop on Parallel Lisp on Parallel Lisp: languages and systems, p.322-347, June 1990, Sendai, Japan

CITED BY 6

	David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, ACM SIGPLAN Notices, v.33 n.10, p.48-64, Oct. 1998
	Dave Clarke , Sophia Drossopoulou, Ownership, encapsulation and the disjointness of type and effect, ACM SIGPLAN Notices, v.37 n.11, November 2002
	Edwin C. Chan , John T. Boyland , William L. Scherlis, Promises: limited specifications for analysis and manipulation, Proceedings of the 20th international conference on Software engineering, p.167-176, April 19-25, 1998, Kyoto, Japan
	John Tang Boyland , William Retert, Connecting effects and uniqueness with adoption, ACM SIGPLAN Notices, v.40 n.1, p.283-295, January 2005
	Luís Lopes , Vasco T. Vasconcelos , Fernando Silva, Fine-Grained Multithreading with Process Calculi, IEEE Transactions on Computers, v.50 n.8, p.852-862, August 2001
	Gregory Kulczycki , Jyotindra Vasudeo, Simplifying reasoning about objects with Tako, Proceedings of the 2006 conference on Specification and verification of component-based systems, November 10-11, 2006, Portland, Oregon