Norman Ramsey

I focus on reusable, low-level programming-language infrastructure; I want to make it easy and cheap to build the programming languages of the future. I also work in functional programming and programming-language design, including the design of special-purpose languages for solving problems in distributed systems.

My most recent work has been on reusable back ends, under the auspices of the C-- project, which I direct. My research is currently in transition: I am working on or interested in compilers; run-time systems; spam filtering; precise, machine-checkable, composable specifications for programming assignments; and algorithms and infrastructure for managing replicated data. I am recruiting PhD students for admission in 2010.

Selected papers

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.
A Single Intermediate Language That Supports Multiple Implementations of Exceptions (with Simon L. Peyton Jones). 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.
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 2002.
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.

Five other significant papers

Specifying Representations of Machine Instructions (with Mary F. Fernández). 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.
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 modifications.
A Generalized Algorithm for Graph-Coloring Register Allocation (with Michael D. Smith and Glenn Holloway). 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.
Embedding an Interpreted Language Using Higher-Order Functions and Types. Journal of Functional Programming, 2009. To appear. (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.

Other recent papers

Converting Intermediate Code to Assembly Code Using Declarative Machine Descriptions (with João Dias). In 15th International Conference on Compiler Construction (CC 2006), LNCS volume 3923, pages 217–231, March 2006.
A significant step toward our agenda of generating a compiler from declarative machine descriptions.
Teach Technical Writing in Two Hours per Week. A handbook for teaching writing to students in science or engineering. Accompanied by a student's edition.
Hoopl: Dataflow Optimization Made Simple (with João Dias and Simon Peyton Jones). Submitted to POPL'10.
A refinement of our 2005 work on compiling with applicative control-flow graphs. If you are a functional programmer and have any interest in dataflow analysis, you will like this paper. And if you have always found dataflow analysis complicated and mysterious, we hope to have demystified it.
Automatically Generating Back Ends Using Declarative Machine Descriptions (with João Dias). Submitted to POPL'10.
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 (a) by using a clever new heuristic search based on algebraic laws, João can generator 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.

Resources for Students

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 may have an opening for Fall 2009.

Other WWW Resources

I no longer maintain a hot list; this is more of a random list. An interest in personal productivity and pointers from Benjamin Pierce and Phil Wadler 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, but I am not yet ready to declare bankruptcy.