CLU (637/clu001)

CLUster programming language - abstractions and iterators 

for CLUster. 1974-1975.

CLU is an object-oriented language of the Pascal family designed to support data abstraction, similar to Alphard.

Introduced the iterator: a coroutine yielding the elements of a data object, to be used as the sequence of values in a 'for' loop.

A CLU program consists of separately compilable procedures, clusters and iterators, no nesting. A cluster is a module naming an abstract type and its operations, its internal representation and implementation.

Clusters and iterators may be generic. Supplying actual constant values for the parameters instantiates the module. There are no implicit type conversions. In a cluster, the explicit type conversions 'up' and 'down' change between the abstract type and the representation. There is a universal type 'any', and a procedure force[] to check that an object is a certain type. Objects may be mutable or immutable. Garbage collection is built in. Exceptions are raised using 'signal' and handled with 'except'. Assignment is by sharing, similar to the sharing of data objects in LISP.

Arguments are passed by call-by-sharing, similar to call by value, except that the arguments are objects and can be changed only if they are mutable. CLU has own variables and multiple assignment.

TED (a text editor), R (a document formatter), SWIFT (an operating system), and lp (a proof tool used for formal specification) have been written in CLU.

Related languages
Alphard => CLU   Influence
MDL => CLU   Written using
Pascal => CLU   Based on
VERS => CLU   Influence
CLU => Argus   Evolution of
CLU => ASBAL   Derivation of
CLU => CAMIL   Influence
CLU => Capsule   Influence
CLU => CCLU   Extension of
CLU => Cluster 86   Influence
CLU => HERAKLIT   Incorporated some features of
CLU => Larch/CLU   Spec written in
CLU => LIMBO   Incorporated some features of
CLU => MODEL   Influence
CLU => PLAIN   Influence
CLU => Ruby   Influence
CLU => Sather   Influence
CLU => VAL   Based on
CLU => XE   Adaptation of

  • Liskov, B., A Note on CLU, Computation Structures Group Memo 112, MIT Project MAC, Cambridge, Mass. (Nov. 1974). view details
  • Horning, J. J. "Some desirable properties of data abstraction facilities" pp60-62 view details Abstract: It is currently popular to say that programming languages need ?data abstraction facilities,? and to assert that the provision of such facilities would provide conceptual and practical advantages in the domain of data structures akin to the advantages provided by procedures in the domain of computational structures. This note explores some of the implications of this metaphor, without attempting to make it precise. I shall use the term capsule to refer to the data analog of procedure. [Those who are familiar with the SIMULA class, the CLU cluster, or the ALPHARD form, may use any of these as an approximation to capsule; I use a neutral term to avoid implying the details of any particular language.] First, what are the advantages provided by procedures (subroutines, functions, macros)? I can think of at least eight (highly interrelated) categories: 1) avoidance of repetition, 2) modular program structure, 3) a basis for structured programming, 4) conceptual units for understanding and reasoning about programs, 5) clearly defined interfaces that may be precisely specified, 6) units of maintenance and improvement, 7) a language extension mechanism, and 8) units for separate compilation. Let us consider each of these in turn.
    DOI Extract: Euclid Modules
    2 Euclid Modules
    The module in Euclid is an encapsulation mechanism whereby the representation of an abstract object and the implementation of associated operations can be hidden from the enclosing scope. Multiple instances of an abstraction can be realized from the definition of a module type by declaring variables of that type. Closed scopes, and modules in particular, provide explicit control over the visibility of identifiers. Objects, operations, and types defined within the module must be explicitly exported in order to be used; similarly, values of variables declared outside a module must be imported explicitly to be known inside.
    Extract: Modules as Abstraction Mechanisms
    2.1 Modules as Abstraction Mechanisms
    A data type is defined by a set of values and a set of operations on those values. An abstract data type is a data type with a representat ion-independent definition. Thus, abstract data types permit access by outside routines only to the abstract values and operations, and not to any of the underlying representation. In this sense, clusters in CLU [Liskov et ai.77] and forms in Alphard [Wulf et al. 76] are abstract data types, whereas classes in Simula 67 [Dahl et al.68] are not, since all data structures in the outermost scope of a class are accessible. Palm, [73] has shown, however, how the necessary protection could be added to Simula 67 in a straightforward way.
    For reasons similar to those for Simula 67 classes, Euclid modules are not true abstract data types. Access to identifiers within a module is severely restricted by the import and export clauses as well as the Euclid scope rules~ but access is allowed. Euclid modules can be used, hoverers to implement abstract data types. This would require additional programmer disciplines unenforceable by the language itself to ensure that the only entities accessible to outside routines are those abstract entities being defined.

          in SIGPLAN Notices 11(02) February 1976 also Proceedings of the SIGPLAN '76 Conference on Data: Abstraction, Definition and Structure, Salt Lake City, Utah, USA, March 22-24, 1976 view details
  • Foster, J. M. and Foster, P. D. Abstract data and functors pp161-167 view details
          in Proceedings of the Strathclyde ALGOL 68 conference Glasgow, Scotland 1977 view details
  • Liskov, Barbara; Snyder, Alan; Atkinson, Russell; Schaffert, Craig "Abstraction mechanisms in CLU" view details Abstract: CLU is a new programming language designed to support the use of abstractions in program construction. Work in programming methodology has led to the realization that three kinds of abstractions—procedural, control, and especially data abstractions—are useful in the programming process. Of these, only the procedural abstraction is supported well by conventional languages, through the procedure or subroutine. CLU provides, in addition to procedures, novel linguistic mechanisms that support the use of data and control abstractions. This paper provides an introduction to the abstraction mechanisms in CLU. By means of programming examples, the utility of the three kinds of abstractions in program construction is illustrated, and it is shown how CLU programs may be written to use and implement abstractions. The CLU library, which permits incremental program development with complete type checking performed at compile time, is also discussed. DOI
          in [ACM] CACM 20(08) (Aug 1977) view details
  • Atkinson, Russell R.; Liskov, Barbara H.; Scheifler, Robert W. "Aspects Of Implementing CLU" pp123-129 view details Abstract: Linguistic mechanisms used in CLU to support 1) structured exception handling, 2) iteration over abstract objects, and 3) parameterized abstractions are briefly reviewed, and methods of realizing these mechanisms are described. The mechanisms discussed support features that are likely to be included in other programming languages, and the implementation methods should be applicable to a wide range of languages.
          in Proceedings of the 1978 annual conference 1978, Washington, D.C., United States view details
  • Sammet, Jean E "Roster of programming languages for 1976-77" pp56-85 view details
          in SIGPLAN Notices 13(11) Nov 1978 view details
  • B. Liskov, R. R. Atkinson, T. Bloom, E. B. Moss, R. Schaffert and A. Snyder "CLU REFERENCE MANUAL" MIT/LCS/TR-225 October 1979 view details Abstract: This document serves both as an introduction to CLU and as a language reference manual. Sections 1 through 4 present an overview of the language. These sections highlight the essential features of CLU, and discuss how CLU differs from other, more conventional, languages. Sections 5 though 13 form the reference manual proper. These sections describe each aspect of CLU in detail, and discuss the proper use of various features. Appendices 1 though III provide concise summaries of CLU's syntax, data types, and I/O facilities. Appendix IV contains example programs.
    External link: Online copy Extract: History of CLU
    History of CLU
    The development of CLU began in January 1971. By the summer of 1975, the first version of the language had been completed. Over the next two years, the entire language design was reviewed and two implementations were produced. Based on this review, and on the experience gained in using CLU, a second version of the language was designed in the fall of 1977, and a new implementation is now complete. A preliminary version of this manual appeared in July 1978. Since that time, an additional statement for exception handling, an own variable mechanism, and three new basic type generators have been added to the language, and a number of minor changes have been made to the I/0 facilities.
    Extract: Modules
    1. Modules
    A CLU program consists of a group of modules. Three kinds of modus are provided, one for each kind of abstraction that we have found to be useful in program construction. Procedures support procedural abstraction, iterators support control abstraction, and clusters support data abstraction.
    1.1 Procedures
    A procedure performs an action on zero or more argument objects, and terminates returning zero or more result objects. All communication between a procedure and its invoker generally takes place through these arguments and results; a procedure has no global variables unless it is defined in a cluster that has own variables. A procedure may retain opts from one invocation to the next through the use of local own variables.
    A procedure may terminate in one of a number of condition^. One of these is the normal condition; the others are exceptional conditions. Differing numbers and types of results may be returned in different conditions. All information about the names of conditions and the number and types of arguments and results is described in the procedure heading. For example.
    square_root = proc (X: real) returns (real) signals (no_real_result)
    is the heading of a square_root procedure, which takes a single real argument. Square_root terminates either in the normal condition (returning the square root of X) or in the no_real_result condition (returning no results).

    1.2 Iterators
    An iterator computes a sequence of items based on its input arguments. These items are provided to its invoker one at a time. Each item consists of zero or more objects. An iterator is invoked by a for statement. The iterator provides each item by yielding it. The objects in the item are assigned to the loop variables of the for statement, and the body of the for statement is executed. Then control is returned to the iterator so it can yield the next item in the sequence. The for loop is terminated when the iterator terminates, or the for loop body may explicitly terminate itself and the iterator.

    Just like a procedure, an iterator has no global variables unless it is defined in a cluster that has own variables. An iterator may retain objects from one invocation to the next through the use of local own variables. An iterator may also terminate in one of a number of conditions. In the normal condition. no results can be returned, but different numbers and types of results can be returned in the exceptional conditions. All information about the names of conditions, and the number and types of arguments and results is described in the iterator heading. For example,
    leaves iter (t: tree) yields (node)
    is the heading for an iterator that produces all leaf nodes of a tree object. This iterator might be used in a for statement as follows:
    for leaf: node in leaves(x) do
    ... examine(leaf) ...

    1.3 Clusters
    A cluster implements a data abstraction, which is a set of objects and a set of primitive operations to create and manipulate those objects. The operations can be either product or control abstractions. The cluster Reading states what operations are available, e.g.,
    int-set = cluster Is create, insert, elements
    states that the operations of int-set are create, insert, and elements.
    A cluster is used to implement a distinct data type, different from all others. Users of this type are constrained to treat objects of the type abstractly. That is, the objects may be manipulated only via the primitive operations. This means that information about how the objects are actually represented in storage may not be used.
    Inside the cluster, a concrete representation (in terms of some other type) is chosen for the objects, and the operations are implemented in terms of this representation. Each operation it implemented by a routine (a procedure or iterator); these routines are exactly like those not contained in clusters, except that they can treat the objects being defined by the cluster both abstractly and in terms of the concrete representation. (The ability to treat objects abstractly it useful when defining recursive data structures, where the concrete representation makes use of the new type.) A cluster may contain additional procedures and iterators, which are purely for local use; these routines do not define operations of the type. The routines in a cluster are not considered to be separate modules; they are simply part of the cluster module.
    A cluster may also contain own variables, whose lifetimes are independent of routine
    activations. These variables are globally available to a11 routines in the cluster, but are not
    available from outside the cluster.
    1.4 Parameterized Modules
    Procedures, iterators, and clusters can all be parameterized. Parameterization provides the
    ability to define a class of related abstractions by means of a single module. Parameters are limited
    to the following types: int, real. b d , char, string, null, and type. The most interesting and
    useful of these are the type parameters.
    When a module is parameterized by a type parameter, this implies that the module was written
    without knowledge of what the actual parameter type would be. Nevertheless, if the module is to
    do anything with objects of the parameter type, certain operations must be provided by any actual
    type. Information about required operations is described in a where clause, which is part of the
    heading of a parameterized module. For example.
    set = cluster [t: type1 is create, insert, elements
    where t has equal: proctype (t, t) returns ( b d
    is the heading of a parameterized cluster defining a generalized set abstraction. Sets of many
    different element types can be obtained from this cluster, but the where clause states that the
    element type is constrained to provide an equal operation.
    To use a parameterized module, actual values for the parameters must be provided, using the
    general form
    module-name [ parameter-values ]
    Parameter values must be computable at the time they are compiled. .Providing actual parameters
    selects one abstraction out of the class of related abstractions defined by the parameterized module;
    since the values are known at compile-time, the compiler can do the selection and can check that
    the where clause restrictions are satisfied. The result of the selection, in the case of a
    parameterized cluster, is a type, which can then be used in declarations; in the case of
    parameterized procedures or iterators, a procedure or iterator is obtained, which is then available
    for invocation. For example, setCintl is a use of the set abstraction shown above, and is legal
    because int does have an equal operation.
    A parameterized cluster, procedure, or iterator is said to implement a type generator, procedure
    generator. or iterator generator, respectively.
    1.6 Program Structure
    As was mentioned before, a program consists of a group of modules. Each module defines
    either a single abstraction or, if parameterized, a class of related abstractions. Modules are never
    embedded in other modules. Rather, the program is a single level structure, with all modules
    potentially usable by all other modules in the program. Type-checking of inter-module references
    is carried out using information in the module headings, augmented, in the case of clusters, by the
    headings of the procedures and iterators that implement the operations.
    Each module is a separate textual unit, and is compiled independently of other modules.
    Compilation and program construction are discussed in Section 4.
          in SIGPLAN Notices 13(11) Nov 1978 view details
  • Samet, P. A. review of Atkinson et al 1978 (CLU) view details Abstract: CLU is a programming language designed to give users the convenient support of a wider class of abstract objects than can be found in other languages, namely, procedural, control, and data abstractions. Of these, only the procedural abstractions are well supported elsewhere, by subroutines, for instance.

    The present paper covers the way in which three of the implementation problems of CLU features have been overcome. The first of these deals with the handling of exceptional conditions, e.g. actions to be taken on attempted division by zero, and how this can be included flexibly within the language definition. The second problem involves the generalization of iteration statements (for statements) where the successive values of the control variable are suitably selected from the collection of possible values, and the phrase "suitably selected" allows a very wide interpretation. Last, there is a discussion of parameterized modules, including, for example, ways in which data of variable types can be processed, with the type as one of the parameters.

    This is an interesting paper, but one which is difficult to follow without knowledge of other work on CLU (which is, however, listed in the references).

          in ACM Computing Reviews 20(11) November 1979 view details
  • Liskov, Barbara et al; "CLU Reference Manual", LNCS 114, Springer 1981 view details
          in ACM Computing Reviews 20(11) November 1979 view details
  • Steensgaard-Madsen, J. " Statement-Oriented Approach to Data Abstraction" pp1-10 view details Extract: Introduction

    Programming languages traditionally offered procedures and functions as the only means of abstraction, that is, of providing powerful and high-level concepts while suppressing the details of their realization. The last ten years have seen many efforts to devise better abstraction facilities. SIMULA 67, Concurrent PASCAL, MODULA, CLU, and MESA are some of the newer languages offering abstraction mechanisms.

    The facilities offered by those languages are intended to hide by abstraction the interplay of different operations on the same data and to prevent access to the common data except by use of the abstract operations. Most researchers have looked to the type concept as a basis for an abstraction mechanism. However, no single type-based approach has been generally accepted.

    The approach taken in this paper differs from previous ones in a fundamental way. It is not based on a generalization of the type concept. Instead, the emphasis is on statements and procedures.

    The syntax we introduce is similar to that used for other proposed abstraction mechanisms. In order to avoid confusion, the reader must initially assume a simplified notion of types. A type is considered to be a set of values. From a theoretical point of view a type is considered to be a set component of an algebra, and a distinction is made between an algebra and its sets of values. This attitude differs essentially from Guttag and Horning's [5]. The algebra itself can be identified with other parts of this proposal, but this is not done explicitly here.

    This paper introduces the proposed language constructs in steps, each including examples. Section 2 concentrates on how to use an abstraction; it is divided into subsections of increasing complexity. Section 3, showing how abstractions are defined, is also subdivided according to complexity. Section 4 specifies the semantics using rewriting rules and thus indicates a possible implementation. Section 5 presents some final remarks.
          in TOPLAS 3(1) January 1981 view details
  • Spector, David "Ambiguities and insecurities in Modula-2" pp43-51 view details Extract: Introduction
    While it is not yet clear whether Ada, BLISS, Mary/2, Modula-2, Mesa, C, CLU, Edison, Concurrent Euclid, Icon, Newton, PLAIN, PLUS, Praxis, Smalltalk, SQURL, Y, or some other language is "best" for systems programming, each language represents an advance towards the goal of supporting an understandable and efficient organization of the many details and relationships inherent in systems programming.
    Unfortunately, no one language has yet achieved the delicate balance between simplicity and power that would distinguish it as ideal, but it appears that Modula-2 comes quite close. Modula-2 represents a step forward in language design, both because it incorporates existing features instead of inventing its own, and because of its evident concern for simplicity.
    Modula-2 offers the following valuable language features:
    Few primitive datatypes are defined, few control constructs are supported (there is no "go to"), and input-output operations are not provided as part of the language (they can be provided via extensions written in Modula-2). This simplicity allows for easier standardization and better portability than can be achieved with most other languages.
    A module is a named collection of variables and procedures, similar to an Ada package. It controls the interfacing and encapsulation of the conceptual parts making up large software systems. Modules provide a more flexible solution to the problem of partitioning the name space of a large program than does the more familiar hierarchical nesting of procedures. They are so valuable they are even being force-fitted onto existing languages.
    Separate Compilation.
    Modules may be compiled separately, providing good management for large programsr and definition modules allow for specifying interfaces without giving implementation details.
    Flexible Datatypes.
    Strong datatypes are enforced, but this can be relaxed when necessary in systems programming to just declaring a parameter to be a word, an address, or an array of words.
    Machine Access.
    Access to specific memory addresses and other characteristics of the underlying machine is supported.
    Flexible and efficient tasking is provided by coroutine management routines.
          in SIGPLAN Notices 17(08) August 1982 view details
  • Gries, D. and J. Prins (1985). "A new notion of encapsulation." view details Abstract: Generally speaking, a `module' is used as an `encapsulation mechanism' to tie together a set of declarations of variables and operations upon them. Although there is no standard way to instantiate or use a module, the general idea is that a module describes the implementation of all the values of a given type. We believe that this is too inflexible to provide enough control: one should be able to use different implementations (given by different modules) for variables (and values) of the same type. When incorporated properly into the notation, this finer grain of control allows one to program at a high level of abstraction and then to indicate how various pieces of the program should be implemented. It provides simple, effective access to earlier-written modules, so that they are usable in a more flexible manner than is possible in current notations. Existing languages such as SETL, Smalltalk, ML, CLU, and Ada already provide some of the capabilities listed above, but our new notion may provide more flexibility and ease of use. The paper is organized as follows. Section 2 gives some basic ground rules for our programming notation and outlines our idea for encapsulation. Section 3 discusses some of the issues involved. Section 4 outlines proofs of correctness. Section 5 discusses a `real' example in detail. This is a report of ongoing work, and not a finished product.     
          in SIGPLAN Notices 20(07) July 1985 (Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments) view details
  • Liskov, Barbara and Guttag, John "Abstraction and Specification in Program Development", McGraw-Hill, 1986. view details
          in SIGPLAN Notices 20(07) July 1985 (Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments) view details
  • LIskov Barbara "The History of CLU" view details ps Abstract: The idea of a data abstraction has had a significant impact on the development of programming languages and on programming methodology. CLU was the first implemented programming language to provide direct linguistic support for data abstraction. This paper provides a history of data abstraction and CLU. CLU contains a number of other interesting and influential features, including its exception handling mechanism, its iterators, and its parameterized types.
    Extract: Introduction
    1. Introduction

    The idea of a data abstraction arose from work on programming methodology. It has had a significant impact on the way modern software systems are designed and organized and on the features that are  provided in modern programming languages. In the early and mid l970's, it led to the development of new  programming languages, most notably CLU and Alphard. These language designs were undertaken to  flesh out the idea and to provide direct support for new techniques for developing software.  This paper provides a history of CLU and data abstraction. CLU provides linguistic support for data  abstraction; it was the first implemented language to do so. In addition, it contains a number of other  interesting and influential features, including its exception handling mechanism, its iterators, and its  parameterized types.

    The paper is organized as follows. Section 2 describes the work that led to the concept of data abstraction and how this concept came into existence. It also describes the beginning of the work on  CLU, and discusses some of the later work on programming methodology that was based on data  abstraction. Section 3 provides a history of the CLU development process, with emphasis on the design  issues related to the technical features of CLU; the section contains material about related work in other  languages as well. The paper concludes with an evaluation of CLU and a discussion of its influence on  programming languages and methodology.
    Extract: Data Abstraction
    2. Data Abstraction

    In my early work on data abstraction, in the latter part of 1972 through the summer of l973 , I was concerned with figuring out what the concept was, rather than designing a full programming language.  This section traces the development of the concept and describes the environment in which the work  occurred and the related work that was going on at that time.

    A data abstraction, or abstract data type, is a set of objects and operations. Programs that access the objects can do so only by calling the operations, which provide means to observe an object's state and to  modify it. The objects contain within them a storage representation that is used to store their state, but  this representation is encapsulated: it is not visible to programs that use the data abstraction. For  example, a set of integers type might have operations to create an empty set, to insert and delete  elements from a set, to determine the cardinality of a set, and to determine whether a particular integer is  a member of a set. A set might be represented by an array or a linked list, but since users can interact  with it only by calling operations, the particular representation is not visible. One important benefit of such  encapsulation is that it allows decisions about implementation to be changed without any need to modify  programs that use the data abstraction.

    The idea of a data abstraction developed in the early seventies. It grew out of work on programming methodology. At that time, there was a great deal of interest in methods for improving the efficiency of  the programming process and also the quality of the product. There were two main approaches:  structured programming, and modularity. Structured programming was concerned with  program correctness (or reliability, as it was called in those days):

    The goal of structured programming is to produce program structures which are amenable to proofs of correctness. The proof of a structured program is broken down into proofs of the correctness of each of the  components. Before a component is coded, a specification exists explaining its input and output and the  function which it is supposed to perform.

    Not using gotos was a part of structured programming because the resulting program structures were easier to reason about, but the idea of reasoning about the program at one level using  specifications of lower level components was much more fundamental. The notion of stepwise refinement  as an approach to constructing programs was also a part of this movement.

    The work on modularity was concerned with what program components should be like. For example, I proposed the idea of partitions: The system is divided into a hierarchy of partitions, where each partition represents one level of abstraction,  and consists of one or more functions which share common resources. . . . The connections in data  between partitions are limited to the explicit arguments passed from the functions of one partition to the  (external) functions of another partition. Implicit interaction on common data may only occur among  functions within a partition.

    This notion of partitions was based on Dijkstra's ideas about levels of abstraction and my own work on the Venus operating system. Venus was organized as a collection of  partitions, each with externally accessible functions and hidden state information, which communicated by  calling one another's functions.

          in [ACM SIGPLAN] SIGPLAN Notices 28(03) March 1993 The second ACM SIGPLAN conference on History of programming languages (HOPL II) view details
  • Library of Congress Subject Headings C24 view details
          in [ACM SIGPLAN] SIGPLAN Notices 28(03) March 1993 The second ACM SIGPLAN conference on History of programming languages (HOPL II) view details