Cormac Flanagan
Matthias Felleisen
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.
- 1.BAKER, H., AND HEWITT, C. The incremental garbage collection of processes. In Proceedings of the Symposium on Artzficzal Intelhgence and Programming Languages (1977), vol. 12(8), 55-59. Google Scholar
Digital Library
- 2.BBN ADVANCED COMPUTERS, INC., CAMBRIDGE, MA. Inszde the GPIO00. 1989.Google Scholar
- 3.CousoT, P., AND COUSOT, R. Abstract interpretation: A unified lattice model for static analyses of programs by consruction or approximation of fixpoints. In POPL (1977), 238-252. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 6.FEELEY, IV{. An Efficient and General Implementation of Futures on Large Scale Shared-Memory Multiprocessots. PhD thesis, Department of Computer Science, Brandeis University, 1993. Google ScholarDigital Library
- 7.FEELEY# M., AND MILLER# J. S. A parallel virtual machine for efficient scheme compilation. In LFP (1990). Google ScholarDigital Library
- 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.Google Scholar
- 9.FLANAGAN, C., AND FELLEISEN, Yr. The semantics of Future. Rice University Comp. Sci. TR94-238.Google Scholar
- 10.FLANAGAN, C., AND FELLEISEN, M. Well-founded touch optimization of Parallel Scheme. Rice University Comp. Sci. TR94-239.Google Scholar
- 11.FLANAGAN, C., SABRY, A., DUBA, B. F., AND FELLEISEN# M. The essence of compiling with continuations. In PLDI (1993), 237-247. Google ScholarDigital Library
- 12.HALSTEAD, R. Multilisp: A language for concurrent symbolic computataion. A CM Transactions on Programmzng Languages and Systems Z 4 (1985), 501-538. Google ScholarDigital Library
- 13.HEINTZE, N. Set Based Program Analyszs. PhD thesis, Carnegie Mellon University, 1992. Google ScholarDigital Library
- 14.HEINTZE, N. Set-based analysis of ML programs. In LFP (1994), 306-317. Google ScholarDigital Library
- 15.HENGLEIN, F. Global tagging optimization by type inference. In LFP (1992), 205-215. Google ScholarDigital Library
- 16.ITO, T., AND HALSTEAD, R., Eds. Parallel Lisp: Languages and Systems. Springer-Verlag Lecture Notes in Computer Science 441, 1989. Google ScholarDigital Library
- 17.ITO, T., AND MATSUI, M. A parallel lisp language: Pailisp and its kernel specification. {16:58-100l.Google Scholar
- 18.JACANNATHAN, S., AND WEEKS, S. Analyzing stores and references in a parallel symbolic language. In LFP (1994), 294-305. Google ScholarDigital Library
- 19.KATZ, M., AND WEISE, D. Continuing into the future: on the interaction of futures and first-class continuations. In LFP (1990). Google ScholarDigital Library
- 20.KESSLER, R.R., AND R. SWANSON. Concurrent scheme.Google Scholar
- 21.KNOPP, J. Improving the performance of parallel lisp by compile time analysis. {16:271-277}.Google Scholar
- 22.KrtANZ, D., HALSTEAD, R., AND MOHr#, E. Mul-T: A high-performance parallel lisp. {16:306-321}. Google ScholarDigital Library
- 23.KRANZ, D., HALSTEAD, R., AND MOHR, E. Mul-T: A high-performance parallel lisp. In PLDI (1989), 81-90. Google ScholarDigital Library
- 24.LEROY, X. Typage polymorphe d'un langage algorithm#que. PhD thesis, Universit# Paris 7, 1992.Google Scholar
- 25.MILLER, J. MultiScheme: A Parallel Processing System. PhD thesis, MIT, 1987.Google Scholar
- 26.MOHR, E., KRANZ, R., AND #IALSTEAD, R. Lazy task creation: A technique for increasing the granularity of parallel programs, in LFP (1990). Google ScholarDigital Library
- 27.MOREAU, L. Sound Evaluation of Parallel Functional Programs with Fwst-Class Continuations. PhD thesis, Universite de Liege, 1994.Google Scholar
- 28.REPPY, J.H. Hzgher-Order Concurrency. PhD thesis, Cornell University, Jan. 1992. Google ScholarDigital Library
- 29.SABRY, A., AND FELLEISEN# M. Is continuation-passing useful for data flow analysis. In PLDI (1994), 1-12. Google ScholarDigital Library
- 30.SHIVERS, O. Control-flow Analysis of Higher-Order Languages or Taming Lambda. PhD thesis, Carnegie- Mellon University, 1991. Google ScholarDigital Library
- 31.SwANsoN, M., KESSLER, R.# AND LINDSTROM, G. An implementation of portable standard lisp on the BBN butterfly. In LFP (1988), 132-142. Google ScholarDigital Library
- 32.WAND, M. Compiler correctness for parallel languages. Unpublished manuscript, 1995. Google ScholarDigital Library
- 33.WRIGHT, A. AND R. CARTWRIGHT. A practical soft type system for scheme. In LFP (1994), 250-262. Google ScholarDigital Library
Index Terms
- The semantics of future and its use in program optimization
Recommendations
Completing Herbelin's programme
TLCA'07: Proceedings of the 8th international conference on Typed lambda calculi and applicationsIn 1994 Herbelin started and partially achieved the programme of showing that, for intuitionistic implicational logic, there is a Curry-Howard interpretation of sequent calculus into a variant of the λ-calculus, specifically a variant which manipulates ...
Denotational semantics for a program logic of objects
The object-calculus is an imperative and object-based programming language in which every object comes equipped with its own method suite. Consequently, methods need to reside in the store (‘higher-order store’), which complicates the semantics. Abadi ...
Coinductive big-step operational semantics
Using a call-by-value functional language as an example, this article illustrates the use of coinductive definitions and proofs in big-step operational semantics, enabling it to describe diverging evaluations in addition to terminating evaluations. We ...
Comments