PL/I-FORMAC(ID:560/pli005)Variant of FORMAC using PL/I as base/host language, became the focus of IBM's development activity as a result of their championing of PL/I. New version of the preprocessor created as a result of a Share task force, based on their interim report, Schwerdt July 1970 This was the final official IBM version Related languages
References: This paper describes the results of a research effort to define a possible PL/I language extension to perform mathematical symbol manipulations. The approach taken is to add this new capability in an embedded way. In this way. all P L/I' s currently defined capabilities can be utilized to assist in expressing analytic solutions to algebraic problems in a convenient and natural manner. Syntax. functional capability. and other aspects are described Extract: Introduction The general area of symbol manipulation has been gaining widespread recognition in the recent past. A facet of symbol manipulation that has proven to be of significant value is mathematical symbol manipulation (or formula manipulation), which enables the manipulation of mathematical expressions in their symbolic form. This is in contrast to solving mathematical problems via numeric techniques. Many programming languages and systems that aid in non-numeric mathematical computation have been developed *. Collectively, these systems have demonstrated the feasibility and practicality of such tools. Mathematical symbol manipulation is, however, still in its infancy. To realize its full potential, research, development, and use of experimental systems must continue. More knowledge is needed to adequately evaluate the many different characteristics that directly influence the effectiveness of these systems. For example, developers of these tools must decide on answers to questions such as: What is the basic level of capability to be provided? Is it to be a general list or string processing system from which specialized tools can be built by the user, or is it to be a higher-level, more specialized tool? If it is a specialized tool, such as symbol manipulation for solving mathematical problems, then for what class of mathematical problems should it be designed? For polynomials? Rational functions? Elementary functions? Matrices? Should the capability be stand-alone or should it be added to standard programming languages and systems? If it should be added to other languages and systems, should it be independent of but callable from the main system or language, or should it be an integral and embedded part of the system? Answers to these and other such questions are neither deeply rooted nor profound, but they are significant because they affect, in a very real way, the tool as seen by the user. This paper summarizes the results of an investigation of the design of a mathematical symbol manipulation capability for IBM System/360. Although all the components of a system were considered (i.e., capability, language, compiler, algorithm design), the prime emphasis was in developing the capability and the language. In order to achieve the goals of this effort, a position had to be taken on some of the above questions. The position taken, as well as much of the actual design work, was based on experience gained in developing and using the experimental FORMAC (FORmula MAnipulation Compiler) system. FORMAC, an extension of FORTRAN IV under the IBM 7090/94 IBSYS/IBJOB Operating System, permits mathematical expressions to be written, retained, and manipulated as symbolic entities. FORMAC permits formal mathematics to be done with the aid of a computer, by using a FORTRAN-like language within a FORTRAN routine. Because of the long association and success with FORMAC, it is not surprising that many of the basic objectives and some of the design features of the FORMAC system were carried into the new work. There are, however, many significant differences, the most important of which is reflected in the source language. Experience with the FORMAC system confirmed beliefs that a high-level language is important to practical and widespread use of a mathematical symbol manipulation system. The language must be simple to learn and yet powerful enough to provide capabilities for numeric computation, loop control, testing, I/O, subroutine organization, etc. At the time of this work, two scientific host languages - FORTRAN and PL/I - were considered. ALGOL was not considered because work to extend ALGOL in this direction was being done elsewhere. Further, FORTRAN and PL/I are more widely accepted in the USA than is ALGOL. Since PL/I promised to be an effective multipurpose programming language, and since a great deal had already been known about adding a symbol manipulation capability to FORTRAN, it seemed appropriate for a study effort to investigate PL/I as the host language. This investigation also adopted a somewhat different attitude towards language extension. In discussing the results of the design effort, this paper includes a description of the language, and in selected cases, examples and motivation. We assume that the readers have a thorough knowledge of the basic features of PL/I. We also assume the existence of the PL/I list-processing data type, POINTER. Extract: Approach to language 2. Approach to language In the FORMAC system, the algebraic capability was added to FORTRAN IV in a way that required separate, specially defined, FORMAC source statements. Although FORMAC statements had a syntax similar to FORTRAN notation, and could be freely intermixed with the FORTRAN statements, FORMAC statements were identified with a leading keyword LET. Although separate statements are not considered a problem, they do present certain limitations and do require explicitly stated interfaces and conversions between numeric and non-numeric computations. For example, FORMAC variables - even though their values may be purely numeric - are not PE!rmitted in FORTRAN statements. FORMAC expressions cannot appear as arguments of CALL statements. There is no provision for FUNCTION subroutine to return a FORMAC value, etc. While these are not serious limitations, the new design attempts to eliminate all such restrictions and thus make the extension to PL/I as natural and as embedded as possible. A major characteristic of PL/I is the freedom it permits in writing expressions and statements (e.g., free-form statements, permitting and defining conversions for variables with different attributes when they appear in an expression, etc.). To embed the formal * capability means that variables representing symbolic or formal values should appear wherever numeric variables are permitted. Since declaration statements have traditionally been used for this purpose, we propose to extend the PL/I declaration statement. The details of this extension are given under the The Domain Attributes section. The introduction of the formal data type, via a declaration, is important in establishing the concept of formula manipulation, but it is not sufficient for a useful system. The use of the data type itself is important. The user must be able to construct formal expressions and express various mathematical operations to be performed on them. Capabilities such as automatic simplification, formal differentiation, expansion, substitution, evaluation, coefficient finding, comparisons, etc., have already proved to be of value in the solution of many practical problems [10] with the IBM 7090 FORMAC system. It is obvious that some new language is required to specify these manipulations. However, a constraint was imposed in defining this new language. Since PL/I, in its entirety, was already very large, the extension should add a minimum of new language, but must be adequate to cover the basic concept. It was interesting to discover that much could be done with a formal data type in PL/I without adding new language. This is accomplished by merely extending the meanings of already defined PL/I statements, where appropriate. For example, by extending the meaning of the arithmetic operators (+, *, _, I, **) to cover formal data types, formal expressions can be defined and established. By extending the arithmetic assignment statement, formal variables can be assigned formal values, etc. While the new data type and extended meanings of statements are necessary, other extensions involving additional language are also necessary. These are summarized as: a) Addition of scale attribute, RATIONAL, to provide an exact noninteger arithmetic capability. b) Addition of six built-in functions to support the FORMAL data type: FORMAL, NUMERIC, CHAIN, DERIV, FAC, COMB, and pseudo-variable DEPEND(X). c) In addition to the built-in functions that add official language to PL/I, there would be many function procedures that do not add to the official PL/I language, but that constitute a basic standard library of routines to manipulate the expressions. Extract: The domain attributes 3. The domain attributes As mentioned earlier, to perform algebra in PL/I, as class of arithmetic variables must be introduced that represent formal or abstract mathematical expressions rather than numerical quantities. This is accomplished by: 1. Introducing a new category, called Domain, which contains the already defined PL/I arithmetic data types and the new formal data type. 2. Defining three attributes of this category Domain - FORMAL, ATOMIC, NUMERIC - to distinguish between items. 3. Extending the PL/I declaration statement to cover the three new attributes. '.. " ...,. All previously defined arithmetic forms are covered by the NUMERIC attribute, and since these forms already exist in the language, NUMERIC would be the default declaration. A formal variable would be explicitly declared: FORMAL or {FORMAL} ATOMIC ATOMIC, which implies FORMAL, conveys that a formal variable represents itself. If the attribute FORMAL is given to an arithmetic variable, the variable may appear in an arithmetic assignment statement and may represent any of a set of formal (symbolic) mathematical expressions. If, for example, we write: DCL (A, (B, C) ATOMIC, D, E) FORMAL; A = B+5*C; E = 5; ALPHA: D = E*A; It must be stressed that the above set of assumptions was somewhat arbitrary. A different set could have been selected and easily justified. The particular choice is not significant for the central purpose of the paper but was included only to demonstrate where the decisions reflect themselves in the language. then we say that A, D, and E are "assigned" FORMAL variables. The value of a FORMAL variable is the expression assigned to it. If a variable is declared ATOMIC, it is its own value, Le., it is an atom. In the above example, Band C are atoms while A, D, and E all have expressions assigned to them. The value of A is the expression B+5*C, the value of E is the expression 5, and the value of D is the expression 5*(B+5*C). When an arithmetic expression is evaluated, each of its variables is replaced by its current value. In the case of FORMAL variables, this implies a process known as unraveling. This means that each p.onatomic variable appearing in the expression is replaced by the expression it names. In the above example, for instance, during the expression evaluation process for D, E is replaced by the FORMAL constant 5, and A is replaced by the expression B+5*C, their current values. Therefore, D names the expression 5*(B+5*C). Note that an atom may become part of a value of a nonatomic variable either directly or indirectly via the unravel process. A variable is declared to be either an atom or an assigned variable and may not change from one to another. Extract: Other attributes of formal variables 4. Other attributes of formal variables In developing a complete system, it is necessary to identify the complete set of attributes pertaining to FORMAL arithmetic data items. Investigation has shown that attributes to be supported are not as much of a language definition problem as they are costly to implement. To assist in keeping the paper specific, and in trying to consider implementation costs, assumptions were made on attributes to be supported. For example: a. The FORMAL data item is represented in coded form, ie., PICTURE attribute is not supported. Attributes specifying base, scale, and mode are used to complete the characteristics. The FORMAL data item is binary base, REAL mode and either FLOAT or RATIONAL scale (see description of RATIONAL attribution). The above implies that FIXED, DECIMAL, PICTURE, and COMPLEX would not be supported. b. FORMAL data items may be used with Dimension, Level Number, SECONDARY, ABNORMAL, INTERNAL, EXTERNAL, STATIC, CONTROLLED, AUTOMATIC, and INITIAL. c. All subscripts must be numeric. d. STATIC FORMAL variables may not be initialized. e. Precision as applied to FORMAL values is used solely to determine width of constants in input/output. It must be stressed that the above set of assumptions was somewhat arbitrary. A different set could have been selected and easily justified. The particular choice is not significant for the central purpose of the paper but was included only to demonstrate where the decisions reflect themselves in the language. Extract: Scope of a formal variable 5. Scope of a formal variable Unlike FORTRAN, PL/I employs the concept of scope within subroutine and function boundaries. In considering FORMAL data types, particularly ATOMIC variables, two views can be taken regarding scope rules. One view is that ATOMIC variables are actually constants and should be known throughout a program. That is, they should have the permanent attributes of EXTERNAL STATIC. The other view is that FORMAL variables, ATOMIC included, should obey the same scope rules as any other name. This view is explored here. It is proposed that when a FORMAL variable is references in a PL/I program, it obeys the same scope rules as any other scope name. Explicit and contextual declarations are used to distinguish between variable names. When an atom is assigned to a FORMAL variable as part of its value (either directly or indirectly through the unraveling process), the atom is attached to it until another expression is assigned to the variable. For example: DCL (A ATOMIC, B,C,D ATOMIC) FORMAL; B = A+l; /* A IS AN ATOM AND IS ATTACHED TO B. */ C = B+D; /* A AND D ARE ATOMS AND BOTH ARE ATTACHED TO C. THIS IS BECAUSE B IS REPLACED BY ITS VALUE, NAMELY, A+1. */ ". '.. .'~ . Note that because atoms appear as values of other FORMAL variables, an atom may exist outside of its scope. For example: BEGIN; DCL (A, B ATOMIC) FORMAL; A= B; BEGIN DCL (B, C ATOMIC STATIC) FORMAL; B = C; A = C; /* THE B, C REFERENCED HERE ARE THE ONES LOCAL TO THIS BLOCK. * / END; /* AT THIS POINT A HAS AS ITS VALUE THE ATOM C FROM THE INNER BLOCK. * Extract: Rational-scale arithmetic 6. Rational-scale arithmetic Traditionally, higher-level languages have supported floating-scale and fixed-scale arithmetic. Since its inception, the IBM 7090 FORMAC system has supported a rational-scale arithmetic capability. Experience with this system supports the knowledge that there are many problems that require exact, nonintegral values for their solutions. Some individuals have used the 7090 FORMAC system primarily for its rational-scale feature. One such application involves the inversion of matrices whose entries are integers, and the results of which are to be exact fractions. This causes one to wonder if rational arithmetic might not be a desirable extension to the numeric features of PL/I, independent of the formula manipulation extension. A new arithmetic-scale attribute, called RATIONAL, is added to the language. It is to be used with other attributes specifying base and mode. Variables declared to be RATIONAL would be treated conceptually as a triple (X, Y, Z), denoting the integer part, the numerator, and the denominator, respectively, of the rational number. For example, a rational numeric quantity 2+1/4 would be handled as an ordered triple (2,1,4). Rational constants must be distinguished from fixed and floating scale constants in the source language. An alphabetic character, such as R, appended to the constant, would suffice as a notation. For example, 36R would be the triple (36,0,1) and 1+2/3R would be the triple (1,2,3). In terms of hierarchy, RATIONAL ranks higher than FIXED but lower than FLOAT. Extract: Data manipulation extensions 7. Data manipulation extensions Since the FORMAL datatype was introduced to permit the building and manipulating of formal expressions, PL/I data handling must be further defined to permit this capability. This section describes extension to PL/I data handling and shows how formal expressions are treated. 7.1. Formal expressions An expression may be defined as an algorithm used for computing a value [9]. Further, expressions are of three types: scalar, array, and structure, depending on the types of operands involved. The type of the result is the same as that of the operands. Operands in a scalar expression need not have the same data attributes. If they differ, well defined conversions will be performed before the operation. Formal expressions have the same syntax as other PL/I expressions, but certain restrictions or rules must be observed if expressions of type FORMAL are desired. The following paragraphs describe some of these considerations. Formal data types may appear as operands of the arithmetic operators +, -, * , **, and /. Mixed characteristics are allowed within a formal expression. Conversions will automatically take place before an arithmetic operation to ensure that the data items have the same characteristics. 7.1.1. Conversions It is obvious that the conversions to be defined depend on the attributes permitted for the data type. Given the assumption stated earlier, the following conversions must be provided: a) Domain conversions are meaningful between data types FORMAL and NUMERIC. Rules and techniques for converting between source and target, base, scale, mode, and precision must be specified. b) Arithmetic conversions must be extended. Conversions between RA TIONAL, and FIXED and FLOAT must be defined. c) Type conversions must also be extended to define conversions between bit strings and FORMAL, and between character strings and FORMAL. 7.1.2. Comparison operations In addition to extending the arithmetic operators +, * , /, -, ** the comparison operators = and '" are supported for FORMAL expressions. These operators would imply that the expressions are evaluated, simplified, and then compared for identity. For example: A*(A+B)=A**2+A*B returns a false relationship because the expressions are not identical even though they are equivalent. Note, however, that A+A=2*A would return a true relationship because automatic simplification would precede the comparison and A+A -+ 2A is one of the automatic simplification transformations that are performed. 7.1.3. Evaluation of formal expressions The value of a formal expression is the expression it names. A variable is evaluated by replacing it with its value. The order of evaluation is the same as that specified for numeric variables in PL/I. Certain functions, supported as generic built-in functions for numeric arguments in PL/I, may be represented symbolically in a formal expression as operators. These functions may be numerically evaluated as a user operation. These are: EXP LOG2 TAND SIN TANH SINH LOG ATAND TAN COSD SQRT, ATANH LOmO ATAN SIND COS COSH, ATAN (x, y) . Three additional functional operators, F AC(X), COMB(X, Y) and DERIV, representing the factorial, combinatorial, and derivative operators, respectively, are supported for FORMAL arguments. 7.1.4. Erasing formal expressions The facility to erase a formal expression is provided by allowing an empty expression to be a valid expression, subject to the restrictions stated below. For example, if the user has previously written X = A**2+SIN(B*C*D+B**2)+A*B**3; and after processing this expression, wants to free the storage occupied by the value of X, he may then write: x =' ' The variable X would be assigned a null value. 7.2. Input/output facilities The input/output facilities described in PL/I [9] would be extended to support the FORMAL data types. Editing for comprehensible output is recognized as being vitally important to a successful system. Although some work has been done in defining the I/O language extension, additional work continues. 7.3. Syntax motation In the remainder of this document, we have used the PL/I syntax language to indicate the syntax of statements and function arguments. The syntax used is consistent with PL/I [9] with respect to the capitalization of keywords and the use of parentheses, braces, and brackets. The following additional notation variables were introduced: formal-exp: Any PL/I expression that is evaluable to type FORMAL. formal-var: Any variable of type FORMAL. atom-var: A formal variable whose value is ATOMIC formal-item: Any formal data, i.e., a formal expression or a formal variable assigned to an expression as its value, or an atomic variable. num-exp: Any PL/I expression that is evaluable to type numeric. integer: Any whole number, either FORMAL or numeric. In all uses of integer, type FORMAL or numeric has been explicitly stated pointer: A variable of type POINTER as defined in Pi/I list processing. Wherever used, its value must point to a chain of formal data items. We define chain as an ordered set of formal items. 7.4. Function procedures It was mentioned earlier that a facility for defining and constructing formal expressions is necessary but not sufficient for a useful system. The ability to symbolically manipulate the mathematical expressions at execution time constitutes a significant portion of the total formula manipulation capability. In the IBM 7090 FORMAC system, separate statements involving individual keyword commands were used to specify most of the various operations. Differentiation was an exception. In this design, references to function procedures appearing as operands in expressions will be used to indicate the various mathematical operations. It is assumed that an automatic simplification capability similar, to that of the 7090 FORMAC system is provided. User control over evaluating or retaining the transcendental and numeric functions, as symbolic operators, will be provided by setting bits of an externally defined system word. Also, control to cause expansion as a part of the simplification process will be provided. This section contains a brief description of the arithmetic function procedures. The majority of the functions described in this section are generic. Reference to a generic function causes the selection of a certain member of the family, depending on the attributes of the arguments. The remainder of the functions are nongeneric, i. e., each function name makes reference to only a single member. Some of the functions are defined as built-in functions and are explicitly labeled as such in the description that follow. Consistent with PL/I argument handling, conversions will be performed when necessary for those functions explicitly defined as built in. For those functions that are not built in, whether generic or not, the user must provide arguments that match one of a set of allowable attributes explicitly stated in the function description. Each of the functions in this class are subject to the following conditions: a) All the declarations for each function used must be explicitly stated in the user's source program. b) Arguments passed to the function must identically match the parameters of that function; i. e., the attributes and number of arguments must match one of the alternative names provided for the function. c) No argument conversions are provided. Note that although this approach requires some user effort, it offers the advantage of independence and flexibility. By providing the functions outside the official language as separate library modules, the set can be added to, deleted from, and modified by the user without disturbing the basic system. Two broad classes of functions are described: those that perform algebraic manipulations, and those that enable the user to write his own manipulation functions. Extract: Algebraic manipulation functions 8. Algebraic manipulation functions This set of functions performs common algebraic'and'ailalytic transformations on an expression. Included in this category are formal differentiation, expansion, substitution, simple factoring, fraction-handling, and equivalence matching. 8.1. Formal differentiation functions A formal differentiation facility is supported through the use of three functions: the DEPEND pseudo-variable, the DEPEND function, and the DERIV built-in function. The first two allow the user to manipulate dependence lists, while the third function performs formal differentiation. The need for a dependence list or chain, formed by the use of either the CHAIN or FIND function (described later) is illustrated as follows: Suppose we are to differentiate 2*X with respect to Y, where both X and Y are atoms. The answer is 2*dX/ dY, which may be simplified to zero only if X is independent of Y. For this reason, there must be a way to associate an atom with other atoms on which it is dependent. Associating an atom with a chain or list of atoms, called a dependence chain, suffices. For example, if Y is an atom and is in the dependence list of X, then X depends on Y. The definition of dependence is transitive and is determined at the time of differentiation. The functions are: (1) DEPEND (atom-var) = pointer. This function attaches a chain of atoms as the dependence list of atom-var. (2) Pointer = DEPEND (atom-var) This function permits the user to access the dependence list of atom -var. (3) DERIV (formal-exp, atom-var1 [, integer 1] [, atom-var2 [, integer] . . . ). This built-in function returns the symbolic formal derivative [ommitted figure] where formal-exp is any expression of type FORMAL, atom-var is a formal variable whose value is type ATOMIC, and ni is an integer representing the order of differentiation. Example: DCL( (A, B, C)A TOMIC, X, Y) FORMAL, M POINTER; DEPEND (A) = CHAIN (B); X = B+A**2+C; Y = DERIV (X, B); /* Y WILL BE ASSIGNED THE VALUE 1+2*A*DERIV(A, B, 1) */ 8.2. The expansion functions There are three expansion functions. One function, MULT, applies the multinomial law of expansion to a given expression, another function, DIST, applies the distributive law, and the third function, EXPAND, applies both laws recursively. The purpose of these functions is to remove parentheses wherever possible from the formal expression to which they are applied. (1) MULT (formal-exp) The multinomial expansion law is applied to all occurrences of a sum raised to an integral power within formal-expo (2) DlST (formal-exp) The distributive expansion law is applied to all products containing simple sums (one in which a sum is not raised to a power other than =F 1). (3) EXPAND (formal-exp) The multinomial and distributive laws are applied recursively to formal-expo This is applied to all levels of depth. Example: DCL( (A,B,C) ATOMIC, Z,X, Y) FORMAL; X = (A+B)**2; Y = 2*A*(A+B)-X; Z = EXPAND(Y)-MULT(Y); /* Z WOULD HAVE A RESULT OF 2*A**2+2*A*B-2*A*(A+B) */ 8.3. The substitution functions The substitution functions are used to substitute an expression bi for each occurrence of another expression ai in the formal expression designated as the argument. There are two substitution functions, EV AL and REPLACE. (1) EVAL (formal-exp, pointer) Performs simultaneous substitution of values using the data items in the chain (referenced by pointer) as ordered pairs. No substitution is affected by the results of any other substitution and substitutions may be made only for atoms. . (2) REPLACE (formal-exp, pOinter) Performs sequential or iterative substitution. After each substitution, the intermediate results are simplified and the next pair of substitution items are acted upon. An attempt is made to permit substitution for expressions. .Example: DCL( (A, B)ATOMIC X, Y) FORMAL, P POINTER; X = A+B; P = CHAIN (A, A-B, B, 2); Y = EVAL (X, P); /* Y IS ASSIGNED THE VALUE A-B+2*/ Y = REPLACE (X, P); /* Y IS ASSIGNED THE VALUE A * / 8.4. The factoring function The facto ring function group provides a special class of factoring capability. There are four functions in this group: COEFF, HIGH POW, LOWPOW, and GCF. The HIGH POW and LOWPOW functions constitute a subset of the COEFF function. The two basic facto ring capabilities performed by HIGH POW and LOWPOW are coefficient finding (the COEFF function) and facto ring out the greatest common factor (the GCF function). Both the GCF and COEFF functions treat the expression being wotkedon as a polynomial. That is, both functions work on the top level of the expression, treating it as a sum of products of powers of subexpressions.' Therefore, it is generally desirable to use expanded expressions as arguments to these functions. (1) COEFF (formal-expt. formal-exP2, num-exp, num-vaq, num-var2) This function attempts to find the coefficient of a well-formed expression (formal-exP2**num-exp) in formal-eXP1' In addition it returns the following: for num-exp =0 num-varl num-var2 [num-varl the highest power of formal-eXP2 in formal-eXP1' the highest power of formal-eXP2 in formaleXPl which is less than num~exp. If none exists, num-vaq = O.] [num-var2 = the lowest power of formal-eXP2 in formal-exPl' the lowest power of formal-exP2 in formaleXPl which is greater than num-expo If none exists, num-var2 = O.] (2) HIGHPOW (formal-expl. formal-exp2) (3) LOWPOW (formal-eXP2, formal-eXP2) These two functions return the highest and lowest power of formal eXP2 in formal-eXP1' (4) GCF (formal-exp) Returns a formal expression that is the mathematical equivalent of formal-exp with the greatest common factor in all the summands fac tored out. Example: DCL( (A,C,X) ATOMIC, Y, Z) FORMAL, (E, F) FLOAT; Y = A*X**2+C*X**4; Z = COEFF (Y,X, 2, E, F); /* Z WILL BE ASSIGNED THE VALUE A, WmCH IS THE COEFFICIENT OF X**2. E WILL BE ASSIGNED THE VALUE ZERO SINCE THERE ARE NO POWERS OF X LESS THAN 2 IN Y, AND F WILL BE ASSIGNED THE VALUE 4 WHICH IS THE LOWEST POWER GREATER THAN X**2. */ 8.5. The fraction-handling junctions The fraction-handling functions allow expressions to be written in the general form a/b. There are four functions in this group: CODEM, which places subexpressions at all levels in the form a /b; FRACTN, which causes only the outermost level of the expression to be placed in the form a /b; and NUM and DENOM, which return the expression's numerator and denominator, respectively, without rewriting the expression. (1) CODEM (formal-exp) Returns a formal expression which is the mathematical equivalent of formal-exp, but which is rewritten in the form a /b. Neither a nor b can be written as a fraction having a denominator different from 1. (2) FRACTN (formal-exp) Returns a formal expression which is the mathematical equivalent of formal-exp, but which is rewritten in the form a/b. FRACTN only searches the outermost level of the expression to determine the num erator and denominator. The resultant formal expression may have a numerator and/or denominator that is further reducible. (3) NUM (formal-exp) (4) DENOM (formal-exp) These functions return the numerator (or denominator) of formal exp. Example: DCL ((A,B,C,D,E,F)ATOMIC, Y,X) FORMAL; X = CODEM( (I+A/B)/(C/D+E/F) ); /* X WILL BE ASSIGNED THE VALUE D*F*(A+B)/(B*(C*F+D*E) ) */ Y = NUM(X); /* Y WILL BE ASSIGNED THE VALUE D*F*(A+B) * / 8.6. The equivalence matching junction EQUIV (formal-exPl, formal-eXP2, num-exp) The equivalence matching function augments the comparison operators = and "', by providing a match for mathematical equivalence between two given formal expressions. [8.7] The domain conversion junctions Two built-in conversion functions enable the conversion of arithmetic data between formal and numeric domain. (1) FORMAL (num-exp) Converts a value from numeric type to formal type. (2) NUMERIC (formal-item) Converts a value from formal type to numeric type if possible. Extract: Nonalgebraic manipulation functions 9. Nonalgebraic manipulation functions The IBM 7090 FORMAC system provided a weak set of primitives with which the user could build his own manipulation routines. An effort was made to significantly improve this capability in this new design. Collectively, these functions enable the user to write his own algebraic manipulation functions in a convenient, natural manner. They provide this capability by allowing the user to obtain parts of expressions as well as information about the expression structures. These functions are also useful when writing recursive routines, controlling loops, etc. Also included in this group of functions are the chain manipulation and chain building functions. 9.1. The integer junctions The integer functions, FAC(X) and COMB(X, Y), are used to compute the factorial and combinatorial values for the arguments given. These built-in functions may be retained as symbolic operators in an expression, or may be evaluated as functions, at the user's option. (1) FAC (formal-item) Computes the factorial of the formal data item. (2) COMB (formal-iteml, formal-item2) Computes the combinatorial, an integer value where COMB(X, Y) = c; 9.2. The lead operator junctions The lead operator functions, LOP and INTLOP, allow the user to determine the lead (outermost) operator of an expression. Some examples of lead operators are: Expression Lead operator a*b**c * x**(y/sin(z) ) ** (a-b)*b*(c-d)+e + a var LOP returns the lead operator as a character string; this is useful for outputting expressions and making code more transparent. INTLOP returns an integer representation of the lead operator; this is useful for indexing transfer tables and for testing classes of operators grouped together such as: arithmetic operators, transcendental operators, etc. (1) LOP (formal-exp) Returns a character string representation for the outermost operator of formal-expo (2) INTLOP (formal-exp) Returns an integer representation for the outermost operator of formal-expo 9.3. The argument counting functions This group of functions allows the user to count the number of operands of the outermost operator, and, when used in conjunction with the partition functions, allows the user to perform algebraic transformations. They are particularly useful when writing recursive procedures. There are three functions in this group: NARGS, NTERMS, NFACTRS. (1) NARGS (formal-exp) Returns the number of arguments of the outermost operator of formal-expo (2) NTERMS (formal-exp) Returns the number of terms in the expression. (3) NFACTRS (formal-exp) Returns the number of factors in the expression. 9.4. The partition functions These functions provide a basic partitioning capability, thereby allowing the user to write his own algebraic transformations to manipulate expressions. The functions in this group are used to extract subexpressions from a given expression, returning either the subexpression or the expression with a particular subexpression removed. The four partition functions are: (1) ARG (formal-exp, integer) Returns the nth argument of the lead operator of formal-expo (2) TERM (formal-exp, integer) Returns the nth term of the lead operator of formal-exp, if it is a +. (3) FACTOR (formal-exp, integer) Returns the nth factor of the lead operator of formal-exp, if it is a *. (4) REMOVE (formal-exp, integer) Removes the nth operand from formal-expo 9.5. Miscellaneous functions Miscellaneous nonalgebraic manipulation functions are described below. (1) SEARCH (formal-exPl> formal-exP2, integer) Returns the index value indicating which argument of the lead opera tor of formal-exP1 is the expression formal-exP2' (2) ATOMIC (formal-name) Indicates if formal-name is atomic. (3) CHAIN (formal-item!> formal-item2,'" ,) Creates a chain of the formal-items listed. (4) FIND (formal-exp) Builds a chain of all unique atomic variables in formal-expo (5) CONCAT (pointer!> pointer2) Concatenates the two chains, pointer1 and pointer2' (6) SUBSET (pointer, integer!> integer2) Returns a pointer to a chain of formal data items identified as the subset of data items in the chain pointed to by the argument, pointer. (7) LOOK (pointeq, pointer2) Determines if a chain of items pointed to by pointer2 exists in the chain pointed to by pointeq. (8) NUMBER (pointer) Counts the number of items in a chain. (9) CALL BUILD (pointer, character string, formal-var) This subroutine permits the creation of expressions by making the items of a chain into the arguments of the lead operator given as the character string. The expression is assigned to formal-var. Extract: Conclusion 10. Conclusion The results of these study have shown that, in extending PL/I to handle mathematical symbol manipulation, goals of embeddedness and minimum language extension can be achieved. Introducing the formal data type, and extending the meanings of many of the PL/I statements, were critical to the entire extension. Minimum languages was involved in that only eight keywords were added: FORMAL, NUMERIC, RATIONAL, CHAIN, DERIV, FAC, COMB, and DEPEND(X). The use of function procedures, a facility which already exists in PL/I for expressing the mathematical manipulations to be performed on the expression, appeared to have more advantage than disadvantage. That is, although the user must declare the functions and supply proper.characteristics for the arguments of the functions, the flexibility' and modulatiry - in being able to add to, delete from, and modify standard routines - are believed to be more important. Also, official language does not have to be added to PL/I. Although the readers who are familiar with IBM 7090/94 FORMAC can detect a great similarity between the FORMAC capability and this proposal, there are some significant differences. The most extensive is in the class of functions that are primitive in nature. That is, a complete set of functions have been provided which permit users to specify algorithms and routines of their own choosing. The user routines or algorithms can then supplement the standard library of routines. This paper was devoted solely to capability and language. Although there are no plans to implement this work, implementation of a compiler and algorithm design was a constant consideration in the investigation. Modeling of certain aspects of the system is being done to assist in evaluations and measurements. Modeling will also be used to experiment with new 'ideas for making the overall capability more mathematically powerful. in Bobrow, D. G. (ed) "Symbol Manipulation Languages and Techniques", Proceedings of the IFIP Working Conference on Symbol Manipulation Languages. North-Holland Publishing Co., Amsterdam, 1968 view details in Tobey, R. G. (ed) Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM Federal Systems Center, Gaithersburg, Maryland, July-August 1968, IBM Programming Laboratory Report No. FSC-69-0312 (proceedings published June 1969). view details in Tobey, R. G. (ed) Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM Federal Systems Center, Gaithersburg, Maryland, July-August 1968, IBM Programming Laboratory Report No. FSC-69-0312 (proceedings published June 1969). view details in Tobey, R. G. (ed) Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM Federal Systems Center, Gaithersburg, Maryland, July-August 1968, IBM Programming Laboratory Report No. FSC-69-0312 (proceedings published June 1969). view details in Tobey, R. G. (ed) Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM Federal Systems Center, Gaithersburg, Maryland, July-August 1968, IBM Programming Laboratory Report No. FSC-69-0312 (proceedings published June 1969). view details wants to learn PL/I. The reader is assumed to have previous programming experience, and a scientific background. The book concludes with a chapter on PL/I-FORMAC. in Tobey, R. G. (ed) Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM Federal Systems Center, Gaithersburg, Maryland, July-August 1968, IBM Programming Laboratory Report No. FSC-69-0312 (proceedings published June 1969). view details in Tobey, R. G. (ed) Proceedings of the 1968 Summer Institute on Symbolic Mathematical Computation, IBM Federal Systems Center, Gaithersburg, Maryland, July-August 1968, IBM Programming Laboratory Report No. FSC-69-0312 (proceedings published June 1969). view details in [ACM] Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, March 23-25, 1971 Los Angeles (SYMSAM 71) view details The system is designed to run under OS/360 on a Model 40 or higher with at least 256K bytes of core storage available. It is designed to run in conjunction with the OS/360 PL/I-F Compiler. An earlier version of FORMAC was written for the IBM 7090/94 as an extension of FORTRAN IV, running under the IBM IBSYS-IBJOB monitor. A paper on this system was presented at the 1966 ACM Symposium on Symbolic and Algebraic Manipulation. As will be evident to those familiar with that system, significant extensions have been incorporated into the new version of FORMAC described here, especially with respect to I/O, the arithmetic capability, and user-defined functions. The paper has four sections. The first section gives an actual programming example, showing the computer output which is produced. The second section describes the externals of the PL/I-FORMAC language, in outline form. The third section outlines the implementation of the system. And the fourth sections compares the current system with the 7090/94 system mentioned above. An annotated bibliography is appended. Extract: Overview of FORMAC-PL/I Language Overview of FORMAC-PL/I Language The FORMAC-PL/I language is a superset of the PL/I language. By this we mean that, in addition to FORMAC statements, the user may include any PL/I statements that he desires in his program. In this document, the term "PL/I Language" will always refer to the language supported by the OS/560 PL/I-F Compiler. Let us consider the following simple example of how FORMAC statements are mixed with PL/I statements: A = X/Y + 2; LET (A = XIY + 2); The first of these two statements is a PL/I assignment statement. It specifies that the constant 2 is to be added to the quotient of the PL/I numeric variables X and Y, and the resulting number assizned to tile PL/I variable A. The second statement is a FORMAC assignment statement, as indicated by the keyword LET. It specifies that the constant 2 is to be added to the quotient of the FORMAC variables X and Y, and the result assigned to the FORMAC variable A. Of course, the first of these statements performs only numeric computation, while the second statement involves formula manipulation. In general, FORMAC statements are inserted into a PL/I program by enclosing the FORMAC statement or expression in parentheses following a reserved keyword. The keyword LET, for example, is used to indicate a FORMAC assignment statement. The FORMAC and PL/I environments of a program are completely distinct. In the above example, there is no conflict whatsoever between the PL/I variables A, X and Y and the FORMAC variables of the sarae name. Special controls are provided, however, so that communication between the two environments is possible. The fact that the user has full access to PL/I facilities in wrlting a program means that both numerical and analytic techniques may be used in the same program. Horeover, the powerful PL/I flow of control facilities (DO, IF statements, etc.) can be used to good advantage in FORMAC prosrams. Extract: The Substitution Functions, EVAL and REPLACE 2.11.3. The Substitution Functions, EVAL and REPLACE These functions replace certain specified patterns in the argument expression specified expressions. EVAL replaces atomic variables and system constants by specified expressions and replaces functions by specified functional patterns (e.g., F.(argl,arg2) argl*COS(arg2), SIN(arg) by arb-arg**5/6, where arg, argl, and arg2 may be arbitrary unknown FORMAC expressions). REPLACE replaces subexpressions of the argument expression specified expressions, thhen multiple substitutions are requested of EVAL or REPLACE, EVAL carries out a parallel substitution, while REPLACE carries out a serial substitution. Extract: The Analytic Differentiation Functions: DERIV, DIFF, and DRV 2.11.4 The Analytic Differentiation Functions: DERIV, DIFF, and DRV The DERIV function carries out analytic differentiation on expressions with respect to one or many variables. Thus, the statement, LET ( A = DERIV(X**2 * Y**2, X, Y) ); causes A to be assigned the value 4 X Y Further argument options permit derivative orders to be specified. The DIFF pseudo-variable is used to specify a formula for the derivative of a function, when the expression for the function itself is not known. When the named unspecified function variable is differentiated, then the correct derivative form is automatically substituted. For example, LET ( Y : F.(N*X) ; DIFF(F) = ($(1)*'2 + A**2 ); R = DERIV(Y,X) ); The second of these statements defines F to have a derivative given by the mathematical formula f(x)=x**2 + a**2. As a result, R is assigned the value N*(9 X**2 + A**2). The DRV function is used to name derivatives of an unspecified function with respect to an argument. This is differentiation by argument, in contrast with differentiation of an expression w|th respect to a variable, which is provided by DERIV. Extract: COEFF function 2.11.5 COEFF function This function is used to determine the coefficient of a desired expression in another expression. For example, LET ( Y = A * X**2; C = COEFF(Y,X**2) ); The second assignment statement takes the coefficient of X**2 in Y, and so gives the value A to C. Extract: HIGHPOW and LOWPOW functions 2.11.6 HIGHPOW and LOWPOW functions These functions return, respectively, the highest and lowest power of a given expression in another expression. For example: LET (Y : X**5 + X; A : HIGHPOW(Y,X); B = LOWPOW(Y,X) ); gives A the value 5, and B the value 1. Extract: NUM and DENOM functions 2.11.7 NUM and DENOM functions These functions compute the numerator and denominator of the desired expression. For example, LET ( P = A/B; Q = NUM(P); R = DENOM(P) ); gives Q the value A and R the value B. Extract: Expression analysis functions LOP, NARGS and ARG 2.11.8 Expression analysis functions LOP, NARGS and ARG These functions collectively allow for a detailed analysis of a FORMAC expression in order to obtain information about its structure or to extract subexpressions. The LOP function determines the "lead operator" of the function, the NARGS functions determines the number of arguments that the lead operator has, and ARG can be used to determine each of the arguments. Extract: CODEM and FRACTN 2.11.2. CODEM and FRACTN These functions are used to place the expression over a common denominator. CODEM places subexpressions at all levels in the form a/b, while FRACTN operates only at the outermost level. For example, LET( X = A/(R+C/D) + E/F ; Y : CODEM(X); Z = FRACTN(X); ); results in the assignments Y <- (F D A + (C + D B) E)/( (C + D ~) F) Z <- ( F A + (B+C/D) E) / ((B+C/D) F) Extract: Automatic Simplification 2.11.1 MULT, DIST and EXPAND These functions provide control over automatic simplification, and will be explained in section 2.13. 2.13 Automatic Simplification Simplification of user expressions takes place automatically. The simplification is of two types. First, ordinary mathematical identities are applied to make the expression simpler. Thus, for example, the expression A÷0+i*A is simplified to 2*A, The second form is applied by ordering the arguments of a plus or times operators in order to provide a normal form. This is necessary to make the implementation of certain algorithms considerably easier. For examples if the system is to determine whether the expressions B+A+C and C+A+~ are equal, it can do so most easily by first reordering both expressions to, say, A+B+C. The programmer is provided with several controls over the simplifications to be applied, frost of these are provided by the TRANSs INT and EXPND options of the OPTSET statement (see section 2.14). In this section, we discuss only the MULT, DIST and EXPAND built-in functions. Ordinarily, FORMAC expressions are not expanded according to the multiplicative and distributive laws of mathematics. That is, for example, the expression (A+B) * (C+D)**2 will not be expanded out in any way during the automatic simplification process. The user can, however, force this expansion to take place via the functions MULT, DIST and EXPAND. The function MULT forces the multiplicative law of mathematics to applied, while the function DIST forces distributive law to be applied. Thus, for example, the statement LET ( X = MULT{ (A+B)*(C+D)**2) ); will cause the value (A+B) (2 C D + C^{2} + D^{2} ) to be assigned to X, while the statement LET( Y = DIST( (A+B)*(C+D)**2) ); will cause the value A (C + D)^{2} + B (C + D)^{2} to be assigned to the variable Y. The EXPAND function causes both the distributive and multiplicative laws to be applied. Extract: OPTSET statement 2.14 OPTSET statement The OPTSET statement allows the programmer to set certain options which will affect the automatic simplification and printout algorithms. The options are described in the following paragraphs, with the default option underlined. TRAHS / NOTRANS. TRANS causes the transcendental functions (such as SIN, LOG) to be evaluated whenever their argument evaluates to a numeric constant. In addition, tile automatic simplification routine carries out certain transformations on transcendental functions, such as: SIN(#P/6) -> 1/2. The NOTRANS option suppresses these simplifications, with, for example, SIN(#P/6) and LOG(3) being maintained as symbolic entities. INT/NOINT. INT causes the FORMAC automatic simplification routines to evaluate the integer functions FAC, COMB and STEP whenever their arguments are numeric constants, such as in: FAC(3) -> 6. NOINT suppresses this action S causing the forms to be maintained as symbolic entities. EXPND/NOEXPND. The EXPND option causes the multinomial and distributive laws to be applied during the simplification of expressions. This option has the same effect as continual application of the EXPAND function. This effect is suppressed with the NOEXPND option, which is the default. EDIT/NOEDIT. The EDIT option causes the output produced by the PRINT_OLIT statement to be in edited format, corresponding the usual mathematical notation -- asterisks removed, exponents raised, etc., as illustrated in the example in Section 1. NOEDIT results in an output format that conforms to the input requirements of FORMAC. Thus, asterisks appear where multiplication is intended, and '**' is used to indicate exponentiation. PROPER/IMPROPER. The PROPER option can be used to force the printout of improper rational fractions in proper form. With this option, for example, the fraction 4/3 will be printed out as (1+1/3), IMPROPER would cause the fraction to be printed as 4/3. LINELENGTH=XXX(120). This option causes FORMAC output to be printed in lines of length not exceeding length XXX. This option is most useful when the output must be formatted to appear on 8-1/2 by 11 paper. PRINT/NOPRINT. The PRINT option can be used to print out the value resulting from the execution of each LET statement. Its main use is for debugging. Extract: FORMAC Variables 2.2 FORMAC Variables The naming rules for FORMAC variables are the same as those for naming PL/I variables, except that certain names are reserved, and the maximum length is 8 characters. FORMAC and PL/I variables are maintained as distinct entities even when a FORMAC and PL/I variable have the same name. FORMAC variables may be subscripted with up to 4 subscripts. A subscript expression must evaluate to an integer in the range -31622 to +31622. Subscripted FORMAC variables, like unsubscripted variables, are not declared; in particular, no "dimension" information is required. Space is not reserved for FORMAC arrays, and particular elements arc created only when needed. FORMAC variables are classified as atomic or as signed. An atomic variable, or atom, is a variable which has not been assigned a value. As such, an atom stands for itself, while an assigned variable stands for the expression which has been assigned to it. Extract: FORMAC constants 2.3 FORMAC constants There are four kinds of FORMAC constants: floating point, integer, rational, and system constants. Floating point numbers are represented by one to nine decimal digits with a decimal point end optionally followed by a decimal exponent. Thus, .0032 and 6.E5 are floating point constants. Integer constants are represented by from one to 2295 decimal digits. Rational numbers are represented externally in FORMAC expressions in the form a/b, where a and b are integers, each of which may be up to 2295 decimal digits lonq. There are three reserved names used as system constants: #E represents e HP represents pi 81 represents i, the square root of -1 These symbols may be manipulated just like ordinary FORMAC variables. The difference is that the FORMAC Automatic Simplification routines will treat them as special cases. For example,ftl**2 will be simplified to -1. Extract: The Assiqnment Statement 2.4 The Assiqnment Statement One or more FORMAC assignment statenents may be enclosed in parentheses following the keyword LET. For example, the statement consists of two FORMAC assignment statements. Extract: FORMAC Built-in Functions 2.5 FORMAC Built-in Functions There are three kinds of FORMAC built-in functions: PL/I-like functions, integer-valued functions, and manipulation functions. Each of the names is a reserved system name. Manipulation Functions. The Manipulation Functions are evaluated immediately, after their arguments have been evaluated. They are not maintained internally in symbolic forn. They will be dcscribed in section 2.11. The PL/I-like functions. The following functions supported in PL/I for numeric arcurnents are available for use in FORMAC expressions with symbolic arpuments: SIN ATAN LOG10 COS ATANH LOG2 SINH ATAN(x,y) ERH COSH LOG These functions, with their evaluated arguments (which may be arbitrary FORMAC expressions) are retained as symbolic entities at execution time. Evaluation of these functions with constant arguments is controlled by the TRANS option of the OPTSET statement. (See section 2.14.) In addition to these functions, a number of other functions may appear in FORMAC expressions but will be translated into an equivalent expression containing the above functions. (For examole, EXP(X) becomss #E**X, and SQRT(X) becomes X * * ( 1 / 2 ) . ) These functions are EXP, SQRT, SIND, COSD, TAN, TAND, TANH, ATAND, ATAND, and ERFC. The Integer-Valued Functions. FAC defines the factorial function . COMB defines the combinatorial function. The STEP function may be used to define arbitrary FORMAC expressions which are given by different formulas for different values of the independent variables. Extract: User-Defined Functions 2.7 User-Defined Functions The FNC pseudo-variable can be used to define user-defined functions . The method for doing this is to execute an assignment statement of the following form: FNC(F) = expression i n $(1),$(2), ..., $(n); This statement define s F as the specified function of the n variable s $(1),$(2), ..., $(n). F may then appear in a later expression with any expressions as arguments. For example, LET ( FNC(F) = $(I) + $(2); A = 2 + F(X+2, Y) 1; will cause A to be assigned the value X+Y+4. Extract: Chains 2.8 Chains FORMAC variables may be assigned a list or CHAIN of FORMAC expressions by means of the CHAIN function . For example, LET ( Y = CHAIN(A,B,C) ); will cause Y to be assigned the actual list consisting of (A, B, C). The CHAIN operation provides the capability of building argument lists for FORMAC functions and routines. For example, after the above statement has been executed, then LET ( Z = F.(X,Y) 1; will cause Z to be assigned the expression F.(X,A,B,C). in [ACM] Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, March 23-25, 1971 Los Angeles (SYMSAM 71) view details I 'EY OF PL/]-FO C FORMAC is not a pure language, it may be considered as an extension of a, host language (PL/I or FORTRAN). Formac allows, in addition to numeric evaluations, formal manipulations of mathematical expressions. PL/I-FORI~C contains the whole set of PL/1 instructions {5 ] and specific Formac statements [6 ]. In batch processing a PL/1-FORHAC program unit is submitted to four steps. This program unit is given first to a preprocessor which will "translate" the pure Formac statements into legal PL/I statements. The PL/I source module thus obtained will be passed then to the compiler and the linkage editor, and finally executed. During the linkage editor step two libraries are called : standard PL/i library and FORMAC run time routires library. For example the statement : LET(A = B + C) ; given to the preprocessor becomes : CALL DENFMCI('A=B+C'); The string appearing as argument of DE:IFI4C1 routine will not be altered during th~ compilation. During the execution ~f this statement, the Formac system will buil~ a tree which shall be the internal representation of the expression : A=B+C I B ~ C All Formac run time routines work upo'. trees and generally admit as argun~nts alphanumeric strings. Extract: FORDECAL DESCRIPTION OF FORDECAL We have seen (§ 2) that a Formac statement is first translated into a PL/i statement. All the problem is to have a go)d preprocessor in view of extending Formac capabilities. So it would be possible "easily" to write procedures with Formac arguments, to have the notion of block in Formac, .... But one of th~ particularities of Formac lies in the fast that each Formac variable is of "universal" domain of definition. This imple; that it is impossible to have the block notion, and the recursion problem will be hard to be solved. It is nevertheless possible to write a more "flexible" rreprocessor allowing recursion and particularly Formac variables with LOCAL attribute. An elementary interactive system could consist of a very short PL/I program which while reading a string gives it to the run time routine DENFMC2 (1) and gives back control to the user. We have develop considerab]y such a system by putting in near the whole set of OS/FORV~C "statements" with the appearence of corresponding run time routines calling sequence. We must, in a f i r s t step, provide a set of "commands" whose syntax must be very near of the usual mathematical writing. In a second step we have introduced the notion of "program unit' by the introduction of blocks and of procedures. The syntax of the commands of FORDECAL has been chosen as near as possibl~ to the syntax of the "equivalent" PL/I statement. Thus the command : A = B + 5 ; is the "equivalence" of the PL/I assignment statement : A = B + 5 ; apart the fact the system works only with Formac variables. The FORDECAL system consists of an int~rpreter~ written in PL/i; and of a run t i - me program library obtained from the PL/I and 0S/360 PL/i-FORI.~C librari~.;. Formac run time routines have not been altered in the part concerning formula manipulations, llowever some modules have been re-written either to take into account the CI.IS environment under which Fordecal is running or to introduce new possibilities. The user, once in the Fordecal environment, dialogues with the system by means of the provided commands. These are submitted to two phases : - one of "reading-interpretation", - one of execution. It is also possible ~ divide ~he commands into three categories : - elementary command, - macro-command, - declare command and DEBUG facility command. The action taken by the system during the two phases may differ according to the command category. For an elementary command, the execution is immediate. For example : ~A= FAC(iO) ; This co,and will ca]cu}ate i0i, affect the result to the variable A and print this result according to the standard printing of PL/I-FORMAC. The input phase consists of : - recovering the input string '~A=FAC(IO)' - detecting the character <$> in the f i r s t position of the string, - going to the execution sequence corresponding to the print out command. Th( execution phase of this command consists in giving to the run time routine DE~FI4C2 the arQument 'A=FAC(IO)'. This routine provokes the evaluation of 10! ev(ntually builds a "repword" for A, attaches the value 10! to this repword ant then prints out the result. in [ACM] Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, March 23-25, 1971 Los Angeles (SYMSAM 71) view details Introduction: The simple past. The first version of FORMAC was written for the IBM 7090/94 as an extension of FORTRAN IV running under the IBM IBSYS-IBJOB monitor. It was an experimental programming system to assist in the symbolic manipulation of mathematical expressions and provided such capabilities as symbolic differentiation, expansion, substitution, comparison and evaluation of expressions. The project originated in August 1962 and the system was released in November 1964. References are given in [27]. Comments of users initialized the design and implementation of PL/I-FORMAC, a more flexible system based on the same principles. The first version was released in 1967, the second in September 1969, [27]. The PL/I-FORMAC interpreter, an extension of the OS/360 PL/I(F) compiler, was originally designed to run on an IBM S360 H-level model 40 and above. It consists of two modules of assembled routines whi6h are added to a system's library: the preprocessor and the objecttime library. In March 1970 the SHARE SMC project (now LASM project) composed a list of known errors and proposed extensions of the IBM preprocessor, [21]. In April 1970 a new preprocessor became available. It was developed at KFA-Julich, Germany-West, by R. Schwerdt, [19]. The errors were corrected and most of the proposed extensions were implemented. To make the FORMAC-system again available to FORTRAN-users, a new FORTRAN-FORMAC, comparable with PL/I-FORMAC, has been written for and tested with FORTRAN IV(H) under 0S/360 in 1970 at DRZ-Darmstadt, Germany-West, by Knut A. Bahr, [1]. At 1.1.1971 IBM stopped the FORMAC project. Information about SHARE's FORMAC maintenance and distribution is given in SIGSAM Bulletin No. 26, page 2. The address of the FORMAC library of SEAS is: ZAM/KFA-Juelich, Postfach 365, D517 Juelich I, Germany-West. Extract: SCOPE FORMAC Another early system was the Scope FORMAC Language, [28]. When the system was operational it ran in a 256 K partition of an IBM 360/50 with an IBM 2250 graphic display unit as I/0 device. The system was last operational in January 1969, at which time IBM decided to support it no longer, [29]. Extract: FINSTER A prototype of FINSTER ran on the IBM 360/75 of KFA-Juelich in 1970, in a 160 K partition under OS/MFT and serving four 2260 terminals. Extract: FORDECAL FORDECAL is running in a number of institutions on an IBM 360/67 under CP67-CMS and serving 2741 terminals. The system may be used on an IBM 370 under VM, although the testing of this FORDECAL version is not yet finished, [15]. A TSO-version will be announced in the near future, [15]. FORDECAL is an interactive system similar to a desk calculator. The statements are executed as soon as they have been typed on the key-board of the terminal. Although this system does not allow to execute a program with the whole range the PL/I-FORMAC language itself offers, some statements may be executed repeatedly with either a DO or BEGIN command (compound DO-loops, DOgroups and blocks respectively). The system allows to c~ll user typed (function) procedures, which can be recursive. The FORDECAL statements resemble the PL/I-FORMAC statements, but are written in a syntax as nearly similar as the usual mathematical syntax. FORDECAL uses only the FORMAC-components of PL/I-FORMAC and can be used without any knowledge of PL/I and with only a vague impression of FORMAC. [ii] and [12] survey the system, [13] contains a description of some of the practised implementation techniques and [14], written in French, offers an accurate and detailed description of FORDECAL and its implementation, Extract: TUTOR TUTOR, [16], was originally implemented on an IBM 360/65 at Calspan Corporation, Buffalo, N.Y., under OS/MFT using the FORTRAN GSP package for the graphics facility (an IBM 2250 as I/O device) and an interface program to make it compatable with PL/I. When MVT and the PL/I GSP package became available the program was modified for these facilities. A normal run at Calspan allowed 250 K. Due to changes in Calspan's computer configuration TUTOR's future is uncertain, [17]. TUTOR is a simple conversational system without advanced control commands as provided in FORDECAL. An essential difference between TUTOR and the other interactive systems is its capability of accepting two-sides equations, that is mathematical expressions on either or both sides of the equal sign. Special commands to manipulate equations are implemented. Extract: SYMBAS An experimental version of SYMBAS, a FORMAC orientated version of BASIC, is running under TSS since summer 1972 at KFA-J~lich serving 2741 terminals. A TSO-version of SYMBAS, running under VS2, is in consideration, [9]. To have a system available which is well suited for symbolic as well as numerical applications the interactive, line-orientated BASIC system was chosen and its semantics were extended in the case of symbolic applications. This technique enabled the implementation of an interpreter which evaluates expressions numerically when ~ ever possible. In this extension BASIC variables do not need to have assigned numerical values; they may be interpreted as atoms or symbolic expressions may be assigned to them. So assigning numerical values to all variables of a SYMBAS program does the program run as if it would have been a proper BASIC program. The matrix statements of BASIC are also included and are extended to facilitate fraction free elimination algorithms for symbolic matrices. The run-time routines of FORMAC are used to do symbolic computations. A special editor is available to create and change programs. A debugging system enables the user to stop his program at any point, to display and to reassign variables, and to change statements and program flow. in [ACM] Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, March 23-25, 1971 Los Angeles (SYMSAM 71) view details The best known, purely symbolic systems are, of course, Formac and its current version PL/IFORMAC (Petrick, 1971; pp. 105-114). Formac was the first widely available general-purpose algebraic manipulation system and served for a period to define the field. Certainly, there was a time when one could have safely made the statement that the majority of all mechanical symbolic mathematical computations had been done within Formac. The practical success of these systems, in spite of their rigidity with respect to user modifications and their lack of any seminumerical facilities for rational function computations, is probably due to the overall intelligence of the facilities that were provided. Above all, they were certainly sufficient to support the dominant application area of truncated power series expansion. Current support is minimal. Extract: PL/I-FORMAC The best known, purely symbolic systems are, of course, Formac and its current version PL/I-FORMAC. Formac was the first widely available general-purpose algebraic manipulation system and served for a period to define the field. Certainly, there was a time when one could have safely made the statement that the majority of all mechanical symbolic mathematical computations had been done within Formac. The practical success of these systems, in spite of their rigidity with respect to user modifications and their lack of any seminumerical facilities for rational function computations, is probably due to the overall intelligence of the facilities that were provided. Above all, they were certainly sufficient to support the dominant application area of truncated power series expansion. Current support is minimal. Extract: Symbolic systems SYMBOLIC SYSTEMS. We should mention first a sequence of three early programs for the simplification of general symbolic mathematical expressions represented as prefix-notation tree structures. The first, at M.I.T., was due to Hart, and the other two were due to Wooldridge and Korsvold at Stanford. The latter has survived in current usage as a result of its incorporation, subject to modification, into the MATHLAB, MACSYMA, and SCRATCHPAD systems. In the mid-1960s there appeared two systems, Formula Algol and FAMOUS, which, while dedicated to the symbolic manipulation of mathematical expressions, presented the user with almost no built-in automatic simplification facilities. This was due, at least in the case of FAMOUS, to a conscious decision that, since the "simplicity" of an expression is surely context- dependent, it should be reasonable to present the user with complete control over the simplification process. That is, the user'should be compelled to define all transformations, rather than, as with most systems, be permitted simply to switch on and off the transformations supplied by the system architects. No system of this species has ever solved the inherent efficiency problems to the extent that it could serve more than didactic purposes. Probably neither Formula Algol nor FAMOUS could be revived today. Another lost symbolic system of importance is the Symbolic Mathematical Laboratory of W. A. Martin. This system provided high-quality 2-D graphics on a DEC-340 display and was also the first to employ a light pen for subexpression selection. In some ways, it represented a degree of interaction that has not been duplicated by any subsequent system. Nor were its innovative internal programming techniques restricted to its graphics facilities. Of particular interest is the use of hash coding for subexpression matching (Petrick, 1971; pp. 305-310). in Encyclopedia of Computer Science, Ralston, Anthony, and Meek, Chester L. (eds) New York, NY Petrocelli/Charter 1976 view details in Encyclopedia of Computer Science, Ralston, Anthony, and Meek, Chester L. (eds) New York, NY Petrocelli/Charter 1976 view details in Encyclopedia of Computer Science, Ralston, Anthony, and Meek, Chester L. (eds) New York, NY Petrocelli/Charter 1976 view details |