Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.
Appendix 18 Relation Between Programming Languages and Linguistics EFFECT OF LINGUISTICS ON PROGRAMMING This effect varies from period to period of programming history (which is very short) . In pre-Fortran times the effect was al- most nil since all programming was in machine language and almost all computation was scientific. I n the period from Fortran to ALGOL (1956-1960) the connection was almost totally terminological: words and definitions, but not theory and technique, were borrowed from linguistics, for ex- ample, grammar and syntax. The real link was between program- ming and mathematical logic, as witness the development of ADES languages based on recursive functions and the development of several Polish prefix-oriented languages. Syntax analysis during this period was a collection of ad hoc techniques. Thus the paper by Sheridan on Fortran~ is enormously complex. Descriptions of even more complex grammars are much more clearly understand- able today. The period from ALGOL to the present shows intense borrowing of current mathematical linguistic theory, technique, and notation. The source of this dependency can be traced to the definition of ALGOL 60 syntax production notation. The similarity between this notation and the rewriting rules of some linguistic models caused this theory to be rapidly employed in programming. Still, it is important to note that the definition of the ALGOL language was totally inspired by programming considerations (Fortran, LISP), and not linguistic ones. The effect of this syntax formalism has been enormous and all to the good. Thus ALGOL syntax is "essentially" of Type 2. Hence, parsing mechanisms for Type 2 languages can be applied in the construction of ALGOL translators. Many of the parsing techniques employed were, however, discovered by programmers operating in parallel to, but independent of, similar developments in mathe- matical linguistics. 118
The existence of a theory has made it possible to define vari- ations on a given grammar that permit the same task specifica- tion but in a grammar more efficiently parsed (one push-down stack instead of many, no retracing of paths in a tree of syntax choices), for example, precedence grammars. Certainly it is now the case that the design of programming languages follows a more rational procedure than before because of mathematical linguistics, and proceeds in the following steps: A. A set of tasks is isolated and their informal algorithmic descriptions are specified. B. The data structures inherent in this class of problems are isolated and appropriate computer representations are defined. The natural operators on the data are isolated. C. D. A grammar of increasingly complex units is specified, e.g., atoms, expressions, statements, and programs. E. A parser-recognizer is constructed for the grammar. F. The steps D and E are iterated until a reasonable mixture of flexibility and efficiency is attained. G. A semiformal statement of the evaluation of algorithms described in this language is given, which becomes the basis for a translation process taking this language into some other given language (usually machine code). It is now possible to teach syntax analysis of programming languages, i.e., the basic knowledge is now available in an organized form. It is now possible to construct programs that are general- purpose syntax analysers in the sense that they parse any program- ming language of a given type. EFFECT OF PROGRAMMING ON LINGUISTICS Since programming is an "applied"' activity and linguistics a more abstract one, programming has provided linguistics with "real" models that are sufficiently complicated to permit the development of diverse theories. Programming has also led to the definition of linguistic models possessing a theory of their owns and specifically tailored for use as programming languages.4 The existence of a body of technique in programming has made it possible to develop special programming languages for solving certain linguistic problems, e.g., SNOBOL5 and COMITY. Similarly, programming, being concerned with a growing set of demands, provides a pressure on linguistic theory directing it toward problems particularly relevant to computation, e.g., prob- lems of efficiency of representation and speed of computation. 1:19
FUTURE RELATIONSHIP BETWEEN PROGRAMMING AND LINGUISTICS programming there will be concentration on developing theories of evaluation, i.e., what is meant by the execution of a program written in language ~ ? We may call this the sematics of it. Such studies will replace the present ad hoc development of compiler- compilers with a theory of their properties and more insight into the design of computing machines. This is the translation problem for computer languages. These languages will become sufficiently complex so that a theory of their semantics or evaluation will be a sufficiently interesting model for the equivalent problems arising in natural language translation. Similarly, there will be a reverse flow from the development of semantic theories within natural linguistics into mathematical linguistic models, which, in turn, will influence programming. REFERENCES 1. E. K. Blum, "Automatic Digital Encoding System, " NAVORD Rep. 4411 (1956). 2. P. B. Sheridan, "The Arithmetic Translator-Compiler of the IBM Fortran Automatic Coding System," Commun. Assoc. Computing Mach. _, 9 (1959). 3. S. Ginsburg and R. H. Gordon, "Two Families of Languages Related to ALGOL," J. Assoc. Computing Mach. 9, 350 (1962~. R. W. Floyd, "Syntactic Analysis and Operator Precedence," J. Assoc. Computing Mach. 10, 316 (1964). 5. D. J. Farber, R. E. Griswold, and I. P. Polonsky, 'iSNOBOL, A String Manipulation Language," J. Assoc. Computing Mach. 11, 21 (1964). 6. The Research Laboratory of Electronics and the Computation Center, COMIT Programmers Reference Manual, 2nd ea., The M.I.T. Press, Cambridge, Mass. (1962). 4. Bl BLIOGRAPHY 1. R. W. Floyd, IEEE Trans. Electron. Computers 13, 346 (1964). This bibliography includes subjects related to the syntax of programming languages insofar as they illuminate the problems of analysis and synthesis of formally defined programming languages. 120