|
 ABSTRACT
When some inputs of a program are known at compile-time, certain expressions can be processed statically; this is the basis of the notion of partial evaluation. Identifying these early computations can be determined independently of the actual values of the input by a static analysis called binding time analysis. Then, to process a program, one simply follows the binding time information: evaluate compile-time expressions and defer the others to run-time.
Using abstract interpretation, we present a binding time analysis for an untyped functional language which provides an effective treatment of both higher order functions and data structures. To our knowledge it is the first such analysis. It has been implemented and is used in a partial evaluator for a side-effect free dialect of Scheme. The analysis is general enough, however, to be valid for non-strict typed functional languages such as Haskell. Our approach and the system we have developed solve and go beyond the open problem of partially evaluating higher order functions described in [3] since we also provide a method to handle data structures.
Our analysis improves on previous work [5, 15, 4] in that: (1) it treats both higher order functions and data structures, (2) it does not impose syntactic restrictions on the program being processed, and (3) it does not require a preliminary phase to collect the set of possible functions that may occur at each site of application.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
|
| |
3
|
D. Bj0rner, A. P. Ershov, and N. D. Jones, editors. Partial Evaluation and Mixed Computation. North-Holland, 1988.
|
| |
4
|
|
| |
5
|
A. Bondorf, N. D. Jones, T. Mogensen, and P. Sestoft. Binding time analysis and the taming of self-application. Diku report, University of Copenhagen, Copenhagen, Denmark, 1988.
|
| |
6
|
|
| |
7
|
C. Consel. Analyse de Programmes, Evaluation Partielle ei Generation de Compilateurs. PhD thesis, Universit~ de Paris VI, Paris, France, 1989.
|
| |
8
|
C. Consel and O. Danvy. Static and dynamic semantics processing. Research Report 761, Yale University, New Haven, Connecticut, USA, 1989.
|
| |
9
|
|
 |
10
|
|
| |
11
|
|
| |
12
|
N. D. Jones and S. S. Muchnick. Flow analysis and optimization of lisp-like structures. In S. S. Muchnick and N. D. Jones, editors, Program Flow Analysis: Theory and Applications. Prentice-Hall, 1981.
|
| |
13
|
|
| |
14
|
N. D. Jones, P. Sestoft, and H. S0ndergaard. Mix: a self-applicable partial evaluator for experiments in compiler generation. Lisp and Symbolic Computation, 2:9-50, 1989.
|
| |
15
|
T. Mogensen. Partially static structures in a selfapplicable partial evaluator. In D. Bjorner, A. P. Ershov, and N. D. Jones, editors, Partial Evaluation and Mixed Compuiaiion, pages 325-348. North-Holland, 1988.
|
| |
16
|
|
| |
17
|
|
| |
18
|
|
| |
19
|
|
| |
20
|
|
| |
21
|
|
CITED BY 30
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Brian N. Bershad , Craig Chambers , Susan Eggers , Chris Maeda , Dylan McNamee , Przemysław Pardyak , Stefan Savage , Emin Gün Sirer, SPIN—an extensible microkernel for application-specific operating system services, ACM SIGOPS Operating Systems Review, v.29 n.1, p.74-77, Jan. 1995
|
|
|
Martín Abadi , Anindya Banerjee , Nevin Heintze , Jon G. Riecke, A core calculus of dependency, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.147-160, January 20-22, 1999, San Antonio, Texas, United States
|
|
|
Brian N. Bershad , Craig Chambers , Susan Eggers , Chris Maeda , Dylan McNamee , Przemyslaw Pardyak , Stefan Savage , Emin Gün Sirer, SPIN: an extensible microkernel for application-specific operating system services, Proceedings of the 6th workshop on ACM SIGOPS European workshop: Matching operating systems to application needs, September 12-14, 1994, Wadern, Germany
|
|
|
|
|
|
|
|
|
Charles Consel , Calton Pu , Jonathan Walpole, Incremental partial evaluation: the key to high performance, modularity and portability in operating systems, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.44-46, June 14-16, 1993, Copenhagen, Denmark
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michael Sperber , Robert Glück , Peter Thiemann, Bootstrapping higher-order program transformers from interpreters, Proceedings of the 1996 ACM symposium on Applied Computing, p.408-413, February 17-19, 1996, Philadelphia, Pennsylvania, United States
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.3