Browse Prior Art Database

Early Days of FORTRAN: Compiler Techniques Available in 1954

IP.com Disclosure Number: IPCOM000129430D
Original Publication Date: 1984-Jan-01
Included in the Prior Art Database: 2005-Oct-06
Document File: 2 page(s) / 17K

Publishing Venue

Software Patent Institute

Related People

ROY NUTT: AUTHOR [+2]

Abstract

When I first heard the title for this talk, I thought it was rather silly. After all, there weren't any compiling techniques in 1954. On reflection, that turned out not to be quite true. To give a little background, the open literature known to the FORTRAN group in 1954 contained no compiling articles. One related article, by John W. Backus, was on the IBM 701 Speedcode system.* [Footnote] * J. W. Backus, ";The IBM 701 Speedcoding System."; J. ACM 1, 1 (January 1954), 4-6. In the closed literature, we knew about the A-2 compiler at Univac, but to my knowledge we had no documentation concerning that system. An influential paper from MIT, by Laning and Zierler,** [Footnote] **J. H. Laning and N. Zierler, ";A Program for Translation of Mathematical Equations for Whirlwind I."; Engineering Memorandum E-364, Cambridge, MIT, January 1954. included an interesting interpretive program that employed an algebraic notation and a convenient method for printing the results of the computation. That paper influenced my thinking very strongly in the months preceding the invitation from Backus to join his group. I think other members of the FORTRAN group were also aware of that particular system.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Copyright ©; 1984 by the American Federation of Information Processing Societies, Inc. Used with permission.

Early Days of FORTRAN: Compiler Techniques Available in 1954

ROY NUTT

(Image Omitted: Author's Address: R. Nutt, Computer Sciences Corporation, 650 North Sepulveda Boulevard, El Segundo, CA 90245.)

When I first heard the title for this talk, I thought it was rather silly. After all, there weren't any compiling techniques in 1954. On reflection, that turned out not to be quite true. To give a little background, the open literature known to the FORTRAN group in 1954 contained no compiling articles. One related article, by John W. Backus, was on the IBM 701 Speedcode system.*1 In the closed literature, we knew about the A-2 compiler at Univac, but to my knowledge we had no documentation concerning that system. An influential paper from MIT, by Laning and Zierler,**2 included an interesting interpretive program that employed an algebraic notation and a convenient method for printing the results of the computation. That paper influenced my thinking very strongly in the months preceding the invitation from Backus to join his group. I think other members of the FORTRAN group were also aware of that particular system.

(Image Omitted: Figure 1. Sheridan's notation.)

(Image Omitted: Figure 2. Sheridan's statement.)

(Image Omitted: Figure 3. An IBM sorter.)

Another bit of background is that FORTRAN was designed for a machine with 4096 36-bit words, two 2048-word drums, and four tapes (75 inches per second, 200 bits to the inch with a 3/4-inch record gap). If you have a personal computer with a 10-megabyte hard disk today, you have a much bigger machine than we did. In the following paper, Frances Allen will tell you quite a bit more about the structure of the FORTRAN compiler, but essentially optimizations were achieved in FORTRAN by a number of devices. With the elimination of common subexpressions and expressions, by restriction of the subscripts used, and register assignment (which Dick Goldberg has just told you something about), it was possible to do an exhaustive analysis of the manipulations necessary in DO-loops.

I want to address two landmark techniques used in the FORTRAN compiler. First, of course, is the parsing of algebraic expressions. John Backus and Irving Ziller had concocted a seemingly dubious scheme for inserting parentheses around some operations, which could then be unscrambled at a later time to parse the algebraic expression. Peter Sheridan, in an impressive paper,*3 proved that this was a viable scheme, although some people didn't particularly care for his notation.

1 * J. W...