Optimal Effects
When evaluating functional programs, there are various strategies for reducing expressions. A strategy is Lévy-optimal if it never does unnecessary work such as duplicating terms that are later erased. To implement this efficiently, graphical representations like Interaction Nets can be used to encode the sharing of duplicated terms. Beyond optimality, Interaction Nets provide elegant solutions for parallelization and distributed computing, making them an attractive backend for programming languages. Side effects such as file I/O are rarely discussed in the context of optimal reduction, despite their necessity for real-world applications. In this thesis, we will therefore analyze and formalize existing implementations, and design and implement an optimal runtime with side effects.