Optimizing algebraic programs
Tim Sheard · 2018
This paper considers a programming language where all control is encoded in algebras and combinators over algebras. This language supports higher levels of abstraction than traditional functional languages and is amenable to calculation based optimization. Three well known transformations are illustrated. Each one, requiring varying levels of insight and creativity over ordinary functional programs, can be fully automated in an algebraic language. The algorithm encoding these transformations is presented. This algorithm is an improvement over our previous work since it works over a richer, more expressive language, encodes more transformations, and is more efficient. 1 Introduction We have developed a programming style we call algebraic programming because of its reliance on algebras and combinators for encoding control. Algebraic programs provide two advantages over traditional functional programs. First, they provide a mechanism for abstracting over type constructors, i.e. it is pos...