Practical Normalization by Evaluation for EDSLs

Nachiappan Valliappan, Alejandro Russo, Sam Lindley

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationProceedings of the 14th ACM SIGPLAN International Haskell Symposium (Haskell 2021)
Place of PublicationVirtual, Republic of Korea
Number of pages15
ISBN (Electronic)9781450386159
Publication statusPublished - 18 Aug 2021
EventACM SIGPLAN Haskell Symposium 2021 - Virtual
Duration: 26 Aug 202127 Aug 2021


SymposiumACM SIGPLAN Haskell Symposium 2021
Abbreviated titleHaskell 2021
Internet address


  • Normalization by Evaluation
  • Partial Evaluation
  • eDSL
  • Haskell

Cite this