DYSTAL(ID:401/dys002)Array-based list-processing for Fortranfor DYnamic STorage ALlocation. Adds lists, strings, sorting, statistics and matrix operations to FORTRAN. Sakoda, Sociology Computer Laboratory, Brown University, 1965 A system of subroutines added to FORTRAN to do a limited type of list processing. (Sammett 1966) Structures: Related languages
References: Undoubtedly, DYSTAL' S primary advantage lies in its FORTRAN compatibility. There are large numbers of computer users who unfortunately have available to them only the FORTRAN language and who do not have COMIT, IPL-V, LISP, SNOBOL, or other list processing languages. It should now be possible for these persons to do list processing without having to resort to writing in FAP, UMAP, or other machine oriented languages. The second advantage which DYSTAL possesses is one which it shares with Joseph Weizenbaum's (Project MIT MAC) SLIP. Since both SLIP and DYSTAL compile in FORTRAN, they seek to end the separation of fixed dimension matrix oriented languages (FORTRAN, MAD, ALGOL, etc.) and the variable list processing languages, mentioned above. However, this synthesis, commendable as it is, has not been brought about without paying a price. The disadvantage of such a synthesis seems to be the possible loss of core space. Since the author gives no data concerning core storage requirements, it is impossible to judge how serious the loss of core space might be. Another disadvantage is that DYSTAL is not compatible with MAD, ALGOL or FORTRAN IV; but in time this disadvantage will probably be overcome. It might be noted that SLIP is compatible with MAD. The author's statement that "there appeared to be little need for developing recursive routines that call on themselves" seems subject to challenge. One example to the contrary is SNOBOL 3, which does provide for recursive functions. The distinctive feature in DYSTAL is that it achieves dynamic storage allocation while storing the contents of lists in consecutive core locations. In other words, it does not employ pointers, as is usually the practice in list processing languages. The author states that it is therefore possible to locate an item by calculating an address in DYSTAL (Item (i, LISTA) will return the ith item in LISTA). Although this direct feature is very helpful, its utility in a list processing language is rather limited without the addition of an indirect feature. The demonstration program at the end of the article illustrates the point in question. The sample program deletes duplicates by searching the entire list for each word until that word is found. Non-duplicate words finish the normal loop in a search through the entire list and are stored in the output list. With the addition of an indirect feature, such as that contained in SNOBOL, it is possible to search for any particular word without attempting to search the entire list. Each word which is to be compared for duplicates may be stored as a literal in the contents of a string named according to that word. Thus, "dog" is placed into the contents of a string named "dog". If the word "dog" is encountered again, it is stored again in the same string location. After all the words have been indirectly addressed, it is then possible to begin testing each word in the list for a match between the corresponding string name, which contains the word, and the word being compared now taken from a duplicate of the original list. If the match is a success, the corresponding indirectly addressed string is voided and the word is added to the output list, but if the match is a failure, the next word is checked until the list is void. Thus, the indirect feature would shorten the search normally necessary for deleting duplicates. DYSTAL represents a significant and important effort to give FORTRAN users list processing ability as well as to combine list capability with the advantages of a fixed dimension language. Although it is recognized that a price must be paid for these advantages, the sacrifice of pointers makes data insertion and deletion expensive by involving the movement of large masses of data. Furthermore, indirect facilities are not provided. Yet, the advantages of DYSTAL certainly outweigh its disadvantages. in ACM Computing Reviews 6(05) September-October 1965 view details One central problem is the reconciliation of the fixed-dimension matrix oriented languages with the variable list processing languages. As the author points out, there is now available a middle ground, which allows the use of both types of approaches within the same program. This can be done either by the use of SLIP or DYSTAL which are added to FORTRAN programs; or it can be achieved by the approach used at Carnegie Tech, which refers all variables to a common set of tables enabling the programmer to change computer languages within the same program. Another problem presents itself merely from the sheer mass of data which must be processed in single programs. One approach is Hornseth's semi-automatic tabulation generator for large population files. Work still needs to be done in this area to eliminate unnecessary editing problems, as well as unnecessary program modifications to handle specific problems which are sufficiently similar to be incorporated into one generalized tabulation program. Also, social scientists need more efficient methods for machine and tape storage of vast masses of data. The storage of the 1-1000 sample for the 1960 Census on tape is inadequate. The inability of most languages now in use to give social scientists the necessary control over individual bits in computers, other than by writing subroutines in machine oriented languages, is presently a serious obstacle which the new generation computer languages will overcome. Such control over individual bits is crucial in achieving maximum storage in large scale simulations. The final problem deals with ease of programming and efficiency of production. The author feels that SLIP and DYSTAL are unwieldy and clumsy to program since they are based on their host language, FORTRAN. He writes, "In my opinion, FORTRAN has long been a hopeless case of Mickey Mouse details and limitations too unyielding to be tucked in the mind of an active scholar." The basic simplicity of the rules governing the programming of SNOBOL should serve as an example for other languages, but the difficulty with SNOBOL is that it is a list processing language with only integer arithmetic capability. A serious problem with the two approaches, under consideration in the present discussion, is that neither study states anything to give even a small clue as to their efficiency. What are the storage requirements for their programs and data? What is their efficiency as a unit of time? How do they compare in capability and efficiency with similar efforts? Since neither list processing nor tabulation generation is new, it seems a serious omission that neither author documents in any detail the previous efforts dealing with his subject matter, or makes any attempt to discuss the production efficiency of his efforts, or to compare their efficiency with previous efforts. Such basic data as is lacking in these studies is essential for planning computer techniques for programming large scale social systems. in ACM Computing Reviews 6(05) September-October 1965 view details in ACM Computing Reviews 6(05) September-October 1965 view details in Beshers, James M. , Ed. "Proc. Conf. Computer Methods in the Analysis of Large-Scale Social Systems" 1965 view details in Sakoda, James M. "A general computer language for the social sciences" view details Extract: Survey One of the important questions facing programmers working in fields such as symbolic algebraic manipulation or simulation is the direction in which programming languages are to develop. At the present time. FORTRAN and ALGOL, both algebraic languages, serve as the most commonly abed programming languages. For the specialists there have emerged many special languages such as COBOL for commercial use, COMIT and SNOBOL for string operations, IPL-V and LISP for list-processing. The disadvantage of special purpose languages is their restrictive nature. While they are capable of providing special facilities, such as list-processing or string-manipulation, they lack others, such as arithmetic calculations. A single general purpose language which is capable of providing within its framework most of the special-purpose capabilities of special languages certainly would be of great convenience to programmers. This is especially true of those working with the types of problems which require a wide range of capabilities, such as those dealing with symbolic algebraic manipulation or simulation. To achieve a general purpose language it is possible to undertake the writing of a new language or to extend an existing one. PL 1 comes closest to the notion of writing a new general purpose programming language. Actually, it tends to be more of a hasty pooling of features of FORTRAN, ALGOL and COBOL, with additions of string manipulation and list-processing operations. It lacks the neatness of a single well-integrated language, and demonstrates that more study needs to go into desirable features of a new general purpose programming language. A new language, moreover, while free from restrictions of existing languages, has the serious disadvantage of lack of continuity with existing ones. The alternative to a new programming language is the extension of an existing one. This provides a more gradual development of languages and is less traumatic to the user. The syntax of the existing language tends to restrict the extent to which a language can be extended comfortably, but this avenue needs to be explored, especially because it appears to be easier than the construction of a new language. Efforts to extend an existing language can be classified as horizontal or vertical extensions. Horizontal extensions are illustrated by FORMULA ALGOL and FORMAC. In horizontal extensions compilers are rewritten to provide additional instructional capabilities. In FORMULA ALGOL and FORMAC algebraic languages are extended and given symbolic manipulation capabilities. New data types as well as additional instructions can be incorporated in the expanded language, but this requires correspondingly greater effort. In particular, the rewriting of the compiler for each machine is a costly process. By vertical extension is meant embedding [1] - i.e. using an existing language to write another one. This provides additional capabilities, while at the same time retaining those of the host language. The advantage of embedding is the ease of implementation of the new language, which does not require a compiler of its own. Examples of embedding are SLIP [5] and DYSTAL [4], both written in FORTRAN, and FLIP, which is written in LISP. The disadvantage of embedding is that one is almost completely restricted by the limitations of the host language, and the question can be raised as to whether or not this is a fatal weakness. ALGOL and FORTRAN are logical choices as host languages for embedding a general-purpose programming language since they are currently widely used, one in Europe and the other in the United States. ALGOL has two weaknesses as a host language: its procedures generally cannot be compiled separately. Since the expansion of an algebraic language is largely through the addition of suitable subprograms, this shortcoming is a serious one. Another is its lack of a general input-output system. FORTRAN has neither of these shortcomings, and hence has better potentiality for embedding special languages. FORTRAN, however, lacks dynamic storage allocation and list-processing capabilities, and one of the basic tasks of writing a general-purpose programming language is to provide these two within the limitations of the language. Fortunately, this can be accomplished, and has been done differently by SLIP and DYSTAL. Extract: Dialogue on DYSTAL between Sakoda and Bobrow Bobrow In line with your philosophy that embedding is a very useful technique, and one should add to languages already in existence, why did you design a new language instead of taking an already embedded language in FORTRAN, namely SLIP, and adding just those features which you felt were important for doing the kinds of things you wanted to do? In what way also is your language better than SLIP for doing certain operations? Sakoda I think the primary difference between SLIP and DYSTAL is the way in which the dynamic storage is managed. SLIP, I believe, takes all of the available dynamic storage area, and devotes it to link word pairs of words and you must work within this framework in SLIP. If you want arrays, I think the arrays are created as FORTRAN variables. Perhaps there may be one word said in favor of using DYSTAL to embed SLIP. To turn your question around, and that is, in DYSTAL you can create a matrix and then take that MATRIX and work up the SLIP available word store. This can be dynamic. In other words, if you want a large area of the list. type of word, then you can have a large area. If you only want a small area, you can have a small area. I think this would make for a combination of SLIP and DYSTAL in which the distribution of the two becomes more dynamic. Bobrow Since SLIP was a pre-existing language which was fairly well documented, I don't understand why, if you felt you wanted another kind of storage allocation, that you did not just add the one new storage allocation feature that you are talking about, instead of going to a brand new language and proliferating this Leaning Tower of Babel. Sakoda When I started DYSTAL, SLIP had just come out, and I got some of my ideas from SLIP. I felt that SLIP's chief defect was that it used a linked word list; that this caused a slowness of operation. It seemed more natural to me in FORTRAN to use sequential arrays. I took the basic principle that SLIP was basically wrong in the approach that it used in storage allocation. Now I am coming back to the point where I feel that both capabilities perhaps should be made available to users and perhaps SLIP and DYSTAL might be combined in a single language. Bobrow Have you made comparisons on any problems between running speeds of SLIP and DYSTAL programs to give some indication of whether your original assumption was correct or not? Sakoda No. My assumption is wholly theoretical. 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 The author frankly attempts to achieve for DYSTAL the "status of a universal programming language." It is a well documented, easily read proposition for the extension of FORTRAN or ALGOL. With the use of a few CALL statements to include preceded subroutines, the use of an existing language appears to be "less traumatic to the user" than developing a completely new one. The ability of DYSTAL to become an efficient universal language is entirely plausible. in ACM Computing Reviews 9(09) September 1968 view details in ACM Computing Reviews 9(09) September 1968 view details [321 programming languages with indication of the computer manufacturers, on whose machinery the appropriate languages are used to know. Register of the 74 computer companies; Sequence of the programming languages after the number of manufacturing firms, on whose plants the language is implemented; Sequence of the manufacturing firms after the number of used programming languages.] in ACM Computing Reviews 9(09) September 1968 view details in Computers & Automation 21(6B), 30 Aug 1972 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 Computers & Automation 21(6B), 30 Aug 1972 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 in SIGPLAN Notices 14(01) January 1979 view details I was in the Psychology Department of the University of Connecticut when IBM set up a computation center at MIT for use by New England colleges and universities. I attended the first summer institute offered at MIT in 1956, I believe, and struggled through the assembly- language programming course. At the end of the session, a young man -- I believe Sheldon Best -- got up and announced that IBM was working on an automatic programming system called FORTRAN. The following year when FORTRAN was made available, I attended a short course on it in Boston. As a research associate to the MIT Computation Center, I began to work on statistical programs in FORTRAN; since then it has been the only language in which I have programmed. I think this is the experience of many social scientists and others. My encounter with non-numerical programming came in 1963 when I attended a summer institute on the use of IPL V for simulation at the Rand Corporation. The session was organized by Bert Green. I found that IPL v provided dynamic storage allocation using linked-word lists. It provided list-processing operations such as insertion and deletion, list structures, complex structures, and procedures for handling them that would not normally be performed in FORTRAN. On the other hand, data handling was almost nonexistent, input/output was difficult, and even a simple device like a checkerboard could not be easily represented by linked-word lists. Moves on a checkerboard were generally done by creating lists of possible lists. Furthermore, programs written in IPL V were reputed to be slow, and I attributed this to linked-word lists, which required sequential access instead of direct access to the middle of list. Before the institute was over, I decided to write a list-processing language using FORTRAN subroutines and functions. I was not aware of Herbert L. Gelernter's FLPL, which was written in FORTRAN; Joseph Weizenbaum's SLIP had just been announced, but to me it appeared to be IPL V operations written as a series of FORTRAN subprograms with a few parameters written in machine language. I decided that in order to preserve many of FORTRAN S essential features, lists should consist not of linked words but of a linear string of words. My task was to find ways to provide dynamic storage allocation at run time, list-processing operations, and creation and operation of arrays connected into tree structures. I was able to provide all of these using procedures written as FORTRAN functions. I then proceeded to add string-processing routines, sorting operations, and statistical and matrix operations, aiming for a general-purpose language. The first DYSTAL manual was completed in 1965. After the 1967 IFIP Working Conference on Symbol Manipulation Languages, I decided to make arrays relocatable using a directory to hold the names of arrays and to allow arrays to move to a disk file as room in memory was depleted. A manual incorporating this improvement was put together at Brown in 1970. My approach was that of an amateur unaware of the niceties of computer-language design, doing what appeared necessary to achieve features that FORTRAN did not normally provide. Much of this would not even be of historical significance since DYSTALIS not widely used, but some of it is pertinent to the present effort to provide a more general-purpose language via FORTRAN. The X3J3 FORTRAN committee is discussing setting up a core FORTRAN and extensions into different application areas. I believe that the core should be relatively flexible to allow a variety of extensions. I would like to point out how I was able to make use of basic FORTRAN and FORTRAN IV to accomplish unFORTRAN-like operations while integrating numeric and nonnumeric procedures. Three features were important to my effort to provide list-processing and list-structuring operations in FORTRAN. The first was dynamic storage allocation. The second was the name of an array that was separate from its content. In FORTRAN a variable, whether subscripted or not, refers to its content or value. To create tree structures or to chain arrays, it was necessary to be able to use names of arrays as pointers. This called for a new data type -- array name -- that was different from integers and real variables. The third feature was required to provide the flexibility inherent in linked-word lists. I found this in the five-word head, which I later increased to seven, that I attached to each array. These features were not independent of one another. I began with dynamic storage allocation, which brought into play the need to keep track of the location of an array and its features. Dynamic storage allocation also provided the opportunity to attach a set of information to each created array. To implement dynamic storage allocation of linear arrays, a single storage area was created. From it all arrays were allocated at run time. To accomplish this, three variables -- LOT, an integer variable; FLOT, a real variable; and GLOT, an extra -- were dimensioned the maximum amount and made equivalent to one another and stored in common. Later a disk file was added when arrays were made relocatable. The equivalencing of the three arrays made it possible to cut out any type of array from the same storage area and even to store different types of variables in the same array. The EQUIVALENCE statement therefore played a central role in providing a flexible dynamic storage-allocation system. The use of COMMON allowed each function to have access to an entire dynamic storage area without the need to enter LOT and FLOT as arguments each time. GLOT was placed in common to fool the compiler into believing that LOT and FLOT were not being modified by the FORTRAN function. This rigid requirement was encountered in basic FORTRAN when working with the IBM 1130 compiler, which said that functions cannot change values in COMMON. I would deem this to be overprotection of the user, who would be better served by the ability to change values in COMMON if desired. As for array names, it was dynamic storage allocation that permitted and also required a name separate from the content of the array. The location where the array was stored in COMMON was returned as an integer value that became the name of the array. In the head of the array, I put in a counter that kept track of the number of words stored on the array, the capacity of the array, the mode of the array, and other pieces of information that were necessary. This made it possible to have a great deal of automatic programming like the instruction CALL IDUMP (LSTA), where LSTA is the name of the array. This will print out in the appropriate format any array in dynamic storage. The head attached to each array was very useful. Using these three features, I was able to provide other unFORTRAN-like features that included, for example, recursion, virtual memory, and string processing, although I was handicapped by not having the character data type. The last improvement I made was to be able to save the entire dynamic storage area and to recall it later with another program. In conclusion, DYSTAL used linear arrays in place of linked words and was therefore better able to take advantage of FORTRAN S efficient processing features. It is desirable to keep the basic FORTRAN that is being planned as flexible as possible; I think this includes, if possible, keeping EQUIVALENCE and COMMON, which they are talking about doing away with. in Annals of the History of Computing, 6(1), January 1984 view details |