RUSSELL(ID:527/rus004)

(named for the British mathematician Bertrand Russell (1872- 1970))

Boehm, Demers & Donahue. Cornell Univ and Rice Univ

A compact, polymorphically typed functional language, with bignums and continuations. Types are themselves first-class values and may be passed as arguments.

Structures:
Related languages
ML => RUSSELL   Extension of
RUSSELL => Lucinda   Influence
RUSSELL => Persimmon   Influence
RUSSELL => Poly   partially based on
RUSSELL => Xfun   Influence
References:
  • Boehm, H.; Demers, A.; Donahue, J. "An Informal Description of Russell", Technical Report, Computer Science Dept, TR 80-430, Cornell Univ. 1980. view details Extract: Russell
    Our intent is to provide a highly informal, but hopefully comprehensible, description of the language Russell.  No attempt is made to provide a complete definition of the language; it is assumed that the on-line "rhelp" facility [Boe 85] is available for this purpose.

    This description is aimed primarily at a reader who is about to start using the language.

    It includes discussion of both fundamental concepts and relatively superficial (but nonetheless important) syntactic issues. The reader who is interested only in conceptual issues might prefer to read [Don 85].

    Russell is a very compact expression language which is nevertheless extremely general and uniform in its treatment of functions and, more importantly, data types.

    By the term "expression language" we mean that there is no distinction between expressions and statements.  Any executable construct in the language returns a value.  In particular assignment "statements" and conditionals return values, which may or may not be used.  By the same token,  most constructs in the language can also potentially modify the value of some variable, and thus play the role of statements.
  • Harland, David M. "Polymorphic Programming Languages", Ellis Horwood 1984. view details
  • Hook, J.G. "Understanding Russell: A First Attempt" view details
          in Kahn, G. D. B. MacQueen & G. Plotkin, Eds. "Semantics of Data Types", LNCS 173, Springer 1984 view details
  • Boehm, H.; Demers, A. J. and Donahue, J. E. "A Programmer's Introduction to Russell", Technical Report 85-16, Department of Computer Science, Rice University 1985 view details
          in Kahn, G. D. B. MacQueen & G. Plotkin, Eds. "Semantics of Data Types", LNCS 173, Springer 1984 view details
  • Boehm, Hans-J. "Partial Polymorphic Type Inference is Undecidable", Proceedings of the 8th Annual IEEE Symposium on Foundations of Computer Science, Oct. 1985, pp. 339-345. view details
          in Kahn, G. D. B. MacQueen & G. Plotkin, Eds. "Semantics of Data Types", LNCS 173, Springer 1984 view details
  • Donahue, James; Demers, Alan "Data types are values" view details
          in ACM Transactions on Programming Languages and Systems 7(3) July 1985 view details
  • Harland, David M.; Szyplewski, Martyn W. ; Wainwright, John B. "An alternative view of polymorphism" pp23-35 view details Abstract: We shall outline the traditional approaches to polymorphism, in the light of Strachey's original work, and languages in the style of RUSSELL, and review the implications for programming language design of the developing interest amongst theoreticians in this subject.It will be shown that the "parametric type-polymorphism" favoured by the majority of today's designers, is actually a very limited form of polymorphism, and we shall show how a much more general concept of polymorphism can be constructed by placing arbitrary constraints on abstract storage types.We will then investigate ways of employing these "guarded cells", outlining several possible applications.The essence of our proposal is that in any language in which there is an unfettered abstraction mechanism, and a sufficiently rich universe of discourse, including types which are properly manipulable values, many forms of polymorphism can be built as abstractions, and so need not be built directly into the fabric of that language. We interpret this to mean that polymorphism is not a major factor in programming language design, whereas we take the view that achieving maximum expressivity is crucial to a design.We shall conclude by relating our work to that of theoreticians in the field, and showing the implications of our proposal for program verification. DOI
          in SIGPLAN Notices 20(10) October 1985 view details
  • Boehm, Hans-Juergen; Demers, Alan; "Implementing RUSSELL" pp186-195 view details Abstract: We have completed an implementation of the Russell programming language. This effort has been very helpful in the evaluation of the original language design. It has also served to pinpoint the difficulties in implementing languages with type systems as general as that of Russell.Russell treats both functions and types as data objects which can be freely manipulated by the program. Most operators present in conventional programming languages are viewed as function calls. In spite of this, our compiler produces surprisingly efficient machine code, even with minimal effort invested in the code generator.The generality of the language served to simplify some aspects of the compiler. We focus on the separate compilation mechanism.The most difficult implementation problem is that of inferring typing information omitted by the programmer. We argue that this is an essential part of type checking a language such as Russell. Our current solution is only partially satisfactory.
    DOI Extract: Introduction
    Introduction
    Russell is a language in which both functions and types are first-class objects, which may be manipulated by programs. It nonetheless allows compile-time type checking. The ability to freely manipulate function objects allows some approaches to programming not normally possible in Algol-like programming languages. For example, it becomes possible to employ a programming style very similar to that advocated by Backus.
    By treating types as run-time objects, Russell allows normal function definitions to take the place of, for example, Ada generics. This allows the language itself to be very small, and still to provide facilities for easily writing general purpose, reusable software. It further leads to some increased generality. For example, it is possible to write a ?generic? procedure that is parameterized with respect to another "generic" procedure. There have been few implementations of languages comparable to Russell. ML shares some, but by no means all, of the relevant characteristics of the language. Some Lisp systems provide similar flexibility, but not the ability to do static type checking. The Scratchpad II language is similar, but current implementations have pursued different goals. Poly is a simpler and more restrictive a language, partially based on Russell.
    We have completed an implementation of Russell on a VAX under UNIX. This effort was started largely to experiment with Russell as a programming tool. So far, it has been very successful at pointing out a number of (subsequently remedied) language design flaws. It has also given us some insight into the difficulties of implementing such a language. In particular, it has demonstrated that
    1. The major difficulty in implementing Russell lies in inferring type information omitted by the programmer. As we will discuss below, such type inference is essential in making Russell a usable language.
    2. Generating code of reasonable quality is easier than might be expected. In particular, type information is frequently useful. When additional information, such as in-line code for function calls, is needed by the code generator, it can often be associated with the type information and propagated by the type inference algorithm. Thus the ?typing? information attached to an expression by the compiler consists both of information needed to do type checking and of optimization information.
    3. The generality of the language design occasionally simplifies otherwise herd problems. A surprisingly flexible and elegant separate compilation facility was added as an afterthought.
    Extract: An Overview of the Language
    An Overview of the Language
    Russell is a very compact expression language which is nevertheless extremely general and uniform in its treatment of functions and, more importantly, data types. By the term "expression language" we mean that there is no distinction between expressions and statements. Any executable construct in the language returns a value. It may also modify the state of the computation. The following are some of the other important characteristics of the language. The concepts involved are discussed more fully in [Dem 791, [Dem 8Oa], [Dem 8Ob], and [Don 851.

    1. The philosophy underlying Russell data types is that all objects manipulated by a Russell program are elements of one universal domain or set. We may, if we wish, think of this set as being the set of all bit sequences. Thus we can identify an integer with its binary representation, a character string with a sequence bits representing the ASCII codes for the characters, and a function with a sequence of bits representing the code to be executed to evaluate the function, possibly followed by another sequence of bits describing the environment in which the code is to be executed. An object itself gives us no information about how to interpret it. The same bit string could represent either a character string or a function mapping integers to integers. (For a much more abstract view of such a domain see e.g. [Sto 771.) What distinguishes one data type from another then is not the set of its elements, but rather the set of operations (or functions) that may be applied to interpret elements of the universal set. In fact, the Russell view is that a data type is just that collection of operations. Thus the integer type is just the collection of functions +, -, *, /, _.. What makes a value an integer is not any characteristic of the value itself, but the fact that it is intended to be interpreted by exactly these functions.
    2. The Language design permits static (i.e. compile time) type checking (signature checking in Russell terminology). This check is enough to guarantee that the result of a subexpression will not be misused by imposing a different interpretation on it. For example, assume we represent integers using their binary representations, and we represent the boolean constants "true" and "false" by the bit strings "1" and "0" respectively. It would be perfectly possible to evaluate the expression
      3 * false
      by misinterpreting the result of the subexpression "false" as representing the integer 0. The Russell type system insures that only "Boolean" operations may be applied to false. Thus an expression like the preceding one is illegal.
      Information about legitimate uses of expressions is captured in the idea of a signature, or syntactic type, associated with each expression in the language.
      Each expression in the language has such a signature associated with it. For example, the signature of
      "3 * 5" is
      val Integer
      telling us that its result is a value intended to be interpreted by the operations that make up the type "Integer". This signature is determined using the rules of a formal, but very simple, signature calculus. Certain rules of this calculus, referred to as matching rules, specify exactly when subexpressions may be combined in what ways. Other rules specify how the signature of the composite expression "3 * 5" is determined from the signatures of the subexpressions "3", "5", and "*".
    3. Many programming languages allow users to treat functions as data objects in at least some contexts, e.g. as parameters, Since Russell data types are just collections of functions, they can similarly be treated as data objects. Furthermore, since both functions and data types are part of the same universal data domain as other objects, this can be done uniformly in all contexts.
    4. Variables in Russell are data objects. Variables differ from other data primarily in that they identify locations where values can be stored. The ?ValueOf? and ?:=I operations, included in most built in types, can be applied to a variable to obtain and change the value stored at the location.
    5. Russell has a completely uniform declaration mechanism. The declaration
      let x == e, in e2 ni
      simply binds the identifier x to the value of the expression e, inside the expressions e, and e,. New variables are obtained by binding an identifier to the result obtained by calling an allocation function.
      6. Any legal expression can be the body of a function and any identifier that appears inside it may be made a parameter of the function. Thus there are no constraints imposed on the argument and result signatures for functions.


    Extract: Type Inference
    Type Inference
    Recall that Russell associates a signature, with each expression in the language, in order to allow compile-time  type checking. The problem of inferring incompletely  specified signatures is the most novel and difficult aspect of  Russell implementation.
    [Boe 80) gives precise rules for inferring the signature of an expression from the signatures of the subexpressions.  These rules yield a directly applicable algorithm for finding  the signatures of the expressions in a Russell program, as  well as a concise definition of signature-correctness, provided the programmer explicitly specifies the signatures of  all identifiers and functions (and explicitly resolves any  operator overloading). Unfortunately, requiring such explicit specification would make the language too cumbersome  to use. In practice it is essential to allow the omission of  several kinds of information. Some of these are illustrated  here:

    1. Types of declared identifiers are usually apparent from context. We would much prefer to write
      let x == 3 in ...
      rather than
      let x: val Integer == 3 in ...
    2. Result signatures of functions are frequently redundant, as in Pascal. Consider the following function
      which, given an argument f, computes another function, a rough numerical approximation to the derivative of f.
      func [f: func[val Float] val Float ]
      func(val Float] val Float {
      func [x: val Float] val Float {
      (f[x + O.ouOl] -f[x])/0.0001
      }
      }
      It should certainly be possible to omit at least the result signature of the main function.
      Worse problems may arise with functions returning complicated structured objects. This is not serious  in Pascal because functions can return only simple  objects.
    3. Type arguments to functions are frequently redundant, and can make programs hard to read. In  Russell one can declare a function that returns the  composition of two (unary) functions as follows:
      let
      compose ==
      func[f: func(val tZ]val t3;
      g: func[val tl]val t2;
      tl,t2,t3: type{}] (
      func[x: val tl]val t3 { f[g[x]] }
      }in ...
      The three type parameters tl, t2, and t3 are introduced so that "compose" may be applied to functions with any parameter and result types.
      If we assume that "succ" is the successor function on integers, we can define a function that adds 2 to an  integer as
      compose[succ, succ, Integer, Integer, Integer]
      Clearly the type arguments are redundant. In this case, as in the example of figure 1, they can be  inferred easily from the signatures of the first two  arguments

            in SIGPLAN Notices 21(07) July 1986 view details
    4. Boehm, H.-J. "Type inference in the presence of type abstraction" pp192-206 view details Abstract: A number of recent programming language designs incorporate a type checking system based on the Girard-Reynolds polymorphic lambda-calculus. This allows the construction of general purpose, reusable software without sacrificing compile-time type checking. A major factor constraining the implementation of these languages is the difficulty of automatically inferring the lengthy type information that is otherwise required if full use is made of these languages. There is no known algorithm to solve any natural and fully general formulation of this ?type inference? problem. One very reasonable formulation of the problem is known to be undecidable. Here we define a restricted version of the type inference problem and present an efficient algorithm for its solution. We argue that the restriction is sufficiently weak to be unobtrusive in practice.



      DOI
            in SIGPLAN Notices 24(07) July 1989 includes Proceedings of the SIGPLAN '87 symposium on Interpreters and interpretive techniques view details
      Resources
      • repository

        "