Article

Free access

Partial evaluation of call-by-value λ-calculus with side-effects

Authors:

Hidehiko Masuhara,

Akinori YonezawaAuthors Info & Claims

PEPM '97: Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation

Pages 12 - 21

https://doi.org/10.1145/258993.258997

Published: 01 December 1997 Publication History

Abstract

We present a framework of an online partial evaluator for a call-by-value λ-calculus with destructive updates of data structures. It properly and correctly specializes expressions that contain side-effects, while preserving pointer equality, which is an important property for programs using updates. Our partial evaluator uses a side-effect analysis to extract immutable data structures and then performs an online specialization using preactions. Once mutable and immutable data structures are separated, partial evaluation is done in such a way that accesses to immutable ones are performed at specialization time, while accesses to mutable ones are residualized. For the correct residualization of side-effecting operations, preactions are used to solve various issues, including code elimination, code duplication, and execution order preservation. The preaction mechanism also enables us to reduce expressions that were residualized when the conventional let-expression approach of Similix was used. The resulting partial evaluator is simple enough to prove its correctness. Based on the framework, we have constructed a partial evaluator for Scheme, which is powerful enough to specialize fairly complicated programs with side-effects, such as an interpreter.

References

[1]

Andersen, L. O. Progratn Analysis and Specializatton for the C Programmi, tg Language, Ph.D. thesis, DIKU, University of Copenhagen (May 1994).

[2]

Asai, K., H. Masuhara. and A. Yonezawa "Partial Evaluation of Call-by-value A-calculus with Side-effects" Technical report of Department of Information Science, University of Tokyo, 96-04 (November 1996).

[3]

Asai, K., S. Matsuoka, and A. Yonezawa "Duplication and Partial Evaluation- For a Better Understanding of Reflective Languages "' Lisp and Symbolic Computation, Vol. 9, Nos. 2/3, pp. 203-241, Kluwer Academic Publishers (May/June 1996).

Digital Library

[4]

Baler, R., R. Gltick, and R. ZOchling "Partial Evaluation of Numerical Programs in Fortran" ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM "94), pp. 119-132 (June 1994).

[5]

Bondorf, A., and O. Danvy "Automatic autoprojection of recursive equations with global variables and abstract data types," Science of Computer Programming, Vol. 16, pp. 151- 195, Elsevier (1991).

Digital Library

[6]

Clinger, W., and Rees, J. (editors) "Revised4 Report on the Algorithmic Language Scheme", LISP Pointers, Vol. IV, No. 3, pp. 1-55 (July-September 1991).

Digital Library

[7]

Consel, C. "New Insights into Partial Evaluation: the SCHISM Experiment," ESOP'88, 2nd European Symposium on Programmmg (LNCS 300), pp. 236-246 (March } 988).

Digital Library

[8]

Consel, C. "Binding Time Analysis for Higher Order Untyped Functional Languages," Proceedings of the 1990 ACM Conference on Lisp and Functional Programming, pp. 264-272 (June 1990).

Digital Library

[9]

Consel, C. "A Tour of Schism: A Partial Evaluation System for Higher-Order Applicative Languages" Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'93), pp. 145-154 (June 1993).

Digital Library

[10]

Dean, J., C. Chambers, and D. Grove "Identifying Profitable Specialization in Object-Oriented Languages," ACM SIGPLAN Workshop on Partial Evaluation and Semantics- Based Program Manipulation (PEPM "94), pp. 85-96 (June 1994).

[11]

Dussart, D., and P. Thiemann "Partial Evaluation for Higher- Order Languages with State," Submitted for publication (1996).

[12]

Heintze, N. "Set-Based Analysis of ML Programs," Proceedings of the 1994 ACM Conference on Lisp and Functional Programming, pp. 306-317 (June ! 994).

Digital Library

[13]

Jones, N. D., C. K. Gomard, and P. Sestoft Partial Evaluation andAutomatic Program Generation, New York: Prentice-Hall (1993).

Digital Library

[14]

Masuhara, H. et al. "'A simple mechanism to handle l/O-type side-effects in on-line partial evaluators," in preparation.

[15]

Masuhara. H., S. Matsuoka, K. Asai. and A. Yonezawa"Compiling Away the Meta-Level in Object-Oriented Concurrent Reflective Languages Using Partial Evaluation," Tenth Annual Conference of Object-Oriented P,vgramming Systems, Languages, and Applications (OOPSLA '95), pp. 300-315, (.October 1995).

Digital Library

[16]

Meyer, U. "Techniques for partial evaluation of imperative languages," Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM '91), pp. 94-105 (June 1991).

Digital Library

[17]

Mogensen, T.,E. "Partially Static Structures in a Self- Applicable Partial Evaluator," In D. Bjc~mer, A. P. Ershov, and N. D. Jones editors, Partial Evaluation and Mixed Computation, Elsevier Science Publishers, pp. 325-347 (1988).

[18]

Mogensen, T. ~. "Separating Binding Times in Language Specifications," Proceedings of the Fourth International Conference on Functional Programming Languages and Computer Architecture (FPCA'89), pp. 12-25 (September 1989).

Digital Library

[19]

Orb~ek, R "POPE: An On-line Partial Evaluator," available from ftp://ftp, daimi, aau. dk/pub/empl/poe/pope, p s. gz (June 1994).

[20]

Ruf, E. Topics in Online Partial Evaluation, Ph.D. thesis, Stanford University (March 1993). Also published as Stanford Computer Systems Laboratory technical report CSL-TR-93- 563.

Digital Library

[21]

Shivers, O. "Control Flow Analysis in Scheme," Proceedings of the ACM SIGPLAN '88 Conference on Programming Language Design and Implementation (PLDI), pp. 164-174 (June 1988).

Digital Library

[22]

Sperber, M., and P. Thiemann "'The Essence of LR Parsing," Proceedings of the Symposium on Partial Evaluation and Semantics-Based Program Manipulation ( PEPM'95), pp. 146-155 (June 1995).

Digital Library

[23]

Thiemann, P. "Towards Partial Evaluation of Full Scheme," Proceedings of Reflection'96, pp. 105-115 (April 1996).

[24]

Weise, D., R. Conybeare, E. Rut', and S. Seligman "Automatic Online Partial Evaluation," In J. Hughes, editor, Functional Programmblg Languages and Computer Architecture (LNCS 523), pp. 165-191 (August 1991).

Digital Library

[25]

Weise, D., and S. Seligman "Accelerating Object-Oriented Simulation via Automatic Program Specialization," Technical Report of Computer Systems Laboratory, Stanford University, CSL-TR-92-519 (also FUSE Memo 92-10), (April 1992).

Cited By

Shaikhha AKlonatos YParreaux LBrown LDashti MKoch CÖzcan FKoutrika GMadden S(2016)How to Architect a Query CompilerProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2915244(1907-1922)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2915244
Wang WRaghunathan ALakshminarayana GJha N(2006)Input space-adaptive optimization for embedded-software synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2005.85228224:11(1677-1693)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TCAD.2005.852282
Chepovsky AKlimov AKlimov AKlimov YMishchenko ARomanenko SSkorobogatov S(2004)Partial Evaluation for Common Intermediate LanguagePerspectives of System Informatics10.1007/978-3-540-39866-0_19(171-177)Online publication date: 2004
https://doi.org/10.1007/978-3-540-39866-0_19
Show More Cited By

Index Terms

Recommendations

Partial evaluation of call-by-value λ-calculus with side-effects

We present a framework of an online partial evaluator for a call-by-value λ-calculus with destructive updates of data structures. It properly and correctly specializes expressions that contain side-effects, while preserving pointer equality, ...
Model Predictive Control for Partial Differential Equations
ERP Value: Signifikante Vorteile mit ERP-Systemen (Xpert.press)

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM '97: Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation

December 1997

217 pages

ISBN:0897919173

DOI:10.1145/258993

Chairmen:
John Gallagher
Univ. of Bristol
,
Charles Consel
Univ. of Rennes/Irisa
,
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ

ACM SIGPLAN Notices Volume 32, Issue 12
Dec. 1997
217 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/258994
Chairmen:
John Gallagher
Univ. of Bristol
,
Charles Consel
Univ. of Rennes/Irisa
,
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ
Issue’s Table of Contents

Copyright © 1997 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PEPM97

Sponsor:

SIGPLAN

PEPM97: Symposium on Partial Evaluation and Semantics-Based Program Manipulation

June 12 - 13, 1997

Amsterdam, The Netherlands

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
345
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)9

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shaikhha AKlonatos YParreaux LBrown LDashti MKoch CÖzcan FKoutrika GMadden S(2016)How to Architect a Query CompilerProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2915244(1907-1922)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2915244
Wang WRaghunathan ALakshminarayana GJha N(2006)Input space-adaptive optimization for embedded-software synthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2005.85228224:11(1677-1693)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TCAD.2005.852282
Chepovsky AKlimov AKlimov AKlimov YMishchenko ARomanenko SSkorobogatov S(2004)Partial Evaluation for Common Intermediate LanguagePerspectives of System Informatics10.1007/978-3-540-39866-0_19(171-177)Online publication date: 2004
https://doi.org/10.1007/978-3-540-39866-0_19
Asai K(2001)Integrating partial evaluators into interpretersProceedings of the 2nd international conference on Semantics, applications, and implementation of program generation10.5555/1792034.1792044(126-145)Online publication date: 6-Sep-2001
https://dl.acm.org/doi/10.5555/1792034.1792044
Asai K(1999)Binding-Time Analysis for Both Static and Dynamic ExpressionsStatic Analysis10.1007/3-540-48294-6_8(117-133)Online publication date: 1-Oct-1999
https://doi.org/10.1007/3-540-48294-6_8
Shaikhha AKlonatos YParreaux LBrown LDashti MKoch CÖzcan FKoutrika GMadden S(2016)How to Architect a Query CompilerProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2915244(1907-1922)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2915244
Asai K(2001)Integrating Partial Evaluators into InterpretersSemantics, Applications, and Implementation of Program Generation10.1007/3-540-44806-3_8(126-145)Online publication date: 3-Sep-2001
https://doi.org/10.1007/3-540-44806-3_8

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents