The history of Fortran I, II, and III

THE

HISTORY

OF FORTRAN

I,

II,

AND

III

John Backus IBM R e s e a r c h L a b o r a t o r y San Jose, C a l i f o r n i a

I.

Early background

1.1 Attitudes in the 1950's.

A f t e r M a y 1954 the A-2 c o m p i l e r a c q u i r e d a " p s e u d o c o d e " w h i c h was s i m i l a r to the order c o d e s for m a n y f l o a t i n g p o i n t i n t e r p r e t ive s y s t e m s t h a t w e r e a l r e a d y in o p e r a t i o n in 1953: e.g., the Los A l a m o s systems, D U A L and S H A C O [Bouricius 1953; S c h l e s i n g e r 1953], the M I T "Summer S e s s i o n C o m p u t e r " [Adams and L a n i n g 1954], a s y s t e m for the I L L I A C des i g n e d by D. J. W h e e l e r [Muller 1954], and the S P E E D C O D I N G s y s t e m for the IBM 701 [Backus 1954].

and e n v i r o n m e n t .

about automatic

programming

B e f o r e 1954 a l m o s t all p r o g r a m m i n g was d o n e in m a c h i n e l a n g u a g e or a s s e m b l y language. Programmers rightly regarded their w o r k as a c o m p l e x , c r e a t i v e art t h a t req u i r e d h u m a n i n v e n t i v e n e s s to p r o d u c e an efficient program. M u c h of their e f f o r t was d e v o t e d to o v e r c o m i n g the d i f f i c u l t i e s c r e a t e d by the c o m p u t e r s of t h a t era: the lack of i n d e x r e g i s t e r s , the lack of b u i l t in f l o a t i n g p o i n t o p e r a t i o n s , r e s t r i c t e d i n s t r u c t i o n sets (which m i g h t h a v e A N D but not OR, for e x a m p l e ) , and p r i m i t i v e i n p u t output arrangements. G i v e n the n a t u r e of c o m p u t e r s , the s e r v i c e s w h i c h " a u t o m a t i c p r o g r a m m i n g " p e r f o r m e d for the p r o g r a m m e r w e r e c o n c e r n e d w i t h o v e r c o m i n g the m a c h i n e ' s shortcomings. Thus the p r i m a r y c o n c e r n of some " a u t o m a t i c p r o g r a m m i n g " s y s t e m s was to a l l o w the use of s y m b o l i c a d d r e s s e s and d e c i m a l n u m b e r s (e.g., the M I D A C I n p u t T r a n s l a t i o n P r o g r a m [Brown and C a r r 1954]).

The L a n i n g and z i e r l e r s y s t e m was q u i t e a d i f f e r e n t story: it was the w o r l d ' s f i r s t o p e r a t i n g a l g e b r a i c c o m p i l e r , a r a t h e r eleg a n t but s i m p l e one. K n u t h and P a r d o [1977] a s s i g n this h o n o r to A l i c k G l e n n i e ' s A U T O CODE, but I, for one, am u n a b l e to r e c o g n i z e the s a m p l e A U T O C O D E p r o g r a m they g i v e as " a l g e b r a i c " , e s p e c i a l l y w h e n it is c o m p a r e d to the c o r r e s p o n d i n g L a n i n g and Z i e r l e r program. All of the e a r l y " a u t o m a t i c p r o g r a m m i n g " s y s t e m s w e r e c o s t l y to use, s i n c e they slowed the m a c h i n e d o w n by a f a c t o r of five or ten. The m o s t c o m m o n r e a s o n for the slowd o w n was t h a t t h e s e s y s t e m s w e r e s p e n d i n g m o s t of t h e i r time in f l o a t i n g p o i n t subroutines. S i m u l a t e d i n d e x i n g and o t h e r " h o u s e k e e p i n g " o p e r a t i o n s c o u l d be d o n e w i t h s i m p l e i n e f f i c i e n t t e c h n i q u e s , since, s l o w as they were, t h e y t o o k far less time t h a n the f l o a t i n g p o i n t work.

But m o s t of the l a r g e r "automatic. p r o g r a m m i n g " s y s t e m s (with the e x c e p t i o n of L a n i n g and Z i e r l e r ' s a l g e b r a i c s y s t e m [Laning and Z i e r l e r 1954] and the A-2 c o m p i l e r [ R e m i n g t o n R a n d 1953; M o s e r 1954]) s i m p l y p r o v i d e d a s y n t h e t i c " c o m p u t e r " w i t h an order c o d e d i f f e r e n t f r o m that of the real machine. This s y n t h e t i c c o m p u t e r u s u a l l y had f l o a t i n g p o i n t i n s t r u c t i o n s and i n d e x r e g i s t e r s and had i m p r o v e d i n p u t - o u t p u t commands; it was t h e r e f o r e m u c h e a s i e r to prog r a m t h a n its real c o u n t e r p a r t .

Experience with slow "automatic programm i n g " systems, plus t h e i r own e x p e r i e n c e w i t h the p r o b l e m s of o r g a n i z i n g loops and a d d r e s s m o d i f i c a t i o n , had c o n v i n c e d p r o g r a m m e r s t h a t e f f i c i e n t p r o g r a m m i n g was s o m e t h i n g that c o u l d not be a u t o m a t e d . Ano t h e r r e a s o n that " a u t o m a t i c p r o g r a m m i n g " was not t a k e n s e r i o u s l y by the c o m p u t i n g c o m m u n i t y came f r o m the e n e r g e t i c p u b l i c r e l a t i o n s e f f o r t s of some v i s i o n a r i e s to s p r e a d the w o r d t h a t t h e i r " a u t o m a t i c p r o g r a m m i n g " s y s t e m s had a l m o s t h u m a n a b i l i t i e s to u n d e r s t a n d the l a n g u a g e and n e e d s of the user; w h e r e a s c l o s e r i n s p e c t i o n of t h e s e same s y s t e m s w o u l d o f t e n r e v e a l a c o m p l e x , e x c e p t i o n - r i d d e n p e r f o r m e r of c l e r i c a l tasks w h i c h was b o t h d i f f i c u l t to use and i n e f f i cient. W h a t e v e r the r e a s o n s , it is d i f f i c u l t to c o n v e y to a r e a d e r in the late sev-

The A-2 c o m p i l e r a l s o c a m e to be a synt h e t i c c o m p u t e r s o m e t i m e a f t e r e a r l y 1954. But in e a r l y 1954 its i n p u t had a m u c h c r u d e r form; i n s t e a d of " p s e u d o - i n s t r u c tions" its i n p u t was t h e n a c o m p l e x s e q u e n c e of " c o m p i l i n g i n s t r u c t i o n s " t h a t c o u l d take a v a r i e t y of forms r a n g i n g f r o m m a c h i n e c o d e i t s e l f to l e n g t h y g r o u p s of w o r d s c o n s t i t u t i n g r a t h e r c l u m s y c a l l i n g s e q u e n c e s for the d e s i r e d f l o a t i n g p o i n t s u b r o u t i n e , to " a b b r e v i a t e d form" i n s t r u c t i o n s that w e r e c o n v e r t e d by a " T r a n s l a t o r " into o r d i n a r y " c o m p i l i n g i n s t r u c t i o n s " [Moser 1954].

© 1978 Association for Computing Machinery, Inc.

1 65

ACM SlGPLAN Notices, VoI. 13, No. 8, August 1978

e n t i e s the s t r e n g t h of the s k e p t i c i s m a b o u t " a u t o m a t i c p r o g r a m m i n g " in g e n e r a l and a b o u t its a b i l i t y to p r o d u c e e f f i c i e n t p r o g r a m s in p a r t i c u l a r , as it e x i s t e d in 1954.

s t a n d p o i n t of its i n p u t " p r o g r a m s " it p r o v i d e d f e w e r c o n v e n i e n c e s t h a n m o s t of the then c u r r e n t i n t e r p r e t i v e s y s t e m s m e n t i o n ed e a r l i e r ; it l a t e r a d o p t e d a " p s e u d o code" as i n p u t w h i c h was s i m i l a r to the i n p u t c o d e s of t h e s e i n t e r p r e t i v e systems.

(In the a b o v e d i s c u s s i o n of a t t i t u d e s a b o u t " a u t o m a t i c p r o g r a m m i n g " in 1954 I h a v e m e n t i o n e d o n l y t h o s e a c t u a l s y s t e m s of w h i c h m y c o l l e a g u e s and I w e r e a w a r e at the time. For a c o m p r e h e n s i v e t r e a t m e n t of e a r l y p r o g r a i n i n g s y s t e m s and l a n g u a g e s I r e c o m m e n d the a r t i c l e by K n u t h and P a r d o [1977] and S a m m e t [1969].) 1.2

The e c o n o m i c s

The L a n i n g and Z i e r l e r s y s t e m a c c e p t e d as i n p u t an e l e g a n t b u t r a t h e r s i m p l e a l g e braic language. It p e r m i t t e d s i n g l e - l e t t e r variables (identifiers) which could have a s i n g l e c o n s t a n t or v a r i a b l e s u b s c r i p t . The r e p e r t o i r e of f u n c t i o n s one c o u l d use w e r e d e n o t e d by "F" w i t h an i n t e g e r s u p e r s c r i p t to i n d i c a t e the " c a t a l o g n u m b e r " of the desired function. Algebraic expressions were c o m p i l e d into c l o s e d s u b r o u t i n e s and p l a c e d on a m a g n e t i c d r u m for s u b s e q u e n t use. The s y s t e m was o r i g i n a l l y d e s i g n e d for the W h i r l w i n d c o m p u t e r w h e n it had 1,024 s t o r age cells, w i t h the r e s u l t t h a t it c a u s e d a s l o w d o w n in e x e c u t i o n s p e e d by a f a c t o r of a b o u t ten [Adams and L a n i n g 1954].

of p r o g r a m m i n g .

A n o t h e r f a c t o r w h i c h i n f l u e n c e d the dev e l o p m e n t of F O R T R A N w a s the e c o n o m i c s of p r o g r a m m i n g in 1954. The c o s t of p r o g r a m m e r s a s s o c i a t e d w i t h a c o m p u t e r c e n t e r was u s u a l l y at l e a s t as g r e a t as the c o s t of the c o m p u t e r itself. (This f a c t f o l l o w s f r o m the a v e r a g e s a l a r y - p l u s - o v e r h e a d and n u m b e r of p r o g r a m m e r s at e a c h c e n t e r and f r o m the computer rental figures.) In a d d i t i o n , f r o m one q u a r t e r to one h a l f of the c o m p u t e r ' s t i m e was s p e n t in d e b u g g i n g . Thus p ~ o g r a m m i n g and d e b u g g i n g a c c o u n t e d for as m u c h as t h r e e q u a r t e r s of the c o s t of o p e r a t i n g a c o m p u t e r ; and o b v i o u s l y , as c o m p u t e r s g o t c h e a p e r , this s i t u a t i o n w o u l d get worse.

The e f f e c t of the L a n i n g and Z i e r l e r s y s t e m on the d e v e l o p m e n t of F O R T R A N is a q u e s t i o n w h i c h has b e e n m u d d l e d by m a n y m i s s t a t e m e n t s on my part. For m a n y y e a r s I b e l i e v e d t h a t we had g o t t e n the idea for u s i n g a l g e b r a i c n o t a t i o n in F O R T R A N f r o m s e e i n g a d e m o n s t r a t i o n of the L a n i n g and Z i e r l e r s y s t e m at MIT. In p r e p a r i n g a paper [Backus 1976] for the I n t e r n a t i o n a l R e s e a r c h C o n f e r e n c e on the H i s t o r y of Comp u t i n g at Los A l a m o s (June 10-15, 1976), I r e v i e w e d the m a t t e r w i t h I r v i n g Z i l l e r and o b t a i n e d a c o p y of a 1954 l e t t e r [Backus 1954a] (which Dr. L a n i n g k i n d l y s e n t to me). As a r e s u l t the f a c t s of the m a t t e r h a v e b e c o m e clear. The l e t t e r in q u e s t i o n is one I sent to Dr. L a n i n g a s k i n g for a d e m o n s t r a t i o n of his system. It m a k e s c l e a r t h a t we had l e a r n e d of his w o r k at the O f f i c e of N a v a l R e s e a r c h S y m p o s i u m on A u t o m a t i c P r o g r a m m i n g for D i g i t a l C o m p u t e r s , M a y 13-14, 1954, and t h a t the d e m o n s t r a t i o n t o o k p l a c e on J u n e 2, 1954. The l e t t e r a l s o m a k e s c l e a r t h a t the F O R T R A N p r o j e c t was w e l l u n d e r w a y w h e n the l e t t e r was s e n t (May 21, 1954) and i n c l u d e d H a r l a n H e r r i c k , R o b e r t A. N e l s o n , and I r v i n g Z i l l e r as w e l l as m y s e l f . F u r t h e r m o r e , an a r t i c l e in the p r o c e e d i n g s of t h a t same O N R S y m p o s i u m by H e r r i c k and m y s e l f [Backus and H e r r i c k 1954] shows c l e a r l y t h a t we w e r e a l r e a d y c o n s i d e r i n g i n p u t e x p r e s s i o n s like "Zaij •b jk "

T h i s e c o n o m i c f a c t o r was one of the p r i m e m o t i v a t i o n s w h i c h led m e to p r o p o s e the F O R T R A N p r o j e c t in a l e t t e r to m y boss, C u t h b e r t Hurd, in late 1953 (the e x a c t d a t e is n o t k n o w n but o t h e r f a c t s s u g g e s t D e c e m b e r 1953 as a l i k e l y date). I b e l i e v e t h a t the e c o n o m i c n e e d for a s y s t e m like F O R T R A N was one r e a s o n w h y IBM and my s u c c e s s i v e bosses, Hurd, C h a r l e s D e C a r l o , and J o h n M c P h e r s o n , p r o v i d e d for our c o n s t a n t l y e x p a n d i n g n e e d s o v e r the n e x t five y e a r s w i t h o u t e v e r asking us to p r o j e c t or j u s t i f y t h o s e n e e d s in a f o r m a l budget. 1.3

Programming

systems

in 1954.

It is d i f f i c u l t for a p r o g r a m m e r of tod a y to c o m p r e h e n d w h a t " a u t o m a t i c p r o g r a m m i n g " m e a n t to p r o g r a m m e r s in 1954. To m a n y it t h e n m e a n t s i m p l y p r o v i d i n g m n e m o n ic o p e r a t i o n c o d e s and s y m b o l i c a d d r e s s e s , to o t h e r s it m e a n t the s i m p l e ' p r o c e s s of o b t a i n i n g s u b r o u t i n e s f r o m a l i b r a r y and i n s e r t i n g the a d d r e s s e s of o p e r a n d s i n t o each subroutine. Most "automatic programming" systems were either assembly programs, or s u b r o u t i n e - f i x i n g p r o g r a m s , or, m o s t p o p u l a r l y , i n t e r p r e t i v e s y s t e m s to p r o v i d e f l o a t i n g p o i n t and i n d e x i n g o p e r a t i o n s . My f r i e n d s and I w e r e a w a r e of a n u m b e r of a s s e m b l y p r o g r a m s and i n t e r p r e t i v e systems, some of w h i c h h a v e b e e n m e n t i o n e d above; b e s i d e s t h e s e t h e r e w e r e p r i m a r i l y two o t h e r s y s t e m s of s i g n i f i c a n c e : the A-2 c o m p i l e r [ R e m i n g t o n R a n d 1953; M o s e r 1954] and the L a n i n g and Z i e r l e r [1954] a l g e b r a i c c o m p i l e r at MIT. As n o t e d above, the A-2 c o m p i l e r was at t h a t time l a r g e l y a subr o u t i n e - f i x e r (its o t h e r p r i n c i p a l t a s k was to p r o v i d e for " o v e r l a y s " ) ; but f r o m the

and "X÷Y". We w e n t on to r a i s e the q u e s tion "...can a machine translate a sufficiently rich mathematical language into a s u f f i c i e n t l y e c o n o m i c a l p r o g r a m at a suff i c i e n t l y low c o s t to m a k e the w h o l e a f f a i r feasible?" T h e s e and o t h e r r e m a r k s in o u r p a p e r p r e s e n t e d at the S y m p o s i u m in M a y 1954 m a k e it c l e a r t h a t we w e r e a l r e a d y c o n s i d e r i n g algebraic input considerably more sophist i c a t e d t h a n t h a t of L a n i n g and Z i e r l e r ' s s y s t e m w h e n we f i r s t h e a r d of t h e i r p i o n e e r ing work. Thus, a l t h o u g h L a n i n g and Z i e r l e r had a l r e a d y p r o d u c e d the w o r l d ' s f i r s t al-

166

g e b r a i c c o m p i l e r , our b a s i c ideas for F O R T R A N had b e e n d e v e l o p e d i n d e p e n d e n t l y ; thus it is d i f f i c u l t to k n o w what, if any, new ideas we got f r o m s e e i n g the d e m o n s t r a t i o n of t h e i r system.

e x i s t e d to p r o v i d e ; second, it i n c r e a s e d the p r o b l e m of g e n e r a t i n g e f f i c i e n t p r o g r a m s by an o r d e r of m a g n i t u d e by s p e e d i n g up f l o a t ing p o i n t o p e r a t i o n s by a f a c t o r of ten and t h e r e b y l e a v i n g i n e f f i c i e n c i e s n o w h e r e to hide. In v i e w of the w i d e s p r e a d s k e p t i c i s m a b o u t the p o s s i b i l i t y of p r o d u c i n g e f f i c i e n t p r o g r a m s w i t h an a u t o m a t i c p r o g r a m m i n g system and the f a c t that i n e f f i c i e n c i e s c o u l d no l o n g e r be hidden, we w e r e c o n v i n c e d t h a t the k i n d of s y s t e m we had in m i n d w o u l d be w i d e l y u s e d o n l y if we c o u l d d e m o n s t r a t e that it w o u l d p r o d u c e p r o g r a m s a l m o s t as e f f i c i e n t as h a n d c o d e d o n e s and do so on v i r t u a l l y e v e r y job.

Q u a s i - f o o t n o t e : In r e s p o n s e to s u g g e s t i o n s of the P r o g r a m C o m m i t t e e let me try to d e a l e x p l i c i t l y w i t h the q u e s t i o n of w h a t w o r k m i g h t h a v e inf l u e n c e d our e a r l y ideas for F O R T R A N , alt h o u g h it is m o s t l y a m a t t e r of l i s t i n g w o r k of w h i c h we w e r e then u n a w a r e . I have a l r e a d y d i s c u s s e d the w o r k of L a n i n g and Z i e r l e r and the A-2 c o m p i l e r . The w o r k of H e i n z R u t i s h a u s e r [1952] is d i s c u s s e d l a t e r on. L i k e m o s t of the w o r l d (except p e r h a p s R u t i s h a u s e r and C o r r a d o B 6 h m - - w h o was the f i r s t to d e s c r i b e a c o m p i l e r in its own l a n g u a g e [B6hm 195~]) we w e r e e n t i r e l y una w a r e of the w o r k of K o n r a d Zuse [1959; 1972]. Zuse's " P l a n k a l k ~ l " , w h i c h he comp l e t e d in 1945, was, in some ways, a m o r e e l e g a n t and a d v a n c e d p r o g r a m m i n g l a n g u a g e t h a n t h o s e t h a t a p p e a r e d ten and f i f t e e n y e a r s later.

It was our b e l i e f that if F O R T R A N , d u r ing its f i r s t m o n t h s , w e r e to t r a n s l a t e any r e a s o n a b l e " s c i e n t i f i c " s o u r c e p r o g r a m into an o b j e c t p r o g r a m o n l y half as fast as its h a n d c o d e d c o u n t e r p a r t , then a c c e p t a n c e of our s y s t e m w o u l d be in s e r i o u s danger. This b e l i e f c a u s e d us to r e g a r d the d e s i g n of the t r a n s l a t o r as the r e a l c h a l l e n g e , not the s i m p l e t a s k of d e s i g n i n g the language. Our b e l i e f in the s i m p l i c i t y of l a n g u a g e d e s i g n was p a r t l y c o n f i r m e d by the relative ease with which similar languages had b e e n i n d e p e n d e n t l y d e v e l o p e d by R u t i s h a u s e r [1952], L a n i n g and Z i e r l e r [1954], and o u r s e l v e s ; w h e r e a s we w e r e a l o n e in s e e k i n g to p r o d u c e r e a l l y e f f i c i e n t o b j e c t programs.

We w e r e a l s o u n a w a r e of the w o r k of M a u c h l y et al. ("Short Code", 1950) , B u r k s ( " I n t e r m e d i a t e PL", 1950) , B 6 h m (1951) , G l e n n i e ("AUTOCODE", 1952) as d i s c u s s e d in K n u t h and P a r d o [1977]. We w e r e a w a r e of but not i n f l u e n c e d by the a u t o m a t i c p r o g r a m ming efforts which simulated a synthetic c o m p u t e r (e.g., M I T "Summer S e s s i o n Computer", SHACO, DUAL, S P E E D C O D I N G , and the I L L I A C system), s i n c e t h e i r l a n g u a g e s and s y s t e m s w e r e so d i f f e r e n t f r o m t h o s e of FORTRAN. Nor w e r e we i n f l u e n c e d by a l g e braic systems which were designed after our " P r e l i m i n a r y R e p o r t " [1954] but w h i c h b e g a n o p e r a t i o n b e f o r e F O R T R A N (e.g., B A C A I C [Grems and P o r t e r 1956], IT [Perlis, S m i t h and V a n Z o e r e n 1957], M A T H M A T I C [Ash et al. 1957]). Although PACT I [Baker 1956] was not an a l g e b r a i c compiler, it d e s e r v e s m e n t i o n as a s i g n i f i c a n t d e v e l o p m e n t d e s i g n e d a f t e r the F O R T R A N l a n g u a g e but in o p e r a t i o n b e f o r e F O R T R A N , w h i c h a l s o did not i n f l u e n c e our work. (End of q u a s i - f o o t n o t e . )

To this d a y I b e l i e v e t h a t our e m p h a s i s on o b j e c t p r o g r a m e f f i c i e n c y r a t h e r t h a n on l a n g u a g e d e s i g n was b a s i c a l l y correct. I b e l i e v e t h a t had we f a i l e d to p r o d u c e eff i c i e n t p r o g r a m s , the w i d e s p r e a d use of l a n g u a g e s like F O R T R A N w o u l d h a v e b e e n seriously delayed. In fact, I b e l i e v e t h a t we are in a similar, but u n r e c o g n i z e d , situ a t i o n today: in s p i t e of all the fuss t h a t has b e e n m a d e o v e r m y r i a d l a n g u a g e d e t a i l s , c u r r e n t c o n v e n t i o n a l l a n g u a g e s are still v e r y w e a k p r o g r a m m i n g aids, and far m o r e p o w e r f u l l a n g u a g e s w o u l d be in use t o d a y if a n y o n e had f o u n d a w a y to m a k e t h e m run with adequate efficiency. In o t h e r words, the n e x t r e v o l u t i o n in p r o g r a m m i n g w i l l take p l a c e o n l y w h e n b o t h of the f o l l o w i n g r e q u i r e m e n t s h a v e b e e n met: (a) a new k i n d of p r o g r a m m i n g l a n g u a g e , far m o r e p o w e r f u l t h a n those of today, has b e e n d e v e l o p e d and (b) a t e c h n i q u e has b e e n f o u n d for exe c u t i n g its p r o g r a m s at not m u c h g r e a t e r c o s t than t h a t of t o d a y ' s p r o g r a m s .

Our O N R S y m p o s i u m a r t i c l e [Backus and H e r r i c k 195~] a l s o m a k e s c l e a r t h a t the F O R T R A N g r o u p was a l r e a d y a w a r e t h a t it f a c e d a n e w k i n d of p r o b l e m in a u t o m a t i c programming. The v i a b i l i t y of m o s t c o m p i l ers and i n t e r p r e t e r s p r i o r to F O R T R A N had r e s t e d on the f a c t that m o s t s o u r c e l a n g u a g e o p e r a t i o n s w e r e not m a c h i n e o p e r a t i o n s . Thus e v e n l a r g e i n e f f i c i e n c i e s in p e r f o r m ing b o t h l o o p i n g / t e s t i n g o p e r a t i o n s and c o m p u t i n g a d d r e s s e s w e r e m a s k e d by m o s t ope r a t i n g time b e i n g s p e n t in f l o a t i n g p o i n t subroutines. B u t the a d v e n t of the 70~ w i t h b u i l t in. f l o a t i n g p o i n t and i n d e x i n g r a d i c a l l y a l t e r e d the s i t u a t i o n . The 70~ p r e s e n t e d a d o u b l e c h a l l e n g e to t h o s e w h o w a n t e d to s i m p l i f y p r o g r a m m i n g ; f i r s t it rem o v e d the r a i s o n d ' E t r e of e a r l i e r s y s t e m s by p r o v i d i n g in h a r d w a r e the o p e r a t i o n s t h e y

B e c a u s e of our 1954 v i e w t h a t s u c c e s s in p r o d u c i n g e f f i c i e n t p r o g r a m s was m o r e imp o r t a n t than the d e s i g n of the F O R T R A N language, I c o n s i d e r the h i s t o r y of the comp i l e r c o n s t r u c t i o n and the w o r k of its inv e n t o r s an i n t e g r a l p a r t of the h i s t o r y of the F O R T R A N l a n g u a g e ; t h e r e f o r e a later s e c t i o n d e a l s w i t h that subject. 2. The e a r l y

s t a g e s of the F O R T R A N p r o j e c t .

After Cuthbert Hurd approved my proposal to d e v e l o p a p r a c t i c a l a u t o m a t i c p r o g r a m m i n g s y s t e m for the 704 in D e c e m b e r 1953 or

167

J a n u a r y 1954, I r v i n g Z i l l e r w a s a s s i g n e d to the p r o j e c t . We s t a r t e d w o r k in one of the m a n y s m a l l o f f i c e s the p r o j e c t w a s to occ u p y in the v i c i n i t y of IBM h e a d q u a r t e r s at 590 M a d i s o n A v e n u e in N e w York; the f i r s t of t h e s e was in the Jay T h o r p e B u i l d ing on F i f t h A v e n u e . By M a y 1954 we h a d b e e n j o i n e d by H a r l a n H e r r i c k and then by a n e w e m p l o y e e w h o h a d b e e n h i r e d to do t e c h n i c a l typing, R o b e r t A. N e l s o n (with Ziller, he soon b e g a n d e s i g n i n g o n e of the m o s t s o p h i s t i c a t e d s e c t i o n s of the c o m p i l e r ; he is n o w an IBM F e l l o w ) . By a b o u t M a y we h a d m o v e d to the 19th f l o o r of the a n n e x of 590 M a d i s o n A v e n u e , n e x t to the e l e v a t o r m a c h i n e r y ; the g r o u n d f l o o r of this b u i l d ing h o u s e d the 701 i n s t a l l a t i o n on w h i c h c u s t o m e r s t e s t e d t h e i r p r o g r a m s b e f o r e the a r r i v a l of t h e i r o w n m a c h i n e s . It w a s h e r e t h a t m o s t of the F O R T R A N l a n g u a g e w a s designed, m o s t l y by H e r r i c k , Z i l l e r and m y self, e x c e p t t h a t m o s t of the i n p u t - o u t p u t l a n g u a g e and f a c i l i t i e s w e r e d e s i g n e d by Roy Nutt, an e m p l o y e e of U n i t e d A i r c r a f t Corp. w h o w a s soon to b e c o m e a m e m b e r of the F O R T R A N p r o j e c t .

puter, n o t to m e n t i o n t h o s e of o t h e r m a n u facturers. (After all, t h e r e w e r e v e r y few c o m p u t e r s a r o u n d then.) B u t we did e x p e c t our s y s t e m to h a v e a big impact, in the s e n s e t h a t it w o u l d m a k e p r o g r a m m i n g for the 704 v e r y m u c h faster, c h e a p e r , m o r e reliable. W e a l s o e x p e c t e d that, if we w e r e s u c c e s s f u l in m e e t i n g our g o a l s , o t h e r g r o u p s and m a n u f a c t u r e r s w o u l d f o l l o w our e x a m p l e in r e d u c i n g the c o s t of p r o g r a m m i n g by p r o v i d i n g s i m i l a r s y s t e m s w i t h d i f f e r e n t but similar languages [Preliminary Report 1954]. By the fall of 1954 w e had b e c o m e the " P r o g r a m m i n g R e s e a r c h G r o u p " and I h a d bec o m e its " m a n a g e r " . By N o v e m b e r of t h a t y e a r we h a d p r o d u c e d a paper: " P r e l i m i n a r y R e p o r t , S p e c i f i c a t i o n s for the I B M M a t h e m a t ical F O R m u l a T R A N s l a t i n g S y s t e m , F O R T R A N " [ P r e l i m i n a r y R e p o r t 1954] d a t e d N o v e m b e r 10. In its i n t r o d u c t i o n w e n o t e d t h a t " s y s t e m s w h i c h h a v e s o u g h t to r e d u c e the job of c o d ing and d e b u g g i n g p r o b l e m s h a v e o f f e r e d the c h o i c e of e a s y c o d i n g and s l o w e x e c u t i o n or l a b o r i o u s c o d i n g and f a s t e x e c u t i o n . " On the b a s i s m o r e of f a i t h t h a n of k n o w l e d g e , we s u g g e s t e d t h a t p r o g r a m s "will be e x e c u t e d in a b o u t the same time t h a t w o u l d be req u i r e d h a d the p r o b l e m b e e n l a b o r i o u s l y hand coded." In w h a t t u r n e d o u t to be a t r u e s t a t e m e n t , we said t h a t " F O R T R A N m a y a p p l y c o m p l e x , l e n g t h y t e c h n i q u e s in c o d i n g a p r o b l e m w h i c h the h u m a n c o d e r w o u l d h a v e n e i t h e r the t i m e nor i n c l i n a t i o n to d e r i v e or a p p l y . "

A f t e r we h a d f i n i s h e d d e s i g n i n g m o s t of the l a n g u a g e we h e a r d a b o u t R u t i s h a u s e r ' s p r o p o s a l s for a s i m i l a r l a n g u a g e [Rutish a u s e r 1952]. It w a s c h a r a c t e r i s t i c of the u n s c h o l a r l y a t t i t u d e of m o s t p r o g r a m m e r s then, and of o u r s e l v e s in p a r t i c u l a r , t h a t we d i d n o t b o t h e r to c a r e f u l l y r e v i e w the s k e t c h y t r a n s l a t i o n of his p r o p o s a l s t h a t we f i n a l l y o b t a i n e d , s i n c e f r o m t h e i r symb o l i c c o n t e n t they d i d n o t a p p e a r to add a n y t h i n g n e w to our p r o p o s e d l a n g u a g e . R u t i s h a u s e r ' s l a n g u a g e h a d a for s t a t e m e n t and o n e - d i m e n s i o n a l a r r a y s , b u t no IF, GOTO, n o r I/O s t a t e m e n t s . Subscript variables c o u l d n o t be u s e d as o r d i n a r y v a r i a b l e s and operator precedence was ignored. His 1952 a r t i c l e d e s c r i b e d two c o m p i l e r s for this l a n g u a g e (for m o r e d e t a i l s see [Knuth and P a r d o 1977]). As far as we w e r e aware, w e s i m p l y m a d e up the l a n g u a g e as we w e n t along. We did not r e g a r d l a n g u a g e d e s i g n as a d i f f i c u l t p r o b l e m , m e r e l y a s i m p l e p r e l u d e to the real problem: designing a compiler which could produce efficient programs. Of c o u r s e o n e of our g o a l s was to d e s i g n a l a n g u a g e w h i c h w o u l d m a k e it p o s s i b l e for e n g i n e e r s and s c i e n t i s t s to w r i t e p r o g r a m s t h e m s e l v e s for the 704. W e a l s o w a n t e d to e l i m i n a t e a lot of the b o o k k e e p i n g and detailed, repetitive planning which hand coding i n v o l v e d . V e r y e a r l y in our w o r k w e h a d in m i n d the n o t i o n s of a s s i g n m e n t s t a t e m e n t s , s u b s c r i p t e d v a r i a b l e s , and the DO s t a t e m e n t (which I b e l i e v e w a s p r o p o s e d by Herrick). We felt that these provided a g o o d b a s i s for a c h i e v i n g o u r g o a l s for the l a n g u a g e , and w h a t e v e r else w a s n e e d e d em e r g e d as w e t r i e d to b u i l d a w a y of p r o g r a m m i n g o n t h e s e b a s i c ideas.

The l a n g u a g e d e s c r i b e d in the " P r e l i m i n a r y R e p o r t " h a d v a r i a b l e s of o n e or two c h a r a c t e r s in length, f u n c t i o n n a m e s of t h r e e or m o r e c h a r a c t e r s , r e c u r s i v e l y defined "expressions", subscripted variables w i t h up to t h r e e s u b s c r i p t s , "arithmetic formulas" (which t u r n o u t to be a s s i g n m e n t s t a t e m e n t s ) , and " D O - f o r m u l a s " . T h e s e latter f o r m u l a s c o u l d s p e c i f y b o t h the f i r s t and l a s t s t a t e m e n t s to be c o n t r o l l e d , thus p e r m i t t i n g a DO to c o n t r o l a d i s t a n t seq u e n c e of s t a t e m e n t s , as w e l l as s p e c i f y i n g a t h i r d s t a t e m e n t to w h i c h c o n t r o l w o u l d p a s s f o l l o w i n g the end of the i t e r a t i o n . If o n l y o n e s t a t e m e n t was s p e c i f i e d , the "range" of the DO w a s the s e q u e n c e of s t a t e m e n t s f o l l o w i n g the DO d o w n to the s p e c i f i e d statement. E x p r e s s i o n s in " a r i t h m e t i c f o r m u l a s " c o u l d be "mixed": i n v o l v e b o t h " f i x e d p o i n t " (integer) a n d " f l o a t i n g p o i n t " q u a n t i t i e s . The a r i t h m e t i c u s e d (all i n t e g e r or all f l o a t i n g point) to e v a l u a t e a m i x e d e x p r e s sion w a s d e t e r m i n e d by the t y p e of the v a r i a b l e on the l e f t of the "=" sign. "IFf o r m u l a s " e m p l o y e d an e q u a l i t y or i n e q u a l ity sign ("=" or ">" or ">=") b e t w e e n two (restricted) e x p r e s s i o n s , f o l l o w e d by two s t a t e m e n t n u m b e r s , o n e for the "true" case, the o t h e r for the "false" case. A " R e l a b e l f o r m u l a " w a s d e s i g n e d to m a k e it e a s y to r o t a t e , say, the i n d i c e s of the r o w s of a m a t r i x so t h a t the same c o m p u t a -

W e c e r t a i n l y h a d no idea t h a t l a n g u a g e s a l m o s t i d e n t i c a l to the o n e w e w e r e w o r k i n g on w o u l d be u s e d for m o r e t h a n one IBM com-

168

a p r o g r a m "by i n d e p e n d e n t l y r e c r e a t i n g the s p e c i f i c a t i o n s for a p r o b l e m f r o m its F O R T R A N f o r m u l a t i o n [!]" It says n o t h i n g a b o u t the s y s t e m c a t c h i n g s y n t a c t i c errors, but n o t e s t h a t an e r r o r - f i n d i n g p r o g r a m can be w r i t t e n a f t e r some e x p e r i e n c e w i t h e r r o r s has b e e n a c c u m u l a t e d .

tion w o u l d apply, a f t e r r e l a b e l l i n g , e v e n t h o u g h a n e w r o w had b e e n r e a d in and the n e x t c o m p u t a t i o n was n o w to take p l a c e on a d i f f e r e n t , r o t a t e d set of rows. Thus, for e x a m p l e , if b is a 4 by 4 m a t r i x , a f t e r R E L A B E L b(3,1), a r e f e r e n c e to b(1,j) has the same m e a n i n g as b(3,j) b e f o r e r e l a b e l ling; b(2,j) a f t e r = b(4,j) before; b(3,j) a f t e r = b(1,j) before; and b(4,j) a f t e r = b(2,j) b e f o r e r e l a b e l l i n g .

U n f o r t u n a t e l y we w e r e h o p e l e s s l y o p t i m i s t i c in 1954 a b o u t the p r o b l e m s of d e b u g g i n g F O R T R A N p r o g r a m s (thus we find on p a g e 2 of the Report: " S i n c e F O R T R A N s h o u l d v i r t u a l l y e l i m i n a t e c o d i n g and d e b u g g i n g . . . [!]") and h e n c e s y n t a c t i c e r r o r c h e c k i n g f a c i l i t i e s in the f i r s t d i s t r i b u t i o n of F O R T R A N I w e r e weak. Better facilities w e r e a d d e d not long a f t e r d i s t r i b u t i o n and f a i r l y g o o d s y n t a c t i c c h e c k i n g was p r o v i d e d in F O R T R A N II.

The i n p u t - o u t p u t s t a t e m e n t s p r o v i d e d inc l u d e d the b a s i c n o t i o n of s p e c i f y i n g the s e q u e n c e in w h i c h d a t a was to be r e a d in or out, but did not i n c l u d e any "Format" s t a t e ments. The R e p o r t also lists four k i n d s of " s p e c i f i c a t i o n s e n t e n c e s " : (I) " d i m e n s i o n s e n t e n c e s " for g i v i n g the d i m e n s i o n s of arrays, (2) " e q u i v a l e n c e s e n t e n c e s " for ass i g n i n g the same s t o r a g e l o c a t i o n s to v a r iables, (3) " f r e q u e n c y s e n t e n c e s " for ind i c a t i n g e s t i m a t e d r e l a t i v e f r e q u e n c y of b r a n c h p a t h s or loops to h e l p the c o m p i l e r o p t i m i z e the o b j e c t p r o g r a m , and (4) "rela t i v e c o n s t a n t s e n t e n c e s " to i n d i c a t e subs c r i p t v a r i a b l e s w h i c h are e x p e c t e d to change their values very infrequently.

The F O R T R A N l a n g u a g e d e s c r i b e d in the Programmer's Reference Manual dated October 15, 1956 [IBM 1956] d i f f e r e d in a few res p e c t s f r o m t h a t of the P r e l i m i n a r y Report, but, c o n s i d e r i n g our i g n o r a n c e in 1954 of the p r o b l e m s we w o u l d later e n c o u n t e r in p r o d u c i n g the c o m p i l e r , there w e r e r e m a r k a b l y few d e l e t i o n s (the R e l a b e l and R e l a tive C o n s t a n t s t a t e m e n t s ) , a few r e t r e a t s , some f o r t u n a t e , some not ( s i m p l i f i c a t i o n of DO s t a t e m e n t s , d r o p p i n g i n e q u a l i t i e s f r o m IF s t a t e m e n t s - - f o r lack of a ">" symbol, and p r o h i b i t i n g m o s t "mixed" e x p r e s s i o n s and s u b s c r i p t e d s u b s c r i p t s ) , and the r e c t i f i c a t i o n of a few o m i s s i o n s ( a d d i t i o n of FORMAT, C O N T I N U E , c o m p u t e d and a s s i g n e d GOTO s t a t e m e n t s , i n c r e a s i n g the l e n g t h of v a r i a b l e s to up to six c h a r a c t e r s , and g e n e r a l i m p r o v e m e n t of i n p u t - o u t p u t s t a t e m e n t s ) .

T o w a r d the end of the R e p o r t (pp. 26-27) t h e r e is a s e c t i o n " F u t u r e a d d i t i o n s to the F O R T R A N system". Its f i r s t i t e m is: "a v a r i e t y of new i n p u t - o u t p u t f o r m u l a s w h i c h w o u l d e n a b l e the p r o g r a m m e r to s p e c i f y v a r ious f o r m a t s for cards, p r i n t i n g , i n p u t tapes and o u t p u t tapes" It is b e l i e v e d t h a t this i t e m is a r e s u l t of our e a r l y c o n s u l t a t i o n s w i t h Roy Nutt. This s e c t i o n goes on to list o t h e r p r o p o s e d f a c i l i t i e s to be added: c o m p l e x and d o u b l e p r e c i s i o n arithmetic, matrix arithmetic, sorting, solving simultaneous equations, differential e q u a t i o n s , and l i n e a r p r o g r a m m i n g p r o b l e m s . It a l s o d e s c r i b e s f u n c t i o n d e f i n i t i o n capa b i l i t i e s s i m i l a r to those w h i c h later app e a r e d in F O R T R A N II; f a c i l i t i e s for numerical integration; a summation operator; and t a b l e l o o k u p f a c i l i t i e s . The final s e c t i o n of the R e p o r t (pp 2829) d i s c u s s e s p r o g r a m m i n g t e c h n i q u e s to use to h e l p the s y s t e m p r o d u c e e f f i c i e n t p r o grams. It d i s c u s s e s h o w to use p a r e n t h e s e s to h e l p the s y s t e m i d e n t i f y i d e n t i c a l sube x p r e s s i o n s w i t h i n an e x p r e s s i o n and t h e r e by e l i m i n a t e t h e i r d u p l i c a t e c a l c u l a t i o n . T h e s e p a r e n t h e s e s had to be s u p p l i e d o n l y w h e n a r e c u r r i n g s u b e x p r e s s i o n o c c u r r e d as p a r t of a t e r m (e.g., if a~b o c c u r r e d in s e v e r a l places, it w o u l d be b e t t e r to w r i t e the t e r m a ~ b ~ c as (a~b)~c to a v o i d d u p l i c a t e c a l c u l a t i o n ) ; o t h e r w i s e the s y s t e m w o u l d i d e n t i f y d u p l i c a t e s w i t h o u t any a s s i s t a n c e . It a l s o o b s e r v e s t h a t the s y s t e m w o u l d not p r o d u c e o p t i m a l c o d e for loops c o n s t r u c t e d w i t h o u t DO s t a t e m e n t s . This final s e c t i o n of the R e p o r t a l s o n o t e s that "no s p e c i a l p r o v i s i o n s h a v e b e e n i n c l u d e d in the F O R T R A N s y s t e m for l o c a t i n g e r r o r s in f o r m u l a s " . It s u g g e s t s c h e c k i n g

169

S i n c e our e n t i r e a t t i t u d e a b o u t l a n g u a g e d e s i g n had a l w a y s b e e n a v e r y c a s u a l one, the c h a n g e s w h i c h we felt to be d e s i r a b l e d u r i n g the c o u r s e of w r i t i n g the c o m p i l e r were made equally casually. We n e v e r f e l t t h a t any of t h e m i n v o l v e d a real s a c r i f i c e in c o n v e n i e n c e or p o w e r (with the p o s s i b l e e x c e p t i o n of the R e l a b e l s t a t e m e n t , w h o s e p u r p o s e was to c o o r d i n a t e i n p u t - o u t p u t w i t h c o m p u t a t i o n s on arrays, but this was one f a c i l i t y w h i c h we felt w o u l d h a v e b e e n r e a l l y d i f f i c u l t to i m p l e m e n t ) . I believe the s i m p l i f i c a t i o n of the o r i g i n a l DO s t a t e m e n t r e s u l t e d f r o m the r e a l i z a t i o n t h a t (a) it w o u l d be h a r d to d e s c r i b e p r e c i s e l y , (b) it was a w k w a r d to c o m p i l e , and (c) it p r o v i d e d l i t t l e p o w e r b e y o n d t h a t of the final v e r s i o n . In our n a i v e u n a w a r e n e s s of l a n g u a g e d e s i g n p r o b l e m s - - o f c o u r s e we k n e w n o t h i n g of m a n y i s s u e s w h i c h w e r e later t h o u g h t to be i m p o r t a n t , e.g., b l o c k s t r u c t u r e , cond i t i o n a l e x p r e s s i o n s , type d e c l a r a t i o n s - it s e e m e d to us t h a t o n c e one had the not i o n s of the a s s i g n m e n t s t a t e m e n t , the subs c r i p t e d v a r i a b l e , and the DO s t a t e m e n t in h a n d (and t h e s e w e r e a m o n g our e a r l i e s t ideas), then the r e m a i n i n g p r o b l e m s of lang u a g e d e s i g n w e r e t r i v i a l : e i t h e r t h e i r solu t i o n was t h r u s t u p o n one by the n e e d to p r o v i d e some m a c h i n e f a c i l i t y such as r e a d -

ing input, or by some p r o g r a m m i n g t a s k w h i c h c o u l d n o t be d o n e w i t h e x i s t i n g s t r u c t u r e s (e.g., s k i p p i n g to the end of a DO l o o p w i t h o u t s k i p p i n g the i n d e x i n g i n s t r u c t i o n s there: this g a v e rise to the C O N T I N U E s t a t e ment).

Washington (D.C.), A l b u q u e r q u e , P i t t s b u r g h , Los A n g e l e s , and o n e or two o t h e r p l a c e s were not very helpful. O n e t r i p to g i v e o u r talk, p r o b a b l y in J a n u a r y 1955, h a d an e x c e l l e n t p a y o f f . This talk, at U n i t e d A i r c r a f t Corp., r e s u l t e d in an a g r e e m e n t b e t w e e n o u r g r o u p and W a l t e r R a m s h a w at U n i t e d A i r c r a f t t h a t Roy N u t t w o u l d b e c o m e a r e g u l a r p a r t of o u r e f f o r t ( a l t h o u g h r e m a i n i n g an e m p l o y e e of U n i t e d A i r c r a f t ) to c o n t r i b u t e his e x p e r t i s e on i n p u t - o u t p u t and a s s e m b l y r o u t i n e s . With a few b r e a k s d u e to his i n v o l v e m e n t in w r i t i n g v a r i o u s S H A R E p r o g r a m s , he w o u l d t h e n c e f o r t h c o m e to N e w Y o r k two or t h r e e t i m e s a w e e k u n t i l e a r l y 1957.

O n e m u c h - c r i t i c i z e d d e s i g n c h o i c e in F O R T R A N c o n c e r n s the u s e of spaces: b l a n k s w e r e i g n o r e d , e v e n b l a n k s in the m i d d l e of an i d e n t i f i e r . Roy Nutt reminds me that t h a t c h o i c e w a s p a r t l y in r e c o g n i t i o n of a p r o b l e m w i d e l y k n o w n in SHARE, the 704 users' a s s o c i a t i o n . There was a common prob l e m w i t h k e y p u n c h e r s n o t r e c o g n i z i n g or p r o p e r l y c o u n t i n g b l a n k s in h a n d w r i t t e n data, a n d this c a u s e d m a n y e r r o r s . We also r e g a r d e d i g n o r i n g b l a n k s as a d e v i c e to ena b l e p r o g r a m m e r s to a r r a n g e t h e i r p r o g r a m s in a m o r e r e a d a b l e f o r m w i t h o u t a l t e r i n g t h e i r m e a n i n g or i n t r o d u c i n g c o m p l e x r u l e s for f o r m a t t i n g s t a t e m e n t s .

It is d i f f i c u l t to a s s e s s the i n f l u e n c e the e a r l y w o r k of the F O R T R A N g r o u p h a d on other projects. C e r t a i n l y the d i s c u s s i o n of L a n i n g and Z i e r l e r ' s a l g e b r a i c c o m p i l e r at the O N R S y m p o s i u m in M a y 1954 w o u l d h a v e b e e n m o r e l i k e l y to p e r s u a d e s o m e o n e to und e r t a k e a s i m i l a r l i n e of e f f o r t t h a n w o u l d the b r i e f d i s c u s s i o n of the m e r i t s of u s i n g "a f a i r l y n a t u r a l m a t h e m a t i c a l language" t h a t a p p e a r e d t h e r e in the p a p e r by H e r r i c k and m y s e l f [Backus and H e r r i c k 1954]. But it w a s o u r i m p r e s s i o n t h a t our d i s c u s s i o n s w i t h v a r i o u s g r o u p s a f t e r t h a t time, t h e i r a c c e s s to our P r e l i m i n a r y R e p o r t , and t h e i r a w a r e n e s s of the e x t e n t and s e r i o u s n e s s of our e f f o r t s , t h a t t h e s e f a c t o r s e i t h e r g a v e the i n i t i a l s t i m u l u s to some o t h e r p r o j e c t s or at l e a s t c a u s e d t h e m to be m o r e a c t i v e than they might have been otherwise. It w a s o u r i m p r e s s i o n , for e x a m p l e , t h a t the "IT" p r o j e c t [Perlis, S m i t h and V a n Z o e r e n 1957] at P u r d u e and l a t e r at C a r n e g i e - M e l l o n b e g a n s h o r t l y a f t e r the d i s t r i b u t i o n of our P r e l i m i n a r y R e p o r t , as d i d the " M A T H - M A T I C " p r o j e c t [Ash et al. 1957] at S p e r r y Rand.

A n o t h e r d e b a t a b l e d e s i g n c h o i c e w a s to rule out "mixed" m o d e e x p r e s s i o n s i n v o l v i n g b o t h i n t e g e r and f l o a t i n g p o i n t q u a n t i t i e s . A l t h o u g h our P r e l i m i n a r y R e p o r t had i n c l u d e d such e x p r e s s i o n s , a n d r u l e s for e v a l u a t i n g them, we f e l t t h a t if c o d e for t y p e c o n v e r sion w e r e to be g e n e r a t e d , the u s e r s h o u l d be a w a r e of that, and the b e s t w a y to i n s u r e t h a t he w a s a w a r e w a s to ask h i m to s p e c i f y them. I b e l i e v e we w e r e a l s o d o u b t f u l of the u s e f u l n e s s of the r u l e s in o u r R e p o r t for e v a l u a t i n g m i x e d e x p r e s s i o n s . In a n y case, the m o s t c o m m o n sort of " m i x t u r e s " was a l l o w e d : i n t e g e r e x p o n e n t s and f u n c t i o n a r g u m e n t s w e r e a l l o w e d in a f l o a t i n g point expression. In late 1954 and e a r l y 1955, a f t e r comp l e t i n g the P r e l i m i n a r y R e p o r t , H a r l a n H e r rick, I r v i n g Z i l l e r and I g a v e p e r h a p s five or six t a l k s a b o u t our p l a n s for F O R T R A N to v a r i o u s g r o u p s of I B M c u s t o m e r s w h o h a d ord e r e d a 704 (the 704 h a d b e e n a n n o u n c e d a b o u t M a y 1954). A t t h e s e t a l k s we c o v e r e d the m a t e r i a l in the R e p o r t and d i s c u s s e d o u r p l a n s for the c o m p i l e r (which w a s to be comp l e t e d w i t h i n a b o u t six m o n t h s [!] ; this w a s to r e m a i n the i n t e r v a l - t o - c o m p l e t i o n u n t i l it a c t u a l l y was c o m p l e t e d o v e r two y e a r s later, in A p r i l 1957). In a d d i t i o n to i n f o r m i n g c u s t o m e r s a b o u t our p l a n s , ano t h e r p u r p o s e of t h e s e t a l k s was to a s s e m b l e a list of t h e i r o b j e c t i o n s and f u r t h e r requirements. In this we w e r e d i s a p p o i n t e d ; o u r l i s t e n e r s w e r e m o s t l y s k e p t i c a l ; I bel i e v e t h e y h a d h e a r d too m a n y g l o w i n g d e s c r i p t i o n s of w h a t t u r n e d o u t to be c l u m s y s y s t e m s to take us s e r i o u s l y . In t h o s e d a y s o n e w a s a c c u s t o m e d to f i n d i n g lots of p e c u l iar b u t s i g n i f i c a n t r e s t r i c t i o n s in a s y s t e m w h e n it f i n a l l y a r r i v e d t h a t h a d n o t b e e n m e n t i o n e d in its o r i g i n a l d e s c r i p t i o n . Most of all, our c l a i m s t h a t w e w o u l d p r o d u c e efficient object programs were disbelieved. Whatever thereasons, w e r e c e i v e d a l m o s t no s u g g e s t i o n s or f e e d b a c k ; o u r l i s t e n e r s h a d d o n e a l m o s t no t h i n k i n g a b o u t the p r o b l e m s w e f a c e d and h a d a l m o s t no s u g g e s t i o n s or criticisms. T h u s we f e l t t h a t our t r ip s to

It is n o t c l e a r w h a t i n f l u e n c e , if any, our Los A n g e l e s t a l k and e a r l i e r c o n t a c t s w i t h m e m b e r s of t h e i r g r o u p had on the P A C T I e f f o r t [Baker 1956], w h i c h I b e l i e v e w a s a l r e a d y in its f o r m a t i v e s t a g e s w h e n we g o t to Los A n g e l e s . It is clear, w h a t e v e r inf l u e n c e the s p e c i f i c a t i o n s for F O R T R A N m a y h a v e had on o t h e r p r o j e c t s in 1 9 5 4 - 5 5 - 5 6 , t h a t our p l a n s w e r e w e l l a d v a n c e d a n d q u i t e f i r m by the end of 1954 and b e f o r e w e h a d c o n t a c t or k n o w l e d g e of t h o s e o t h e r p r o jects. Our s p e c i f i c a t i o n s w e r e n o t a f f e c t e d by t h e m in a n y s i g n i f i c a n t w a y as far as I am aware, e v e n t h o u g h some w e r e o p e r a t i n g b e f o r e F O R T R A N w a s (since t h e y w e r e p r i m a r i l y i n t e r e s t e d in p r o v i d i n g an i n p u t lang u a g e r a t h e r t h a n in o p t i m i z a t i o n , t h e i r t a s k w a s c o n s i d e r a b l y s i m p l e r t h a n ours). 3.

The

construction

of the

compiler.

T h e F O R T R A N c o m p i l e r (or " t r a n s l a t o r " as w e c a l l e d it then) w a s b e g u n in e a r l y 1955, a l t h o u g h a lot of w o r k on v a r i o u s s c h e m e s w h i c h w o u l d be u s e d in it h a d b e e n d o n e in 1954; e.g., H e r r i c k had d o n e a lot of t r i a l p r o g r a m m i n g to t e s t o u t o u r l a n g u a g e and w e h a d w o r k e d o u t the b a s i c sort of m a c h i n e

170

p r o g r a m s w h i c h w e w a n t e d the c o m p i l e r to g e n e r a t e for v a r i o u s s o u r c e l a n g u a g e p h r a s e s ; Z i l l e r and I h a d w o r k e d o u t a b a s i c s c h e m e for t r a n s l a t i n g a r i t h m e t i c e x p r e s sions.

the a d d r e s s of the p r e c e d i n g r e f e r e n c e to the a r r a y A w h e n e v e r I and J a r e c h a n g i n g linearly. To e m p l o y this far m o r e e f f i c i e n t m e t h o d s e c t i o n 2 h a d to d e t e r m i n e w h e n the s u r r o u n d i n g p r o g r a m was c h a n g i n g I and J linearly.

B u t the real w o r k on the c o m p i l e r g o t u n d e r w a y in our t h i r d l o c a t i o n o n the f i f t h f l o o r of 15 E a s t 56th Street. By the m i d d l e of F e b r u a r y t h r e e s e p a r a t e e f f o r t s w e r e underway. The f i r s t two of t h e s e c o n c e r n e d s e c t i o n s I and 2 of the c o m p i l e r , and the t h i r d c o n c e r n e d the input, o u t p u t and ass e m b l y p r o g r a m s w e w e r e g o i n g to n e e d (see below). We b e l i e v e d t h e n t h a t t h e s e e f f o r t s w o u l d p r o d u c e m o s t of the c o m p i l e r .

Thus one p r o b l e m w a s t h a t of d i s t i n g u i s h ing b e t w e e n , on the o n e hand, r e f e r e n c e s to an a r r a y e l e m e n t w h i c h the t r a n s l a t o r m i g h t t r e a t by i n c r e m e n t i n g the a d 4 r e s s u s e d for a p r e v i o u s r e f e r e n c e , and t h o s e a r r a y r e f e r e n c e s , o n the o t h e r hand, w h i c h w o u l d req u i r e an a d d r e s s c a l c u l a t i o n s t a r t i n g f r o m s c r a t c h w i t h the c u r r e n t v a l u e s of the subscripts.

(The e n t i r e p r o j e c t w a s c a r r i e d on by a l o o s e c o o p e r a t i o n b e t w e e n a u t o n o m o u s , sepa r a t e g r o u p s of one, two, or t h r e e people; each g r o u p was r e s p o n s i b l e for a " s e c t i o n " of the c o m p i l e r ; e a c h g r o u p g r a d u a l l y d e v e l o p e d and a g r e e d u p o n its own i n p u t and output s p e c i f i c a t i o n s w i t h the g r o u p s for neighboring sections; each group invented and p r o g r a m m e d the n e c e s s a r y t e c h n i q u e s for d o i n g its a s s i g n e d job.) S e c t i o n I was to r e a d the e n t i r e s o u r c e p r o g r a m , c o m p i l e w h a t i n s t r u c t i o n s it could, and fi]e all the r e s t of the i n f o r m a t i o n from the s o u r c e p r o g r a m in a p p r o p r i a t e tables'. Thus the c o m p i l e r w a s "one pass" in the s e n s e that it "saw" the s o u r c e prog r a m o n l y once. Herrick was responsible for c r e a t i n g m o s t of the tables, P e t e r S h e r i d a n (who had r e c e n t l y j o i n e d us) comp i l e d all the a r i t h m e t i c e x p r e s s i o n s , and Roy N u t t c o m p i l e d a n d / o r f i l e d the I/O statements. H e r r i c k , S h e r i d a n and N u t t g o t some h e l p l a t e r on f r o m R. J. B e e b e r and H. Stern, but they w e r e the a r c h i t e c t s of section I and w r o t e m o s t of its code. Sheridan d e v i s e d and i m p l e m e n t e d a n u m b e r of o p t i m i z ing t r a n s f o r m a t i o n s on e x p r e s s i o n s [Sheridan 1959] w h i c h s o m e t i m e s r a d i c a l l y a l t e r e d t h e m (of c o u r s e w i t h o u t c h a n g i n g t h e i r m e a n i n g ) . Nutt transformed the I/O "lists of q u a n t i t i e s " into n e s t s of DO s t a t e m e n t s w h i c h w e r e then t r e a t e d by the r e g u l a r m e c h a n i s m s of the c o m p i l e r . The r e s t of the I/O i n f o r m a t i o n he f i l e d for l a t e r t r e a t m e n t in section 6, the a s s e m b l e r s e c t i o n . (For f u r t h e r d e t a i l s a b o u t h o w the v a r i o u s s e c t i o n s of the c o m p i l e r w o r k e d see [Backus et al. 1957] .) U s i n g the i n f o r m a t i o n t h a t w a s f i l e d in s e c t i o n I, s e c t i o n 2 f a c e d a c o m p l e t e l y n e w k i n d of p r o b l e m ; it was r e q u i r e d to ana l y z e the e n t i r e s t r u c t u r e of the p r o g r a m i n o r d e r to g e n e r a t e o p t i m a l c o d e f r o m DO s t a t e m e n t s and r e f e r e n c e s to s u b s c r i p t e d variables. The s i m p l e s t w a y to e f f e c t a r e f e r e n c e to A(I,J) is to e v a l u a t e an exp r e s s i o n i n v o l v i n g the a d d r e s s of A ( I , 1 ) , I, and K×J, w h e r e K is the l e n g t h of a c o l umn (when A is s t o r e d c o l u m n - w i s e ) . B u t this calculation, w i t h its m u l t i p l i c a t i o n , is m u c h less e f f i c i e n t than the w a y m o s t h a n d c o d e d p r o g r a m s e f f e c t a r e f e r e n c e to A ( I , J ) , n a m e l y , by a d d i n g an a p p r o p r i a t e c o n s t a n t to

171

It was d e c i d e d that it was n o t p r a c t i c a l to t r a c k d o w n and i d e n t i f y l i n e a r c h a n g e s in s u b s c r i p t s r e s u l t i n g from a s s i g n m e n t statements. Thus the sole c r i t e r i o n for l i n e a r c h a n g e s , and h e n c e for e f f i c i e n t h a n d l i n g of a r r a y r e f e r e n c e s , w a s to be that the s u b s c r i p t s i n v o l v e d w e r e b e i n g c o n t r o l l e d by DO s t a t e m e n t s . D e s p i t e this s i m p l i f y i n g a s s u m p t i o n , the n u m b e r of c a s e s that s e c t i o n 2 had to a n a l y z e in o r d e r to p r o d u c e o p t i m a l or n e a r - o p t i m a l c o d e was v e r y large. (The n u m b e r of such c a s e s inc r e a s e d e x p o n e n t i a l l y w i t h the n u m b e r of s u b s c r i p t s ; this w a s a p r i m e f a c t o r in o u r d e c i s i o n to l i m i t t h e m to three; the fact t h a t the 704 had o n l y t h r e e i n d e x r e g i s t e r s was n o t a factor.) It is b e y o n d the s c o p e of this p a p e r to go into the d e t a i l s of the a n a l y s i s w h i c h s e c t i o n 2 c a r r i e d out. It w i l l s u f f i c e to say t h a t it p r o d u c e d code of s u c h e f f i c i e n cy that its o u t p u t w o u l d s t a r t l e the p r o g r a m m e r s w h o s t u d i e d it. It m o v e d c o d e o u t of l o o p s w h e r e t h a t was p o s s i b l e ; it t o o k a d v a n t a g e of the d i f f e r e n c e s b e t w e e n r o w w i s e and c o l u m n - w i s e scans; it took n o t e of s p e c i a l c a s e s to o p t i m i z e e v e n the e x i t s from loops. The d e g r e e of o p t i m i z a t i o n p e r f o r m e d by s e c t i o n 2 in its t r e a t m e n t of i n d e x i n g , a r r a y r e f e r e n c e s , and l o o p s was not equalled again until optimizing compilers b e g a n to a p p e a r in the m i d d l e and l a t e sixties. The a r c h i t e c t u r e and all the t e c h n i q u e s e m p l o y e d in s e c t i o n 2 w e r e i n v e n t e d by Robert A. N e l s o n and I r v i n g Ziller. They planned and p r o g r a m m e d the e n t i r e section. O r i g i n a l l y it was t h e i r i n t e n t i o n to p r o d u c e the c o m p l e t e c o d e for t h e i r area, i n c l u d i n g the c h o i c e of the i n d e x r e g i s t e r s to be u s e d (the 704 had t h r e e i n d e x r e g i s t e r s ) . W h e n t h e y s t a r t e d l o o k i n g at t h a t p r o b l e m it r a p i d l y b e c a m e c l e a r t h a t it w a s n o t going to be e a s y to t r e a t it o p t i m a l l y . At that p o i n t I p r o p o s e d t h a t they s h o u l d p r o d u c e a p r o g r a m for a 704 w i t h an u n l i m i t e d n u m b e r of i n d e x r e g i s t e r s , and t h a t l a t e r s e c t i o n s w o u l d a n a l y z e the f r e q u e n c y of exe c u t i o n of v a r i o u s p a r t s of the p r o g r a m (by a M o n t e C a r l o s i m u l a t i o n of its e x e c u tion) and t h e n m a k e i n d e x r e g i s t e r a s s i g n m e n t s so as to m i n i m i z e the t r a n s f e r s of i t e m s b e t w e e n the s t o r e and the i n d e x r e g -

isters.

fully ging.

This p r o p o s a l g a v e r i s e to two n e w sect ion s of the c o m p i l e r w h i c h we h a d n o t ant i c i p a t e d , s e c t i o n s 4 and 5 ( s e c t i o n 3 w a s a d d e d s t i l l l a t e r to c o n v e r t the o u t p u t of s e c t i o n s I and 2 to the f o r m r e q u i r e d for s e c t i o n s 4, 5, and 6). In the fall of 1955 L o i s M i t c h e l l H a i b t j o i n e d our g r o u p to p l a n and p r o g r a m s e c t i o n 4, w h i c h w a s to a n a l y z e the f l o w of a p r o g r a m p r o d u c e d by s e c t i o n s I and 2, d i v i d e it into "basic blocks" (which c o n t a i n e d no b r a n c h i n g ) , do a M o n t e C a r l o (statistical) a n a l y s i s of the e x p e c t e d f r e q u e n c y of e x e c u t i o n of b a s i c b l o c k s - - b y s i m u l a t i n g the b e h a v i o r of the p r o g r a m and k e e p i n g c o u n t s of the use of e a c h b l o c k - - u s i n g i n f o r m a t i o n f r o m DO s t a t e m e n t s and F R E Q U E N C Y s t a t e m e n t s , a n d c o l l e c t i n f o r m a t i o n a b o u t i n d e x r e g i s t e r u s a g e (for m o r e d e t a i l s see [Backus et al. 1957; C o c k e and S c h w a r t z 1970 p.511]) . S e c t i o n 5 w o u l d t h e n do the a c t u a l t r a n s f o r m a t i o n of the p r o g r a m f r o m o n e h a v i n g an u n l i m i t e d n u m b e r of i n d e x r e g i s t e r s to o n e h a v i n g o n l y three. A g a i n , the s e c t i o n w a s e n t i r e l y p l a n n e d and p r o g r a m m e d by Haibt.

and

took

charge

of

its

final

debug-

T h e f i n a l s e c t i o n of the c o m p i l e r , sect i o n 6, a s s e m b l e d the f i n a l p r o g r a m into a r e l o c a t a b l e b i n a r y p r o g r a m (it c o u l d also p r o d u c e a s y m b o l i c p r o g r a m in SAP, the S H A R E A s s e m b l y P r o g r a m for the 704). It p r o d u c e d a s t o r a g e m a p of the p r o g r a m and d a t a t h a t w a s a c o m p a c t s u m m a r y of the F O R TRAN output. Of c o u r s e it a l s o o b t a i n e d the n e c e s s a r y l i b r a r y p r o g r a m s for i n c l u s i o n in the o b j e c t p r o g r a m , i n c l u d i n g t h o s e req u i r e d to i n t e r p r e t F O R M A T s t a t e m e n t s and perform input-output operations. Taking a d v a n t a g e of the s p e c i a l f e a t u r e s of the p r o g r a m s it a s s e m b l e d , this a s s e m b l e r w a s a b o u t ten t i m e s f a s t e r t h a n SAP. It w a s d e s i g n e d and p r o g r a m m e d by Roy N u t t , w h o a l s o w r o t e all the I/O p r o g r a m s and the rel o c a t i n g b i n a r y l o a d e r for l o a d i n g o b j e c t programs. By the s u m m e r of 1956 l a r g e p a r t s of the system were working. S e c t i o n s I, 2, and 3 c o u l d p r o d u c e w o r k a b l e c o d e p r o v i d e d no more than three index registers were needed. A n u m b e r of t e s t p r o g r a m s w e r e c o m p i l e d and run at this time. N u t t t o o k p a r t of the s y s t e m to U n i t e d A i r c r a f t ( s e c t i o n s I, 2, and 3 and the p a r t of s e c t i o n 6 w h i c h p r o d u c e d SAP o u t p u t ) . T h i s p a r t of the s y s t e m w a s p r o d u c t i v e t h e r e f r o m the s u m m e r of 1956 u n t i l the c o m p l e t e s y s t e m w a s a v a i l a b l e in e a r l y 1957.

S e c t i o n 5 w a s p l a n n e d and p r o g r a m m e d by S h e l d o n Best, w h o w a s l o a n e d to our g r o u p by a g r e e m e n t w i t h his e m p l o y e r , C h a r l e s W. A d a m s , at the D i g i t a l C o m p u t e r L a b o r a t o r y at MIT; d u r i n g his s t a y w i t h us B e s t w a s a t e m p o r a r y IBM e m p l o y e e . S t a r t i n g in the e a r l y f a l l of 1955, he d e s i g n e d w h a t t u r n e d o u t to be, a l o n g w i t h s e c t i o n 2, o n e of the m o s t i n t r i c a t e and c o m p l e x s e c t i o n s of the c o m p i l e r , o n e w h i c h h a d p e r h a p s m o r e inf l u e n c e on the m e t h o d s u s e d in l a t e r comp i l e r s t h a n any o t h e r p a r t of the F O R T R A N compiler. (For a d i s c u s s i o n of his t ec h n i q u e s see [Cocke and S c h w a r t z 1970 pp. 510515].) It is i m p o s s i b l e to d e s c r i b e his r e g i s t e r a l l o c a t i o n m e t h o d here; it s u f f i c e s to say t h a t it w a s to b e c o m e the b a s i s for m u c h s u b s e q u e n t w o r k and p r o d u c e d code w h i c h w a s v e r y d i f f i c u l t to i m p r o v e .

F r o m late s p r i n g of 1956 to e a r l y 1957 the p a c e of d e b u g g i n g w a s i n t e n s e ; o f t e n w e w o u l d r e n t r o o m s in the L a n g d o n H o t e l (which d i s a p p e a r e d long ago) on 56th S t r e e t , s l e e p t h e r e a l i t t l e d u r i n g the d a y and t h e n s t a y up all n i g h t to g e t as m u c h u s e of the c o m p u t e r (in the h e a d q u a r t e r s a n n e x on 57th Street) as p o s s i b l e . It w a s an e x c i t i n g p e r i o d ; w h e n l a t e r on w e b e g a n to g e t f r a g m e n t s of c o m p i l e d p r o g r a m s out of the s y s t e m , w e w e r e o f t e n ast o n i s h e d at the s u r p r i s i n g t r a n s f o r m a t i o n s in the i n d e x i n g o p e r a t i o n s and in the arr a n g e m e n t of the c o m p u t a t i o n w h i c h the comp i l e r m a d e , c h a n g e s w h i c h m a d e the o b j e c t p r o g r a m e f f i c i e n t b u t w h i c h we w o u l d n o t h a v e t h o u g h t to m a k e as p r o g r a m m e r s o u r s e l v e s (even t h o u g h , of c o u r s e , N e l s o n or Z i l l e r c o u l d f i g u r e o u t h o w the i n d e x i n g w o r k e d , S h e r i d a n c o u l d e x p l a i n h o w an exp r e s s i o n had b e e n o p t i m i z e d b e y o n d r e c o g n i t i o n , and G o l d b e r g or S a y r e c o u l d tell us h o w s e c t i o n 5 h a d g e n e r a t e d a d d i t i o n a l indexing operations). T r a n s f e r s of c o n t r o l a p p e a r e d w h i c h c o r r e s p o n d e d to no s o u r c e s t a t e m e n t , e x p r e s s i o n s w e r e r a d i c a l l y rea r r a n g e d , and the same DO s t a t e m e n t m i g h t p r o d u c e no i n s t r u c t i o n s in the o b j e c t p r o g r a m in o n e c o n t e x t , and in a n o t h e r it w o u l d p r o d u c e m a n y i n s t r u c t i o n s in d i f f e r ent p l a c e s in the p r o g r a m .

A l t h o u g h I b e l i e v e that no p r o v a b l y o p t i m a l r e g i s t e r a l l o c a t i o n a l g o r i t h m is k n o w n for g e n e r a l p r o g r a m s w i t h loops, etc., e m p i r i c a l l y B e s t ' s 1 9 5 5 - 5 6 p r o c e d u r e app e a r e d to be o p t i m a l . For s t r a i g h t - l i n e c o d e B e s t ' s r e p l a c e m e n t p o l i c y w a s the same as t h a t u s e d in B e l a d y ' s M I N a l g o r i t h m , w h i c h B e l a d y p r o v e d to be o p t i m a l [Belady 1965]. Although Best did not publish a f o r m a l p r o o f , he h a d c o n v i n c i n g a r g u m e n t s for the o p t i m a l i t y of his p o l i c y in 1955. L a t e in 1955 it w a s r e c o g n i z e d t h a t y e t a n o t h e r s e c t i o n , s e c t i o n 3, w a s n e e d e d . T h i s s e c t i o n m e r g e d the o u t p u t s of the prec e d i n g s e c t i o n s into a s i n g l e u n i f o r m 704 p r o g r a m w h i c h c o u l d r e f e r to any n u m b e r of index registers. It w a s p l a n n e d and p r o g r a m m e d by R i c h a r d G o l d b e r g , a m a t h e m a t i c i a n w h o j o i n e d us in N o v e m b e r 1955. Also, late in 1956, a f t e r B e s t h a d r e t u r n e d to M I T a n d d u r i n g the d e b u g g i n g of the system, s e c t i o n 5 was t a k e n o v e r by G o l d b e r g and D a v i d S a y r e (see b e l o w ) , w h o d i a g r a m m e d it c a r e -

By the s u m m e r of 1956 w h a t a p p e a r e d to be the i m m i n e n t c o m p l e t i o n of the p r o j e c t s t a r t e d us w o r r y i n g (for p e r h a p s the f i r s t

172

time) a b o u t d o c u m e n t a t i o n . D a v i d Sayre, a c r y s t a l l o g r a p h e r w h o had j o i n e d us in the s p r i n g (he h a d e a r l i e r c o n s u l t e d w i t h B e s t on the d e s i g n of s e c t i o n 5 and had l a t e r b e g u n s e r v i n g as s e c o n d - i n - c o m m a n d of w h a t w a s n o w the '~Programming R e s e a r c h D e p a r t m e n t " ) took up the task of w r i t i n g the P r o g r a m m e r ' s R e f e r e n c e M a n u a l [IBM 1956]. It a p p e a r e d in a g l o s s y cover, h a n d s o m e l y p r i n t e d , w i t h the d a t e O c t o b e r 15, 1956. It s t o o d for some time as a u n i q u e e x a m p l e of a m a n u a l for a p r o g r a m m i n g l a n g u a g e (perhaps it s t i l l does): it h a d w i d e m a r g i n s , y e t was o n l y 51 p a g e s long. Its d e s c r i p t i o n of the F O R T R A N l a n g u a g e , e x c l u s i v e of i n p u t - o u t p u t s t a t e m e n t s , w a s 21 pages; the I/O d e s c r i p t i o n o c c u p i e d a n o t h e r 11 pages; the r e s t of it was e x a m p l e s and d e t a i l s a b o u t a r i t h m e t i c , t a b l e s , etc.. It g a v e an e l e g a n t r e c u r s i v e d e f i n i t i o n of e x p r e s s i o n s (as g i v e n b y S h e r idan), and c o n c i s e , c l e a r d e s c r i p t i o n s , w i t h e x a m p l e s , of e a c h s t a t e m e n t type, of w h i c h t h e r e w e r e 32, m o s t l y m a c h i n e d e p e n d e n t items like S E N S E LIGHT, IF D I V I D E CHECK, PUNCH, R E A D DRUM, and so on. (For e x a m p l e s of its s t y l e see figs. I, 2, and 3.)

time at n i g h t on t h e i r 704 to h e l p us in our m a d r u s h to d i s t r i b u t e the system. Up to this p o i n t t h e r e h a d b e e n r e l a t i v e l y l i t t l e i n t e r e s t f r o m 704 i n s t a b l a t i o n s (with the e x c e p t i o n of R a m s h a w ' s U n i t e d A i r c r a f t shop, H a r r y C a n t r e l l ' s GE i n s t a l l a t i o n in S c h e n e c t a d y , and S i d n e y F e r n b a c h ' s L i v e r m o r e o p e r a t i o n ) , b u t n o w t h a t the full system was b e g i n n i n g to g e n e r a t e o b j e c t p r o grams, i n t e r e s t p i c k e d up in a n u m b e r of places. S o m e t i m e in e a r l y A p r i l 1957 we felt the s y s t e m w a s s u f f i c i e n t l y b u g - f r e e to d i s t r i b ute to all 704 i n s t a l l a t i o n s . S a y r e and Grace Mitchell (see below) s t a r t e d to p u n c h out the b i n a r y d e c k s of the system, e a c h of a b o u t 2,000 cards, w i t h the i n t e n t i o n to m a k e 30 or 40 d e c k s for d i s t r i b u t i o n . This p r o c e s s was so e r r o r - p r o n e t h a t they h a d to g i v e up a f t e r s p e n d i n g an e n t i r e n i g h t in p r o d u c i n g o n l y one or two decks. ( A p p a r e n t l y one of t h o s e d e c k s was sent, w i t h o u t any i d e n t i f i c a t i o n or d i r e c t i o n s , to the W e s t i n g h o u s e B e t t i s i n s t a l l a t i o n , w h e r e a p u z z l e d g r o u p h e a d e d by H e r b e r t S. B r i g h t , s u s p e c t i n g t h a t it m i g h t be the l o n g - a w a i t e d F O R T R A N deck, p r o c e e d e d , ent i r e l y by g u e s s w o r k , to g e t it to c o m p i l e a test p r o g r a m - - a f t e r a d i a g n o s t i c p r i n t out noting that a comma was missing in a s p e c i f i c s t a t e m e n t ! This p r o g r a m then p r i n t e d 28 p a g e s of c o r r e c t r e s u l t s - - w i t h a few F O R M A T errors. The date: A p r i l 20, 1957. A n a m u s i n g a c c o u n t of this i n c i d e n t by B r i g h t is in C o m p u t e r s and A u t o m a t i o n [Bright 1971].)

One f e a t u r e of F O R T R A N I is m i s s i n g f r o m the P r o g r a m m e r ' s R e f e r e n c e M a n u a l , n o t f r o m an o v e r s i g h t of S a y r e ' s , b u t b e c a u s e it w a s a d d e d to the s y s t e m a f t e r the m a n u a l was w r i t t e n and b e f o r e the s y s t e m w a s d i s t r i b uted. This f e a t u r e was the a b i l i t y to define a f u n c t i o n by a " f u n c t i o n s t a t e m e n t " . T h e s e s t a t e m e n t s h a d to p r e c e d e the r e s t of the p r o g r a m . They looked like assignment s t a t e m e n t s , w i t h the d e f i n e d f u n c t i o n and d u m m y a r g u m e n t s on the left and an e x p r e s sion i n v o l v i n g t h o s e a r g u m e n t s on the right. T h e y are d e s c r i b e d in the a d d e n d a to the P r o g r a m m e r ' s R e f e r e n c e M a n u a l [Addenda 1957] w h i c h we sent on F e b r u a r y 8, 1957 to J o h n G r e e n s t a d t , w h o was in c h a r g e of I B M ' s facility for d i s t r i b u t i n g i n f o r m a t i o n to SHARE. T h e y are a l s o d e s c r i b e d in all subs e q u e n t m a t e r i a l o n F O R T R A N I.

A f t e r f a i l i n g to p r o d u c e b i n a r y decks, S a y r e d e v i s e d and p r o g r a m m e d the s i m p l e e d i t o r and l o a d e r that m a d e it p o s s i b l e to d i s t r i b u t e and u p d a t e the s y s t e m f r o m m a g n e t i c tapes; this a r r a n g e m e n t s e r v e d as the m e c h a n i s m for c r e a t i n g n e w s y s t e m t a p e s from a m a s t e r tape and the b i n a r y c o r r e c t i o n c a r d s w h i c h our g r o u p w o u l d g e n e r a t e in l a r g e n u m b e r s d u r i n g the long f i e l d d e b u g g i n g and m a i n t e n a n c e p e r i o d w h i c h f o l l o w e d distribution.

The n e x t d o c u m e n t a t i o n t a s k we set ours e l v e s w a s to w r i t e a p a p e r d e s c r i b i n g the F O R T R A N l a n g u a g e and the t r a n s l a t o r p r o g r a m . The r e s u l t was a p a p e r e n t i t l e d "The F O R T R A N a u t o m a t i c c o d i n g s y s t e m " [Backus et al. 1957] w h i c h we p r e s e n t e d at the W e s t e r n J o i n t C o m p u t e r C o n f e r e n c e in Los A n g e l e s in F e b r u a r y 1957. I h a v e m e n t i o n e d all of the t h i r t e e n a u t h o r s of t h a t p a p e r in the prec e d i n g n a r r a t i v e e x c e p t one: R o b e r t A. Hughes. He was e m p l o y e d by the L i v e r m o r e R a d i a t i o n L a b o r a t o r y ; by a r r a n g e m e n t w i t h S i d n e y F e r n b a c h , he v i s i t e d us for two or t h r e e m o n t h s in the s u m m e r of 1956 to h e l p us d o c u m e n t the system. (The a u t h o r s of t h a t p a p e r were: J. W. B a c k u s , R. J. B e e b e r , S. Best, R. G o l d b e r g , L. M. Haibt, H. L. H e r r i c k , R. A. H u g h e s , R. A. N e l s o n , R. Nutt, D. Sayre, P. B. S h e r i d a n , H. Stern, I. Ziller.)

W i t h the d i s t r i b u t i o n of the s y s t e m tapes went a "Preliminary Operator's Manual" [ O p e r a t o r ' s M a n u a l 1957] d a t e d A p r i l 8, 1957. It d e s c r i b e s h o w to use the tape editor and h o w to m a i n t a i n the l i b r a r y of functions. F i v e p a g e s of such g e n e r a l ins t r u c t i o n s are f o l l o w e d by 32 p a g e s of err o r stops; m a n y of t h e s e say " s o u r c e p r o g r a m error, g e t off m a c h i n e , c o r r e c t form u l a in q u e s t i o n and r e s t a r t p r o b l e m " and then, for e x a m p l e (stop 3624) " n o n - z e r o l e v e l r e d u c t i o n due to i n s u f f i c i e n t or red u n d a n t p a r e n t h e s e s in a r i t h m e t i c or IFtype f o r m u l a " . S h o r t l y a f t e r the d i s t r i b u t i o n of the s y s t e m we d i s t r i b u t e d - - o n e c o p y per i n s t a l l a t i o n - - w h a t was f o n d l y k n o w n as the "Tome", the c o m p l e t e s y m b o l i c l i s t i n g of the e n t i r e c o m p i l e r plus o t h e r s y s t e m and d i a g n o s t i c i n f o r m a t i o n , an 11" by 15" v o l u m e a b o u t four or five i n c h e s thick.

At a b o u t the time of the W e s t e r n J o i n t C o m p u t e r C o n f e r e n c e w e s p e n t some t i m e in Los A n g e l e s s t i l l f r a n t i c a l l y d e b u g g i n g the system. N o r t h A m e r i c a n A v i a t i o n g a v e us

173

Subscripts. GENERAL

FORM

EXAMPLES

Let v represent any fixed point variable and c (or c') any-unsigned fixed point constant. Then a subscript is an expression of one of the forms:

I 3 MU+2 MU-2 5*J 5"J+2 5"J-2

V C V+C or V--C c*v c* V + C ' or c*v--c'

T h e symbol • denotes multiplication. T h e variable v must not itself b e subscripted.

Subscripted Variables. GENERAL

FORM

EXAMPLES

A fixed or floating point variable

A(I)

followed, by parentheses enclosing 1, 2, or 3 subscripts separated by commas.

K(3) BEIA(5*.I-2, K + 2,L)

For each wlriable that appears in subscripted form the size of the array (i.e. the maxinuun wdues which its subscripts can attain) must be stated in a D I M E N SION statement (see Chapter 6) preceding the first appearance of the variable. The m i n i m u m value which a subscript may assume in the object p r o g r a m is + 1.

A rrangement o / A rrays in Storage. A 2-dimensional array A will, in the object program, be stored sequentially in the order A1,1, A2.1, • . . . . .

Am,l, A],z, A2,2, • . . . . .

Am,2, • . . . . . . . .

Am,,. Thus

it is stored "columnwise", with the first of its subscripts varying most rapidly, and the last varying least rapidly. The same is true of 3-dimensional arrays. l-dimensional arrays are of course simply stored sequentially. All arrays are stored backwards in storage; i.e. the above sequence is in the order of decreasing absolute location.

II

Figure

I:

O r i g i n a l F O R T R A N Manual,

174

Page

11

A n y such routine will be compiled into the object program as a closed subroutine. In the section on Writing Subroutines for the Master Tape in Chapter 7 are given the specifications which any such routine must meet.

Expressions

A n expression is any sequence of constants, w~riables (subscripted or not subscripted), and functions, separated by operation symbols, commas, and parentheses so as to form a meaningful mattmmatical expression. However, one special restriction does exist. A FORTRAN expression may be either a fixed or a lloating point expression, but it must not be a mixed expression. This does not mean that a floating point quantity can not appear in a fixed point expression, or vice versa, but rather that a quantity of one mode can appear in an expression of the other mode only in certain ways. Brielty, a floating point quantity can appear in a fixed point expression only as an a r g u m e n t of a function; a fixed point quantity can appear in a floating point expression only as an argument of a function, or as a subscript, or as an exponent.

Formal Rules /or Forming Expressions.

By repeated use of the following

rules, all permissible expressions may be derived. 1. Any fixed point (floating point) constant, variable, or subscripted variable is an expression of the same mode. Thus 3 and I are fixed point expressions, and AI.I'HA and A(I,J,K) are tloating point exprcssi~ms. 2.

If SOMEF is some function of n wLriahles, and if E, F . . . . . . H are a set of n expressions of the correct modes for SOMEF, then SONIEF (E, F, . . . . , H) is an expression of the same mode as SOMEF.

3.

If E is an expression, and if its lirst character is not -t or --, then t- E and --E are expressions of the same mode as E. Thus - A is an expression, but -k-A is not.

4.

If E is an expression, then (E) is an expression of the same mode as E. Thus (A), ( ( A ) ) , ( ( ( A ) ) ) , . c t c . are expressions.

5.

If E and F are expressions of the same mode, and if the first character of F is not + o r - - , then

E+F E-F E* F [/F are expressions of the same mode. Thus A - - + B and A / 4 B are not expressions. The characters + , - , *, and / denote addition, subtraction, multiplication, and division. 14

Figure 2: Original FORTRAN Manual, Page 14 175

STOP

GENERAL FORM

EXAMPLES

"STOP" or "STOP n" where n is an

STOP

unsigned octal fixed point constant.

STOP 77777

This statement causes the m a c h i n e to H A L T in such a way that pressing the S T A R T button has no effect. Therefore, in c o n t r a s t to the P A U S E , it is used where a g e t - o i l - t h e - m a c h i n e stop, r a t h e r than a t e m p o r a r y stop, is desired. T h e octal n u m b e r n is d i s p l a y e d on the 704 console in the a d d r e s s field of the storage register. ( I f n is not stated it is taken to be 0.)

DO GENERAL FORM

EXAMPLES

"DO n i = m,, m2" or "DO n i = m,, m2, m3"

DO 301 = 1,10

where n is a statement number, i is a

DO301 = 1, M, 3

non-subscripted fixed point variable, and m,, m2, ma are each either an unsigned fixed point constant or a non-subscripted fixed point variable. If ma is not stated it is taken to be 1.

T h e D O s t a t e m e n t is a c o m m a n d to " D O the statements which follow, to and including the s t a t e m e n t with s t a t e m e n t n u m b e r n, repeatedly, the first time with i = m~ a n d with i increased by mz for each succeeding time; after they have been done with i equal to the highest of this sequence of values which does not e x c e e d m., let control reach the s t a t e m e n t following the s t a t e m e n t with statem c n t n u m b e r n". T h e range of a D O is the set of statements which will be e x e c u t e d rep e a t e d l y ; it is the sequence of consecutive statements i m m e d i a t e l y following the D O , to a n d including the s t a t e m e n t n u m b e r e d n. T h e index of a D O is the fixed p o i n t variable i, which is c o n t r o l l e d by the D O in such a way that its value begins at m l a n d is i n c r e a s e d each time by ma until it is a b o u t to exceed m > T h r o u g h o u t the range it is available for c o m putation, either as an o r d i n a r y fixed p o i n t variable o r as the variable of a subscript. D u r i n g the last execution of the range, the D O is said to be satisfied. Suppose, for e x a m p l e , that c o n t r o l has r e a c h e d s t a t e m e n t

10 of the

program 10

DO 11 I =

11

A(I) =

1, 10

I*N(I)

12

20 Figure

3: Original

FORTRAN Manual,

176

Page

20

d i a g n o s t i c s y s t e m and d e s c r i b e s the n e w "subroutine definition" and END statements, plus some o t h e r s w h i c h w e r e n o t i m p l e m e n t e d . It d e s c r i b e s h o w s y m b o l i c i n f o r m a t i o n is r e t a i n e d in the r e l o c a t a b l e b i n a r y f o r m of a s u b r o u t i n e so t h a t the " b i n a r y s y m b o l i c s u b r o u t i n e [BSS] l o a d e r " can i m p l e m e n t refe r e n c e s to s e p a r a t e l y c o m p i l e d s u b r o u t i n e s . It d e s c r i b e s n e w p r o l o g u e s for t h e s e subr o u t i n e s and p o i n t s o u t that m i x t u r e s of F O R T R A N - c o d e d and a s s e m b l y - c o d e d r e l o c a t a b l e b i n a r y p r o g r a m s c o u l d be l o a d e d and run t o g e t h e r . It d o e s n o t d i s c u s s the F U N C T I O N s t a t e m e n t t h a t w a s a l s o a v a i l a b l e in F O R T R A N II. F O R T R A N II w a s d e s i g n e d m o s t l y by N e l s o n , Ziller, and m y s e l f . Mitchell p r o g r a m m e d the m a j o r i t y of n e w c o d e for F O R T R A N II (with the m o s t u n u s u a l f e a t u r e that she d e l i v e r e d it a h e a d of s c h e d u l e ) . She w a s a i d e d in this b y B e r n y c e B r a d y and L e R o y May. S h e r i d a n p l a n n e d and m a d e the n e c e s s a r y c h a n g e s in his p a r t of s e c t i o n I; N u t t did the same for s e c t i o n 6. FORTRAN II w a s d i s t r i b u t e d in the s p r i n g of 1958.

The p r o p r i e t o r s of the six s e c t i o n s w e r e k e p t b u s y t r a c k i n g d o w n b u g s e l i c i t e d by our c u s t o m e r s ' u s e of F O R T R A N u n t i l the late s u m m e r of 1957. Hal S t e r n s e r v e d as the coo r d i n a t o r of the f i e l d d e b u g g i n g and m a i n t e n a n c e effort; he r e c e i v e d a s t r e a m of t e l e g r a m s , m a i l and p h o n e c a l l s f r o m all o v e r the c o u n t r y and d i s t r i b u t e d the inc o m i n g p r o b l e m s to the a p p r o p r i a t e m e m b e r s of our g r o u p to t r a c k d o w n the e r r o r s and g e n e r a t e c o r r e c t i o n cards, w h i c h he then d i s t r i b u t e d to e v e r y i n s t a l l a t i o n . In the s p r i n g of 1957 G r a c e E. M i t c h e l l j o i n e d o u r g r o u p to w r i t e the P r o g r a m m e r ' s P r i m e r [IBM 1957] for F O R T R A N . The P r i m e r w a s d i v i d e d into t h r e e s e c t i o n s ; e a c h d e s c r i b e d s u c c e s s i v e l y l a r g e r s u b s e t s of the l a n g u a g e a c c o m p a n i e d by m a n y e x a m p l e p r o grams. The f i r s t e d i t i o n of the P r i m e r was i s s u e d in the late fall or w i n t e r of 1957; a s l i g h t l y r e v i s e d e d i t i o n a p p e a r e d in March 1958. M i t c h e l l p l a n n e d and w r o t e the 6 4 - p a g e P r i m e r w i t h some c o n s u l t a t i o n w i t h the r e s t of the group; she l a t e r programmed m o s t of the e x t e n s i v e c h a n g e s in the s y s t e m w h i c h r e s u l t e d in F O R T R A N II (see below).

5.

A r e p o r t on F O R T R A N u s a g e in N o v e m b e r 1958 [Backus 1958] says that "a s u r v e y in A p r i l [1958] of t w e n t y - s i x 704 i n s t a l l a t i o n s i n d i c a t e s t h a t o v e r half of t h e m use F O R T R A N [I] for m o r e than h a l f of t h e i r p r o b l e m s . M a n y use it for 80~ or m o r e of t h e i r w o r k . . . and a l m o s t all use it for some of t h e i r work." By the fall of 1958 t h e r e w e r e some 60 i n s t a l l a t i o n s w i t h a b o u t 66 704s, and "... m o r e t h a n h a l f the m a c h i n e i n s t r u c tions for t h e s e m a c h i n e s are b e i n g p r o d u c e d by F O R T R A N . SHARE recently designated FORT R A N as the s e c o n d o f f i c i a l m e d i u m for t r a n s m i t t a l of p r o g r a m s [SAP w a s the first]

4.

."

FORTRAN

III

W h i l e F O R T R A N II w a s b e i n g d e v e l o p e d , Z i l l e r w a s d e s i g n i n g an e v e n m o r e a d v a n c e d s y s t e m t h a t he c a l l e d F O R T R A N III. It all o w e d o n e to w r i t e i n t e r m i x e d s y m b o l i c ins t r u c t i o n s and F O R T R A N s t a t e m e n t s . The symb o l i c (704) i n s t r u c t i o n s c o u l d h a v e F O R T R A N v a r i a b l e s (with or w i t h o u t s u b s c r i p t s ) as "addresses". In a d d i t i o n to this m a c h i n e d e p e n d e n t f e a t u r e (which a s s u r e d the d e m i s e of F O R T R A N III a l o n g w i t h t h a t of the 704), it c o n t a i n e d e a r l y v e r s i o n s of a n u m b e r of i m p r o v e m e n t s t h a t w e r e l a t e r to a p p e a r in F O R T R A N IV. It had " B o o l e a n " e x p r e s s i o n s , f u n c t i o n and s u b r o u t i n e n a m e s c o u l d be p a s s e d as a r g u m e n t s , and it had f a c i l i t i e s for h a n d l i n g a l p h a n u m e r i c data, i n c l u d i n g a n e w F O ~ 4 A T c o d e "A" s i m i l a r to c o d e s "I" and "E". This s y s t e m w a s p l a n n e d and p r o g r a m m e d by Z i l l e r w i t h some h e l p f r o m N e l s o n and Nutt. Z i l l e r m a i n t a i n e d it and m a d e it a v a i l a b l e to a b o u t 20 (mostly IBM) i n s t a l lations. It w a s n e v e r d i s t r i b u t e d g e n e r a l ly. It was a c c o m p a n i e d by a b r i e f d e s c r i p tive d o c u m e n t [ A d d i t i o n s to F O R T R A N II 1958]. It b e c a m e a v a i l a b l e on this l i m i t e d s c a l e in the w i n t e r of 1 9 5 8 - 5 9 and was in o p e r a t i o n u n t i l the e a r l y s i x t i e s , in p a r t on the 709 u s i n g the c o m p a t i b i l i t y f e a t u r e (which m a d e the 709 o r d e r code the same as that of the 704).

The P r i m e r had an i m p o r t a n t i n f l u e n c e on the s u b s e q u e n t g r o w t h in the use of the system. I b e l i e v e it was the o n l y a v a i l a b l e s i m p l i f i e d i n s t r u c t i o n m a n u a l (other t h a n r e f e r e n c e m a n u a l s ) u n t i l the l a t e r a p p e a r ance of b o o k s such as [ M c C r a c k e n 1961], [ O r g a n i c k 1963] and m a n y others.

.,

FORTRAN

II

D u r i n g the f i e l d d e b u g g i n g p e r i o d some s h o r t c o m i n g s of the s y s t e m d e s i g n , w h i c h we h a d b e e n a w a r e of e a r l i e r b u t h a d no time to deal with, w e r e c o n s t a n t l y c o m i n g to o u r attention. In the e a r l y fall of 1957 we s t a r t e d to p l a n w a y s of c o r r e c t i n g t h e s e shortcomings; a document dated September 25, 1957 [Proposed S p e c i f i c a t i o n s 1957] c h a r a c t e r i z e s t h e m as (a) a n e e d for b e t t e r d i a g n o s t i c s , c l e a r e r c o m m e n t s a b o u t the n a t u r e of s o u r c e p r o g r a m errors, and (b) the n e e d for s u b r o u t i n e d e f i n i t i o n c a p a b i l ities. "(Although o n e F O R T R A N I d i a g n o s t i c w o u l d p i n p o i n t , in a p r i n t o u t , a m i s s i n g c o m m a in a p a r t i c u l a r s t a t e m e n t , o t h e r s c o u l d be v e r y c r y p t i c . ) This d o c u m e n t is t i t l e d " P r o p o s e d S p e c i f i c a t i o n s for F O R T R A N II for the 704"; it s k e t c h e s a m o r e g e n e r a l

6.

FORTRAN

after

1958;

comments.

By the end of 1958 or e a r l y 1959 the FORTRAN g r o u p (the P r o g r a m m i n g R e s e a r c h D e p a r t m e n t ) , w h i l e s t i l l h e l p i n g w i t h an occasional debugging problem with FORTRAN II, was p r i m a r i l y o c c u p i e d w i t h o t h e r research. A n o t h e r IBM d e p a r t m e n t had long s i n c e t a k e n r e s p o n s i b i l i t y for the F O R T R A N s y s t e m and was r e v i s i n g it in the c o u r s e of p r o d u c i n g a t r a n s l a t o r for the 709 w h i c h u s e d the same p r o c e d u r e s as the 704 F O R T R A N II t r a n s l a t o r . S i n c e m y f r i e n d s and I no l o n g e r h a d r e s p o n s i b i l i t y for F O R T R A N and

177

w e r e b u s y t h i n k i n g a b o u t o t h e r t h i n g s by the end of 1958, t h a t s e e m s like a g o o d p o i n t to b r e a k off this a c c o u n t . There r e m a i n o n l y a f e w c o m m e n t s to be m a d e a b o u t the s u b s e q u e n t d e v e l o p m e n t of F O R T R A N . The m o s t o b v i o u s d e f e c t in F O R T R A N II for m a n y of its u s e r s w a s the t i m e s p e n t in compiling. E v e n t h o u g h the f a c i l i t i e s of F O R T R A N II p e r m i t t e d s e p a r a t e c o m p i l a t i o n of s u b r o u t i n e s and h e n c e e l i m i n a t e d the n e e d to r e c o m p i l e an e n t i r e p r o g r a m at e a c h s t e p in d e b u g g i n g it, n e v e r t h e l e s s c o m p i l e t i m e s w e r e long and, d u r i n g d e b u g g i n g , the c o n s i d e r a b l e time s p e n t in o p t i m i z i n g w a s wasted. I r e p e a t e d l y s u g g e s t e d to t h o s e w h o w e r e in c h a r g e of F O R T R A N t h a t t h e y should now develop a fast compiler and/or i n t e r p r e t e r w i t h o u t any o p t i m i z i n g a t all for use d u r i n g d e b u g g i n g and for s h o r t - r u n jobs. U n f o r t u n a t e l y the d e v e l o p e r s of F O R T R A N IV t h o u g h t t h e y c o u l d h a v e the b e s t of b o t h w o r l d s in a s i n g l e c o m p i l e r , o n e w h i c h was b o t h f a s t and p r o d u c e d o p t i m i z e d code. I w a s u n s u c c e s s f u l in c o n v i n c i n g t h e m t h a t two c o m p i l e r s w o u l d h a v e b e e n far b e t ter t h a n the c o m p r o m i s e w h i c h b e c a m e the o r i g i n a l F O R T R A N IV c o m p i l e r . The latter w a s not n e a r l y as f a s t as l a t e r c o m p i l e r s like W A T F O R [Cress, D i r k s e n a n d G r a h a m 1970] nor did it p r o d u c e as g o o d c o d e as F O R T R A N II. (For m o r e d i s c u s s i o n of l a t e r d e v e l o p m e n t s w i t h F O R T R A N see [Backus and H e i s i n g 196~] .) M y o w n o p i n i o n as to the e f f e c t of F O R T R A N on l a t e r l a n g u a g e s and the c o l l e c t i v e i m p a c t of such l a n g u a g e s on p r o g r a m m i n g g e n e r a l l y is n o t a p o p u l a r o p i n i o n . That v i e w p o i n t is the s u b j e c t of a long p a p e r [Backus 1978] w h i c h s h o u l d a p p e a r soon in the C o m m u n i c a t i o n s of the ACM. I n o w reg a r d all c o n v e n t i o n a l l a n g u a g e s (e.g., the F O R T R A N s , the A L G O L s , t h e i r s u c c e s s o r s and derivatives) as i n c r e a s i n g l y c o m p l e x e l a b o r a t i o n s of the s t y l e of p r o g r a m m i n g d i c t a t e d by the v o n N e u m a n n c o m p u t e r . These "von N e u m a n n l a n g u a g e s " c r e a t e e n o r m o u s , u n n e c e s s a r y i n t e l l e c t u a l r o a d b l o c k s in t h i n k i n g a b o u t p r o g r a m s and in c r e a t i n g the h i g h e r l e v e l c o m b i n i n g f o r m s r e q u i r e d in a really powerful programming methodology. V o n N e u m a n n l a n g u a g e s c o n s t a n t l y k e e p our n o s e s p r e s s e d in the d i r t of a d d r e s s comp u t a t i o n and the s e p a r a t e c o m p u t a t i o n of s i n g l e w o r d s , w h e r e a s w e s h o u l d be f o c u s i n g o n the f o r m and c o n t e n t of the o v e r a l l res u l t we are t r y i n g to p r o d u c e . We have c o m e to r e g a r d the DO, FOR, W H I L E s t a t e m e n t s and the like as p o w e r f u l tools, w h e r e a s t h e y are in f a c t w e a k p a l l i a t i v e s t h a t are n e c e s s a r y to m a k e the p r i m i t i v e v o n N e u m a n n s t y l e of p r o g r a m m i n g v i a b l e at all.

s t a r t i n g w i t h a small, e l e g a n t f r a m e w o r k - b u t m u s t be b u i l t into the f r a m e w o r k of the l a n g u a g e at the outset. T h e G a r g a n t u a n size of r e c e n t v o n N e u m a n n l a n g u a g e s is e l o q u e n t p r o o f of t h e i r i n a b i l i t y to d e f i n e n e w constructs: for no o n e w o u l d b u i l d in so m a n y c o m p l e x f e a t u r e s if t h e y c o u l d be d e f i n e d and w o u l d fit i n t o the e x i s t i n g f r a m e w o r k l a t e r on. The w o r l d of e x p r e s s i o n s has s o m e e l e g a n t and u s e f u l m a t h e m a t i c a l p r o p e r t i e s w h e r e a s the w o r l d of s t a t e m e n t s is a d i s o r d e r l y one, without useful mathemetical properties. S t r u c t u r e d p r o g r a m m i n g c a n be v i e w e d as a m o d e s t e f f o r t to i n t r o d u c e a s m a l l a m o u n t of o r d e r into the c h a o t i c w o r l d of s t a t e ments. The work of Hoare [1969], Dijkstra [1976] and o t h e r s to a x i o m a t i z e the p r o p e r t i e s of the s t a t e m e n t w o r l d can be v i e w e d as a v a l i a n t and e f f e c t i v e e f f o r t to be p r e c i s e a b o u t t h o s e p r o p e r t i e s , u n g a i n l y as t h e y m a y be. This is n o t the p l a c e for m e to e l a b o r a t e any f u r t h e r m y v i e w s a b o u t v o n N e u m a n n languages. M y p o i n t is this: w h i l e it w a s p e r h a p s n a t u r a l and i n e v i t a b l e t h a t lang u a g e s like F O R T R A N and its s u c c e s s o r s s h o u l d h a v e d e v e l o p e d o u t of the c o n c e p t of the v o n N e u m a n n c o m p u t e r as t h e y did, the fact that such languages have dominated our t h i n k i n g for t w e n t y y e a r s is u n f o r t u n a t e . It is u n f o r t u n a t e b e c a u s e t h e i r l o n g - s t a n d ing f a m i l i a r i t y w i l l m a k e it h a r d for us to u n d e r s t a n d and a d o p t n e w p r o g r a m m i n g s t y l e s w h i c h one d a y w i l l o f f e r far g r e a t e r i n t e l l e c t u a l and c o m p u t a t i o n a l power. Acknowledgments My g r e a t e s t d e b t in c o n n e c t i o n w i t h this p a p e r is to m y o l d f r i e n d s and c o l l e a g u e s w h o s e c r e a t i v i t y , h a r d w o r k and i n v e n t i o n made FORTRAN possible. It is a p l e a s u r e to a c k n o w l e d g e m y g r a t i t u d e to t h e m for t h e i r c o n t r i b u t i o n s to the p r o j e c t , for m a k i n g our w o r k t o g e t h e r so long ago s u c h a c o n g e n i a l and m e m o r a b l e e x p e r i e n c e , and, m o r e r e c e n t l y , for p r o v i d i n g m e w i t h a g r e a t a m o u n t of i n f o r m a t i o n and h e l p f u l m a t e r i a l in p r e p a r i n g this p a p e r a n d for t h e i r c a r e ful r e v i e w s of an e a r l i e r draft. F o r all this I t h a n k all t h o s e w h o w e r e a s s o c i a t e d w i t h the F O R T R A N p r o j e c t b u t w h o are too n u m e r o u s to l i s t here. In p a r t i c u l a r I w a n t to t h a n k t h o s e w h o w e r e the p r i n c i p a l m o v e r s in m a k i n g F O R T R A N a r e a l i t y : S h e l d o n Best, R i c h a r d G o l d b e r g , L o i s H a i b t , H a r l a n H e r r i c k , G r a c e M i t c h e l l , R o b e r t N e l s o n , Roy Nutt, D a v i d Sayre, P e t e r S h e r i d a n , and I r v i n g Ziller. I a l s o w i s h to t h a n k B e r n a r d G a l l e r , J. A. N. Lee, a n d H e n r y T r o p p for t h e i r amiable, e x t e n s i v e and i n v a l u a b l e s u g g e s t i o n s for i m p r o v i n g the f i r s t d r a f t of this paper. I am g r a t e f u l too for all the w o r k of the p r o g r a m c o m m i t t e e in p r e p a r i n g h e l p f u l q u e s t i o n s t h a t s u g g e s t e d a n u m b e r of t o p i c s in the paper.

By s p l i t t i n g p r o g r a m m i n g into a w o r l d of e x p r e s s i o n s on the o n e h a n d and a w o r l d of s t a t e m e n t s on the o t h e r , v o n N e u m a n n lang u a g e s p r e v e n t the e f f e c t i v e u s e of h i g h e r leve l c o m b i n i n g forms; the l a c k of the latter m a k e s the d e f i n i t i o n a l c a p a b i l i t i e s of y o n N e u m a n n l a n g u a g e s so w e a k t h a t m o s t of t h e i r i m p o r t a n t f e a t u r e s c a n n o t be d e f i n e d - -

178

REFERENCES Most of the items listed b e l o w have dates in the fifties, thus m a n y that appeared in the open l i t e r a t u r e will be o b t a i n a b l e only in the largest and oldest collections. The items with an asterisk were either not published or were of such a nature as to m a k e their a v a i l a b i l i t y even less likely than that of the other items.

m a t i c p r o g r a m m i n g systems. In Proc. Symp. on A u t o m a t i c P r o g r a m m i n g for Digital Computers. W a s h i n g t o n DC: The O f f i c e of Naval Research. Backus, J. W.; Beeber, R. J.; Best, S.; Goldberg, R.; Haibt, L. M.; Herrick, H. L.; Nelson, R. A.; Sayre, D.; Sheridan, P. B.; Stern, H.; Ziller, I.; Hughes, R. A.; and Nutt, R. 1957 February. The F O R T R A N a u t o m a t i c coding system. In Proc. W e s t e r n Joint Computer Conf. Los Angeles.

Adams, Charles W. and Laning, J. H., Jr. 195~ May. The MIT systems of automatic coding: C o m p r e h e n s i v e , Summer Session, and Algebraic. In Proc. Symp. on Automatic P r o g r a m m i n g for Digital Computers. W a s h i n g t o n DC: The O f f i c e of Naval Research.

Baker, Charles L. 1956 October. The PACT I coding system for the IBM Type 701. JACM 3 (4): 272-278.

•Addenda to the F O R T R A N P r o g r a m m e r ' s Reference Manual. 1957 F e b r u a r y 8. (Transm i t t e d to Dr. John Greenstadt, Special Programs Group, A p p l i e d Science Division, IBM, for d i s t r i b u t i o n to SHARE members, by letter from John W. Backus, Programming R e s e a r c h Dept. IBM. 5 pages.)

Belady, L . A . 1965 June 15. Measurements on programs: one level store simulation. Y o r k t o w n H e i g h t s NY: IBM Thomas J. W a t s o n R e s e a r c h Center. R e p o r t RC 1420. B6hm, Corrado 1954. C a l c u l a t r i c e s digitales: Du d ~ c h i f f r a g e de formules logic o - m a t h ~ m a t i q u e s par la m a c h i n e m~me dans la c o n c e p t i o n du programme. In Annali di M a t e m a t i c a Pura ed A p p l i c a t a 37 (4): 175-217.

•Additions to F O R T R A N II 1958. Description of Source Language A d d i t i o n s to the FORTRAN II System. New Y o r k : P r o g r a m m i n g Research, IBM Corp. (Distributed to users of F O R T R A N III. 12 pages.)

Bouricius, W i l l a r d G. 1953 December. Operating e x p e r i e n c e w i t h the Los Alamos 701. In Proc. E a s t e r n J o i n t _ C o m p u t e r Conf. W a s h i n g t o n DC.

•Ash, R.; Broadwin, E.; Della Valle, V.; Katz, C.; Greene, M.; Jenny, A.; and Yu, L. 1957. P r e l i m i n a r y M a n u a l for MATHMATIC and A R ! T H - M A T I C Systems (for Algebraic T r a n s l a t i o n and C o m p i l a t i o n for UNIVAC I and II). P h i l a d e l p h i a Pa: Remington Rand UNIVAC.

Bright, H e r b e r t S. 1971 November. FORTRAN comes to W e s t i n g h o u s e - B e t t i s , 1957. In C o m p u t e r s and Automation. Brown, J. H. and Carr, John W., III 1954 May. A u t o m a t i c p r o g r a m m i n g and its dev e l o p m e n t on MIDAC. In Proc. Symp. on A u t o m a t i c P r o g r a m m i n g for Digital Computers. W a s h i n g t o n DC: The Office of Naval Research.

Backus, J. W. 1954 January. The IBM 701 S p e e d c o d i n g system. J A C M I (I):4-6. *Backus, John 1954 May 21. Laning, Jr.

Letter to J. H.

Backus, J. W. 1958 November. Automatic programming: p r o p e r t i e s and p e r f o r m a n c e of F O R T R A N systems I and II. In Proc. S~mp. on the M e c h a n i s a t i o n of Thought Processes. Teddington, Middlesex, England: The National Physical Laboratory.

Cocke, John and Schwartz, J. T. 1970 April. P r o g r a m m i n g Languages and their Compilers. (Preliminary Notes, Second Revised Version, April 1970) New York: New York University, The C o u r a n t Institute of M a t h e m a t i c a l Sciences.

Backus, John 1976 June 10-15. Programming in A m e r i c a in the n i n e t e e n fifties-some personal impressions. In Proc. I n t e r n a t i o n a l Conf. on the H i s t o r y of Computing, Los Alamos. (Publisher yet to be selected.)

Cress, Paul; Dirksen, Paul; and Graham, J. Wesley 1970. F O R T R A N IV w i t h W A T F O R and WATFIV. E n g l e w o o d Cliffs NJ: Prentice-Hall. Dijkstra, Edsger W. 1976. A D i s c i p l i n e of Programming. E n g l e w o o d Cliffs NJ: Prentice-Hall.

Backus, John 1978. The von N e u m a n n style as an obstacle to high level programming; an a l t e r n a t i v e functional style and its algebra of programs. (to appear CACM).

Grems, M a n d a l a y and Porter, R. E. 1956. A truly automatic p r o g r a m m i n g system. In Proc. W e s t e r n Joint C o m p u t e r Conf. 10-21.

Backus, J. W. and Heising, W. P. 1964 August. "FORTRAN. In IEEE T r a n s a c t i o n s on E l e c t r o n i c Computers. Vol EC-13 (4): 382-385. Backus, May.

Hoare, C. A. R. 1969 October. An a x i o m a t i c basis for computer programming. CACM 12 (10): 576-580, 583.

John W. and Herrick, H a r l a n 1954 IBM 701 S p e e d c o d i n g and other auto-

179

• IBM 1956 October 15. P r o g r a m m e r ' s Reference Manual, The F O R T R A N A u t o m a t i c Coding System for the IBM 704 EDPM. New York: IBM Corp. (Applied Science D i v i s i o n and P r o g r a m m i n g R e s e a r c h Dept., W o r k i n g Committee: J. W. Backus, R. J. Beeber, S. Best, R. Goldberg, H. L. Herrick, R. A. Hughes [Univ. of calif. R a d i a t i o n Lab. Livermore, Calif.], L. B. Mitchell, R. A. Nelson, R. Nutt [United A i r c r a f t Corp., East Hartford, Conn.], D. Sayre, P. B. Sheridan, H. Stern, I. Ziller).

Rutishauser, Heinz 1952. Automatische R e c h e n p l a n f e r t i g u n g bei p r o g r a n ~ g e s teuerten Rechenmaschinen. In M i t t e i l u n g en aus dem Inst. fur angew. Math. an der E. T. H. ZUrich. Nr. 3. Basel: Birkh~user.

• IBM 1957. Progra~nmer's Primer for F O R T R A N A u t o m a t i c Coding S y s t e m for the IBM 704. New York: IBM Corp. Form No. 32-0306.

Sammet, Jean E. 1969. Progranuaing Languages: H i s t o r y and F u n d a m e n t a l s . E n g l e w o o d Cliffs NJ: P r e n t i c e Hall.

Knuth, Donald E. and Pardo, Luis Trabb 1977. Early d e v e l o p m e n t of p r o g r a m m i n g languages. In E n c y c l o p e d i a of C o m p u t e r Science and Technology. Vol 7:419-493. New York: M a r c e l Dekker.

Sheridan, Peter B. 1959 February. The a r i t h m e t i c t r a n s l a t o r - c o m p i l e r of the IBM F O R T R A N a u t o m a t i c coding system. C A C M 2 (2) :9-21.

*Remington Rand, Inc. 1953 N o v e m b e r 15. The A-2 c o m p i l e r system o p e r a t i o n s manual. P r e p a r e d by Richard K. R i d g w a y and M a r g a r e t H. Harper under the d i r e c t i o n of Grace M. Hopper.

• Schlesinger, S. I. 1953 July. Dual coding system. Los A l a m o s NM: Los A l a m o s S c i e n t i f i c Lab. Los A l a m o s R e p o r t LA 1573.

•Laning, J. H. and Zierler, N. 1954 January. A p r o g r a m for t r a n s l a t i o n of m a t h ematical e q u a t i o n s for W h i r l w i n d I. C a m b r i d g e Mass.: MIT I n s t r u m e n t a t i o n Lab. E n g i n e e r i n g M e m o r a n d u m E-364.

Zuse, K. 1959. Dber den PlankalkUl. Elektron. Rechenanl. 1:68-71.

McCracken, Daniel D. 1961. A Guide to F O R T R A N Programming. New York: Wiley.

In

Zuse, K. 1972. Der Plankalkul. In Berichte der G e s e l l s c h a f t fur M a t h e m a t i k und D a t e n v e r a r b e i t u n g . 63, part 3. Bonn. (Manuscript p r e p a r e d in 1945.)

Moser, Nora B. 1954 May. Compiler method of a u t o m a t i c programming. In Proc. Symp. on A u t o m a t i c P r o g r a m m i n g for Digital Computers. W a s h i n g t o n DC: The O f f i c e of Naval Research. Muller, David E. 1954 May. Interpretive r o u t i n e s in the ILLIAC library. In Proc. Symp. on A u t o m a t i c P r o g r a m m i n g for Digital Computers. W a s h i n g t o n DC: The O f f i c e of Naval Research. •O p e r a t o r ' s M a n u a l 1957 April 8. Preliminary O p e r a t o r ' s M a n u a l for the F O R T R A N A u t o m a t i c Coding S y s t e m for the IBM 704 EDPM. N e w York: IBM Corp. P r o g r a m m i n g R e s e a r c h Dept. Organick, E l l i o t I. 1963. A F O R T R A N Primer. Reading Mass.: A d d i s o n - W e s l e y . • Perlis, A. J.; Smith, J. W.; and Van Zoeren, H. R. 1957 March. Internal Translator (IT): a compiler for the 650. Pittsburgh: C a r n e g i e I n s t i t u t e of Tech. •P r e l i m i n a r y R e p o r t 1954 N o v e m b e r 10. S p e c i f i c a t i o n s for the IBM m a t h e m a t i c a l F O R m u l a T R A N s l a t i n g system, FORTRAN. New York: IBM Corp. (Report by Programm i n g R e s e a r c h Group, A p p l i e d Science Division, IBM. D i s t r i b u t e d to p r o s p e c t i v e 704 c u s t o m e r s and other i n t e r e s t e d parties. 29 pages.) •P r o p o s e d S p e c i f i c a t i o n s 1957 S e p t e m b e r 25. P r o p o s e d S p e c i f i c a t i o n s for F O R T R A N II for the 704. (Unpublished m e m o r a n d u m , P r o g r a m m i n g R e s e a r c h Dept. IBM.)

180