Store Mapping
KEY A variable declared in an IMP80 program is allocated storage on the stack (Section 3). It is possible in IMP80 to give an alternative name to such a variable. It is also possible to refer to an arbitrary store location, not necessarily within the stack area, and operate on it as though it held a variable of a specified type. "Store mapping" is the name given to this technique. It is useful for the following reasons: * to enable entities not declared within a program to be accessed and operated on by the program, without recourse to machine code or other machine specific features * to save space in main store (see first example below) * to access a variable both as declared, and as a set of sub-variables; for example, a variable of type %integer can be accessed as several separate variables of type %byte %integer
* to access an array element as a simple variable, with consequent saving of machine time * to improve the clarity of a program The store mapping facilities in IMP80 are provided by means of several components: * reference variables * user-written mapping functions * the ADDR function * the standard mapping functions
Reference variables & mapping fns
KEY Two of the fundamental entities from which programs are constructed are constants and variables (Section 2). A variable comprises an identifier (its name), and a type which specifies what type of value it may have. Its value is a constant, or a reference to a variable. Thus, the value of a variable of type %integer is an integer constant, while the value of a variable of type %integer %name is a reference to an integer variable. A function (Section 3) is similar to a variable in that it has an identifier, and a type which specifies what sort of value it returns. A mapping function (or map) is analogous to a reference variable in that its type (the type of the value that it returns) is a reference to a variable; for this reason maps are sometimes called "name functions". The difference between a variable and a function, of course, is that a variable has its value stored while a function computes its result.
Examples
KEY 1) Use of a reference variable with a map. In this program, a two-dimensional array is accessed by means of a map, because the array is symmetrical: i.e. X(i,j) = X(j,i) for all valid i and j. Thus to save storage space only the values of X(i,j) with i >= j are stored. By keeping only these values in a one-dimensional array A - which is global to the map - we can make economical use of store without losing the symmetrical appearance of the array X. The array is first assigned values and then various references to it involving %integer ALPHA and %integer %name BRAVO are made.
%begin %integer %array A(1:210) %integer ALPHA, I, J %integer %name BRAVO %integer %map X(%integer I,J) %signal %event 6 %unless 1<=I<=20 %and 1<=J<=20; ! Array bound check. %result == A(I*(I-1)/2 + J) %if I>J %result == A(J*(J-1)/2 + I) %end %for I = 1,1,20 %cycle X(I,J) = I\\2 + 2*I*J + J\\2 %for J = 1,1,I %repeat
ALPHA = X(17,10) {ALPHA assigned the value of the variable returned {by the call X(17,10) of map X. BRAVO == ALPHA {BRAVO made to refer to ALPHA (thus BRAVO is now {synonymous with ALPHA). BRAVO = 4 {BRAVO (i.e. ALPHA) assigned the value 4. BRAVO == X(16,9) {BRAVO made to refer to the variable returned by {the call X(16,9) of map X. BRAVO = 4 {BRAVO (i.e. the variable it currently refers to) {assigned the value 4. ALPHA = BRAVO {ALPHA assigned the value of the variable to which {BRAVO currently refers. This value is 4. X(6,15) = 17 {The variable to which reference is returned by {the call X(6,15) of map X is assigned the {value 17. ALPHA = X(15,6) {ALPHA set to the value of the variable returned {by the call X(15,6) of the map X. From the {previous statement, and bearing in mind the {symmetry of X, this value is 17. : %end %of %program
2) Reference variable used as a procedure parameter When a procedure is called, its formal parameters - in the example below SIZE and STATUS - are assigned values according to their types and to the actual parameters used in the call. SIZE is of type %integer and so has the current value of TOTAL assigned to it; STATUS is of type %integer %name and so is "pointed at" the integer variable RETURN. This example is included because procedure %name-type parameters provide a method for renaming variables, and as such represent a common application of store mapping techniques. %routine %spec TEST(%integer SIZE, %integer %name STATUS) %integer TOTAL, RETURN : TOTAL = 3 TEST(TOTAL, RETURN) ! TEST called: formal parameters assigned values. :
3) Mapping a direct access file The following map enables the programmer to treat a direct access file held on backing store as though it were a real array with declaration %real %array FILE(1:NBLOCK, 0:255), where NBLOCK is the number of blocks in the file. In use, the only difference from a normal array is that a closing call <real var> = FILE(0,n) must be made. In this implementation of IMP80, real variables are 32-bit entities, and each block of a direct access file consists of 1024 8-bit bytes. It is assumed that the direct access file has been associated with channel number 1 prior to the execution of this program. Note that when a virtual memory operating system is being used, a simpler and better method for mapping arrays onto files may be available - see later example.
%real %map FILE(%integer BLOCK, ELEMENT) ! The external routines specified below relate to the use of direct- ! access (DA) files. They are the standard routines provided in most ! implementations of IMP80, but do not form part of the language ! definition. Further details for some implementations are given in ! Appendix B. %externalroutinespec OPEN DA(%integer CHANNEL) %externalroutinespec CLOSE DA(%integer CHANNEL) %externalroutinespec READ DA(%integer CHANNEL, %integername BLOCK, %name START, FINISH) %externalroutinespec WRITE DA(%integer CHANNEL, %integername BLOCK, %name START, FINISH) %constant %integer NO=0, YES=1 %own %integer CURRENT BLOCK = 0, BLOCK CHANGED = NO %own %integer LAST ELEMENT %own %real LAST VALUE %own %real %array BUF(0:255) = 0(256)
%unless BLOCK>0 %and 0<=ELEMENT<=255 %start ! Could be an error, or the closing call. ! In either case, tidy up and close the file. WRITE DA(1, CURRENT BLOCK, BUF(0), BUF(255)) %if BLOCK CHANGED=YES CURRENT BLOCK = 0 %if BLOCK=0 %start; ! Closing call. CLOSE DA(1) %result == BUF(0); ! Irrelevant in this case. %finish ! Error - parameters out of range. %signal %event 6 %finish %if CURRENT BLOCK=0 %start; ! First call. OPEN DA(1) CURRENT BLOCK = BLOCK READ DA(1, CURRENT BLOCK, BUF(0), BUF(255)) %finish %else %start; ! Not the first call.
! Has the value of the last element returned by the map been ! changed? If so, note the fact so that the block is written back ! when no longer required by the map. BLOCK CHANGED = YES %if BUF(LAST ELEMENT) # LAST VALUE %if CURRENT BLOCK # BLOCK %start ! Block required differs from that currently held in BUF. ! Write currently held block back if it has been changed. WRITE DA(1,CURRENT BLOCK,BUF(0),BUF(255)) %if BLOCK CHANGED=YES ! Now get block required. CURRENT BLOCK = BLOCK READ DA(1, CURRENT BLOCK, BUF(0), BUF(255)) BLOCK CHANGED = NO; ! Reset change flag. %finish %finish LAST ELEMENT = ELEMENT LAST VALUE = BUF(ELEMENT) %result == BUF(ELEMENT) %end; ! Of %real %map FILE.
ADDR, standard mapping fns
KEY A variable has an identifier, a type and a value. A fourth attribute of an accessible variable is its address. This is a positive integer which uniquely specifies its location in the computer store. The address of a variable can be obtained by use of the standard %integer %function ADDR. Example: %string(27) S %integer ADDRESS OF S : ADDRESS OF S = ADDR(S) The parameter of ADDR can be a variable or array element of any type; in the case of a reference variable parameter, ADDR returns the address of the variable to which it refers, not the address of the reference variable itself. Given a variable, it is thus possible to find its address. Conversely, given an address, it is possible to construct a variable of any type, subject to certain restrictions detailed below. This is achieved by the use of the standard mapping functions. For each arithmetic and string type there is an associated standard map whose name is the same as that of the type; thus BYTE INTEGER, LONG REAL, STRING, etc. A standard map has a single parameter of type %integer, which is an address; it returns a reference to a variable of the appropriate type, located at that address. There are also two special standard maps, ARRAY and RECORD. They are described later in this Section. Example: %integer I, J %byte %integer %array B(0:3) : I = M'ABCD' : B(J) = BYTE INTEGER(ADDR(I)+J) %for J = 0,1,3 :
In this example the integer I has been unpacked into its four component byte integers (implementation using 32-bit integers assumed). Example: %byte %integer %array IN(0:80) %string(*)%name LINE : LINE == STRING(ADDR(IN(0))) : From this point onward the array can be referenced either as an array of bytes or as the string LINE. Obviously the length byte of the string, normally the first byte of the string location, will have to be set to an appropriate value.
There are a number of points to note about the use of the standard mapping functions: * They are efficient. * An address error will occur if the address passed to a standard mapping function is not aligned correctly with respect to the type of reference implied. On byte addressed machines, for example: SHORT INTEGER requires the address to be divisible by 2 INTEGER (if 32-bit integers used) requires the address to be divisible by 4 REAL requires the address to be divisible by 4 The maps for the longer arithmetic types may have corresponding requirements. * In Section 3 it was explained that variables declared in a program are allocated storage on the stack. However, if the computer system being used enables an IMP80 program to obtain store addresses of items not on the stack (e.g. items within the operating system, or a connected file in a virtual memory system), then the standard mapping functions can be used to refer to them as variables. This is an extremely powerful facility. * It is possible to cause a location in which, for example, a real constant is stored to be treated as an integer or a string, etc. While this facility may be useful on occasions it should be used with care, because: 1) misuse can lead to errors which are hard to diagnose; 2) it requires a knowledge of the precise format of data types and is necessarily implementation dependent; 3) the purpose of providing types in IMP80 is to enable checks to be made that dissimilar items of data are not being erroneously combined. Use of the standard mapping functions merely to avoid such checks is bad programming practice.
ARRAY
KEY {EMAS IMP80: There is only one standard mapping function, ARRAY, for all the array types. It takes two parameters: an address, and an array format to specify the type of the array being referenced. %array %format statements are analogous to %record %format statements in that they enable an identifier to be associated with a type and a structure. They can then be referenced by name in subsequent statements. ARRAY can only be used to assign to a reference variable of the appropriate array type. Example: %integer %array AONE(1:10 000) %integer %array %name ATWO %integer %array %format AFORM(1:100, 1:100) : ATWO == ARRAY(ADDR(AONE(1)), AFORM) : ATWO(27, 43) = 928 :
The %array %format statement is used to describe the characteristics of the array ATWO - i.e. the number of dimensions and bounds for each dimension. As an alternative to using an array format for the second parameter, the name of another array (of the appropriate type) can be used, if one with suitable characteristics has been declared and is in scope. In order to map record arrays, the second parameter of ARRAY must either be an existing record array variable, or a record array format. A record array format must specify both the dimensions of the array and the format of each (record) element of the array: %record (<record format>) %array %format <name> (<array dims>)
Example: This example is of a record array format being used in an IMP80 program running under the operating system EMAS. The integer function SMADDR returns the address of a file connected in the virtual memory of the user process. %routine PAYCHECK(%integer CHANNEL, RECNO) %integer I, J, K, START, LENGTH %string(11) NAME %external %integer %fn %spec SMADDR(%integer CHANNEL, %integername L) %record %format PAYF (%string(11) SURNAME, %integer AGE, SEX, YEAR, %integerarray SALARY (1:12)) ! Each record thus formatted contains 72 bytes. %record(PAYF)%array %format PAYAF(1:RECNO) %record(PAYF)%array %name PAY : ! Assume that a file was associated with channel CHANNEL, ! prior to the execution of the routine.
START = SMADDR(CHANNEL,LENGTH); ! File now connected. %if LENGTH < 72*RECNO %start PRINTSTRING("File too small:") WRITE(LENGTH,1); NEWLINE PRINTSTRING("Must be at least") WRITE(72*RECNO,1); NEWLINE %return %finish PAY == ARRAY(START,PAYAF) ! Now record array name PAY has been mapped onto the file. ! Note that START was set by the SMADDR call. : NAME=PAY(I)_SURNAME %if PAY(I)_SALARY(J)>350 .... : PAY(K)_YEAR=1978 : %end; ! Of %routine PAYCHECK. }
RECORD
KEY The main use of the standard map RECORD is to assign a reference to a record reference variable. The format of the record in question is that of the reference variable on the left-hand side. Example: %record %format F(%integer A, B, C, %real D, %string(11) E) %record (F) R %record (F) %array RA(1:50) %record (F) %name N1, N2, N3 %integer ADDRESS : ADDRESS = address of some store location : N1 == R;! Record name N1 now synonymous with record R. N2 == RA(20);! Record name N1 now synonymous with element 20 ! of record array RA. N3 == RECORD(ADDRESS);! Record name N3 now synonymous with a ! record of format F located at ! address ADDRESS. :
Example: %integer J %integer %array II(1:100) %record %format A(%byte %integer I, J, K, L) %record %format B(%half %integer P, Q) ! Implementation-dependent type %record(A)%name X %record(B)%name Y : X == RECORD(ADDR(II(J))) Y == RECORD(ADDR(II(J))) : Now, for example: X_I is a reference to the leftmost byte of II(J) Y_P is a reference to the leftmost half-word of II(J)
This example could have used an alternative record format: %integer J %integer %array II(1:100) %record %format A(%byte %integer I, J, K, L %or %c %half %integer P, Q) ! Implementation-dependent type %record(A)%name X : X == RECORD(ADDR(II(J))) : Now, for example: X_I is a reference to the leftmost byte of II(J) X_P is a reference to the leftmost half-word of II(J)
{EMAS IMP80: RECORD returns a reference to a record whose format is unspecified but "very large". This is acceptable when assigning a reference to a reference variable, as described above, since in EMAS IMP80 the format of the reference on the right-hand side of such an assignment statement does not have to match that of the reference variable on the left-hand side. However, a record variable cannot be assigned by a statement of the form RECVAR = RECORD(ADDRESS) since the sizes of the records on each side are not equal. On the other hand, the form RECVAR <- RECORD(ADDRESS) is permitted; as many bytes as RECVAR can hold (determined by its format) will be transferred.}
{IMP77: the standard map RECORD is of the form %record(*)%map RECORD(%integer AD) i.e. the reference returned by RECORD may be to a record of any format; the actual format is determined by the context. Thus RECORD can be used to assign to a complete record. Example: %record %format AF(%integer %array X(1:20), %string(10) TITLE) %record(AF) A %integer AD : : A = RECORD(AD) {The record format used is that of A, i.e. AF} :
Note that statements of the form RECORD(I) = RECORD(J) are not allowed, since no format is indicated from the context.} {EMAS IMP80: programmer-written record maps are not available.}