Wheeler Jump - Computerphile
Vložit
- čas přidán 5. 02. 2018
- Professor Brailsford returns to the Wheeler Jump (as mentioned by Doctor Bagley in the Subroutine video)
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
I love the interactions between Sean and Professor Brailsford, it's almost like a "History of Computing" class teacher-student dynamic
Eric Vilas
it's like listening to the grandpa you secretly wish had been yours.
I just love how Prof. Brailsford presents all this information from the earlier days of programming and computer design, as well as how much he knows and remembers. Most people these days with a supercomputer in their pocket have no idea how much work went into how many decades to learn how to build the things that led up to that technology.
The Parallax Propeller microcontroller (as found in the YBox2 kit on Adafruit) makes you do self-modifying code like this for subroutine calls. It makes implementing a recursive function rather hard, but embedded programs almost never do recursion because of unbounded stack growth.
I don't care the subject. I see a video with Professor Brailsford and I'll watch start to finish with awe
Self modifying code was still a thing well into the 80's, games were famous for it to obfuscate entry points.
Another common trick was modifying the top of the stack to manipulate return addresses.
Professor Brailsford's videos made me understand computer architecture better then I ever did during my CS degree..
Using accumulator register in a non-standard way reminds me of Commodore 64 times when I've been using stack register S as a data register to avoid r/w in memory. This was saving one or two CPU cycles per loop. Simple architectures rock!
I think you would appreciate the content on my channel haha
I'm rather surprised it saves that much time using a 6502 based system; The whole point is that memory access (especially to zero page) is only marginally slower than doing calculations in the registers.
Then again, you are talking an optimisation of only 1-2 cycles, which is I guess the difference between a calculation taking 5 cycles or 3...
Still seems like a rather extreme optimisation to need...
But what would I know? XD - my 6502 derived systems are the 800XL and SNES... Both of which have faster processors than a c64, and have design features that make the use of a tightly coupled graphics kernel less likely to be necessary... (Antic, as primitive as it is, truly is something of a miracle... At least, as long as you don't need TOO many DLI's...)
That optimization was necessary to beat the world record in shadeplots per frame. The code and the intermediate data were on zero page. If you save 2 cycles per 44-cycle loop (making up the numbers now as it was so long ago) that gives you 10+ more iterations possible. Cannot remember the proper numbers now, unfortunately :(
Ah, the good old Z80 - first came across self modifying code during the loading of a particular video game. During loading the screen would flicker in two colours, but mid way through the colour scheme would "magically" change. The game bootstrap had moved the tape routine to somewhere in the middle of RAM and as it was loading itself from tape would overwrite that location with new colours. Was blown away at the time !
Jump-back-outable is now my favorite adjective.
@yondaime500 When did he say that?
I like how he said " *fairly* sane" at 7:50
I now want that on a t-shirt. "fairly sane"
The best type of sane.
Hmm, this doesn't allow recursion, but it DOES mean you can have subroutines that link in to _other_ subroutines themselves, possibly setting up whole context changes, _without needing a stack or stack pointer,_ which is a pretty neat trick in terms of saving both registers and memory space (as the stack swallows up quite a lot of bytes for each level of recursion or other nesting...)
This is a really cool insight, thanks!
@@sanderbos4243 a missing part of the above also is a repeat of what i put in my other comment - not only does it save registers and memory, which would be at an extreme premium in the kind of computer this is intended for, but not needing a hardware stack pointer is kind of vital if your machine doesn't even have one because it hasn't been invented yet...
Bjarne Stroustrup completed his PhD under David Wheeler's supervision.
Oh yeh , he is back and looking cool and trendy in that tshirt and jacket. Never stop professor , the computing and IT industry needs old dogs like you to tell all the kids how it is.
You can bypass the protection on modern CPUs tho , thats how allot of local hacking and modding can be done. Its super dangerous but you can do it.
Essentially that's what Protected and particularly Virtual mode on everything from the 386 (and 68010) forwards was meant to guard against ... user code can never tell whether it has admin rights or not, because only the supervisor thread gets any say over that, and everything else is always _told_ it's the supervisor, but is fed a pack of lies re: what's in the status registers and has any attempts to do super-mode stuff silently squashed... It's essentially stuck in the matrix. But there are presumably still ways you can fiddle with code so as to work out that you are, indeed, a program that's stuck in user mode, and finagle your way out by tricking the supervisor somehow ("correctly written" OSes should guard against that completely, of course, but the perfectly correct system doesn't yet exist)...
Another great video. With so much focus on high level code and programming patterns, its good to learn about the important low level considerations. I look forward to the next video
"Jumpbackoutablefrom" is now part of my vocabulary for ever.
I found out the hard way that a particular graphical effect I want to do on the Atari 2600 requires self-modifying code because it's just not fast enough otherwise. So in that case you need to sacrifice tens of bytes copying a subroutine template into the 128-byte RAM, because (on a stock machine, no extra memory on the cartridge) that's the only rewritable area.
Now, my purpose is just to make a cute little single-screen animated demo, not a game, so I have plenty of memory to spare.
Professor Brailsford rules.
Not only is the speaker phenomenal, the graphics are fantastic.
Professor Brailsford has to be one of the best at explaining things.
My stomach starts to flip when I realize that self-modifying code is the direction of the video. Oh my.
This certainly helps me appreciate learning about "activation records" last semester
And i feel like a little kid listening to the best stories from this guy!
I just noticed the T-shirt. The professor does keep his word
fun fact: if you type recursion on google you get "Did you mean: recursion".
I giggled far more than I should have by doing that and then clicking the link over and over again.
Quite a few textbooks have this sort of thing in the index; recursion having the index page as an entry
loooooooool :))
He's back! Whoo!
Professor Brailsford is my favorite.
a similar technique was also used on 8 and 16 bit machines to build efficient jump tables. They can be found all over the place, mostly in video games and demos
Sounds like a memory-intensive approach. Might not have been usable on one of those early valve machines with only 1kword of memory.
The core dump of the subroutine would tell you where it was called from last. That might actually help debugging.
This video reminds me of a programming game BOX-256 which was simulating assembly programming with restricted set of instructions and output drawn as coloured grid/matrix. One could overwrite any memory cell including modifying the program itself and some people were able to perform wonderful tricks with it.
The funny thing is that the latest thing in weird machine code is doing your regular branches by putting the destination in the link register and "returning" somewhere you didn't actually come from. On many CPUs, this turns out to prevent one of the variants of Spectre, because the CPU doesn't predict returns.
That sounds like continuation passing style code.
Well, continuation passing style is where all of your flow control is making function calls with no returns. So maybe we've built up 43 years of function calls that we never returned from, and now it's time to balance that out with returns to code that never called us.
I also did it when patching closed-source programs. Having "push ; ret" in a DLL that patches an executable is one of convenient ways to do a jump into a routine in the main program.
The joy of self modifying code - I remember doing this on the Game Boy's Z80 xD
So a link register would only allow single layer subroutines, the wheeler jump would allow multi layer subroutines, but no recursion, so in order to do both multi layer and recursion, what you need is a link stack, which as far as I remember is the modern solution, where the cpu just puts the latest return address on top of a stack of return addresses that came before and then reads them off in reverse order
You know I like the zachtronics games, particularly spacechem and TIS100 because it taught me many tricks in assembler programming, but especially the assembler puzzles are always so frustrating, because they have such a steep learning curve and I either run out of space or trip over the fine print of functionality.
I should continue playing exapunks at some point. I haven't found the limit of things I can do in that yet
One of the so-called benefits of OOP was code reuse, but it's older than most people think it is...
Pretty cool! Guess it only works for small programs as the accumulator only stores an 8-bit value (in the early computers mentioned)
Very interesting and educational!
One question though, why did we save 70 and incremented it by 2 in subroutine?
We know where to return to before calling subroutine, so we coluld've saved 72, and in subroutine we could've only modify the return branch without making this unnecessary +2 math.
Great video, but I think you guys have already covered Wheeler Jumps a few months back
A link register isn't actually required for subroutines, though. You can just use a stack. For instance, the 6502 has only three general-purpose registers (A, X, Y) and no link register, but it of course has subroutines. It uses $0100-$01FF as a 256-byte stack, and a jsr automatically pushes the PC + 1 onto the stack, while an rts pulls it from the stack and puts it back into the PC. The 6502 does have an 8-bit stack pointer register, but if it didn't, the stack pointer could have been stored in memory as well.
I guess the problem is that you need a full word on the EDSAC for each address and for the stack pointer, so there just isn't space for it in memory. But the Atari 2600 used this method, despite having only 128 8-bit words of RAM, mirrored as both zero-page and stack. In other words, every read and write was technically to and from the stack (but hopefully far enough down that it didn't overwrite it).
I'm a little confused. One link register isn't enough for branches within branches (function calls within function calls), as the second "internal" branch would overwrite the accumulator value and you'd lose your pointer back to the original calling location. So you need a stack which stores multiple pointers to do even branches-within-branches. If you can do branching-in-branching, why couldn't you also do recursion using that same stack?
Wow. I remember trying to write programs for the ZX Spectrum in machine code and having to use something like this technique.
On the Spectrum (Z80 assembly) you use the stack to store the program counter. No modifying of code necessary. Of course there was nothing actually stopping you using this method if you really wanted to.
Xei You're probably right, but programming was a new thing for me at the time and I didn't really know what I was doing!
And his MMIX machine, although you no longer need self-modifying code, just store your rJ in a local register if you call yourself or some other subroutine, remembering to restore that value back to rJ prior to POP.
Well, as the prof says, you can totally use this on Z80s if you want to or need to... as, thanks to being 8080 derived, it doesn't have a specific Link Register, though it does at least have a couple of Index regs alongside the SP (and if you're going for speed or compactness, using the stack just for simple subroutine return address storage, rather than full context switches, can be a bit inefficient anyway).
6:45 ... well, I'd probably start with spotting how it's supposed to be altering location 540, but instead it's writing to 561. That's probably not going to go well. Though it is of course rather easier to spot faults in self-modifying code when you've got a nice colourful animation to make it obvious...
This guy's by far my favorite Computerphile instructor, so whats up with all the hate in the comments?
literally no hate at all
Does this mean that you wouldn't be able to keep subroutines in rom. If so how would you implement firmware subroutines
If you were forced to use this technique, you could _store_ them in ROM, but you wouldn't be able to _run_ them from it without copying them to RAM first.
ROM hadn't been invented yet, other than as a series of jumper cables used much like a telephone switchboard. EDSAC loaded all its programs into vacuum-tube RAM from paper tape.
Though to properly answer your question, for a ROM+RAM system using such a technique, you would almost certainly be executing single-threaded software with absolute dominion over the whole machine and the programmer would be able to define exactly, through the ROM program, where everything would be stored in RAM. So you would just write your return address into some particular location in RAM (sort of like a miniature, single-value stack; though if you wanted to be able to jump between different subroutines you could have each one place its return address in a different location, and if you wanted to implement recursion you could even use some flavour of true stacking, if there was enough memory for it - on something like the Atari VCS, with its 128-byte RAM, you might find that space gets a bit tight), and the last instruction of the subroutine is essentially "jump to the ROM address specified in RAM location XYZ". Most microprocessors have provision within their JMP routines for that kind of indirect addressing.
If you had a ROM, the solution would be to store the return address in RAM and use it by the best method available. This would either mean stuffing it into a program counter or placing a jump instruction in RAM and jumping to it.
@@gwenynorisu6883 EDSAC used mercury delay lines for memory.
this technique seems vaguely related to "threaded" code (of the kind Forth uses, not threaded as in multithreading) but I don't yet understand the latter well enough to tell how
Where is he? It doesn't look like his usual place(s) at the school.
Thought it would be, but I wonder why. He's still active at the university, isn't he, or has he retired?
I imagine that one advantage of this method over link registers is that you are fine if you call another function within your function (other than itself, as mentioned). Link registers don't allow you to do this by themselves; you need to have some kind of stack (either assisted by hardware or manually implemented).
So I suppose you could say that recursion is actually no different between this method and using a link register, since you'll need some kind of stack either way (excluding really weird hacks).
What prevented them from putting return addresses on a stack?
A lot of the early computers didn't have a stack.
Kasper Guldmann Had to event that next!
That became the next epiphany.
Edzac iz older than universe itself.
If you don't have a link register when you need one, you probably haven't got a stack pointer either (which is probably the more relevant term for modern CPUs, other than anything ARM-based, as they don't have LRs anyway, just SPs and IRs). And without a stack pointer... how are you going to stack? Best you can do is inject additional code at the start _and end_ of _every_ subroutine to do it manually (going full Turing Machine on the problem), but if you're going to do that sort of thing, you're a) going to need some additional storage to keep track of how deep the stack is and _where_ it is anyway (unless you have the maximum amount of memory allowed by your architecture, AND your stack grows downwards from memtop, you can't just go "count this far backwards from 0-1"), b) likely pretty short on memory so the tactic will badly hamper the potential size and sophistication of your programs, and c) probably going to find that just using the Wheeler Jump is the faster, more efficient, less memory hungry, and indeed _easier to follow_ and less potentially code-stomping option.
My first time writing C for a - if I remember correctly - PIC18F45K22 I learned firsthand what it's like to have a processor that doesn't care what address you're writing to. On the plus side this does also allow for some unique ways of code optimization.
Didn't they do a video on this already? I thought I saw one about this
Apparently the system already had RAM because that's where the program code is, so why didn't they just use part of that RAM to store a stack?
If a link register is used, a subroutine cannot call another subroutine. Right? Every processor I've used either was limited to one subroutine, used a separate stack (usually 16 deep), or just pushed the return address (and status registers, if you're lucky) onto the program stack.
Tail recursion still works.
How do you pull that off in assembly?
You would have an instruction to jump back to the start of the recursive routine, but *without* modifying the link register. So when you finally return, you go back to the level of execution *before* all the recursion.
Technically that's not really a subroutine call, but it would certainly work. Thanks for the tip.
To add recursion to the wheeler method, can't you just copy the subroutine to a new memory location. Call it and have that re-write on the go? You can have as many subroutines as you like then because each has it's own return address copy.
that "new memory location" needs to be tracked down by some sort of pointer, a stack pointer that is, so there you have the need for a Stack Pointer register. If you don't have a SP then your code would be much longer and it will consume a lot of memory, which would be very scarce at the time (we are talking a few hundreds of memory locations for an entire machine)
You have re-invented the stack idea that is used on all modern CPUs.
Only thing is that it doesn't copy the whole subrutine but just copies the return adress in to a list (Along with other cpu registers so that you can mess them up as much as you like during your subrutine)
as berni8k points out, if you have a known block of addressable memory then you don't need to copy the function, just use it as a stack
So how are branches in branches done?
(Cool video BTW)
If you mean, how does one subroutine call another subroutine, it'd be in the same way. The restriction is that there's only one copy of each subroutine in code, so recursion is impossible. But you can jump from one subroutine to another as many times as you like, since each one has its own final instruction to mutate with the correct return address.
So the only real gain this methods provided was that the instruction was fed automatically to the CPU when the time came, instead of heaving to do a lookup? You still need to put the number in the arithmetic unit and then write it to, basically, the same external memory that is so much slower than a register, at least if we are talking Von Neuman.
Really interesting stuff.
: D
Haha, he really got that t-shirt! Love it!
Oh, and lazy binding for shared libraries is a modern example of where code is modified by an application while it is running.
Tends to be default when building applications for Linux (and probably other systems, but I don't know). Sometimes disabled for security reasons (since it means that that area (GOT or PLT; I forget which) can't be protected by the MMU as read only.
I need to meet professor brailsford it's very important. He will be happy we talked.
Why can't you do a wheeler-jump style subroutine for recursion with a fixed depth? Could you not put a table of "scratch memory" at the end of your subroutine and write self-modifying code there that behaves like a stack? Sure, you would only be able to make one recursive call in the routine so that you don't clobber the stack index, but that's still something.
How often do you actually need recursion? More often you can just use loops
The DEC PDP-8 did this:
Your main code has a jump to subroutine
By time the instruction is decoded, the program counter is incremented
The 1st action of the jump is to store the program counter into the place addressed by the jump instruction.
The word after the one pointed to is then loaded as the 1st one to do in the subroutine
...but how does it then know to read from that location again to get the return address? Presumably the end of the subroutine has an instruction to read from that original memory cell, which overall makes the whole operation a variant of the Wheeler Jump, just with the locations and operation order a bit back to front.
I mean, it definitely makes the code a lot easier to edit without causing massive issues if you forget to change the location that you store the return address into as the subroutine length alters, it's got _that_ going for it...
DEC’s 12-bit (PDP-5, PDP-8, PDP-12) and 18-bit (PDP-1, 4, 7, 9 etc) machines used this trick. The jump-to-subroutine instruction was called “JMS”, so
JMS SUBR
would store the address of the following instruction at location SUBR, and transfer control to address SUBR + 1. (cont’d)
(cont’d) By the way, the first prototype of what became Unix was developed on a PDP-7. You can see why they were quick to move to a PDP-11, which had a much nicer architecture with a proper stack.
(cont’d) This would jump to the address stored at SUBR, which was of course the point in the caller at which to resume execution. (cont’d)
(cont’d) There was no return-from-subroutine instruction as such, instead you ended execution of SUBR with an indirect jump: (cont’d)
But isn't it that link registers also cannot provide recursion?
A link register by itself couldn't provide recursion, or even depth in subroutine calls. Add a stack into which the value can be stored and you can do recursion.
Tail recursion still works.
Definitely not thread safe. :)
aw yeah
I just thought of something; how would function arguments be passed with no stack and with the only available register in use?
Mostly routines expected values to be held in fix locations of RAM in such machines. You have the same issue on the 8051 microcontroller and many of the ones from Microchip because their stack only holds return addresses.
Link register? In all the architectures I've seen, it just uses the stack.
I'd like to see a talk on link registers vs the stack and calling conventions.
I can't believe early processors didn't have stack frames. What if the routine was longer than the start of the instruction stream? Like if the subroutine was 80 instructions but started at location 70.
...huh? Why would that be a problem? You'd just store the return address into location 150, surely?
When you've got 512 words of memory to play with and are using subroutines as a method of cramming much more functionality into your programs by saving space, often ending up using every last bit of available storage, where are you going to stick your stack?
If you can write to the program-memory, why can't you write in some different ("random") memory location to store the jump back adress?
maybe the architecture didn't offer that addressing mode, only direct addressing? that sounds horrible
Der Jens The EDSAC had no indirect jump.
I remember having to push the program counter or PC out to the stack, then jump to the routine, then in the routine pop the PC with the stack content +1 and go to that.
That is how x86-64 works. Not sure why they said modern machines have link register.
Well I used it on something outside the X86-64 - but a Z80.
kd1s Why would you use that on a Z80 that has CALL/RET instructions?
With a stack you have the other trick, which is to push the address of the next subroutine you want to call as the return address of the subroutine you're calling first.
+glorygeek Some other architectures have it, e.g. ARM. If a subroutine being called doesn't call any other subroutines or itself, it's possible to use the link register for the return address instead of stack, which is a lot faster. It's kind of optimization, really.
I would say this would be the precursor to the idea of a THUNK. Essentially, a quick instruction overwritten on entry or exit of a routine. Windows had to deal with thunks a lot when evolving from 16bit to "enhanced memory paging" to true 32bit addressing architectures.
Is where the Term Offset comes?
I can't explain to anyone I know why I would stumble upon this and yet watch to the end with fascination.
I was waiting for him to say "self-modifying code".
Doesn't using a stack in the CPU mean you have a limited stack depth for recursion? Is the reason you don't store that in say a linked list in main memory that it would be too slow?
Actually, the stack is not part of the CPU, it is also in memory. Recursion depth is only limited by the size of the stack, which is just a reserved area in memory. The stack is way simpler than a linked list, as logically neighbouring elements are also neighbouring in memory. You don't need the overhead of saving the link pointers between the elements. Also, a stack won't fragment the heap like any object based graph would.
Built-in stack rather means having a dedicated stack pointer register and push/pop instructions. All of these can be implemented in software using very few basic inc/dec and mov instructions. So a dedicated instructions are just more convinient.
emgoz is this something implemented at the OS/runtime level, or in hardware?
Hardware. In CISC architectures most often the jump-to-subroutine (jsr) will push the current program counter onto the stack and return (ret/rts) will pop it off again automatically. RISC architectures oftenly use a link register as mentioned in the video, as it does not require a memory access. If you want to perform recursion, you have to push the return address onto the stack in software (either using a dedicated stack pointer register or not). Minimalistic architectures neither have link registers nor a hardware stack, so a jsr will leave the return address in the accumulator and you have to take care of them in software as well, no matter you want to recurse or not.
Not entirely correct. Some CPUs had multi-level stack registers in hardware and it still exists today in micro-controllers. The main benefit is that you can program your device without any external RAM and only use ROM for the program. The man drawback is as mentioned a limited call depth, including recursion depth.
That's not what having a Stack Pointer or Link Register in the CPU means, though. They're just bookmarks to some location in the actual program memory (RAM for the SP, but as likely to be ROM as RAM for an LR), either one that you'll soon be returning to (LR; you'd only use it for fairly simple jumps, as using it for anything more complicated would involve saving the value out somewhere and by that point you may as well use the SP), or one that holds the address of the last place you jumped from as well as possibly a bunch of other info (SP).
In this case, however, we're _inventing_ the GOSUB, on a processor architecture that was only really designed for linear programs and whose jumping capability was meant more for implementing loops instead. So we've got to get a bit dirty about it. And the "stack depth" is only ever really going to be, well... one. Which is a lot when up until now it's _always_ been zero. Maybe you could push the boat out to two or three if you get really fancy. There's just not enough memory space to write programs any more sophisticated than that, and certainly no room to waste on an actual stack when the preexisting, entirely necessary jump instructions themselves can have the required data injected into them.
(it helped somewhat that the memory word structure of the machine, like a lot of early computers, was a bit of a strange hybrid where every location held an instruction, a bit of data, and sometimes an implicit jump command where the address of the next instruction to run was burned in to every single "line". So you could just say "write XYZ to the data section of memory address ABC", or maybe write it to the jump section, without affecting any of the rest of that memory word, or more than likely even consuming any extra storage space than was already being used...)
2:21 is kinda adorable imo
I like assembly, but I still remember when I first used a BASIC which had GOTO but no GOSUB (well, nothing about it in the docs anyway).
So I ended up setting a return label, then GOTO routine, which would finish with GOTO the return label. Messy.
Then I discovered Z80 assembly, then IBM S/370, then x86 :-)
Why no mention of modern call/return instructions where the return address is placed on the stack at the time of subroutine invocation so that no link registers are required?
+1. It turns out link register is a bit more modern, because it's used in ARM as it is faster than stack. Still, ignoring x86 is a mistake.
given how he talks about writing over program memory, I wonder what insights the instructor has on the Meltdown & Spectre vunerabilities. No disrespect to Dr Bagley's video, but this insight puts it in a new light. I'd also note that Dr Bagley has his own video on the Wheeler Jump from last year's Computerphile Essentials series.
If you can write the accumulator into program memory, why couldn't you write it onto the stack, and do recursion that way?
What stack?
wehh a Link REgister is faster... but the stack allows you to nest subrouts inside eachother. you can't do that with a Link Register because it only remembers the last address before a CALL Instruction
Wait... so that method is just overwriting memory right? Why not use a designated memory location for the return address?
GLaDHuRriCAn with the EDSAC, you would in the end have to patch the jump that performed the return - the machine had no indirect jump!
@@RandallHayter Could you write to the SCT register to perform a jump?
@@bryede The SCT was not software writable.
Edited to add: of course branch statements DO write the SCT. This is what the Wheeler jump uses. I don't have the EDSAC instruction set memorized and haven't studied it in years, but their must be a copy online somewhere. Take a look and you will understand the limitations.
Is this technique a primitive example of metaprogramming?
What's his shirt say?
Malcolm Arcand its his log2(10)=3.32 shirt. Worn before think when discussing Von Neumann Edit: why use binary at 3:32
Log (base 2) 10 = 3.322
Caio Sobreiro much nicer layout
Yo Malcolm love ya work. (Shredsauce)
He said in one of the previous videos that he would buy a shirt with this equation (log2(10) = 3.322) if anyone ever sold those. So I just sent him one 😁
Yeah. ...
No recursion, sure. But you can't have multiple processors executing same code either.
True but nobody was even thinking of making multi CPU computers back then.
Sharing access to the other parts of the computer would have taken a lot of extra hardware back when every transistor was valuable and other parts of the computer ware likely too slow anyway to have multiple CPUs use them.
For quite a while memory speed was the limiting factor in computer performance. Once that was solved CPUs started getting faster and faster rapidly until they got well in to the GHz range and at that point it became harder and harder to create a faster CPU and since bilions of transistors was no problem the easy solution to making a computer faster was putting multiple CPUs in it.
Wheeler Jump ; The original self modifying code.
Remember to use a mutex if you do this in muti threaded code.
Please give us software engineering & architecture lessons in your style.
Why not just use a stack pointer? Just reserve some bytes and have a memory address hold the value of the first memory address of those reserved bytes, and make a macro so when you want to "call" a subroutine, the macro expands out into (1) storing the program counter into the memory address the stack pointer is pointing to, (2) then incrementing the stack pointer, (3) then jumping. And the "return" macro would expand out into (1) loading the value the stack pointer is pointing to, (2) incrementing that value by some fixed amount, (3) decrementing the stack pointer, (4) jumping to the newly calculated memory address. It's not much slower and allows for recursion, the depth of the recursion allowed depending on how much memory you allocated for the stack.
For example, pseudo-assembly code:
main:
'call here
ld a, pc
ld b, (stack_pointer)
ld (b), a
inc (b)
jp subroutine
'more code here
end
subroutine:
'some code
'return
ld a, (stack_pointer)
ld b, (a)
dec (a)
add b, 3
jp b
stack:
.rb 5
stack_pointer:
.db stack
It's fast and allows for recursion and is easy to implement even on primitive machines.
Yes -- it's perfectly plausible to make your Initial Orders be more adventurous in the sort of ways you indicate. So why wasn't this done on EDSAC I?
Answer: because there was SO LITTLE memory available (only 1024 words) that users wanted every single word of that memory and would happily vote for losing only 42 words of it to Initial Orders II rather than several hundred words (say) being lost to some more powerful Initial Orders III.
I would also imagine that the ability to implement a subroutine of any sort was such an improvement that it was considered sufficient for a time, especially when you consider the size of the programs we're talking about. You can always work around the need for recursion by adding routines. Implementing a stack purely in software would probably be just as large and would slow things down.
Wait, why can't you just push an address to the stack in memory and pop it back off at the end of the subroutine?
Elias Simon Because that had not yet been invented when Wheeler came up with this jump concept.
Regular random-access memory had not been invented?
Elias Simon Turing had described the mathematical construct of the stack at roughly the same time the EDSAC was being designed (1948), but it was a very early machine (the second stored program computer ever). It had no stack pointer. It used mercury delay lines for storage. No indirect jump. These were pioneer times.
Or in other words: it's 1949. There is *no* stack, there is *no* stack pointer, just the same as there are no index registers, and indeed no general purpose registers other than the accumulator ( *everything* runs through the main memory, like the ultimate refinement of the 6502 ideal; the accumulator only exists because without it you have no way to add the contents of two or more memory locations together before storing the answer back into RAM, and thus would have no computer at all).
If there was, there wouldn't have been a problem, as you could have just used _that_ to hold the return address then shunted it (+1) into the PC to return from whence you came.
You need to remember that a stack is an automated machine within modern processors. It has a pointer register and it performs reads and writes to memory with automatic increments and decrements to that register. In the 1940s, such a feature would mean another rack of tubes.
How did named registers come about? Why don't CPU makers just say, "here are a bunch of 4-byte registers, use them however you want?"
Probably just convention
These names indeed are just convention, in CPU they are usually referred to by their indices encoded in instructions, e.g. R0 = 0000 (binary), R1 = 0001, R2 = 0010, R3 = 0011 ... R15 = 1111. Some instructions may work with a smaller subset of registers and encode them slightly differently, e.g. if some instruction works only with R5-R8, it may number them from zero and use fewer bits to encode them: R5 = 00, R6 = 01, R7 = 10, R8 = 11.
The names are used in assemblers and programming languages for convenience.
Thanks Artem. Seems "some instructions may only work on some registers" is the main reason.
Necessary in its time but a most appalling bodge. Not only does it prevent recursion but also re-entrancy - so for example such a subroutine won't be ok if also called from an interrupt service room also, or be shareable by processes in a multiprocessing operating system.
When it was improved I'm not sure, but the PDP-11 had a jump to subroutine instruction, that in the case of JSR PC, Destination automatically saved the program counter on the stack before entering the subroutine and later a RTS PC return instruction popped the address off the stack and jumped back.
That, in my opinion, was a much greater advance.
We're talking about a machine made out of tubes in the '40s. There's no concept yet of interrupts or stacks or multi-anything and even if there were, it might not be worth the hundreds more tubes it would require to make it work.
The world is good.
Am I the only one wondering why you couldn't just use a jump register instruction (jump with the contents of a register as the argument) instead of writing self modifying code?
Subroutines didn’t really exist before edsac
i used to write self modifying code. now it doesnt work on linux since it has the said protection and segfaults. So when I wrote the graphics dithering code for the Twibright Links, instead of coding one neat self modifying routine, I had to write many of them, for each possible video memory format one. Way to go, code bloat. So that companies can sell more PCs.
Reminds me of the BASIC interpreter in the VIC64, which used self modifying code. There was a short bit of assembler in zero-page that loaded next byte of BASIC to be interpreted. The load used absolute addressing, and then the address part of that instruction was treated as a variable, and incremented.
Why not save it on stack??
Ajinkya Kamat You would need a stack for that and the concept of a subroutine stack was still to be invented!
Randall Hayter Ohh.. History can be harsh to the residents of the past
my god.
computerphile.
computer.
file.
Called a "Return Jump" or "Exchange Jump" ... ala Seymour Cray
Is the wheelers' jump threadsafe? What if there are multiple threads wanting to execute the subroutine?
Paula J. Bean that would create the same problem as recursion. Calling the same routine before it has been returned from, albeit from another thread.
Paula J. Bean It is not reentrant. Thus supports neither recursion nor parallel execution.
These machines wouldn't support multiple threads. It's like asking if Roman ships were bulletproof.
he is wrong. rewriting code at runtime is a standard industry practice. just google for UPX as the executable packer almost everyone uses