EUVIMEDEUVIMED entdecken
Crossref

A partial evaluator for the untyped lambda-calculus

Carsten K. Gomard, Neil D. Jones

Journal of Functional Programming · 1991

DOI: 10.1017/s0956796800000058 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Functional Programming, 1991. Verfasst von Carsten K. Gomard und 1 weiteren Autor:innen. Die Arbeit wurde bisher 87-mal zitiert (Crossref) und nennt 52 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This article describes theoretical and practical aspects of an implemented self-applicable partial evaluator for the untyped lambda-calculus with constants and a fixed point operator. To the best of our knowledge, it is the first partial evaluator that is simultaneously higher-order, non-trivial, and self-applicable. Partial evaluation produces a residual program from a source program and some of its input data. When given the remaining input data the residual program yields the same result that the source program would when given all its input data. Our partial evaluator produces a residual lambda-expression given a source lambda-expression and the values of some of its free variables. By self-application, the partial evaluator can be used to compile and to generate stand-alone compilers from a denotational or interpretive specification of a programming language. An essential component in our self-applicable partial evaluator is the use of explicit binding time information. We use this to annotate the source program, marking as residual the parts for which residual code is to be generated and marking as eliminable the parts that can be evaluated using only the data that is known during partial evaluation. We give a simple criterion, well-annotatedness, that can be used to check that the partial evaluator can handle the annotated higher-order programs without committing errors. Our partial evaluator is simple, is implemented in a side-effect free subset of Scheme, and has been used to compile and to generate compilers and a compiler generator. In this article we examine two machine-generated compilers and find that their structures are surprisingly natural.

Zitieren

APA

Gomard, C. K., & Jones, N. D. (1991). A partial evaluator for the untyped lambda-calculus. Journal of Functional Programming. https://doi.org/10.1017/s0956796800000058

Vancouver

Gomard CK, Jones ND. A partial evaluator for the untyped lambda-calculus. Journal of Functional Programming. 1991. doi:10.1017/s0956796800000058

BibTeX
@article{Gomard1991,
  author = {Gomard, Carsten K. and Jones, Neil D.},
  title = {A partial evaluator for the untyped lambda-calculus},
  journal = {Journal of Functional Programming},
  year = {1991},
  doi = {10.1017/s0956796800000058}
}
Kostenlos starten →