home | publications | teaching | projects | personal | misc

Publications

Blogs

blog :: Brent -> [String]: where I write about Haskell, combinatorics, research, projects, and so on.

The Math Less Traveled: A blog exploring fun and beautiful mathematics, aimed at high schoolers, math educators, and anyone, really.

Conference articles

(Standard copyright disclaimer, which applies to all publications below unless otherwise noted:

ACM COPYRIGHT NOTICE. Copyright © 2010-2012 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM, Inc., fax +1 (212) 869-0481, or permissions@acm.org.)

---

Monoids: Theme and Variations (Functional Pearl) (Haskell '12)

Brent A. Yorgey
September 2012

Click to view abstract

The monoid is a humble algebraic structure, at first glance even downright boring. However, there’s much more to monoids than meets the eye. Using examples taken from the diagrams vector graphics framework as a case study, I demonstrate the power and beauty of monoids for library design. The paper begins with an extremely simple model of diagrams and proceeds through a series of incremental variations, all related somehow to the central theme of monoids. Along the way, I explain the power of compositional semantics; why you should also pay attention to the monoid’s even humbler cousin, the semigroup; monoid homomorphisms; and monoid actions.

Giving Haskell a Promotion (TLDI '12)

Brent A. Yorgey, Stephanie Weirich, Julien Cretin, Simon Peyton Jones, Dimitrios Vytiniotis, and José Pedro Magalhães
January 2012

Click to view abstract

Static type systems strive to be richly expressive while still being simple enough for programmers to use. We describe an experiment that enriches Haskell’s kind system with two features promoted from its type system: data types and polymorphism. The new system has a very good power-to-weight ratio: it offers a significant improvement in expressiveness, but, by re-using concepts that programmers are already familiar with, the system is easy to understand and implement.

Binders Unbound (ICFP '11)

Stephanie Weirich, Brent A. Yorgey, and Tim Sheard
September 2011

Click to view abstract

Implementors of compilers, program refactorers, theorem provers, proof checkers, and other systems that manipulate syntax know that dealing with name binding is difficult to do well. Operations such as \(\alpha\)-equivalence and capture-avoiding substitution seem simple, yet subtle bugs often go undetected. Furthermore, their implementations are tedious, requiring “boilerplate” code that must be updated whenever the object language definition changes.

Many researchers have therefore sought to specify binding syntax declaratively, so that tools can correctly handle the details behind the scenes. This idea has been the inspiration for many new systems (such as Beluga, Delphin, FreshML, FreshOCaml, C\(\alpha\)ml, FreshLib, and Ott) but there is still room for improvement in expressivity, simplicity and convenience.

In this paper, we present a new domain-specific language, Unbound, for specifying binding structure. Our language is particularly expressive—it supports multiple atom types, pattern binders, type annotations, recursive binders, and nested binding (necessary for telescopes, a feature found in dependently-typed languages). However, our specification language is also simple, consisting of just five basic combinators. We provide a formal semantics for this language derived from a locally nameless representation and prove that it satisfies a number of desirable properties.

We also present an implementation of our binding specification language as a GHC Haskell library implementing an embedded domain specific language (EDSL). By using Haskell type constructors to represent binding combinators, we implement the EDSL succinctly using datatype-generic programming. Our implementation supports a number of features necessary for practical programming, including flexibility in the treatment of user-defined types, best-effort name preservation (for error messages), and integration with Haskell’s monad transformer library.




unbound package

Species and Functors and Types, Oh My! (Functional Pearl) (Haskell '10)

Brent A. Yorgey
September 2010

Click to view abstract

The theory of combinatorial species, although invented as a purely mathematical formalism to unify much of combinatorics, can also serve as a powerful and expressive language for talking about data types. With potential applications to automatic test generation, generic programming, and language design, the theory deserves to be much better known in the functional programming community. This paper aims to teach the basic theory of combinatorial species using motivation and examples from the world of functional programming. It also introduces the species library, available on Hackage, which is used to illustrate the concepts introduced and can serve as a platform for continued study and research.




species package