Cecil

Cecil is a purely object-oriented, garbage-collected programming language designed by Craig Chambers and the Cecil Group at the University of Washington in the early 1990s. It set out to combine features that other languages kept apart: a simple classless (prototype-based) object model like Self’s, symmetric multiple dispatch in the tradition of CLOS, a module system, and a static type system that programmers could use as much or as little as they liked. Cecil never left the research lab, but it was a working, self-hosting language - the Vortex optimizing compiler was written in it - and the ideas it tested, especially around typechecking multi-methods, open classes and predicate-based dispatch, fed directly into later research languages.

History and Origins

Chambers came to Cecil from the Self project at Stanford, where he had built the optimizing Self compiler; his Ph.D. thesis, The Design and Implementation of the Self Compiler, an Optimizing Compiler for Object-Oriented Programming Languages, was completed in March 1992. The Cecil specification credits a conversation with Danny Bobrow (one of the designers of CLOS) and David Ungar (co-creator of Self) at OOPSLA ‘89 as the original inspiration for the language. According to the project’s own history, the design effort proper began in early 1991.

The language was introduced publicly in the paper “Object-Oriented Multi-Methods in Cecil”, presented at ECOOP ‘92 in Utrecht, the Netherlands, in June/July 1992 and published in Springer’s Lecture Notes in Computer Science volume 615. The specification itself states that Cecil “was inspired initially by Self, CLOS, and Trellis”.

Implementation proceeded in stages:

The first full language report, The Cecil Language: Specification and Rationale, appeared as a UW technical report in March 1993. Later revisions added predicate objects, the module system and more efficient typechecking algorithms; the final revision, version 3.2, is dated February 2004.

Design Philosophy

The Cecil specification frames the design around two goals: letting programmers develop software quickly and reuse and modify it easily, and supporting the production of high-quality, reliable software. Much of the language follows from trying to satisfy both at once.

• A pure object model. All data are objects and are manipulated only by sending messages. Even instance variables (called fields) are read and written only through automatically generated accessor methods, so a field can later be replaced by a computed method, or vice versa, without changing any client code.
• Classless objects. Like Self, Cecil has no classes: objects inherit directly from other objects, and new “instances” are made by inheriting from an existing object. The designers considered this simpler and more powerful than class-based models, and it makes one-of-a-kind objects such as true, false and nil trivial to define. The specification notes that Cecil’s object model is somewhat more restricted than those of other prototype-based languages such as Self, in response to its other design goals; predicate objects, for instance, are offered as a more structured alternative to Self’s dynamic inheritance.
• Unbiased multiple dispatch. Method selection can depend on the run-time objects of any subset of a method’s arguments, and all dispatched arguments are treated symmetrically - unlike CLOS, where earlier arguments take priority over later ones. Multiple inheritance is likewise unbiased with respect to parent order; ambiguities are reported to the programmer rather than resolved by an ordering rule.
• Types are separate from inheritance. Cecil distinguishes the subtype graph (interfaces) from the code-inheritance graph (implementation reuse), while providing syntactic sugar for the common case where the two run in parallel.
• Optional static typing. Type declarations can be added incrementally. Where they are present, the typechecker ensures they are consistent; where they are omitted, dynamic checking still guarantees run-time type safety. The stated aim was to let a program migrate from an exploratory style to a production style without being rewritten.
• Immutability by default. Local variables and fields are initialize-only unless declared with var, encouraging a functional style.

Key Features

Objects and multi-methods

Methods are declared outside objects, and a formal argument can be specialized on an object with the @ notation. The following example is taken from the Cecil specification:

object shape;
  method draw(s, d) { (-- draws s on display d --) }
  method move_to(s, new_center) { (-- move s to new_center --) }
object circle isa shape;
  method area(c@circle) { c.radius * c.radius * pi }
  method circum(c@circle) { c.radius * 2 * pi }
object rectangle isa shape;
  method area(r@rectangle) { r.length * r.width }
  method circum(r@rectangle) { 2 * r.length + 2 * r.width }
  method draw(r@rectangle, d@Xwindow) {
    (-- override draw for the case of drawing rectangles on X windows --) }
object rhombus isa shape;
object square isa rectangle, rhombus;
  -- inherits area method, but overrides circum
  method circum(s@square) { 4 * s.length }

Here move_to behaves like an ordinary function (no specialized arguments), area and circum behave like single-dispatch methods, and the second draw is a true multi-method that is selected only when a rectangle is drawn on an X window. Callers cannot tell which kind they are invoking, so a plain procedure can later be split into specialized cases without touching client code. The indentation of methods under objects is purely a convention; methods are not syntactically contained in objects.

Predicate objects

Cecil’s most distinctive feature is the predicate object (introduced as “predicate classes” at ECOOP ‘93). A predicate object is a virtual child of some parent object that an object automatically inherits from whenever a boolean expression over it is true. Because that expression can test mutable state, an object’s classification can change as the program runs. The specification illustrates this with a bounded buffer:

object buffer isa collection;
  field elements(b@buffer);   -- a queue of elements
  field max_size(b@buffer);   -- an integer
  method length(b@buffer) { b.elements.length }
  method is_empty(b@buffer) { b.length = 0 }
  method is_full(b@buffer) { b.length = b.max_size }

predicate empty_buffer isa buffer when buffer.is_empty;
  method get(b@empty_buffer) { ... }  -- raise error or block caller

predicate non_empty_buffer isa buffer when not(buffer.is_empty);
  method get(b@non_empty_buffer) { remove_from_front(b.elements) }

predicate full_buffer isa buffer when buffer.is_full;
  method put(b@full_buffer, x) { ... }  -- raise error or block caller

predicate non_full_buffer isa buffer when not(buffer.is_full);
  method put(b@non_full_buffer, x) { add_to_back(b.elements, x); }

Instead of an if inside get and put, each state of the buffer is named and carries its own methods, and ordinary method lookup chooses the right one.

Other features

• Closures - first-class, lexically nested anonymous functions in the style of Smalltalk blocks, used throughout the standard library for control structures, iterators and exception handlers.
• External extension - methods, fields and even parents can be added to an existing object from outside its original declaration, often in a separate module, supporting what the specification calls role-based or subject-oriented programming.
• Bounded parametric polymorphism - objects, types and methods can be explicitly or implicitly parameterized, with constraint-based bounds that subsume F-bounded polymorphism.
• Lazy field initializers - a field’s default initializer is evaluated when the field is first read, which lets it refer to the object being built and allows circular structures to be constructed.
• Modules - an encapsulation mechanism designed specifically to work in the presence of multi-methods and cross-module inheritance.
• User-declared precedence and associativity for infix operators.

The Vortex Compiler

Cecil’s main implementation grew into Vortex, a language-independent, whole-program optimizing compiler for object-oriented languages, written entirely in Cecil. Its OOPSLA ‘96 paper describes front-ends for Cecil, C++, Java and Modula-3; the project page also lists Smalltalk and, later, Diesel. Front-ends translate into a common intermediate language, and Vortex emits either portable C++ code or SPARC assembly.

Vortex was the platform for the group’s research on optimizing dynamically dispatched code, including:

• static intraprocedural and interprocedural class analysis, allowing message sends to be bound statically;
• class hierarchy analysis over the whole program;
• profile-guided receiver class prediction, inserting inline class tests for the most common receivers at a call site;
• selective procedure specialization driven by profile and class hierarchy information;
• closure optimizations such as stack-allocating closures that provably do not escape;
• selective recompilation, so that whole-program optimization remained usable during incremental development.

The final release, Vortex 3.3 (February 2006), shipped precompiled Cecil interpreter and Vortex executables for x86/Linux, x86/Cygwin on Windows and PowerPC/Mac OS X. The release notes state that older versions had also been built on SPARC (SunOS 4.x and Solaris), PowerPC/AIX, Alpha/OSF1 and HP-PA/HP-UX.

Evolution

Over its lifetime the Cecil language grew in three main directions, each documented in a conference paper:

1. Predicate objects (ECOOP ‘93), later generalized by Michael Ernst, Craig Kaplan and Chambers into predicate dispatching (ECOOP ‘98), a single mechanism that subsumes single and multiple dispatch, ML-style pattern matching and predicate classes.
2. Modular typechecking of multi-methods (Chambers and Leavens, OOPSLA ‘94), addressing how to typecheck independently developed modules that each add methods to shared generic operations.
3. Constraint-bounded polymorphism (Litvinov, OOPSLA ‘98), which was put to a practical test by typechecking the 100,000-line Vortex compiler; the paper reports that dynamically typed code needed very little rewriting.

In the 2000s the group’s attention moved on. MultiJava (Clifton, Leavens, Chambers and Millstein, OOPSLA 2000) brought open classes and symmetric multiple dispatch to Java, and work on extensible ML (EML) followed. Diesel, described by the group as Cecil’s successor, adopted a module system based on the MultiJava and EML work and simplified the object model. Diesel became the implementation language of the group’s next compiler, Whirlwind.

Current Relevance

Cecil is a historical research language. Its last language manual is from 2004, and its last implementation release, Vortex 3.3 in 2006, already advised using Diesel instead. The University of Washington still hosts the project pages and the 3.3 release page on an archival basis (some of the release tarballs no longer download), and there is no known active development or user community.

Why It Matters

Cecil was one of the earlier languages to take multiple dispatch out of the Lisp world and try to reconcile it with the things mainstream object-oriented programmers expected: encapsulation, modules, and static type checking. Its papers on modular typechecking of multi-methods and on predicate dispatch led directly to the same group’s MultiJava and Diesel, and its specification remains a detailed, candid record of the design trade-offs involved, from keeping code inheritance separate from subtyping to resolving dispatch ambiguities without argument-order bias. Just as significantly, Cecil showed that a pure, dynamically dispatched language with these features could be implemented well enough to write a large, self-hosting optimizing compiler in it.