-
Notifications
You must be signed in to change notification settings - Fork 6
Abstracts.2020.Improvement.Theory
by David Sands
One program fragment is an improvement of another if its execution is more efficient in any program context. Improvement theory can be used to prove that transformations always do good; more surprisingly, it provides new proof techniques to establish the correctness of program transformations even if you don't care about efficiency. Improvement theory provides a rich theoretical foundation for understanding call-by-need (the evaluation mechanism of Haskell), including the thorny problem of space efficiency. In this talk we give an overview of our work on the theory and applications of improvement and a brief review of the recent revival in interest in improvement theory.
David Sands. Total correctness by local improvement in the transformation of functional programs. ACM Transactions on Programming Languages and Systems (TOPLAS), 18(2):175-234, March 1996. Extended version of [POPL'95]. [ bib | pdf ]
David Sands. Improvement theory and its applications. In A. D. Gordon and A. M. Pitts, editors, Higher Order Operational Techniques in Semantics, Publications of the Newton Institute, pages 275-306. Cambridge University Press, 1998. [ bib | pdf | Abstract ]
A. K. Moran and David Sands. Improvement in a lazy context: An operational theory for call-by-need. In Proc. POPL'99, the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 43-56. ACM Press, January 1999. [ bib | pdf ]
J. Gustavsson and David Sands. A foundation for space-safe transformations of call-by-need programs. In A. D. Gordon and A. M.Pitts, editors, The Third International Workshop on Higher Order Operational Techniques in Semantics, volume 26 of Electronic Notes in Theoretical Computer Science. Elsevier, 1999. [ bib | pdf | Abstract ]
Jörgen Gustavsson and David Sands. Possibilities and limitations of call-by-need space improvement. In Proceeding of the Sixth ACM SIGPLAN International Conference on Functional Programming (ICFP'01), pages 265-276. ACM Press, September 2001. [ bib | pdf | Abstract ]
Jennifer Hackett and Graham Hutton. Parametric polymorphism and operational improvement. Proceedings of the ACM on Programming Languages, Volume 2, Issue ICFP, Article 68, September 2018. [ bib | pdf ]
Martin Handley and Graham Hutton. Improving Haskell. Proceedings of the Symposium on Trends in Functional Programming, Gothenburg, Sweden, March 2018. [ bib | pdf ]
Jennifer Hackett and Graham Hutton. Programs for cheap! Proceedings of the Thirtieth Annual ACM/IEEE Symposium on Logic in Computer Science, Kyoto, Japan, July 2015. [ bib | pdf ]
Jennifer Hackett and Graham Hutton. Worker/wrapper/makes it/faster. Proceedings of the 19th ACM SIGPLAN International Conference on Functional Programming, Gothenburg, Sweden, September 2014. [ bib | pdf ]