Making Monads First-class with Template Haskell∗Pericles S. Kariotis Adam M. Procter William L. HarrisonDepartment of Computer ScienceUniversity of MissouriColumbia, Missouri. [email protected] [email protected] [email protected] as an organizing principle for programming and semanticsare notoriously difficult to grasp, yet they are a central and power-ful abstraction in Haskell. This paper introduces a domain-specificlanguage, MonadLab, that simplifies the construction of monads,and describes its implementation in Template Haskell. MonadLabmakes monad construction truly first class, meaning that arcanetheoretical issues with respect to monad transformers are com-pletely hidden from the programmer. The motivation behind thedesign of MonadLab is to make monadic programming in Haskellsimpler while providing a tool for non-Haskell experts that will as-sist them in understanding this powerful abstraction.Categories and Subject Descriptors D.3.3 [Software]: Program-ming LanguagesGeneral Terms Languages, DesignKeywords Staged Programming, Monads, Domain-specific Lan-guages1. IntroductionPraising monads to the Haskell community is like “preaching tothe choir.” Monads have become a central programming abstractionin Haskell with benefits including modularity and maintainability,effectful programming and mathematical precision. Monad lore(i.e., the principles underlying the use and construction of monads)is also infamous for its steep learning curve. This is more thana pedagogical concern. The steep learning curve of monad loreintimidates potential new Haskell users and impedes the growth ofthe Haskell community.One means of improving this situation is to encapsulate monadconstruction within a language design. The approach exploredin this article creates a DSL for automatically defining monads(“MonadLab”) embedded in Template Haskell (TH). With Monad-Lab, the creation of monads is first-class: the monad lore underly-ing the creation of layered monads is encapsulated entirely by the∗This research supported by NSF CAREER Award #00017806, NRL Con-tract 1302-08-015S, and the Gilliom Cybersecurity Endowment.Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. To copy otherwise, to republish, to post on servers or to redistributeto lists, requires prior specific permission and/or a fee.Haskell’08 September 25, 2008, Victoria, BC, Canada.Copyrightc 2008 ACM 978-1-60558-064-7/08/09. . . $5.00language definition. The contributions of this paper are:•First-class Monads. The MonadLab DSL insulates users fromthe theoretical details underlying monad construction. The im-plementation of MonadLab in Template Haskell handles all de-tails of monad construction.•Simplicity & Completeness. The Haskell Monad TransformerLibrary gets close to full automation of monad construction,but falls short in several ways. Template Haskell’s meta-programming can overcome these problems as it does in theMonadLab implementation. The result is a very direct formula-tion of monad transformers.•A Non-trivial Case Study for Template Haskell. TemplateHaskell provides useful functionality for Haskell users, but itsdocumentation is less than extensive. We believe that this paperwill be of value to those trying to learn TH. This paper providesfeedback data about its strengths and weaknesses.•A Tool for Learning Monadic Programming and Semantics.Monad lore is difficult to learn, and MonadLab permits newor potential Haskell users to experiment easily with monads.Why not just use the monad transformer library? Haskell’smonad transformer library (MTL) does provide tools for construct-ing “layered” monads, however the MTL does not insulate usersfrom details underlying monad transformer application. It is well-known that the order of monad transformer application can affectthe behavior of the whole specification. While monad transformersalways produce monads, there are certain cases in which the be-havior of the extra “non-proper” morphisms defined on a monaddepends on the order of application (Liang 1998) and the MTL re-quires users to grasp this somewhat arcane material. MonadLab in-corporates this domain knowledge, thereby freeing users from suchconsiderations.The MTL is not well-suited to multiple applications of the samemonad transformer because of its implementation within Haskell’stype class system. There are scenarios that are best expressed viamultiple applications of a single monad transformer. Monadic sep-aration kernels (Harrison and Hook 2008), for example, use the dis-tinct imperative operations arising from separate applications of thestate monad transformer to delimit effects and enforce informationflow security. For example, to create a monad with n distinct putand get operations using the MTL, one would first have to createa class with n distinctly named put and get methods. Alternatively,one could use a single application of the state monad transformerwith a single global n-tuple state and define the n distinct methodsas projections. Either strategy is ungainly and effectively obscuresthe modularity given by modular monadic semantics.This paper proceeds as follows. Section 2 presents a familiarexample—modular interpreters—expressed in terms of MonadLab.Section 3 gives a quick review of Template Haskell. Section 4 de-scribes the basic API provided by MonadLab. MonadLab is a DSLembedded in Template Haskell; this embedding is described in Sec-tion 5. Sections 6 and 7 present related work and conclusions, re-spectively.2. Introducing MonadLabThis section introduces the syntax of MonadLab and an extendedexample of its use. The abstract syntax for monad declarations inMonadLab is:<Decl> ::= monad Tag = <Monad><Monad> ::= <Layer> { + <Layer> }*<Layer> ::= <MT> ( <Type> ) Tag | Id | List<MT> ::= StateT | EnvT | WriteT | ErrorT | ContTA top-level declaration, <Decl>, declares a new monad, namedwith a Tag. A <Monad> is a collection of <Layer>s. Each <Layer>represents the application of a particular monad transformer or basemonad (i.e., either the identity or list monad). A <Type> refers toa Haskell type expression and Tag is used to distinguish the non-proper morphisms of this <Layer> from others in a <Monad> spec-ification. A Tag is an