AXLE(ID:218/axl001)Table-based string processing languagefor AXiomatic LanguagE String processing language. Cohen and Wegstein, National Bureau of Standards, Washington, D.C., 1964 Program consists of an assertion table which specifies patterns, and an imperative table which specifies replacements. Structures: Related languages
References: AXLE imperatives can deal with any data which is readily expressed by a linear string of characters. A wide range of information can be expressed in these terms including some of the special notations of pure mathematics, logic, linguistics, chemistry and electrical engineering. An area for further investigation is the manipulation of abstract information contained in diagrams. Transferred to linear form, this information might be treated in the workspace by AXLE imperatives and assertions which themselves may be transformations of information produced by a light pen. A possible extension to the AXLE language will permit the computer to make inferences during run time. For this purpose a facility is needed for permitting the computer itself to change imperative and assertion tables as a result of earlier operations on the workspace. Abstract: AXLE is a language designed for data manipulation. Data arranged in a linear form in a workspace is transformed according to a table of axioms, called imperatives. A transformation consists of a matching procedure, which decides where an imperative is applicable, and a replacement procedure that modifies that part of the workspace. Imperatives are applied in accordance with definitions of symbolic terms, presented systematically in an assertion table. The process of definition includes the special case of recursive assertions. Several complete programs of imperatives are given to show a few applications of the language. Extract: Introduction Introduction AXLE is a string transformation language, This paper presents a description of the language and several example programs, designed to show both the characteristics of the language and some of its possible uses. An AXLE program transforms a data-string in a workspace, nil approach to symbol manipulation already used by COMIT and SNOBOL. A transformation is done by the application of a sequence of roles called imperatives. This sequence of roles may be regarded as a table of axioms. The application of these imperatives to specifle data is facilitated by definitions of symbolic terms, called nonliteral characters, for use in the imperatives. Use of these nonliteral characters enables an imperative to act with great generality, manipulating any data of a given type or pattern, rather than just specific data. The definitions of nonliteral characters are systematically presented in an assertion table, which accompanies each program of imperatives. The action of the imperatives is similar to Robert W. Floyd's productions for symbol manipulation, but the assertion table, permitting the these of symbolic terms, including those defined recursively, adds much versatility. A detailed description of the language and four example programs follow; explanatory comments are included with these programs. The variety of material chosen for the program indicates the scope of a symbol manipulation language of this kind. Extract: The Language The Language Each AXLE program consists of an imperative table and art assertion table. The imperative table modifies the contents of the workspace, a finite string of arbitrary characters. The workspace is of undefined and variable length. The assertion table provides definitions of any nonliteral characters used in the imperative table. A. The Assertion Table. The assertion table is a set of assertion lines which define nonliteral characters. The definitions may be in terms of literals (characters which represent only themselves) or in terms of other nonlitcrMs which are themselves defined in the assertion table. Recursive definitions are permitted. The definitions of a nonliteral give the set of all strings of literals which "match" or satisfy the nonliteral. A nonliteral character in an imperative line mat, ches a section of the workspaee if that string of characters in the workspace is one which, according to the assertion table, satisfies the nonliteral. A literal character matches only itself. B. The Imperative Table. The imperative table is composed of one or more numbered imperative lines, or instructions, each of which (with exceptions explained below) consists of a left side, an equal sign, a right side, and a transfer number. For each line of the imperative table, the workspace is searched from the left until a group of consecutive characters is found that matches the left side of the imperative line. The section of the workspace matched is thus a string of literals that form consecutive substrings that match, in order, the symbols on the left side of the imperative line. in [ACM] CACM 8(11) Nov 1965 view details On AXLE Editor: I would like to make some comments on an article in the November 1965 issue of the Communications of the ACM, viz., "AXLE, an axiomatic language for string transformation", by Kenneth Cohen and J. H. Wegstein. AXLE is introduced in this paper as a new language for string transformation. Its two main concepts are: the assertion table and the imperative table. Maybe it would have been useful to relate these ideas to already existing ones: an assertion table is apparently nothing but a context free grammar and an imperative table is a Markov algorithm. The extension of the latter to include explicit transfer orders is inessential since it has been proved that for each scheme with explicit transfers there exists an equivalent normal algorithm. Moreover, the combination of a context-free grammar and a normal algorithm was introduced by van Wijngaarden [2, 3] in an even more general language which has the possibility of intermixing rules from the assertion table and the imperative table and adding new rules at run time. This language was used in [1] to give a formal description of syntax and semantics of ALGOL 60. REFERENCES : 1. DE BAKKER, J. W. Formal definition of algorithmic languages, with an application to the definition of ALGOL 60. Report. MR 74, Mathematisch Centrum, Amsterdam. 2. WIJNAGAARDEN, A. VAN. Generalized ALGOL. Annual Review in Automatic Programming, 3, Pergamon Press, Ltd. and Macmillan Co., 1964. 3. Recursive definition of syntax and semantics. Prec.IFIP Working Conf. on Formal Language Description Languages, Vienna, 1964. J. W. DE BAKKER Mathematisch Centrum 2e Boerhaavestraat 49 Amsterdam (O), Holland in [ACM] CACM 9(04) April 1966 view details Among the accompanying examples are a quick conversion of an algebraic expression with parentheses to Polish prefix form and a reduction of an integral involving cos x to the equivalent expression containing the integral in terms of COSINE I, as one would find in Peirce's tables. The capabilities and limitations of AXLE appear to be just those of context-free grammars. in ACM Computing Reviews 7(03) May-June 1966 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 general, string processing systems deal with data which is in the form of unstructured strings of characters. COMIT (Yngve, 1962), SNOBOL-3 (Farber, Griswold and Polansky, 1966) and SNOBOL4 (Griswold, Poage and Polansky, 1968) are three well-known string processing languages. Typical of the types of operation possible in these languages are matching, insertion, replacement and concatenation of strings and substrings. With the increasing usage of computers in many different fields, the distinction between numeric and non-numeric applications is becoming less apparent, as for example in information retrieval problems. Consequently it seems desirable that a single programming system should incorporate efficient numeric and non-numeric capabilities. The SP/1 system described here has been designed and implemented as a string processing system embedded in FORTRAN-IV. To avoid adding to the diversity of programming systems already in existence and since SNOBOL is a wellknown language whose syntax is readily adaptable to a FORTRAN environment, the operations provided in SP/I are similar to those available in SNOBOL-3. Unlike, for example DASH (Milner, 1967), which is a string processing extension embedded in ALGOL, SP/1 is both a syntactic and semantic extension to FORTRAN. The string processing statements can be represented by a set of macros which are expanded into FORTRAN statements by a macro generator (Macleod and Pengelly, 1969) prior to compilation. The macros have been designed so that there is a close similarity between the syntax of the corresponding SP/1 and SNOBOL3 statements. For example, the SNOBOL-3 statement REPEAT E "(" *V* ")" = V /S (REPEAT) deletes all the pairs of left and right parentheses from a string E. The corresponding SP/I statement is In addition, SP/1 provides a data type known as an association which may have a range of alternative values associated with it. This data type is in some ways similar to the pattern type in SNOBOL-IV and the assertion type in AXLE (Cohen and Wegstein, 1965). A further distinctive feature of SP/1 is that strings are stored as sequences of atoms where an atom is the smallest meaningful unit of the string. The size of an atom is determined on input as shown below, but normally an atom may be regarded as a single character symbol or as a group of consecutive alphameric characters. The latter could be the case for example in text processing where one atom would be equivalent to a word of text. This approach allows the processor to operate on strings composed of text words while retaining the capability to manipulate strings of individual symbols where required. This provides faster operation with a considerable saving in storage requirements in the text processing types of applications where the smallest logical unit of information is a word of text. Thus, essentially, there are two modes of operation, character and text, corresponding to the two types of storage. In the current version of SP/1 mixed mode operations are not allowable. The method of string storage, which involves a hash table, is described elsewhere (Macleod, 1969a). Extract: Introduction In general, string processing systems deal with data which is in the form of unstructured strings of characters. COMIT (Yngve, 1962), SNOBOL-3 (Farber, Griswold and Polansky, 1966) and SNOBOL4 (Griswold, Poage and Polansky, 1968) are three well-known string processing languages. Typical of the types of operation possible in these languages are matching, insertion, replacement and concatenation of strings and substrings. With the increasing usage of computers in many different fields, the distinction between numeric and non-numeric applications is becoming less apparent, as for example in information retrieval problems. Consequently it seems desirable that a single programming system should incorporate efficient numeric and non-numeric capabilities. The SP/1 system described here has been designed and implemented as a string processing system embedded in FORTRAN-IV. To avoid adding to the diversity of programming systems already in existence and since SNOBOL is a wellknown language whose syntax is readily adaptable to a FORTRAN environment, the operations provided in SP/I are similar to those available in SNOBOL-3. Unlike, for example DASH (Milner, 1967), which is a string processing extension embedded in ALGOL, SP/1 is both a syntactic and semantic extension to FORTRAN. The string processing statements can be represented by a set of macros which are expanded into FORTRAN statements by a macro generator (Macleod and Pengelly, 1969) prior to compilation. The macros have been designed so that there is a close similarity between the syntax of the corresponding SP/1 and SNOBOL3 statements. For example, the SNOBOL-3 statement REPEAT E "(" *V* ")" = V /S (REPEAT) deletes all the pairs of left and right parentheses from a string E. The corresponding SP/I statement is In addition, SP/1 provides a data type known as an association which may have a range of alternative values associated with it. This data type is in some ways similar to the pattern type in SNOBOL-IV and the assertion type in AXLE (Cohen and Wegstein, 1965). A further distinctive feature of SP/1 is that strings are stored as sequences of atoms where an atom is the smallest meaningful unit of the string. The size of an atom is determined on input as shown below, but normally an atom may be regarded as a single character symbol or as a group of consecutive alphameric characters. The latter could be the case for example in text processing where one atom would be equivalent to a word of text. This approach allows the processor to operate on strings composed of text words while retaining the capability to manipulate strings of individual symbols where required. This provides faster operation with a considerable saving in storage requirements in the text processing types of applications where the smallest logical unit of information is a word of text. Thus, essentially, there are two modes of operation, character and text, corresponding to the two types of storage. In the current version of SP/1 mixed mode operations are not allowable. The method of string storage, which involves a hash table, is described elsewhere (Macleod, 1969a). in The Computer Journal 13(3) 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 |