SYMBAL(ID:350/sym002)An extension of ALGOL to do formal algebraic manipulation.SYMbolic ALgebra. Max Engeli, Swiss Federal Institute of Technology, Zurich, Switzerland 1967 Symbolic math language with ALGOL-like syntax. Implemented for CDC6600. An extension of ALGOL to do formal algebraic manipulation. (Sammett 1966) Places People: Related languages
References: Introduction The "Algebraic Processor" is a general purpose algebraic manipulation system, implemented on the CDC 1604-A at the Swiss Federal Institute of Technology in Zurich. In order to avoid any unintentional limitations, it has been designed as a completely new and self-contained system. On the other hand, existing techniques which have already proven their merits are used in several places. From the very beginning, the intention has been to develop an efficient and usable system. This is expressed more explicitly by the following goals: a) utmost generality in the source language, b) high concentration of useful information in memory, while preserving a form suitable for efficiency in computation, c) economy in the use of memory space and time in order to achieve a maximum domain of practically solvable problems. Though not complete at present, the project has proceeded to a stage where a large set of problems can be solved. From the many problems solved, valuable experience has been gained which may serve as a basis for further improvements while additional elements are being incorporated into the Algebraic Processor. The Algebraic Processor may be divided into three parts which roughly correspond to the three points mentioned above as goals: a) the source language, b) the list structure, c) the logic of simplification. In the first section, some of the special problems inherent in symbolic manipulations with formulae are outlined and the various parts of the Algebraic Processor are briefly described. The two following sections deal with the highly problem-oriented list structure and with some features of the source language and the last section is devoted to the problem of simplification Extract: THE SOURCE LANGUAGE SYMBAL THE SOURCE LANGUAGE SYMBAL ALGOL 60 [1] has been used as a basis for SYMBAL. Many proposals for generalizations have been examined for a possible adoption. In particular, several of the ideas of Wirth which are implemented in his EULER Language [2] offer advantages for our applications and have consequently been used. This section is too short to serve as a full description of the language. It assumes familiarity of ALGOL 60 and deals with some of the additional features offered in SYMBAL. The major features which make it suitable for algebraic problems are the following: a) Numbers appear simply as a trivial case of algebraic expressions. b) Computations with numbers are exact (no round-off) unless some finite precision is specified. c) Variables and functions may be used before a value is assigned to them. Assignments may later occur in terms of other (unknown) quantities. d) Substitution, differentiation and integration are embedded as operators into the language. e) Arrays are implemented in a general form which makes them suitable for list processing. f) The control of the form of expressions occurs through values assigned to standard variables. In numeric computations no variable may occur in an expression before a numeric value has been assigned to it. In SYMBAL, the value of a variable is the expression last assigned to it in the dynamic sense or, if no assignment has been made since its declaration, the variable itself. Since the use of numbers is essential in expressions it is only natural to avoid any distinction between numbers and more general expressions. The reason for exact numerical computations is two-fold. First, lengthy computations may have small integer numbers or simple fractions as their result, and it may then be important to know that these are exact and not accidental. Second, in many cases the user has little knowledge about the path numbers take in the computation and therefore he may not know how many of the digits of a result computed with fixed precision floating point arithmetic are still correct. It might be none. In the Algebraic Processor all numbers are represented as exact integers or rationals. The precision of any computations or results is automatically adapted to whatever multiplicity may be required, availability of memory space being the only restriction. Extract: SIMPLIFICATION SIMPLIFICATION The application of the elementary operations +, -, x, /, T on two expressions is trivial, since it merely requires the concatenation of the two formulae strings with the operation symbol. Even symbolic differentiation, which has always been an attractive operation, requires the application of less than a dozen simple rules. Admittedly, some way to deal with the re-cursivity inherent in parenthetical expressions is required. This is done either by prior conversion to postfix notation, through list processing methods (which include recursive routines) or by some combination of the two. Any formula string produced, as the instructions contained in the source program are executed, must pass through the process of simplification before it may eventually be stored. As indicated above, most of the operations will concatenate existing expressions and therefore produce new expressions of ever increasing length. It is the task of the simplifier to do everything to avoid this explosion of the expressions. The following list mentions the most important cases in which the simplifier will take action: In powers: 1. Change the sign of a negative exponent by reciprocating the entire power. 2. Handle all cases where the exponent is 0 or 1. 3. If the exponent is a positive integer and the base is negative eliminate the minus sign of the base and give the expression the proper sign. 4. Handle all cases where the base is 0 or 1. In terms: 5. Multiply numerical factors. 6. Drop terms which contain a factor zero. 7. Combine factors or powers using the same variable: a xa -» a T 2, a/a- 1, axaT6-aTc where c= 6+1, at 61 xaT 62-ate where c = 61 + 62. 8. Combine powers with the same exponent. 9. Add terms which are identical except for their numerical factor. Unnecessary parenthesis are removed in the following cases: 10. When the base of a power is itself a power: (a T 61) T 62 - ate where c = 61 x 62. 11. When a factor in a term is itself a product but not a sum: x (product) x -> xproduct x . 12. When a term contains a single factor which is a subexpression between parenthesis: + (expression) + -> + expression + . Removal of parenthesis involves substituting the subexpression in place of its link. In all of the above cases the different combinations of signs and operators (+ or -, x or /) must be distinguished and each handled correctly. In two places (7 and 10) the separation of a power of -1 may be required prior to the actual operation. The simplifier establishes a canonical form for any subexpression encountered. In fact, exhaustive simplification in complicated expressions is not possible otherwise, since only a canonical form can guarantee that larger portions of an expression will reappear in the same form and may then be collapsed. A second set of operations contains those which establish a specific form of the subexpression as requested by the user: 13. Distributive multiplication for the removal of parenthesis. 14. Application of the multinomial law on powers of expressions. 15. Computation of a common denominator. 16. Removal of identical factors in all the terms of an expression. 17. Elimination of powers of numbers. 18. Truncation of power series. 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 Morrell, A. J. H. (Ed.): Information Processing 68, Proceedings of IFIP Congress 1968, Edinburgh, UK, 5-10 August 1968 view details in Morrell, A. J. H. (Ed.): Information Processing 68, Proceedings of IFIP Congress 1968, Edinburgh, UK, 5-10 August 1968 view details 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 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 Advances in Information Systems Science, Vol. 1 Tou, J T (ed) Plenum Press, New York, 1969 view details The manual is very easy to read. The introduction is followed by a detailed discussion of the syntax, and one must refer to the problems at the back for tutorial information. A section on the techniques of implementation would have been useful. in ACM Computing Reviews 10(11) November 1969 view details in ACM Computing Reviews 10(11) November 1969 view details Engeli (1968a)--describes SYMBAL, a formula manipulation language; Engeli (1968b)--this paper outlines a future system for formula manipulation, and also discusses current systems. Engeli (1969)--discusses formula manipulation from the user's point of view (includes a bibliography); in [ACM] ACM Computing Surveys 2(4) Dec1970 view details in [ACM] Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, March 23-25, 1971 Los Angeles (SYMSAM 71) view details in ACM Computing Reviews 15(04) April 1974 view details The exact number of all the programming languages still in use, and those which are no longer used, is unknown. Zemanek calls the abundance of programming languages and their many dialects a "language Babel". When a new programming language is developed, only its name is known at first and it takes a while before publications about it appear. For some languages, the only relevant literature stays inside the individual companies; some are reported on in papers and magazines; and only a few, such as ALGOL, BASIC, COBOL, FORTRAN, and PL/1, become known to a wider public through various text- and handbooks. The situation surrounding the application of these languages in many computer centers is a similar one. There are differing opinions on the concept "programming languages". What is called a programming language by some may be termed a program, a processor, or a generator by others. Since there are no sharp borderlines in the field of programming languages, works were considered here which deal with machine languages, assemblers, autocoders, syntax and compilers, processors and generators, as well as with general higher programming languages. The bibliography contains some 2,700 titles of books, magazines and essays for around 300 programming languages. However, as shown by the "Overview of Existing Programming Languages", there are more than 300 such languages. The "Overview" lists a total of 676 programming languages, but this is certainly incomplete. One author ' has already announced the "next 700 programming languages"; it is to be hoped the many users may be spared such a great variety for reasons of compatibility. The graphic representations (illustrations 1 & 2) show the development and proportion of the most widely-used programming languages, as measured by the number of publications listed here and by the number of computer manufacturers and software firms who have implemented the language in question. The illustrations show FORTRAN to be in the lead at the present time. PL/1 is advancing rapidly, although PL/1 compilers are not yet seen very often outside of IBM. Some experts believe PL/1 will replace even the widely-used languages such as FORTRAN, COBOL, and ALGOL.4) If this does occur, it will surely take some time - as shown by the chronological diagram (illustration 2) . It would be desirable from the user's point of view to reduce this language confusion down to the most advantageous languages. Those languages still maintained should incorporate the special facets and advantages of the otherwise superfluous languages. Obviously such demands are not in the interests of computer production firms, especially when one considers that a FORTRAN program can be executed on nearly all third-generation computers. The titles in this bibliography are organized alphabetically according to programming language, and within a language chronologically and again alphabetically within a given year. Preceding the first programming language in the alphabet, literature is listed on several languages, as are general papers on programming languages and on the theory of formal languages (AAA). As far as possible, the most of titles are based on autopsy. However, the bibliographical description of sone titles will not satisfy bibliography-documentation demands, since they are based on inaccurate information in various sources. Translation titles whose original titles could not be found through bibliographical research were not included. ' In view of the fact that nany libraries do not have the quoted papers, all magazine essays should have been listed with the volume, the year, issue number and the complete number of pages (e.g. pp. 721-783), so that interlibrary loans could take place with fast reader service. Unfortunately, these data were not always found. It is hoped that this bibliography will help the electronic data processing expert, and those who wish to select the appropriate programming language from the many available, to find a way through the language Babel. We wish to offer special thanks to Mr. Klaus G. Saur and the staff of Verlag Dokumentation for their publishing work. Graz / Austria, May, 1973 in ACM Computing Reviews 15(04) April 1974 view details SYMBAL Restricted to polynomials, rational functions, and truncated power series, this system is distinguished primarily by its elegant Algol-like syntax. Engeli provides many extremely concise programming examples. Extract: FORMAC 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: 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 History DYSTAL began as an effort in 1963 to write a list-processing language in FORTRAN, using IPL-V as a model. In this regard it followed SLIP (Weizenbaum), which had just been released. DYSTAL differed from SLIP in that in place of the chained word list, used by both IPL-V and SLIP, it substitued linear arrays. It was the writer's belief that the linear array, in which words were implicitly rather than explicitly connected,.was the more natural and efficient arrangement of words and more compatible with FORTRAN operations. Use of links prevented the convenience of using address modification to access words of an array and to employ a basic data structure—the matrix. The initial effort on DYSTAL began with a primitive storage allocation system, and list and tree structure operations were worked out. To these were added string handling operations from SNOBOL and COMIT, matrix and statistical operations and sorting and ranking routines to provide general purpose programming capabilities. The first system was implemented on the IBM 7070 and the DYSTAL MANUAL was put out in 1964 (Sakoda, 1964). In 1967 DYSTAL was presented at the IFIP Working Conference on Symbol Manipulation Languages at Pisa (Sakoda, 1968). After the conference work was begun on making arrays relocatable by accessing them indirectly through a directory, using an approach adopted by Engeli (1968) in writing SYMBAL, a formula manipulation language. This step led to expandable arrays and virtual memory or two-level store using a disk file as secondary storage. The most recent work on DYSTAL 2 has been carried out in Basic FORTRAN for the IBM 1130, permitting it to operate on a relatively small system. For the IBM 1130 a half-word integer version of the storage allocator was written, to increase the amount of usable space. This was used to write various versions of XTAB9, a statistical package with crosstabulation and data modification as the main statistical procedures. XTAB9 was implemented on the IBM 360/67 system and modified to handle hierarchically structured files (Sakoda, 1976). Otherwise, the DYSTAL system has been in relative disuse. A few years ago one might have anticipated FORTRAN simply to disappear because of the development of many sophisticated specialized languages and the appearance of PL/I, a complex general purpose language. But PL/I's complexity has been self-defeating, and the announcement of FORTRAN 77 appears to have revived interest in FORTRAN as a language with a future. DYSTAL may now be of interest to FORTRAN programmers, who feel the need for its dynamic storage allocation and data structuring capabilities, and do not want to wait for the development of FORTRAN 82 or change to a language like PL/I. For those working on revisions of FORTRAN 77, DYSTAL may serve as a prototype for some of the enhancements. in SIGPLAN Notices 14(01) January 1979 view details |