Deforestation: transforming programs to eliminate trees
Theoretical Computer SciencePublished 1 June 1990
Philip Wadler
Citations707
SJR quartileQ2
SJR score0.49
SNIP0.94
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The algorithm applies to any term containing only functions with definitions in a given syntactic form, and is suitable for incorporation in an optimizing compiler.
Abstract
An algorithm that transforms programs to eliminate intermediate trees is presented. The algorithm applies to any term containing only functions with definitions in a given syntactic form, and is suitable for incorporation in an optimizing compiler.
Keywords
Computer Science
Journal of Computer and System SciencesA theory of type polymorphism in programming
2,198 Citations1978Robin Milner
This work presents a formal type discipline for polymorphic procedures in the context of a simple programming language, and a compile time type-checking algorithm w which enforces the discipline.
Journal of the ACMA Transformation System for Developing Recursive Programs
1,316 Citations1977R. M. Burstall, John Darlington
A system of rules for transforming programs, with the programs in the form of recursion equations, are described, with an initially very simple, lucid, and hopefully correct program transformed into a more efficient one by altering the recursion structure.
Principal type-schemes for functional programs
1,096 Citations1982Lúıs Damas, Robin Milner
Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage.
Microprocessors and MicrosystemsThe implementation of functional programming languages
1,079 Citations1987
My 1987 book is now out of print, but it is available here in its entirety in PDF form, in one of two formats: single-page portrait double-page landscape and fully searchable, thanks to OCR and Norman Ramsey.
Transactions of the American Mathematical SocietyThe principle type-scheme of an object in combinatory logic
450 Citations1969Roger Hindley
Lecture notes in computer scienceCompiling pattern matching
176 Citations1985Lennart Augustsson
Only pattern matching in case expressions is described here, since the LML compiler project began as an attempt to produce efficient code for a typed functional language with lazy evaluation and it should also yield efficient code.
Listlessness is better than laziness
85 Citations1984Philip Wadler
One reason for interest in functional programming is that it is well-suited for program development by transformation: begin by writing a clear program, and transform this to an efficient program.
Experiments with a supercompiler
40 Citations1982Valentin F. Turchin, Robert M. Nirenberg +1 more
This paper presents and discusses some examples of the operation of the first experimental model of a supercompiler, and highlights most important features of the supercompilers and intimate its potential uses.
Lecture notes in computer scienceListlessness is better than laziness II: Composing listless functions
26 Citations1986Philip Wadler
The listless transformer applies only to programs from which all intermediate lists can be removed, and defines the class of programs that are subject to bounded evaluation (b.e. programs), that is, programs that can be lazily evaluated in constant bounded space.