CLU

CLU is a programming language designed at MIT by Barbara Liskov and her students between 1973 and 1979. It was the first implemented language to support abstract data types directly: a type is defined by the operations that can be performed on it, and the language guarantees that no other code can see how the type is represented. CLU was never widely used outside research and teaching, and its designers did not intend it to be. Its ideas spread anyway. Iterators with yield, exceptions that are part of a procedure’s declared interface, generic types checked at compile time, and multiple assignment all appear in CLU in forms that later languages adopted.

History and Origins

From modularity to abstract types

In 1972 Liskov was working on programming methodology, specifically on how to divide large programs into modules. She noticed that many of the modules described in the literature, including her own work on the Venus operating system, were really defining data types. This led to the idea of an abstract type: a set of objects together with a set of operations, whose representation is hidden from everything except those operations.

She presented the idea at a workshop in Savannah in April 1973 and then worked it out with Stephen Zilles, also at MIT, over the spring and summer. Their September 1973 paper said an abstract type would be implemented by a cluster, a module holding a description of the representation plus the code for all the operations. A later version of the paper, “Programming with Abstract Data Types”, appeared at the ACM SIGPLAN Symposium on Very High Level Languages in April 1974.

Liskov decided in spring or summer 1973 to build a complete language around clusters. In the fall of 1973 the language was named CLU, from the first three letters of “cluster”, and design work began in earnest. By then several basic choices had been made: types would be implemented by clusters, all objects would live in a garbage-collected heap, and type checking would be complete and static.

The design group

The four main designers were Liskov and three graduate students: Russ Atkinson, Craig Schaffert and Alan Snyder. Zilles was involved early on but moved to specification work by 1974. Bob Scheifler and Eliot Moss joined later. The group held weekly design meetings and recorded its decisions in internal design notes. There were 78 notes, from 6 December 1973 to 30 July 1979. Liskov led the project and made the final decisions; votes in design meetings were never binding.

The designers knew the existing languages well. Liskov described CLU’s semantic model as “largely borrowed from Lisp” and its syntax as Algol-like. Simula 67 was the closest existing language to what they wanted, but it did not enforce encapsulation or support user-defined generic types. The group chose not to adopt Simula’s inheritance, which Liskov called “a distraction from what we were trying to do”. She also said that Smalltalk, developed at the same time, was “completely unknown to us until around 1976.”

Implementation

Work on a compiler for a preliminary version, CLU .5, started in summer 1974. Snyder wrote the parser, Atkinson the code generator and Schaffert the type checker. The code generator first produced Lisp and later MDL, a Lisp dialect used at MIT. The compiler was first written in Lisp and soon rewritten in CLU, and it ran on the PDP-10. The CLU .5 reference manual was issued internally in January 1975. It covered all of CLU in some form except exceptions and iterators.

The rest of the language was designed by the end of 1976, and 1977 was spent reviewing and adjusting it. In 1977 the compiler was rewritten to generate macro-assembler, because compiling through MDL was slow. This meant the group had to write its own runtime system, garbage collector and debugger. A final design pass in 1979 added the resignal statement and own data, and the final reference manual was published in October 1979. By 1980 there was a compiler for the DECSYSTEM-20 good enough to give to other groups. It was later retargeted to the VAX and the Motorola 68000.

Liskov estimated that about fourteen person-years went into CLU between 1973 and the production compiler in 1980.

Which year?

The encyclopedia dates CLU to 1975. That is a reasonable date, but not the only one. The name and the design go back to fall 1973, and a compiler for CLU .5 existed in 1974. The first reference manual (January 1975), the exception mechanism (June 1975) and the iterator design (September 1975) all date from 1975. The first widely read description of the finished language, in Communications of the ACM, came in August 1977.

Design Philosophy

Liskov’s history says the main goal of the project was research on programming methodology, not a product. The group saw its main output as ideas and publications. “We did not think of CLU as a language that would be exported widely,” she wrote.

She listed the design principles the group applied deliberately:

• Keep focused. Features unrelated to data abstraction were not investigated. Concurrency was planned at first and then dropped. It was taken up later in Argus.
• Minimality. Features the designers were unsure about were left out. If users really needed them, they would complain.
• Simplicity. A construct was simple if it and its interactions could be explained easily.
• Expressive power. It should be easy to say what programmers needed to say.
• Safety. Errors should be prevented or caught early. This is why CLU has a garbage-collected heap, complete static type checking and no implicit type conversions.

The designers also avoided things they disliked in other languages. They thought Pascal had made too many compromises for the sake of easy implementation, and that Algol 68 had gone too far with overloading and coercions. CLU therefore has no overloading at all.

Key Features

Clusters

A cluster defines a type. Its header lists the operations visible outside the cluster, and the rep line gives the hidden representation. Inside the cluster, the special type cvt converts between the abstract type and its representation, so only the cluster’s own code can see the representation.

intset = cluster is create, insert, member, elements

    rep = array[int]

    create = proc () returns (cvt)
        return (rep$new())
    end create

    insert = proc (s: cvt, x: int)
        for e: int in rep$elements(s) do
            if e = x then return end
        end
        rep$addh(s, x)
    end insert

    member = proc (s: cvt, x: int) returns (bool)
        for e: int in rep$elements(s) do
            if e = x then return (true) end
        end
        return (false)
    end member

    elements = iter (s: cvt) yields (int)
        for e: int in rep$elements(s) do
            yield (e)
        end
    end elements

end intset

Code outside the cluster can only call intset$create, intset$insert, intset$member and intset$elements. It cannot tell that an intset is an array, so the representation can be changed without changing any code that uses it.

Explicit operation names and syntactic sugar

Every operation belongs to a type and is named type$operation, for example intset$insert(s, 3). This removes any need for overloading. Operators are shorthand: x + y is rewritten by the compiler as t$add(x, y), where t is the type of x. The same rule applies to built-in and user-defined types, so a user-defined type gets + just by naming an operation add. Liskov reported that, to her surprise, users liked the t$o notation because they believed it improved program correctness and readability.

Iterators

Iterators are CLU’s best-known contribution. An iterator is a routine that yields values one at a time to a for loop:

evens = iter (lo, hi: int) yields (int)
    i: int := lo
    if int$mod(i, 2) ~= 0 then i := i + 1 end
    while i <= hi do
        yield (i)
        i := i + 2
    end
end evens

% usage:
%   for n: int in evens(1, 10) do ... end

The idea came from generators in Alphard, the data-abstraction language being developed at Carnegie Mellon. The CLU group saw them on a visit to CMU in summer 1975 and thought they were too complicated. Russ Atkinson designed CLU’s iterators on the flight back to Boston and wrote them up in a design note in September 1975. CLU iterators were deliberately restricted, so that they can be nested but not run side by side. In return they can be implemented on a single stack: each yield is effectively a call to the body of the loop.

Exceptions

A CLU procedure declares the exceptions it can raise as part of its signature, raises them with signal, and callers handle them with except when:

pop = proc (s: stack) returns (int) signals (empty)
    ...
end pop

n: int
n := int$parse(text)
   except when bad_format, overflow: n := 0
   end

CLU uses the termination model: a procedure either returns normally or ends in one of its named exceptions. The designers rejected the resumption model of PL/I and Mesa as too complex. CLU also does not propagate exceptions automatically. An exception that the caller does not handle becomes the special exception failure, so a procedure can never raise an exception that is not in its specification. The main principles were settled by June 1975 and the design was complete by fall 1977. Because exceptions were implemented cheaply, CLU programmers used them as an ordinary way to return information to the caller, not only for errors.

Parameterized types

Built-in types such as array are type generators: array[int] and array[string] are different types. Users can write their own generators, and a where clause states what operations a type parameter must provide:

set = cluster [t: type] is create, member, size, insert, delete, elements
    where t has equal: proctype (t, t) returns (bool)

The compiler checks each instantiation against the where clause, so parameterized code is fully type-checked. In CLU .5, parameterized types were still checked at run time; the where clause came later. Liskov wrote in 1992 that CLU “was way ahead of its time” here, since most languages still lacked parametric polymorphism.

Other features

• Multiple assignment and multiple return values: x, y := y, x, and q, r := divide(a, b).
• Mutable and immutable type pairs: array/sequence, record/struct, and variant/oneof. The last two are tagged unions.
• First-class procedures that can be passed, returned and stored. They cannot have free variables, so CLU has no closures. Liskov counted closures and recursive type definitions as the main missing features.
• Type any, the union of all types, with a checked run-time force to recover the real type.
• A program library of interface descriptions, so modules could be type-checked against the interfaces of modules not yet written.

Evolution

Once the design was frozen in 1979, CLU changed very little. Work moved to implementations and to successor languages:

Dorothy Curtis did the Portable CLU work. The 3.7 README says plainly that “CLU is no longer actively maintained” and that the release updated 3.6 for 64-bit Linux, tested on Debian 8.6. Enthusiasts have since patched PCLU further. One fork (nbuwe/pclu, mirrored on GitHub) describes itself as “Portable CLU fixed to actually work,” and a separate clu2c translator exists as well.

The closest successor is Argus, which Liskov’s group developed next. It adds guardians and atomic transactions for distributed programs, and some features CLU lacked. At Cambridge, CCLU extended CLU for concurrent systems programming.

Current Relevance

CLU itself is a historical language. Nobody develops it, and in practice the way to run it today is Portable CLU on Unix-like systems (or one of the community-patched forks) or the archived PDP-10 files. There is no Docker image. In 2021 MIT’s Department of Distinctive Collections published CLU files from 1976 to 1989, recovered from the Tapes of Tech Square backup tapes. The collection includes the 1977-78 CLUSYS runtime and version 3.x compilers from 1978.

The ideas are still widely used. Liskov’s 1987 OOPSLA keynote “Data Abstraction and Hierarchy” came out of the same line of work and is the source of the Liskov substitution principle. In 2009 she received the 2008 ACM A.M. Turing Award for contributions to programming language and system design, particularly data abstraction, fault tolerance and distributed computing.

Why It Matters

Liskov’s 1992 history names Ada, C++, ML, Modula-3 and Trellis/Owl as languages influenced by CLU. Other designers have said the same about their own languages:

• C++: Bjarne Stroustrup’s history of C++ says “the main sources for ideas for C++ were Simula, Algol68, and later Clu, Ada, and ML”. His 1986 paper “What is Object-Oriented Programming?”, quoted there, lists “Ada, Clu, and ML” as supporting parameterized types that C++ then lacked, and “Ada, Algol68, and Clu” as having standard exception handling.
• Lua: The Lua designers’ HOPL III paper states: “From CLU we took multiple assignment and multiple returns from function calls.”
• Sather and Python: Python’s PEP 255, which added generators, points to “iterators in Sather, which were inspired by iterators in CLU.”
• Ruby: Yukihiro Matsumoto has said Ruby’s blocks came from CLU’s iterators, according to a 2019 AppFolio Engineering account of Ruby’s roots.
• Swift: Chris Lattner’s 2014 homepage note lists CLU among the languages whose experience Swift drew on.

CLU had these ideas decades before most of the languages that use them today: encapsulation enforced by the compiler, generic code checked without access to its implementation, exceptions as part of a procedure’s contract, and iteration that separates producing values from using them. Its designers set out to influence other languages rather than to be widely used, and that is what happened.