Abstract:
Koka is a functional programming language with native support for algebraic effects and handlers. To implement effect handler operations efficiently, Koka employs a semantics where the handlers in scope are passed down to each function as an evidence vector. At runtime, these evidence vectors are adjusted using the open constructs to match the evidence for a particular function. All these adjustments can cause significant runtime overhead. In this paper, we present a novel transformation on the Koka core calculus that we call open floating. This transformation aims to float up open constructs and combine them in order to minimize the adjustments needed at runtime. Open floating improves performance by 2.5 times in an experiment. Furthermore, we formalize an aspect of row-based effect typing, including the closed prefix relation on effect rows, which clarifies the constraint on open floating.
Reference:
Towards Efficient Adjustment of Effect Rows (Naoya Furudono, Youyou Cong, Hidehiko Masuhara and Daan Leijen), In Trends in Functional Programming (Swierstra, Wouter, Wu, Nicolas, eds.), Springer International Publishing, volume 13401, 2022.
Bibtex Entry:
@inproceedings{furudono2022tfp,
author = {Naoya Furudono and Youyou Cong and Hidehiko Masuhara and Daan Leijen},
title = {Towards Efficient Adjustment of Effect Rows},
editor = {Swierstra, Wouter and Wu, Nicolas},
booktitle = {Trends in Functional Programming},
year = 2022,
publisher = {Springer International Publishing},
pages = {169--191},
month = mar,
series = {Lecture Notes in Computer Science},
volume = {13401},
date = {2022-03-17},
year = 2022,
pdf = {tfp2022adjustment.pdf},
doi = {10.1007/978-3-031-21314-4_9},
isbn = {978-3-031-21314-4},
abstract = {Koka is a functional programming language with native support for algebraic effects and handlers. To implement effect handler operations efficiently, Koka employs a semantics where the handlers in scope are passed down to each function as an evidence vector. At runtime, these evidence vectors are adjusted using the open constructs to match the evidence for a particular function. All these adjustments can cause significant runtime overhead. In this paper, we present a novel transformation on the Koka core calculus that we call open floating. This transformation aims to float up open constructs and combine them in order to minimize the adjustments needed at runtime. Open floating improves performance by 2.5 times in an experiment. Furthermore, we formalize an aspect of row-based effect typing, including the closed prefix relation on effect rows, which clarifies the constraint on open floating.},
url = {https://trendsfp.github.io/schedule.html}
}