ALPAKB(ID:5627/alp004)Generalised version of ALPAKAdvanced, generalised version of ALPAK, based in the OEDIPUS system Places Related languages
References: OEDIPUS Now let us discuss briefly some of the programming problems which were encountered in the implementation of ALPAK. In the first place polynomials and rational functions must be put somewhere inside the computer, and this is clearly the sort of problem that the ALPAK user'should not have to think about. The amount of space required for a particular expression cannot usually be predicted in advance, and space must also be found for intermediate expressions whose existence the user may not even be aware of. This problem is solved by writing a dynamic storage allocator which finds and frees blocks of space on request. The storage allocator must also be able to handle lists and trees, since our data structures--e.g., products of polynomials--are often fairly complicated. A second problem is that many algebraic procedures are recursive. For example, to divide two polynomials in n variables, it is necessary to call a procedure for dividing polynomials in n-1 variables. If n > l, the second procedure is the same as the first, which therefore must be able to call itself. A third problem is that the introduction of complex data structures, dynamic storage allocation, and recurslon has necessitated a new approach to the problem of post mortem analysis. When a run is terminated because of insufficient space or time or because of a programming error, how can we get the computer to tell us in a problem oriented way what it thinks it was trying to do, where it was, and how it got there? Finally there is the ever present problem of book- keeping for subroutines. The facilities for dynamic storage allocation, recurslon, and post mortem analysis impose so many requirements on the writer of a subroutine that he needs the help of a computer to survive. These problems are all more general than ALPAK, and they led us to develop an operating environment called OEDIPUS (Operating E__nvironment with D_ynamlc Storage Allocation, I_nput-Output, Public Pushdown List, U_nhurried Diagnostics, and Symbolic Snaps). This serves as a foundation for ALPAKB, a new version of ALPAK, and can also be used to implement other systems having similar requirements. in [ACM] CACM 9(08) August 1966 view details In March 1958 a Celestial Mechanics Conference was held at Columbia University and the Watson Scientific Computing Laboratory in New York (Davis 1958). One of the topics discussed was the possibility of constructing general-purpose compilers capable of carrying out literal theories in celestial mechanics. Such a compiler, according to Grosch, should be capable of performing the manipulations of complicated algebra as well as differentiation and integration of a limited class of functions. He estimated that 200 man-years of effort would be needed to program a completely literal theory, such as Delaunay's. That the programming language may be of crucial importance in endeavors of this kind is emphasized by the fact that Barton (1966) carried out the literal development of the lunar disturbing function to the sixth order in 2 min, to the eighth order in 7 min, and to the tenth order (two orders of magnitude beyond Delaunay) in 50 min. Barton noted that it took less than 6 h of programming effort to write this program. To complete and extend the work of Delaunay additional programming has to be done for the manipulations of the transformation theory. More about Barton's work later. Three problems were recognized almost ten years ago relative to the development of analytical theories on computers: (1) The generally slow speed of computers (2) Their small storage capacities (3) The nonexistence of algebraic compilers for literal calculations Today the large computers are some 15 times faster than the large computers of 1958 and fast core memories have increased in size by a factor of about 4. Algebraic compilers have come into existence as well as other languages suited to symbol manipulation. While all of these languages have some shortcomings, many are useful enough for celestial mechanicians to adopt as regular "tools of the trade." Actually, the number of languages on various levels of sophistication which may be used for a variety of nonnumerical applications is quite imposing. Table I gives a list of current symbolic manipulation languages (Sammet 1966). These languages may be categorized as follows: (1) List Processing. In this method of programming, information in the computer memory is stored associa-tively, i.e., elements of a data set are not stored consecutively but rather each element contains pointers to its succeeding (also sometimes preceding) element. These pointers are part of the data, and are wholly transparent to the user. This technique is especially useful in building up and manipulating lists of information. Such methods are often needed in building compilers to algebraically manipulate formal expressions. Examples: LISP, IPL V and SLIP. (2) String Manipulation. String manipulation involves operations on a concatenation of characters, including matching, insertion, deletion and replacement of characters. Example: SNOBOL. (3) Symbol Manipulation. Generally the same as (2) above. (4) Formula Manipulation. Generally means operations on algebraic expressions. In addition to the general languages shown here, there are many special-purpose programs designed to do a special job. These may be written in a high-level language, such as FORTRAN or ALGOL or may be in a low-level language. Broadly speaking, high-level languages allow less flexibility to the user but are easier to learn and apply, while low-level languages permit more flexibility but may require a considerable investment of time to acquire knowledge of the assembly language, basic machine instructions and special programming techniques. Extract: Time taken in developing ALPAK, ALTRAN, ALPAKA, ALPAKB ALTRAN has rational number arithmetic, rational functions, dynamic storage allocation and allows recursive procedures. It is of interest to see how much work is involved in building compilers of this type. ALPAK A 6.5 man-years ALPAK B 2.5 ALTRAN 0.5 _________ 9.5 man-years ALPAK B contains many improvements and extensions of version A, such as internal procedures to simplify the simplification process and multiple precision coefficients. The Bell Telephone Laboratories have subcontracted the development of ALPAK C which will be written in PL/I. BTL itself is writing ALTRAN C in PL/I and will consist of a series of calls to ALPAK C. Variables in ALTRAN C will be of five basic function data types: (1) number, (2) array, (3) entry, (4) polynomial, and (5) rational, allowing for a wide range of function domains. in [ACM] CACM 9(08) August 1966 view details |