The next 700 program transformers

DOI10.1007/978-3-030-98869-2_7MaRDI QIDQ6102254zbMATH OpenOpenAlexFDO

Authors G. W. Hamilton

Publication date 8 May 2023

Published in Logic-Based Program Synthesis and Transformation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.11347, http://doras.dcu.ie/27091/

zbMATH Keywords

supercompilationdistillationspeedupstransformation hierarchy

Mathematics Subject Classification ID

Theory of compilers and interpreters (68N20)

Abstract: In this paper, we describe a hierarchy of program transformers in which the transformer at each level of the hierarchy builds on top of those at lower levels. The program transformer at level 1 of the hierarchy corresponds to positive supercompilation, and that at level 2 corresponds to distillation. We prove that the transformers at each level terminate. We then consider the speedups that can be obtained at each level in the hierarchy, and try to characterise the improvements that can be made.

Recommendations

• scientific article; zbMATH DE number 3943000
• Convergence of program transformers in the metric space of trees
• The concept of a supercompiler
• Asymptotic speedups, bisimulation and distillation (work in progress)
• Program transformation and rewriting

Cites work

• scientific article; zbMATH DE number 3924119 (Why is no real title available?)
• scientific article; zbMATH DE number 3684895 (Why is no real title available?)
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• scientific article; zbMATH DE number 236855 (Why is no real title available?)
• A Transformation System for Developing Recursive Programs
• A positive supercompiler
• How powerful are folding/unfolding transformations?
• Loop checking in partial deduction
• Ordering by Divisibility in Abstract Algebras
• The Zipper
• The concept of a supercompiler
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture

Cited in

(3)

• Fission for Program Comprehension
• Extracting the essence of distillation
• Asymptotic speedups, bisimulation and distillation (work in progress)

This page was built for publication: The next 700 program transformers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6102254)