Article

Free access

Loops in combinator-based compilers

Author:

Mitchell WandAuthors Info & Claims

POPL '83: Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

Pages 190 - 196

https://doi.org/10.1145/567067.567086

Published: 24 January 1983 Publication History

PDF eReader

Abstract

In our paper [Wand 82a], we introduced a paradigm for compilation based on combinators. A program from a source language is translated (via a semantic definition) to trees of combinators; the tree is simplified (via associative and distributive laws) to a linear, assembly-language-like format: the "compiler writer's virtual machine" operates by simulating a reduction sequence of the simplified tree. The correctness of these transformations follows from general results about the λ-calculus. The code produced by such n generator is always tree-like. In this paper, the method is extended to produce target code with explicit loops. This is done by re-introducing variables into the terms of the target language in a restricted way, along with a structured binding operator.

References

[1]

{Barendregt 81} Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics, North-Holland, Amsterdam, 1981.

Google Scholar

[2]

{Milne & Strachey 76} Milne, R. and Strachey C. A Theory of Programming Language Semantics Chapman & Hall, London, and Wiley, New York, 1976

Digital Library

Google Scholar

[3]

{Raskovsky & Collier 80} Raskovsky, M. and Collier, P. "From Standard to Implementation Denotational Semantics" in Semantics-Directed Compiler Generation (N. D. Jones, ed.) Lecture Notes in Computer Science, Vol. 94, Springer, Berlin, 1980.

Digital Library

Google Scholar

[4]

{Sethi 81} Sethi, R. "Circular Expressions: elimination of static environments" Automata, Languages, and Programming, 8th Colloquium, Acre Lecture Notes in Computer Science, Vol. 115, Springer, Berlin, 1981.

Digital Library

Google Scholar

[5]

{Sethi 82} Sethi, R. "Control Flow Aspects of Semantics Directed Compiling" Proc. SIGPLAN '82 Symposium on Compiler Construction (Boston, 1982) SIGPLAN Notices 17, 6 (June, 1982), 245-260.

Digital Library

Google Scholar

[6]

{Thatcher et al. 81} Thatcher, J. W., Wagner, E. G., and Wright, J. B. "More on Advice on Structuring Compilers and Proving Them Correct" Theoret. Comp. Sci. 15 (1981), 223-250.

Crossref

Google Scholar

[7]

{Turing 37} Turing, A. M. "The p-functions in λ-K-conversion" J. Symbolic Logic 2 (1937), 164.

Crossref

Google Scholar

[8]

{Turner 79} Turner, D. A. "A New Implementation Technique for Applicative Languages" Software-Practice and Experience 9 (1979), 31-49.

Crossref

Google Scholar

[9]

{Wand 80} Wand, M. "Different Advice on Structuring Compilers and Proving Them Correct", Indiana University Computer Science Department Technical Report No. 95 (September, 1980).

Google Scholar

[10]

{Wand 82a} Wand, M. "Semantics-Directed Machine Architecture" Conf. Rec. 9th ACM Symp. on Principles of Prog. Lang. (1982), 234-241.

Digital Library

Google Scholar

[11]

{Wand 82b} Wand, M. "Deriving Target Code as a Representation of Continuation Semantics" ACM Trans. on Prog. Lang. and Systems 4, 3 (July, 1982) 496-517.

Digital Library

Google Scholar

Cited By

View all

Amin NBurnham JGarillot FGennaro RKünzang CRogozin DWong C(2023)LURK: Lambda, the Ultimate Recursive Knowledge (Experience Report)Proceedings of the ACM on Programming Languages10.1145/36078397:ICFP(259-274)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607839
Asai KKitani AKutsia TSchreiner WFernández M(2010)Functional derivation of a virtual machine for delimited continuationsProceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming10.1145/1836089.1836101(87-98)Online publication date: 26-Jul-2010
https://dl.acm.org/doi/10.1145/1836089.1836101
Giorgi JMétayer D(2009)Continuation-based compilation of functional languages for parallel machinesMathematical Structures in Computer Science10.1017/S09601295000015472:04(393)Online publication date: 4-Mar-2009
https://doi.org/10.1017/S0960129500001547
Show More Cited By

Index Terms

Loops in combinator-based compilers

Recommendations

Metaprogramming with combinators
GPCE 2021: Proceedings of the 20th ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences

There are a wide array of methods for writing code generators. We advocate for a point in the design space, which we call metaprogramming with combinators, where programmers use (and write) combinator libraries that directly manipulate object language ...
Combinators and type-driven transformers in Objective Caml

We describe an implementation of LDTA 2011 Tool Challenge tasks in Objective Caml language. Instead of using some dedicated domain-specific tools we utilize typical functional programming machinery such as polymorphic functions, monads and combinators; ...
Surgical precision JIT compilers
PLDI '14

Just-in-time (JIT) compilation of running programs provides more optimization opportunities than offline compilation. Modern JIT compilers, such as those in virtual machines like Oracle's HotSpot for Java or Google's V8 for JavaScript, rely on dynamic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

POPL '83: Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

January 1983

312 pages

ISBN:0897910907

DOI:10.1145/567067

Conference Chairs:
John R. White
Xerox PARC, Palo Alto, CA
,
Larry Landweber
University of Wisconsin, Madison, Wisconsin
,
Program Chairs:
Alan Demers
Cornell University, Ithaca, NY
,
Tim Teitelbaum
Cornell University, Ithaca, NY

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 January 1983

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

POPL '83 Paper Acceptance Rate 28 of 170 submissions, 16%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
304
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)5

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Amin NBurnham JGarillot FGennaro RKünzang CRogozin DWong C(2023)LURK: Lambda, the Ultimate Recursive Knowledge (Experience Report)Proceedings of the ACM on Programming Languages10.1145/36078397:ICFP(259-274)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607839
Asai KKitani AKutsia TSchreiner WFernández M(2010)Functional derivation of a virtual machine for delimited continuationsProceedings of the 12th international ACM SIGPLAN symposium on Principles and practice of declarative programming10.1145/1836089.1836101(87-98)Online publication date: 26-Jul-2010
https://dl.acm.org/doi/10.1145/1836089.1836101
Giorgi JMétayer D(2009)Continuation-based compilation of functional languages for parallel machinesMathematical Structures in Computer Science10.1017/S09601295000015472:04(393)Online publication date: 4-Mar-2009
https://doi.org/10.1017/S0960129500001547
Wand M(2005)Correctness of procedure representations in higher-order assembly languageMathematical Foundations of Programming Semantics10.1007/3-540-55511-0_15(294-311)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-55511-0_15
Wand M(2005)From interpreter to compiler: A representational derivationPrograms as Data Objects10.1007/3-540-16446-4_17(306-324)Online publication date: 29-May-2005
https://doi.org/10.1007/3-540-16446-4_17
Giorgi JLe Métayer DKahn G(1990)Continuation-based parallel implementation of functional programming languagesProceedings of the 1990 ACM conference on LISP and functional programming10.1145/91556.91648(209-217)Online publication date: 1-May-1990
https://dl.acm.org/doi/10.1145/91556.91648
Cartwright RFelleisen M(1989)The semantics of program dependenceACM SIGPLAN Notices10.1145/74818.7482024:7(13-27)Online publication date: 21-Jun-1989
https://dl.acm.org/doi/10.1145/74818.74820
Cartwright RFelleisen M(1989)The semantics of program dependenceProceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation10.1145/73141.74820(13-27)Online publication date: 21-Jun-1989
https://dl.acm.org/doi/10.1145/73141.74820
Clinger WBoyer RSchneider ESteele G(1984)The scheme 311 compiler an exercise in denotational semanticsProceedings of the 1984 ACM Symposium on LISP and functional programming10.1145/800055.802052(356-364)Online publication date: 6-Aug-1984
https://dl.acm.org/doi/10.1145/800055.802052
Wand MKennedy KVan Deusen MLandweber L(1984)A types-as-sets semantics for milner-style polymorphismProceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages10.1145/800017.800527(158-164)Online publication date: 15-Jan-1984
https://dl.acm.org/doi/10.1145/800017.800527
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Metaprogramming with combinators

Combinators and type-driven transformers in Objective Caml

Surgical precision JIT compilers