Cω (C-Omega)

Cω is an experimental programming language from Microsoft Research that extends C# in two directions: asynchronous concurrency, and typed access to relational and XML data. The name is the letter C followed by a lower-case Greek omega. Microsoft’s own page says it is pronounced “c” followed by a phonetic respelling of the word omega, and that “it can be written (and searched for) as Cw or the ‘Comega language’”. The compiler was called cwc.exe, source files ended in .cw, and the installer is still named Comega1_1.0.4220.0.msi.

Cω was never a product. Its documentation said so under a bold “Important” label at the top of the overview: “Cω is an experimental research language. There are no plans to turn it into a commercial language supported by Microsoft. It is not supported by either the C# or the Visual Studio teams.”

A note on this entry

The master list this encyclopedia follows carries the language twice, once as Cω (C-Omega) and once as Comega. They are the same language under two spellings. The Comega page covers the data side in detail: streams, anonymous structs, content classes, XML literals, the SQL-style select expressions, and the path from there to LINQ. This page concentrates on the other half, the concurrency constructs that Cω inherited from Polyphonic C#, and on the dating of the releases.

History & Origins

The join calculus

The concurrency model comes from the join calculus, a process calculus that Cédric Fournet and Georges Gonthier introduced in “The reflexive CHAM and the join-calculus” at POPL ‘96. Its distinguishing feature is the join pattern: a single rule can wait for messages on several channels at once and fire only when all of them have arrived. JoCaml put the idea into a functional language. The Cω documentation names both as sources: “we took ideas from a theoretical model called the join calculus and a join-based concurrent functional language called JoCaml.”

Polyphonic C#

At Microsoft Research in Cambridge, Fournet, Nick Benton and Luca Cardelli worked out what a join pattern would look like in an object-oriented language. The result was Polyphonic C#. The paper, “Modern Concurrency Abstractions for C#”, was presented at the FOOL 9 workshop in January 2002 and at ECOOP 2002 in Málaga that June, and a revised version appeared in ACM Transactions on Programming Languages and Systems in September 2004.

Polyphonic C# does not seem to have had a public compiler of its own. Archived copies of the project page from May 2002 through mid-September 2004, by which time the Cω preview was already out, list under resources “Our prototype compiler. Coming real soon now. Honest.” What the page did offer was the paper, slides, a poster “for your office or bedroom”, and a Dining Philosophers demo as source plus a .NET executable.

The merger

Meanwhile Erik Meijer, Wolfram Schulte and Gavin Bierman were working on a data-oriented extension of C#, known at different times as X# and as Xen. In 2004 the two efforts were put under one name. The Microsoft Research project page gives 8 April 2004 as the date the project was established. The web address is slightly older than that: the Internet Archive holds a capture from 26 March 2004 that shows only a Cω logo. An archived copy from 11 May 2004 already describes Cω as “an extension of C# in two areas”: a control flow extension “formerly known as Polyphonic C#” and a data type extension “formerly known as Xen and as X#”.

The Cω tutorials are direct about how little changed on the concurrency side: “The new constructs are a mild syntactic variant of those we have previously described under the name ‘Polyphonic C#’.”

The compiler preview

The 11 May 2004 copy of the project page has no download. The copy from 26 July 2004 says: “A Cω compiler preview is now available for download. This release requires Visual Studio .NET 2003 to be installed on the target machine.” So the first public release falls between those two dates, in mid-2004.

A second release followed in the autumn. The page captured on 21 October 2004 still has the Visual Studio requirement; the one from 20 November reads “This new release no longer requires Visual Studio .NET 2003 to be installed on the target machine!” The October 2004 date sometimes quoted for the preview probably refers to this second release.

By November 2004 the page listed six project members: Nick Benton, Gavin Bierman, Luca Cardelli, Erik Meijer, Claudio Russo and Wolfram Schulte.

Design Philosophy

The Cω overview states three principles:

1. Asynchronous concurrency and the processing of relational and semi-structured data “are sufficiently important that they should be directly supported in a modern general purpose programming language”. The stated benefits are stronger compile-time guarantees, intentions that are visible in the code rather than “buried in the dynamic flow of control into mysterious library routines”, more freedom for the compiler, more natural syntax, and better tool support.
2. “We should extend an already-popular language, rather than design a new one from scratch.”
3. “The extensions should be principled”, taking models from more academic, special-purpose languages and fitting them into the mainstream object-oriented framework.

The argument for the concurrency half was that mainstream languages were stuck with what the overview calls the “1970s threads and locks model which is implemented entirely in terms of library routines”, while applications were being pushed towards one-way asynchronous messaging over networks, where “incoming messages arrive at unpredictable times and in unpredictable orders”.

Key Features

Asynchronous methods

A method in Cω is either synchronous, as in C#, or asynchronous. An asynchronous method is declared with the new keyword async in place of a return type. Calling it returns immediately and yields no result. The documentation compares it to posting a letter rather than asking a question face to face.

One detail differs from the usual .NET pattern of the time. In .NET the caller chose to invoke a method asynchronously. In Cω the callee declares that a method is asynchronous.

Cω’s async has nothing to do with the async modifier that C# gained in version 5.0 in 2012, which marks a method that can await. The two share a word and a general subject, not a meaning.

Chords

In C#, each declared method has exactly one body. In Cω a body can be attached to a set of methods. Such a definition is called a chord, and its body can run only once every method in its header has been called. This is the simplest example in the documentation:

1
2
3
4

public class Buffer {
    public async Put(string s);
    public string Get() & Put(string s) { return s; }
}

Put never blocks; its argument is queued. Get blocks until some Put is available to pair with, and then returns that string. No locks appear in the source. The documentation notes that the compiler generates the locking, and that the locking “is fine-grained and brief”: polyphonic methods do not lock the whole object and do not run with monitor semantics.

The rules for what happens on a call are spelled out:

• If no chord is enabled, the call is queued. An asynchronous call queues its arguments; a synchronous call blocks its thread.
• If one chord is enabled, the matched calls are de-queued and the body runs.
• If several chords are enabled, “an unspecified one of them is chosen to run”. Which queued call is consumed is likewise unspecified.
• A chord can contain at most one synchronous method, and that method receives the return value.

A synchronous method may have several chords, each with its own body:

1
2
3
4
5
6
7

public class Buffer {
    public async Put(string s);
    public async Put(int n);
    public string Get()
        & Put(string s) { return s; }
        & Put(int n)    { return n.ToString(); }
}

Messages as state

Private asynchronous methods can carry an object’s state, so that a class needs no fields. This counter, from the tutorial on the technique, keeps its value in a pending mystate message:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public class Counter {
    async mystate(long i);
    public Counter() {
        mystate(0);
    }
    public void Inc() & mystate(long i) {    // acquire the state
        mystate(i+1);
    }
    public long Value() & mystate(long i) {
        mystate(i);
        return i;
    }
}

At any moment there is at most one mystate message pending. A thread that consumes it has exclusive access until it sends the next one.

The same pattern turns chords into a readable state machine. The documentation’s reader-writer lock uses two private messages, idle() and s(n), where n is the number of current readers:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public class ReaderWriter {
    private async idle();
    private async s(int n);
    public ReaderWriter() { idle(); }

    public void Exclusive() & idle() { }
    public void ReleaseExclusive() { idle(); }

    public void Shared()
        & idle()   { s(1); }
        & s(int n) { s(n+1); }

    public void ReleaseShared() & s(int n) {
        if (n == 1) idle(); else s(n-1);
    }
}

Each chord reads as one transition. A writer may proceed only when the lock is idle. A reader may proceed when it is idle or when there are already readers. There is no chord for a writer arriving while readers hold the lock, so that writer simply waits. The documentation points out that this version raises a fairness question and refers to the Polyphonic C# paper for a variant that addresses it.

Spawning threads with when

A chord that contains only asynchronous methods has no caller waiting for it, so its body runs in a new thread. Such chords are introduced by a second new keyword, when:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

using System;
using System.Threading;

public class SpawningTutorial {
    static async m(string s);

    static void Main() {
        m("thread one");
        m("thread two");
    }

    when m(string s) {
        while (true) {
            Console.WriteLine(s);
            Thread.Sleep(1000);
        }
    }
}

Each call to m returns at once and starts a thread with its argument, which in the C# of the time took a ThreadStart delegate and some extra work to pass parameters.

Rules from the specification

The language specification’s section on concurrency constructs adds some constraints and typing rules:

The inheritance rule exists because synchronization and subclassing interact badly: a subclass that replaced one method of a chord but not the others could break the superclass’s synchronization. Cω’s restriction keeps a chord’s methods together.

The data extensions

The other half of Cω adds stream types, anonymous structs, choice types, XML literals, XPath-like member access and SQL-style query expressions to C#. The documentation summarizes it as a language “that bridges the gap between semi-structured hierarchical data (XML), relational data (SQL), and the .NET Common Type System”. Those features are described on the Comega page.

Evolution

There was no later version of Cω. After the two 2004 releases of the compiler preview the project page changed only in its news links and references, and no later compiler build is listed there. The installer Microsoft hosts today, Comega1_1.0.4220.0.msi, appears to be that 2004 preview, though the Download Center listing does not say which of the two releases it is.

The concurrency constructs moved on in other forms:

• The Joins Concurrency Library. Once C# 2.0 had generics, Claudio Russo showed that join patterns could be provided as a library instead of a compiler. The PADL ‘07 paper lists the trade: the library is language-neutral and its patterns can be built at run time, but it offers the compiler fewer opportunities for optimization than a language feature does.
• Visual Basic. Russo’s “Join Patterns for Visual Basic” (OOPSLA 2008) went back the other way and put the constructs into a language again.
• Scalable joins. “Scalable Join Patterns” by Aaron Turon and Russo (OOPSLA 2011) revisited the implementation for multiprocessors, comparing a join-calculus library with specialized algorithms on seven coordination problems.

Join patterns also appeared outside .NET in the same years, for example in Philipp Haller and Tom Van Cutsem’s “Implementing Joins Using Extensible Pattern Matching” for Scala (COORDINATION 2008).

The data constructs went into LINQ, which Microsoft released with .NET Framework 3.5 in 2007.

Current Relevance

Cω is a historical language. The compiler preview can still be downloaded from the Microsoft Download Center, where the listing gives version 1.0.2 and a description that begins “Comega is an experimental language which extends C# with new constructs for relational and semi-structured data access and asynchronous concurrency”. The listing’s publication date and supported-systems line have been refreshed since the 2004 release and say little about the software’s age. The original requirement, per the 2004 project page, was Visual Studio .NET 2003, and later no Visual Studio at all.

Microsoft Research keeps a project page with the overview and samples text. The fuller 2004 documentation (tutorials, language specification and compiler reference) survives mainly in web archives.

Nobody writes new software in Cω. It is read today for two reasons: as the first public compiler for the chord constructs of Polyphonic C#, and as the research prototype behind LINQ.

Why It Matters

Cω showed that a join pattern, a construct from process-calculus theory, could be written as an ordinary-looking class member and understood by reading it aloud: when Get and Put have both been called, return the string. A buffer takes two lines, a semaphore two, and a reader-writer lock about fifteen, with the synchronization policy visible in the declarations and the locking left to the compiler.

The language also shows how research ideas reach working programmers without the research language surviving. Neither half of Cω shipped under its own name. The data half became a mainstream language feature. The concurrency half became a library, then a proposal for another language, then a subject of further research on scalability.

Sources

• Comega project page, Microsoft Research (establishment date, overview)
• Archived copies of research.microsoft.com/Comega/ from 11 May, 26 July, 21 October and 20 November 2004 in the Internet Archive (release dating, project members) and from 26 March 2004, December 2005 and January 2006 (logo-only placeholder, the LINQ notice), and of the Cω documentation under /Comega/doc/ from August and September 2004 (overview with the “no plans” notice, tutorials and language specification quoted above)
• Polyphonic C#, Nick Benton, and archived copies of research.microsoft.com/~nick/polyphony/ from 2002 to 2004
• Benton, Cardelli and Fournet, “Modern Concurrency Abstractions for C#”, ECOOP 2002 (LNCS 2374) and ACM TOPLAS 26(5), 2004
• Bierman, Meijer and Schulte, “The Essence of Data Access in Cω”, ECOOP 2005 (LNCS 3586)
• Russo, “The Joins Concurrency Library”, PADL 2007
• Turon and Russo, “Scalable Join Patterns”, OOPSLA 2011
• Comega compiler preview, Microsoft Download Center
• Dare Obasanjo, “Introducing Comega”, XML.com, 12 January 2005