Emerald

Emerald is a distributed, object-based programming language designed and built in the Department of Computer Science at the University of Washington in the mid-1980s by Andrew P. Black, Norman C. Hutchinson, Eric Jul and Henry M. Levy. Its goal was to make distributed applications easy to write. Its creators describe it as the first language to propose and implement object mobility: an Emerald object could move from one computer on a network to another while it continued to execute, and code invoking the object did not need to know or care where the object was. The authors once summarised Emerald as being “like Java, except that it has always had generics, and that its objects are mobile”. It never became a commercial language. Its ideas about location-independent invocation and type conformity reached later distributed object systems, including ANSA, Modula-3’s Network Objects and, less directly, Java RMI and Jini.

History and Origins

The Eden problem

Emerald grew out of Eden, an object-based distributed operating system project that started at the University of Washington around 1979-80 with one of the first grants from the National Science Foundation’s Coordinated Experimental Research programme. Eden treated every network resource as an object that could be invoked wherever it lived. The idea worked, but the implementation was heavy.

Each Eden object was a full UNIX process, at least 200-300 kilobytes in size. Even an invocation between two objects on the same machine needed inter-process communication through a separate Eden kernel process. A local invocation took 137 ms in October 1983, close to half the cost of a remote one at about 300 ms. Programmers therefore used a second, lightweight kind of object for everything that did not strictly need to be distributed. That object came from the Eden Programming Language (EPL), a dialect of Concurrent Euclid. The result was two incompatible object models, and programmers had to decide in advance which one each abstraction would use.

A coffee-shop challenge

Henry Levy had worked on the VAX at Digital Equipment Corporation and returned to the University of Washington as a research assistant professor in September 1983. Shortly afterwards he heard Ph.D. students Eric Jul and Norman Hutchinson describe their work on Eden. He invited them to a coffee shop on “the Ave”, listened to their complaints, and asked them what they would do differently, and then: “Why don’t you do it?” Andrew Black had joined Eden in 1981 after a D.Phil. at Oxford under C.A.R. Hoare. He became the group’s language designer and worked closely with Hutchinson on the type system.

The group’s discussions of an Eden successor took place in what Levy called “the land of Oz”. A memo titled Getting to Oz, dated 27 April 1984, records their realisation that the real problem was language design, not kernel design. The language was first called Toto, then Jewel, and finally Emerald. The name kept the Oz connection and also referred to Seattle’s nickname, the Emerald City.

Building it

The work divided cleanly. Hutchinson wrote the compiler and Jul wrote the run-time system, which the team called the kernel. The two shared an office and a whiteboard, and by convention the data-structure layouts drawn on the whiteboard were “the truth”. The team’s surviving version notes show an incremental path:

Development began on the Eden project’s VAX 11/780 and 11/750 machines. In December 1985 Digital granted the group five MicroVAX II workstations, which arrived a few months later. The first public description, “Object Structure in the Emerald System”, was presented at the first OOPSLA conference in October 1986. The team dispersed almost as soon as the system was finished. Hutchinson graduated in January 1987 and went to the University of Arizona. Jul returned to Copenhagen in February 1987 to finish his thesis. Black had joined Digital’s distributed systems group in December 1986. Levy stayed at Washington.

Design Philosophy

Emerald’s authors set out a few explicit goals:

• One object model. Local and remote objects should look the same to the programmer. The compiler, not the programmer, chooses how each object is implemented.
• Performance competitive with conventional languages. Local operations should be about as fast as in C, and remote invocation about as fast as a remote procedure call. Under the principle of “no use, no cost”, programs that do not use distribution should not pay for it.
• Simpler distributed programming. Marshalling, dispatch, thread management and object location should be handled automatically. Object placement was left to the programmer, because the team did not believe it could be automated well.
• Information hiding. An object’s interface should be all a client can rely on, so one abstraction can have several implementations.

Key Features

Objects without classes

Emerald has no classes. The team regarded Smalltalk-style classes as hard to define in a distributed system. If a class changed while its instances were spread across machines, some of them unreachable, there was no satisfactory meaning for the update. Emerald instead uses object constructors: expressions, modelled on record constructors, that create a new, fully initialised object each time they are evaluated. Object constructors can be nested, so factories and prototype-style cloning objects are easy to write.

An object can have an optional process section. If it has one, the object is active and its process starts running as soon as the object is initialised. A program has no main procedure. It is simply a set of object declarations, and any objects with processes start running when the program is loaded. Here is the “hello, world” program as published in the HOPL III paper (which typesets assignment as ←):

const simpleprogram ← object myMainProgram
  const i ← 1
  process
    stdout.PutString[i.asString || ": hello, world!\n"]
  end process
end myMainProgram

Operations that may be called from outside an object are marked export. Encapsulation is per object, not per class as in C++ and Java: no other object, even one built by the same constructor, can reach into an object’s state. This strict encapsulation is what allowed the run-time system to move objects safely.

Abstract types and conformity

Emerald is statically typed, but a type describes behaviour, not implementation. An abstract type is a set of operation signatures. An object belongs to a type if it conforms to it, which means it provides at least those operations with compatible signatures, no matter how the object was implemented or where it was compiled. This is the approach now called structural typing. The team adopted it because objects compiled on another machine could arrive over the network at run time. For the same reason types are themselves objects that exist at run time, an idea taken from the Russell language. Checking is static where possible and deferred to run time where necessary.

Parameterised types fall out of this design. A declaration such as Array.of[Integer] is an invocation of the function of on the immutable object Array, and the compiler can evaluate it at compile time because it is a functional operation on immutable objects.

Immutability

Influenced by CLU, Emerald lets the programmer declare objects immutable and operations function. The implementation uses this freely. There is logically one integer 3, but any number of copies may exist across the network. An object’s code is logically owned by the object, but it is copied to each machine that needs it. Because immutable objects never change, nobody can tell the copies from the original. Emerald trusts these declarations and does not try to verify them, a choice the team made after frustrating experiences with Concurrent Euclid’s enforcement.

Concurrency

Concurrency control follows Concurrent Pascal and Concurrent Euclid. An object can be declared as a monitor, which makes its exported operations mutually exclusive, and condition objects provide Hoare-style wait and signal. Emerald’s processes were lightweight and protected by the language implementation rather than by the operating system. Today they would be called threads.

Mobility

Invocation in Emerald is location-independent. Location itself is still visible to programs that need it, through a small set of primitives:

Here Y can be any object, not just a node. fix aMessage at aMailbox means “keep the message wherever the mailbox is”. Two parameter-passing modes also affect location. Call-by-move sends an argument object to the callee’s node. Call-by-visit sends it there and brings it back afterwards. An attached annotation on a variable makes the referenced object move along with its container. The “Kilroy was here” program on the project’s history site shows the style. An object with its own process visits every active node and then returns home:

const Kilroy ← object Kilroy
  process
    const origin ← locate self
    const up ← origin.getActiveNodes
    for e in up
      const there ← e.getTheNode
      move self to there
    end for
    move self to origin
  end process
end Kilroy

The process keeps running across each move. Its stack and local state travel with the object.

Performance

Performance was a stated goal, and the HOPL III paper publishes the team’s measurements. Most were taken in February 1987 on MicroVAX II machines running Ultrix:

• Local invocation: an Emerald local invocation took 16.6 µs. A C procedure call compiled with the Berkeley portable C compiler took 13.4 µs, and a Concurrent Euclid call took 16.4 µs. Emerald and Concurrent Euclid were slower than C mainly because they checked for stack overflow explicitly on each call. Primitive integer and real operations compiled to the same instructions as in C.
• Remote invocation: a parameterless remote invocation took 27.9 ms. Of that, 24.5 ms was the underlying network message exchange, so Emerald’s own invocation handling added about 3.4 ms. For comparison, the paper gives 54 ms for an Eden remote invocation on a Sun 2 and 136 ms for an empty remote invocation in Bennett’s Distributed Smalltalk.
• Mobility: moving a simple data object took about 12 ms. Moving an object that contained a small process with six variables took about 40 ms.
• Ackermann’s function, a benchmark dominated by procedure calls: with arguments (7,3), Emerald took 27.7 s against 16.6 s for the same C code compiled with the optimizer, about 67% slower. The authors attribute the gap to slower calls, the type information passed with parameters, and mandatory variable initialisation. They also report that after the 1992 SPARC port, Emerald invocations were almost 15% faster than SPARC C procedure calls, because Emerald did not use SPARC register windows.

Evolution

After the original team dispersed, Emerald continued as a research and teaching vehicle, mostly at the institutions its creators moved to:

• New architectures. Between 1987 and 1994 the native-code compiler was retargeted from the VAX to the Sun 3 (Motorola 68000 family), Sun 4 (SPARC) and Digital Alpha. Hutchinson then wrote a byte-code compiler (itself written in Emerald) and a portable virtual machine. His UBC page, last updated in 1998, lists that implementation for Linux, FreeBSD, SPARC/Solaris, HP-PA/HP-UX and Windows 95/NT.
• Types. Black and Hutchinson kept refining the theory of conformity from 1986 to 1989. That work was captured in the technical report Typechecking Polymorphism in Emerald (Digital Cambridge Research Laboratory, CRL 91/1), which its bibliographic entry dates to December 1990, although the HOPL III text calls it the January 1991 report.
• Heterogeneous mobility. In 1990-91 Jul worked with students on a version in which objects and running threads could move between VAX, Sun 3 and SPARC machines. Threads could move at “bus stops”, which occur after essentially every statement. The work was published at SOSP in 1995.
• Wide-area Emerald. In 1992-93, DIKU master’s students adapted the LAN-based system to the Internet. They report that a trip around the world through seven machines initially took 15-20 minutes and, after protocol tuning, only a few seconds.
• Garbage collection, databases and transactions. Niels Christian Juul built a distributed, on-the-fly garbage collector. Niels Elgaard Larsen added database support and, in a Ph.D. thesis completed in 2006, transactions.
• Open source. In 2005, version 1.05 alpha and then 1.06 alpha were published on SourceForge with an Eclipse plugin.

Influence

The HOPL III paper traces Emerald’s influence along two lines, distributed objects and type systems:

• ANSA and ISO RM-ODP. Andrew Herbert, chief architect of the Advanced Networked Systems Architecture (ANSA), wrote that its “Big DPL” language “borrowed very heavily from Emerald”. Through ANSA, an Emerald-style conformity type system made its way into the ISO Reference Model of Open Distributed Processing (ISO 10746).
• Guide. Sacha Krakowiak of INRIA Grenoble describes Emerald as “one important source of inspiration” for the Guide language, specifically its separation of types from implementations and its type conformity rules.
• Network Objects. Birrell, Nelson, Owicki and Wobber wrote that their Modula-3 Network Objects system “built closely on the ideas of Emerald” and SOS. They deliberately dropped object mobility in favour of what they called powerful marshalling.
• Java RMI and Jini. The influence here was indirect. According to the HOPL III paper, whose account of this episode draws largely on material from Doug Lea, Emerald’s capabilities were part of the argument at Sun that led to RMI being chosen over a plain CORBA binding. Jim Waldo wrote that RMI and Jini “took many of the ideas pioneered in Emerald having to do with moving objects around the network”.
• ANSI Smalltalk. The 1997 ANSI Smalltalk draft standard specifies behaviour with protocols and conformance rules. Emerald’s authors see this as a case of feedback, since Smalltalk’s protocols had been Emerald’s own starting point.

Current Relevance

Emerald is a historical research language. The authors say the project “never came to a formal conclusion; it simply faded away” as its members moved on to other research. The most recent public release is the 2005 SourceForge alpha. The project’s history site, emeraldprogramminglanguage.org, hosts the HOPL III paper, the original theses, the 1991 language report and scanned project documents from 1983-86, including Eden timing notes, the Getting to Oz memo and a photograph of the whiteboard that defined the system’s data structures.

Why It Matters

Emerald showed in the mid-1980s that distributed objects did not have to be slow or awkward. One object model covered everything from an integer to a remote service, and a compiler could make the local cases nearly as cheap as C. Its fine-grained object and thread mobility remained unusual: the authors noted in 2007 that in more than twenty years no other language had adopted mobile objects as thoroughly. Its structural, behaviour-based typing, adopted out of necessity in an open distributed system, foreshadowed ideas that became widespread decades later. Many of the ideas behind present-day distributed object and RPC systems were tried in Emerald on a handful of MicroVAX workstations in Seattle.