David Espinosa

I'm now a computer scientist at Kestrel Institute. Before that, I was a graduate student in computer science at Columbia University and was also unofficially visiting Project MAC at MIT. My interests are in

Programming language design and implementation.
Formal methods for specification and verification.
New software architectures, including operating systems.

My thesis was on building interpreters from reusable parts using monad transformers (see below).

Papers

Generic Interpreters.
This paper is an earlier thesis proposal on generic interpreters (built using CLOS) and an "object oriented" module system. Soon after, I discovered found that an identical module system had already been described by Bracha and Lindstrom (International Conference on Computer Languages, April 1992). Later, my ideas on modules changed, but that's another story.
Semantic Lego.
This paper describes an implementation of Moggi's theory of monad transformers. The basic idea is to start with a type and transform it. With each transformation, we add new operators to the type and lift previously defined operators.
Stratified Monads.
This paper describes a revision of the above based on stratification rather than lifting. We define language constructs in terms of a semantic algebra that allows access (using monads) to multiple semantic "levels". This theory is clearer, more modular, and more flexible than the lifting theory.
Both papers describe programming languages as abstract data types. This point of view is graceful and hasn't had impact it deserves (although it's twenty years old). It shows that there needn't be a difference between "metalinguistic abstraction" (in Abelson and Sussman's sense) and ordinary abstraction and that new syntax isn't necessary to build new languages.
Semantic Lego (PhD thesis).
This thesis supercedes both of the above papers.
Slides for Semantic Lego talk.
These slides show the best parts of the thesis in nice BIG letters!

Programs

These files contain Scheme code implementing the ideas in the above papers. All files are in compressed tar format, and all but the first two are somewhat specific to MIT Scheme.

Semantic Lego
Stratified Monads
Generic Interpreters
B&L Module System
Program Simplifier
This simplifier is used with Stratified Monads to display automatically generated language constructs.

Related papers

Here are some interesting papers on monads. Wadler's "Essence" paper is a now-classic introduction. Also, if you are familiar with monads from the functional programming point of view but have never tried to read Moggi, you might want to look at his notes; the difference in point of view is remarkable.

An Abstract View of Programming Languages, Eugenio Moggi, Stanford course notes 1989.
The Essence of Functional Programming, Philip Wadler, POPL 1992.
Combining Monads, Philip Wadler and David King, Glasgow technical report 1992.
Composing monads, Mark Jones and Luc Duponcheel, Yale technical report 1992.
Building Interpreters by Composing Monads, Guy L. Steele, POPL 1994.
Extensible Denotational Language Specifications, Matthias Felleisen and Robert Cartwright, TACS 1994.
Monad Transformers and Modular Interpreters, Sheng Liang, Mark Jones, and Paul Hudak, POPL 1995.
Modular Denotational Semantics for Compiler Construction, Sheng Liang and Paul Hudak, ESOP 1995 (?).

Useful web links

Notes

Miscellaneous Scheme programs

David Espinosa
espinosa@kestrel.edu
dae@martigny.ai.mit.edu
(415) 493-6871 (work)