For some time now I have been teaching from a draft textbook which is
intended to introduce the field of programming languages to an
audience composed primarily of people who will have careers in
My working title is Programming Languages: Build, Prove, and
Compare, and if you want you can read a little bit about it.
My research interests are broad, but grounded in programming
I like programming languages because there is nothing like
a good language to help us express computations precisely, in ways
that we can reason about them, while still keeping things
at a high level.
For many years I focused on reusable, low-level programming-language infrastructure;
I wanted to make it easy and cheap to build the programming
languages of the future.
My most recent work has been on reusable back ends and optimization
which has been applied to the increasingly misnamed Glasgow Haskell Compiler (GHC).
(I also keep an old snapshot of C--.)
Today I still work on programming-language infrastructure,
but I focus on functional programming and on programming-language design,
including the design of special-purpose languages.
I am very interested in applying programming-language techniques to
distributed source-code control
and in the design and application of probabilistic programming
This page show my most significant and most recent papers.
Links are to abstracts so you can check
out the topic without downloading a monster.
For a complete view, including older work, see my
Five most significant papers
- Relocating Machine
Instructions by Currying.
Proceedings of the ACM
SIGPLAN '96 Conference on Programming Language Design and Implementation,
in SIGPLAN Notices, 31(5):226–236, May 1996.
This paper connects two worlds: the ``low cult'' of systems programming
and the pure, mathematical world of the lambda-calculus. The key insight is
that relocation, which is a low-level operation performed on binary code, is
an instance of currying, which is the expression of a multiple-argument
function in the lambda-calculus.
- Stochastic Lambda Calculus and
Monads of Probability Distributions (with Avi Pfeffer).
Proceedings of the 29th ACM Symposium on the Principles of Programming
Languages, in SIGPLAN Notices, 37(1):154–165, January
This paper explores the design of probabilistic languages in a
foundational, principled way. Its special contribution is to analyze
important implementation techniques in a way that is completely formal and is
rigorously connected to the theory of probability.
- A Transformational Approach to
Binary Translation of Delayed Branches (with Cristina Cifuentes).
ACM Transactions on Programming Languages and Systems,
25(2):210–224, March 2003.
The paper solves a small but difficult problem in analysis of binary
codes. This problem is repeatedly a stumbling block for industry groups that
work with binary codes, and I believe our solution is definitive.
- An Expressive Language of
Signatures (with Kathleen Fisher and Paul Govereau).
In Proceedings of the Tenth
ACM SIGPLAN International Conference on Functional Programming
(ICFP'05), pages 27–40, September 2005.
In this paper, we identified an important class of programming problems
the solutions to which cannot be expressed in current languages, and we
showed that these problems can be solved by new mechanisms that cohere with
an existing language.
- Automatically Generating Back
Ends Using Declarative Machine Descriptions (with João Dias).
In Proceedings of the 37th ACM Symposium on the Principles of Programming
Languages, pages 403–416, January 2010.
The most beautiful results from João Dias's doctoral
dissertation: (a) if all you know is the semantics of the intermediate
code and the target instruction set, generating a code generator is
undecidable; and (b) by using a clever new heuristic search based on
algebraic laws, João can generate code generators for real machines
quickly. The core of the algorithm combines Hoare logic and unification to
find sequences of machine instructions that implement intermediate code. Will
appeal especially to those who like inference rules with their compilers.
Five other significant papers
These are some recent papers not listed above.
They are in chronological order,
so the most recent work is at the bottom.
- Specifying Representations of
Machine Instructions (with Mary F.
ACM Transactions on Programming Languages and Systems,
19(3):492–524, May 1997.
This is the most technical and the definitive description of my early
work on declarative machine descriptions.
- A Single Intermediate Language
That Supports Multiple Implementations of Exceptions (with Simon L. Peyton
Proceedings of the ACM SIGPLAN '00 Conference on Programming Language
Design and Implementation, in SIGPLAN Notices,
35(5):285–298, May 2000.
This paper is the most technical and rigorous of the C-- papers.
It exemplifies what I am trying to achieve in C--: clean, low-level
mechanisms that compiler writers can use to implement different
high-level–language features and to control cost tradeoffs.
- An Algebraic Approach to File
Synchronization (with Elöd Csirmaz).
In Proceedings of the 8th European Software Engineering Conference (ESEC)
and 9th ACM SIGSOFT Symposium on the Foundations of Software Engineering
(FSE-9), pages 175–185, September 2001.
This paper discusses how to maintain consistency among multiple
replicas of files that may be modified concurrently. We proposed reasoning
about this problem by examining the algebraic structure of a sequence of
- A Generalized Algorithm for
Graph-Coloring Register Allocation (with Michael D. Smith and
ACM SIGPLAN '04
Conference on Programming Language Design and Implementation, in
SIGPLAN Notices, 39(6):277–288, June 2004.
A new technique for dealing with irregularities in target machines,
which arise because not all machine registers can be used interchangeably. We
hope this will be the definitive paper on handling irregular register files
in a graph-coloring register allocator.
- Staged Allocation: A Compositional
Technique for Specifying and Implementing Procedure Calling Conventions
(with Reuben Olinsky and Christian Lindig).
In Proceedings of the
33rd ACM Symposium on the Principles of Programming Languages,
pages 409–421, January 2006.
A specification language for parameter passing, unique in having a
formal semantics. Together with an earlier paper on stack-frame layout, a
complete approach to calling conventions.
For a complete view, including older work, see my
- Hoopl: A Modular, Reusable
Library for Dataflow Analysis and Transformation (with João Dias and Simon
In Proceedings of the 3rd ACM SIGPLAN Symposium on Haskell
(Haskell 2010), September 2010.
We implement dataflow analysis and transformation in modular fashion
using advanced features of Haskell. Unlike our 2009 technical report, which
emphasizes the advantages of using Hoopl, this paper focuses on the
implementation, which has been carefully modularized to separate each of the
tricky bits from all of the others. Of greatest interest to hard-core
functional programmers and compiler writers.
- Resourceable, Retargetable, Modular
Instruction Selection Using a Machine-Independent, Type-Based Tiling of
Low-Level Intermediate Code (with João Dias).
In Proceedings of the 38th ACM Symposium on the Principles of Programming
Languages, pages 575–586, January 2011.
In most compilers, building an instruction selector requires a mapping
from intermediate form to target-machine instructions. The mapping must be
defined once per target machine. Here we describe a single mapping that works
for all register machines. By using this mapping, we make the
machine-dependent components simple enough that they can be generated
- Teaching Technical Writing Using the
March 2011. A handbook for teaching writing to students in science or
engineering. Accompanied by a student's edition.
- Embedding an Interpreted Language
Using Higher-Order Functions and Types.
Journal of Functional
Programming, 21(6):585–615, November 2011.
(A previous version appeared in ACM SIGPLAN 2003 Workshop on
Interpreters, Virtual Machines and Emulators.).
Homage to Olivier Danvy: How to
embed an application-specific function into an interpreter simply by
describing its type. The paper, while not technically deep, shows the
capabilities of functional languages to elegant advantage, and it is
representative of my work on interpreters.
- Experience Report: Haskell in
Computational Biology (with Noah M. Daniels and Andrew Gallant).
In Proceedings of the Seventeenth ACM SIGPLAN International Conference on
Functional Programming (ICFP'12), pages 227–234, September
Selected as one of the best papers of ICFP 2012.
Encouragement for computational biologists to try Haskell. If you are a
functional programmer, you will see an interesting variation on lazy search.
You might also get some insight into why beginners may find it difficult to
- MRFy: Remote Homology Detection for Beta-Structural Proteins Using Markov
Random Fields and Stochastic Search (with Noah Daniels, Andrew Gallant, and
In Fourth ACM International Conference on Bioinformatics, Computational
Biology, and Biomedical Informatics (ACM BCB 2013),
pages 133–143, 2013.
Best Student Paper.
Results of our work on stochastic search for protein homologies. The
search tool was written in the functional language Haskell.
- Engineering Definitional
Interpreters (with Jan Midtgaard and Bradford Larsen).
In Proceedings of the 15th International Symposium on Principles and
Practice of Declarative Programming (PPDP'13), pages 121–132,
Definitional interpreters can be simple but often don't perform very
well. Mature bytecode interpreters can perform very well but aren't simple or
easy to build. This paper recounts our extensive search for the "best simple"
variation on a definitional interpreter written in a functional language.
- On Teaching How to Design
Programs: Observations from a Newcomer.
To appear in Proceedings of the Nineteenth ACM SIGPLAN International Conference on
Functional Programming (ICFP'14), 2014.
In Fall 2013 I taught introductory programming using the interesting
textbook How to Design Programs. If you might teach from this book,
this paper contains lots of useful information about how to prepare and teach
such a course.
The ACM requires this disclaimer:
The documents contained in these pages are included
to ensure timely
dissemination of scholarly and technical work on a
non-commercial basis. Copyright and all rights therein
are maintained by the authors or by other copyright
holders, notwithstanding that they have offered their
works here electronically. It is understood that all
persons copying this information will adhere to the terms
and constraints invoked by each author's copyright.
These works may not be reposted without the explicit
permission of the copyright holder.
In Fall 2013 I taught COMP 50,
a pilot version of the first course that I have co-developed with Ben Hescott.
I also taught
a seminar in advanced
In the past, I have taught
COMP 40 (Machine Structures and Assembly-Language
COMP 150GIT (Functional Programming and
COMP 150DAO (Dataflow Analysis and
COMP 150FP (Advanced Functional
COMP 150TW (The
Engineering Method of Technical Writing),
as well as many courses at other universities that need not be named.
Resources for Students
Thursdays from 2:30–3:00
and by appointment.
I am always interested in discussing
projects with students, and I
often have several undergraduate or master's students working with me part-time.
I have gathered material of interest to research
students, including resources for
how to give a talk.
My professional home is in the
Department of Computer Science
at Tufts University.
Some people think I'm a power
others think I never sleep.
My ORCID ID is
Undergraduate research students might also be interested, especially
in my thoughts about
how to get admitted to a PhD program.
And I tell you what you need to give me
(and when) if you want a letter of recommendation.
I currently serve ACM as a member of the SIGPLAN Executive Committee.
I served as program chair for ICFP '07.
I signed the email
charter; if you won't, I won't.
I don't carry a cell phone.
I no longer maintain a
hot list; this is more of a random list.
An interest in personal productivity and pointers from
got me to Inbox Zero
on Wed 21 Feb 2007 at 6:00 PM.
After serious lossage caused by various alarums and excursions,
I recovered Zero at 6:30 PM on Mon 31 Dec 2007.
It was a pleasure to start the New Year with an empty inbox!
After starting at Tufts, I got a little behind; at the end of my
first year, my email debt was over 600 messages.
At the end of my third year, at 9:12 PM on Monday 23 May 2011,
I recovered Zero once again, but I cheated—I put
600 messages from 2009 and 2010 into an
The next time I got to Zero was at 5:03 PM on Wednesday
29 August 2012, and again at
2:54 PM on 30 May 2014.
Do we detect a pattern here?
Although it surprises some people, for over forty years I have
When it's not football season, I've been known to play Guild Wars.
I also have a rare autographed copy of
I try to avoid P. J. Brown's deadly sins.
I'm married to a licensed
I've appeared onstage
(and in various
dreams are of sleeping.