MAD List Language(ID:6005/mad011)Extensions of MAD for list processingA system of extensions to MAD to permit list processing Related languages
References: External link: Online Extract: Use of names USE OF NAMES The distinction between a name and the value is one of the first hurdles one crosses on proceeding beyond FORTRAN in computer programming. The necessity for FORTRAN programmers to learn it is fast disappearing, if it has not already gone. Nevertheless, this distinction is of fundamental importance to the systems programmer. Strictly speaking, a name is a symbol together with all its attributes. These attributes may include such things as mode (floating point, integer, etc. ), storage length in words or bytes, address within the computer assigned to this symbol, as well as many others. The value ascribed to this symbol is an attribute usually only defined at the time of execution. Oddly enough, by the time of execution most of the other attributes of the symbol (including. the symbol itself) have been discarded. All that remains is its current value and its address. In the following sections when we use the term name, we will usually be referring only to the address for the symbol, having discarded most of the rest of the attributes at compile time. This restriction is not fundamental, however, since it is merely a matter of choice which attributes should be fixed and interpreted at compile time, and which should be left free until execution time. In particular, in function calls, MAD passes parameters by name, name in this case including the address associated with the symbol and the structuring information (to be described below). As a result of the compilation process, each symbol within the source program is mapped into an address and a relocation factor. We can think of this symbol as marking the position within some memory space which will be related to a real computer memory at some later time, For example, MAD programs produce symbols which are relocatable within the program, within a reserved area of core called PROGRAM COMMON, and within another area of core called ERASABLE. Similarly FORTRAN programs produce symbols within the program, within COMMON, or within one of the areas called labeled COMMON. The absolute location of each of these areas is undetermined at compile time as is the relative displacement of one area with respect to another. The only quantity which is determined at compile time is the relative displacement of one symbol with respect to another of the same relocation type. The usual method of relating these symbols to absolute memory locations is by means of a relocatable loader, which also has the task of performing interprogram linkages when more than one program segment is required for execution. At the time of loading each symbol becomes associated with a definite computer address. It is possible, however, to defer the A Compiler Language for Data Structures 389 determination of this definite address to an even later time. Using techniques known as dynamic memory allocation, a running program can determine the absolute origin of a certain storage region and use the symbol value as an offset into this region. Doing this means that a given symbol may refer to more than one machine address during the course of execution of a program. It also means that at the time of execution, one requires a means of indicating the memory origin of the storage area. To construct a list-processing system, a language must be able to compute the names which it employs within a running program. This ability allows us to represent a graph within the list structure and to alter dynamically the connectedness of the graph within the computer. As we have noted, MAD (and FORTRAN) have the ability to use run-time computed names through the medium of the subscript. This construction is limited in its utility, however, and its use for complex problems can be awkward if not downright unmanageable. What is needed as an addition to language facilities is the ability to calculate more conveniently names within the running programs. The definition of "conveniently," however, must rely on experience and some intuition, and it will always be tempered with the realization that "what is one man's meat is another man's poison." The type of operation envisaged was first based on the primitive functions of SLIP; 6 this was later abandoned and a scheme which was modeled on the facilities of L6 was developed. Extract: List-Processing Facilities List-Processing Facilities The first set of language extensions are designed to make it possible to program list-processing systems directly in MAD. The SLIP system 6 will be used in what follows as an example of a system which could be programmed in this language, but the facilities do not in themselves depend on SLIP. L6 2 was used as a model for type of facilities desired, although in some respects there is a resemblance to the APL system V as well as to PL/I. Two new operand modes have been created to afford the list-processing facilities desired: REFERENCE and DYNAMIC RECORD. A REFERENCE variable is a MAD-language variable whose value is a machine pointer to some other entity. REFERENCE variables may be combined with certain operators (to be described below) to form expressions of REFERENCE mode. The value of such expressions is a language name and as such may appear on the left side of assignment statements: REFERENCE expressions acquire utility when we must refer within a program to constructs whose names must be calculated at run time. Such objects are normally found within declarations called DYNAMIC RECORD. A variable is of mode DYNAMIC RECORD when it is used as a name for heterogeneous grouping of variables of other modes for which space is to be assigned by a dynamic-allocation routine at run time. This grouping may be such that several variables share parts of one computer word. An example from SLIP should serve to clarify the nature of DYNAMIC RECORD declarations. A SLIP cell normally contains four parts occupying two computer words. There are two pointers, LNKL and LNKR, linking the cell to its predecessor and its successor, an identification field, ID, which can assume the values from 0 to 3, and an entire word named DATUM normally used to store the information on the list. Extract: Other Extensions To The Mad Syntax Other Extensions To The Mad Syntax The MAD language offers a powerful facility to programmers to tailor their compiler to fit their application, viz., the MAD operator-definition facility. Using this part of the MAD compiler, the programmer (or programming staff) can extend the compiler by introducing new operators and new operand mode definitions into the language. In the formulation of any graphical language, the MAD operator-definition facility should play a large role. The syntax extensions we are describing in this paper are those which cannot be encompassed within the operator-definition facility. The list-processing facilities described in the last section resulted from the examination of the L6 syntax, and the identification of these elements which were beyond the scope of the operator-definition ability. The rest we leave for development at the MAD programming level. In a similar fashion, we have tried to identify those elements of graphical language which were beyond the scope of the MAD syntax for their possible incorporation into the compiler. The one example of a graphic language which encompasses most of the desirable elements is the LEAP language of Feldman and Rovner. 1 This language is an ALGOL-type language which includes elements of set operations as well as Feldman's own method of representing graphical relations. LEAP is predicated on a highly elaborate but efficient method of data storage involving hash coding, but the details" of the implementation do not concern us here. It What does concern us, however, is the language syntax, insofar as it is incompatible with a MAD representation. Of all the elements of the LEAP language, the only construct which represents any serious difficulty in implementation within the MAD operator-definition framework is that of the local variable. A local variable is one which has an undetermined value before the execution of a given statement (or block within ALGOL), but after the first occurrence of the variable within the statement, its value is constrained to be that which it was in the first occurrence. Upon close examination of this construct, we notice that it is always associated with an implied or overt iteration over some set of permissible values. Consider one well-known language which contains local variables, SNOBOL. The local-variables concept is present within SNOBOL as is evidenced in the statement LIST *A* ', ' *B* ', ' A--A ', 'B This statement directs us to search the string named LIST for the following pattern, an arbitrary string, call it A, followed by a literal comma followed by an arbitrary string, call it B, followed by a literal comma, followed by the field A repeated. A in this example serves as a local variable. In the first occurrence of A, its value is free, to be determined by the search. In its second occurrence, A is constrained to have the same value which it had in its first occurrence. This statement, however, has an implied iteration contained within it. In order to perform the pattern match, A is associated with certain substrings of the string LIST according to a preset algorithm. In the LEAP language, also, the use of locals is constrained to be within iterations, specifically iterations over the elements of some set. The role of a local, therefore, is that of a variable of iteration in that the iteration is a specification of a set of values which the variable should take on successively to the satisfaction of some condition. To accommodate such a construct in MAD we must be able to perform operations which result in the sequencing of some element over the available elements of a set and to let this operation control an iteration. The first part of this requirement can be most easily satisfied within the MAD operator-definition facility. Consider, for example, the operator .MEMBER. X .MEMBER. S could, by suitable definition, result in the sequencing of X through all the possible values of the set S, performing the sequencing every time the operator is executed. The necessity of iterating over this construction, however, requires a change in our iteration statement. In what follows we use the abbreviations < sid > := <.simple iteration description > < e > : = := With this notation, the MAD iteration statement has the form THROUGH where We have modified the syntax of the iteration statement as follows: THROUGH where and < sid> := The first extension allows us to incorporate several iterations within the same statement which are automatically nested from left to right. In addition, the iteration may contain a WHENEVER clause which determines whether the scope of the iteration is to be executed for that particular iteration. The extension of the simple iteration description allows us to include sequencing operations instead of assignments as the controlling elements of the iterations. These features are all exemplified in the iteration THROUGH A, FOR I ---- 1, l, I.G. SIZE.(S), X. MEMBER. S, WHENEVER X .NE. Y(I) A This statement provides a double-nested iteration, the outer iteration being over the value of I, and the inner iteration being over the value of X. The phrase X.MEMBER.S is assumed to be a defined operator which sequences X over all possible members of the set S. The result of this operation is (Boolean) false as long as the sequencing proceeds, and is true when the set S is exhausted. The conditional phrase X.NE. Y(I) does not terminate the iteration but merely provides that the scope of the iteration shall not be performed whenever the condition is not satisfied. We must emphasize that the operator .MEMBER. has not been defined within our compiler; the statement only serves to illustrate the modifications of the iteration statement syntax. The implementation of .MEMBER. and the formulation of the behavior of variables like S which represent sets is left completely open, to be defined by some operator-definition package for a given application. in Proceedings of the 23rd ACM national conference January 1968 view details |