Abstract: In our work this summer, we addressed the relative lack of knowledge surrounding cost analysis of lazy programs relative to strict programs. The cost of a program can be defined in many different manners, but generally it corresponds with the amount of time required to complete operations in a computer program and it allows the programmer to get a sense of the efficiency of their code. In strict programming, which is used by the majority of programming languages, evaluation is conducted immediately, whereas lazy programming stores expressions until evaluation is seen to be necessary for the result of the program. Laziness provides the programmer with several advantages, such as better termination, faster evaluation, and a convenient mechanism to work with infinite data structures. However, it becomes much more difficult to reason about the operations and efficiency of a lazy program than a strict program due to the fact that evaluation does not always occur immediately or even at all. Thus, we worked to develop a parser and interpreter that enabled us to track the cost of a program. Using an example program, we demonstrated that Hackett and Hutton’s clairvoyant call by value approach to lazy cost analysis can be applied to extracting cost recurrences from lazy programs. Clairvoyance provides us with a set of semantic rules that allow us to see whether an evaluation is necessary for the end result of a program. Thus, we can immediately conduct evaluation if needed and otherwise, the expression will be discarded. Looking ahead, we hope to further extend Hackett and Hutton’s findings to allow for a more formalized approach to the derivation of cost recurrences from lazy programs.
Video:
Live Poster Session:
Thursday, July 29th 1:15-2:30pm EDT