Want to know how the machine works? Consider COMP 40!

Norman Ramsey

Send email to nr@cs.tufts.edu.
Send physical documents to my postal address.
If you come yourself you'll want directions.
Telephone +1 617 627 4923.
Skype (chat preferred): norman-ramsey
AIM: norman62ramsey
Yahoo chat: norman_ramsey
Fax +1 617 627 2227 (but if you can, scan and email instead)
My vita and public key are online.

I type 75 words per minute. Test yourself.

On this page:

Research

My research interests are broad, but grounded in programming languages. 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.

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. Starting in Fall 2008, I will continue work on C-- but with a greater focus on the run-time system. I am especially interested in low-level support for synchronization, concurrency, and work-stealing in run-time systems for multicore processors. I plan to use this problem as a springboard for my next big project: an investigation of abstraction, modularity, and reuse in run-time systems.

Here are some of the kinds of problems to be solved:

The implementor of a new language might well want to have Kent Dybvig's implementation of first-class continuations as realized in Chez Scheme, Perry Cheng's incremental garbage collector as realized in TILT, Charles Leiserson's work-stealing scheduler as realized in Cilk, and Tim Harris's software transactional memory as realized in GHC. But all of these features require extensive run-time support, and this support is implemented in four mutually incompatible systems, so there is no hope of reusing the code. Worse, it is not understood even in principle what are the difficulties in combining such a set of features or what are the barriers to making them reusable.
The run-time system of the Glasgow Haskell Compiler offers a pleasing collection of useful run-time services, carefully implemented. It is also an immense, bloated hog: it is four times the size of version 6 Unix, a major operating system. The size and complexity of the GHC run-time system is a serious problem for those who want to create secure software using Haskell and for those who wish to use Haskell without an underlying operating system (Hallgren et al. 2005). It is an important and urgent problem to understand how to break this kind of run-time system into pieces, such that an implementor can choose only the pieces needed for the task at hand, and such that most pieces can be reused for different tasks in different contexts.

I also have some ongoing projects in functional programming and compiling, and I hope to start a new project in distributed systems. Here are some details about a couple of projects:

Today position-independent code is based entirely on standards documents, which must be reconstructed laboriously for each new machine. I believe it is possible to develop a new implementation of position-independent code and dynamic linking by automatic analysis of the instruction set to identify two properties:
- How an instruction can depend on its own position
- How an instruction can depend on the positions of external labels
I would like such analysis to become the foundation of a new, machine-independent implementation of position-independent code and dynamic linking for C--.
The TinyCC project is a very interesting small, fast, integrated, dynamic compiler for C99. I'm very keen to have a back end for TinyCC that generates C--.

Selected papers

I have collected both highly significant and 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 publications list.

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, 2008. 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

These are some recent papers not listed above. They are in chronological order, so the most recent work is at the bottom.

An Applicative Control-Flow Graph Based on Huet's Zipper (with João Dias). In ACM SIGPLAN Workshop on ML, pages 101–122, September 2005.
A control-flow graph for doing classical imperative-style optimization in your functional compiler.
ML Module Mania: A Type-Safe, Separately Compiled, Extensible Interpreter. In ACM SIGPLAN Workshop on ML, pages 172–202, September 2005.
A functional pearl that explains Lua-ML's extension mechanism: separately compiled libraries. For modules hackers everywhere.
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, October 2006. A handbook for teaching writing to students in science or engineering. Accompanied by a student's edition.
Automatically Generating Back Ends for a Portable Assembly Language Using Declarative Machine Descriptions (with João Dias). Technical report, Harvard University, January 2008.
This somewhat hasty technical report presents the most exciting results from João Dias's doctoral dissertation. Persons actually wishing to understand the results should ask Dias for a copy of the dissertation.

For a complete view, including older work, see my publications list.

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.

Teaching

In Spring 2009 I am teaching COMP 150FP (Advanced Functional Programming). The course will be geared toward advanced undergraduate students and beginning graduate students. Although the course will focus on preparation for research, no prior knowledge of functional programming is expected.

In the past, I have taught COMP 40 (Computer Architecture).

Resources for Students

Office hours for Spring 2009 are Tuesday 1:30–2:30 and Wednesday 4:00–5:00. If you don't know whether to come to office hours, you might like to read Stuart Shieber's diatribe.

I am always interested in discussing projects with students, and I often have several undergraduate students working with me part-time. I hope to take on a small number of new students starting in the summer of 2009.

I have gathered material of interest to research students, including resources for writers, and how to give a talk.
Undergraduate research students might also be interested.

Other WWW Resources

I was program chair for ICFP '07.

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; in April 2009, near the end of my first year, my email debt was over 450 messages, but I am not yet ready to declare bankruptcy.

I'm a Bellcore alumnus and a long-standing member of the Luxuriant Flowing Hair Club for Scientists, and I have an Erdös Number of 5. I've been seen wearing orange and black academic regalia. Despite these distinguished credentials, I'm not ashamed to subscribe to a magazine with a centerfold. A secret vice is that I answer programming questions for fun; at one time, I was the 54th most reputable contributor (out of over 60,000).

Although it surprises some people, for over thirty years I have been a foot ball fan. When it's not football season, I've been known to play Guild Wars. I also have a rare autographed copy of Ad Verbum. I try to avoid P. J. Brown's deadly sins. I'm married to a licensed psychologist. In my copious free time, when I'm not reading Questionable Content or xkcd, I enjoy overworking.

My professional home is in the Department of Computer Science at Tufts University. Some people think I'm a power user.