The semantics of future and its use in program optimization

ABSTRACT

The future annotations of MultiLisp provide a simple method for taming the implicit parallelism of functional programs. Past research concerning futures has focused on implementation issues. In this paper, we present a series of operational semantics for an idealized functional language with futures with varying degrees of intensionality. We develop a set-based analysis algorithm from the most intensional semantics, and use that algorithm to perform touch optimization on programs. Experiments with the Gambit compiler indicates that this optimization substantially reduces program execution times.

REFERENCES

• 1: Henry C. Baker, Jr. , Carl Hewitt, The incremental garbage collection of processes, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.55-59, August 15-17, 1977
• 2: BBN ADVANCED COMPUTERS, INC., CAMBRIDGE, MA. Inszde the GPIO00. 1989.
• 3: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 4: CoUSOT, P., AND COUSOT, R. Higer order abstract interpretation (and application to comportment analysis generalizing strictness, termination, projection and per analysis of functional languages. ICCL (1994), 95-112.
• 5: DEUTSCH, A. ModUles Opdrationnels de Language de Programmation et Reprdsentations de Relations sue des Languages Rationnels avec Applicatzon a la Ddtermination Statique de Propridtes de Partages Dynamiques de Donnges. PhD thesis# Universite Paris VI, 1992.
• 6: Marc Feeley, An efficient and general implementation of futures on large scale shared-memory multiprocessors, Brandeis University, Waltham, MA, 1993
• 7: Marc Feeley , James S. Miller, A parallel virtual machine for efficient scheme compilation, Proceedings of the 1990 ACM conference on LISP and functional programming, p.119-130, June 27-29, 1990, Nice, France [doi>10.1145/91556.91606]
• 8: FELLEISEN, M., AND FRIEDMAN, D. P. Control operators, the SECD-machine, and the Iambda-calculus. In 3rd Working Conference on the Formal Description of Programming Concepts (Aug. 1986), 193-219.
• 9: FLANAGAN, C., AND FELLEISEN, Yr. The semantics of Future. Rice University Comp. Sci. TR94-238.
• 10: FLANAGAN, C., AND FELLEISEN, M. Well-founded touch optimization of Parallel Scheme. Rice University Comp. Sci. TR94-239.
• 11: Cormac Flanagan , Amr Sabry , Bruce F. Duba , Matthias Felleisen, The essence of compiling with continuations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.237-247, June 21-25, 1993, Albuquerque, New Mexico, United States
• 12: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 13: Nevin Charles Heintze, Set based program analysis, Carnegie Mellon University, Pittsburgh, PA, 1992
• 14: Nevin Heintze, Set-based analysis of ML programs, Proceedings of the 1994 ACM conference on LISP and functional programming, p.306-317, June 27-29, 1994, Orlando, Florida, United States
• 15: Fritz Henglein, Global tagging optimization by type inference, Proceedings of the 1992 ACM conference on LISP and functional programming, p.205-215, June 22-24, 1992, San Francisco, California, United States
• 16: Proceedings of the US/Japan workshop on Parallel Lisp on Parallel Lisp: languages and systems, June 1990
• 17: ITO, T., AND MATSUI, M. A parallel lisp language: Pailisp and its kernel specification. {16:58-100l.
• 18: Suresh Jagannathan , Stephen Weeks, Analyzing stores and references in a parallel symbolic language, Proceedings of the 1994 ACM conference on LISP and functional programming, p.294-305, June 27-29, 1994, Orlando, Florida, United States
• 19: Morry Katz , Daniel Weise, Continuing into the future: on the interaction of futures and first-class continuations, Proceedings of the 1990 ACM conference on LISP and functional programming, p.176-184, June 27-29, 1990, Nice, France [doi>10.1145/91556.91628]
• 20: KESSLER, R.R., AND R. SWANSON. Concurrent scheme.
• 21: KNOPP, J. Improving the performance of parallel lisp by compile time analysis. {16:271-277}.
• 22: KrtANZ, D., HALSTEAD, R., AND MOHr#, E. Mul-T: A high-performance parallel lisp. {16:306-321}.
• 23: D. A. Kranz , R. H. Halstead, Jr. , E. Mohr, Mul-T: a high-performance parallel Lisp, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.81-90, June 19-23, 1989, Portland, Oregon, United States
• 24: LEROY, X. Typage polymorphe d'un langage algorithm#que. PhD thesis, Universit# Paris 7, 1992.
• 25: MILLER, J. MultiScheme: A Parallel Processing System. PhD thesis, MIT, 1987.
• 26: Eric Mohr , David A. Kranz , Robert H. Halstead, Jr., Lazy task creation: a technique for increasing the granularity of parallel programs, Proceedings of the 1990 ACM conference on LISP and functional programming, p.185-197, June 27-29, 1990, Nice, France [doi>10.1145/91556.91631]
• 27: MOREAU, L. Sound Evaluation of Parallel Functional Programs with Fwst-Class Continuations. PhD thesis, Universite de Liege, 1994.
• 28: John Hamilton Reppy, Higher-order concurrency, Cornell University, Ithaca, NY, 1992
• 29: Amr Sabry , Matthias Felleisen, Is continuation-passing useful for data flow analysis?, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.1-12, June 20-24, 1994, Orlando, Florida, United States
• 30: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 31: Mark Swanson , Robert Kessler , Gary Lindstrom, An implementation of portable standard LISP on the BBN butterfly, Proceedings of the 1988 ACM conference on LISP and functional programming, p.132-142, July 25-27, 1988, Snowbird, Utah, United States [doi>10.1145/62678.62694]
• 32: WAND, M. Compiler correctness for parallel languages. Unpublished manuscript, 1995.
• 33: Andrew K. Wright , Robert Cartwright, A practical soft type system for Scheme, Proceedings of the 1994 ACM conference on LISP and functional programming, p.250-262, June 27-29, 1994, Orlando, Florida, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics
      D.3.2 Language Classifications

          Nouns: MULTILISP

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics

General Terms:
Algorithms, Experimentation, Languages, Theory