Programs for cheap!

Hackett, Jennifer; Hutton, Graham

Abstract

Write down the definition of a recursion operator on a piece of paper. Tell me its type, but be careful not to let me see the operator’s definition. I will tell you an optimization theorem that the operator satisfies. As an added bonus, I will also give you a proof of correctness for the optimisation, along with a formal guarantee about its effect on performance. The purpose of this paper is to explain these tricks.

Citation

Hackett, J., & Hutton, G. (2015). Programs for cheap!. In Proceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (115-126). https://doi.org/10.1109/LICS.2015.21

• Conference Name: Thirtieth Annual ACM/IEEE Symposium on Logic in Computer Science
• Conference Location: Kyoto, Japan
• Start Date: Jul 6, 2015
• End Date: Jul 10, 2015
• Acceptance Date: Mar 30, 2015
• Online Publication Date: Jul 1, 2015
• Publication Date: Jul 1, 2015
• Deposit Date: Apr 8, 2016
• Publicly Available Date: Apr 8, 2016
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Volume: 2015-July
• Pages: 115-126
• Book Title: Proceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
• ISBN: 9781479988754
• DOI: https://doi.org/10.1109/LICS.2015.21
• Public URL: https://nottingham-repository.worktribe.com/output/982982
• Publisher URL: https://dl.acm.org/doi/abs/10.1109/LICS.2015.21
• Additional Information: Published in: 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) IEEE, 2015, pp. 115-126, doi: 10.1109/LICS.2015.21