[Topic drift alert...]
Tim Bradshaw <tfb+google@tfeb.org> wrote:
+---------------
| Charlton Wilbur <cwil...@chromatico.net> wrote:
| > Because what you know is wrong: iteration and recursion are
| > computationally equivalent. If you can express an algorithm
| > iteratively, you can express it recursively, and vice versa; the
| > principal difference is that you can maintain some state implicitly in
| > a recursive expression of the algorithm, but you must maintain all the
| > state explicitly in an iterative expression of the algorithm.
|
| As a note to this, it's worth noting that not all processors actually
| have instructions which support recursion directly. Instead, code for
| them typically maintains various stacks itself. It's reasonably
| obvious how you compile recursive code for such a system, which helps
| to make it clear that the two ideas are actually equivalent.
|
| The RCA 1802 is a well-known example (well-known to me, anyway, since
| I wrote code for it...)
+---------------
And the DEC PDP-8 [for which I wrote lots of code], which was
particularly nasty in that regard in having only one main data
register ("the accumulator" a.k.a. "AC"), and in having as its
only subroutine call an instruction ("JMS") which wrote the value
of the return PC into the *target* subroutine address!! [Yes, this
means that PDP-8 program code must (usually) be write-enabled!]
See <http://www.cs.uiowa.edu/~jones/pdp8/refcard/74.html> and
<http://www.cs.uiowa.edu/~jones/pdp8/man/>.
Nevertheless, very small amounts of macro hackery [together with
a couple of *small* utility subroutines] sufficed to provide the
PDP-8 assembly-language programmer with software-managed stacks,
so that instead of this:
...
JMS FOO / call FOO
...
and this:
FOO: 0 / reserve space to store return PC
...[body of FOO]...
JMP I FOO / return by jumping indirect through entry loc.
one could write this [patterned on the PDP-10 instructions
of the same names]:
...
PUSHJ / call FOO: Push return address on stack then JMP.
FOO
...
and this:
FOO: ...[body of FOO]...
POPJ / return by popping ret. PC off stack then JMP I.
Said another way, despite having no hardware stacks at all,
people were neverthless quite successful at getting Fortran,
Algol [both Algol-60 and an emulation of BALGOL (Burroughs Algol,
the systems-programminbg langauge of the B5500)], MUMPS, FOCAL,
DIBOL (a subset of COBOL), and a bunch of other languages to
run just fine on a PDP-8.
-Rob
-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607