Automatic Improvement of Programs in Very High Level Languages.
Amelia C. Fong:
Automatic Improvement of Programs in Very High Level Languages.
POPL 1979: 21-28@inproceedings{DBLP:conf/popl/Fong79,
author = {Amelia C. Fong},
title = {Automatic Improvement of Programs in Very High Level Languages},
booktitle = {POPL},
year = {1979},
pages = {21-28},
ee = {db/conf/popl/Fong79.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
In this paper we study the profitability of applying the "reduction in strength" technique to programs in set-theoretic languages, focusing on the high level constructs involving set-formers.
We define recursively two classes of expressions we shall call inductively computable set-formers and inductively computable predicates which can be evaluated with an order of magnitude improvement of the asymptotic running time as compared to the straightforward evaluation.
The quantity developed for this comparison can be used to derive further results when additional information is known.
For programs written in very high level languages, which often consist mostly of "nested" iterative constructs, this technique amounts to altering the "algorithm" used to compute the program by replacing it with an asymptotically faster algorithm.
Copyright © 1979 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
POPL Proceedings Compendium
CDROM Version: Load the CDROM "POPL, The First Ten Years" and ...
BibTeX
Printed Edition
Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas, January 1979.
ACM 1979 BibTeX
Contents
Referenced by
- Françoise Fabret, Mireille Régnier, Eric Simon:
Optimizing Incremental Computation of Datalog Programs with Non-deterministic Semantics.
ICDT 1992: 155-170
BibTeX
Copyright © Sat May 16 23:34:34 2009
by Michael Ley (ley@uni-trier.de)