CHAPTER 22 EXPRs, STATEMENTs, QUANTIFIERs And DECLARATIONs In ICL This chapter documents in detail all of ICL excluding its type- constructors and type-specific EXPR forms. Those matters are dealt with in chapter 23. We begin with general EXPR forms, which are all EXPR notations except for type-specific notations. We will encounter the parts-of-speech BOP, UOP, and RHUOP in the formation of EXPRs. We then explore STATEMENTs, QUANTIFIERs, and finally DECLARATIONs. 22.1 General EXPR Forms 22.1.1 Operators EXPR BOP EXPR -> EXPR This rule supports the ~infix notation for combining EXPRs via BOPs (Binary OPerators). An example BOP is "+". This BOP is an ~infix operator because it sits ~in ~between its operands. The two operands for any BOP are the two EXPRs that appear to the left and right of the BOP, as our rule indicates. Example: Since "+" is a BOP and each of "1" and "2" are EXPRs, our rule supports the familiar expression: 1 + 2 as in: 1 + 2 EXPR BOP EXPR Example: The expression 1 + 2 * 3 is an EXPR because: 1 is an EXPR + is a BOP, and 2*3 is an EXPR. "2*3" is an EXPR because: 2 is an EXPR, * is a BOP, and 3 is an EXPR Notice how we bind together the "2*3" prior to binding the "+" with "1" and "2*3". A note about "Binding Order" or "Operator Precedence": The fact that "*" binds before "+" is based on the notation of "binding order" or "operator precedence". That is, the EXPR 1 * 2 + 3 * 4 is interpreted as: (1*2) + (3*4) because the operator "*" binds before the operator "+". You will see that "*" binds before "+" when you look at the rules for the BOPs "+" and "*": (They will be introduced more completely later): * -> BOP[3] + -> BOP[4] The 3 associated with the "*" is lower than the 4 associated with the "+". Therefore, the "*" (3) will bind before the "+" (r). You can enclose any EXPR within parentheses to override our default binding orders. The notation of operator precedence allows a minimal use of parentheses, and has been used in arithmetic and mathematics for years. An implementation of operator precedence appears in Chapter 3. NOTE: We generally do NOT guarantee order of evaluation, e.g., the left EXPR might be evaluated AFTER the right EXPR. For example, our EXPR-BOP-EXPR rule in Chapter 8 in fact evaluates the righthand operand before the lefthand one. UOP EXPR -> EXPR This rule supports ~prefix ~unary operators. A ~unary operator, like the "-" in "-5", takes in only one value, the "5" in "-5". "-" is a ~prefix operator because it appears ~before its input (5). UOPs (Unary OPerators) have "binding orders" like BOPs (Binary OPerators) do. ICL presently has only one UOP syntactically: - -> UOP[1] Its binding order is 1 (which is enclosed here in square brackets). This is lower than the binding orders of all BOPs. Thus, our unary minus "-" binds first, before any BOPs. For example: -1 is -1 -1+2 is (-1)+2 because the unary "-" binds before the "+" BOP. -(1+2) is is -3, because EXPRs in parentheses always bind first. EXPR RHUOP -> EXPR The rule supports ~postfix ~unary operators (RHUOPs, short for RightHand Unary OPerators). Examples of RHUOPs will appear shortly. RHUOPs have what we call ~indefinite binding order. We will introduce this notion shortly as we present ICL's BOPs. RHUOPs, like BOPs of indefinite binding order, tend to bind ~last. ( EXPR ) -> EXPR This rule allows you to override ICL's default binding orders. EXPRs enclosed in parentheses always bind first. Examples: 1 + 2 * 3 is 7, or 1+(2*3) by ICL's default binding orders. (1+2) * 3 is 9. Here, "+" binds before "*" because the EXPR involving "+" is enclosed in parentheses. 22.1.2 BOPs The BOPs following are presented in order from the tightest (lowest) binding order to the weakest (highest) binding. For each BOP, we will specify its binding order, enclosed in square brackets, like we did in Chapter 3. We will also specify the ~types of data on which it can apply. Recall that INTs (integers) are whole numbers, and that REALs include numbers with fractions. A POINT is a two-dimensional vector, or complex number. BOOLeans are binary values, TRUE or FALSE. The type TEXT is any chunk of text enclosed in single quotes, e.g., 'Monday'. ^ -> BOP[2] Exponentiation. It works on the following types: ~INT ^ ~INT -> ~INT ~REAL ^ ~INT -> ~REAL ~REAL ^ ~REAL -> ~REAL One can also write "~INT ^ ~REAL" because the INT can be coerced to a REAL. * -> BOP[3] Multiplication. It works on types as follows: ~INT * ~INT -> ~INT (integer multiply) ~REAL * ~REAL -> ~REAL (floating multiply) ~POINT * ~POINT -> ~POINT (complex multiply) ~REAL * ~POINT -> ~POINT (scalar multiply) ~POINT * ~REAL -> ~POINT (scalar multiply) Multiplication of points acts by interpreting POINTs as complex numbers. Multiplication does not occur independently for each coordinate. The final two rules multiply each coordinate of the POINT by the same REAL value. / -> BOP[3] Division. It works on types as follows: ~INT / ~INT -> ~INT (integer divide) ~REAL / ~REAL -> ~REAL (floating divide) ~POINT / ~POINT -> ~POINT (complex division) ~POINT / ~REAL -> ~POINT (scalar divide) Division on points acts by interpreting POINTs as complex numbers. Division does not occur independently for each coordinate. For INTegers, division is like that for REALs, except that the fractional part is lost. The final rule divides each coordinate of the POINT by the same REAL. + -> BOP[4] Addition. It operates on types as follows: ~INT + ~INT -> ~INT (integer add) ~REAL + ~REAL -> ~REAL (floating add) ~POINT + ~POINT -> ~POINT (coordinate-wise) Addition on points operates independently on each coordinate. You can still think of POINTs as complex numbers, as this is complex addition. - -> BOP[4] Subtraction. It operates on types as follows: ~INT - ~INT -> ~INT (integer subtract) ~REAL - ~REAL -> ~REAL (floating subtract) ~POINT - ~POINT -> ~POINT (coordinate-wise) Subtraction on points operates independently on each coordinate. You can still think of POINTs as complex numbers, as this is complex subtraction. & -> BOP[5] ANDing. It operates on types as follows: ~BOOL & ~BOOL -> ~BOOL ~INT & ~INT -> ~INT ANDing on BOOLeans yields TRUE exactly when both of the given BOOLs are TRUE. ANDing on INTegers occurs bitwise. The high-order (leftmost) bit of the two INTs are ANDed so as to produce the high-order bit of the resulting INTeger. A 1 ~and a 1 yields 1, and all other combinations yield 0. This occurs not only for the high-order bit, but for other corresponding bits as well. Examples: Each of the EXPRs "A<B" and "C<D" are BOOLeans. Each represents a TRUE or FALSE. The AND of these two EXPRs: A < B & C < D is TRUE precisely when both A is less than B and C is less than D. Two integers, shown with their binary equivalents, ~and as follows: 6 & 3 is 2 110 011 is 010 The leftmost bit in each are ANDed together, a 1 and a 0 in this example, yielding a 0. The middle bits are both on, so their AND is a 1. The rightmost bits AND together to form a 0. Thus, the resulting binary number is 010, which is 2 in base 10. ! -> BOP[6] ORing. It operates on types as follows: ~BOOL ! ~BOOL -> ~BOOL ~INT ! ~INT -> ~INT OR on BOOLeans is FALSE exactly when both of the given BOOLeans are both FALSE. The result is TRUE if either of the given BOOLeans (or both) are TRUE. INTeger ORing occurs bitwise, like ANDing does. xor -> BOP[7] XORing. It works on types just like & and ! do: ~BOOL xor ~BOOL -> ~BOOL ~INT xor ~INT -> ~INT XOR on BOOLeans yields TRUE exactly when the two BOOLean values differ. INTeger XOR occurs bitwise. bit -> BOP[7] Extract a single bit from an integer: ~INT bit ~INT -> ~BOOL This extracts a single bit from within the lefthand integer. We number bits from 0 to 31, right-to-left (i.e., by the natural powers of 2). The righthand integer selects which bit to look at, within the lefthand integer. The resulting BOOLean EXPR yields TRUE if the selected bit is on, and FALSE otherwise. shiftl -> BOP[7] Shift left: ~INT shiftl ~INT -> ~INT The lefthand integer is shifted leftward by some number of bits. That shifted lefthand integer is the result. The righthand INT tells how many bits to shift by. (A negative value in the righthand INT causes rightward shifting). Bits of value 0 are shifted in to take the place of bits that have moved from the far right (or left). shiftr -> BOP[8] Shift right: ~INT shiftr ~INT -> ~INT The lefthand INT is shifted rightward by some number of bits. The righthand INT specifies how many bits to shift by. A negative value in the righthand INT causes leftward shifting. min -> BOP[8] Minimum. It operates on types as follows: ~INT min ~INT -> ~INT ~REAL min ~REAL -> ~REAL ~POINT min ~POINT -> ~POINT For INTs and REALs, yield the operand having the lowest value. For POINTs, yield a new point each of whose coordinates is the MIN of the corresponding coordinates of the two given POINTs. That is, the X- coordinate of the result is the MINimum of the two X-coordinates in the two given POINTs. Similarly, the Y-coordinate in the result is the MIN of the the two given POINTs' Y-coordinates. Example: (1#2) MIN (2#0) -> 1#0 (The "#" is used to form POINTs, as we will see shortly, given the X and Y-coordinates on the left and right side of the "#"). max -> BOP[8] Maximum. It operates on types as follows: ~INT max ~INT -> ~INT ~REAL max ~REAL -> ~REAL ~POINT max ~POINT -> ~POINT This is exactly like MIN, except that the larger of the two numbers is used instead of the smaller of the two numbers. Example: (1#2) MAX (2#0) is 2#2 22.1.3 More BOPs: Those Having ~Indefinite Binding Order The following BOPs have what we call ~indefinite binding order. They will bind any possible way, but they tend to bind after all other BOPs (shown up to now) have bound. We can therefore think of the indefinite binding order as being higher than the binding order of other BOPs. BOPs of indefinite binding order are flexible in that this natural binding order will be violated so as to maintain "type consistency". That is, if type consistency can be achieved only by having an indefinite BOP bind ~before a regular BOP, such will occur. Also, if a strictly left-to-right binding would force a loss of type consistency, then another binding order will be chosen. We can say simply that indefinite BOPs bind after other BOPs as much as possible, and as left-to-right among themselves as possible, governed by type consistency. For example, the BOP "#" has indefinite binding order. In the following example, the "*" binds before the "#", following the natural tendency: 1 * 2 # 3 will bind as (1*2) # 3 In contrast, the following example violates the natural binding order. The "#" binds before the "*": 1 # 2 * 3 # 4 will bind as (1#2) * (3#4) Notice how in the first case that "*" binds before "#", but in the second example, the "#"s bind before the "*" The latter example exposes a violation of the natural binding order. The natural binding order would bind the "*" first, and would render our expression as: 1 # (2*3) # 4 One of the two "#"s would be forced to take in a POINT, which is not possible. ("#" takes in only REALs). Also, a left-to-right binding: ( 1 # 2 * 3 ) # 4 would violate type consistency, as the final "#" would be forced to combine the impossible, a POINT and a REAL. Following are ICL's BOPs of indefinite binding order. # -> BOP[indefinite] Point synthesis. It operates on types as follows: ~REAL # ~REAL -> ~POINT This forms a POINT from an X- and Y-coordinate, X#Y. This BOP has the unusual property that it also has meaning on the lefthand side of an assignment statement. It unloads both coordinates into variables. Example: 1 # 2 is the point whose X-coordinate is 1 and whose Y- coordinate is 2. Example: U # V := a point ; sets the variable U to the given point's X-coordinate, and sets V to the point's Y-coordinate. <$ -> BOP[indefinite] Left append. It operates on lists (Section 23.3). Assume that "LIST" is a type defined by: TYPE LIST = { ELEMENT } ; That is, LIST is a list (or set) of ELEMENTs. This BOP can be used as follows: ~ELEMENT <$ ~LIST -> ~LIST This resulting list has ~element as its first element, and all of the given list as its tail. The resulting list has one more element than the given list. (The result's second element is the given list's first element, and so on). This BOP has the unusual property that it also has meaning on the lefthand side of an assignment statement. Example: If X is a list of INTegers, say { 10 ; 20 ; 30 ; 40 ; 50 } then 0 <$ X is the list: { 0 ; 10 ; 20 ; 30 ; 40 ; 50 } and the list -10 <$ 0 <$ X is the list: { -10 ; 0 ; 10 ; 20 ; 30 ; 40 ; 50 } Example: If X is a list of INTegers, and I is an INTeger variable, then the assignment: I <$ X := X ; sets I to the first element of X, and resets X itself to be the tail of the given list X. If X starts out as: { 10 ; 20 ; 30 ; 40 ; 50 } then the assignment sets I to 10, and sets X to the list: { 20 ; 30 ; 40 ; 50 } $> -> BOP[indefinite] Right append. Like "<$", this BOP deals with lists. Assume LIST is declared by: TYPE LIST = { ELEMENT } ; The right-append operator works on types as follows: ~LIST $> ~ELEMENT -> ~LIST The resulting list is the given list but with one element appended to its right end. Example: If X is a list of INTegers, say { 10 ; 20 ; 30 ; 40 ; 50 } then X $> 60 is the list: { 10 ; 20 ; 30 ; 40 ; 50 ; 60 } $$ -> BOP[indefinite] List concatenation. Assume that LIST is a type declared by: TYPE LIST = { ELEMENT } ; This concatenate operator works on types as follows: ~LIST $$ ~LIST -> ~LIST The resulting list consists of all elements of the first list (in order) followed by all elements of the second list (in order). Example: If X is a list of INTegers, say { 10 ; 20 ; 30 ; 40 } then X $$ X is the list: { 10 ; 20 ; 30 ; 40 ; 10 ; 20 ; 30 ; 40 } = -> BOP[indefinite] <> -> BOP[indefinite] Equals and not-equals. These BOPs compare entities and yield a BOOLean value indicating the truth of the comparison. They operate on types as follows: ~INT = ~INT -> ~BOOL ~REAL = ~REAL -> ~BOOL ~POINT = ~POINT -> ~BOOL (equal coordinatewise) ~BOOL = ~BOOL -> ~BOOL ~TEXT = ~TEXT -> ~BOOL These same capabilities exist for "<>" in place of "=". "<>" is exactly NOT "=". Each of these two BOPs operate also on scalar-types and disk-types (Sections 23.8 and 23.9). < -> BOP[indefinite] =< -> BOP[indefinite] > -> BOP[indefinite] >= -> BOP[indefinite] These operators are respectively "less than", "less than or equal", "greater than", and "greater than or equal". An easy way to remember the "... or equal" operators, which involve the "=" character, is that they ~avoid forming arrows. These BOPs operate on types as follows: ~INT < ~INT -> ~BOOL ~REAL < ~REAL -> ~BOOL ~POINT < ~POINT -> ~BOOL Although we don't list them here, these same rules apply for the other three comparator BOPs: "=<", ">", and ">=". POINTs are compared by comparing each coordinate independently. Both have to be true for the same to be said of the point. For example: A < B implies that A.X < B.X and A.Y < B.Y In other words, "A<B" implies that the point A resides to the ~left of and ~below the point B. This "<" ordering on POINTs is a ~partial ~order: It is possible that all of the following are simultaneously false: A = B A < B A > B This interpretation for comparisons is consistent with the MIN and MAX operators on POINTs shown earlier. That is, the following are always true: A MIN B =< A A MIN B =< B and A =< A MAX B B =< A MAX B \ ID -> BOP[indefinite] This notation provides a way to call functions in an ~infix manner. This BOP calls the binary, value-returning function whose name is given by the ID. That is, the EXPR param1 \function_name param2 acts exactly as does: function_name( param1 , param2 ) For example, we can call the function named PAINTED via either: picture \PAINTED red or PAINTED( picture , red ) This infix notation for calling functions is very helpful for clarity. It is used profusely in practice. For example, Section 9.8 introduced the \OFF_OF function, used in expressions like: 1 \OFF_OF "register" 3 Expressions like this appeared in instructions, such as: LOAD( 2 , 1 \OFF_OF 3 ); 22.1.4 UOPs and RHUOPs UOPs and RHUOPs are distinct in that a UOP precedes its operand whereas an RHUOP follows its operand. UOPs are ~prefix unary operators, and RHUOPs are ~postfix unary operators. - -> UOP[1] Negation. This UOP operates on types as follows: - ~INT -> ~INT - ~REAL -> ~REAL - ~POINT -> ~POINT - ~BOOL -> ~BOOL For INTegers and REALs, "-" performs arithmetic negation, turning a positive number into a negative number or vice versa. For POINTs, "-" negates each coordinate independently. Thus: -(1#2) is the point -1 # -2 For BOOLeans, it performs logical negation: A TRUE becomes FALSE and a FALSE becomes TRUE. \ ID -> RHUOP This rule provides a way for calling a unary, value-returning function in a postfix manner. For example, the EXPR param1 \function_name means the same as function_name( param1 ) Sometimes, calling a unary function in a postfix manner lends clarity to the program listing. In the mathematical discipline of group theory, postfix notation is generally used for the application of operators. For example, suppose we have two unary functions that manipulate pictures, ROT_CW (rotate clockwise) and MIRROR_X (mirror about the X-axis). The EXPR: picture \ROT_CW \MIRROR_X reads like what it does. It first applies ROT_CW and then applies MIRROR_X. In the standard prefix notation, this reads as: MIRROR_X( ROT_CW( picture ) ) The order of application is ~not left-to-right, and therefore may be less clear. sorted_by ID : EXPR increasing -> RHUOP sorted_by ID : EXPR decreasing -> RHUOP sorted_by ID : EXPR non_increasing -> RHUOP sorted_by ID : EXPR non_decreasing -> RHUOP These RHUOPs sort elements in a list. These will be described in Section 23.3. These SORTED_BY constructs are cast as RHUOPs for generality. To understand them, imagine always an EXPR appearing to the left of this notation, as in: ~EXPR sorted_by ID: EXPR increasing This is itself an EXPR (due to our rule: EXPR RHUOP -> EXPR. Any RHUOP preceded by an EXPR is always an EXPR). For example, given a set of PEOPLE, we acquire the same sorted by increasing age via: PEOPLE SORTED_BY P: P.AGE INCREASING 22.1.5 Cumulative Application Of BOPs BOP EXPR QUANTIFIER -> EXPR Apply the BOP repeatedly so as to combine all the values yielded by the EXPR's evaluation upon each iteration cuased by the QUANTIFIER. That is, if the QUANTIFIER causes N iterations, we denote the values yielded by the EXPR on each iteration as: EXPR(1) , EXPR(2) , ... , EXPR(n) This rule yields the value: EXPR(1) bop EXPR(2) bop ... bop EXPR(n) or more precisely, the grouping is always left-to-right, as in ( ( ( EXPR(1) bop EXPR(2) ) ... ) bop EXPR(n) ) ---------------- Parentheses in previous paragraph around "1", "2" ---------------- and "n" mean subscripting! ---------------------------- This usage of a BOP is called the ~cummulative application of the BOP. In case the QUANTIFIER causes only one iteration, yield simply the EXPR's value attained on that first iteration. In case the QUANTIFIER causes zero iterations, yield NIL, 0, or FALSE. The type requirements of this rule may be stated as follows: It must be possible to declare a temporary variable, say T, such that both of the following are legal: 1) T := EXPR ; and 2) T := T BOP EXPR ; Generally, if the BOP maps two instances of the same type back to an instance of that same type, these requirements are certainly met. Example: The EXPR: + I FOR I FROM 1 TO 10; BOP EXPR QUANTIFIER represents the sum of integers from 1 to 10. (See Section 22.3.1 for the QUANTIFIER "FOR I FROM 1 TO 10;"). When the BOP is a "+", as in this example, this entire rule denotes the mathematician's sigma notation for forming sums over sets. This example is equivalent to: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 The EXPR * I FOR I FROM 1 TO 10; forms the produce of the integers from 1 to 10. If PS is a list of POINTs, and P is a variable of type POINT, the following EXPR sums up all the POINTs in PS: + P FOR P $E PS; The QUANTIFIER "FOR P $E PS;" reads as ~for ~each ~P ~in ~PS. The following EXPR yields the number of points in PS: + 1 FOR P $E PS; The "average" over the set of POINTs PS can be specified as: ( + P FOR P $E PS; ) / ( + 1 FOR P $E PS; ) Example: Since any binary function can be called as though it were a BOP, due to the rule: \ ID -> BOP , you can actually use this "cummulative" construct for operators of your own making. For example, suppose we have a type PICTURE, and an operator SUPERIMPOSE which maps two PICTUREs to one PICTURE. We can form the superimposed union over a ~set of PICTUREs with: \SUPERIMPOSE PICTURE FOR PICTURE $E PICTURES; A variation on this cummulative operator syntax is offered by the semantically identical rule: QUANTIFIER BOP EXPR -> EXPR This rule puts the QUANTIFIER first, which can be used to place emphasis on the QUANTIFIER. (Use one or the other rule so as to stress the BOP or the QUANTIFIER). This second rules chooses as its EXPR the largest possible amount of text, so that: QUANTIFIER + A + B groups as: QUANTIFIER + (A+B) and not as ( QUANTIFIER + A ) + B, which yields a different result. 22.1.6 General EXPR Forms Beyond BOPs, UOPs, and RHUOPs do STATEMENT give EXPR -> EXPR Peform the STATEMENT immediately before evaluating the EXPR. Example: The EXPR DO R:= SQRT( X*X + Y*Y ) ; GIVE R*COS(THETA) # R*SIN(THETA) assigns a value into R (the DO part) and then yields a value that is computed by referencing R twice. This entire EXPR not only yields a value (the GIVE), but it has the side-effect of setting the variable R (the DO). This construct is most helpful when context demands an EXPR but you want to perform some STATEMENT prior to delivering the EXPR. For example, a function that returns a value must have an EXPR for its body (Section 22.4.3). That is, we might declare a function as follows: DEFINE F( X,Y,THETA: REAL ) = REAL: some EXPR ENDDEFN The EXPR that makes up the body may be rendered with the DO...GIVE construct as in: DEFINE F( X,Y,THETA: REAL ) = REAL: DO R:= SQRT( X*X + Y*Y ) ; GIVE R*COS(THETA) # R*SIN(THETA) ENDDEFN NOTE about binding order: This rule takes as its EXPR (following the GIVE) as much as possible: Therefore: DO STATEMENT GIVE I + J binds as DO STATEMENT GIVE (I+J) as opposed to: ( DO STATEMENT GIVE I ) + J giving EXPR do STATEMENT end -> EXPR Perform the STATEMENT immediately after evaluating the EXPR. The STATEMENT does not affect the value of the EXPR. Example: The EXPR: GIVING TIME DO TIME:= TIME+1; END yields the value presently in TIME, but leaves that variable holding a value one greater. begin DECLARATION EXPR end -> EXPR This rule supplies new local variables for use within the EXPR between the BEGIN and the END. The DECLARATION specifies the new local variables. We will see shortly the rules that form DECLARATIONs. Only the declaration of variables is allowed here (the VAR declaration). For example, let's use the EXPR DO R:= SQRT( X*X + Y*Y ) ; GIVE R*COS(THETA) # R*SIN(THETA) This EXPR presumes the existence of a variable R. Let's declare R to be local for this EXPR. We surround this EXPR and the declaration of R by a BEGIN...END: BEGIN VAR R = REAL; DO R:= SQRT( X*X + Y*Y ) ; GIVE R*COS(THETA) # R*SIN(THETA) END Most function bodies are formed this way. A BEGIN...END surrounds a DO...GIVE, as in. DEFINE F( X,Y,THETA: REAL ) = REAL: BEGIN VAR R = REAL; DO R:= SQRT( X*X + Y*Y ) ; GIVE R*COS(THETA) # R*SIN(THETA) END ENDDEFN There is also a similar BEGIN...END for STATEMENTs. ( EXPR := EXPR ; ) -> EXPR This shorthand notation performs an assignment statement and yields as its value the value assigned. That is: (EXPR1 := EXPR2;) is equivalent to DO EXPR1 := EXPR2 ; GIVE EXPR1 ICL supports other kinds of assignment statements besides the ":=" (see Section 22.2.1). Any of the various assignment statements can appear between the parentheses. nil -> EXPR The value NIL is meaningful for all types except INT, REAL, BOOL, and CHAR. It means "no value". A NIL list has no elements. A NIL record has no components, etc. defined( EXPR ) -> EXPR The given EXPR can be of any type except INT, REAL, BOOL, and CHAR. The resulting EXPR is of type BOOLean. Yields TRUE if the EXPR is ~not NIL. In practice, this is used to test for NIL. ID :: EXPR -> EXPR This syntactic construct has two distinct meanings, one for the synthesis of ~variants, and the other for ~type ~disambiguation. For the synthesis of variants, refer to Section 23.5.1. We now present the type-disambiguation meaning. Due to ICL's polymorphism and coercions, any given EXPR may in fact be interpretable as an instance of ~several distinct types. For example, "5" is interpretable as both an INT and a REAL. This construct enables you to specify which of the possible interpretations you desire. The ID must be the name of a declared type, and the first EXPR must be interpretable as an instance of that type. The result is the given EXPR interpreted as an instance of that type. Example: Suppose we have a coercion from type INTeger to REAL, (like FORTRAN has). Suppose also that we have two WRITE procedures, one of which takes in an INTeger and the other of which takes in a REAL. If we specify: WRITE( 5 ) ; we will see a "5" printed on the terminal. We will see the same thing if we specify: WRITE( INT :: 5 ); However, we will see "5.0" if we specify: WRITE( REAL :: 5 ); In consideration of polymorphism and coercion, ICL always chooses an interpretation that minimizes the total number of coercions. You may override such choices by using this "::" construction. For example, the first WRITE statement shown above prints the INT 5 because "5" is an INT and there exists a WRITE that accepts directly INTs. This interpretation requires the use of zero coercions, and hence is chosen. The final example WRITE statement, the one that prints "5.0", chooses also an interpretation that minimizes the number of coercions. However, in this case that minimal number of coercions is one and not zero. The "REAL::" specifies that the "5" must be interpreted as a REAL along the way. This requirement can be met with no fewer than one coercion, the coercion that maps the INT 5 into the REAL 5.0. NOTE about binding order: The "ID::" binds with the smallest EXPR, just like a unary operator of binding order 1, (like unary "-"). For example: POINT :: 1#0 will group as: (POINT::1) # 0 regardless of type consistency. In this case, type consitency may be lost. In contrast, the following makes sense: POINT :: (1#0) 22.1.7 Decision Making if EXPR then EXPR else EXPR fi -> EXPR if EXPR then EXPR ef EXPR then EXPR ef EXPR then EXPR ... ef EXPR then EXPR else EXPR fi -> EXPR This is known as the IF-THEN-ELSE construct for EXPRs. The EXPRs following the words IF and EF must be of type BOOLean, which of course evaluate always to TRUE or FALSE. The first rule yields the then-EXPR if the if-EXPR yields TRUE, otherwise it yields the else-EXPR. The second rule evaluates each if-EXPR and ef-EXPR, in order, until one yields TRUE, at which point, it yields the corresponding then-EXPR (the one on the same line as shown here). If none of the if-EXPRs yields TRUE, then it yields the else-EXPR. The keyword "EF" is short for "Else If". All of the then-EXPRs and the else-EXPR must be of the same type. That type is the type of the resulting EXPR. A similar looking IF-THEN-ELSE exists for STATEMENTS (Section 22.2.3). There, the ELSE clause is optional. Here, it is mandatory, as always some value must be presented, e.g., ... ELSE NIL FI Example: The following IF-THEN-ELSE yields the absolute value of X: IF X < 0 THEN -X ELSE X FI The following tells how long you might wait in your car at an intersection for a green light: IF LIGHT = GREEN THEN 0 EF LIGHT = RED THEN 60 ELSE "(Light is yellow)" 70 FI The trailing FI exists to disambiguate between two possible interpretations. Consider the following IF-THEN-ELSE, shown without a FI: IF A < B THEN 10+20 ELSE 3+4 Suppose A<B is true, so that the THEN clause will be taken. Is the result 30 or 34? The appearence of the mandatory FI disambiguates these two interpretations: IF A < B THEN 10+20 ELSE 3+4 FI is 30 (with A<B true) IF A < B THEN 10+20 ELSE 3 FI + 4 is 34 goto EXPR NUMBER => EXPR NUMBER => EXPR ... NUMBER => EXPR endgoto -> EXPR The first EXPR (following the "GOTO") must be of type INTeger. This acts exactly like a big IF-THEN-ELSE construction. It choses the EXPR that follows the literal NUMBER matching the value yielded by the GOTO EXPR. All the EXPRs except the GOTO EXPR must be of the same type, and that type is the type of the result. If the GOTO EXPR has a value that matches none of the NUMBERs, then NIL, 0, or FALSE (depending on the result type) is the resulting value. A similar GOTO construct exists for STATEMENTs as well. In addition: You may substitute one occurence of "NUMBER" with the keyword "ELSE", to capture all values not covered by the NUMBERs. If you include the ELSE, some EXPR will always be chosen. NOTE: The NUMBERs must be all non-negative. NOTE: Given many clauses, this construct may be more efficient than a corresponding IF-THEN-ELSE construct. Example: The following writes a non-negative number (N) in the "ordinal" English: WRITE( GOTO N 1 => 'first' 2 => 'second' 3 => 'third' 4 => 'fourth' 5 => 'fifth' ELSE => N $$ '''th' ENDGOTO ); (The EXPR: N $$ '''th' turns the number N into TEXT, a list of characters, and appends on the right the text "'th"). case ID of ID : EXPR ID : EXPR ... ID : EXPR endcase -> EXPR This is the ~variant CASE construct. It is described along with variant datatypes in Section 23.5.2 case EXPR of ID : EXPR ID : EXPR ... ID : EXPR endcase -> EXPR This is the ~scalar CASE construct. It is described along with the SCALAR datatype in Section 23.8. 22.1.8 Universal And Existential Quantification always EXPR QUANTIFIER -> EXPR This rule implements universal quantification, as in the mathematician's ~for ~all. The given EXPR, and the resulting EXPR are of type BOOLean. Yield TRUE if the given EXPR yields TRUE for every iteration caused by the QUANTIFIER. Example: If PS is a list of POINTs, we determine that all their X- coordinates are positive by writing: ALWAYS P.X > 0 FOR P $E PS; (The quantifier "FOR P $E PS" sets P to each element in PS). We can use this EXPR in an IF-THEN-ELSE as follows: IF ALWAYS P.X > 0 FOR P $E PS; THEN WRITE('All points have positive x-values'); ELSE WRITE('The point'); WRITE(P); WRITE(' has a non-positive x-value'); FI NOTE: In case the condition fails, the very first iteration in which it fails is left intact. The variable(s) are left holding the value(s) which cause the first violation. never EXPR QUANTIFIER -> EXPR NEVER yields TRUE if the given EXPR yields FALSE on every iteration caused by the QUANTIFIER. NOTE: In case NEVER yields FALSE, the very first iteration for which the EXPR yields TRUE is left intact. there_is EXPR QUANTIFIER -> EXPR THERE_IS yields TRUE if the given EXPR yields TRUE on some iteration caused by the QUANTIFIER. NOTE: In case THERE_IS yields TRUE, the first iteration upon which this becomes known is left intact. That is, the very first iteration in which the EXPR yields TRUE is left intact. NOTE: In case the QUANTIFIER causes zero iterations: ALWAYS yields TRUE, NEVER yields TRUE, and THERE_IS yields FALSE. In addition: All three of these constructs, ALWAYS, NEVER, and THERE_IS can be cast in the following semantically identical syntax, where the QUANTIFIER appears first: QUANTIFIER always EXPR -> EXPR QUANTIFIER never EXPR -> EXPR QUANTIFIER there_is EXPR -> EXPR Example: The following two uses of ALWAYS are equivalent: IF ALWAYS P.X > 0 FOR P $E PS; THEN ... ELSE ... FI and IF FOR P $E PS; ALWAYS P.X > 0 THEN ... ELSE ... FI This choice of notations allows you to stress either the EXPR or the QUANTIFIER. These rules' EXPRs consume as must text as possible to the right (even disregarding type consistency). Thus, for example: QUANTIFIER ALWAYS A < B ! B < C groups as QUANTIFIER ALWAYS (A < B ! B < C) and not as: ( QUANTIFIER ALWAYS A < B ) ! B < C 22.1.9 Minimizing Functions pick EXPR minimizing EXPR QUANTIFIER -> EXPR The first EXPR may be of any type, and that is the type of the result. The second EXPR must be either of type INT or type REAL. The result is one of the values taken on by the first EXPR during the iterations caused by the QUANTIFIER. The chosen value is taken from the particular iteration which causes the second EXPR to take on a ~minimal value. If the QUANTIFIER causes zero iterations, the result is 0, NIL, or FALSE. Example: Given a list of POINTs PS, we pick the POINT in PS which is closest to the origin by: PICK P MINIMIZING ABS(P) FOR P $E PS; The chosen P has the smallest "ABS(P)". pick EXPR maximizing EXPR QUANTIFIER -> EXPR This is similar to the previous rule, except that the chosen iteration is one which ~maximizes the second EXPR. The following are equivalent: PICK A MAXIMIZING B QUANTIFIER PICK A MINIMIZING -B QUANTIFIER Finally, you get the equivalent forms: QUANTIFIER pick EXPR minimizing EXPR -> EXPR QUANTIFIER pick EXPR maximizing EXPR -> EXPR Each rule consumes as much text to the right of the keyward "MINIMIZING" (or "MAXIMIZING") as possible. These alternative notations let you stress the QUANTIFIER instead of the two EXPRs. 22.1.10 Global Variables holding ID ; ID ; ... ID ; give EXPR endhold -> EXPR Please refer to the HOLDING construct for STATEMENTs for a detailed explanation. The EXPR (following the GIVE) can be of any type, and that is the type of the resulting EXPR. 22.1.11 Objective Modification The following operators are actually required relatively rarely. @ ( EXPR ) -> EXPR (target) This is the "@-operator", the one operator in ICL that actually exposes the use of pointers. This notation has meaning only on the lefthand side of an assignment statement, as in: @(P) := Q ; This assignment statement does not modify P. It modifies what P points to. This assignment causes the block of memory that P points to to be overwritten with the contents of the block that Q points to. Throughout all of ICL excluding this operator, all modifications affect only variables and NEVER datastructures. Thus for example, if X and Y are variables of the same record type (Section 23.4), the assignment: X := Y ; makes X point to the same block of memory that Y presently points to. Consider a subsequent assignment: Y.A := a new value ; This assignment to "Y.A" affects the variable Y and not the structure pointed to by Y. Thus, even after the first assignment made X and Y point to the same thing, the second assignment makes Y point to a new block of memory, a record which differs from the original in its A component. We say that modifications always occur on a "copy-on-write" discipline, as introduced in Chapter 10. No existing data are ever modified (without using the @-operator). All modifications are "subjective" in that each modification affects exactly ONE point of view, a single variable. This "subjective" default in ICL means that in the absence of the @-operator, and in conjuntion with our "pass by value" discipline for function calls, we can actually guarantee the following: In looking at a program listing, if you don't see a variable's occurence on the lefthand side of an assignment, you can rest assured that that variable, and all data accessable from that variable, are entirely unchanged from start to finish. This invariant is true, no matter how many functions might be called in the interim. Also, in the absence of the @-operator, you can actually believe that each and every assignment statement makes a complete copy of all data accessable from the value being assigned, and that every function call creates a complete copy of each parameter passed into that function. The @-operator overrides ICL's default "subjective" implementation of modification. The @-operator allows data and not just variables to be modified. Modifications implanted via the @-operator are said to be "objective" modifications; these modifications become apparent from ~all points of view. Refer to the previous example involving X and Y. Having said: X := Y ; we know that X and Y point to the same block of memory. If we now go ahead and say: @(X).A := a new value ; then we will affect not the variable X, but rather, the actual record referenced by X. Since X and Y (still) point to the same record, Y's A component will appear to have been modified, just like X's A component has. In fact, any other data that reference this record will "see" this modification to this record's A component. Of all possible types in ICL, only lists, records, variants, and processes may be @-assigned. Lists are special when compared to these other types. Lists may experience partial sharing. One list may in fact point to the tail of another list. (See T and S in figure 22.1. T points to a tail of S). Thus, an @-assign performed upon the tail (T) may become visible to the long list (S). This fact can be used to advantage. Example: Let S be a "refreshed" list like in figure 22.1(a). (More about "refreshed" in a moment). We set T to be the tail of S starting at S's 5'th element: T := S[5-] ; (This notation is introduced in Section 23.3). The figure shows T, and also T[2-] (which is the same as S[6-]). We can use the @-operator as follows: @(T) := T[2-] ; This causes the block that T points to to be overwritten with the value T[2-], as in figure 22.1(b). That value, T[2-], is the block containing an F. Notice how the block at T comes to hold that F and a pointer to the G node, just like the block that was T[2-]. Thus, the @-operator allows for explicit list processing, such as deleting elements in lists. Example: Let's consider another objective modification upon T: @(T) := X <$ Y <$ T[2-] ; This inserts the elements X and Y in place of the element T[1] objectively. Figure 22.1(c) shows the value: X <$ Y <$ T[2-]. Figure 22.1(d) shows the effect of this @-assignment. The block referenced by T has been overwritten with this new value. Because of the objective @, S will see this modification as well. X and Y will replace S's 5'th element. "Refreshed" Lists: Lists are NOT necessarily represented by a sequence of blocks left-to-right. This is essential to know only if you use "@" on lists. Lists formed exclusivly via the curly-bracket notation and the left append operator ("<$") are said to be "refreshed". (See Section 23.3). These lists are in fact guaranteed to be represented by a list of blocks whose order corresponds logically with the order of the list. In contrast, the right-append operator ("$>") and concatenate operator ("$$") do ~not produce "refreshed" lists. All guarantees are off if S is not "refreshed", as far as the @-operator is concerned. You can use the REFRESH operator to render any list "refrehsed". Subtle Example: If S is a refreshed list, then the assignment: @(S) := U <$ S ; actually creates a list with a cycle in it, i.e., a list that appears to have infinitely many U's in front! Figure 22.2(b) shows "S" and "U <$ S". Notice that "U <$ S" points to S. If we overwrite the S block with the "U <$ S" block, as this assignment does, figure 22.2(c) shows the result. The block to which S points contains a reference to itself, the S in "U <$ S". In contrast, we gain the desired effect of inserting objectively U at the front of S via: @(S) := U <$ COPY(S) ; The righthand side of this statement no longer references what S points to. It references only a copy of the block S points to. Figure 22.2(d and e) show what happens. The block that S points to now represents the old value of S with U inserted at the front as desired. (Note that these considerations are absent if we omit the @-operator. The following has no problems: S := U <$ S ; It merely makes S point to the leftmost block in figure 22.2(b)). NOTE: The @-operator issues a runtime error if the EXPR is NIL. copy ( EXPR ) -> EXPR The EXPR must be interpretable as an instance of a type which may be @-assigned, e.g., records. The result is of the same type. The resulting value occupies a different memory block than does the given value. COPY thus produces a copy of ~exactly ~one block of memory. This operator is useful only in conjunction with uses of the @- operator. (See previous example). NOTE: COPY issues a runtime error if the EXPR is NIL. EXPR =:= EXPR -> EXPR Compare any two items of the same types, except for our non-pointer types: INT, REAL, BOOL, and CHAR. Are the two items identical, that is, do they reside at the same ~memory ~address? Examples: A =:= A is always TRUE A =:= COPY(A) is always FALSE If A=:=B, then the objective modification: @(A):= ... ; will be apparent to B as well, since A and B reference the same memory location. You may need to enclose each of the two EXPRs in parentheses. "=:=" binds to the smallest possible EXPRs on the left and right, even if it results in datatype errors. That is: A \FUNCTION B =:= C groups as A \FUNCTION (B =:= C) and not as: (A \FUNCTION B) =:= C 22.2 STATEMENTs STATEMENTs perform actions rather than computing values as EXPRs do. 22.2.1 Assignment Statements We begin with the most popular statement, the assignment statement. EXPR := EXPR ; -> STATEMENT EXPR ::= BOP EXPR ; -> STATEMENT EXPR ::= EXPR BOP ; -> STATEMENT EXPR ::= UOP ; -> STATEMENT EXPR ::= RHUOP ; -> STATEMENT These rules are all forms of the assignment statement. NOTICE that ALL forms of assignment REQUIRE a semicolon for termination. The standard assignment statement is given by the first rule. All of the other forms of assignment will be described in terms of the standard assignment. The standard assignment (first rule) means: Evaluate the righthand EXPR, and stuff that value into the lefthand EXPR. The lefthand and righthand EXPRs must be of the same type. Generally, the lefthand EXPR is just a variable. However, there are other EXPRs that can appear there. Each syntax rule specifies whether or not it may be used on the lefthand side of assignment statements. In the absence of any such statement, the syntax rule cannot be used on the lefthand side. Example (standard assignment): If P, P1, and P2 are variables of type POINT, then the assignment: P := P1 + P2 ; is meaningful. It evaluates the point P1+P2, the righthand EXPR, and stuffs that value into the lefthand EXPR, P. Similarly, if X and Y are REAL variables, then: X # Y := P1 + P2 ; is also meaningful. (The presentation of the BOP "#" states that it is meaningful on the lefthand side of assignments). As a result of this assignment, X winds up holding the x- coordinate of the point P1+P2, and Y winds up holding the y-coordinate of that sum. Each of the non-standard assignments is described now by a rewrite operation. The "::=" notation maps to the ":=" (standard) notation by copying the lefthand EXPR over to the righthand side. Let E1 and E2 be EXPRs, and B be a BOP. The assignment: 1) E1 ::= B E2 ; means E1 := (E1) B E2 ; Example: The assignment: I ::= + 1 ; means I := I + 1; This shorthand increments I. Similarly, the assignment: LIST ::= $> ELEMENT ; means LIST := LIST $> ELEMENT ; Either of these assignments right appends an element onto the list. Also: I ::= MIN J ; means I := I MIN J ; This says "I becomes no larger than J". 2) E1 ::= E2 B ; means E1 := E2 B (E1) ; Example: The assignment: I ::= 1 - ; means I := 1 - I ; Also, the following left appends an element onto a list: LIST ::= ELEMENT <$ ; (which is equivalent to: LIST := ELEMENT <$ LIST ; ) Now let U denote any UOP. 3) E1 ::= U ; means E1 := U (E1) ; Example: The assignment: I ::= - ; means I := - I ; and can be read as "negate I". Now let R denote any RHUOP. 4) E1 ::= R ; means E1 := (E1) R ; Example: "\ABS" is a RHUOP, and so: X ::= \ABS ; means X := X \ABS ; or X := ABS(X) ; In addition: The non-standard assignments involving unary operators (UOP and RHUOP) are generalized to allow any sequence of unary operators. That is, if U1, U2, ..., Un denote unary operators, then the general assignment: EXPR ::= U1 U2 ... Un ; means "apply U1 to the EXPR, then apply U2 to that result, then apply U3 to that result, ..., then finally apply Un to that result, and stuff this final result into the EXPR. Example: The assignment: X ::= \ABS - ; puts a non-positive number into X, X's negative ABSolute value. In addition: Any of these assignment statements, if enclosed in parentheses, passes as an EXPR (and not STATEMENT). The value of that EXPR is the value actually assigned. (See Section 22.1.6). For example, the following are legal EXPRs: (I:= 3;) (I::= + 1;) (I::= - ;) (I::= \ABS - ;) 22.2.2 Global Variables holding ID ; ID ; ... ID ; do STATEMENT endhold -> STATEMENT Each ID must denote a variable. This construct executes the STATEMENT and assures that each of the named variables appears unchanged upon completion. That is, even though the execution of the STATEMENT may assign new values into those variables, their old values will be restored upon completion of execution (the ENDHOLD). This construct is useful primarily for dealing safely with global variables. It provides for a "scoped" assignment of global variables. We can paraphrase a need for this construct: "I now have in mind a use for these global variables, although I don't know how they are presently being used. Therefore, I will use the HOLDING to provide insulation between my use of the globals and the present (unknown) use of those globals. When I'm done with them, (the ENDHOLD), they will appear to have been untouched to their present (unknown) users. " Example: Suppose we are operating in a context where the global variable ORIENTATION, a MATRIX, is meant to be applied to all POINTs that we are about to plot. Whenever a point is plotted, someone will incorporate this ORIENTATION matrix by plotting not the given POINT, but rather the transformed POINT: point \AT orientation (a point) Suppose now that we want to affect ORIENTATION so that for a limited period, all points going to the plotter will be transformed differently, say by the matrix NEW_ORIENTATION. We specify: HOLDING ORIENTATION ; DO ORIENTATION := NEW_ORIENTATION ; cause points to be plotted ENDHOLD This assures that all points will be plotted with the original ORIENTATION except for those points plotted during the reign of this HOLDING...ENDHOLD. Those points will be plotted with the orientation NEW_ORIENTATION instead. POINTs plotted before or after this program text will plot at the original ORIENTATION (not NEW_ORIENTATION). In addition: Each occurence of: ID ; in the HOLDING rules may be replaced by a general assignment statement, as long as the lefthand side of that assignment statement is just a variable (ID). For example, we can write: ID := EXPR ; in place of ID ; Example: Continuing with the ORIENTATION example shown above, we can rewrite that text more concisely: HOLDING ORIENTATION := NEW_ORIENTATION ; DO cause points to be plotted ENDHOLD 22.2.3 Decision Making if EXPR then STATEMENT fi -> STATEMENT if EXPR then STATEMENT else STATEMENT fi -> STATEMENT if EXPR then STATEMENT ef EXPR then STATEMENT ef EXPR then STATEMENT ... ef EXPR then STATEMENT fi -> STATEMENT if EXPR then STATEMENT ef EXPR then STATEMENT ef EXPR then STATEMENT ... ef EXPR then STATEMENT else STATEMENT fi -> STATEMENT This is the IF-THEN-ELSE construct for STATEMENTs. Each EXPR appearing here must be of type BOOLean. The first rule executes the STATEMENT if the EXPR yields TRUE, otherwise it does nothing. The second rule executes the first STATEMENT if the EXPR yields TRUE, otherwise it executes the second STATEMENT. The third rule evaluates each EXPR, in order, until an EXPR yields TRUE, at which point it executes the corresponding STATEMENT (following the THEN). If none of the EXPRs yields TRUE, then it does nothing. The keyword "ef" is short for "else if". The fourth rule is like the third, except that if all the EXPRs yield FALSE, then it executes the final "else" STATEMENT. The terminating FI is present to disambiguate for example the following, which is written without a FI: IF A < B THEN I:= 1; ELSE J:= 2; K:= 3; If "A<B" is true, we certainly set I to 1, but do we also set K to 3? That choice is dictated by the appearence of FI: IF A < B THEN I:= 1; ELSE J:= 2; FI K:= 3; versus IF A < B THEN I:= 1; ELSE J:= 2; K:= 3; FI The former always sets K to 3 whether or not A<B. The latter sets K to 3 only if A<B is false. goto EXPR NUMBER => STATEMENT NUMBER => STATEMENT ... NUMBER => STATEMENT endgoto -> STATEMENT The EXPR must be of type INTeger. This acts exactly like a big IF-THEN-ELSE construction. It chooses the STATEMENT that follows the literal number (NUMBER) matching the value yielded by the integer EXPR following the GOTO. If the GOTO EXPR has a value that matches none of the NUMBERs, then nothing is executed. A similar GOTO construct exists for EXPRs as well. In addition: You may substitute one occurence of "NUMBER" with the keyword "ELSE" to capture all values not covered by the NUMBERs. If you include an ELSE, some STATEMENT will always be chosen. NOTE: The NUMBERs are all non-negative NOTE: Given many clauses, this construct may be more efficient than a corresponding IF-THEN-ELSE construct. case ID of ID : STATEMENT ID : STATEMENT ... ID : STATEMENT endcase -> STATEMENT This is the ~variant CASE construct. It is described along with variant datatypes in Section 23.5.2 case EXPR of ID : STATEMENT ID : STATEMENT ... ID : STATEMENT endcase -> STATEMENT This is the ~scalar CASE construct. It is described along with the SCALAR datatype in Section 23.8. 22.2.4 Local Variables begin DECL STATEMENT end -> STATEMENT STATEMENTs, as well as EXPRs (Section 22.1.6) may be enclosed in a BEGIN...END along with variable declarations. The following is an example: BEGIN VAR I = INT; I:= 2; DO I:= I*I; REPEAT 5; WRITE(I); END The new variable I is made available to the STATEMENT (3 lines) within the BEGIN...END. 22.2.5 Looping do STATEMENT QUANTIFIER -> STATEMENT QUANTIFIER do STATEMENT end -> STATEMENT These two rules are semantically identical. Execute the STATEMENT once for each iteration caused by the QUANTIFIER. Note that the second rule, which allows you to specify the STATEMENT after the QUANTIFIER, ~requires the terminating END keyword. Example: The STATEMENT: DO CRLF; WRITE(I); FOR I FROM 1 TO 10; prints the numbers from 1 to 10, each preceded by a carriage- return line-feed (CRLF). The following specification does exactly the same thing: FOR I FROM 1 TO 10; DO CRLF; WRITE(I); END 22.2.6 Miscellaneous: STATEMENT STATEMENT -> STATEMENT In ICL, any sequence of STATEMENTs as a whole is a valid STATEMENT. Sequences of STATEMENTs don't need to be enclosed by anything, not even a BEGIN...END. For example, each of the following is a valid STATEMENT: I:= 2; DO I:= I*I; REPEAT 5; Together, this whole piece of text is also a valid STATEMENT. 22.3 QUANTIFIERs QUANTIFIERs cause looping. Ultimately, any QUANTIFIER is associated with a STATEMENT or an EXPR, so as to cause repeated execution of that STATEMENT or EXPR. A QUANTIFIER by itself is neither a STATEMENT nor EXPR. 22.3.1 Basic Quantifiers We first introduce basic QUANTIFIERs, some of which you may find in many languages. We then introduce ways to combine QUANTIFIERs into more complex QUANTIFIERs, and provide for the modification of any QUANTIFIER. repeat EXPR ; -> QUANTIFIER The EXPR must be of type INT. This QUANTIFIER causes that INTeger number of iterations. If the INTeger is less than or equal to zero, zero iterations occur. Note that the semicolon is required as part of the QUANTIFIER. while EXPR ; -> QUANTIFIER The EXPR must be of type BOOL. This QUANTIFIER causes an iteration while the EXPR yields TRUE. This QUANTIFIER causes zero iterations if the EXPR yields FALSE upon first evaluation. Only if the EXPR yields TRUE will there be another iteration. The QUANTIFIER causes no more iterations as soon as the EXPR yields FALSE. Note that the semicolon is required as part of the QUANTIFIER. until EXPR ; -> QUANTIFIER The EXPR must be of type BOOL. This QUANTIFIER causes ~another iteration until if finds the EXPR yielding TRUE. This QUANTIFIER always causes ~at ~least ~one ~iteration. It does not evaluate the EXPR until the second iteration. This quantifier is identical to the WHILE except that: a) it negates the EXPR, and b) it gives always one iteration. Note that the semicolon is required as part of the QUANTIFIER. for ID from EXPR to EXPR by EXPR in EXPR ; -> QUANTIFIER for ID from EXPR to EXPR by EXPR in* EXPR ; -> QUANTIFIER This is the ~arithmetic ~FOR quantifier. The ID must denote a variable whose type is either INTeger or REAL. The FROM-, TO-, and BY-EXPRs must be of the same type as the variable. The IN-EXPR must be of type INTeger always. Any subset of the four clauses (the FROM EXPR, TO EXPR, BY EXPR, and IN EXPR) may be omitted. Also, the clauses may appear in any order (with no change in meaning). Note that the semicolon is required as part of the QUANTIFIER. The from-EXPR denotes the value to be taken on by the variable for the first iteration. If absent, the variable takes on its present value for the first iteration. The other three clauses, TO, BY, and IN, imply various meanings dependent on their presence or absence. The in-EXPR, if present, specifies the number of iterations. The by-EXPR, if present, specifies the increment which will be applied to the variable for all non-first iterations. The to-EXPR, if present, specifies the value ~beyond ~which no more iterations will occur. The to-EXPR is ignored if both the by- and in- EXPRs are present. If the in-EXPR and the to-EXPR are present, but the by-EXPR is absent, then the increment is chosen so as to divide the interval from the FROM value to the TO value into IN sub-intervals. You get the ~left endpoint of each of those intervals. You do not get the right endpoint of the final sub-interval, the to-EXPR value, unless you put an asterisk following the keyword IN. If you do include that asterisk, you get IN+1 iterations. If you include only the to-EXPR, and not the by- nor in- EXPRs, the increment is + or - 1, +1 if TO is greater than FROM, -1 if TO is less than FROM. (IF TO equals FROM, then you get only one iteration). A summary of behavior based on the presence or absence of each of the BY, TO, and IN clauses follows. We specify the behavior by showing both the chosen increment and the total number of iterations: BY TO IN ! INCR COUNT -- -- -- ! ---- ----- . . . ! +1 infinity . . IN ! +1 IN . TO . ! + or - 1 1 + ABS( TO-FROM ) . TO IN ! (TO-FROM) / IN IN BY . . ! BY infinity BY . IN ! BY IN BY TO . ! BY 1 + (TO-FROM) / BY BY TO IN ! BY IN In case IN* is specified, the occurence of IN in the COUNT column should be IN+1. All arithmetic, including the divides, occur in the INTeger domain if the variable (ID) is of type INTeger, otherwise they occur in the REAL domain. Examples: FOR I FROM 1 TO 10 ; causes 10 iterations, with I taking on the values 1 thru 10. FOR I FROM 1 TO 10 BY 2 ; causes I to take on the values 1,3,5,7, and 9. FOR I FROM 1 BY 2 IN 12 ; causes 12 iterations, with I taking on the values 1,3,5,7,9,11,13,15,17,19,21,23 FOR I FROM 1 BY 2 IN* 12 ; causes 13 iterations, with I taking on the values 1,3,5,7, 9,11,13,15,17,19,21,23, and 25. FOR I FROM 1 ; causes infinitely many iterations, with I taking on the values 1,2,3,... (The utilitiy of such infinite QUANTIFIERs occurs in conjunction with the "&&" operator for QUANTIFIERs, which will be shown shortly). FOR I FROM 1 BY -2 ; causes infinitely many iterations, with I taking on the values 1,-1,-3,-5,-7,... FOR I FROM 10 IN 17 ; causes 17 iterations, with I taking on the values 10,11,12,..., 24,25, and 26. FOR R FROM 0 TO 1.0 IN 4 ; We presume R is a REAL variable. This QUANTIFIER causes 4 iterations, with R taking on the values 0, 0.25, 0.5, 0.75. FOR R FROM 0 TO 1.0 IN* 4 ; We presume R is a REAL variable. This QUANTIFIER causes 5 iterations, with R taking on the values 0, 0.25, 0.5, 0.75, and 1.0. Example Using The QUANTIFIER: The following list of points denotes an N-sided circle (regular polygon), where N is given: { COLLECT COS(T) # SIN(T) FOR T FROM 0 TO TWO_PI IN N; } T takes on the values 0 thru TWO_PI in N even steps. That is, it takes on the ~left endpoint of each of N even intervals. The COS and SIN produce a point on the unit circle upon each iteration. (The ~COLLECT construction for lists appears in Section 23.3). The following list of points denotes the same, except that the first point appears again at the very end. T finally takes on the value TWO_PI, which produces the same point as did the first iteration, when T=0. { COLLECT COS(T) # SIN(T) FOR T FROM 0 TO TWO_PI IN* N; } NOTE: All the EXPRs in the clauses are evaluated once, in the preparation for the first iteration. Thus, the body of your loop cannot change their values midstream. (The order of evaluation of those initial EXPRs is uncertain). Also, the variable (the ID) is set at each iteration. Thus, even if you assign new values into that variable from within the body of the loop, this will ~not affect values during subsequent iterations. One can count on the values in the iterations variable(s) upon completion of the quantifier. They hold the values that existed upon the last iteration. for EXPR $e EXPR ; -> QUANTIFIER This QUANTIFIER steps thru elements in a list. The "$e" reads as ~is ~an ~element ~of. The second EXPR must be a list, and the first EXPR must be of that list's ~element type. (Section 23.3 introduces lists). This QUANTIFIER causes one iteration per element in the list. Example: Suppose we make the type declaration: TYPE LIST = { INT } ; and declare two variables: VAR L = LIST ; I = INT ; The QUANTIFIER: FOR I $e L ; which reads ~FOR ~I ~an ~element ~of ~L, sets I to each element in L, causing one iteration for each value. For example, the QUANTIFIER: FOR I $E {1;2;5;1;3} ; sets I to the numbers 1,2,5,1, and 3, in that order, and causes one iteration for each of those values. This "$e" QUANTIFIER is a special case of the following, "$c" QUANTIFIER. for EXPR $c EXPR ; -> QUANTIFIER This QUANTIFIER steps thru lists in a more general manner than does the "$e" QUANTIFIER just shown. The "$c" reads as ~contained ~in. We call this the official form. The "$e" FOR QUANTIFIER is a special case, and is rendered in terms of the official "$c" QUANTIFIER as follows: for EXPR1 $e EXPR2 ; becomes: for { EXPR1 } $c EXPR2 ; The "$C" operator acts exactly like our familiar assignment operator ":=". By itself, it causes only one iteration. It stuffs the value of the righthand EXPR into the lefthand EXPR and gives exactly one iteration. All looping, the emergence of more than one iteration, is dictated entirely by the lefthand EXPR. For example, the abbreviated "$e" notation causes multiple iterations by enclosing its given lefthand EXPR in curly brackets. It is those curly brackets around the lefthand EXPR that cause the original lefthand EXPR to be assigned "each element in" the righthand EXPR. The official "$c" QUANTIFIER requires that the two EXPRs on either side of the "$c" be of the same type, just as our assignment statement (":=") requires. This is consistent with our description of the "$e" QUANTIFIER. That is, the QUANTIFIER: FOR X $e Y ; requires X to be of the element type of the list Y. The EXPR: { X } is a list like Y. Thus, the official form: FOR { X } $C Y ; does indeed have the same (list) type on either side of the $C. Example: Our previous example presented with the "$e" QUANTIFIER: FOR I $E L ; is equivalent to the form: FOR { I } $C L ; The Lefthand EXPR: ~Looping ~Targets What forms can the lefthand EXPR take on? The lefthand EXPR can be any EXPR that is meaningful on the lefthand side of an assignment statement. In this simple case, the "$c" QUANTIFIER acts exactly like an assignment statement, and causes exactly one iteration. However, the lefthand EXPR can be formed by some operators that are not valid on the lefthand side of an assignment. In general, the lefthand EXPR must make sense in the ~looping ~target domain, a domain created especially for use in this FOR QUANTIFIER. What is a looping target? The set of all looping targets is formed by first including all target forms, that is, all EXPRs that are valid on the lefthand side of an assignment statement: 1) target -> looping target This transformation causes no additional iterations. A looping target may be formed by enclosing other looping targets within curly brackets: 2) { looping target ; ... ; looping target } -> looping target We have seen an example of this form already, where only one element appears between the curly brackets. The "$e" gets its meaning by using this form. This formation of a looping target contributes one dimension of iteration. The ~given ~list is the one that appears to the right of the "$c". The first iteration sets the first looping target to the first element in the given list. It also assigns to the second looping target the second element in the list, etc. The second iteration sets the first looping target now to the second element in the given list. It also assigns to the second looping target the third element in the given list, etc. Examples: Suppose we declare the following types and variables (See Section 23.3 for declaring lists): TYPE LIST = { ELEMENT } ; VAR L, L1 = LIST ; E1,E2,E3 = ELEMENT ; The QUANTIFIER: FOR { E1 } $C L ; causes one dimension of iteration, setting E1 to each element in L (in order). The QUANTIFIER: FOR { E1 ; E2 } $C L ; causes one dimension of iteration, setting E1 and E2 to adjacent elements in L. That is, the iterations set E1 and E2 as follows: First iteration: E1 = L[1] and E2 = L[2] Second iteration: E1 = L[2] and E2 = L[3] Third iteration: E1 = L[3] and E2 = L[4] ... Last iteration: E1 = L[n-1] and E2 = L[n] where n is the number of elements in L. This is a total of n-1 iterations. The QUANTIFIER: FOR { E1 ; E2 ; E3 } $C L ; causes one dimension of iteration, setting E1, E2, and E3 to triples of adjacent elements in L. Whereas the previous QUANTIFIER causes n-1 iterations, this QUANTIFIER causes n-2 iterations. (The last iteration has E1 holding the n-2'th element of L). This curly bracket formation of looping targets may include an asterisk ("*") following any one of the semicolons. The asterisk indicates that the elements (looping targets) specified to the right of that asterisk may ~wrap ~around back to the beginning of the given list. Example: The QUANTIFIER: FOR { E1 ;* E2 } $C L ; causes one dimension of iteration. Like the previous example without the asterisk, it sets E1 and E2 to adjacent elements contained in L. However, unlike the previous example, we get an extra iteration at the end. The final iteration sets E1 to the last element in L, and E2 to the first element in L. The E2 has thus wrapped around back to the beginning of the list. This is a total of n iterations. This quantifier is very useful to enumerate the ~edges of a polygon represented by a list of vertices. (L would be a list of POINTs, the vertices, and E1 and E2 would be the two POINT variables that represent the two endpoints of each edge). The QUANTIFIER: FOR { E1 ;* E2 ; E3 } $C L ; causes one dimension of iteration. Here, each of E2 and E3 is allowed to wrap around to the beginning of the list L. The final iteration sets E1 to the last element in L, E2 to the first element in L, and E3 to the second element in L. The QUANTIFIER: FOR { E1 ; E2 ;* E3 } $C L ; differs from the previous example only in the placement of the asterisk. Here, only E3 is allowed to wrap around, and hence the final iteration sets E1 to the second to last element in L, sets E2 to the last element in L, and E3 to the first element in L. We introduce now another form of looping target. Whereas the previous form gave access to element in a list, this next form delivers ~tails of a given list. The looping target form: 3) looping target - -> looping target stuffs into the left looping target ~each successive tail of the given list, starting with the entire list, then with the list less its first element, etc. The final tail delivered with this construct is a list of length one, the final tail which contains only the last element in the given list. Example: The QUANTIFIER: FOR L1 - $C L ; sets L1 to each tail of L. We get iterations as follows: First iteration: L1 is L Second iteration: L1 is L[2-] Third iteration: L1 is L[3-] ... Last iteration: L1 is L[n-] where n is the length of the given list L. (For the "L[2-]" notation, see Section 23.3. It reads as "the tail of L starting from the second element"). That is, on the first iteration, L1 has length n, and on the second iteration, L1 has length n-1, etc. 22.3.2 Quantifier Combinations QUANTIFIER && QUANTIFIER -> QUANTIFIER The "&&" causes two QUANTIFIERs to step in unison, also known as ~lock-stepping. This combined QUANTIFIER stops as soon as either one of the given QUANTIFIER stops. In other words, the number of iterations caused by the combined QUANTIFIER is the ~minimum of the numbers of iterations caused by each of the given QUANTIFIERs. Because of this early termination, one of the quantifiers can be a non-terminating quantifier. Example: The QUANTIFER: FOR E1 $E L1 ; && FOR E2 $E L2 ; sets E1 and E2 to corresponding elements in the lists L1 and L2. The first iterations sets E1 to the first element of L1, and E2 to the first element in L2. The second iteration sets E1 to the second element of L1, and E2 to the second element of L2, etc. This QUANTIFIER causes as many iterations as the length of the shorter list (L1 or L2). The QUANTIFIER: FOR E1 $E L1; && FOR E2 $E L2; && FOR E3 $E L3; sets E1, E2, and E3 to corresponding elements in all three lists L1, L2, and L3. QUANTIFIER !! QUANTIFIER -> QUANTIFIER The "!!" causes two QUANTIFIERs to ~nest, the second nested within the first. That is, for each iteration caused by the first given QUANTIFIER, step thru the entirety of the second QUANTIFIER. The number of iterations caused by the combined QUANTIFIER is the ~product of the numbers of iterations caused by each of the given QUANTIFIERs. Example: The QUANTIFIER: FOR E1 $E L1 ; !! FOR E2 $E L2 ; sets E1 and E2 to all possible pairs of elements where E1 is in L1 and E2 is in L2. We often call the "!!" operator the ~cartesian ~product operator. As in this example, it sets the pair E1 and E2 to each element in the cartesian product of the sets L1 and L2. Example: Suppose LL is a list of lists, e.g., as declared by: TYPE LIST_OF_LISTS = { LIST } ; VAR LL = LIST_OF_LISTS ; The QUANTIFIER: FOR L $E LL ; !! FOR E1 $E L ; sets L to each list in LL, and E1 to each element in that list L. This QUANTIFIER thus delivers individual elements from a list of lists. QUANTIFIER then QUANTIFIER -> QUANTIFIER The "then" has the second QUANTIFIER start up right after the first QUANTIFIER stops. The number of iterations caused by the combined QUANTIFIER is the ~sum of the numbers of iterations caused by each of the given QUANTIFIERs. Examples: The QUANTIFIER: FOR E1 $E L1 ; THEN FOR E1 $E L2 ; sets E1 to each element of L1 and then to each element of L2. It is logically equivalent to: FOR E1 $E (L1 $$ L2) ; which sets E1 to each element in the list formed by concatenating the lists L1 and L2. The QUANTIFIER: FOR E1 $E L1 ; THEN FOR E1 FROM 1 TO 10; sets E1 to each element of L1 and then to each of the numbers 1 thru 10. Finally, when more than one of these binary operators is used to form a QUANTIFIER, the grouping, or "binding order" is uncertain. However, the next rule allows you to put parentheses around any QUANTIFIER, and thus dictate explicitly the grouping of QUANTIFIERs. ( QUANTIFIER ) -> QUANTIFIER This rule is semantically an identity, but it allows you to specify how QUANTIFIERs are grouped together. Example: The QUANTIFIER: FOR X FROM 1 TO 5; sets X to the horizontal set of points (X#0) shown in figure 22.3(a). The QUANTIFIER: FOR Y FROM 1 TO 5; sets Y to the vertical set of points (0#Y) shown in figure 22.3(b). The combined QUANTIFIER: FOR Y FROM 1 TO 5; !! FOR X FROM 1 TO 5; sets X and Y so that X#Y forms the two-dimensional array of points shown in figure 22.3(c). Let's take this combined QUANTIFIER and make it lock-step with the new quantifier: FOR I FROM 1 BY 1; The combination: ( FOR Y FROM 1 TO 5; !! FOR X FROM 1 TO 5; ) && FOR I FROM 1 BY 1; sets the variables X, Y, and I so as to produce figure 22.3(d), if we write I at the location X#Y. In contrast, let's put in the parentheses differently, as in: FOR Y FROM 1 TO 5; !! ( FOR X FROM 1 TO 5; && FOR I FROM 1 BY 1; ) Now, the variables X, Y, and I are set so as to produce figure 22.3(e). The "FOR I" quantifier lock-steps with the "FOR X" quantifier, and both the X and I quantifiers do their thing for each iteration caused by the "FOR Y" quantifier. 22.3.3 Quantifier Modifiers Following are ways to ~modify a QUANTIFIER. They are all of the form: QUANTIFIER ~modifier -> QUANTIFIER The modifiers each binds to the smallest QUANTIFIER to its left. QUANTIFIER with EXPR ; -> QUANTIFIER This WITH modifier filters out iterations from the given QUANTIFIER. The resulting QUANTIFIER may have fewer iterations. The EXPR must be of type BOOL. The resulting QUANTIFIER shows only those iterations for which the with-EXPR yields TRUE. Iterations of the given QUANTIFIER which cause the EXPR to yield FALSE are omitted. Example: The QUANTIFIER: FOR E1 $E L1; WITH E1.X > 5 ; sets E1 to all elements of L1 for which the EXPR E1.X > 5 is TRUE. It therefore sets E1 to all elements of L1 whose x-coordinates exceed 5. (This example presumes that L1 is a list of POINTs, and that E1 is a POINT, whose x-coordinate is acquired by the notation "E1.X"). This WITH construct can be read as the mathematician's "...such that...". QUANTIFIER initially STATEMENT ; -> QUANTIFIER Cause the STATEMENT to be executed ~before starting up the given QUANTIFIER QUANTIFIER first_do STATEMENT ; -> QUANTIFIER Execute the STATEMENT upon the ~first iteration of the given QUANTIFIER. That is, after the given QUANTIFIER prepares for the first iteration, execute the STATEMENT, before the loop body is entered. QUANTIFIER other_do STATEMENT ; -> QUANTIFIER Execute the STATEMENT upon all non-first iterations of the given QUANTIFIER. That is, after the QUANTIFIER prepares for each non- first iteration, execute the STATEMENT. QUANTIFIER each_do STATEMENT ; -> QUANTIFIER Execute the STATEMENT uopn each iteration caused by the given QUANTIFIER. That is, after the QUANTIFIER prepares for each iteration, execute the STATEMENT. Notice that: QUANTIFIER first_do STATEMENT ; other_do STATEMENT ; is equivalent to QUANTIFIER each_do STATEMENT ; if all three STATEMENTs here are identical. QUANTIFIER finally_do STATEMENT ; -> QUANTIFIER Execute the STATEMENT ~after the QUANTIFIER stops. This does ~not execute the STATEMENT upon the QUANTIFIER's last iteration, rather it causes the STATEMENT to be executed ~after the last iteration. You can imagine that the QUANTIFIER tries to cause another iteration, but finds that there are no more. At that point in time, the STATEMENT is executed. Example: The following STATEMENT sums up the integers from 1 to 10: FOR I FROM 1 TO 10; INITIALLY ANSWER:= 0; ; DO ANSWER::= + I ; END The QUANTIFIER used here: FOR I FROM 1 TO 10; INITIALLY ANSWER:= 0; ; sets I to 1 thru 10, but first sets ANSWER to 0. The body of the loop sums I into ANSWER on each iteration. (The appearence of two semicolons after the "0" is correct. The first semicolon belongs to the assignment statement: ANSWER:= 0 ; The second semicolon is part of the INITIALLY construct, as per the rule: QUANTIFIER initially STATEMENT ; -> QUANTIFIER ). This loop can be written equivalently as: ANSWER:= 0 ; FOR I FROM 1 TO 10; DO ANSWER::= + I; END The advantage of using the INITIALLY construct is that ANSWER's initialization is part of the quantifier. As just rendered without the INITIALLY, some programmer might overlook this relationship, and erase or move that initial assignment to ANSWER. In ICL, this same loop can be written most simply as: ANSWER:= + I FOR I FROM 1 TO 10; ; (The appearence of two semicolons following the 10 is correct. The first semicolon is part of the FOR-quantifier, and the second is part of this overall assignment statement). Example: The following EXPR uses INITIALLY to set a variable C to a value used in all iterations: + SIN(X*C) FOR X $E L; INITIALLY C:= SQRT(Y+Z); ; Example: The following quantifier sets R to the square-root of each member in L: FOR X $E L; EACH_DO R:= SQRT(X);; Example: The following quantifier causes two iterations, setting K to R and then setting K to -R: REPEAT 2; FIRST_DO K:= R;; OTHER_DO K:= -R;; We can combine this quantifier with our previous quantifier as follows: FOR X $E L; EACH_DO R:= SQRT(X);; !! REPEAT 2; FIRST_DO K:= R;; OTHER_DO K:= -R;; This sets K to both the positive and negative square-roots of each element in L. We cause two iterations (REPEAT 2;) for each X in L, via the "!!" notation. This complex quantifier can be rendered equivalently as: FOR X $E L; !! REPEAT 2; FIRST_DO K:= SQRT(X);; OTHER_DO K:= -K;; Example: The following STATEMENT writes out the numbers 1 thru 10 with commas ~between the numbers: FOR I FROM 1 TO 10; OTHER_DO WRITE(',');; DO WRITE(I); END That is, a comma precedes each number, on all but the first iteration. Example: The following EXPR tells whether each element in L1 is less than its corresponding element in L2: ALWAYS X < Y FOR X $E L1; && FOR Y $E L2; That is, for X and Y holding corresponding elements in L1 and L2, is X always less than Y? Example: The following QUANTIFIER sets X to all positive elements in L1 and then to all negative elements in L2: FOR X $E L1; WITH X>0 ; THEN FOR X $E L2; WITH X<0 ; Example: Imagine that the positive elements in L1 correspond to the positive elements in L2. The following QUANTIFIER sets X and Y to corresponding positive elements: FOR X $E L1; WITH X>0; && FOR Y $E L2; WITH Y>0; Example: The following EXPR delivers the sum of the products of corresponding elements in L1 and L2: + X*Y FOR X $E L1; && FOR Y $E L2; Example: Given two sets S and T, the following EXPR delivers the minimum difference between all elements in S against all elements in T: MIN ABS(X-Y) FOR X $E S; !! FOR Y $E T; The following delivers the same, where only the positive elements in S and T are considered: MIN ABS(X-Y) FOR X $E S; WITH X>0 ; !! FOR Y $E T; WITH Y>0 ; Example: The following STATEMENT writes both the positive and negative square- roots of the elements in L, each on a separate line: ( FOR X $E L; !! REPEAT 2; FIRST_DO Y:= SQRT(X);; OTHER_DO Y:= -Y;; ) DO CRLF; WRITE(Y); END (The CRLF writes out a carriage-return and line-feed). (The parenthese around the two quantifiers are optional). Our next example does the same, but writes at the beginning of each line the line number (1,2,3...): ( FOR X $E L; !! REPEAT 2; FIRST_DO Y:= SQRT(X);; OTHER_DO Y:= -Y;; ) && FOR I FROM 1 BY 1; DO CRLF; WRITE(I); TAB; WRITE(Y); END Notice how easily we introduced the text: && FOR I FROM 1 BY 1; to our general QUANTIFIER, so as to deliver a line number for each iteration. Even though this FOR quantifier by itself causes infinitely many iterations, the large quantifier (in parentheses) preceeding the "&&" causes only finitely many iterations, and so as a whole, this entire quantifier causes only finitely many iterations. Suppose we wanted to consider only positive elements in L. We introduce the text shown italicized: ( FOR X $E L; ~WITH ~X>0 ~; !! REPEAT 2; FIRST_DO Y:= SQRT(X);; OTHER_DO Y:= -Y;; ) && FOR I FROM 1 BY 1; DO ... END Our line numbers (I) still correspond to each line written, although there might now be fewer lines. In contrast, the following rendition omits the same lines, but also omits those lines' line numbers: ( ( FOR X $E L; !! REPEAT 2; FIRST_DO Y:= SQRT(X);; OTHER_DO Y:= -Y;; ) && FOR I FROM 1 BY 1; ) ~WITH ~X>0 ~; DO ... END We have moved the WITH clause so as to encompass now also the FOR-I quantifier. The WITH clause here omits entire lines ~including their line numbers. We can get the following output: 1 .2786 2 -.2786 5 .331 6 -.331 (Here, we imagine that the second element in L is not positive, and hence we omit lines 3 and 4). In the former example, we would get: 1 .2786 2 -.2786 3 .331 4 -.331 Example: The following QUANTIFIER sets X to all elements in S, and Y to all elements in T which are greater than X: FOR X $E S; !! FOR Y $E T; WITH Y>X ; Example: The following EXPR uses that QUANTIFIER, delivering the smallest difference between elements in S and T where the element in T is greater than the element in S: MIN Y-X FOR X $E S; !! FOR Y $E T; WITH Y>X ; The following EXPR delivers the apple whose weight to price ratio is maximized: PICK APPLE MAXIMIZING WEIGHT(APPLE) / PRICE(APPLE) FOR APPLE $E APPLES; The next EXPR yields a similar apple, but this time we consider only apples whose prices are less than 1: PICK APPLE MAXIMIZING WEIGHT(APPLE) / PRICE(APPLE) FOR APPLE $E APPLES; WITH PRICE(APPLE) < 1; 22.4 DECLARATIONs Declarations serve to ~augment the linguistic universe. DECLARATIONs can introduce new types, variables, functions, and coercions. 22.4.1 Type Declaration: type ID = TYPEX ; -> DECLARATION This declares a new type. The ID is the name for the new type, and the TYPEX is the specification of the new type. Example: TYPE INTEGERS = { INT } ; INTEGERS now denotes the type list of INTegers. 22.4.2 Variable Declaration: var ID , ID , ... , ID = TYPEX ; -> DECLARATION This declaration introduces new variables. Each ID in each list of IDs is declared to be a new ~variable of type TYPEX. (Read this as: var ID, ID, ..., ID ~each ~is = TYPEX ; ) For example, the following declaration(s) create new variables: VAR AGES , HEIGHTS = INTEGERS ; SEX = BOOL ; DATES = INTEGERS ; Each of AGES, HEIGHTS, and DATES is a new variable of type INTEGERS. As this example shows, within a sequence of VAR declarations, the word VAR may be omitted on all but the first line. Each declared variable, say X, is now a valid EXPR, e.g.,: x -> EXPR The type of the EXPR is the type just now associated with the new variable X. This EXPR is valid also on the lefthand sides of assignment statements. 22.4.3 Function Declarations define ID ( ID : TYPEX ID : TYPEX ... ID : TYPEX ) = TYPEX : EXPR enddefn -> DECLARATION This declares a new function. The name of the function follows the word DEFINE. The parameters of the function appear between the parentheses. Each parameter is denoted by a variable name (the ID) and the type of that parameter (the TYPEX). Following the "=", the TYPEX denotes the type of this function's result. The IDs specified in the input parameters become variables that hold the actual input values given when this function is called. Those variables may be used within the body of the function, the EXPR. The function body (EXPR) must be of the type specified as this function's result's type, the TYPEX following the "=". If within the EXPR you assign new values to any of the input parameters, this will have ~no effect from the point of view of the caller of this function. In other words, input parameters are always passed ~by ~value (Section 19.10.1). (Within this function body, any such assignment does affect the variable, as you would expect. In fact, each input variable is really a local variable that has an initial value already, the value passed in by the caller). Example: The following declares a function POWER: DEFINE POWER( X:REAL EXPONENT:INT ) = REAL: * X REPEAT EXPONENT; ENDDEFN This function has two input parameters, a REAL and an INT, in that order. This function's result is of type REAL (see the "="). The body of this function multiplies X by itself EXPONENT many times. The EXPR uses the input variables X and EXPONENT. In general, the declaration: DEFINE NAME ( ID(1):TYPEX(1) ... ID(k):TYPEX(k) ) = TYPEX(0): EXPR ENDDEFN effectively adds the rule of grammar: name ( ~TYPEX(1) , ... , ~TYPEX(k) ) -> ~TYPEX(0) This rule supports the calling of this function. It means that our example POWER function introduces the rule: power( ~REAL , ~INT ) -> ~REAL ---------------- Parentheses in previous paragraph around "1", ---------------- nad "0" and "k" mean subscripting! -------------------- If there are only two input parameters, we also effectively introduce the rule: ~TYPEX(1) \name ~TYPEX(2) -> ~TYPEX(0) Thus, our example function, which takes in two parameters, also introduces the rule: ~REAL \power ~INT -> ~REAL ---------------- Parentheses in previous paragraph mean subscripting! --- If there is only one input parameter, we also effectively introduce the rule: ~TYPEX(1) \name -> ~TYPEX(0) ---------------- Parentheses in previous paragraph mean subscripting! --- The actual syntax rules that support these notations are: ID ( EXPR , EXPR , ... , EXPR ) -> EXPR \ ID -> BOP \ ID -> RHUOP In addition: Each of the "ID:TYPEX"s appearing in these rules may also be of the form: ID , ID , ... , ID : TYPEX This is a shorthand form that represents more than one input parameter, all of which have the same type. For example, the following two function declarations are absolutely equivalent: DEFINE SUM( I:INT J:INT ) = INT: I+J ENDDEFN and DEFINE SUM( I,J: INT ) = INT: I+J ENDDEFN Note that the order of parameter specification is important. That order is assumed by the caller of the function. 22.4.3.1 Polymorphism Note that ICL is a ~polymorphic language. This means that you may define two or more functions of the same name, as long as their input and output types provide some distinction. For example, we can define the following two functions: DEFINE DISTANCE( A,B: REAL ) = REAL: ABS( A-B ) ENDDEFN DEFINE DISTANCE( A,B: POINT ) = REAL: SQRT( (A.X-B.X)^2 + (A.Y-B.Y)^2 ) ENDDEFN Both of these functions go by the name DISTANCE, but they are distinguished in that one takes in POINTs whereas the other takes in REALs. When you call DISTANCE, one or the other of these two functions will be called; the choice will be based upon the types of the parameters you pass in that call. For example, if you say: WRITE( DISTANCE( 5 , 6 ) ) ; you will see "1.0" on your terminal, but if you say: WRITE( DISTANCE( 1#2 , 4#6 ) ) ; you will see "5.0" printed on the terminal. 22.4.3.2 Variations On The Function Declaration The following three rules are variations on the one function declaration rule just shown. This next rule declares a function that returns no value: define ID ( ID : TYPEX ID : TYPEX ... ID : TYPEX ) : STATEMENT enddefn -> DECLARATION Notice that the function body is a STATEMENT, not a value (EXPR). Also note that a colon follows the close parenthesis. Compared to our first function declaration rule, we have dropped the "=TYPEX" following the close parenthesis. This kind of function without a resulting value, is often called a ~procedure. ICL provides only one way to call a procedure: ID ( EXPR , EXPR , ... , EXPR ) ; -> STATEMENT This is identical to the notation for calling functions that deliver values, except that a terminating semicolon is required. This notation forms a STATEMENT instead of an EXPR. (The terminating semicolon is present so as to look like the assignment statement, which also ends in a semicolon). The remaining rules declare functions and procedures that take no inputs at all: define ID = TYPEX : EXPR enddefn -> DECLARATION define ID : STATEMENT enddefn -> DECLARATION These are like the first two rules except that the parentheses and everything between them is omitted. We call these ~parameterless functions (procedures). You call a parameterless function that returns a value just by specifying the function's name, i.e.: ID -> EXPR You call a parameterless procedure (that returns no value) by specifying the name and then a semicolon: ID ; -> STATEMENT Example: The following declares a parameterless function that returns a value: DEFINE RANDOM_NUMBER = REAL: some EXPR ENDDEFN You call this function via: RANDOM_NUMBER RANDOM_NUMBER denotes a REAL value. Example: The following declares a parameterless procedure: DEFINE CRLF : some STATEMENT ENDDEFN You call this procedure via: CRLF ; We chose to require a semicolon following procedure calls so as to match our most popular STATEMENT, the assignment statement. 22.4.3.3 Coercion Declarations let ID : TYPEX become TYPEX by EXPR enddefn -> DECLARATION This declares a new coercion. A coercion is a function, without a name, that takes in one parameter and yields a value. Unlike functions, you never explicitly call a coercion. (There is no name with which to call it)! The ICL compiler determines where to call which coercions based on the requirements of context. ICL always applies a minimum number of coercions over your program text, in its effort to make sense of your program within the domain of datatypes. For example, we can tell the ICL compiler that "any INTeger may be viewed also as a REAL" by writing: LET I:INT BECOME REAL BY FLOAT(I) ENDDEFN Having made this declaration, we can call our function DISTANCE (defined earlier) even if we specify INTegers, say, the INTeger variables I and J: WRITE( DISTANCE( I , J ) ) ; This program text requires two applications of our new coercion so that each of I and J can be interpreted as a REAL, prior to calling the DISTANCE function defined for REALs. Of course, ICL worries about all this for you; you don't have to say any more than what appears here. You can declare coercions between any two types, without restriction. You can even declare the following coercion as well as the one just shown: LET X:REAL BECOME INT BY FIX(X) ENDDEFN Although this last coercion might be objectionable, as it loses information, there are examples where two-way pairs of coercions offer some profound capabilities concerning program maintenance (Section 23.5.3.2). Another example coercion follows, which lets a REAL be viewed as a POINT (complex number): LET X:REAL BECOME POINT BY X#0 ENDDEFN The given REAL becomes the x-coordinate of the result, and the y- coordinate is zero. This is consistent with our view of POINTs as complex numbers. The coercion: let ID : TYPEX1 become TYPEX2 by EXPR ; introduces simply the rule of grammar: ~TYPEX1 -> ~TYPEX2 22.4.4 Miscellaneous DECLARATIONs DECLARATION DECLARATION -> DECLARATION (left-to-right) This indicates that any sequence of DECLARATIONs is itself a valid DECLARATION. Thus, for example, the following text can be seen as a single DECLARATION: TYPE INTEGERS = { INT } ; VAR NUMBERS = INTEGERS ; DEFINE F( X:REAL ) = REAL: ... ENDDEFN DEFINE G( X:INT ) = POINT: ... ENDDEFN The order of declarations put together this way is always irrelevant. For example, F can reference G even though G is defined later. 22.5 The Grouping Of DECLARATIONs Into UNITs Of Compilation Programmers deliver DECLARATIONs. They deliver function and coercion declarations, type declarations, and global variable declarations. The wealth of these contributions is realized by calling functions, creating and examining instances of the new types, and/or placing values in and reading values out of the new global variables. As a system grows, as the number of declarations increases, it becomes necessary to organize or group declarations. Declarations may be entered into files. Each file may contain many declarations. ICL reads one file at a time, and compiles all declarations in the file at once. Each file containing declarations becomes known to ICL as a ~unit, and ICL compiles one unit at a time. It is possible to ~plug ~in, or ~include any subset of units. You can use all declarations within that subset of units. Units not included are inaccessible. Their declarations are invisible. Thus for example, if you want the coercion from REAL to INT, you INCLUDE the unit containing that declaration, otherwise, you don't include that unit. Beyond the notations of ICL shown so far, we introduce basically two more notations. The first meaningful line in a file containing declarations should be: unit ID : The ID gives a name to this unit. It is by this name that the declarations contained in this file will be made available to others. In another file, one gains access to the declarations in this unit by using a second notation, saying: include ID ; This ~include stands for all the declarations in the named unit (ID). For example, here is a unit that delivers three declarations: UNIT ABSOLUTE_VALUE : DEFINE ABS(I:INT)=INT: IF I<0 THEN -I ELSE I FI ENDDEFN DEFINE ABS(R:REAL)=REAL: IF R<0 THEN -R ELSE R FI ENDDEFN DEFINE ABS(P:POINT)=REAL: SQRT( P.X^2 + P.Y^2 ) ENDDEFN Now, by INCLUDing unit ABSOLUTE_VALUE, you can use these three ABS functions. (It is certainly not required that all function names in a unit be the same, although this example happens to do so). In another unit, say MATH_1, the three ABS functions may be used, as one is in: UNIT MATH_1 : INCLUDE ABSOLUTE_VALUE ; DEFINE CLOSEST_TO_ORIGIN( PS: SET_OF_POINTS ) = POINT: BEGIN VAR P = POINT ; PICK P MINIMIZING ABS(P) FOR P $E PS; END ENDDEFN This unit MATH_1 includes ABSOLUTE_VALUE so as to gain access to the function ABS. ~Includes cannot be circular. That is, if unit A includes unit B, then unit B may ~not include unit A. The contents of a file of declarations is formed just as described via the following rules of grammar. These new rules produce the new part-of-speech UNIT_SPEC: unit ID : -> UNIT_SPEC include ID, ID, ..., ID ; -> UNIT_SPEC Of course, DECLARATIONs may be part of a unit's specification, and so we include the rule: DECLARATION -> UNIT_SPEC Any sequence of these three forms of UNIT_SPECs makes up a unit, as is supported by the rule: UNIT_SPEC UNIT_SPEC -> UNIT_SPEC The DECLARATION may include the declaration of variables, variables other than those declared within functions. For example, consider the following unit that contains all three kinds of declaration: UNIT GENERIC_OUTPUT: TYPE OUTPUT_DEVICE = //(CHAR)\\ ; "Type declaration" VAR THE_OUTPUT_DEVICE = OUTPUT_DEVICE; "Variable decl" DEFINE OUTPUT( C: CHAR ) : "Function declaration" <*THE_OUTPUT_DEVICE*>(C); ENDDEFN The variable THE_OUTPUT_DEVICE is declared in no function, and hence it is a ~global ~variable. That variable can be accessed by anybody who INCLUDEs this unit GENERIC_OUTPUT. You may wish to specify also a STATEMENT, outside of any function, which will perform something as soon as compilation is complete, like initializing a global variable. For example, following the VAR declaration, we might like to assign an initial value into THE_OUTPUT_DEVICE, as in: UNIT ... TYPE ... VAR ... THE_OUTPUT_DEVICE:= //(C:CHAR) WRITE(C) \\ DEFINE ... This assignment is carried out first thing once this unit is compiled. Our assignment makes THE_OUTPUT_DEVICE send characters to the terminal (because we used WRITE). Such initializing STATEMENTs are admitted into unit specifications via the rule: STATEMENT -> UNIT_SPEC 22.5.1 The PRIVATE And PUBLIC Parts Of A UNIT We introduce now a dichotomy into the contents of a unit. We introduce the optional "PRIVATE" part, which may coexist with the familiar "PUBLIC" part. Thus far in our presentation of units, we've assumed that the entirety of a unit's specification resides in the PUBLIC part of the unit. By default, all parts of a unit in fact reside in the PUBLIC section, and so everything shown so far remains entirely valid. Before we show how to create a PRIVATE part in a unit, let's motivate the existence of a least some kind of dichotomy. The author of a unit experiences an inevitable conflict: On one hand, the author wants to provide a brief and simple set of bullet- proof functions for use by people who might INCLUDE this unit. On the other hand, the author generally needs access to other functions and units in order to write the definitions for these functions. For example, the author may wish to define some "intermediate" functions to aid in the definitions of the functions desired originally. The author needs such "intermediate" functions but simultaneously abhores the thought of giving users access to them. Such intermediate functions are very often necessarily not bullet- proof; they may offer "too much" flexibility and pose great danger if used by anybody less experienced in the application than the author. Not only might the author prefer to render a PRIVATE set of "intermediate" functions, but the author might wish also to INCLUDE privately a set of units, or possibly declare privately some global variables. A private global is indeed a global variable, but it may be accessed only within the unit where it's declared. Rendering items ~private reduces name conflicts within large projects. That is, to aid in the definition of the bullet-proof functions desired originally, the author may need to INCLUDE some (dangerous) units but may simultaneously in all good conscience need to supress their accessability to the (naive) users of the author's new services. 22.5.2 The Keywords PRIVATE And PUBLIC Any declaration can be removed from the public section and be placed into the private section by inserting the keyword PRIVATE in front of those declarations. The keyword PRIVATE "sets a mode" in that one appearence is sufficient to render all subsequent declarations as PRIVATE, until a subsequent appearence of our second keyword, PUBLIC, sets the mode back to the default. You may change modes as often as you like. You are always started in PUBLIC mode at the top. The PRIVATE and PUBLIC keywords are admitted via the rules: private -> UNIT_SPEC public -> UNIT_SPEC Let's render a unit named NUCLEAR_POWER_PLANT. This unit INCLUDEs publically the units ELECTRICITY and POWER_LINES, as would any power plant. It INCLUDEs privately the units URANIUM and FISSION, which it must have to operate, but which it does not want to deliver as part of its overall service. Finally, it defines one function that yields electricity. Since this one function is the desired service, it is declared publicly. The body of that function however has access to the private parts, as would the body of any function defined in this unit. UNIT NUCLEAR_POWER_PLANT: INCLUDE ELECTRICITY, POWER_LINES ; PRIVATE INCLUDE URANIUM, FISSION ; PUBLIC DEFINE POWER_SUPPLY = ELECTRICITY: URANIUM \PURIFIED \FISSION_REACT \HEAT_WATER \INTO_TURBINE ENDDEFN Presumably the referenced functions ~URANIUM \purified -> ~NUCLEAR_FUEL ~NUCLEAR_FUEL \fission_react -> ~HEAT are defined somewhere in units URANIUM and FISSION, and the functions: ~HEAT \heat_water -> ~PRESSURE ~PRESSURE \into_turbine -> ~ELECTRICITY are defined somewhere in the units ELECTRICITY and POWER_LINES. Please note that the distinction between PUBLIC and PRIVATE applies to function headers, not to function bodies. The bodies of all functions in a unit have access to all PUBLIC ~and PRIVATE entities regardless of whether the particular function's header is PUBLIC or PRIVATE. In summary: 1) Anybody who INCLUDEs a unit acquires only its PUBLIC entities, and 2) During the compilation of a unit, the distinction between PUBLIC and PRIVATE ceases to exist in that unit. All PRIVATE declarations in the unit act as though they are PUBLIC. Put another way, you could remove any or all occurences of the keywords PUBLIC and PRIVATE and not affect the legality of your functions whatsoever. Again, the distinction between PUBLIC and PRIVATE manifests itself only when somebody INCLUDEs a unit. 22.6 Interactive ICL Sitting at the terminal, you can specify something for ICL to execute immediately. Any UNIT_SPEC is valid input, although one usually issues only STATEMENTs. One may also specify DECLARATIONs, which last as long as the interactive session. Thus the user can declare functions, coercions, types and/or variables interactively, and then make use of them at will. The user may also INCLUDE units so as to gain access to their declarations. Interactive ICL expects a UNIT_SPEC followed by a control-G (^G). The ^G instead of the carriage-return was chosen to terminate ICL interactions so as to allow multi-line inputs. For example, to declare a mutually recursive pair of functions, you may want to use two lines to specify them. Multiple functions or multiple types that depend on one another must be declared in one gulp, with no intervening ^Gs.