This paper presents an overview of the programming language Modula-3, and a more detailed description of its type system.

The “Whiteboards” system is intended to be an electronic equivalent of the whiteboards and corkboards that we have in our offices. A Whiteboard database has similar qualities of storing disparate collections of data and saving their spatial location in a window to help with organization. A Whiteboard database can contain references to arbitrary entities: text files, notes, programs, tools, pictures, etc. Whiteboards runs as an application in the Cedar programming environment developed at the Xerox Palo Alto Research Center.

An important goal of programming language research is to isolate the fundamenal concepts of languages, those basic ideas that allow us to understand the relationships among various language features. This paper examines one of these underlying notions, that of data type , with particular attention to the treatment of generic or polymorphic procedures and static type-checking.

One of the fundamental notions of programming, and thus of programming languages, is the variable. Recently, the variable has come under attack. The proponents of "functional programming" have argued that variables are at the root of all our problems in programming. They claim that we must rid our languages of all manifestations of the "vonNeumann bottleneck" and learn to live in the changeless world of functional combinators.While we may not, believe all the claims of the functional programming advocates, there is evidence that the treatment of variables in most programming languages leaves much to be desired. In this paper we discuss how to make variables "abstract", i.e., how to introduce the notion of variable in to a language so that variables have reasonable mathematical properties. This paper includes:--- a discussion of language design principles that allow a more mathematical treatment of variables in programming language, and--- a description of an equational logic for the programming language Russell [Boehm80]. Although this logic follows much of the development of abstract data types (cf. [Guttag78]), it is novel in its treatment of a language in which expressions not only produce values but also can have effects. We discuss the over all structure of the logic and present in detail the rules particularly relevant to the semantics of variables. A complete presentation of the logic appears in [Demers82], and the rule numbers in this paper agree with the numbers used there.In the next section, we discuss the underlying language principles needed to make an equational specification of variables possible. In the sections that follow, we present a logic that does so for Russell.

In statically typed programming languages, each variable and expression in a program is assigned a unique "type" and the program is checked to ensure that the arguments in each application are "type-compatible" with the corresponding parameters. The rules by which this "type-checking" is performed must be carefully considered for modern languages that allow the programmer to define his own data types and allow parameterized types or types as parameters. (Such languages include Alphard [Wulf78], CLU [Liskov77], Euclid [Lampson77] and Russell [Demers79].) These features increase the expressive power of the languages, but also increase the difficulty of type-checking them.In this paper, we describe a treatment of type-checking that makes it possible to do completely static checking with a general parameterization mechanism allowing parameterized types, types as parameters, and even a disciplined form of self-application. Our method defines a calculus of "signatures," where signatures are similar to the "program types" of [Reynolds78]. Each identifier and expression is given a signature, and applications are type-correct when argument and parameter signatures are equivalent under a simple set of signature transformation rules. Below we present the signature calculus of Russell; we also present a semantic justification of this calculus and specify the language constraints necessary for us to justify our purely static approach to type-checking.

In his recent Turing Lecture, John Backus delivered a trenchant argument for the proposition that "programming languages are in trouble." Backus claims this to be inevitable: the development of Algol-like languages must lead to this sorry state because it begins from faulty assumptions.A less radical interpretation of the difficulties of language design is that we still do not understand the fundamental principles that should guide our design efforts; the machines we use may limit our results, but our ignorance has far greater effect. As evidence to support this position, we can cite the difficulties of building successors to Algol 60 and Pascal. Both languages have been acclaimed as well-designed, but it has proved extremely difficult to capture just what they "got right." Thus, Hoare has claimed that "Algol 60 was not only a great improvement on its predecessors, but also on nearly all of its successors." [73a] The recent Ada design suggests that the same fate may befall Pascal.In this paper, we expand on an idea of Landin [66] to develop an important principle of programming languages: type-completeness. We argue that application of this principle is an effective tool in understanding problems of programming language design. In particular, type-completeness1. allows us to point out many of the flaws and inconsistencies in existing languages (so we can know what mistakes not to repeat) and2. provides a framework for the design of languages (or language families) that have wide variation in their changeable parts.Below, we present the principle of type-completeness and its ramifications for language design. We then discuss some common examples of incompleteness found in existing Algol-like languages. And we end by presenting the type structure of the type-complete programming language Russell, which has been designed by the authors. As we show, the flexibility provided in Russell by the combination of a small, rich type structure and type-completeness belie Backus's assertion of inherent weakness of vonNeumann languages.

This paper considers the general problem of specifying the meaning of programming languages that include “data type definition facilities.” The fundamental question posed in attempting to define such languages is: “what meaning should be given to a data type definition,” or more simply, “what does data type mean?” In this paper we describe a new approach to defining the meaning of data types, treating data types as values, and give its application to the definition of a typed lambda calculus extension. We also prove a theorem stating that our lambda calculus definition is “strongly typed.”

We describe a means of presenting hierarchically organized formal definitions of programming languages using the denotational approach of D. Scott and C. Strachey. As an example of our approach, we give the semantics of PL/CS, an instructional variant of PL/I. We also discuss the implications of this approach to language design, pointing out some cases where the wrong choices may cause the hierarchy to collapse into chaotic rubble.

This paper describes a novel approach to the treatment of data types in programming languages, which allows a simple interpretation of "polymorphic" or "generic" procedures, makes a simple set of type-checking rules semantically justifiable and provides a straightforward treatment of encapsulation.