ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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

Online Edition: ACM Digital Library


Referenced by

  1. 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)