Norman Ramsey

Contents

Send email to nr@cs.tufts.edu.

Send physical documents to my postal address.

My vita and public key (now with photo!) are online.

Who I am and I care about

I'm a retired professor (emeritus) at Tufts University, where I did research in programming languages and taught a mix of classes. I care about simplicity, clarity, and elegance. These days I mostly pay attention to software development and game design. But over the years I have had my fingers in a lot of pies.

Programming-language infrastructure

Of all the problems in making programming-language infrastructure reusable, the most challenging is this: if we are given a new machine and are told what its instructions do, how do we generate code for it? Working with João Dias, I developed methods of automatically generating an instruction selector—the heart of a code generator—from declarative machine descriptions (POPL 2010). We also published the abstraction that the instruction selector is built on (POPL 2011).

Ideas about infrastructure are most convincing when they are deployed. In 2014, my group’s ideas about code generation were deployed in a new code generator for the Glasgow Haskell Compiler (GHC). Deployment required several years’ effort from João Dias, Simon Marlow of Microsoft Research, Simon Peyton Jones of Microsoft Research, and me. The new code generator’s most interesting component is a reusable, higher-order optimization library, Hoopl (Haskell 2010), which uses generalized algebraic data types to guarantee at compiler-compile time that no matter what Haskell program it is given, GHC never builds an ill-formed control-flow graph. Much later, I developed an algorithm for turning arbitrary control flow into structured control flow, which Cheng Shao incorporated into GHC’s WebAssembly back end.

Languages and learning

People who want to learn to use programming languages effectively can try starting with an industrial language, but the sheer size of a typical industrial language and library make it hard to discover and apply the ideas that make the language worth learning. People can also consult books, but existing books primarily talk about programming languages, or they talk about how programming languages are implemented, or they steer people to industrial languages. To make it possible for people not just to learn about great ideas in programming languages, but to build software that applies these ideas effectively, I have designed and implemented a collection of tiny programming languages for language learners. Using my languages, learners can build programs that apply some of the greatest ideas in programming languages: functions, types, and objects. The languages form the skeleton of a new book, Programming Languages: Build, Prove, and Compare, published by Cambridge University Press.

While implementing the languages I created for the book, I found an interesting problem: there is a big engineering gap between simple, definitional interpreters, which we write to illustrate precisely what a language is supposed to mean, and industrial-strength interpreters and compilers, which we write to run programs efficiently. To narrow this gap, I’ve investigated ways of engineering definitional interpreters to be more efficient, without making them much harder to write (PPDP 2013).

Because programming languages are the medium in which software is written, they are also the medium in which beginners learn to build software. The programming language and technique taught in introductory courses are widely believed to affect learning. An excellent basis for a first course can be found in How to Design Programs by Felleisen et al., which uses functional programming languages and techniques. My analysis, refinements, and recommendations were published at the International Conference on Functional Programming (ICFP 2014).

Language applications, design, and semantics

Languages and techniques are refined, evaluated, and improved by using them on real problems. I’ve applied functional-programming techniques to computational biology; working with graduate students in computational biology, I showed ways in which functional programming works to help solve their problems (ICFP 2012). We also identified obstacles that prevented functional programming from working as well as it could have.

Another application area, machine learning, builds on Bayesian reasoning about probabilities. But in current practice, a programmer’s Bayesian ideas are usually hand-translated into a general-purpose programming language like Matlab or C++. Such programmers might be much more productive if given a probabilistic programming language, in which Bayesian reasoning can be expressed directly. With support from DARPA, I'm working with colleagues from BAE Systems and Northeastern University on the design and semantics for probabilistic programming languages.

Curricular development

While teaching at Tufts, I revamped a significant portion of our required undergraduate curriculum in computer science. Our students are required to take four courses that have programming assignments. As a result of my work, these courses now ask much more of our students than they did formerly, and they also offer more. In particular, we now offer many more challenging, rewarding problems of a sort that students would not think to tackle on their own.

In addition to the pilot introductory course mentioned above, I completely redesigned the third and fourth courses in our programming sequence.

Our third course, COMP 40 (Machine Structures and Assembly-Language Programming), is most similar to a course in machine organization or systems programming. I redesigned the course to focus on two sets of skills: applied data abstraction and machine-level programming. The redesigned course is viewed by some as the most valuable course in our department. It is highly praised on surveys of graduating seniors, who are given the opportunity to identify just one course that exemplifies “what a truly excellent college course should be.”
I replaced an older “paradigms” course in programming languages with a new required course in programming languages, COMP 105, which demands that students learn to use key programming-language ideas in actual programming, and which also demands some mathematical content (e.g., operational semantics, equational proofs). The course, which uses my book Programming Languages: Build, Prove, and Compare, effectively serves as our fourth programming course. COMP 105 is also highly regarded by students and mentioned on senior surveys, although not quite as much as COMP 40.

Both courses continue to be taught much as I designed them.

My teaching and curricular work were recognized with the 2015 Lerman-Neubauer Prize for Outstanding Teaching and Advising. This prize is awarded annually to a member of the Tufts faculty who has had a profound intellectual impact on his or her students, both inside and outside the classroom.

Selected papers

This page shows some of my most academically significant papers, as well as papers of interest to people building compilers or interpreters. 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.
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, which was selected as one of the best papers of ICFP 2005, 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 Instruction Selectors 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

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

If you're building a compiler

About half the papers in this list include ideas or algorithms that other people have used, liked, and let me know about. The rest are just those that I think you might find useful if you're building a compiler.

Eliminating Spurious Error Messages Using Exceptions, Polymorphism, and Higher-Order Functions. Computer Journal, 42(5):360–372, 1999.
Widening Integer Arithmetic (with Kevin Redwine). In 13th International Conference on Compiler Construction (CC 2004), LNCS volume 2985, pages 232–249, April 2004.
A principled way to run 32-bit codes on a 64-bit machine. Shows which integer operators require sign extension, zero extension, or no extension. The most interesting contribution is not the algorithm itself, but a simple type system which classifies all arithmetic operations according to how they may be handled using a machine word that is too wide. The work generalizes to any pair of precisions.
Declarative Composition of Stack Frames (with Christian Lindig). In 13th International Conference on Compiler Construction (CC 2004), LNCS volume 2985, pages 298–312, April 2004.
A simple, powerful approach to stack-frame layout.
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.
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.
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.
Hoopl: Dataflow Optimization Made Simple (with João Dias and Simon L. Peyton Jones). July 2009.
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.
Beyond Relooper: Recursive Translation of Unstructured Control Flow to Structured Control Flow (Functional Pearl) (with Norman Ramsey). Proceedings of the ACM on Programming Languages, 6(ICFP), August 2022.
This functional pearl revives a 1973 program translation that can convert any reducible control-flow graph to structured control flow, without introducing superfluous code, variables, or tests. When implemented functionally, the algorithm is simple, and its correctness is easy to argue. The key new idea is that the translation can be implemented by a function that is recursive over the dominator tree.

If you're building an interpreter

I'm not sure who else, if any, has used these techniques, but I think they're good.

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.
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.
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, September 2013.
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.

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

I taught my last course Spring 2023: CS 106 (Simple Virtual Machines and Language Translation). Or as I prefer to call it, “Compilers: The Good Parts.” I had to wait over 20 years for my turn to teach compilers, but I'm proud of the result. Worth the wait.

At Tufts, I also taught COMP 250RTS (Run-Time Systems); COMP 150PP (Probabilistic Programming Languages); COMP 150TW (The Engineering Method of Technical Writing); COMP 50, a pilot version of the first course that I co-developed with Ben Hescott; COMP 40 (Machine Structures and Assembly-Language Programming); COMP 105 (Programming Languages); COMP 150GIT (Functional Programming and Source-Code Control); COMP 150DAO (Dataflow Analysis and Optimization); and COMP 150FP (Advanced Functional Programming). I also taught many courses at other universities that need not be named.

Resources for Students

I have gathered material of interest to research students, including resources for writers, how to give a talk.
Undergraduate research students might also be interested, especially in my thoughts about how to get admitted to a PhD program. I no longer write letters of recommendation.

If you want to teach at a community college, here are some tips from a community-college dean.

About Me

I type 75 words per minute. We are typists first, so test yourself.

My professional home is in the Department of Computer Science at Tufts University. My GPG public key's fingerprint is 72F7 B434 AB7C D7D0 D5A9 B537 BD01 D704 7276 3614. My ORCID ID is 0000-0002-5435-1135. Some people think I'm a power user; others think I never sleep. They may be right; my ~/bin directory contains over a thousand scripts, almost all of which I wrote myself. But a lot of people know me only as the creator of noweb.

I have twice served 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. After years of relying on the kindness of strangers, I finally started carrying a cell phone. I no longer maintain a hot list; this is more of a random list. I like Free DNS. 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. 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 email demilitarized zone. The next time I got to Zero was at 5:03 PM on Wednesday 29 August 2012, again at 2:54 PM on 30 May 2014, again at 6:34 PM on 12 November 2014, and again at 12:00 PM on 7 June 2017. For a time I almost thought I detected a pattern there.

I'm a Dou ble Tiger, a Bellcore alumnus, and a long-standing member of the Luxuriant Flowing Hair Club for Scientists, and I have an Erdös Number of 3. 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 used to answer programming questions for fun; at one time, I was the 40th most reputable contributor (out of over 100,000) on Stack Overflow (motto: "This thread has been closed as Off Topic"). Along the way I earned silver Specialist badges in C, Haskell, programming languages, functional programming, and a couple of other topics.

I’ve seen one total eclipse of the sun. Although I read extensively about viewing eclipses, I still was not prepared to take it all in. You can read my advice to my future self.

Although it surprises people, for over forty years I have been a foot ball fan—though I wouldn't mind realignment. When it's not football season, I've been known to make sawdust or play Guild Wars, although I can usually be found behind a Game Master screen. 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, game designer, and modder. I've appeared onstage (and in various clubs) as a jazz pianist, as a dancer, but most often as a chorister. My wish-fulfillment dreams are of sleeping.