





           A Programmer’s Introduction to Russell

           H. Boehm A. Demers J. Donahue

























































           Our intent is to provide a highly informal, but hopefully compre‐
           hensible, description of the language  Russell.   No  attempt  is
           made  to provide a complete definition of the language; it is as‐
           sumed that the on‐line ‘‘rhelp’’ facility [Boe 85]  is  available
           for this purpose.  This description is aimed primarily at a read‐
           er who is about to start using the language.  It includes discus‐
           sion of both fundamental concepts and relatively superficial (but
           nonetheless important) syntactic issues.  The reader who  is  in‐
           terested only in conceptual issues might prefer to read [Don 85].
           Russell is a very compact expression language which is  neverthe‐
           less  extremely general and uniform in its treatment of functions
           and, more importantly, data types.  By the term ‘expression  lan‐
           guage’  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.
           We’ll start with a very simple example which will serve to illus‐
           trate a few of the points which follow.  In keeping  with  tradi‐
           tion,  we  will  use  a  declaration of the factorial function: 1
           fact == 2       func [ n : val Short ] val Short 3           {  4
           if  5                      n  >  0  ==>  n  *  fact[  n  ‐  1 ] 6
           #         n = 0 ==> 1 7               fi  8            }  Russell
           has  a  completely  uniform declaration mechanism.  An identifier
           ‘‘a’’ can be bound to a simple value, a function, a  type,  or  a
           variable,  with  a  declaration of the form ‘‘a == b’’.  This has
           the effect of binding the identifier a to the value  produced  by
           the expression b.  We could use b == 0 to declare b to be equiva‐
           lent to the integer constant 0.   (This  is  completely  distinct
           from declaring an integer variable.  The identifier b is purely a
           value.  It does not make sense to assign to it. ) In  this  case,
           the  expression appearing in the declaration is an explicit func‐
           tion construction (abstraction).   Its  value  is  the  factorial
           function  whose  body  consists of lines 4‐7.  The heading of the
           function construction (line 2) indicates it is ‘‘a function  map‐
           ping  a  single short (16 bits in the Vax implementation, 32 bits
           in the Sun implementation) integer value n  to  a  short  integer
           value’’.   If  we had wanted a factorial function that could pro‐
           duce arbitrarily large results without overflowing,  the  heading
           should have been: 2       func [ n : val Long ] val Long The body
           of the ‘‘fact’’ function is an expression whose value will be re‐
           turned as the value of a function call.  In this case the expres‐
           sion produces a simple integer value.  In general, the body of  a
           function may be any expression; it could just as well produce an‐
           other function or a type.  Similarly it might accept  a  function
           or type argument.  Here the body consists of a conditional.  Here
           we used a slightly extended version of Dijkstra’s guarded command
           notation [Dij 76].  (More conventional, Algol‐like syntax is also
           allowed.)  Since Russell is an expression language,  conditionals
           return  a value.  In this latter respect Russell conditionals re‐
           semble  Algol  conditional  expressions.   The  conditional  here
           should  be  interpreted  as follows:  If the first guard is true,
           i.e. n is greater than 0, then the value returned is the value of
           the  expression n*fact[n‐1].  Note that arguments to function ap‐
           plications (calls) are enclosed in square  brackets  rather  than
           parentheses.  Function application syntax is actually quite flex‐
           ible.  Brackets may frequently be omitted.  This is discussed be‐
           low.  If the second guard is true then the integer 1 is returned.
           If neither guard is true a run‐time error occurs.  If two or more
           guards of some conditional are all true, then any one of the cor‐
           responding expressions may be chosen to be  evaluated.   Assuming
           n ≥ 0, the conditional could also have been written as: if
                 n > 0 ==> n * fact[ n ‐ 1 ] #     else  ==> 1 fi or as if n
           > 0 then
                 n * fact[ n ‐ 1 ] else
                 1 fi So far, we have not introduced any  variables  or  as‐
           signments.   The identifier n denotes a fixed value, which cannot
           be changed.  In order to look at variables, we first have to  ex‐
           amine  the notion of ‘‘type’’.  Russell was designed to explore a
           particular view of data types.  Traditional programming  language
           designs  typically  fall  into  one of two categories.  Languages
           like LISP impose essentially no type  structure  which  could  be
           checked  by  a  compiler; a typical LISP compiler would allow any
           argument to be passed to any function  or  operator.   (Executing
           the  function  call  may  of  course result in a run‐time error.)
           This allows a great deal of flexibility, but many trivial  errors
           are  likely  to go undetected, at least until that section of the
           program is actually executed.  It also makes  the  compilers  job
           much  more difficult, since it cannot necessarily tell in advance
           whether a ‘‘+’’ should be compiled to, say, an integer or  float‐
           ing  point  add  instruction.   Languages like Pascal solve these
           problems by imposing a very rigid type structure.  A Pascal  com‐
           piler  would  object  to an expression such as 3 * False Unfortu‐
           nately this results in a loss of generality.  Such languages make
           it  particularly  difficult  to  write  general purpose, reusable
           software.  It does not suffice to write one implementation of bi‐
           nary search trees; a different one must be provided for each kind
           of data to be stored in the leaves.  This can usually be  avoided
           by  defeating  the  type  structure.   This,  at least partially,
           negates the purpose of having the type  structure  in  the  first
           place.   A  number of more recent language designs try to combine
           the flexibility of dynamically typed  languages,  such  as  LISP,
           with  the  reliability and efficiency resulting from compile‐time
           type checking.  Russell is  one  such  ‘‘polymorphically  typed’’
           language.   The  fundamental  view underlying Russell is that all
           objects manipulated by a Russell program are in fact 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 of 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  fol‐
           lowed  by  another sequence of bits describing the environment in
           which the code is to be executed.  Thus the 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, for example, [Sto 77].)  What distinguishes one  data
           type  from another 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, a data type is just that
           collection of operations.  Thus the Boolean type is just the col‐
           lection  of  functions and, or, not, ... .  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 func‐
           tions.  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 again part of the same  univer‐
           sal  data  domain as other objects, this can be done uniformly in
           all contexts.  Compile‐time ‘‘type checking’’ is performed by as‐
           sociating  a  syntactic type, or signature with each expression.
           Such a signature specifies in which contexts  an  expression  may
           appear.   Signature checking (type checking translated to Russell
           terminology) insures that an expression does not appear in a con‐
           text  in  which it is not meaningful.  Thus the value produced by
           an expression cannot be misinterpreted.  For example,  assume  we
           are  representing  integers  using  their  binary representation.
           Furthermore we  represent  the  Boolean  constants  ‘‘True’’  and
           ‘‘False’’  as the bit strings ‘‘1’’ and ‘‘0’’ respectively.  Sig‐
           nature checking in Russell will prevent us from writing  the  ex‐
           pression  3 * False in spite of the fact that it produces a well‐
           defined answer.  Clearly the 0 value produced by  the  expression
           ‘‘False’’ is intended to be used in a ‘‘Boolean’’ context, and is
           not intended to be treated as an integer.  This is  reflected  by
           assigning  the expression ‘‘False’’ the signature ‘‘val Boolean’’
           (‘‘Boolean’’ value).  The signature of ‘‘*’’ is func [val  Short;
           val  Short]  val  Short  Actually  there are several instances of
           ‘‘*’’ with different signatures.  Each of the types Short,  Long,
           and  Float  has  a separate ‘‘*’’ operation.  They provide 16‐bit
           integer, unlimited size integer, and floating  point  multiplica‐
           tion,  respectively.  This indicates, among other things, that it
           is a function whose arguments must have signatures ‘‘val Short’’,
           and  thus  must be interpretable as short (i.e. 16 bit) integers.
           Since the parameter signature for ‘‘*’’ (‘‘val Short’’) does  not
           match   the   signature   of   the   second  argument  expression
           (‘‘val Boolean’’), the above expression will be rejected  by  the
           compiler.   It  is important to distinguish signatures, which are
           associated with expressions, and are  purely  syntactic  objects,
           from  types,  which are collections of functions.  ‘‘Short’’ is a
           built‐in type, which contains operations such as  ‘‘*’’.   It  is
           convenient to use the same identifier (or expression, in general)
           inside signatures, to indicate appropriate uses of an expression.
           It  is  much easier to write applicative (variable‐free) programs
           in Russell than in most conventional languages.   Our  experience
           indicates  that  small  Russell programs tend to naturally be ap‐
           plicative.  Nonetheless, it is easy to introduce variables if one
           prefers.   We  illustrate this by rewriting the ‘‘fact’’ function
           so that it uses a loop rather than recursion. (Clearly loops  are
           not  useful  without  variables.)   Variables, like functions and
           types, are themselves data objects.   They  identify  a  location
           where other values can be stored.  A short integer variable N can
           be declared by means of a declaration such as N ==  Short$New[  ]
           The  type Short is, like all Russell types, nothing but a collec‐
           tion of functions.  One of these functions is New.  It  allocates
           a  new  integer  variable  and returns it.  Thus its signature is
           func [ ] var Short The $‐symbol is used to indicate  a  selection
           from a type.  ‘‘Short$New’’ explicitly specifies the New function
           from the type Short, and ‘‘Short$New[ ]’’ is an expression  which
           returns  a  new  integer variable.  ‘‘N’’ is then simply bound to
           the the result of this expression.  The loop  construct  has  the
           same syntax as the conditional, except that ‘if’ and ‘fi’ are re‐
           placed by ‘do’ and ‘od’ respectively.  (See [Dij 76].)  It  indi‐
           cates  that while one of the guards is true the corresponding ex‐
           pression should be executed.  A loop always returns  the  special
           value  ‘‘Null’’.  An imperative version of the factorial function
           can be written as: fact ==
               func [ n : val Short ] val Short
                   {
                       let
                           N == Short$New[ ];
                           F == Short$New[ ]
                       in
                           N := 2;  F := 1;
                           do N <= n ==>
                               F := F * N;
                               N := N + 1
                           od;
                           F
                       ni
                   } A block can be used anywhere an  expression  is  legal.
           Its  general  syntax  is  let  <declarations> in <expressions> ni
           where both declarations and expressions are  separated  by  semi‐
           colons.   The value of the block is the value of the last expres‐
           sion.  Thus the value returned by the block in the example is the
           final  value of the variable F.  As before this becomes the value
           returned by the function.  There is no separate notion of  ‘‘pro‐
           cedure’’  in  Russell.  Functions may may modify variable parame‐
           ters.  The assignment operator ‘‘:=’’ is an  example  of  such  a
           function.  It expects two arguments, a variable on the left and a
           value on the right.  Both preceding examples  have  been  written
           using  syntax  similar  to  that  of other programming languages.
           This is usually the case for  real  Russell  programs.   Formally
           this syntax is only an abbreviation.  ‘‘Full Russell’’ syntax re‐
           flects the concepts underlying the language  much  more  clearly,
           but  is usually unpleasant to write.  It is useful to look at the
           full language, both to simplify explanations, and  to  understand
           the   generality   of  the  language.   Consider  the  assignment
           ‘‘N := N + 1’’ in the preceding example.   We  stated  previously
           that  operations  on  ‘‘Short’’ values are components of the type
           ‘‘Short’’.  Thus the operation ‘‘+’’ does not exist by itself; it
           is  one  element  in  the ‘‘Short’’ collection of operations.  In
           full Russell, ‘‘+’’ would need to  be  replaced  by  ‘‘Short$+’’.
           Similarly, ‘‘:=’’ is an operation provided by many types, includ‐
           ing ‘‘Short’’.  The instance provided by ‘‘Short’’ has  signature
           func  [var Short, val Short] val Short indicating that it expects
           a location as its left argument, a value as its  right  argument,
           and  returns  a  value  (namely that of its right argument).  The
           value returned by the operation is discarded in this case.  As in
           other programming languages, the two occurrences of ‘‘N’’ actual‐
           ly have different meanings.  The occurrence on the left side  de‐
           notes a variable, or location, at which the value produced by the
           right side is to be stored.  The  right  side  occurrence  simply
           produces  a  value.   As  declared,  ‘‘N’’  has  signature  ‘‘var
           Short’’, which is appropriate for the left side.   On  the  right
           side  it  appears  as an argument to ‘‘Short$+’’, which expects a
           ‘‘val Short’’ subexpression.  To get from one to  the  other,  we
           have  to  go  from  the location ‘‘N’’ to the value stored there.
           This is done by calling the  ‘‘V’’  operation  provided  by  most
           types.   In particular, ‘‘Short$V’’ has signature func[var Short]
           val Short A more complete version of the assignment  would  be  N
           Short$:=  Short$V[N]  Short$+  Short$1 We have still used conven‐
           tional infix notation for ‘‘:=’’ and ‘‘+’’.  These are just func‐
           tion calls Thus a real purist could write the assignment in fully
           expanded Russell as Short$:=[N, Short$+[Short$V[N], Short$’1’[]]]
           and have it be correctly recognized by the compiler.  (The inter‐
           pretation of Short$1 is discussed in a later section.)   Appendix
           2  contains  a short summary of the differences between full Rus‐
           sell, and the abbreviated version which is  normally  used.   Now
           that  we  have hopefully conveyed some rough feeling for the lan‐
           guage, we finally start over at the beginning.  A Russell program
           consists  of  a  sequence of identifiers, keywords, strings, com‐
           ments, and punctuation characters.  Upper versus lower case  dis‐
           tinctions  are  significant  in  all contexts.  An identifier may
           have one of three forms: It may consist of any letter followed by
           some number of letters and digits. "_" is considered to be a let‐
           ter.  Any sequence of characters enclosed in single  quotes  con‐
           stitute  an identifier.  These identifiers are most commonly used
           for constants, as will be  described  in  the  next  section.   A
           ’‐symbol can be included in such an identifier by doubling it, or
           preceding it by a ‘‘\’’ character.   Any  sequence  of  ‘operator
           characters’.   These are: ! %  &  * + ‐ . / : < = > ? @ \ ^ ‘ | ~
           By convention these are used as function names.  Some of the  se‐
           quences formed using (1) and (3) are actually reserved for use as
           keywords and may not be used for other purposes.  Note that  none
           of   these   include   upper   case  letters.   These  are:  Key‐
           words                              Purpose

           cand, cor                             conditional and, or do, od,
           if,  fi, else, elsif, ==>       conditionals, loops enum, record,
           prod, union, extend     building types export, hide,  with,  con‐
           stants        modifying   types   let,   use,  in,  ni,  ==,  ===
        declarations val,  var,  func,  type,  field,  characters,  readonly
        signatures  extern                                 separate compila‐
           tion <<, >>                                explicit overload res‐
           olution  :                                     parameters, decla‐
           rations The syntax of strings is complementary to that of identi‐
           fiers.   The following are legal strings: Any sequence of charac‐
           ters enclosed in double quotes.  Any sequence of letters and dig‐
           its  starting  with  a  digit.   The  following  are  examples of
           strings:        123                            "123"        2A1FB
           "A1FB" "Hello"                 """" ("" represents a single " in‐
           side the string) "’"                     "\"" (same as """")  The
           sequences  \n,  \r,  and \t may be used to denote line‐feed, car‐
           riage return, and tab characters inside strings and quoted  iden‐
           tifiers.   The  next  section discusses the meaning of strings in
           the language.  Usually they are interpreted as in other  program‐
           ming languages.  In particular 123 will usually represent the in‐
           teger and "Hello" the corresponding character string. The  formal
           definitions  differ  however, both to allow treatment of infinite
           sets of constants within the Russell framework, and to allow  the
           user  the  same mechanism in constructing his own types.  Russell
           comments are delimited by ‘(*’ and ‘*)’.  Comments may be nested.
           Thus  the  following  is legal: (* This is a comment (* This is a
           nested comment *) *) On the other hand, (* (* This is an  improp‐
           erly  constructed  comment  *) is illegal.  As we pointed out be‐
           fore, types in Russell are just collections of  functions.   Thus
           the  only  way  one can talk about particular values is by having
           functions in that type that produce them.  Consider the  built‐in
           type  Boolean.   It  contains  two  functions, named ‘‘True’’ and
           ‘‘False’’,  with signatures (roughly speaking) func [ ] val Bool‐
           ean.  These are functions with no arguments which produce a Bool‐
           ean result.  Thus we can always get the Boolean  value  false  by
           writing  ‘‘Boolean$False[ ]’’ in full Russell, or, more commonly,
           just ‘‘False’’.  This allows us to deal with finite sets of  con‐
           stants  for a given type.  Since we always want to consider types
           as finite sets of operations, we need to extend this idea to han‐
           dle  infinite  sets  of  constants (such as those in the built‐in
           Short type).  This is done by treating strings, in the sense  de‐
           scribed  above,  as abbreviations.  The only Short constants pro‐
           vided explicitly (i.e. in the same way as ‘‘True’’ and  ‘‘False’’
           for  the  Boolean  type) are ’0’ through ’9’.  (The ’‐symbols are
           part of the identifiers.)  Also provided is a concatenation oper‐
           ation  ‘‘^+’’ which, in this case, gives the value of the integer
           obtained by writing an integer next to  another  digit.   Roughly
           what happens then is that the expression 123 is treated as an ab‐
           breviation for: (’1’[ ] ^+ ’2’[ ]) ^+ ’3’[ ] If the concatenation
           operator  were  not already built in, it could be declared as: ^+
           == func[ x, y : val Short ] {
                   let
                       ’10’ == 5 + 5
                   in
                       ’10’ * x + y
                   ni
                 } Note that using ‘‘10’’ instead of ‘‘ ’10’ ’’ would result
           in  infinite recursion.  In the above example we have again omit‐
           ted the selections of the constants ’1’, ’2’, and ’3’, as well as
           the  ‘‘^+’’  operator, from the Short type.  Formally strings are
           always selected  from  a  type.   Thus  we  should  have  written
           ‘‘Short$123’’.   This  selection  would  normally be inferred, so
           that, in practice, writing ‘‘123’’ is  usually  sufficient.   All
           this allows us to define the meaning of (unquoted) strings a lit‐
           tle more  precisely.   In  general  T$a1a2...an  is  expanded  to
           ((...((T$’a1’[  ]   T$^+  T$’a2’[ ])  T$^+  T$’a3’[ ]) ...)  T$^+
           T$’an’[ ]) Quoted strings are treated only slightly  differently.
           Since  we want "" to be legal we have to generalize the treatment
           to handle this in a reasonable way.  We do this by agreeing  that
           ’ ’  (2  single  quotes) will implicitly be concatenated onto the
           left of  any  such  string.   Furthermore,  to  distinguish  such
           strings more explicitly from unquoted ones ^* will be used as the
           concatenation operator.  Thus T$"ab" is expanded to (T$’’[ ] T$^*
           T$’a’[  ])  T$^*  T$’b’[  ]  In  accordance with this scheme, the
           builtin type ChStr (character strings)  has  constants,  that  is
           nil‐ary functions, with names ’’ and ’c’, for all characters c in
           the character set.  It also includes a ^* concatenation function,
           which  unlike  the one for integers, really does character string
           concatenation.  We have gained something  besides  uniformity  in
           this  approach.   It is possible to make use of the string mecha‐
           nism for user defined types.  For example, we can define an  ‘oc‐
           tal  integer’ type by simply modifying the builtin type ‘‘Short’’
           in the following two ways: First the constants ’8’ and  ’9’  have
           to  be deleted.  Secondly ^+ now has to multiply by 8 rather than
           10.  As will be described later Russell allows the user to easily
           construct  such new types.  Russell provides the following primi‐
           tives for building expressions: Selection from a type.  A  compo‐
           nent  function f of a type T may be selected by writing T$f Func‐
           tion constructions (lambda abstraction in lambda calculus  termi‐
           nology).  Any expression E can be turned into a function by writ‐
           ing function_signature { E } The result signature may be  omitted
           if  it  can  be  inferred.  Any identifiers appearing in E can be
           treated as parameters by including them as such in the signature.
           The above declarations of factorial functions are simple examples
           of this.  Function application.  A function f may be  applied  to
           arguments  a1 ... an by writing [a1, ... , aj] f [aj+1, ... , an]
           Which arguments go before the function an which  go  after  is  a
           choice that can be made arbitrarily (though hopefully consistent‐
           ly) by the programmer.  If one of the argument lists is empty  it
           can  always  be  omitted.  (As mentioned above, if both are empty
           they can usually, but not always, both  be  omitted.)   Thus  any
           function can be treated as an infix, prefix, or postfix function.
           (We could introduce more  reasonable  syntax  for  the  factorial
           function  by declaring it as "! == func ... ".)  Blocks.  The use
           of blocks to introduce declarations was illustrated above.   Rus‐
           sell allows two other kinds of blocks.  The block let in <expres‐
           sions> ni can be abbreviated as ( <expressions>  )  .   The  con‐
           struct use <comma_separated_list_of_type_expressions> in <expres‐
           sions> ni tells the compiler that it should use the  types  given
           in  inferring  omitted  selections  in the second list of expres‐
           sions.  Otherwise it is equivalent to ( <expressions> )  .   Note
           that  in inferring such selections the compiler will first try to
           use the types of the arguments and then search surrounding  "use"
           lists  inside  out.  (As it turns out this means that "use" lists
           are primarily useful for implicit selections of constants,  which
           have no arguments.)  Furthermore, in abbreviated Russell, any us‐
           er program is treated as if it were  embedded  in  the  following
           construct: use Float in use ChStr in use Boolean in use Short in
                   user_program  ni  ni  ni  ni Sequence control constructs.
           Loops and conditionals were described above.   (Conditionals  can
           also  be written in a more Pascal‐like if‐then‐else form, not de‐
           scribed here.)  Conditionals can sometimes be abbreviated by  the
           conditional  and/or  constructs: expression1 cand expression2 ex‐
           pression1 cor expression2 Here  all  expressions  return  Boolean
           values.   Function calls in Russell always pass arguments by val‐
           ue, and thus must evaluate the arguments first.  This is not  al‐
           ways  desirable  with  the  Boolean functions ‘‘and’’ and ‘‘or’’.
           The ‘‘cand’’ and ‘‘cor’’ constructs are similar  to  ‘‘and’’  and
           ‘‘or’’, except that they are not call‐by‐value operations.  (This
           is hinted at by the absence of [  ]  around  the  ‘‘arguments’’.)
           The  second ‘‘argument’’ is only evaluated if necessary.  Thus e1
           cand e2 is actually equivalent to if
                 e1   ==> e2 #     else ==> Boolean$False[ ]  fi  Type  con‐
           structions  and  modifications.   These provide ways to build new
           types out of existing ones.  They are  discussed  below.   A  few
           more  remarks on the syntax of applications and selections are in
           order at this point.  First, an expression such as [a]b$c is cur‐
           rently  ambiguous.  The function b could produce a type, and thus
           the expression could be interpreted as  ([a]b)$c.   This  is  re‐
           solved  by  having selections bind more tightly than application.
           Thus the correct interpretation is [a](b$c).  The second  problem
           is  that the above syntax would require us to write the statement
           x := x + 1 as [x] := [[x] + [1]] This would, at best,  be accept‐
           able  only  to  LISP  programmers.  Thus the actual syntax allows
           dropping the brackets for functions used as either binary  infix,
           or  as  unary  prefix operators.  A standard FORTRAN style prece‐
           dence scheme is used to disambiguate the  resulting  expressions.
           It  is worth noting that this scheme relies purely on the identi‐
           fiers appearing in the expression, and not at all on any semantic
           or  signature information.  As previously mentioned, each Russell
           expression has a signature associated with  it.   This  signature
           describes  how the result produced by that expression should, and
           should not, be interpreted.  Russell expressions  always  produce
           objects which are intended to be used as either simple (i.e. non‐
           function, non‐type) values, variables, functions, types, or  sig‐
           natures.   In  order to distinguish between these, there are five
           different kinds of signatures, corresponding to  the  above  five
           categories.   They  are described somewhat informally below.  The
           general form of such a signature is val T where T is  an  expres‐
           sion  denoting  a  type.   Informally it indicates that the value
           produced by the corresponding expression should be interpreted as
           a  value  of type T.  More formally it means only that the result
           produced by the expression should only be interpreted by (that is
           passed  as a parameter to) a function that expects an argument of
           signature val T.  Thus one way of viewing the whole issue is that
           the  expression  T  is just a tag used to match up functions with
           proper arguments.  An alternate view is the following: We want to
           guarantee  that  the first‐class value in question is passed only
           to functions that know how to interpret it.  An obvious way to do
           that  is  to  keep  track, in its signature, of all the functions
           that can be applied to it.  Since usually all these functions are
           components  of  a  type,  we use the expression representing that
           type as a shorthand.  (In fact some functions not in T  may  also
           expect  val  T arguments.  These however are usually built out of
           the ‘‘primitive’’ functions in T.)  As an  example  consider  the
           following  expressions,  where it is assumed that all identifiers
           have the natural meanings:  a)  1  +  2  b)  (BoundedStack[Short,
           10])$push[  S,  3 ] c) (BoundedStack[Short,5+5])$push[ S, 3 ] (a)
           is a simple integer expression.  It has signature ‘‘val  Short’’.
           In  (b)  and  (c) we assume that BoundedStack is a function which
           takes two arguments.  The first is the type of the individual el‐
           ements  to  be  pushed onto the stack.  The second is the maximum
           size of the stack.  Its  result  is  the  corresponding  type  of
           bounded  stacks.   We assume that everything works in an applica‐
           tive fashion, so that the push operation returns a  stack  value.
           The  signature  of  (b)  then  is ‘‘val BoundedStack[Short,10]’’.
           That of (c) is ‘‘val BoundedStack[Short,5+5]’’.  It should be em‐
           phasized  that signatures are purely syntactic objects, which are
           determined using some simple rules described below.  In  particu‐
           lar nothing in the whole signature mechanism knows anything about
           the semantics of ‘‘+’’.  Thus the signatures of (b) and  (c)  are
           completely    distinct,   and   the   functions   in   ‘‘Bounded‐
           Stack[Short,5+5]’’ Cannot be used to interpret objects of  signa‐
           ture  ‘‘val  BoundedStack[Short,10]’’.   This  restriction rarely
           causes any real inconvenience.  (If we want to do  any  syntactic
           ‘‘type checking’’ at all, some such restriction is clearly essen‐
           tial.  Semantic equivalence of Russell  type  expressions  is  in
           general  undecidable.)   Conversely, the above interpretation re‐
           quires that two syntactically identical type  expressions  should
           always  denote the same set of functions.  It does not make sense
           to say that S has signature ‘‘val BoundedStack[Short,x]’’,  where
           x  is  a  variable;  the value of x may change, but certainly the
           collection of functions used to access S should not.  In order to
           insure  that  this property holds, Russell generally enforces the
           following import rule: No expression with function or type signa‐
           ture  may mention a non‐local variable.  (As described below, the
           orecise rule can be somewhat more relaxed.)  It follows from this
           that no expression may depend on (or alter) variables it does not
           explicitly mention.  Thus no function or type  valued  expression
           can  depend  on  the  values of variables.  The general form of a
           variable signature is var T where T  is  a  type  expression,  as
           above.   This  indicates  that  the result of the expression is a
           variable (or location) which can hold an object to be interpreted
           as  by  the functions of type T.  Usually (though not always) the
           only thing that can be done with an object of signature ‘‘var T’’
           is  to  pass it as an argument to ‘‘T$:=’’ or ‘‘T$V’’, or to bind
           an identifier to it.  The most common example of an expression of
           signature  ‘‘var  T’’  (other than a simple variable) is T$New[ ]
           where New is the function in T that  allocates  a  new  variable.
           Another  example  is  A.1 where A is a variable of an appropriate
           array type, and ‘‘.’’ is the name of the subscription operator in
           the (built‐in) array type.  It produces the location of the first
           element of the array.  (Array types usually have two versions  of
           the  ‘‘.’’  operation.   In  addition  to the one mentioned here,
           there would normally be an operation mapping an array  value  and
           an  index into a component value.)  In order to insure that func‐
           tions are passed only appropriate arguments, it is clearly neces‐
           sary  that  their  signature  include the signatures of the argu‐
           ments, as well as the signature of the result.   Function  signa‐
           tures  may  also include the names of the formal parameters.  Al‐
           though these are not important in determining the correctness  of
           a  particular application, there are nevertheless two reasons for
           putting them here.  First the syntax  of  function  constructions
           requires  it.  (There’s  nowhere  else to put them.)  The second,
           more important one, should become apparent when we state the rule
           for  determining the signature of an application.  The syntax for
           function signatures is func[param1; ... ;  paramn]  result_signa‐
           ture  where each parami is a list of parameter names with identi‐
           cal signature, and the signature itself: id1, ... , idm : parame‐
           ter_signature If one of the parami includes only a single parame‐
           ter name which is not otherwise used, then both it  and  the  ‘:’
           can  be  omitted.   A  signature such as func[x,y: val Short] val
           Short is considered to be identical to func[x: val Short; y:  val
           Short]  val Short Function signatures are usually written explic‐
           itly only in function headings.  Even in this  case,  the  result
           signature  may  be  omitted  whenever it can be easily determined
           from the body of the function.  Some examples of function  signa‐
           tures  were  already given above.  More interesting examples will
           be presented below in conjunction with type  signatures.   If  we
           want  to  specify  how a type expression can be used, we need two
           kinds of information.  First, we need to know what operations can
           be  selected  from  it.  Second, we need to know how those opera‐
           tions themselves can be used.  Thus a type signature consists  of
           operation  names,  and  of  the signatures corresponding to those
           names.  The syntax is: type { op1; ... ; opn } The syntax for the
           individual opi is the same as that used for parameters in a func‐
           tion signature (except that no names can be omitted, and all sig‐
           natures have to be either type or function signatures).  The sim‐
           plest example is the builtin type Void.  It has no operations  as
           part of the type.  Its signature is therefore: type {} There is a
           built‐in function Null, which has signature ‘‘func[ ] val Void’’.
           (Recall  that  a  Void  value  is  also produced by the do ... od
           loop.)  Now consider a type VOID which has the function  Null  as
           its only component.  Such a type could be declared as
                          VOID == Void with { Null == Null }
           It  would make sense to use this as the built‐in type.  The other
           alternative was chosen only so that we could  write  ‘‘Null[  ]’’
           instead  of  of ‘‘Void$Null[ ]’’.  It would have signature type {
           Null: func [ ] val VOID } Unfortunately, this notion  of  a  type
           signature  won’t  get  us  very  far.  It is frequently useful to
           build a new type which behaves like an existing one, but is  nev‐
           er‐  theless  distinct from it.  For example, we may wish to have
           two types, Meters and Feet with the same operations of  addition,
           subtraction  etc.  By keeping them distinct we can use the signa‐
           ture checking mechanism to guarantee that we don’t  get  the  two
           mixed  up.   We  should  be  able to build both of these types by
           first constructing Meters, and then simply using the declaration:
           Feet  ==  Meters  to get the type feet.  (Note once more that the
           signature mechanism is purely syntactic.  Thus ‘‘val  Feet’’  and
           ‘‘val  Meters’’  are  still  distinct signatures, and we can thus
           achieve the desired protection.  In fact, this  is  probably  too
           much  protection.   In  reality,  we would want to introduce some
           conversion functions at some point.  Again the signature checking
           mechanism  can  assure that these are used exactly where they are
           appropriate.)  To illustrate what goes wrong in a simple context,
           let’s  try the analogous exercise with the type VOID.  We use the
           declaration VOID2 == VOID to get a  second  type  with  identical
           characteristics.   Certainly  its signature has to be the same as
           that of Void, namely type { Null : func [ ] val VOID }  But  what
           we  wanted  was type { Null : func [ ] val VOID2 } The problem is
           that Null should return value of whatever type it is a  component
           of,  not  the specific type VOID.  Therefore we need to give this
           type a name in the signature.  Such a local type name is  written
           immediately  after  the  ‘type’ keyword in the signature.  Thus a
           more appropriate signature for VOID would be type V { Null : func
           [  ]  val V } Now the construction of VOID2 works properly.  This
           version of VOID is harder to obtain.  It might be declared as
           VOID = extend { Void } with V { Null == func[ ] { V$In[Null] }  }
                                    export{ Null }
           These  constructs are discussed below.  We conclude with two more
           examples.  The built‐in type Short will serve as the first.   Its
           signature  is:  type  S {         New; :=; V; < ; > ; = ; <=; >=;
           <>;         ’0’; ’1’; ’2’; ’3’; ’4’; ’5’;  ’6’;  ’7’;  ’8’;  ’9’;
                   ‐  : func [ val S ] val S ;         +, ‐, *, /, **, %, ^+
           : func [ x,y : val S ] val S;         +=, ‐= : func [var  S;  val
           S]  val  S;         get: func [var Void] val S;         put: func
           [val  S]  val  S;          puts:    func  [val  S]   val   ChStr;
                   shift  : func [what, how_much: val S] val S;         New:
           func [ ] var S;         New: func [ val S ] var S; }  (The  func‐
           tion  ‘‘get’’  returns  an  integer  read from the standard input
           file, ‘‘put’’ prints an integer, and ‘‘puts’’ converts an integer
           to  its  decimal  character  string  representation.   The second
           ‘‘New’’ function initializes the freshly created variable.)   The
           above  makes  use of yet another form of abbreviation.  Operation
           names such as ‘‘V’’ tend to occur in many  types  with  the  same
           signature.   They  therefore  have  default signatures associated
           with them which can be omitted from a type signature.  Such names
           and  the associated signatures are given in appendix 2.  As a fi‐
           nal illustration, the following is a possible  signature  of  the
           BoundedStack function used above: func [ T : type { New; V; := };
           val Short ]         type S {                 push : func [ val S;
           val  T  ]  val  S;                  top   : func [ val S ] val T;
                           pop  : func [ val S ] val S;                 emp‐
           ty:  func  [  ]  val S         } The signature indicates that the
           BoundedStack function expects an integer  and  a  type  argument.
           The type argument used must include the functions New, V, and :=.
           The signature checking rules described  below  allow  the  actual
           type  argument  to  have additional components as well.  Thus the
           builtin Short type would be an acceptable argument.  In  fact  if
           we were willing to be slightly clever about the implementation of
           the BoundedStack function we would not even have to require  that
           the parameter include the three functions specified.  The parame‐
           ter signature would then be given simply as type {} and any  type
           whatsoever  could  be passed to it.  (If the three operations are
           provided then an array implementation could be used.)  Signatures
           themselves  may  appear  as expressions.  Such expressions do not
           compute interesting values.  (Since there are no interesting  op‐
           erations  that are applicable to signatures, there is not much we
           can do with such a value in any case.)  Being able to write  sig‐
           natures  in  expression  contexts  does however allow us to write
           functions that operate uniformly on values, variables, functions,
           and types.  This will be illustrated below.  It also allows us to
           give names to long signatures so that they don’t need to  be  re‐
           peated.  For example, We could write let
               s === val Short;
                   fact == func[n: s] { ... } in ...  We use ‘‘===’’ instead
           of ‘‘==’’ to indicate that ‘‘s’’ and ‘‘val Short’’ should be con‐
           sidered to be completely identical, even for purposes of checking
           signature correctness.  The Russell type checking system  can  be
           described  by  a  pair of rules for each language construct.  The
           first rule gives constraints on the signatures of the  subexpres‐
           sions.  These constraints must be satisfied for the expression to
           be signature correct.  The second gives the signature of the con‐
           struct itself.  Signature constraints usually require that two or
           more signatures be ‘‘the same’’.  This means that they should  be
           syntactically  identical,  with  the  following  exceptions:  The
           present compiler allows some other minor differences, such as re‐
           ordered  guards  in  conditionals.   We  list only those that are
           likely to be of interest.  Parameter names and local type identi‐
           fiers may differ, provided they are uniformly renamed.  Type sig‐
           natures may list components in different order.  (The  components
           must,  however,  have the same names.)  Parameters with identical
           signatures may, or may not, be grouped together.  The  left  side
           of  a  ‘‘===’’  declaration  is viewed as an abbreviation for the
           right side.  As we pointed out earlier, type expressions may  not
           depend  on  the values of variables.  Thus, if two signatures are
           the same,  then all type expressions they contain  must  actually
           denote  the  same  types.  As an example of the general approach,
           consider a function construction such as func [x: val Short]  val
           Short {
                if   x%2  =  0  ==>  x/2   #   else ==> 3*x+1  fi } (‘‘x%2’’
           yields the remainder of dividing x by 2.)  A large number of con‐
           straints  needs  to  be  checked to insure that this is signature
           correct.  We will elaborate on a few of them.  The checking  rule
           for  the conditional requires that all clauses have the same sig‐
           nature, This constraint is not enforced when  the  value  of  the
           conditional is immediately discarded.  Specifically, if x, y, and
           z are ‘‘Short’’ variables then
             if x > 0 ==> y := x # else ==> put["error\n"] fi; z := y; ...
           is signature correct, in spite of the fact that the first  clause
           of  the  conditional  has signature ‘‘val Short’’, and the second
           has signature ‘‘val ChStr’’.  A similar situation occurs  if  the
           conditional  is  the  body of a function with val Void signature.
           In our example this is satisfied since ‘‘x/2’’ and ‘‘3*x+1’’ both
           have  signature ‘‘val Short’’ (for reasons discussed below).  The
           checking rule also requires all guards to  have  signature  ‘‘val
           Boolean’’.  The guard ‘‘x%2 = 0’’ satisfies this constraint.  The
           second guard abbreviates ‘‘not x%2 = 0’’ and thus  also  has  the
           appropriate  signature.   The signature of the conditional itself
           is that of the arms.  In our example, the conditional,  and  thus
           the  body  of the function, has signature ‘‘val Short’’.  Similar
           rules exist for function  constructions.   We  require  that  the
           specified  result  signature  (if any) match the signature of the
           body.  The signature of the construction is that specified by the
           heading  (with the possible addition of an inferred result signa‐
           ture).  Thus the above function construction has  signature  func
           [x:  val  Short]  val Short which may be abbreviated to func [val
           Short] val Short since the parameter name is not significant  for
           signature  checking.  Signature calculus rules for the other lan‐
           guage constructs are given in [Boe 85].  Only  two  of  them  are
           non‐obvious,  and  they  are  described  below.  We first examine
           function applications.  Given our examples so far, an obvious set
           of rules for function applications would be: The parameter signa‐
           tures in the function signature must be the same  as  the  signa‐
           tures  of  the corresponding argument subexpressions.  The signa‐
           ture of the function application is the result signature  of  the
           function.   Unfortunately,  this  is  no longer adequate, once we
           start taking advantage of the Russell type structure.  As a  sim‐
           ple  example, consider writing an identity function.  A first at‐
           tempt might be: identity == func [x: ?]  ?  {  x  }  Clearly,  it
           should  be  possible  to apply this function to any simple value,
           any function, any type,  or  any  variable.   Substituting,  say,
           ‘‘val  Short’’ for ‘‘?’’ would restrict it to one argument signa‐
           ture, and is thus not acceptable.  This situation is  dealt  with
           in  Russell by passing the signature associated with the argument
           as another argument.  Thus we would rewrite the identity function
           as  identity  == func [x: S; S: signature] S Alternatively, if we
           wanted to restrict the function to only simple values,  we  could
           write  it  as identity2 == func [x: val T; T: type {}] val T This
           was necessary in earlier versions of the language.  If we  wanted
           to  apply  the  identity  function  to the (short) integer 13, we
           would write identity[13, val Short] which can be  abbreviated  as
           Trailing  arguments  may  be omitted if they can be inferred from
           the explicit ones.  identity[13] This application is  not  signa‐
           ture  correct  by  rule  (1)  above.  First, ‘‘13’’ has signature
           ‘‘val Short’’, and not ‘‘S’’.  Clearly, the  parameter  signature
           ‘‘S’’  is intended to denote the second parameter, and should not
           be used literally in the  comparison.   Thus  the  checking  rule
           needs  to be adapted to read: The signatures of the argument sub‐
           expressions must match the parameter signatures, after any param‐
           meter names in the parameter signatures have been replaced by the
           corresponding actual argument.  Thus we first replace  the  ‘‘S’’
           in  the  signature of ‘‘x’’ by ‘‘Short’’, and then check that the
           resulting parameter signature matches the  signature  of  ‘‘13’’.
           In the case of ‘‘identity2’’, we would write the function call as
           ‘‘identity2[13, Short’’].  Here another problem  occurs  when  we
           check  that  the  argument ‘‘Short’’ matches the second parameter
           signature.  The type ‘‘Short’’ contains a large number of  opera‐
           tions,  but  the parameter signature calls for none.  This should
           not matter; the signature ‘‘type{}’’  was  intended  to  indicate
           that we did not require any operations from the type ‘‘T’’.  Thus
           the word ‘‘match’’ in our revised rule should be  interpreted  to
           mean  that  the  two  signatures are either the same, or they are
           both type signatures, and the argument signature contains  a  su‐
           perset  of  the  operations in the parameter signature.  Any type
           signature ‘‘matches’’ the signature  ‘‘type{}’’.   Finally,  rule
           (2)  needs  to  be  updated to correspond to the revised checking
           rule.  The application ‘‘identity[13, val  Short]’’  should  have
           signature  ‘‘val Short’’,  rather  than ‘‘S’’.  Thus we write The
           signature of the function application is the result signature  of
           the  function  with parameter names replaced by actual arguments.
           A situation similar to that occurring for applications occurs for
           selections  of  an operation from a type.  The ‘‘+’’ component of
           the type ‘‘Short’’ has signature func [val S; val S] val S  where
           S is the local type identifier.  But the signature of ‘‘Short$+’’
           should be func [val Short; val Short] val Short  (In  particular,
           we need to insure that ‘‘1 + 2’’ has signature ‘‘val Short’’, and
           not ‘‘val S’’.)  Thus the signature of a selection is the  signa‐
           ture of the component, with the local type identifier replaced by
           the type expression preceding the $‐sign.   As  was  pointed  out
           above,  we  require that two syntactically identical type expres‐
           sions appearing inside signatures refer to the same  type  value.
           The  signature  ‘‘val  T’’  implies that operations from the type
           ‘‘T’’ are applicable.  But this only make sense if the  type  ex‐
           pressions ‘‘T’’ evaluates to a well‐defined type value.  This re‐
           quires that a type expression may not depend on the  value  of  a
           variable.  In the original version of the language [Boe 80], this
           was enforced by requiring that neither  type  valued  expressions
           nor  function  valued  expressions  (which  could,  after all, be
           called from type valued expressions) may mention variables.   Un‐
           fortunately,  the  restriction  that  functions be ‘‘pure’’, i.e.
           not mention variables, has proved to be impractical.  It  forbids
           functions  that  update debugging or profiling information.  More
           importantly, it prevents functions  from  ‘‘remembering’’  values
           that  it previously computed to reduce the running time of subse‐
           quent calls.  In order to avoid these problems, we optionally al‐
           low  a  more  liberal restriction on functions.  (This is invoked
           with the ‐L option to the compiler.)  This is based on the intro‐
           duction  of  a  variable  (called FS for historical reasons) that
           represents the entire state of the machine and its  file  system.
           It  has signature ‘‘var Void’’.  There are no operations that al‐
           locate Void variables, so this is the only such  variable  avail‐
           able.   (The use of the Void type is rather arbitrary.  A new and
           different type could have been introduced instead.)   A  function
           that  has  access to a var Void variable, that is a function that
           was passed a var Void variable as a parameter, has access to  the
           entire  machine state, and thus may access global variables.  (We
           currently insist that the var Void parameter be the last  parame‐
           ter  of  the  function.)   Such functions are known as ‘‘impure’’
           functions.  This scheme still insures that  type  valued  expres‐
           sions  always produce the same value, since a type expression may
           not mention the variable FS, and there is no possibility of allo‐
           cating a local variable with ‘‘var Void’’ signature.  This scheme
           is made syntactically much more pleasant  by  the  following  two
           conveniences: The entire user program is implicitly surrounded by
           let impure === var Void in ... ni Arguments with var Void  signa‐
           tures  may be omitted.  They are automatically inferred to be the
           trailing var Void argument of the innermost surrounding  function
           (or  FS  at  the outer level).  The first point allows reasonable
           syntax for impure functions.  A ‘‘function’’ that increments  the
           global  variable ‘‘x’’ by a value ‘‘y’’ passed as a parameter can
           be written as func[ y : val Short; impure] { x += y } The  second
           point assures that it is essentially never necessary to explicit‐
           ly pass FS to an impure function; calls to impure functions  look
           like  calls to pure functions.  Much of Russell is devoted to the
           creation and manipulation of types.  This is what gives the  lan‐
           guage most of its flexibility.  Rather than discussing the neces‐
           sary facilities in detail, we give an overview of  what’s  avail‐
           able,  and  defer  to [Boe 85] for the details.  Types in Russell
           are obtained: as built‐in types, by applying  built‐in  type‐pro‐
           ducing  functions,  through the use of type constructors provided
           by the language, or by modifying some existing type.

           The built‐in types provided by the  current  implementation  are:
           Provides  no operations.  Void values are used where the value of
           an expression is not  of  interest.   Provides  standard  Boolean
           (logical)  operations.  Provides 16 bit integer operations.  Pro‐
           vides (64 bit) floating point operations.  Provides operations on
           integers  of  size  limited  only  by machine memory constraints.
           Built‐in type producing functions  are:  Requires  a  (‘‘Short’’)
           size,  and  an  element  type as arguments.  The result is a type
           containing operations to access arrays of the given size and ele‐
           ment  type.  A two‐dimensional array of 100 by 100 floating point
           numbers might be declared as:  matrix  ==  Array[100,  Array[100,
           Float]];  A == matrix$New[ ]; The element Ai,j can then be refer‐
           enced as: A.i.j Provides operations on  linear  lists  containing
           elements of the specified argument type.  Operator syntax is cho‐
           sen so that it is relatively easy to build functions on  a  vari‐
           able  number  of  arguments by writing them as functions on lists
           Similar to List except that an efficient ‘‘lazy’’ cons operation,
           i.e.  one  that defers evaluation of its second argument, is pro‐
           vided.  Provides operations on ‘‘references’’ or ‘‘pointers’’.

           The following type constructions are  provided.   Note  that  the
           above types and functions are simply predeclared identifiers, and
           are not otherwise special.   Type  constructions,  on  the  other
           hand,  are  really  language  primitives, with associated syntax.
           Provides Cartesian product operations, that is, functions to  ma‐
           nipulate  tuples  of  objects.  in particular, the resulting type
           includes a function ‘‘Mk’’ to build a tuple, functions to  select
           a  component of a tuple, and ‘‘New’’, ‘‘:=’’, and ‘‘V’’ functions
           to manipulate product variables.  For  example,  prod  {  i:  val
           Short;  x: val Float } contains operations on pairs, the first of
           which represents an integer, and the second of which represents a
           floating  point  number.   These  would include ‘‘Mk’’ to build a
           pair, ‘‘i’’ to obtain the first component, and  ‘‘x’’  to  obtain
           the  second  component.   They  would  have  signatures func [val
           Short; val Float] val t func [val t] val Short func [val  t]  val
           Float  where t is the local type name.  The signature of one com‐
           ponent may depend on another component.  We may build  a  product
           such  as: prod { x: val T; T: type { ... } } Values corresponding
           to such a type are, in a sense,  self‐describing.   They  contain
           both  a  value  (‘‘x’’) and information about how to interpret it
           (‘‘T’’).  Objects in the sense of ‘‘object‐oriented programming’’
           can  be  built in this manner.  Since the result of an expression
           with product type can be assigned to a variable,  and  a  product
           may  have  function or type components, product types may also be
           used simply to convert between functions and assignable  objects.
           As  an  example,  the function ‘‘fact’’ defined earlier cannot be
           directly assigned to a variable.  It can be  argued  convincingly
           that  both  this, and the distinction between ‘‘Ref’’ and ‘‘var’’
           should and could have been avoided by changing the design of  the
           signature  calculus.   We  agree,  and we may eventually make the
           necessary changes.  assignment operations provided  by  the  lan‐
           guage  require  the second subexpression to have ‘‘val’’, and not
           ‘‘func’’ signature.)  On the other hand, if we let T be prod { x:
           func  [val Short] val Short } then T$Mk builds a product with one
           field, that is, it has  signature  func  [func  [val  Short]  val
           Short] val T Thus ‘‘T$Mk[fact]’’ has signature ‘‘val T’’, and can
           thus be assigned to a ‘‘var T’’ variable  (using  the  assignment
           operation provided by the product).  The ‘‘T$x’’ operation can be
           used to convert back.  Informally, a union construction is  simi‐
           lar  to a product construction, except that an object of the type
           contains only one of the kinds of objects specified, rather  than
           all  of them at once.  In the Russell view, a union type contains
           operations to convert back and forth between the union type,  and
           a number of other types.  The names of these operations are built
           by adding standard prefixes to the component names  specified  in
           the  union construction.  Thus if T is defined as T == union { i:
           val Short; x: val Float } then T will contain operations to  con‐
           vert between ‘‘val Short’’ (the signature of the ‘‘i’’ field) and
           the union type, as well as between ‘‘val Float’’  and  the  union
           type.    More   precisely,   ‘‘T$from_i’’   will   convert   from
           ‘‘val Short’’ to ‘‘val T’’, ‘‘T$to_i’’ will convert in the  other
           direction,  ‘‘T$is_x’’  will  test whether a ‘‘val T’’ expression
           actually represents a ‘‘val Short’’, and thus whether  ‘‘T$to_i’’
           may  be safely applied.  Analogous functions will be included for
           the ‘‘x’’ component.  It is allowable to give  the  union  (or  a
           product)  a  local  name  to  facilitate recursion.  For example:
           union U { end: val Void;
                                   other: val prod { first: val Short; rest:
           val  U } } operates on elements which are either ‘‘Null’’ or con‐
           sist of an integer and another similar element.  Thus such an ob‐
           ject  is  effectively a list of integers.  This is similar to the
           ‘‘prod’’ construction, except that all fields must  have  ‘‘val’’
           signature, and that individual fields of ‘‘record’’ variables may
           be assigned to.  Builds enumeration types (scalar type in  Pascal
           terminology).  Creates a copy of an existing type with conversion
           operations between the new and old types.

           Russell types may be modified with the  following  language  con‐
           structs: Adds operations to, or replaces operations in, an exist‐
           ing type.  The syntax is old_type_expression with local_type_name
           {  new_operation_declarations  }  New operations may refer to old
           ones (or to themselves) by selecting from the  local  type  name.
           Remove  any unmentioned operations from an existing type.  Remove
           the specified operations from an existing type.  Russell provides
           for  a  rather simple‐minded, but effective, separate compilation
           facility.  Any function that refers only to built‐in  identifiers
           (and parameters to the function) may be placed in a separate file
           and compiled by itself.  The function in file ‘‘filename.r’’  can
           be referenced in other files with the expression: extern { "file‐
           name" } Typically  separately  compiled  functions  will  produce
           types.   For  example, stacks could be implemented by placing the
           following Russell program  in  a  file  ‘‘stack.r’’:  func  [ele‐
           ment_type: type{}] {
               (List   [element_type])   with   stack   {          empty  ==
           stack$nil;         top == stack$head;         pop ==  stack$tail;
                   push  ==  func  [S:  val  stack;  x:  val element_type] {
           cons[x,S] };
               } export { New; :=; V; top; pop; push } } The  body  of  this
           function  takes the built‐in type producing function ‘‘List’’ and
           applies it to the type of stack elements (the  parameter  to  the
           stack  implementation).   The  ‘‘with’’ construct is then used to
           add operations appropriate for stacks.   Finally  the  ‘‘export’’
           clause  removes  all  operations  from  the resulting type except
           those  that  are  appropriate  to  stacks.   (For  example,   the
           ‘‘cons’’, ‘‘head’’ and ‘‘tail’’ operations from the original list
           type are removed.  But the original assignment operation is  pre‐
           served,  since it applies equally well to stacks.)  The above im‐
           plementation, once compiled, can be referenced from a  main  pro‐
           gram using, for example, let
               stack  == extern { "stack" }; in ...  (stack[Short])$push ...
           ni Compilation of the main program will examine information  pro‐
           duced  by the compilation of ‘‘stack.r’’ in order to check signa‐
           ture correctness of the main program (and to produce better  code
           for it).  We require that subsidiary functions be compiled before
           those functions that reference them.  This restriction can be ef‐
           fectively  circumvented  (sometimes at the cost of some execution
           efficiency) by parametrizing different program sections with  re‐
           spect  to  all other units they reference.  For example, we could
           rewrite the above main program (in file  ‘‘main.r’’)  as  func  [
           stack:  func  [ t: type{ } ] type s {New; := ; V; empty: func [ ]
           val s; ...} ] {
                ...  (stack[Short])$push ...  } It is now possible  to  com‐
           pile it without first compiling the stack program.  We do need to
           subsequently compile a main program that specifies how to  assem‐
           ble the various program pieces.  In this case, it would read sim‐
           ply extern {‘‘main’’} [ extern { ‘‘stack’’} ]  We  conclude  with
           some  more  examples.  The following is the factorial function we
           saw before, modified to compute results of essentially  unbounded
           size,  and  embedded in enough context to turn it into a complete
           program: let
               ! == func [ n : val Short ]
                           {
                               if
                                     n > 0 ==> Long$In[n] * ((n ‐ 1)!)
                               #     n = 0 ==> Long$1
                               fi
                            };
               x == Short$New[ ]; in
               do
                   (put["Factorial of?"]; x := get[FS]) >= 0  ==>   put[x!];
           put["\n"]
               od ni The program will calculate factorials until it is given
           a negative input.  Note that the do ... od construct  in  Russell
           can  be  used  to simulate a number of other loop constructs, in‐
           cluding a repeat ... until loop, by moving more of the loop  body
           into  the  guard.   Dijkstra’s  original construct does not allow
           side effects in guards.  Thus this comment does not apply to  his
           language.  This, and the following example, illustrate the use of
           functions as objects to be manipulated by the  program.   Certain
           operations  are  naturally  viewed  as mapping functions to func‐
           tions.  Many programming languages force us to modify this  view,
           and to recast them in a different framework.  Russell allows them
           to be represented directly.  Here we look at (a  naive  view  of)
           numerical  differentiation.   We  give  a function ‘‘derivative’’
           which returns an approximation to the derivative of a given func‐
           tion.   We  illustrate its use by embedding it in a program which
           uses it to multiply 13 by 2, the hard way: let
               epsilon == 0.0001;
               derivative == func [f: func[val Float]val Float] {
                                                   func[x:  val  Float]  val
           Float {
                                                        (f[x]  ‐  f[x  ‐ ep‐
           silon])/epsilon
                                                   }
                                               };
               square == func[x: val Float] {x * x};
               double == derivative[square] in
               put[double[13.0]]; put["\n"]; ni The last illustration is  an
           unusual implementation of binary trees.  The following is a func‐
           tion which expects a type describing values stored at  leaves  as
           an argument, and produces a corresponding binary tree type as its
           result.  The result type contains functions to obtain the left or
           right  subtree  of  a given tree, to obtain the value stored at a
           leaf, to build a leaf containing a given value,  to  combine  two
           subtrees  into a new tree, and to inquire whether a tree consists
           solely of a leaf.  (The latter is provided directly by the  union
           construction and is not explicitly implemented.)  A non‐leaf tree
           could be represented as an explicit product or record  type.   We
           instead  use  a function which maps {left, right} to the left and
           right subtrees: func [L: type {}] {
               let
                   lr == enum { left, right };
               in use lr in
                   union B { leaf: val L; interior: func [val lr] val B }
                   with B {
                        left_sub_tree == func [x: val B] {

           B$to_interior[x][left]
                                                                       };
                        right_sub_tree == func [x: val B] {

           B$to_interior[x][right]
                                                                         };
                        leaf_value == B$to_leaf;
                        make_leaf == B$from_leaf;
                        make_tree == func [l,r: val B] val B {
                                                                  B$from_in‐
           terior [
                                                                        func
           [x: val lr] {
                                                                         if

           x = left  ==> l
                                                                           #
           x = right ==> r
                                                                         fi
                                                                     }
                                                                 ]
                                                               }
                   }
                   export  {  New;  :=;  V;  left_sub_tree;  right_sub_tree;
           leaf_value;
                                             make_leaf; is_leaf; make_tree }
               ni ni } We would like to thank Hausi Muller for his construc‐
           tive criticism of an earlier draft of this paper.  Boehm, H.,  A.
           Demers,  and  J. Donahue, ‘‘An Informal Description of Russell’’.
           Technical Report 80‐430,  Computer  Science  Department,  Cornell
           University, 1980.  Boehm, H., A Logic for the Russell Programming
           Language, Thesis, Cornell University, 1984.  Boehm,  H.,  Russell
           on‐line ‘‘rhelp’’ facility.  Distributed with the Russell Compil‐
           er.  (A version of this paper is available as  ‘‘rhelp  intro’’.)
           Boehm,  Hans‐J.,  and Alan Demers, ‘‘Implementing Russell’’, Pro‐
           ceedings of the SIGPLAN ’86 Symposium on  Compiler  Construction,
           SIGPLAN  Notices  21, 7, July 1986, pp. 186‐195.  Demers, A., and
           J. Donahue, ‘‘Data Types are  Values’’,  Department  of  Computer
           Science,  Cornell  University,  Technical  Report TR79‐393, 1979.
           Demers, A. and J. Donahue, ‘‘Data Types,  Parameters,  and  Type‐
           Checking’’.   Proceedings,  Seventh Annual Principles of Program‐
           ming Languages Symposium, 1980, pp. 12‐23.   Demers,  A.  and  J.
           Donahue, ‘‘Type‐Completeness as a Language Principle’’.  Proceed‐
           ings, Seventh Annual Principles of Programming  Languages  Sympo‐
           sium, 1980, pp. 234‐244.  Demers, A. and J. Donahue, ‘‘The Seman‐
           tics of Russell: An Exercise in Abstract Data Types’’.  Technical
           Report  80‐431,  Computer Science Department, Cornell University,
           1980.  Demers, A. and J. Donahue, ‘‘Making variables abstract: an
           equational  theory for Russell’’. Proceedings, Tenth Annual Prin‐
           ciples of Programming Languages Symposium,  1983.   Donahue,  J.,
           and  A.  Demers,  ‘‘Data  Types are Values’’, ACM Transactions on
           Programming Languages and Systems 7, 3 (July 1985), pp.  426‐445.
           Dijkstra,  E., A Discipline of Programming.  Prentice‐Hall, 1976.
           Hook, Jim, ‘‘Understanding Russell ‐ A First Attempt’’, Semantics
           of  Data  Types,  Proceedings, Springer Lecture Notes in Computer
           Science 173, 1984, pp. 69‐86.  Stoy, J., Denotational  Semantics:
           The  Scott‐Strachey Approach to Programming Language Theory.  MIT
           press, 1977. See esp. chapter 7.  The language Russell was devel‐
           oped  at  Cornell, primarily by the latter two authors.  The con‐
           cepts  involved  are  are  discussed  more  fully  in   [Dem 79],
           [Dem 80a],  [Dem 80b], and [Don 85].  The purpose of the language
           design is to test the practicality of the type system in the con‐
           text  of a very small language (at least as measured by number of
           grammar productions).  As a result, no attempt was  made  to  ad‐
           dress certain issues, notably that of concurrency.  It seems pos‐
           sible to graft a notion of concurrency onto the implemented  lan‐
           guage  in  a very inelegant fashion.  Later designs can deal with
           the issue more easily, though the proposed formal semantics  gen‐
           erally  do not.  We described the implemented version of the lan‐
           guage.  The implementation differs form the language of  [Boe 80]
           primarily  in  that  it corrects some problems with the signature
           calculus,  adds the ‘‘prod’’ type construction in  place  of  the
           more  restrictive  ‘‘image’’  construct, revises the semantics of
           ‘‘extend’’ and ‘‘record’’ for the sake  of  efficiency,  provides
           explicit constructs to support separate compilation, and provides
           a different collection of built‐in types  and  operations  (which
           now includes ‘‘Call/cc’’).  Unfortunately it does not incorporate
           a number of more recently proposed design changes, such as  Algol
           68  style  ‘‘ref’’ types, and an explicit notion of ‘‘purity’’ in
           the signature calculus.  It also has not been brought  into  con‐
           formity  with  the  ideas  in [Hoo 84].  A number of language de‐
           scriptions more formal than [Boe 80] have  also  been  published.
           [Dem 80c]  gives  a  denotational/operational definition, using a
           Russell subset as the meta‐language.   [Dem 83]  gives  a  purely
           equational definition of much of the language.  [Boe 84] performs
           the same task in an axiomatic  framework.   [Hoo 84]  provides  a
           more  mathematical  interpretation  of  the type structure of the
           language.  Currently implementations exist for Sun 3 and Vax  ma‐
           chines.   The  Vax  implementation is described in [Boe 86].  For
           details on obtaining a copy, please send mail to  boehm@rice.edu.
           The  following  kinds of abbreviations are allowed by the current
           implementation in at least some contexts.  Selections from a type
           T  can  usually  be omitted if any of the arguments has signature
           ‘‘val T’’ or ‘‘var T’’.  It is also possible to specify a list of
           ‘‘default’’  types  for selections.  Types such as ‘‘Short’’ nor‐
           mally appear on this list.  Applications of V functions can  usu‐
           ally  be  omitted.  Square brackets ‘‘[ ]’’ denoting function ap‐
           plication with no arguments can be omitted if there presence  can
           be  inferred  from  signature information.  Trailing arguments to
           function applications can usually be omitted  if  their  identity
           can  be  determined from the remaining arguments, if their signa‐
           ture is var Void, or if the function is named ‘‘.’’, and the  ap‐
           plication ‘‘looks like a floating point constant’’.  Function re‐
           sult signature can be omitted if they can be ascertained from the
           body  of  the function construction.  Application brackets can be
           omitted if they can be reconstructed  from  the  precedences  de‐
           scribed  above.   Strings may be used to abbreviate certain kinds
           of repeated concatenations, as described above.  Type  components
           with  certain  names have associated default signatures.  If such
           components have the indicated signature, then the signature spec‐
           ification may be omitted from a type signature.  The following is
           a     complete     list     of     such     names:      Identifi‐
           er                              Default Signature

           New                                       func   [  ]  var  T  :=
                       func [ var T; val T ] val T  =,  <,  >,  <=,  >=,  <>
                       func   [   x,   y:   val  T  ]  val  Boolean  ^+,  ^*
                       func   [   x,    y:    val    T    ]    val    T    V
                       func   [   var  T  ]  val  T  any  quoted  identifier
                       func [ ] val T In all of the above, T represents  the
           local type name.  If none is explicitly specified it is generated
           by the compiler.  Selection types and omitted arguments  are  in‐
           ferred primarily in a ‘‘bottom‐up’’ manner.  That is arguments to
           function applications are used to infer selections of  the  func‐
           tion  and  to  infer  missing arguments for the application.  The
           context in which the application appears is not used.  This means
           that  selections  of functions from types other than the type sof
           their arguments frequently need to be specified in some  explicit
           manner.   In  particular,  the  compiler is very poor at choosing
           types from which to select constants and  ‘‘prod’’  ‘‘Mk’’  func‐
           tions.   The  ‘‘use  <type  list> in <expr> ni’’ construct can be
           used to suggest types from which to infer such  selections.   The
           following  help files are available through the ‘‘rhelp’’ facili‐
           ty.  A few of them are actually duplicates of each other.  A num‐
           ber of topics are not even touched on in this introduction.  Thus
           this list should also be useful in providing an overview of omis‐
           sions from this document.  Function to ungracefully terminate ex‐
           ecution.  Function to test whether two  variables  refer  to  the
           same  location.   Function calls.  Access command line arguments.
           Function for constructing array types.  Unlimited size  integers.
           Built‐in  type.  Capture the current continuation associated with
           a computation.  Can be  used  to  implement  exception  handling,
           coroutines, etc.  Partial evaluation ‘‘and’’.  Built‐in character
           string type.  Acceptable abbreviations.  How to invoke  the  com‐
           piler.  Russell conditionals.  Partial evaluation ‘‘or’’.  Blocks
           and declarations.  The Russell loop construct.  Enumeration  type
           constructor.   Test  for  end of file on the standard input.  Ex‐
           plicitly increase heap size.   Removing  components  from  types.
           Types  of  expressions  and how they’re parsed Building new types
           with conversion functions Access separately compiled Russell  and
           non‐Russell  programs File I/O.  Built‐in double precision float‐
           ing point data type.  The ‘‘machine state’’  variable.   Function
           constructions.  How to get started;  also printed if no arguments
           are given.  Common problems.  Lexical rules.  Restriction on  the
           use  of global variables in functions.  The built‐in 16 bit inte‐
           ger data type A copy of this introduction.  Limits imposed by the
           compiler.   Function  for  producing linear list types.  Val Void
           constant.  Function for producing pointer  types.   Product  type
           constructor.   Record type constructor.  Accessing a component of
           a type.  An unusual interface to UNIX (trademark AT&T Bell  Labs)
           signals.  Brief description and syntax.  The unorthodox treatment
           of character strings and numeric constants.  Some  simple  debug‐
           ging  facilities.   The  type  constructor.   The  built‐in type.
           Adding operations to types.






















































