A “linear logic” Quicksort

ABSTRACT

The linear style of programming inspired by linear logic has been proposed to reduce garbage collection and synchronization costs in serial and parallel systems. We programmed Quicksort for both lists and arrays in a "linear" fragment of Lisp to estimate the performance impact of linearity on a serial machine. Even though Quicksort is well-tuned for current non-linear architectures, we find that linearity extracts no real penalty. Our "linear" list Quicksort is as fast as any non-linear list Quicksort, and our "linear" vector Quicksort is only 3.5% slower than a non-linear vector Quicksort. The linear style is moderately pleasant, and the redundancy of linearity checking can aid in finding bugs.

REFERENCES

• 1: Samson Abramsky, Computational interpretations of linear logic, Theoretical Computer Science, v.111 n.1-2, p.3-57, April 12, 1993 [doi>10.1016/0304-3975(93)90181-R]
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Sara Baase, Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 4: Henry G. Baker, The buried binding and dead binding problems of Lisp 1.5: sources of incomparability in garbage collector measurements, ACM SIGPLAN Lisp Pointers, v.V n.2, p.11-19, April-June 1992 [doi>10.1145/1039991.1039993]
• 5: 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]
• 6: Henry G. Baker, NREVERSAL of Fortune - The Thermodynamics of Garbage Collection, Proceedings of the International Workshop on Memory Management, p.507-524, September 17-19, 1992
• 7: Jawahar Chirimar , Carl A. Gunter , Jon G. Riecke, Proving memory management invariants for a language based on linear logic, Proceedings of the 1992 ACM conference on LISP and functional programming, p.139-150, June 22-24, 1992, San Francisco, California, United States
• 8: Friedman, D.P., and Wise, D.S. "Aspects of applicative programming for parallel processing". IEEE Trans. Comput. C-27, 4 (Apr. 1978), 289-296.
• 9: 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]
• 10: 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]
• 11: Hesselink, W.H. "Axioms and Models of Linear Logic". Formal Aspects of Comput. 2, 2 (Apt-June 1990), 139-166.
• 12: John Hogg, Islands: aliasing protection in object-oriented languages, ACM SIGPLAN Notices, v.26 n.11, p.271-285, Nov. 1991
• 13: Knuth, D.E. The Art of Computer Programming, v. 3, Sorting and Searching. Addison-Wesley, Reading, MA 1973.
• 14: 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]
• 15: Martí-Oliet, N., and Meseguer, J. "From Petri nets to linear logic". Math. Struct. in Comp. Sci. 1, 1 (Mar. 1991).
• 16: 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]
• 17: Shalit, A. Dylan^TM: An object-oriented dynamic language. Apple Computer, Camb., MA, 1992.
• 18: Robert E. Strom, Mechanisms for compile-time enforcement of security, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.276-284, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567093]
• 19: Norihisa Suzuki, Analysis of pointer “rotation”, Communications of the ACM, v.25 n.5, p.330-335, May 1982 [doi>10.1145/358506.358513]
• 20: 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
• 21: 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

INDEX TERMS

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

          Nouns: LISP

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Design, Languages, Theory