parts of CPUs, and things like this. And one of the things he'd mentioned during

one of the videos is something that I believe you want to tell us a bit more

about -- the Wheeler Jump ? >> DFB: Yes the Wheeler Jump David Wheeler [a]

very very talented computer scientist. An excellent lateral thinker. I didn't know

him very well; I knew him very slightly. Maybe met him four or five times but you

just had to be impressed that he, as a computer pioneer, had to grapple with the

fact that very early computers did not have enough registers in their CPUs.

>> Sean: Registers are just like tiny bits of memory? >> DFB: Yeah! tiny bits of memory, but within the

central processor unit. They could be built of much faster technology than

main memory, so typically, you know, like with the ARM chip at user level, you'd

end up with 16 general-purpose registers. One or two of those might be set aside

to use for all sorts of useful things. And one of the useful things was the

idea of -- you're running through your program -- you want to jump into a subroutine to

calculate a sine, or to print out "Hello World", or something like that. You don't

want it to be running linearly on your program you want to jump into it and

jump back out of it again. So you could use it several times in your program

from several different places. You could jump in and jump back out. Now David

Wheeler is credited with this idea of inventing the subroutine and say[ing] "Well,

yeah, when people want to calculate sine of something they don't want to have to

replicate, in their program, the coding for sine in six different places". It might

make it go faster - and of course some of you will know that if you write macros

you can force it [to create in-line code] to do that. [You] sacrifice a lot more code for faster speed But no, to

keep it clean you basically say "I want this piece of code to be separate but

"jumpable into" and "jump back outable from", back to where you came from.

So, before you jump in, at the moment of the jump, you've got to say "Where am i coming

from? Whose responsibility is it to remember

that? And in modern CPUs you would have a link register of some sort that

remembers. You didn't have that in the very early days. But, boy, did it [soon] dawn on them

that you needed it! So if you didn't have a link register how on earth were you

going to get into, and out of, your subroutine? So let's say you're coming

from 70 shall we say - location 70 - something like that? Right, now, on this

particular occasion therefore - when you get back out of that subroutine - you

don't want to go back to 70 itself because you'd end up in an endless loop

of jumping back into yourself you want to go to the instruction just beyond 70.

But you want to get back out! You want to remember 70 [and] add -- depending on the

architecture -- you add 1, 2, 4 ... depending. whetherWhen it's a byte machine, a word machine,

whatever. But you add a small number on to that address and say: "That's where I

want to get back to -- the instruction after where I jumped from". >> Sean: And the

problem is that you've got nowhere tosave [it]? >> DFB: Well, on modern machines [address] 70 would be

saved in a link register, maybe [on the ARM chip] register number 14, or something.

You say: "Jump to subroutine". The moment you say it, it automatically

remembers where you're jumping from and puts it in the link register. So when you

want to come back out you say: "ere I am, on this architecture, where's my link

register? Number 14?. Let's look at its content. Oh! it says "70" and I'm on a

32-bit machine with 4 bytes to the word so that's ... I want to jump 4 beyond 70".

Or if it's, y' know, like EDSAC it might be 1 or 2 beyond. But you want to

just jump back to where you came from, slightly adjusted, with a little amount

added. And it is that link register that saves you from going insane. Now back in

the early days of David Wheeler and this EDSAC machine he had to do this for ...

Oh golly! I wish I had an extra register but I haven't

Wat register have I got, that's in use all the time, that might - if I'm very careful -

serve me all right. And the answer is - the Arithmetic Accumulator.

Every time you loaded a number into the accumulator, or did some arithmetic, the

answer stays in the accumulator. OK, so here's the deal: we're going to use the

arithmetic accumulator as the means of remembering where we came from. So here

you are at location 70, in the early EDSAC machine, what do you have to do ...

>> Sean: So, you have to add 70 to 0, or something? >> DFB: Yes! Basically "yes"! You're jumping

from 70 -- OK 70 has got to be in the accumulator at the moment of jump -- and

then you do an unconditional branch instruction to get to the start of the

subroutine. Fine! But you wake up in that subroutine your

first job is to preserve your link to get back! You must NOT do any arithmetic

- because you [might] feel like it. Duty calls! You must save off your return link

somewhere safe! Right?! Because, if you don't, you won't be able to get back.

But you have no spare ... >> Sean: So we've got nowhere to save .... >> DFB: ... no spare registers to save it

Yeah! you might think so, but how about this: suppose at the bottom of your

subroutine there is a branch instruction, a dummy one, which is basically going to

say branch, or jump, back to where I came from. But "where I came from"

must be a literal correct address. And in the accumulator is 70. So what you that

have to do is - knowing the length of your subroutine and its addresses and knowing

where the return instruction is planted as a dummy - you've basically got to turn

70 into 72, 74, whatever it is, to make it go back to the next instruction after

where you came from. And you must literally plant that instruction and -

shock! horror! - overwrite your own program code at the bottom of this subroutine, so

that the dummy jump, which has probably got zeros left in it by now, becomes jump

back to location 72, shall we say. But you are actually

altering memory. Now can you imagine if that goes wrong, how to debug a program

that's trampling all over itself and jumping back to the wrong address! you

know >> Sean: Code gets altered all the time, right?! Can you give us some sense of how

sacrosanct these lines of code are when it's running? >> DFB: Well, code may seem to alter

itself all the time but it's usually altering itself by manipulating

registers in the CPU not physically overwriting memory in your main memory store.

>> Sean: So it's OK to obviously change the value for variables, and and all of

that, but actually changing those lines of code should be .... >> DFB: Changing variables is

fine. That's data. You're allowed to change data. What you're not allowed to

do is to treat a program-instruction bit pattern as if it was just a piece of

data and to patch something on top of it Now you can do this on Z80 chips,

I've tried doing it! If you go to very simple chips there's no protection

mechanisms. They'll let you do anything you want and you just hang yourself! Fine.

More advanced chips, now, and particularly operating systems make use of this, give

you an ability to mark which pieces of memory are read-only and are not to be

overwritten. And that way you can stay fairly sane.

Although you've left behind a polluted piece of code saying "jump back to 72" the

next time you come into this routine - maybe having jumped from 256, shall we

say, you've now got to remember 256six in the accumulator. The moment you

get in there you adjust it ever so slightly to come back to 258,

or whatever it is, and you plant that instruction to overwrite the jump back

to 72 which is still there, literally inside your code. So, every single call

you make into that subroutine the link back has to overwrite whatever

usage you had before and plant it in exactly the right place to get back. You

can see now why the moment EDSAC II came along - all of a sudden this had link

registers. All of this early experience just showed the pioneers

what the next generation of machinery had to have. And that's how the

importance of link registers became obvious. It will have occured to you of

course, Sean, I think I've got this right, that doing it the day David Wheeler way

with a Wheeler Junp, right, you successively at the end of your routine

of writing back and patching it with your address you need to get back to,

That's fine and it'll work. But what does that NOT enable you to do? Begins with an "R". omen

>> Sean: A further ... recursion oh yeah! >> DFB: One of thereasons for wanting a more general

mechanism for doing it is [that] you can't do recursion with the Wheeler method

because you've only got one place in memory, at the end of the subroutine,

where you patch back a new return address. What you need with recursion is

to have *several* return addresses all waiting to be used

queued up ... no not queued up ... stacked up on tha stack. So, that's the other thing.

>> Sean: Recursion is obviously a very particular special case but does this Wheeler Jump

not even allow you to do branches in branches? >> DFB: Oh! you can do that. Yes, yes, you

can do that but but actually having, y'know a thing call itself, since you've

textually only got one copy of the routine, just one, you're not able to

replicate the text in any way, there's no ability to do that. You can only damage

that one return address, just the one. That means that the next realization from

being a pioneer is my golly we've gotta be able to do recursion. My golly we need

more general-purpose registers and all this kind of stuff. And oh! also,

wouldn't it be nice to put a marker on memory saying: "Don't let anybody over-write

this!" And actually have it hardware- imposed not just by people's good nature.