Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-28T19:48:26.689Z Has data issue: false hasContentIssue false
  • English
  • Français

Specifying the correctness of binding-time analysis

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 November 2008

Mitchell Wand
Mitchell Wand
Affiliation:
College of Computer Science, Northeastern University, 360 Huntington Avenue, 161CN, Boston, MA 02115, USA (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Mogensen has exhibited a very compact partial evaluator for the pure lambda calculus, using binding-time analysis followed by specialization. We give a correctness criterion for this partial evaluator and prove its correctness relative to this specification. We show that the conventional properties of partial evaluators, such as the Futamura projections, are consequences of this specification. By considering both a flow analysis and the transformation it justifies together, this proof suggests a framework for incorporating flow analyses into verified compilers.

Type
Articles
Information
Journal of Functional Programming , Volume 3 , Issue 3 , July 1993 , pp. 365 - 387
Copyright
Copyright © Cambridge University Press 1993

References

Barendregt, Henk. (1991) Self-interpretation in lambda calculus. Journal of functional programming, 1(2), 229–234.CrossRefGoogle Scholar
Clinger, William. (1984) (Aug.). The scheme 311 compiler: An exercise in denotational semantics. Pages 356–364of: Proc. 1984 ACM Symposium on Lisp and Functional Programming.CrossRefGoogle Scholar
Consel, Charles. (1990) Binding time analysis for higher order untyped functional languages. Pages 264–272of: Proc. 1990 ACM Symposium on Lisp and Functional Programming.CrossRefGoogle Scholar
Consel, Charles, & Khoo, Siau Cheng. (1992) (June). On-line & off-line partial evaluation: Semantic specifications and correctness proofs. Tech. rept. YALEU/DCS/RR-912. Yale University Department of Computer Science.Google Scholar
Gomard, Carsten K. (1990) Partial type inference for untyped functional programs. Pages 282–287of: Proc. 1990 ACM Symposium on Lisp and Functional Programming.CrossRefGoogle Scholar
Gomard, Carsten K. (1992) A self-applicable partial evaluator for the lambda calculus: Correctness and pragmatics. Acm transactions on programming languages and systems,14(2), 147–172.CrossRefGoogle Scholar
Henglein, Fritz. (1991) Efficient type inference for higher-order binding-time analysis. Pages 448–472of: Hughes, J. (ed), Functional programming languages and computer architecture, 5th acm conference. Lecture Notes in Computer Science, vol. 523. Berlin, Heidelberg, New York:Springer-Verlag.CrossRefGoogle Scholar
Hunt, Sebastian, & Sands, David. (1991) Binding time analysis: A new perspective. Pages 154–165of: Proceedings of the symposium on partial evaluation and semantics-based program manipulation. SIGPLAN Notices 26(9), September, 1991.Google Scholar
Jorring, U., & Scherlis, William L. (1986) Compilers and staging transformations. Pages 86–96of: Conf. Rec. 13th ACM Symposium on Principles of Programming Languages.CrossRefGoogle Scholar
Launchbury, John. (1989) (Nov.). Projection factorizations in partial evaluation. Ph.D. thesis, University of Glasgow.Google Scholar
Launchbury, John. (1991) A strongly-typed self-applicable partial evaluator. In: Hughes, John (ed), Functional programming languages and computer architecture, vol. 523. Berlin, Heidelberg, and New York: Springer-Verlag.CrossRefGoogle Scholar
Mogensen, Torben Æ. (1992a) (June). Efficient self-interpretation in lambda calculus. to appear.CrossRefGoogle Scholar
Mogensen, Torben Æ. (1992b) Self-applicable partial evaluation for pure lambda calculus. Pages 116–121of: Consel, Charles (ed), Acm sigplan workshop on partial evaluation and semantics-based program manipulation.Google Scholar
Nielson, Flemming, & Nielson, Hanne Riis. (1988) Two-level semantics and code generation. Theoretical computer science, 56, 59–133.CrossRefGoogle Scholar
Palsberg, Jens. (1993) Correctness of binding time analysis. Journal of functional programming, 11.Google Scholar
Pfenning, Frank, & Elliott, Conal. (1988) (June). Higher-order abstract syntax. Pages 199–208of: Proceedings sigplan ‘88 conference on programming language design and implementation.CrossRefGoogle Scholar
Wand, Mitchell. (1982) Deriving target code as a representation of continuation semantics. Acm transactions on programming languages and systems, 4(3), 496–517.CrossRefGoogle Scholar
Wand, Mitchell, & Oliva, Dino P. (1992) Proving the correctness of storage representations. Pages 151–160of: Proc. 1992 ACM Symposium on Lisp and Functional Programming.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.