Logo image
Back
The Stack as a Zipper: An Improved Baseline for Algebraic Effect Handlers
Thesis

The Stack as a Zipper: An Improved Baseline for Algebraic Effect Handlers

Hunter Alan Smith
Master of Science (MS), Washington State University
2026
pdf
The_Stack_as_a_Zipper_An_Improved_Baseline_for_Algebraic_Effect_Handlers_FinalDownloadView
Open Access

Abstract

Algebraic effects and effect handlers have gained popularity as a means of writing programs which implement modular control mechanisms such as exceptions, threads, co-routines, web servers, and non-determinism, in a mostly functional programming paradigm. Effect handlers may be operationally modeled and implemented via systems for first-class delimited control, which provides a sufficient basis for integration into a functional language. Many research languages and implementations of algebraic effect handlers exist, and focus on optimizing common idioms for effect handlers. These languages typically implement the baseline for general effect-handler operations with a linear complexity in the number of available handlers. In this work, we propose a system for delimited control that adheres to a model of the stack as fundamentally a Zipper: not a true stack anymore, but a sequence with a focus that no longer need be at the end of the sequence. Our system replaces Felleisen's prompt and control with prompt, prompt call, and prompt yield operators, for moving the Zipper's focus leftward to call a prompt, or rightward to yield back into subordinate code. By implementing the stack as a Zipper-style balanced tree structure, we are able to optimize the baseline complexity for handling an arbitrary dynamic effect call to a logarithmic bound, and show that this optimization improves the worst-case performance for highly effectful programs in a Scheme prototype implementation.

Metrics

1 Record Views

Details

Logo image