Re: Optimization of Uncommon Code

Dwight VandenBerghe commented on the wide use of the 360 (and of
more-or-less 360 clones) back in the days when FORTRAN (and COBOL) were
kings.


For large-scale numerical programming, if you could get time on one, the
super- computers of the day were CDC 6600's (and their close relatives).


The procedure call on the 6600 saved the return address *at a fixed location
in memory*. More precisely, the address you specified was of the word
*before* the first instruction of the procedure. The hardware saved the
return address there, then jumped to the next instruction. (Even more
precisely, what it saved in that word was a jump instruction back to the
caller! A procedure exited by jumping to its entry point.)


There was, of course, no hardware stack. Creating and using one for data
would be very easy. Pushing the return address - well, the return
*instruction* - on the stack would cost you three instructions. You'd
presumably return by simply jumping into the stack. Not too bad - but not
done by any of the standard compilers, and certainly not by either of CDC's
FORTRAN compilers. Recursion was unknown in the FORTRAN world - and the
COBOL world. Add those together and you have almost all the American
programming community through the '60's.


We're all so used to recursive functions these days that we forget you novel
the idea was at first. Tony Hoare has an article somewhere in which he
talks about his development of quicksort. Never having seen recursion, he
originally developed the algorithm without it. He had great trouble
convincing anyone of its correctness in that form. Then he read one of the
original Algol papers - the first time recursion functions had appeared in
the mainstream. (They were, of course, central to work in the Lisp
community by that time - but the Lisp community's work was - and to a great
deal still is - invisible to the outside world.) When Hoare recast
quicksort as a recursion, all of a sudden, it became small, clear, and
obviously correct.


My first exposure to recursive functions was in SNOBOL4. Since the idea was
still so new, the SNOBOL4 manuals spent many pages describing and
illustrating the notion, how it worked, and how one might use it.


-- Jerry
[The 1963 vintage PDP-6, which had a very advanced architecture for its day,
had three different subscroutine call instructions: JSR for the 6600 style
call (used by Fortran), PUSHJ for a stacked call (used by Lisp), and JSP for
a 360-style save return in register call (used by nobody, oddly.) -John]


--

Return to the comp.compilers page.
Search the comp.compilers archives again.