Mad/I(ID:2205/mad003)Advanced algorithmic languageA later, much enhanced version of MAD, for the IBM 360. Michigan's answer to PL/I: it began as a port of Mad from the 7090, but then became the basis for the Concomp conversational programming project, and needed to be extensible to new structures and operators. "a particular procedure-oriented algebraic language [...] intended to be useful both as a general-purpose language, and also as a convenient base or "core" language for extension into various dialects." Unclear as to ultimate fate of the language - Bolas says (in the SIGPLAN piece) "The Mad/I compiler is currently working under MTS at Michigan, but it is not in a state suitable for distribution, Further development of Mad/I has been postponed indefinately due to lack of funds and personnel" Related languages
Samples: References: The state of the MAD/I compiler and it's definition facilities is hopefully made clear by the following set of program segments and interposed explanations. The compiler is operational and is currently being used by CONCOMP personnel in an attempt to use the definition capabilities in graphics applications. As a result of this effort, as well as the natural improvements and additions that are continually made, the current language specifications do not describe all of the features illustrated in what follows. Currently the development group is updating the external specifications. The Concomp Project was formed in December 1965 to do research in the conversational use of computers. Concomp needed a general-purpose- language suitable for writing conversational programs, and also wanted facilities for defining new data types, operations, and statements into the language. Concomp therefore strongly supported the development of an extended Mad, which would serve these needs, and this became the new goal of the language project. In these early days, the language was known variously as Made, Comet, or Mad/360. As work progressed, it became apparent that it was not feasible to retain useful compatibility with Mad/7090. Also, the need for a flexible definitional facility forced the re-examination on of basic concepts about the structure of programming languages. Eventually it was agreed that the Mad/1 project was actually developing a new language (and compiler), which would be independent of Mad. The goals of the Mad/I project were again redefined. We now wanted a language-and-compiler with the following features: It should contain a predefined algebraic language, suitable for conventional general -purpose use without any definitions from the user. The language should have a rather general syntax, so that a variety of new statements and operators might be defined into the same framework as the predefined constructs. It should contain a powerful definitional facility usable by a moderately sophisticated programmer, This facility should allow the user to modify the predefined language so as to satisfy his special requirements. In particular, it should allow the definition (or redefinition) of: data structures and data types; statements and declarations; operators and operations, either in terms of existing operations, or in terms of an assembler-like language allowing access to the object machine instructions, at the user' s option, The compiler should be reasonably fast, especially when the program contains no new definitions. The compiled object program should be reasonably efficient, although perhaps not. highly optimized. These goals have been largely fulfilled, with a few exceptions. The predefined Mad,/ I language is a useful general-purpose language. It has a syntactic structure somewhat like Algol 60, but it includes many of the important features of Mad and PL/I. The Mad/I compiler has been working since late 1968, and is being used for practical system programming. Portions of the compiler itself have been written in Mad/1. The syntax rules of Mad/I are sufficiently general to allow a large 'space' of possible definitions. A great variety of symbols, expressions, and statements are syntactically possible. The definitional facility exists, but it is not complete. The Mad/I language itself is implemented using this facility, and one can indeed define new data types, operators, etc, Unfortunately, this facility in too 'low-level', and cannot be used without considerable study. A user-oriented facility is certainly feasible, but this requires more research and development. The compiler is unfortunately not fast. It is large and very slow, because it constantly reinterprets definitions. With a little more work , the compiler could be speeded up by a factor of at least four. The object program now produced is reasonably efficient, although not highly optimized. Even better object code is possible, (From the introduction) The Mad/I compiler is currently working under MT5 at Michigan, but it is not in a state suitable for distribution, Further development of Mad/I has been postponed indefinately due to lack of funds and personnel Bruce J. Bolas in SIGPLAN Notices 5(11) November 1970 view details Description of the Mad/I Language This section briefly mentions some of the principal concepts and features of the MAD/I language. Input Form The language is defined in terms of a continuous sequence of characters, independent of card format or line boundaries. The compiler accepts its input as a sequence of records (lines) L which may vary in length. This input is normally treated as completely free-form, and is broken into a sequence of symbols. Blanks and comments may be used freely between symbols, but most symbols cannot contain blanks. Symbols In MAD/I two concepts nave been separated: the form of a symbol (how it is composed of characters), and the usage of the symbol (how it functions as a language element). Examples of symbol forms (called "lexical classes") are: Alphanumeric symbol (e.g., F A32 BETA) Primed symbol (e.g., 'IF' 'TRUE' 'END' ) Quoted symbol (e.g., "CHAR-STRING" "OOlA4"X) Unsigned-integer symbol (e.g., 4 003 5140) Special symbol (e.g., + : , ( ) = ) The symbols may be used in any of several ways; example usage classes are: Identifier. Usually formed as an alphanumeric symbol, but the primed symbol 'DEFAULT' is also a pre-defined identifier. Keyword. The pre-defined keywords are primed symbols. An . alphanumeric symbol (such as IF or BEGIN) could be defined as a keyword, but then it could not also be used as an identifier. Constant The symbols 307, 'TRUE', 18.4E3, and "P=**" are all constant symbols. Operator. The symbols + , = , .ABS. , .OR. , := , and ** are pre-defined operators. Attributes and Declarations Language items such as identifiers, constants, and expressions have attributes. Example attributes are: Mode (e.g., 'INTEGER', 'CHARACTER', 'VARYING ARRAY', 'POINTER') Storage layout (e.g., Length, Alignment, Dimension) Storage class (e.g., Static, Automatic, Based) Attributes of an item may be explicitly declared either in a declaration statement or by attaching a declaration to any occurrence of the item in the program. Declarations may appear anywhere in the program, and in particular need not precede the first occurrence of the item. There are also default attributes for items which are not completely declared. The defaults to be applied are themselves declarable. Example declarations: 'INTEGER' I, K, N 'DECLARE' (AIPHA, BETA) 'FIXED ARRAY' (50,50) 'BOOLEAN' I@('INTEGER') := N@('INTEGER') + 3 'DECLARE' 'DEFAULT' 'FLOATING LONG' Expressions A MAD/I expression is basically similar to an expression in FORTRAN, MAD, ALGOL, or PL/I, but is slightly more general. The four expressions ALPHA, A + B, (X-Y)*Z, -XYZ all have the usual meanings in the pre-defined language. However, the conventional concepts of "subscripted variable" and "assignment statement" are handled as expressions in MAD/I. For example, if ALPHA is an array name, then ALPHA is considered a variable, but ALPHA(I) is not a variable; both ALPHA and ALPHA(I), however, are expressions (called "designators"). In "ALPHA(I)" the subscription operation is implied by the context of the array name expression followed by the left-parenthesis symbol; it is treated as a convenient way of writing "ALPHA .TAG. I", where .TAG. is the operator denoting subscription. An assignment such as "AA := BB" is also an expression; its result is the same as AA , except that the value of AA has been set to the value of BB. We could compute the maximum value of AA and BB with the statement: 'IF' (MAX := AA) < BB , MAX := BB The concepts of "operator" and "operation" have been separated. For example, the special symbol + is pre-defined as an infix operator which, in the contexts of arithmetic operands, denotes "addition". Addition is a binary (i.e., dyadic) operation. The + operator could, however, be defined to mean something other than addition for other contexts. Statements MAD/I statements are roughly similar to those of ALGOL 60 and PL/I. There are five general statement classes: simple statements, compound statements, prefix statements, list statements, and declaration statements. (1) Simple statements. A simple statement is either an expression or a "statement keyword" (reserved word) followed by a fixed number of expressions. A := BCD 'GO TO' LABEL 'ALLOCATE' STRUCT, K*10 (2) Compound statements. A compound statement consists of a sequence of statements, separated by semicolons, and bracketed by a statement keyword and an "end keyword". 'BEGIN' B := A; C := D 'END' (3) Prefix statements. A prefix statement consists of a "prefix" followed by a "scope". The prefix consists of a g statement keyword followed by a fixed number of expressions. The scope may consist either of one statement (separated from the prefix by a comma), or of a sequence of statements separated by semicolons and terminated by an end keyword (separated from the prefix by a semicolon). 'IF' A > 0 , B := A 'IF' A > 0 ; B := A ; C := D 'ENDIF' 'FOR' I:=1,1,I>N , G(I) := 0 'FOR' I:=1,1,I>N ; G(I) := 0 ; H(I) := 1 'ENDFOR' (4) List statements. A list statement consists of a prefix followed by a varying number of expressions. 'READ' ('UNIT' 0), A, B, C 'PRESET' D := 1, F := 3.5, CH := "**" (5) Declaration statements. These have two forms: the 'DECLARE' statement and the "inverted" declaration statements, as exemplified below. 'DECLARE' AA 'INTEGER', BB 'BOOLEAN', CC 'COMPONENT STRUCTURE' ('BIT'(8), 'BIT'(24)) 'DCL' (DD, EE, FF) 'FLOATING', GG 'ENTRY NAME' 'INTEGER' II, JJ, XX 'EIXED ARRAY' A1(5,10), A2(4,4,4) Statements to be successively executed are written in I sequence, separated by semicolons. Empty statements are I permitted. A statement may be labeled with an identifier, I separated from the statement by a colon. I := 0; LBL: 'IF' Z(I) -= 0, 'RETURN' I ; I := I + 1 ; 'GO TO' LBL Embedded statements Any statement (or sequence of statements) can be made to produce a result, and can therefore be used as an expression (i.e., "embedded" in an expression). The 'VALUE' prefix statement is provided for this purpose. The prefix designates a variable whose value at the end of the statement is used as the result of the statement. The 'VALUE' statement is enclosed in parentheses and used as an expression. SUMSQUARE := ('VALUE' S ; S := 0 ; 'FOR' I:=1,1,I>N, S := S + (X(I) - Y(I))**2 'ENDVALUE') Program structure MAD/I provides a "block structure" much like ALGOL 60 and PL/I. Each block is either a "compound-statement block" or a "procedure block". A compound-statement block has the form 'BLOCK' ... 'END' where the ... represents an arbitrary sequence of statements. Procedure blocks have several variations; they typically look either like 'PROCEDURE' NAME.(PAR1,PAR2) ; ... 'END PROCEDURE' or like 'PROCEDURE' FN.(X,Y) := expression Both kinds of blocks are statements, and can be used wherever a statement is valid. Blocks, therefore, may be nested. Block structure serves to delimit the scopes of declarations and names. Each block may either have its own default attributes, or may inherit the defaults of the enclosing block. A MAD/I program is a block not contained in any other block. Each source program is separately compiled into its object program. in SIGPLAN Notices 5(11) November 1970 view details MAD/I is a computer language under development at the University of Michigan Computing Center, sponsored by the CONCOMP Project. It can be thought of as a remote descendant of 7090 MAD and ALGOL 60, with PL/I being a not-too distant relative. However, MAD/I and its compiler have some unusual features that aid language modification and extendibility, although these features are beyond the scope of this paper. Except for block structure scope facilities and the default setting facilities, then, MAD/I may be regarded as simply another representative of the class of procedural languages which includes ALGOL 60 and PL/I. Briefly, MAD/I has blocks, as in PL/I and ALGOL 60. Like PL/I (but unlike ALGOL 60), declarations may occur anywhere within a block, and are not required for all variables in the program. If some attributes of a variable are not declared then they are given "default" values. Such attributes include storage class (e.g., static, based, etc.) and data type. The facilities for specifying the defaults are very different from those of PL/I, and are generalization of those of 7090 MAD. The scope of a variable is determined in much the same spirit as in ALGOL 60 and PL/I, but the programmer has more control over the specification of scope, including the scope of variables which are not declared. This makes determining scope and determining defaults a complicated problem. Extract: Defaults In Mad/I Defaults In Mad/I The default assignment of data types is done in a very systematic and general manner. At any point within the program there is defined a current default data type. This default data type may be declared by the programmer on a block basis. A special symbol, 'DEFAULT', is used to carry the default information, and is treated like a variable when in the context of declarations, but otherwise it is not written by the programmer. The default data type is given to any variable for which no data type has been explicitly declared. For some data types one can declare a "sub-data-type," such as the component data type of an array, the data type of the result returned from a subroutine, or the data type of a component of a structure. If such a "sub data-type" is not specified then it is given the de fault data type. For example, assume that the default has been declared as follows: 'DECLARE' 'DEFAULT' 'INTEGER' Then assume the following declaration: 'DECLARE' A 'FIXEDARRAY'(4,4)'FLOATING', B 'FIXEDARRAY'(4,4); The mode of both A and B is 'FIXEDARRAY', with dimension 4 x 4. The component data type of A was explicitly declared to be 'FLOATING'. Since the component data type of B is not explicitly declared, it is taken to be the default 'INTEGER'. If some other variable that belonged to that block were referenced in the block but no declaration made about its data type then it would also be assigned 'INTEGER' data type. There are other cases where default actions occur in MAD/I. They will be mentioned briefly here although they are not involved in the rest of this paper. The dimension information given in the above example is specified in a declaration "suffix." If such a suffix is omitted for declarations where they are normally expected, then a default set of information is assumed for the missing information. For example, in the case of an item of 'CHARACTER' mode, the suffix specifies how many characters the variable has. If the suffix is omitted, the number of characters is assumed to be one. If the dimension information were omitted above, a warning message would be issued, and an array which has one dimension and one component would result. The lexical class of constants specifies an implicit data type which they are assigned, unless a declaration is explicitly written which specifies some other data type. As an example, the constant 5 will be assigned 'INTEGER' data type (32 bits long on the IBM 360), whereas 5@('INTEGERSHORT') produces a constant 16-bit integer. These two types of default operations are presently not controllable any further by the programmer. For suffixes the default is associated with the mode involved. For constants the default is associated with the lexical class of the symbol. It would be possible to have these defaults also controllable by the programmer by adding special declarations to the language, but this has not yet been done. The default data type in the outermost block is 'FLOATING' unless it is explicitly declared to be something else. For any other block the default is the same as for the next outer block unless it was explicitly declared in the inner block. If a default mode is declared, but not completely, then the remainder of the default is taken from the default of the next outer block. This is done in exactly the same manner in which defaults are applied to a variable whose "subdata-type" may not have been declared. As an example, assume that in the outer block the default is 'BOOLEAN'. Assume that the default is then declared as follows in the inner block: 'DECLARE' 'DEFAULT' 'FIXEDARRAY'(10); Thus the component of the inner block's default is not explicitly specified. It will be made the data type of the default of the next outer block, 'BOOLEAN'. Generally the default propagates inward from the next outer block, in a manner similar to the propagation of scope of variables. Extract: Block Structure in Mad/I 3. Block Structure in Mad/I There are three concepts embodied in block structure as it is traditionally specified in ALGOL 60 and similar languages. Typically the block is denoted by a beginning keyword and an ending keyword. In ALGOL a block has three functions: (1) to specify scope of variables, (2) to specify the dynamic nature of storage allocation for certain classes of variables, and (3) to group statements. In PL/I the grouping effect can also be obtained with a DO statement as well as with a BEGIN statement. In MAD/I the 'BEGIN' statement is used for simple grouping of statements, and the other two facilities are specified by 'BLOCK' or 'PROCEDURE', corresponding to BEGIN and PROCEDURE in PL/I. Thus MAD/I has facilities similar to those of PL/I, although with different names. The scope in which a variable is known is determined rather simply in ALGOL. If a variable is declared in a given block, that variable's name represents a different variable from one of the same name in the next outer block. If a variable is used in an inner block but not declared there, then it is the same variable as one of the same name in the next outer block. Finally, in ALGOL 60 all variables must be explicitly or implicitly declared in the outermost block in which they are to be known. In MAD/I the "naming" or scope rules are similar to those of ALGOL 60, but there are additional rules allowing the programmer more control over the "naming" facility. In MAD/I the user does not have to declare a variable at all; therefore he needs conventions in order to know in which block an undeclared variable belongs. In PL/I the rule apparently is that a declared variable belongs to the outermost block in which it is declared. If it is not declared, then it belongs to the outermost block. Let us motivate the additional rules for assigning defaults to symbols. By writing a large block and specifying the default within that block, the user can avoid writing a large number of individual declarations for variables in that block. But if the block is an inner one, then, following the PL/I rule, variables that are not declared in that block would belong to the next outer block and would not be affected by the default. What is desired, in some cases, is that unless otherwise specified, any variable used in a block is declared in that block implicitly. In other cases we would want to have the PL/I rule. Thus we have modified the scope rules for MAD/I as follows: (1) If no default is declared for a block then the only symbols that belong to that block are those that are declared in the block. (2) If a default is declared in a block, but 'NEW' has not been declared for that default symbol, then symbols that have not been declared in the block are treated as if they were referenced in the next outer block. (3) If default was declared for the block and 'NEW' was also declared for the default, then, unless otherwise specified (by rules below), all symbols referenced in the block are implicitly declared in the block. Note that under these rules a block with default declared 'NEW' would not be able to access any variables outside that block. Therefore, we have devised additional rules, which apply irrespective of any default declarations or 'NEW' declarations currently in effect: (1) If a symbol is declared 'NOTNEW' in a given block, then it is treated as if it were referenced in the next outer block. (2) It- a symbol is declared 'GLOBAL', then it is treated as if it were declared 'NOTNEW' in that block and each surrounding block. (3) If there is no next outer block as stated (1) and (2) above, then the variable be longs to the outermost block. Although MAD/I has not yet been used extensively, most of these rules have proved useful and have eliminated much writing of declarations in some cases. Typically, the scope rules of block structure are used to allow the writing of relatively independent sections of program which are to be part of the same compilation. The block structure allows the user to write the sections without worrying that two variables in different sections may accidentally have the same name. In ALGOL the variables in the two blocks would be declared in their own blocks, and those that are intended to be common would be declared in the next outer block. In MAD/I the programmer has the freedom of not declaring all variables in such blocks; instead he declares 'NEW' 'DEFAULT' in each independently written block. Then all variables referenced in each block belong to that block unless declared 'NOTNEW'. This combination of rules gives the user the advantages of both the block structure and the default declaration facility. In the left-hand column below are several blocks representing the skeleton of a complete MAD/I program. All references are indicated by occurrences of variable 5 names. All declarations are indicated. The right hand column contains comments about items to the left. 'PROCEDURE' MAIN; Block 1 begins. Main is implicitly declared 'ENTRYPOINT' mode. ... A ... This variable A is not declared it belongs to the outermost block and has default mode of 'FLOATING'. 'BLOCK' The beginning of block 2. This block has no default declared for it. ... A ... This is the same A as in block 1. 'DECLARE' B; B is new to this block, and will have the default mode, 'FLOATING'. 'DECLARE' C; 'NOTNEW' C; Despite the declaration, C is not new to block 2, but belongs to block 1, and has $ default mode. 'BLOCK'' 'DECLARE''DEFAULT''INTEGER' Block 3 begins.; There is a new default for this block, but 'DEFAULT' 1 has not been declared 'NEW'. ... A ... Since it is only referenced here, this A is the same as in block 1 and 2. ... B ... Since it is not declared in this block, B is the same as in block 2. 'DECLARE' C; C is new to this block and has default mode of 'INTEGER'. 'END'; The end of block 3. 'BLOCK' The beginning of block 4. 'DECLARE''DEFAULT''NEW' 'CHARACTER'(256); This block does have its default declared 'NEW'. ... A ... As a result, this A is a new variable even though it is only referenced in the block; it has the default mode of 'CHARACTER'(256). 'DECLARE' B 'FLOATING'; B is new to this block. 'DECLARE' D 'NOTNEW''BOOLEAN'; D is the only variable referenced in this block which does not belong to the block. It belongs to the next outer block. 'END'; The end of block 4. 'DECLARE' D; This is the same D as in block 4. D belongs in this R block instead of the next outer one because of this declaration. 'END'; End of block 2. 'END'; End of block 1. In this example have two distinct As, two distinct Bs, and two distinct Cs. Of course this example looks rather complicated, because no other program details are supplied to make it look more natural, and because it attempts to illustrate many rules with one example. It is interesting to point out, for procedures in MAD/I, that entry points to a procedure fall inside the 'PROCEDURE' 'END' brackets, and are implicitly declared to be 'ENTRYPOINT' mode. According to the strict rules specified above, these entry points would be "new" variables in the block and thus not known outside the block, definitely an undesirable situation! Thus there is also an implicit 'NOTNEW' declaration on each entry point specified in the prefix of a 'PROCEDURE' statement. Extract: Conclusion Conclusion Everything described in this paper has been successfully implemented in a compiler for the MAD/I language which runs on an IBM/360 model 67 under the University Of Michigan timesharing system, MTS. For various reasons which are not relevant here it is a very large compiler. Since the system provides very large virtual memory for execution (about four million bytes), the compiler is written to take advantage of a large virtual memory. MAD/I was also written mostly in an experimental compiler implementation "macro" language, which allows easy modification of the compiler, even at run time, for those who know the incredible intricacies of the compiler. These factors, of course, have influenced the implementation of the block structure and default facilities. Nevertheless, it is felt that what we have learned about these facilities may be useful to compiler implementers whose design requirements impose very different constraints on their compilers. in SIGPLAN Notices 5(11) November 1970 view details 1. INTRODUCTION The MAD/I project of the University of Michigan has designed and implemented a flexible translator- building system called the MAD/I facility. The facility provides services to aid in the lexical and syntactic scanning [ 3 ] of the program, storage allocation, and object- code generation. A compiler is written in the facility as a set of procedures, called a macro, to which is control passed at various times by the syntactic scanner and by the contents of the intermediate storage of the partially compiled programs. New macros can be redefined while a compiler is executing, thus making extensions to the compiler (and hence to the language) possible. A compiler, called the MAD/I compiler, has been implemented using the MAD/I facility. The language accepted by the MAD/I compiler is called the MAD/I language The MAD/I language is a procedure-oriented algebraic language which is a descendant of ALGOL 60 and 7090 MAD, similar in power and scope to PL/I. Because the MAD/I compiler is written in the MAD/I facility, there is a great potential for extensibility features within the MAD/I language. To date, no extension facilities have been designed for the MAD/I language; that is properly a goal of further research. This report presents an example definitional facility in the MAD/I language. A simple list-processing program is written in the MAD/I language as extended to include three new modes, three new statements, and eight new operators. These extensions are written using the macro language of the MAD/I facility and two experimental definitional statements. These definitional statements, or similar ones determined to be more appropriate, could easily be incorporated as a part of the MAD/I language. For the moment, they also are defined at compile-time. The remainder of this report explains in detail the simple program and the code necessary to define the language extensions. This explanation references the computer output which appears at the end of the report. This output consists of six parts: (1) a listing of the contents of the file SKETCH which is the sample MAD/I program, (2) a listing of the contents of the DISPLAYDEF which defines the extensions for the MAD/I language, (3) a listing of the contents of the file DEFFACILITY which defines the two experimental statements, (4) a listing of the contents of the file -DATA which contains the data used in the run of Step (6), (5) the compilation of the MAD/I program, and (6) the run of the generated object program using the data of Step(4). The object-code listing of the compilation has been removed to reduce the bulk of the report. Extract: DATA 5. DATA The file -DATA contains the data presented to the MAD/I program in the run of Section 7. The program is intended to be used from a terminal on a conversational manner. Running the program in batch has required us to anticipate the requests for input and the assignment of internal display numbers. The reader will find it helpful to look at the printed output from the run with this data (Section 7) while reading Section 5. Line 1 requests a display of the current contents of the list-structure. Since the list-structure is empty the comment "NOTHING TO DISPLAY". is printed. Lines 2 through 9 define four points having coordinates (10,10),(10,40),(40,10) and (40,40). These points are assigned internal display numbers 1,2,3, and 4, respectively. Line 10 requests the current list-structure to be displayed, resulting in the first graph showing the four points. Lines 11 through 18 connect the four points with lines forming a square. Line 19 requests the current list- structure to be displayed, resulting in the second graph showing the square.(This looks like a rectangle because the horizontal scale is 10 characters/inch while the vertical scale is 6 characters/inch (before reduction)). Lines 20 and 21 move the first point from its original position of (10,10) to the new position (15,20). Since this point is not a member of any picture, it is the only point moved. Line 22 displays the third graph showing the point moved to its new location. Lines 23 through 28 mark the four points as members of the same picture. Lines 29 and 30 move the first point from its current position of (15,20) to the new position (20,20). The second, third, and fourth points are also translated horizontally by five raster units because they are members of the same picture as the first point. Line 31 causes the display of the fourth graph which shows the results of this translation. in SIGPLAN Notices 5(11) November 1970 view details |