Lively linear Lisp: “look ma, no garbage!”

ABSTRACT

Linear logic has been proposed as one solution to the problem of garbage collection and providing efficient "update-in-place" capabilities within a more functional language. Linear logic conserves accessibility, and hence provides a mechanical metaphor which is more appropriate for a distributed-memory parallel processor in which copying is explicit. However, linear logic's lack of sharing may introduce significant inefficiencies of its own.We show an efficient implementation of linear logic called Linear Lisp that runs within a constant factor of non-linear logic. This Linear Lisp allows RPLACX operations, and manages storage as safely as a non-linear Lisp, but does not need a garbage collector. Since it offers assignments but no sharing, it occupies a twilight zone between functional languages and imperative languages. Our Linear Lisp Machine offers many of the same capabilities as combinator/graph reduction machines, but without their copying and garbage collection problems.

REFERENCES

• 1: Martin Abadi , Gordon Plotkin, A logical view of composition and refinement, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.323-332, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99626]
• 2: Arvind , R S Nikhil, Executing a program on the MIT tagged-token dataflow architecture, Volume II: Parallel Languages on PARLE: Parallel Architectures and Languages Europe, p.1-29, March 1987, Eindhoven, The Netherlands
• 3: Arvind , Rishiyur S. Nikhil , Keshav K. Pingali, I-structures: data structures for parallel computing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.598-632, Oct. 1989 [doi>10.1145/69558.69562]
• 4: Henry C. Baker, Jr. , Carl Hewitt, The incremental garbage collection of processes, ACM SIGPLAN Notices, v.12 n.8, p.55-59, August 1977
• 5: Henry G. Baker, Jr., Shallow binding in Lisp 1.5, Communications of the ACM, v.21 n.7, p.565-569, July 1978 [doi>10.1145/359545.359566]
• 6: 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]
• 7: Baker, H.G. "Equal Rights for Functional Objects". Tech. Rept., Nimble Computer, 1991.
• 8: Henry G. Baker, Shallow binding makes functional arrays fast, ACM SIGPLAN Notices, v.26 n.8, p.145-147, Aug. 1991 [doi>10.1145/122598.122614]
• 9: Henry G. Baker, The Boyer Benchmark at warp speed, ACM SIGPLAN Lisp Pointers, v.V n.3, p.13-14, July-Sept. 1992 [doi>10.1145/147135.147137]
• 10: Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977 [doi>10.1145/359636.359713]
• 11: Paul S. Barth , Rishiyur S. Nikhil , Arvind, M-Structures: Extending a Parallel, Non-strict, Functional Language with State, Proceedings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture, p.538-568, August 26-30, 1991
• 12: 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]
• 13: Michael Beeler , R. W Gosper , Rich Schroeppel, HAKMEM, Massachusetts Institute of Technology, Cambridge, MA, 1972
• 14: Gerard Berry , Gerard Boudol, The chemical abstract machine, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.81-94, December 1989, San Francisco, California, United States [doi>10.1145/96709.96717]
• 15: Adrienne Bloss, Update analysis and the efficient implementation of functional aggregates, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.26-38, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99373]
• 16: David Read Chase , Kenneth W. Kennedy, Garbage collection and other optimizations, Rice University, Houston, TX, 1988
• 17: 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]
• 18: A. P. Ershov, On programming of arithmetic operations, Communications of the ACM, v.1 n.8, p.3-6, Aug. 1958 [doi>10.1145/368892.368907]
• 19: Richard J. Fateman, FRPOLY: a benchmark revisited, Lisp and Symbolic Computation, v.4 n.2, p.155-164, April 1991 [doi>10.1007/BF01813018]
• 20: Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 21: Gabriel, R.P. "The Why of Y". ACM Lisp Pointers 2, 2 (Oct.-Dec. 1988), 15-25.
• 22: 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]
• 23: Goto, Eiichi. "Monocopy and Associative Algorithms in an Extended Lisp". Tech. Rep. 74-03, Info. Sci. Lab., U. Tokyo, April 1974.
• 24: Eiichi Goto , Yasumasa Kanada, Hashing LEMMAs on time complexities with applications to formula manipulation, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.154-158, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806334]
• 25: Goto, E., et al. "Parallel Hashing Algorithms". Info. Proc. Let. 6, 1 (Feb. 1977), 8-13.
• 26: E. Goto , T. Soma , N. Inada , T. Ida , M. Idesawa , K. Hiraki , M. Suzuki , K. Shimizu , B. Philipov, Design of a Lisp machine - FLATS, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.208-215, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802152]
• 27: 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]
• 28: Hederman, Lucy. "Compile Time Garbage Collection". MS Thesis, Rice University Computer Science Dept., Sept. 1988.
• 29: 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]
• 30: Katsuro Inoue , Hiroyuki Seki , Hikaru Yagi, Analysis of functional programs to detect run-time garbage cells, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.555-578, Oct. 1988 [doi>10.1145/48022.48025]
• 31: Thomas Johnsson, Efficient compilation of lazy evaluation, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.58-69, June 17-22, 1984, Montreal, Canada
• 32: Thomas Johnsson, Lambda lifting: transforming programs to recursive equations, Proc. of a conference on Functional programming languages and computer architecture, p.190-203, January 1985, Nancy, France
• 33: Thomas Johnsson, Parallel evaluation of functional programs: the <vG>-machine approach (summary), Proceedings on Parallel architectures and languages Europe : volume I: parallel architectures and algorithms: volume I: parallel architectures and algorithms, p.1-5, June 1991, Eindhoven, The Netherlands
• 34: Simon B. Jones , Daniel Le Métayer, Compile-time garbage collection by sharing analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.54-74, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99375]
• 35: 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
• 36: Richard B. Kieburtz, The g-machine: a fast, graph-reduction evaluator, Proc. of a conference on Functional programming languages and computer architecture, p.400-413, January 1985, Nancy, France
• 37: Richard B. Kieburtz, A RISC architecture for symbolic computation, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.146-155, October 1987, Palo Alto, California, United States
• 38: Tom Knight, An architecture for mostly functional languages, Proceedings of the 1986 ACM conference on LISP and functional programming, p.105-112, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319854]
• 39: 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]
• 40: Yves Lafont, Interaction nets, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.95-108, December 1989, San Francisco, California, United States [doi>10.1145/96709.96718]
• 41: Lafont, Yves. "The Paradigm of Interaction (Short Version)". Unpubl. manuscript, July 12, 1991, 18p.
• 42: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• 43: B. J. MacLennan, Values and objects in programming languages, ACM SIGPLAN Notices, v.17 n.12, December 1982 [doi>10.1145/988164.988172]
• 44: 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]
• 45: Ian A. Mason, The semantics of destructive LISP, Center for the Study of Language and Information, Stanford, CA, 1987
• 46: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• 47: Morris, J.M. "A proof of the Schorr-Waite algorithm". In Broy, M., and Schmidt, G., Eds. Theoretical Foundations of Programming Methodology. NATA Advanced Study Inst., D. Reidel, 1982, 43-51.
• 48: Eugene W. Myers, Efficient applicative data types, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.66-75, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800517]
• 49: Peyton-Jones, S.L. The Implementation of Functional Programming Languages. Prentice-Hall, New York, 1987.
• 50: J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986 [doi>10.1145/15042.15043]
• 51: C. Ruggieri , T. P. Murtagh, Lifetime analysis of dynamically allocated objects, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-293, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73585]
• 52: H. Schorr , W. M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, Communications of the ACM, v.10 n.8, p.501-506, Aug. 1967 [doi>10.1145/363534.363554]
• 53: Strom, R.E., et al. "A recoverable object store". IBM Watson Research Ctr., 1988.
• 54: Norihisa Suzuki, Analysis of pointer “rotation”, Communications of the ACM, v.25 n.5, p.330-335, May 1982 [doi>10.1145/358506.358513]
• 55: Terashima, M., and Goto, E. "Genetic Order and Compactifying Garbage Collectors". IPL 7, 1 (Jan. 1978), 27-32.
• 56: Turner, D. "A New Implementation Technique for Applicative Languages". SW--Pract.&Exper. 9 (1979), 31-49.
• 57: Wadler, Philip. "Linear types can change the world!". IFIP TC2 Conf. on Progr. Concepts & Meths., April 1990.
• 58: 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
• 59: 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
• 60: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
• 61: Jon L. White, Address/memory management for a gigantic LISP environment or, GC considered harmful, Proceedings of the 1980 ACM conference on LISP and functional programming, p.119-127, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802797]
• 62: Wilson, Paul R. Two comprehensive virtual copy mechanisms. Master's Thesis, U. Ill. @ Chicago, 1988.
• 63: P. R. Wilson , T. G. Moher, Demonic memory for process histories, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.330-343, June 19-23, 1989, Portland, Oregon, United States
• 64: Paul R. Wilson, Some issues and strategies in heap management and memory hierarchies, ACM SIGPLAN Notices, v.26 n.3, p.45-52, March 1991 [doi>10.1145/122167.122173]
• 65: Wise, D.S., and Friedman, D.P. "The one-bit reference count". BIT 17, 3 (Sept. 1977), 351-359.
• 66: David S. Wise, Design for a multiprocessing heap with on-board reference counting, Proc. of a conference on Functional programming languages and computer architecture, p.289-304, January 1985, Nancy, France

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LISP

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures
      D.3.4 Processors
          Subjects: Interpreters

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

General Terms:
Algorithms, Languages