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’21)
Place of PublicationVirtual, Republic of Korea
Number of pages15
Publication statusAccepted/In press - 23 Jun 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