CHAPTER 21 A BRIEF VISIT WITH ICL 21.1 Overview Of Presentation We will expore our model language ICL by starting with EXPRs. We divide EXPR notations into two packages. First, we will present EXPR notations that are good no matter what types of EXPRs may be involved. These are called ~general ~EXPR ~forms. At the end, we introduce more EXPR notations which are specific to certain types of data, such as the "{...}" notation just seen at the end of the previous chapter. Between the first and last presentation of EXPRs, we explore STATEMENTs, QUANTIFIERs, and DECLARATIONs. Chapter 22 explores in more detail the general EXPR forms and these other parts-of-speech. Chapter 23 explores in more detail the final part of this chapter, the second package of EXPRs, known as the type-specific EXPR forms. We will present each rule that forms a new TYPEX, a type constructor, together with a corresponding set of EXPR notations that form and examine new ~instances of the new type. This chapter is a relatively brief overview of ICL. 21.2 A Briefer Notation For Rules Of Grammar For ease of reading and learning, we will adopt an abbreviated notation for rules of grammar. We will drop the angle brackets ("<...>") that surround non-terminal parts-of-speech. We will distinguish non-terminals now by writing them in uppercase. Thus, where we have written: <EXPR> <BOP> <EXPR> -> EXPR we will now write instead: EXPR BOP EXPR -> EXPR All other occurences of names, which are terminal parts-of-speech, are shown in lower case. Thus, where we use to write: WHILE <EXPR> ; -> <QUANTIFIER> we will now write: while EXPR ; -> QUANTIFIER 21.2.1 Types In EXPRs Each EXPR in ICL has a ~type associated with it. We will use uppercase italics to denote types in rules. For example, we might introduce a rule like: ~POINT . x -> ~REAL This says that an instance of type ~POINT followed by ".X" is a ~REAL. (This notation selects the x-coordinate from a ~POINT). In the implementation, this rule appears as a syntax rule ~and as a datatype rule. The datatype rule: ~POINT . x -> ~REAL looks like the syntax rule: EXPR . ID -> EXPR Any type (in uppercase italics) really means EXPR in the syntax domain. Chapter 24 shows that in the implementation, after syntax processing, the semantic action is to generate new phrases in the ~datatype grammar, a grammar distinct from the syntax grammar. There, the parts-of-speech denote types. This second level processing of phrases resolves all datatype concerns. For convenience, here we don't show the datatype rules explicitly, rather, we cast them in terms of familiar syntax rules, whose semantics the datatype rules implement. For another example, we might say that the declaration: TYPE REALS = { REAL } ; ~introduces the following datatype rules: { ~REAL ; ~REAL ; ... ; ~REAL } -> ~REALS ~REALS [ ~INTEGER ] -> ~REAL What we mean is that there are the syntax rules: { EXPR ; EXPR ; ... ; EXPR } -> EXPR and EXPR [ EXPR ] -> EXPR and that the datatype rules, when projected up into these syntax rules, appear as shown. (Section 23.3 introduces these notations officially). The datatype rules impart more information. 21.3 IDentifiers (Names) And Comments In ICL, And "$E" In ICL, any name, also called ~identifier, or ~ID for short, consists of the following characters: Letters: A-Z Digits: 0-9 Underscore: _ IDs however must ~begin with a letter, A thru Z. Upper and lower case are ~not distinguished, and so the following all denote the same name: HELLO_JILL Hello_Jill hellO_jILl ~Comments are text within program specifications that are very helpful for human readers of a program, although the computer ignores them entirely. Comments in ICL begin and end with the double-quote character ("), as in: " This is a comment " or "This comment spans two lines." We use the character epsilon "$E" in some places. To type it into the computer, write "$E" (dollar E). 21.4 A Brief Look At ICL We begin with EXPRs that are meaningful no matter what the EXPR's type is. 21.4.1 General EXPR Forms We begin with the most popular rule in programming languages. 21.4.1.1 Operators The rule: EXPR BOP EXPR -> EXPR supports the popular infix notation for forming EXPRs with binary operators (BOPs) between them. Two example BOPs are: + -> BOP and * -> BOP They support addition and multiplication. We will see in chapter 22 the ~types of data dealt with by each BOP, such as the types INTeger and REAL which are meaningful for these two BOPs. You can even specify a function call as a BOP, via: \ ID -> BOP For example, the notation: polygon \PAINTED red \ROTATED_BY 90 means the same as: ROTATED_BY( PAINTED( polygon, red ) , 90 ) Emmense clarity can be achieved by using this ~infix, or BOP notation for calling functions. EXPRs can be formed with a minus sign preceding another EXPR. This ~unary ~minus, "-", appears in the EXPRs "-1" and "-(A+B)". This minus notation is supported by the two rules: UOP EXPR -> EXPR and - -> UOP ICL provides an alternative notation for specifying some other unary operators. Some unary operators, called ~righthand ~unary ~operators (RHUOP), appear to the right of their inputs, as supported by the rule: EXPR RHUOP -> EXPR Finally, EXPRs may be enclosed in parentheses to specify which operators must occur before other operators: ( EXPR ) -> EXPR 21.4.1.2 Cummulative Application Of BOPs You may apply any BOP so as to operate over a ~set of values, not merely two values. Where you might wish to write: EXPR(1) + EXPR(2) + ... + EXPR(n) you can write instead: + EXPR(k) QUANTIFIER ---------------- Parentheses in previous paragraph mean subscripting! --- The QUANTIFIER produces, say, N iterations. For each of those iterations, the EXPR sitting between the "+" and the QUANTIFIER is re-evaluated. This produces N (different) values, which we have denoted as EXPR(K) for K from 1 to N. This overall notation forms the sum ("+") over those N values. ---------------- Parentheses in previous paragraph around "K" ---------------- mean subscripting! ------------------------------------ The general rule of grammar works for any BOP: BOP EXPR QUANTIFIER -> EXPR For example: * I FOR I FROM 1 TO 10; denotes the product: 1 * 2 * 3 * ... * 10 21.4.1.3 Getting Side-Effects Into An EXPR You may wish to assign intermediate values into variables before you are ready to deliver a value. For example, you might like to deliver: R * R + R where R is: 2 * X + 1 We write this EXPR as: DO R:= 2*X+1; GIVE R*R+R The DO-clause is a STATEMENT, and it is executed first. In this example, it assigns a value into R. The GIVE-clause is then executed, which in our example reads R. The GIVE-clause is an EXPR, and the GIVE-clause's value becomes the value for the overall DO-GIVE. This notation is supported by the rule: do STATEMENT give EXPR -> EXPR 21.4.1.4 Local Variables For EXPRs You may require some extra variables for a computation. Our previous example used the extra variable, R, to aid in the computation. The BEGIN-END rule exists to associated new variable DECLARATIONs with an EXPR: begin DECLARATION EXPR end -> EXPR The variables introduced by the DECLARATION are available only within the EXPR inside the BEGIN...END. They are called ~local variables. Outside of this BEGIN...END, the new variables cease to exist. For example, our previous example involving R is most completely specified as: BEGIN VAR R = REAL; DO R:= 2*X+1; GIVE R*R+R END The variable R exists only here, inside the BEGIN...END. There exists a similar notation for STATEMENTs (Section 21.4.2.4). 21.4.1.5 Decision Forms For EXPRs. We include at least the following IF-THEN-ELSE notation: if EXPR then EXPR else EXPR fi -> EXPR so as to decide between the then-EXPR and the else-EXPR. The if-EXPR, if TRUE, causes the then-EXPR to be the overall value, while a FALSE chooses the else-EXPR instead. More complex IF constructs exist, as well as a construct that chooses one of N possible EXPRs, based on a given integer between 1 and N, (Sections 22.1.7 and 22.2.3). 21.4.1.6 Minimizing And Maximizing EXPRs Since it is relatively easy to introduce new syntaxes into a language, we've chosen to include the following useful notation. Given a set of objects, you may wish to pick the object which ~minimizes some EXPR. For example: pick APPLE minimizing PRICE(APPLE) FOR each APPLE in a set The result is an apple, the pick-EXPR. That apple makes the EXPR PRICE(APPLE) take on a minimal value. Each apple is taken from a set (via the FOR-notation). This notation is supported by the rule: pick EXPR minimizing EXPR QUANTIFIER -> EXPR The QUANTIFIER causes iterations, and for each iteration, the minimizing-EXPR is computed. On that iteration for which this EXPR yielded the smallest value, the pick-EXPR is evaluated. The result of the pick-EXPR is the overall value for this notation. 21.4.1.7 Universal And Existential Quantification Sometimes, you want to know if something is true for ~all elements in a set. For example, are all values in a set positive? You check if a given value, say R, is positive via: R > 0 You find out if all elements in a set are positive by writing: ALWAYS R > 0 FOR R in the given set This overall EXPR is TRUE if all R's are positive, and FALSE otherwise. This example is supported by the rule: always EXPR QUANTIFER -> EXPR It yields TRUE when the EXPR yields the value TRUE on all iterations caused by the QUANTIFIER. A variation on this rule: there_is EXPR QUANTIFIER -> EXPR yields TRUE if at least one of the values delivered by the EXPR is TRUE. Once again, the EXPR is re-evaluated for each iteration caused by the QUANTIFER, until the EXPR yields TRUE. These constructs usually occur as the if-EXPR in IF-THEN-ELSEs, as in: IF ALWAYS R > 0 FOR R in a given set THEN WRITE('All are positive.'); ELSE WRITE(R); WRITE(' is a non-positive element.'); FI The QUANTIFIER in all cases causes iterations only until the condition becomes known. 21.4.1.8 Objective Modification As discussed in Chapter 10, the rule: @ ( EXPR ) -> EXPR is valid on the lefthand sides of assignment statements. 21.4.1.9 Some Example Functions To illustrate some of these constructs, we enclose them in complete function definitions. (Function definitions themselves are introduced in Section 21.4.4). Here are two independent renditions of FACTORIAL, which means the ~product of all integers between 1 and a given N: DEFINE FACTORIAL( N:INT ) = INT: IF N > 1 THEN N * FACTORIAL( N-1 ) ELSE 1 FI ENDDEFN or: DEFINE FACTORIAL( N:INT ) = INT: BEGIN VAR K=INT; * K FOR K FROM 1 TO N; END ENDDEFN The first rendition uses the IF-THEN-ELSE construct and the second uses the BEGIN-END and the BOP-EXPR-QUANTIFIER rules. The ~minimum over a set of REALs is delivered by the following function, which also uses the BOP-EXPR-QUANTIFIER rule: DEFINE MINIMUM( RS:REALS ) = REAL: BEGIN VAR R=REAL; MIN R FOR R $E RS; END ENDDEFN The ~average over a set of REALs is given by: DEFINE AVERAGE( RS:REALS ) = REAL: BEGIN VAR R=REAL; + R FOR R $E RS; / + 1 FOR R $E RS; END ENDDEFN Here is a (slow) sorter: DEFINE SORT( RS:REALS ) = REALS: BEGIN VAR R,LOW=REAL; IF DEFINED(RS) THEN "The list is non-empty" DO "Lowest value..." LOW := MIN R FOR R $E RS; ; GIVE "Lowest value left-appended onto the sorted rendition of all larger elements in RS..." LOW <$ SORT( {COLLECT R FOR R $E RS; WITH R > LOW;} ) ELSE NIL FI END ENDDEFN More briefly and quickly you sort a list RS of REALs by: RS SORTED_BY R: R INCREASING 21.4.2 STATEMENTs Recall that a STATEMENT denotes an action and not a value. 21.4.2.1 Assignment Statements The simplest STATEMENT is the assignment statement, which follows: R := 2*X+1 ; This notation is supported by the rule: EXPR := EXPR ; -> STATEMENT A variation on this basic assignment statement supports the following notation: NUMBER ::= + 1 ; This is entirely equivalent to the standard: NUMBER := NUMBER + 1 ; This abbreviation allows us to write the name NUMBER only once. This is supported by the rule: EXPR ::= BOP EXPR ; -> STATEMENT This rule merely copies the lefthand EXPR onto the righthand side, before the BOP. Unlike the language C, any BOP can be used, including the form of BOP that represents a function call. 21.4.2.2 Safeguarding Global Variables ICL comes with a notation that protects the values in (global) variables. Global variables can be read and written over an enormous amount of program specification. Their existence is not limited to the insides of one function, as local variables are. Therefore, whenever we commence using a global variable, we would like to assure that its old value gets restored when we are done with it. This kind of protection lets us be unaware of other uses of the global variable, which might be frozen in progress during our use of the global variable. The HOLDING construct follows: holding ID ; ID ; ... ID ; do STATEMENT endhold -> STATEMENT Each ID is the name of a variable. Upon the HOLDING, the values in those variables are saved. The given STATEMENT is then executed, and it may use any of those variables freely. Upon completion, when the ENDHOLD is reached, the old values are restored into the variables. Thus, our use of those variables is invisible outside of this HOLDING...ENDHOLD construct. (There is also a HOLDING that applies to EXPRs instead of STATEMENTs). 21.4.2.3 Decision Making For STATEMENTs All the decision notations for EXPRs also exist for STATEMENTs. For example, the IF-THEN-ELSE statement is supported by the rule: if EXPR then STATEMENT else STATEMENT fi -> STATEMENT One of the then-STATEMENT and the else-STATEMENT is executed. Which one depends on the if-EXPR. 21.4.2.4 Local Variables For STATEMENTs Just like we have for EXPRs, we have a BEGIN...END notation for STATEMENTs: begin DECLARATION STATEMENT end -> STATEMENT 21.4.2.5 Looping With STATEMENTs A QUANTIFIER can be applied to a STATEMENT, as in: FOR I FROM 1 TO 10; DO WRITE(I); END This writes the numbers from 1 to 10, and is supported by the rule: QUANTIFIER do STATEMENT end -> STATEMENT The STATEMENT is executed once for each iteration caused by the QUANTIFIER. ?BOX: With what two parts-of-speech can a QUANTIFIER ?BOX: ultimately be applied? 21.4.3 QUANTIFIERs We will summarize three of ICL's basic QUANTIFIERs, introduce two ways to combine QUANTIFIERs to form more complex QUANTIFIERs, and one of ICL's quantifier modifiers. 21.4.3.1 Basic QUANTIFIERs The following rule supports what is called the ~arithmetic-FOR quantifier: for ID from EXPR to EXPR by EXPR in EXPR ; -> QUANTIFIER Not all of the clauses are required. For example: FOR I FROM 1 TO 5 ; causes 5 iterations and sets I to the values 1 thru 5. The QUANTIFIER: FOR X FROM 0 TO 1.0 IN 4 ; causes 4 iterations, and sets X to the vaues 0, .25, .5, and .75. Another possibly familiar QUANTIFER is the WHILE-quantifier: while EXPR ; -> QUANTIFIER The WHILE-quantifier causes arbitrarily many iterations. It causes iterations while the while-EXPR delivers TRUE. As soon as it delivers FALSE, there are no more iterations. For example, the following STATEMENT increments I and decrements J as long as I is less than J: WHILE I < J ; DO I::= + 1; J::= - 1; END Perhaps the most powerful basic quantifier in ICL is the list-FOR quantifier: for EXPR $e EXPR ; -> QUANTIFIER The "$e" reads as "is an element of". If S is a set (list) of REALs, then: FOR X $E S ; causes one iteration per element in S. It sets X to each element in S. For example, the following sums up the elements in S: + X FOR X $E S; 21.4.3.2 Quantifier Combinations Quantifiers can be combined to form more complex quantifers. 21.4.3.2.1 Lock-Stepping - The "&&" Two or more QUANTIFIERs may be combined so as to step in unison. Both QUANTIFIERs deliver their first iteration, and then both deliver their second iterations, etc. The notation for this is: QUANTIFIER && QUANTIFIER -> QUANTIFIER The "&&" makes them step in unison. For example: FOR I FROM 1 TO 5; && FOR J FROM 2 TO 10 BY 2; causes iterations as follows: iteration #1: I=1, J=2 iteration #2: I=2, J=4 ... iteration #5: I=5, J=10. The "&&" combined QUANTIFIER ceases as soon as either one of the given QUANTIFIERs ceases. The following iterates thru elements in two lists: FOR X $E S1; && FOR Y $E S2; Corresponding elements in both lists are delivered upon each iteration, so that the N'th iteration delivers S1's and S2's N'th elements. We can use this complex quantifier to ascertain whether each element in S1 is less than its corresponding element in S2: IF ALWAYS X < Y FOR X $E S1; && FOR Y $E S2; THEN "Each element in S1 is less than its corresponding element in S2 " ... 21.4.3.2.2 Nesting - The "!!" Another way to combine QUANTIFIERs follows: QUANTIFIER !! QUANTIFIER -> QUANTIFIER For each iteration caused by the first QUANTIFIER, perform ~all iterations of the second QUANTIFIER. That is, the second QUANTIFIER is ~nested within the first QUANTIFIER. For example, a two- dimensional grid of points is made by: FOR X FROM 1 TO 10; !! FOR Y FROM 1 TO 5; This causes 50 iterations. X takes on the value 1 while Y takes on the values 1 thru 5. Then X takes on 2, and Y once again takes on the values 1 thru 5. Finally, X takes on the value 10 and Y takes on the values 1 thru 5. If you plot the point delivered with each iteration, whose X-coordinate is X and whose Y-coordinate is Y, you will see a 10 by 5 grid of points. 21.4.3.2.3 QUANTIFIER Modifiers Any QUANTIFIER, be it a basic or a complex QUANTIFIER, may be ~modified. We show one modifier here: QUANTIFER with EXPR ; -> QUANTIFIER The WITH modifier ~filters ~out some iterations from the original QUANTIFIER. Only those iterations which cause the with-EXPR to yield TRUE become iterations of the resulting, modified QUANTIFIER. For example, if S is a set of INTegers, then the following QUANTIFIER causes one iteration for each ~positive member of the set S: FOR I $E S; WITH I > 0 ; Those elements in S which aren't positive are ignored. The following EXPR delivers the smallest positive integer in S: MIN I FOR I $E S; WITH I > 0 ; (This makes use of the BOP-EXPR-QUANTIFIER rule where the BOP is MIN (short for MINimum)). The following EXPR picks an apple out of a set which maximizes weight- to-price ratio: PICK APPLE MAXIMIZING WEIGHT(APPLE)/PRICE(APPLE) FOR APPLE $E a set of apples ; The following picks the same, except that only apples whose PRICEs are less than 1 are considered: PICK APPLE MAXIMIZING WEIGHT(APPLE)/PRICE(APPLE) FOR APPLE $E a set ; WITH PRICE(APPLE) < 1; BOX: BOX: If you wanted the WITH to have no effect, short of BOX: deleting the WITH-clause, what EXPR would you provide? 21.4.4 DECLARATIONs Declarations introduce new variables, types, and functions. 21.4.4.1 Variables Variables are introduced by: var ID , ID , ... , ID = TYPEX ; -> DECLARATION Each ID becomes a new variable, whose type is specified by the TYPEX. An example follows: VAR I,J = REAL ; Each of I and J now denotes a new variable of type REAL. 21.4.4.2 Types The following declares a new type and gives it a name: type ID = TYPEX ; -> DECLARATION The TYPEX expresses the new type, and the ID is the name given to that new type. For example: TYPE REALS = { REAL } ; makes REALS denote the type which is a ~list, each of whose elements is a REAL. 21.4.4.3 Functions The following introduces a new function: define ID ( ID : TYPEX ... ID : TYPEX ) = TYPEX : EXPR enddefn -> DECLARATION The function's name is the ID following the word DEFINE. The function's inputs appear in the parentheses. Each input indicates the type of the input (the TYPEX) and the variable name (ID) which will hold that input for use within the function's body, the EXPR. The type of the function's result appears following the "=". (The type of the EXPR must be found to match that TYPEX). (The "=TYPEX" will be omitted for functions returning no value, as in Section 22.4.3.2). For example, the following defines a function named ABS (short for ~absolute ~value): DEFINE ABS( R: REAL ) = REAL: IF R < 0 THEN -R ELSE R FI ENDDEFN The one input is of type REAL, and R is the name of the variable used to hold that input. Notice that R is used within the function's body (the IF-THEN-ELSE EXPR). The result of this function is of type REAL, as indicated at the end of the first line. The IF-THEN-ELSE EXPR denotes a REAL expression, as is required by that first line. ICL is a strongly typed language, which means that any value is an instance of some type. ~The ~types ~of ~all ~inputs ~and ~output ~are ~mandatory ~information. 21.4.4.4 Polymorphism ICL supports polymorphism or overloading, in that several functions can have the ~same ~name as long as they are distinguished by some input's or output's type. For example, the function ABS (absolute value) has at least three different meanings depending on the type of data involved: abs ( ~INT ) -> ~INT abs ( ~REAL ) -> ~REAL abs ( ~POINT ) -> ~REAL That is, ABS can map an INT to an INT, a REAL to a REAL, or a POINT to a REAL. These three functions can exist simultaneously, and are declared by: DEFINE ABS( X:INT ) = INT: ... ENDDEFN DEFINE ABS( X:REAL ) = REAL: ... ENDDEFN DEFINE ABS( X:POINT ) = REAL: ... ENDDEFN When you call ABS, the choice of which function to call is based on the ~type of data you are passing into ABS, INT, REAL, or POINT. (In general, the choice can depend also on the ~type of the output). 21.4.4.5 Coercion It is possible to declare functions without names. Such nameless functions are called ~coercions. Since they don't have names, they cannot be called explicitly. They are called implicitly. A coercion is a function that maps an instance of one type into an instance of another type. Coercions are called automatically, so as to maintain type-correctness of the overall program. An example will follow shortly. The declaration of a coercion is supported by the rule: let ID : TYPEX become TYPEX by EXPR enddefn -> DECLARATION The coercion maps instances of the first TYPEX into instances of the second TYPEX. The ID denotes the name of a variable that holds the input. The EXPR can refer to that variable. The EXPR must be of the type denoted by the second, output TYPEX. For example, the following coercion will let INTegers pass equally well as REALs: LET I:INT BECOME REAL BY FLOAT(I) ENDDEFN (The body of this coercion, the EXPR "FLOAT(I)", explicitly translates the INTeger I into a REAL). Armed with this coercion, any INTeger can be turned into a REAL without writing anything at all! For example, the following assignment of an INTeger into a REAL variable, R, is meaningful: R := N + 1 ; In the absence of this coercion, we would have to make an explicit notation, as in: R := FLOAT( N+1 ) ; The FLOAT would be necessary in order to convert the INT N+1 into a REAL, because the variable R is of type REAL presumably. Coercions may be declared from any type to any other type without restriction. You can even declare a coercion from type A to type B, and declare another coercion from type B back to type A. All coercions, like all functions, are type-checked so as to guarantee semantic consistency. Our example coercion is legal because the function FLOAT that it uses takes in an INTeger (like I) and delivers a REAL, which is the type that this coercion maps to. It is perhaps suprising that coercions turn out to be very useful. They're useful in forming concise and correct programs, and even more drammatically, in supporting simple and correct but major program modifications. (Section 23.5.3.2 shows an example). 21.4.4.6 Polymorphism And Coercion Heal The Wounds Of Type-Checking The distinction between INT and REAL is not one that a human necessarily wants to make. It is the computer that forces this distinction upon us. INTs and REALs on the computer are so different that our single concept of "1" takes on two very different representations, depending on whether we are talking about the INTeger 1 or the REAL 1.0: The INT 1 is represented by: 00000000000000000000000000000001 The REAL 1 is represented by: 00000000000000000100000010000000 Confusing the INT and REAL representations of "1" would be disasterous. Type-checking refers to guaranteeing that distinct types, like INT and REAL, never get confused. Type-checking is required if you want an absolute guarantee, even before your program ever runs, that INTs and REALs and other types aren't confused. Having made the distinction between the types INT and REAL, it is possible to go back and bandage up that distinction. While that distinction is required by the computer, the programmer can and often wants to live without it. This distinction is partly covered up by polymorphism. For example, the same notation, "+", can be used to add up INTs or to add up REALs. In the absence of polymorphism, you would have to use distinct symbols to specify addition, depending on whether you are adding INTs or REALs. This polymorphism lets you partially blur the distinction between INT and REAL. The distinction can be partially or even completely covered up by the use of coercions. The coercion we've just supplied lets us ignore the distinction so far as any INT will pass equally well as a REAL. That is, we can now supply either an INT or a REAL in any context that demands a REAL. To make INT and REAL completely interchangeable, we can add a coercion going in the opposite direction, via: LET X: REAL BECOME INT BY FIX(X) ENDDEFN Given coercions in both directions, from INT to REAL and back, you can supply either an INT or a REAL to any context which requires an INT or which requires a REAL. For the human, the distinction can now be ignored entirely. However, the computer forever makes this distinction, and all necessary translations do occur, even though the human need not be aware of them. This example of a coercion pair is partly objectionable because many of us don't like the coercion from REAL to INT. It loses information (the fractional part of the REAL). However, there are many other good examples of coercion pairs that don't lose information. The ability to cover up distinctions between types makes for clear and simpler programming, and greater ease of program modification. 21.4.4.7 Grouping DECLARATIONs Into UNITs Of Compilation A set of declarations may be entered into a file. The file as a whole will be compiled by ICL, separately from the compilation of other files. Such files are called ~units in ICL. Each unit has a name, and may ~include other units (files) so as to gain access to the other units' declarations. Thus, by including or not including a unit, you can pick and choose specifically which declarations you want to see or not to see. The use of units permits the growing of arbitrarily large systems. 21.4.5 TYPEXs And Type-Specific EXPRs ICL has built-in types including INTeger, REAL, BOOLean, CHARacter, and TEXT. Beyond these, ICL provides notations for forming new, more complex types from existing types. The part-of-speech TYPEX denotes notations that express (new) types. 21.4.5.1 Lists The rule: { TYPEX } -> TYPEX is used in the following type declaration: TYPE INTEGERS = { INT } ; The "{...}" is used primarily with list formation. An example list of type INTEGERS is: { 1 ; 2 ; 3 } or { COLLECT I FOR I FROM 1 TO 10; } This latter list contains the numbers 1 thru 10. The list: { COLLECT I*I FOR I FROM 1 TO 10; } contains the ~squares of the numbers 1 thru 10. If we assign this list into a variable: X := { COLLECT I*I FOR I FROM 1 TO 10; } ; then we can use ~list ~indexing to get at, say, the eighth element: X [ 8 ] Lists may have arbitrary lengths. Lists can be concatenated together, or can have a new element appended to the front or back of the list. Notations also exist to ~sort lists. The most popular way to access elements in a list is the FOR-quantifier FOR element $E list ; For example: FOR I $E X ; reads as "for I an element of X", and causes one iteration per element in X, setting I to each element in X. The list: { COLLECT I+1 FOR I $E X; } has the same length as the list X, and these elements are one greater than the corresponding elements in X. 21.4.5.2 Records All elements in a list have the same type. In contrast, the components of a ~record may have distinct types. Square-brackets ("[...]") are used generally with records. The type declaration: TYPE COMPLEX_NUMBER = [ REAL_PART: REAL IMAGINARY_PART: REAL ] ; declares COMPLEX_NUMBER to be a record having two components named REAL_PART and IMAGINARY_PART, both of which are of type REAL. The following is an instance of the type COMPLEX_NUMBER: [ REAL_PART: 5 IMAGINARY_PART: 3 ] The components of a record may be accessed one at a time. For example, if C is a variable of type COMPLEX_NUMBER, then the assignment: C := [ REAL_PART: 5 IMAGINARY_PART: 3 ] ; sets C to the COMPLEX_NUMBER so that subsequently: C . REAL_PART (C's real part) is 5, and C . IMAGINARY_PART (C's imaginary part) is 3. (See Section 23.4). 21.4.5.3 Variants It is possible that you may want a new type which can be any ~one member in a set of (other) types. For example, if APPLE and ORANGE are types, we may want to declare a new type FRUIT which can be either an APPLE or an ORANGE. The following type declaration makes this so: TYPE FRUIT = EITHER STATE1 = APPLE STATE2 = ORANGE ENDOR ; The type FRUIT is said to be a ~variant. With this type declaration, any instance of type APPLE will also be an instance of type FRUIT. Similarly, any ORANGE also passes as an instance of FRUIT. That is, this declaration delivers the two coercions we expect: ~APPLE -> ~FRUIT ~ORANGE -> ~FRUIT We most definitely do ~not introduce coercions going in the opposite direction. It is simply not so that any FRUIT is an APPLE, because it might be an ORANGE. A variant may be examined via the variant-CASE statement, e.g.: CASE fruit OF state1: statement state2: statement ENDCASE Within the first clause, the STATE1, the given fruit is known to be an apple, and can be accessed as such. Similarly, in the STATE2-clause, the fruit is known to be an orange, and can be accessed as such. 21.4.5.4 Processes A ~process is a packaged program. Programs can be packaged and then passed around like any other kind of data. Processes can be ~invoked at a later time. Invocation causes the packaged program to execute. A process type is supported by the rule: // \\ -> TYPEX In general, more information can be associated with the // and \\, to denote processes that take input or produce output upon each invocation. The same notation //...\\ is used to package a program so as to produce an instance of a process type. For example, let's declare the type BASIC_PROCESS that we've seen in Chapter 2: TYPE BASIC_PROCESS = // \\ ; An instance of this new type follows: // CRLF; WRITE( 2*PI ); \\ This process, when invoked, will cause the program to execute, and hence will cause a carriage-return line-feed to be printed (CRLF;) following by the number 2*PI. Another notation, <*...*>, is used to invoke a process. For example, let's assign our example process into the variable X: X := // CRLF; WRITE(2*PI); \\ ; We invoke X via: <* X *> ; This STATEMENT causes the program to execute. Processes are useful for implementing device-independent interfaces. Also, like we stressed in Chapter 2, processes are useful to ~delay the execution of programs. Processes can be formed from other processes, to easily and clearly build up very general complex processes. 21.4.5.5 Other Type Constructors ICL has at least three other forms of TYPEX. 21.4.5.5.1 Scalars The ~scalar construct admits a specific set of names (IDs) to be instances of the new, scalar type (see Section 23.8). 21.4.5.5.2 Disk-Residency Another TYPEX forms ~disk-resident types. A new type can be a disk- resident version of another type. Instances of a disk-resident type consume very little memory. The choices of what and when to swap out, or keep in main memory, are made automatically. A disk-resident object may exist in memory as long as there is enough memory. Swapping out occurs when memory is low. This kind of swapping is ~not based on ~pages of memory, rather, it is based on semantically meaningful objects. Thus, when an object swaps in, the whole object and only the object is swapped in. 21.4.5.5.3 Private Types Another TYPEX forms what are called ~private types. For example, the declaration: TYPE SORTED_INTEGERS = PRIVATE INTEGERS ; makes SORTED_INTEGERS be represented by the type INTEGERS, but the two types are not interchangeable. SORTED_INTEGERS presumably is an INTEGERS which has a special property, that of being sorted. Here, you introduce a distinction that would otherwise be unseen by ICL. One usually introduces one or both coercions between these two types. For example, a SORTED_INTEGERS is certainly valid as an INTEGERS, This invariant can be introduced by declaring a coercion going from SORTED_INTEGERS into INTEGERS. A coercion in the other direction might sort the given INTEGERS so as to come up with a valid SORTED_INTEGERS. The advantage of making such type distinctions is the ability to define functions that take in a SORTED_INTEGERS. The function can rest assured that its input (of type SORTED_INTEGERS) is already sorted, without having to re-sort the input. By using the type SORTED_INTEGERS instead of INTEGERS where appropriate, some sorting may be omitted. PRIVATE types, like this one, can be used also to force the programmer to specify units, such as ~feet or ~inches.