Practical Normalization by Evaluation for EDSLs
Nachiappan Valliappan

, Alejandro Russo, and Sam Lindley
(Chalmers University of Technology, Sweden; University of Edinburgh, UK)
Embedded domain-specific languages (eDSLs) are typically implemented in a rich host language, such as Haskell, using a combination of deep and shallow embedding techniques. While such a combination enables programmers to exploit the execution mechanism of Haskell to build and specialize eDSL programs, it blurs the distinction between the host language and the eDSL. As a consequence, extension with features such as sums and effects requires a significant amount of ingenuity from the eDSL designer. In this paper, we demonstrate that Normalization by Evaluation (NbE) provides a principled framework for building, extending, and customizing eDSLs. We present a comprehensive treatment of NbE for deeply embedded eDSLs in Haskell that involves a rich set of features such as sums, arrays, exceptions and state, while addressing practical concerns about normalization such as code expansion and the addition of domain-specific features.
@InProceedings{Haskell21p56,
author = {Nachiappan Valliappan and Alejandro Russo and Sam Lindley},
title = {Practical Normalization by Evaluation for EDSLs},
booktitle = {Proc.\ Haskell},
publisher = {ACM},
pages = {56--70},
doi = {10.1145/3471874.3472983},
year = {2021},
}
Publisher's Version
Published Artifact
Artifacts Available