...
> It does not, and I regret the implication. To clarify, a language with
> subroutine call is best implemented with a runtime stack: a context
> free language can only be compiled with a stack, but that point isn't
> relevant to Schildt's point. If it also has recursive subroutine call,
> it can ONLY be implemented with a stack.
I wonder. Somewhere in my archives I have the transcript of a discussion
between van Wijngaarden and somebody else where van Wijngaarden did show
that labels were not needed. (I do not have it nearby, my archive is a
bit scattered around.) The first step in the transformation of a program
with labels was to a program without subroutines, replacing nearly every
subroutine by a label. So apparently, every program containing recursive
subroutine calls could be transformed to a program without recursive
subroutine calls. (The next step was replacing every label by a subroutine.)
I don't this would have worked. It appears to me that it would
transform a recursive factorial program into one with N procedures for
each level of calculation, bounding the maximum N and creating an
absurd number of procedures. But I could be wrong. Sounds like early
art before the lads had mastered everything.
> And note something very interesting in this regard. A language which
> has subroutine call, but no recursion, is dead on arrival. This is
> because the language compiler cannot detect indirect recursion where a
> calls b calls c ... calls x calls a if there are library routines
> whose source code is not available to the compiler.
Right, that was why Fortran was dead on arrival.
OK, Fortran II wouldn't be useful today! And as it happened, very few
recursive descent parsers were written in Fortran in the early days,
and those that were, used stacks represented as arrays with fixed
bounds, creating a limit on the number of parenthesis levels. I do
recall a recursive descent parser being described in a Cambridge
University Press book on non-numeric Fortran (from which I learned how
to create bar charts on line printers) but it was a toy.
Fortran was used for "primitive recursive" calculations at best, or
worst if you please.
Furthermore, the limitations of early Fortran (and Jovial) have
probably caused over time any number of genocidal cockups in Western
militaries. We don't know what they are and we hold the apparatus
harmless because of official secrecy.
> This means that if indirect recursion occurs by accident, a hard to
> detect bug will probably occur when control returns to the first
> subroutine called by a (b) and it tries to return to a's first
> activation.
I indeed have seen this happen with Fortran programs, resulting in infinite
loops. Not the only problem with Fortran that could not be detected by
either the compiler or the runtime.
Excuse me, but compilers did NOT detect circular calls at that time.
And how do you detect circularity at runtime? With modern software
it's easy. Back then it required an unbounded table, and the machines
of that era didn't have the storage.
No, back then, if you wanted to do recursion, you used Algol: period.
And if you didn't want it to run slowly and interpretively on an IBM
mainframe (assuming you could persuade IBM to stop messing around and
support Algol), you went to Burroughs...which supplied machines with a
stack.
Indeed, I just happen to have all these years a ruin of a book which
has survived black rainstorms in Hong Kong and floods in Fiji. Let's
get it off the bookshelf, shall we?
Ah yes. "Computer Structures: Readings and Examples". Copyright 1971,
McGraw Hill. Ah: memories, if of machines I did not for the most part
program. Perhaps they will evoke memories in you, Mr. Winter, of
Justice Shallow's "Chimes at Midnight" i' th' old play.
The DEC 338 Display Computer. One Level Storage System. The Pilot Ace
("it was based on an earlier design by Dr. A. M. Turing"). The
Olivetta Programma 101 Desk Calculator: buddy of mine flogged them in
the Loop in 1966. The Illiac IV Computer. System Design of a Fortran
Machine. Parallel Operation in the Control Data 6600. The SDS 910-9300
Series. The DEC PDP-8. The IBM 1401, my first machine.
Design of the B 5000 System: "The Stack":
"The problem is attacked directly in the B 5000 by the incorporation
of a 'pushdown' stack, which completely eliminates the need for
instructions coded (or compiled) to store or recall intermediate
results."
There was a Burroughs B 5000 in the window of a Burroughs show room at
the corner of Michigan and Van Buren streets when I was working one
block to the south. The programmers in that shop seemed far more
intelligent and relaxed than the IBM systems engineers I worked with,
perhaps because they were not as hag-ridden by the almost theological
need to "save" dem registers.
Burroughs, in the USA at any rate, fulfilled a need banks had back
then for computing trustworthiness. Although the torch was then passed
to Tandem and its fault-tolerant (and equally stack-based) machine by
the mid 1970s, the deregulation of the financial industry which
started with Reagan, and which destroyed savings and loans by 1989,
meant that banking computing could be less concerned with reliability.
The long-term result was today's depression.