Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The Gabriel FRPOLY benchmark was rewritten in a "linear" fragment of Common Lisp and is competitive with the standard FRPOLY benchmark code. This linear FRPOLY is considerably more perspicuous than the standard code, while its running time is only 6% longer than that of the standard FRPOLY code. Linear FRPOLY recovers all of its garbage, and its "high water mark" space requirement is very probably smaller than that of the standard code. In the expansion of (x+y+z+1)¹⁵, the standard FRPOLY does 48,892 new conses, while the linear FRPOLY does only 4821 new conses---i.e., it does only about 10% of the consing of the standard FRPOLY code.We also tested versions of FRPOLY in which squarings were not used for exponentiation. This non-linear FRPOLY does 38,780 conses, and takes only 59% of the time of the non-linear squaring FRPOLY. The linear non-squaring FRPOLY takes only 62% of the time of the linear squaring FRPOLY, and cuts the new consing to 3988 cells. A slightly slower version cuts the new consing to 2590 cells---only 567 cells (28%) more than are used in the result.

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: 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]
• 3: 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]
• 4: 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 [doi>10.1145/141471.141527]
• 5: 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]
• 6: Fateman, R. "On the Computation of Powers of Sparse Polynomials". <i>Studies Appl. Math. 53</i>,2 (1974), 145--155.
• 7: Richard J. Fateman, FRPOLY: a benchmark revisited, Lisp and Symbolic Computation, v.4 n.2, p.155-164, April 1991 [doi>10.1007/BF01813018]
• 8: Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 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: Ian A. Mason, The semantics of destructive LISP, Center for the Study of Language and Information, Stanford, CA, 1987
• 11: Shalit, A. <i>Dylan&trade;: An object-oriented dynamic language.</i> Apple Computer, Camb., MA, 1992.
• 12: 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]
• 13: 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 [doi>10.1145/115865.115894]
• 14: 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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming
      I.2.5 Programming Languages and Software

          Nouns: LISP

General Terms:
Languages, Performance, Reliability, Theory