{Begin SubSec The Decl Package}
{Title The Decl Package}
{Text

{Tag DECL}

{index *BEGIN* Decl package}
{index *BEGIN* type declarations}


{note The Decl package was designed and implemented by R. M. Kaplan and B. A. Sheil, with the assistance of W. Teitelman and L. M. Masinter.}


{it
Note:  Decl is a LispUsers package that is contained on the file {lisp DECL.DCOM}.  The Decl package requires the {lisp LAMBDATRAN} package ({SectionRef Tag LAMBDATRAN}), so {lisp LAMBDATRAN.DCOM} will automatically be loaded with Decl if it is not already present.
}




The Decl package extends Interlisp to allow the user to declare the types of variables and expressions appearing in functions.  It provides a convenient way of constraining the behavior of programs when the generality and flexibility of ordinary Interlisp is either unnecessary, confusing, or inefficient.


The Decl package provides a simple language for declarations, and augments the interpreter and the compiler to guarantee that these declarations are always satisfied.  The declarations make programs more readable by indicating the type, and therefore something about the intended usage, of variables and expressions in the code.  They facilitate debugging by localizing errors that manifest themselves as type incompatibilities.  Finally, the declaration information is available for other purposes:  compiler macros can consult the declarations to produce more efficient code; coercions for arguments at user interfaces can be automatically generated; and the declarations will be noticed by the Masterscope function analyzer.


The declarations interpreted by the Decl package are in terms of a set of declaration types called {it decltypes}{index decltypes (in Decl package)},  each of which specifies a set of acceptable values  and also (optionally) other type specific behavior.  The Decl package provides a set of facilities for defining decltypes and their relations to each other, including  type valued expressions and a comprehensive treatment of union types.


The following description of the Decl package is divided into three parts.  First, the syntactic extensions  which permit the concise attachment of declarations to program elements are discussed.  Second, the mechanisms by which new decltypes can be defined and manipulated are covered.  Finally, some additional capabilities based on the availability of declarations are outlined.



{Begin SubSec Using Declarations in Programs}
{Title Using Declarations in Programs}
{Text

Declarations may be attached to the values of arbitrary expressions and to {lisp LAMBDA} and {fn PROG} variables throughout (or for part of) their lexical scope.  The declarations are attached using constructs that resemble the ordinary Interlisp {lisp LAMBDA}, {fn PROG}, and {fn PROGN}, but which also permit the expression of declarations.  The following examples illustrate the use of declarations in programs.


Consider the following definition for the factorial function {lisp (FACT {arg N})}:

{lispcode
[LAMBDA (N)
   (COND
      ((EQ N 0) 1)
       (T (ITIMES N (FACT (SUB1 N]}


Obviously, this function presupposes that {lisp N} is a number, and the run-time checks in {fn ITIMES} and {fn SUB1} will cause an error if this is not so.  For instance, {lisp (FACT T)} will cause an error and print the message {lisp NON-NUMERIC ARG T}.  By defining {lisp FACT} as a {lisp DLAMBDA}{index DLAMBDA (in Decl package)}, the Decl package analog of {lisp LAMBDA}, this presupposition can be stated directly in the code:

{lispcode
[DLAMBDA ((N NUMBERP))
   (COND
      ((EQ N 0) 1)
       (T (ITIMES N (FACT (SUB1 N]}


With this definition, {lisp (FACT T)} will {it not} result in a {lisp NON-NUMERIC ARG T} error when the body of the code is executed.  Instead, the {lisp NUMBERP} declaration will be checked when the function is first entered, and a {it declaration fault}{index declaration fault (in Decl package)} will occur.  Thus, the message that the user will see will not dwell on the offending value {lisp T}, but instead give a symbolic indication of what variable and declaration were violated, as follows:{index DECLARATION NOT SATISFIED Error}


{lispcode
DECLARATION NOT SATISFIED
((N NUMBERP) BROKEN)
:}



The user is left in a break from which the values of variables, e.g. {lisp N}, can be examined to determine what the problem is.

The function {lisp FACT} also makes other presuppositions concerning its argument, {lisp N}.  For example, {lisp FACT} will go into an infinite recursive loop if {lisp N} is a number less than zero.  Although the user could program an explicit check for this unexpected situation, such coding is tedious and tends to obscure the underlying algorithm.  Instead, the requirement that {lisp N} not be negative can be succinctly stated by declaring it to be a subtype of {lisp NUMBERP} which is restricted to non-negative numbers.  This can be done by adding a {lisp SATISFIES}{index SATISFIES (in Decl package)} clause to {lisp N}'s type specification:

{lispcode
[DLAMBDA ([N NUMBERP (SATISFIES (NOT (MINUSP N])
   (COND
      ((EQ N 0) 1)
       (T (ITIMES N (FACT (SUB1 N]}


The predicate in the {lisp SATISFIES} clause will be evaluated after {lisp N} is bound and found to satisfy {lisp NUMBERP}, but before the function body is executed.  In the event of a declaration fault{index declaration fault (in Decl package)}, the {lisp SATISFIES} condition will be included in the error message. For example, {lisp (FACT -1)} would result in:

{lispcode
DECLARATION NOT SATISFIED
((N NUMBERP (SATISFIES (NOT (MINUSP N))) BROKEN)
:}


The {lisp DLAMBDA} construct also permits the type of the value that is returned by the function to be declared by means of the pseudo-variable {lisp RETURNS}{index RETURNS (in Decl package)}.  For example, the following definition specifies that {lisp FACT} is to return a positive integer:


{lispcode
[DLAMBDA ([N NUMBERP (SATISFIES (NOT (MINUSP N]
          [RETURNS FIXP (SATISFIES (IGREATERP VALUE 0])
   (COND
      ((EQ N 0) 1)
       (T (ITIMES N (FACT (SUB1 N]}



After the function body is evaluated, its value is bound to the variable {var VALUE}{index VALUE Var} and the {lisp RETURNS} declaration is checked.  A declaration fault will occur if the value is not satisfactory.  This prevents a bad value from propagating to the caller of {lisp FACT}, perhaps causing an error far away from the source of the difficulty.


Declaring a variable causes its value to be checked not only when it is first bound, but also whenever that variable is reset by {fn SETQ} within the {lisp DLAMBDA}.  In other words, the type checking machinery will not allow a declared variable to take on an improper value.  An iterative version of the factorial function illustrates this feature in the context of a {fn DPROG},{index DPROG Fn} the Decl package analog of {fn PROG}:

{lispcode
(DLAMBDA ([N NUMBERP (SATISFIES (NOT (MINUSP N]
          [RETURNS FIXP (SATISFIES (IGREATERP VALUE 0])
   [DPROG ([TEMP 1 FIXP (SATISFIES (IGREATERP TEMP 0]
           [RETURNS FIXP (SATISFIES (IGREATERP VALUE 0])
      LP  (COND ((EQ N 0) (RETURN TEMP)))
          (SETQ TEMP (ITIMES N TEMP))
          (SETQ N (SUB1 N))
          (GO LP]}


{fn DPROG} declarations are much like {lisp DLAMBDA} declarations, except that they also allow an initial value for the variable to be specified.  In the above example, {lisp TEMP} is declared to be a positive integer throughout the computation and {lisp N} is declared to be non-negative.  Thus, a bug which caused an incorrect value to be assigned by one of the {fn SETQ} expressions would cause a declaration failure.  Note that the {lisp RETURNS} declaration for a {fn DPROG} is also useful in detecting the common bug of omitting an explicit {lisp RETURN}.

}{End SubSec Using Declarations in Programs}




{Begin SubSec DLAMBDAs}
{Title DLAMBDAs}
{Text

The Decl package version of a {lisp LAMBDA} expression is an expression beginning with the atom {lisp DLAMBDA}.{index *PRIMARY* DLAMBDA (in Decl package)}  Such an expression is a function object that may be used in any context where a {lisp LAMBDA} expression may be used.  It resembles a {lisp LAMBDA} expression except that it permits declaration expressions in its argument list, as illustrated in the examples given earlier.  Each element of the argument list of a {lisp DLAMBDA} may be a literal atom (as in a conventional {lisp LAMBDA}) or a list of the form {lisp ({arg NAME} {arg TYPE} . {arg EXTRAS})}.{foot
Strictly, this would require a declaration with a {lisp SATISFIES} clause to take the form {lisp (N (NUMBERP (SATISFIES --)) --)} ({PageRef (Decl Type Expression) SATISFIES}).  However, due to the frequency with which this construction is used, it may be written without the inner set of parentheses, e.g. {lisp (N NUMBERP (SATISFIES --) --)}.
}{comment endfootnote}


{arg NAME} fulfills the standard function of a parameter, i.e. providing a name to which the value of the corresponding argument will be bound.


{arg TYPE} is either a Decl package type name or type expression.  When the {lisp DLAMBDA} is entered, its arguments will be evaluated and bound to the corresponding argument names, and then, after {it all} the argument names have been bound, the declarations will be checked.  The type checking is delayed so that {lisp SATISFIES} predicates can include references to other variables bound by the same {lisp DLAMBDA}.  For example, one might wish to define a function whose two arguments are not only both required to be of some given type, but are also required to satisfy some relationship (e.g., that one is less than the other).


{arg EXTRAS} allows some additional properties to be attached to a variable.  One such property is the accessibility of  {arg NAME} outside the current lexical scope.  Accessibility specifications include the atoms {lisp LOCAL}{index LOCAL (in Decl package)} or {lisp SPECIAL}{index SPECIAL (in Decl package)}, which indicate that this variable is to be compiled so that it is either a {lisp LOCALVAR} or a {lisp SPECVAR}, respectively.  This is illustrated by the following example:

{lispcode
[DLAMBDA ((A LISTP SPECIAL)
          (B FIXP LOCAL))
         {ellipsis}]}


A more informative equivalent to the {lisp SPECIAL} key word is the {lisp USEDIN}{index USEDIN (in Decl package)} form, the tail of which can be a list of the other functions which are expected to have access to the variable:{foot
{lisp USEDIN} is mainly for documentation purposes, since there is no way for such a restriction to be enforced.{note what, no tie-in to masterscope?}
}{comment endfootnote}


{lispcode
[DLAMBDA ((A LISTP (USEDIN FOO FIE))
          (B FIXP LOCAL))
         {ellipsis}]}


{arg EXTRAS} may also include a comment in standard format, so that descriptive information may be given where a variable is bound:


{lispcode
[DLAMBDA ((A LISTP (USEDIN FOO FIE)   (* This is an important variable))
          (B FIXP LOCAL))
         {ellipsis}]
}


As mentioned earlier, the value returned by a {lisp DLAMBDA} can also be declared, by means of the pseudo-variable {lisp RETURNS}{index *PRIMARY* RETURNS (in Decl package)}.  The {lisp RETURNS} declaration is just like  other {lisp DLAMBDA} declarations, except (1) in any {lisp SATISFIES} predicate, the value of the function is referred to by the distinguished name {var VALUE}; and (2) it makes no sense to declare the return value to be {lisp LOCAL} or {lisp SPECIAL}.

}{End SubSec DLAMBDAs}



{Begin SubSec DPROG}
{Title DPROG}
{Text

Just as {lisp DLAMBDA} resembles {lisp LAMBDA}, {fn DPROG}{index DPROG Fn} is analogous to {fn PROG}.  As for an ordinary {fn PROG}, a variable binding may be specified as an atom or a list including an initial value form.   However, a {fn DPROG} binding also allows {arg TYPE} and {arg EXTRAS} information to appear following the initial value form.  The format for these augmented variable bindings is
{lisp ({arg NAME} {arg INITIALVALUE} {arg TYPE} . {arg EXTRAS})}.
The only difference between a {fn DPROG} binding and a {lisp DLAMBDA} binding is that the second position is interpreted as the initial value for the variable.  Note that if the user wishes to supply a type declaration for a variable, an initial value {it must} be specified.  The same rules apply for the interpretation of the type information for {fn DPROG}s as for {lisp DLAMBDA}s, and the same set of optional {arg EXTRA}s can be used.  {fn DPROG}s may also declare the type of the value they return, by specifying the pseudo-variable {lisp RETURNS}.

Just as for a {lisp DLAMBDA}, type tests in a {fn DPROG} are not asserted until {it after} all the variables have been bound, thus permitting predicates to refer to other variables being bound by this {fn DPROG}.  If {lisp NIL} appears as the initial value for a binding (i.e. the atom {lisp NIL} actually appears in the code, not simply an expression which evaluates to {lisp NIL}) the initial type test will be suppressed, but subsequent type tests, e.g. following a {fn SETQ}, will still be performed.  


A common construct in Lisp is to bind and initialize a {fn PROG} variable to the value of a complicated expression in order to avoid recomputing it, and then to use this value in initializing other {fn PROG} variables, e.g.


{lispcode
[PROG ((A {arg EXPRESSION}))
      (RETURN (PROG ((B ({ellipsis} A {ellipsis}))
                     (C ({ellipsis} A {ellipsis})))
                    {ellipsis}]}


The ugliness of such constructions in conventional Lisp often tempts the programmer to loosen the scoping relationships of the variables by binding them all at a single level and using {fn SETQ}'s in the body of the {fn PROG} to establish the initial values for variables that depend on the initial values of other variables, e.g.

{lispcode
[PROG ((A {arg EXPRESSION}) B C)
      (SETQ B ({ellipsis} A {ellipsis})) 
      (SETQ C ({ellipsis} A {ellipsis}))
      {ellipsis}]}


In the Decl package environment, this procedure undermines the protection offered by the type mechanism by encouraging the use of uninitialized variables. Therefore, the {fn DPROG} offers a syntactic form to encourage more virtuous initialization of its variables.   A {fn DPROG} variable list may be segmented by occurrences of the special atom {lisp THEN}{index THEN (in Decl package)}, which causes the binding of its variables in stages, so that the bindings made in earlier stages can be used in later ones, e.g.


{lispcode
[DPROG ((A (LENGTH FOO) FIXP LOCAL)
        THEN (B (SQRT A) FLOATP)
        THEN (C (CONS A B) LISTP))
       {ellipsis}]}


Each stage is carried out as a conventional set of {fn DPROG} bindings (i.e., simultaneously, followed by the appropriate type testing).  This layering of the bindings permits one to gradually descend into a inner scope, binding the local names in a very structured and clean fashion, with initial values type-checked as soon as possible.

}{End SubSec DPROG}



{Begin SubSec Declarations in Iterative Statements}
{Title Declarations in Iterative Statements}
{Text


The CLISP iterative statement ({PageRef Tag CLISP}) provides a very useful facility for specifying a variety of {fn PROG}s that follow certain widely used formats.  The Decl package allows declarations to be made for the scope of  an iterative statement via the {lisp DECLARE} CLISP i.s.opr.{index DECLARE (I.S. Operator)}  {lisp DECLARE} can appear as an operator anywhere in an iterative statement, followed by a list of declarations, for example:

{lispcode
(for J from 1 to 10 declare (J FIXP) do {ellipsis}}


Note that {lisp DECLARE} declarations do not {it create} bindings, but merely provide declarations for existing bindings.  For this reason, an initial value cannot be specified and the form of the declaration is the same as that of {lisp DLAMBDA}s, namely {lisp ({arg NAME} {arg TYPE} . {arg EXTRAS})}.

Note that variables bound {it outside} of the scope of the iterative statement, i.e. a variable used freely in the i.s, can also be declared using this construction. Such a declaration will only be in effect for the scope of the iterative statement.

}{End SubSec Declarations in Iterative Statements}



{Begin SubSec Declaring a Variable for a Restricted Lexical Scope}
{Title Declaring a Variable for a Restricted Lexical Scope}
{Text


The Decl package also permits declaring the type of a variable over some restricted portion of its existence.  For example, suppose the variable {lisp X} is either a fixed or floating number, and a program branches to treat the two cases separately.  On one path {lisp X} is known to be fixed, whereas on the other it is known to be floating.  The Decl package {fn DPROGN}{index DPROGN Fn} construct can be used in such cases to state the type of the variable along each path.  {fn DPROGN} is exactly like {fn PROGN}, except that the second element of the form is interpreted as a list of {lisp DLAMBDA} format declarations.  These declarations are added to any existing declarations in the containing scope, and the composite declaration (created using the {lisp ALLOF} type expression, {PageRef (Decl Type Expression) ALLOF}) is considered to hold throughout the lexical scope created by the {fn DPROGN}.  Thus, our example becomes:

{lispcode
(if (FIXP X)
  then (DPROGN ((X FIXP)) {ellipsis})
  else (DPROGN ((X FLOATP)) {ellipsis}))}


Like {fn DPROG} and {lisp DLAMBDA}, the value of a {fn DPROGN} may also be declared, using the pseudo-variable {lisp RETURNS}.{index RETURNS (in Decl package)}


{fn DPROGN} may be used not only to restrict the declarations of local variables, but also to declare variables which are being used freely.  For example, if the variable {lisp A} is used freely inside a function but is known to be {fn FIXP},  this fact could be noted by enclosing the body of the function in {lisp (DPROGN ((A FIXP FREE)) {arg BODY})}.{index FREE (in Decl package)}  Instead of {lisp FREE}, the more specific construction {lisp (BOUNDIN {arg FUNCTION{sub 1}} {arg FUNCTION{sub 2}} {ellipsis})} can be used.{index BOUNDIN (in Decl package)}  This not only states that the variable is used freely but also gives the names of the functions which might have provided this binding.{foot
Like {lisp USEDIN}{index USEDIN (in Decl package)} declarations, {lisp FREE} and {lisp BOUNDIN} declarations cannot be checked, and are provided for documentation purposes only.
}{comment endfootnote}


Since the  {fn DPROGN} form introduces another level of parenthesization, which results in the enclosed forms being prettyprinted indented, the Decl package also permits such declarations to be attached to their enclosing {lisp DLAMBDA} or {fn DPROG} scopes by placing a {lisp DECL}{index DECL (in Decl package)} expression, e.g. {lisp (DECL (A FIXP (BOUNDIN FUM))}, before the first executable form in that scope.  Like {fn DPROGN}'s, {lisp DECL} declarations use {lisp DLAMBDA} format.

}{End SubSec Declaring a Variable for a Restricted Lexical Scope}



{Begin SubSec Declaring the Values of Expressions}
{Title Declaring the Values of Expressions}
{Text

The Decl package allows the value  of an arbitrary form to be declared with   the Decl construct {lisp THE}{index THE (in Decl package)}.   A {lisp THE} expression is of the form {lisp (THE {arg TYPE} . {arg FORMS})}, e.g. {lisp (THE FIXP (FOO X))}.   {arg FORMS} are evaluated in order, and the value of the {it last} one is checked to see if it satisfies {arg TYPE}, a type name or type expression. If so, its value is returned, otherwise a declaration fault occurs.

}{End SubSec Declaring the Values of Expressions}




{Begin SubSec Assertions}
{Title Assertions}
{Text


The Decl package also allows for checking that an arbitrary predicate holds at a particular point in a program's execution, e.g. a condition that must hold at function entry but not throughout its execution.  Such predicates can be checked using an expression of the form
{lisp (ASSERT {arg FORM{sub 1}} {arg FORM{sub 2}} {ellipsis})},{index ASSERT (in Decl package)} in which each {arg FORM{sub i}} is either a list (which will be evaluated) or a variable (whose declaration will be checked).  Unless all elements of the {lisp ASSERT} form are satisfied, a declaration fault will take place.


{lisp ASSERT}ing a variable provides a convenient way of verifying that the value of the variable has not been improperly changed by a lower function. Although a similar effect could be achieved for predicates by explicit checks of the form {lisp (OR {arg PREDICATE} (SHOULDNT))}, {lisp ASSERT} also provides the ability both to check that a variable's declaration is currently satisfied and to remove its checks at compile time without source code modification (see {PageRef Var COMPILEIGNOREDECL}).

}{End SubSec Assertions}




{Begin SubSec Using Type Expressions as Predicates}
{Title Using Type Expressions as Predicates}
{Text

{index TYPE? (Record Operator)}

The Decl package extends the Record package {lisp TYPE?} construct so that it accepts decltypes, as well as record names, e.g. {lisp (TYPE? (FIXP (SATISFIES (ILESSP VALUE 0))) {arg EXPR})}.  Thus, a {lisp TYPE?} expression is exactly the same as a {lisp THE} expression except that, rather than causing a declaration fault, {lisp TYPE?} is a predicate which determines whether or not the value satisfies the given type.   

}{End SubSec Using Type Expressions as Predicates}



{Begin SubSec Enforcement}
{Title Enforcement}
{Text

The Decl package is a "soft" typing system - that is, the data objects themselves are not inherently typed.  Consequently, declarations can only be enforced within the lexical scope in which the declaration takes place, and then only in certain contexts.  In general, changes to a variable's value such as those resulting from side effects to embedded structure (e.g., {fn RPLACA}, {fn SETN}, etc.) or free variable references from outside the scope of the declaration cannot be, and therefore are not, enforced.


Declarations {it are} enforced i.e. checked, in three different situations: when a declared variable is bound to some value or rebound with {fn SETQ} or {fn SETQQ}, when a declared expression is evaluated, and when an {lisp ASSERT} expression is evaluated.  In a binding context, the type check takes place {it after} the binding, including any user-defined behavior specified by the type's binding function.  Any failure of the declarations causes a break to occur and an informative message to be printed.  In that break, the name to which the declaration is attached (or {arg VALUE} if no name is available) will be bound to the offending value.  Thus, in the {lisp (FACT T)} example above, {lisp N} would be bound to {lisp T}.   The problem can be repaired either by returning an acceptable value from the break via the {lisp RETURN} command, or by assigning an acceptable value to the offending name and returning from the break via an {lisp OK} or {lisp GO} command.  The unsatisfied declaration will be reasserted when the computation is continued, so an unacceptable value will be detected.{foot
With this exception, assignments to variables from within the break are not considered to be in the scope of the declarations that were in effect when the break took place, and so are not checked.
}{comment endfootnote}


The automatic enforcement of type declarations is a very flexible and powerful aid to program development.  It does, however, exact a considerable run-time cost because of all the checking involved.  Factors of two to ten in running speed are not uncommon, especially where low level, frequently used functions employ type declarations.  As a result, it is usually desirable to remove the declaration enforcement code when the system is believed to be bug-free and performance becomes more central.  This can be done with the variable {var COMPILEIGNOREDECL}:

{VarDef {Name COMPILEIGNOREDECL}
{Text
Setting the value of the variable {var COMPILEIGNOREDECL} to {lisp T} (initially {lisp NIL}) instructs the compiler not to insert declaration enforcement tests in the compiled code.  More selective removal can be achieved by setting {var COMPILEIGNOREDECL} to a list of function names.  Any function whose name is found on this list is compiled without declaration enforcement.
}}


{Def {Type FileCom}  {Name IGNOREDECL}  {Args {lisp .} VAL}
{Text
Declaration enforcement may be suppressed selectively by file using the {filecom IGNOREDECL} file package command.  If this appears in a file's file commands, it redefines the value of {var COMPILEIGNOREDECL} to {arg VAL} for the compilation of this file only.  
}}


}{End SubSec Enforcement}




{Begin SubSec Decltypes}
{Title Decltypes}
{Text


A Decl package type, or decltype, specifies a subset of data values to which values of this type are restricted.  For example, a "positive number" type might be defined to include only those values that are numbers and greater than zero.  A type may also specify how certain operations, such as assignment or binding (see {PageRef Tag BINDFN}), are to be performed on variables declared to be of this type.


The inclusion relations among the sets of values which satisfy the different  types define a natural partial ordering on types, bound by the universal type {lisp ANY}{index *PRIMARY* ANY (in Decl package)} (which all values satisfy) and the empty type {lisp NONE}{index *PRIMARY* NONE (in Decl package)} (which no value satisfies).  Each type has one or more {it supertypes}{index supertypes (in Decl package)} (each type has at least {lisp ANY} as a supertype) and one or more {it subtypes}{index subtypes (in Decl package)} (each type has at least {lisp NONE} as a subtype).  This structure is important to the user of Decl as it provides the framework in which new types are defined.  Typically, much of the definition of a new type is defaulted, rather than specified explicitly.  The definition will be completed by inheriting atttributes which are shared by all its immediate supertypes. 


An initial set of decltypes which defines the Interlisp built-in datatypes and a few other commonly used types is provided.  Thereafter, new decltypes are created in terms of existing ones using the type expressions described below.  For conciseness, such new types can be associated with literal atoms using the function {fn DECLTYPE} ({PageRef Fn DECLTYPE}). 

}{End SubSec Decltypes}



{Begin SubSec Predefined Types}
{Title Predefined Types}
{Text


Some commonly used  types, such as the Interlisp built-in data types, are already defined when the Decl package is loaded.  These types, indented to show subtype-supertype relations, are:

{note this WILL have to be redone}


{lispcode
ANY
  ATOM            LST{foot
{lisp LST} is defined as either {lisp LISTP} or {lisp NIL}, i.e. a list or {lisp NIL}.  The name {lisp LST} is used, because the name {lisp LIST} is treated specially by  clisp.
}{comment endfootnote}       ARRAYP      STRINGP    FUNCTION    STACKP 
    LITATOM         ALIST{foot {lisp ALIST} is defined as either {lisp NIL}, or a list of elements each of which is of type {lisp LISTP}.
}{comment endfootnote}     HARRAYP 
      NIL           LISTP       READTABLEP
    NUMBERP
      FIXP
        LARGEP
        SMALLP
      FLOATP

                                     NONE
}



Note that the definition of {lisp LST} causes {lisp NIL} to have multiple supertypes, i.e. {lisp LITATOM} and {lisp LST}, reflecting the duality of {lisp NIL} as an atom and a (degenerate) list.  


In addition, declarations made using the Record package ({PageRef Tag RecordPackage}) also define types which are attached as subtypes to an appropriate existing type (e.g., a {lisp TYPERECORD} declaration defines a subtype of {lisp LISTP}, a {lisp DATATYPE} declaration a subtype of {lisp ANY}, etc.) and may be used directly in declaration contexts.

}{End SubSec Predefined Types}



{Begin SubSec Type Expressions}
{Title Type Expressions}
{Text


Type expressions provide convenient ways for defining new types in terms of modifications to, or compositions of one or more, existing types. 


{Def {Type (Decl Type Expression)}
{Name MEMQ} {Args VALUE{sub 1} {ellipsis} VALUE{sub N}}
{Text
Specifies a type whose values can be any one of the fixed set of elements
{lisp {bracket {arg VALUE{sub 1}} {ellipsis} {arg VALUE{sub N}}}}.
For example, the status of a device might be represented by a datum restricted to the values {lisp BUSY} and {lisp FREE}.  Such a "device status" type could be defined via  {lisp (MEMQ BUSY FREE)}.  The new type will be a subtype of the narrowest type which all of the alternatives satisfy (e.g., the "device status" type would be a subtype of {lisp LITATOM}).  The membership test uses {fn EQ} if this supertype is {lisp LITATOM}; {fn EQUAL} otherwise.  Thus, lists, floating point numbers, etc., can be included in the set of alternatives.
}}


{Def {Type (Decl Type Expression)}
{Name ONEOF} {Args TYPE{sub 1} {ellipsis} TYPE{sub N}}
{Text
Specifies a type which is the union of two or more other types.  For example, the notion of a possibly degenerate list is something that is either {lisp LISTP} or {lisp NIL}.  Such a type can be (and the built-in type {lisp LST} in fact is) defined simply as {lisp (ONEOF NIL LISTP)}.  A union data type becomes a supertype of all of the alternative types specified in the {lisp ONEOF} expression, and a subtype of their lowest common supertype.  The type properties of a union type are taken from its alternative types if they all agree, otherwise from the supertype.
}}


{Def {Type (Decl Type Expression)}
{Name ALLOF} {Args TYPE{sub 1} {ellipsis} TYPE{sub N}}
{Text
Specifies a type which is the intersection of two or more other types.  For example, a variable may be required to satisfy both {lisp FIXP} and also some type which is defined as {lisp (NUMBERP (SATISFIES {arg PREDICATE}))}.
The latter type will admit numbers that are not {lisp FIXP}, i.e. floating point numbers; the former does not include {arg PREDICATE}.  Both restrictions can be obtained by using the type {lisp (ALLOF (NUMBERP (SATISFIES {arg PREDICATE})) FIXP)}.{foot
When a value is tested, the component type tests are applied from left to right.
}{comment endfootnote}
}}


{Def {Type (Decl Type Expression)}
{Name OF} {PrintName ({arg AGGREGATE} OF {arg ELEMENT})}
{Text
Specifies{Tag DECLaggregate} a type which is an aggregate of values of some other type (e.g., list of numbers, array of strings, etc.).  {arg AGGREGATE} must be a type which provides an {lisp EVERYFN} property ({PageRef Tag EVERYFN}).  The {lisp EVERYFN} is used to apply an arbitrary function to each of the elements of a datum of the aggregate type, and check whether the result is non-{lisp NIL} for  each element.  {arg ELEMENT} may be any type expression.  For example, the type "list of either strings or atoms" can be defined as {lisp (LISTP OF (ONEOF STRINGP ATOM))}.  The type test for the new type will consist of applying the type test for {arg ELEMENT} to each element of the aggregate type using the {lisp EVERYFN} property.  The new type will be a subtype of its aggregate type.{foot
The built-in aggregate types are {lisp ARRAYP}, {lisp LISTP}, {lisp LST}, and {lisp STRINGP} (and their subtypes).
}{comment endfootnote}
}}


{Def {Type (Decl Type Expression)}
{Name SATISFIES} {PrintName ({arg TYPE} (SATISFIES {arg FORM{sub 1}} {ellipsis} {arg FORM{sub N}}))}
{Text
Specifies a type whose values are a subset of the values of an existing type.  The type test for the new type will first check that the base type is satisfied, i.e. that the object is a member of {arg TYPE}, and then  evaluate {arg FORM{sub 1}} {ellipsis} {arg FORM{sub N}}.  If each form returns a non-{lisp NIL} value, the type is satisfied.  

The value that is being tested may be referred to in {arg FORM{sub 1}} {ellipsis} {arg FORM{sub N}} by either (a) the variable name if the type expression appears in a binding context such as {lisp DLAMBDA} or {fn DPROG} (b) the distinguished atom {lisp ELT} for a {lisp SATISFIES} clause on the elements of an aggregate type, or (c) the distinguished atom {lisp VALUE}, when the type expression is used in a context where no name is available (e.g., a {lisp RETURNS} declaration).  For example, one might declare the program variable {lisp A} to be a negative integer via
{lisp (FIXP (SATISFIES (MINUSP A)))},
or declare the value of a {lisp DLAMBDA} to be of type
{lisp ((ONEOF FIXP FLOATP) (SATISFIES (GREATERP VALUE 25)))}.
Note that more than one {lisp SATISFIES} clauses may appear in a single type expression attached to different alternatives in a {lisp ONEOF} type expression, or attached to both the elements and the overall structure of an aggregate.
For example,

{lispcode
[LISTP OF [FIXP (SATISFIES (ILEQ ELT (CAR VALUE]
          (SATISFIES (ILESSP (LENGTH VALUE) 7]}

specifies a list of less than 7 integers each of which is no greater than the first element of the list.
}}


{Def {Type (Decl Type Expression)}
{Name SHARED} {Args TYPE}
{Text
Specifies{Tag DECLshared} a subtype of {arg TYPE} with default binding behavior, i.e. the binding function (see {PageRef Tag BINDFN}), if any, will be suppressed.{foot
As no predefined type has a binding function, this is of no concern until the user defines or redefines a type to have a binding function.
}{comment endfootnote}
For example, if the type {lisp FLOATP} were redefined so that {lisp DLAMBDA} and {fn DPROG} bindings of variables that were declared to be {lisp FLOATP} copied their initial values (e.g., to allow {fn SETN}s to be free of side effects), then variables declared {lisp (SHARED FLOATP)} would be initialized in the normal fashion, without copying  their initial values.
}}



}{End SubSec Type Expressions}




{Begin SubSec Named Types}
{Title Named Types}
{Text

{Tag DELCTYPE}
{Tag DECLTYPE}

Although type expressions can be used in any declaration context, it is often desirable to save the definition of a new type if it is to be used frequently, or if a more complex specification of its behavior is to be given than is convenient in an expression.  The ability to define a named type is provided by the function  {fn DECLTYPE}.



{FnDef {FnName DECLTYPE} {FnArgs TYPENAME TYPE PROP{SUB 1} VAL{SUB 1} {ellipsis} PROP{SUB N} VAL{SUB N}}
{Type NLAMBDA NOSPREAD}
{Text
Nlambda, nospread function.   {arg TYPENAME} is a literal atom, {arg TYPE} is either the name of an existing type or a type expression, and {arg PROP{sub 1}}, {arg VAL{sub 1}}, {ellipsis}, {arg PROP{sub N}}, {arg VAL{sub N}} is a specification (in property list format) of other attributes of the type.  {fn DECLTYPE} derives a type from {arg TYPE}, associates it with {arg TYPENAME}, and then defines any properties specified with the values given.
}}


The following properties are interpreted by the Decl package.{foot
Actually, any property can be attached to a type, and will be available for use by user functions via the function {fn GETDECLTYPEPROP}, described below.
}{comment endfootnote}
Each of these properties can have as its value either a function name or a {lisp LAMBDA} expression.  


{Begin LabeledList properties interpreted by the Decl package}

{Label {lisp TESTFN}}
{Item
will be used by the Decl package to test whether a given value satisfies this type.  The type is considered satisfied if {arg FN} applied to the item is non-{lisp NIL}.  For example, one might define the type {lisp INTEGER} with {lisp TESTFN} {fn FIXP}.{foot
Typically, the {lisp TESTFN} for a type is derived from its type expression, rather than specified explicitly.  The ability to specify the {lisp TESTFN} is provided for those cases where a predicate is available that is much more efficient than that which would be derived from the type expression.  For example, the type {lisp SMALLP} is defined to have the function {fn SMALLP} as its {lisp TESTFN}, rather than {lisp (LAMBDA (DATUM) (AND (NUMBERP DATUM) (FIXP DATUM) (SMALLP DATUM)))} as would be derived from the subtype structure.
}{comment endfootnote}
}


{Label {lisp EVERYFN}}
{Item
{Tag EVERYFN}specifies a mapping function which can apply a functional argument to each "element" of an instance of this type, and which will  return {lisp NIL} unless the result of every such application was non-{lisp NIL}.  {arg FN} must be a function of two arguments: the aggregate and the function to be applied.  For example, the {lisp EVERYFN} for the built-in type {lisp LISTP} is {fn EVERY}.  As described on {PageRef Tag DECLaggregate}, the Decl package uses the {lisp EVERYFN} property of the aggregate type to construct a type test for aggregate type expressions.  In fact, it is the presence of an {lisp EVERYFN} property which allows a type to be used as an aggregate type.{foot
Note that a type's {lisp EVERYFN} is {it not} used in type tests for that type, but only in type tests for types defined by {lisp OF} expressions which used this type as the aggregate type.  For example, {fn EVERY} is not used in determining whether some value satisfies the type {lisp LISTP}.
}{foot
The Decl package never applies the {lisp EVERYFN} of a type to a value without first verifying that the value satisfies that type.
}{comment endfootnote}
}


{Label {lisp BINDFN}}
{Item
{Tag BINDFN}is used to compute from the initial value supplied for a {lisp DLAMBDA} or {fn DPROG} variable of this type, the value to which the variable will actually be initialized.   {arg FN} must be a function of one argument which will be applied to the initial value,{foot
For a {fn DPROG} binding, {arg FN} will be applied to no arguments if the initial value is lexically {lisp NIL}.
}{comment endfootnote}
and which should produce another value which is to be used to make the binding.  For example, a {lisp BINDFN} could be used to bind variables of some type so that new bindings are copies of the initial value.  Thus, if {lisp FLOATP} were given the {lisp BINDFN} {fn FPLUS}, any variable declared {lisp FLOATP} would be initialized with a new floating box, rather than sharing with that of the original initial value.{foot
The {lisp BINDFN}, if any, associated with a type may be suppressed in a declaration context by creating a subtype with the type expression operator {lisp SHARED}, as described on {PageRef Tag DECLshared}.
}{comment endfootnote}
}


{Label {lisp SETFN}}
{Item
is used for performing  a {fn SETQ} or {fn SETQQ} of  variables of this type.  {arg FN} is a function of two arguments, the name of the variable, and its new value.  A {lisp SETFN} is typically used to avoid the allocation of storage for intermediate results.  Note that the {lisp SETFN} is {it not} the mechanism for the enforcement of type compatibility, which is checked {it after} the assignment has taken place.  Also note that not all functions which can change values are affected: in particular, {fn SET} and {fn SETN} are not.
}

{End LabeledList properties interpreted by the Decl package}



{Begin SubSec Manipulating Named Types}
{Title Manipulating Named Types}
{Text

{lisp DECLTYPES} is a file package type ({PageRef Tag FilePkg}).  Thus all of the operations relating to file package types, e.g. {fn GETDEF}, {fn PUTDEF}, {fn EDITDEF}, {fn DELDEF},{foot
Deleting a named type could possibly invalidate other type definitions that have the named type as a subtype or supertype.  Consequently, the deleted type is simply unnamed and left in the type space as long as it is needed.
}{comment endfootnote}
{fn SHOWDEF}, etc., can be performed on decltypes.


The file package command, {filecom DECLTYPES}{index DECLTYPES FileCom}, is provided to dump named decltypes symbolically.  They will be written as a series of {fn DECLTYPE} forms which will specify only those fields which differ from the corresponding field of their supertype(s).  If the type depends on any unnamed types, those types will be dumped (as a compound type expression), continuing up the supertype chain until a named type is found.  Care should be exercised to ensure that enough of the named type context is dumped to allow the type definition to remain meaningful.  


The functions {fn GETDECLTYPEPROP}{index GETDECLTYPEPROP FN} and {fn SETDECLTYPEPROP}{index SETDECLTYPEPROP FN}, defined analogously to the property list functions for atoms, allow the manipulation of the properties of named types.  Setting  a property to {lisp NIL} with {fn SETDECLTYPEPROP} removes it from the type.

}{End SubSec Manipulating Named Types}

}{End SubSec Named Types}





{Begin SubSec Relations Between Types}
{Title Relations Between Types}
{Text


The notion of equivalence of two types is not well defined.  However, type equivalence is rarely of interest.  What is of interest is type {it inclusion}, i.e. whether one type is a supertype or subtype of another.  The predicate {fn COVERS} can be used to determine whether the values of one type include those of another.



{FnDef {FnName COVERS} {FnArgs HI LO}
{Text
{Tag COVERS}is {lisp T} if {arg HI} can be found on some (possibly empty) supertype chain of {arg LO}; else {lisp NIL}.  Thus, {lisp (COVERS 'FIXP (DECLOF 4))}={lisp T}, even though the {fn DECLTYPE} of 4 is {lisp SMALLP}, not {lisp FIXP}.  The extremal cases are the obvious identities:
{lisp (COVERS 'ANY {arg ANYTYPE})} = {lisp (COVERS {arg ANYTYPE} 'NONE)} = {lisp (COVERS {arg X} {arg X})} for any type {arg X} = {lisp T}.
}}


{fn COVERS} allows declaration based transformations of a form which depend on elements of the form being of a certain type to express their applicability conditions in terms of the weakest type to which they apply, without explicit concern for other types which may be  subtypes of it.  For example, if a particular transformation is to be applied whenever an element is of type {lisp NUMBERP}, the program which applies that transformation does not have to check whether the element is of type {lisp SMALLP}, {lisp LARGEP}, {lisp FIXP}, {lisp FLOATP}, etc., but can simply ask whether {lisp NUMBERP} {fn COVERS} the type of that element.


The elementary relations among the types, out of which arbitrary traversals of the type space can be constructed, are made available via:




{FnDef {FnName SUBTYPES} {FnArgs TYPE}
{Text
Returns the list of types which are {it immediate} subtypes of {arg TYPE}.
}}



{FnDef {FnName SUPERTYPES} {FnArgs TYPE}
{Text
{Tag SUPERTYPES}Returns the list of types which are {it immediate} supertypes of {arg TYPE}.
}}

}{End SubSec Relations Between Types}



{Begin SubSec The Declaration Database}
{Title The Declaration Database}
{Text


One of the primary uses of type declarations is to provide information that other systems can use to interpret or optimize code.  For example, one might choose to write all arithmetic operations in terms of general functions like {fn PLUS} and {fn TIMES} and then use variable declarations to substitute more efficient, special purpose code at compile time based on the types of the operands.  To this end, a data base of declarations is made available by the Decl package to support these operations.  



{FnDef {FnName DECLOF} {FnArgs FORM}
{Text
Returns the type of {arg FORM} in the current declaration context.{foot
The "current declaration context"{index current declaration context} is defined by the environment at the time that {fn DECLOF} is called.  Code reading systems, such as the compiler and the interpreter, keep track of the lexical scope within which they are currently operating, in particular, which declarations are currently in effect.  Note that (currently) {fn DECLOF} does {it not} have access to any global data base of declarations.  For example, {fn DECLOF} does not have information available about the types of the arguments of,  or the value returned by, a particular function, unless it is currently "inside" of that function.  However, the {lisp DECLOF} property (described below) can be used to inform {fn DECLOF} of the type of the value returned by a particular function.
}{comment endfootnote}
If {arg FORM} is an atom, {fn DECLOF} will look up that atom directly in its database of current declarations.  Otherwise, {fn DECLOF} will look on the property list of {lisp (CAR {arg FORM})} for a {prop DECLOF}{index DECLOF Prop} property, as described below.  If there is no {prop DECLOF} property, {fn DECLOF} will check if {lisp (CAR {arg FORM})} is one of a large set of functions of known result type (e.g., the arithmetic functions).  Failing that, if {lisp (CAR {arg FORM})} has a {prop MACRO} property, {fn DECLOF} will apply itself to the result of expanding
(with {fn EXPANDMACRO}, {PageRef Fn EXPANDMACRO})
the macro definition.  Finally, if {arg FORM} is a Lisp program element that {fn DECLOF} "understands" (e.g., a {fn COND}, {fn PROG}, {fn SELECTQ}, etc.), {fn DECLOF} applies itself recursively to the part(s) of the contained form which will be returned as value.  
}}


{PropDef {Name DECLOF}
{Text
{index *PRIMARY* DECLOF Prop}Allows the specification of the type of the values returned by a particular function.  The value of the {lisp DECLOF} property can be either a type, i.e. a type name or a type expression, or a list of the form {lisp (FUNCTION {arg FN})}, where {arg FN} is a function object.  {arg FN}  will be applied (by {fn DECLOF}) to the form whose {fn CAR} has this {prop DECLOF} property on its property list.  The value of this function application will then be considered to be the type of the form.
}}



As an example of how declarations can be used to automatically generate more efficient code, consider an arithmetic package.  Declarations of numeric variables could be used to guide code generation to avoid the inefficiencies of Interlisp's handling of arithmetic values.  Not only could the generic arithmetic functions be automatically specialized, as suggested above, but by redefining the {lisp BINDFN} and the {lisp SETFN} properties for the types {lisp FLOATP} and {lisp LARGEP} to re-use storage in the appropriate contexts (i.e., when the new value can be determined to be of the appropriate type), tremendous economies could be realized by not allocating storage to intermediate results which must later be reclaimed by the garbage collector.  The Decl package has been used as the basis for several such code optimizing systems.

}{End SubSec The Declaration Database}





{Begin SubSec Declarations and Masterscope}
{Title Declarations and Masterscope}
{Text

The Decl package notifies {fn MASTERSCOPE} about type declarations and defines a new {fn MASTERSCOPE} relation, {lisp TYPE},  which depends on declarations.{index TYPE (Masterscope relation)} Thus, the user can ask questions such as "{lisp WHO USES  MUMBLE AS A TYPE?}," "{lisp DOES FOO USE FIXP AS A TYPE?}," and so on.

}{End SubSec Declarations and Masterscope}



{index *END* Decl package}
{index *END* type declarations}

}{End SubSec The Decl Package}