What is Bootstrapping? - Computerphile
ฝัง
- เผยแพร่เมื่อ 18 มี.ค. 2014
- A little bit of magic - bootstrapping, allows the separation of code and machine, allowing one single piece of code to run on many different machines. Professor Tom Rodden introduces the idea.
EXTRA BITS - Complexity: • EXTRA BITS - Complexit...
Reverse Polish and Stacks: Coming Soon
/ computerphile
/ computer_phile
This video by Sean Riley and Brady Haran.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradychannels
"there come a time when you understand you can't understand everything about computers" - man, the feels. That's been my life's quest, and I've reluctantly come to the same conclusion :(
The quintessential instance of bootstrapping occurred when we needed to create the first compilers (actually, "assemblers") which would allow programmers to write native machine code in a textual format. Before you could write 6502 assembly language, someone first had to write a 6502 compiler in pure machine language, or do the translation from assembler to machine code by hand. Of course it's even possible that the first 6502 compiler was written on a Z80 or any other existing architecture. Once the 6502 compiler existed, it could then be improved, writing the next version using that initial hand-compiled version.
Taking the Atari 6502 computers as an example, their first 6502 assembler was probably a reference assembler that had been hand-coded by the chip-maker. But they quickly used that tool to build a better assembler, and used that first Atari-based program to write the core Atari OS, the code to read and write to its memory-mapped custom chips, to handle tape and disk I/O, keyboard polling, etc. They used that first assembler to create a better Macro Assembler (one which allows coders to combine blocks of assembly code into reusable units) as a full Integrated Development Environment (IDE) combining file management, editing, assembly, debugging, etc. They used this tool to write AtariBASIC, a simple high-level language. And other developers used the assembler to write the "Deep Blue C" compiler, one of the earliest C compilers. The "B Key" compiler (which turns AtariBASIC into small and efficient bytecode that runs much faster) was itself written in AtariBASIC, then used to compile itself, so it's a bootstrap within a bootstrap.
So very quickly the bare 6502 chip became a computer with innovative audiovisual hardware and a multi-language code platform, all bootstrapped from that first early reference assembler. Today we don't need to bootstrap new chips, because we can just make a GCC or Clang plugin that spits out the right machine code. But we can always get a similar experience by building 3D printers that make new 3D printers, robots that construct newer and better robots, tools that allow us to make better tools...
This explanation is a 1000x better than that of the professor and it takes a fraction of time to communicate a lot more detail. Great comment.
Gotta love these Turing machines...
Since bootstrapping can have so many meanings in computing, this is what he's actually referring to: en.wikipedia.org/wiki/Bootstrapping_(compilers)
The article also cleared up some questions I had after watching this video.
This video answers one of the most common questions people new to programming or computers in general ask. Thanks a lot!
The way he says it sounds like you need different code for each individual computer, only later (when Brady gets confused) is it made clear that it's about different architectures
Java and C++ were both bootstrapped in C
But the egg obviously came before the chicken by millions of years.
There was no first chicken, but if there was it would have been inside a non-chicken egg (if you define a chicken egg as an egg laid by a chicken) or it would have been inside a chicken egg (if you define a chicken egg as an egg with a chicken in it).
In all cases the chicken could never have come before the egg.
The chicken had to be bootstrapped by a non-chicken :-)
You should do a video on Operating Systems!
Virtual Address Space (and translation), Processes/Threads, Program memory etc.
I think that the OS is often just viewed as "Something I can boot, which lets me click things and access files". A more in-depth view of the OS would hopefully clear up many of the misconceptions.
Though it is also important to understand how the low level stuff works because their restrictions and limitations doesn't vanish when using high level language.
For example CPU cache. An algorithm can be correct and run slowly because it isn't optimized to fit in the CPU cache.
Caching is generally done by the system. It's convenient to know how much of your code will be cached, but it's more important to understand efficiency on a high level. We don't really study efficiency on a low level -- it's already about as efficient as it's going to get.
SniperReady That's true in case you're using managed language like C# or Java, which should mean that in the first place you're not making a resource demanding program.
No. I mean that any language, even C, is compiled to a set of instructions ( and the compiler can execute further optimization levels using the o flag ) that will essentially make the code as optimized as possible. YOU as the developer don't have any control over how the cache is used.
You're right, however, that having some insight into how a particular machine caches and how much cache it has might be useful, but that defeats the purpose of portable code. Efficiency is done at a high level first and foremost because low level efficiency isn't portable.
SniperReady Which is also (among other reasons) why a lot of software for *NIX systems is shipped as high-level source code so you can compile it yourself and take advantage of the per-CPU optimizations
This reminded me of Ken Thompson's talk Reflections on Trusting Trust which demonstrates the most insidious hack I can imagine, where an exploited compiler adds a vulnerability to the compiled binaries of itself which can be potentially impossible to detect. You guys should definitely do a video on it.
No one has bootstrapped compilers in the *decades* since cross-compilers were invented. But every day, people bootstrap their computers when they push the power button.
0:40 I can die in peace now
Our bootstrap in 1973 was a punched card with 40 pairs of numbers (80 column total). It consisted of and FF to mark the end. The instructions on the boot card read 1 block from the disk, which then executed code to read more from the disk. Our line printer in the morning printed the 1'st few lines very uneven, so the same boot process was used to create a card that printed rows of E's on the printer to warm it up. That was machine coding.
For everyone out there wondering. The Egg came first. At some point way back in time some creature that wasn’t a chicken laid an egg that hatched Into a chicken. That’s how evolution works.
This video makes it sound way more complicated than it is - bootstrapping is just building a compiler with itself. If a compiler can build its own code, that is, if it can bootstrap, it is called self-hosting.
Years ago it was possible to use 6502 machine code directly on my Acorn machine. "LDA"=Load value A. "JSR" Jump to Subroutine in register. and Many others all followed by a memory address or pointer to the Hi byte or Lo byte of said address. I forget now it was years ago, but it could be done if you had the patience and inspiration!!!
I hoped to see something about to boot sequence of a computer or something on the history of languages and compilers (from assembler to BCPL, C, and VMs languages). But still, that was cool !
If you understand evolution surely you know the egg came first.
"There comes a moment when you can’t understand it all, you can’t understand the thing that your building is so complex it doesn't all fit in your head."
And this is precisely why I still program Apple II computers, I CAN understand the whole system. I don't need a compiler, don't really need an assembler - I know the 6502 op codes, where everything is in memory, exactly what the program is going to do at any given time.
Wow! That's advanced bootstrapping! Many early machines didn't have a ROM. Bootstrapping was the sequence of instructions that were individually (manually) set into RAM address by address via a sequence of switches. This allowed a tape to be read which loaded the drivers and operating system when the computer was switched on or rebooted. Have a look at a PDP 11 for example.#
On a lighter note of course the rooster came first.
Great video! As a web designer I'm constantly baffled how my html and css code gets interpreted by computers, smartphones, tablets and TV's and somehow looks everywhere how I wanted it to look. Just imagine all the calculations that have to be done to convert the code into a color-matrix which can be sent over to the display!
It's interpreted by the browser which is built in the operating system's native language, which is compiled to binary code, which is a series of machine instructions for your particular architecture.
It is definitely quite complex. You've probably found it doesn't look very similar all over the place because devices are so different. Your 255-red is probably pretty different than a TV's 255-red. :P
Yeah, I guess I wasn't completely precise there... the colors look different on every screen of course (I don't think 255-red is even in the broadcast save color range for television)! What I ment was, that if you write a responsive desing for a website, all your content is in the right place and order on every device. Take for example this website I'm currently working on ( schmuckzauberwelt.ch ). The frame around the site build up from 4 different frame parts which are stiched together seamlessly and therefore look like a single frame around the website. It even uses only two images as assets, which each get turned by 180 degrees for the third and fourth frame part! And it just works everywhere...
I have an idea for a video: About how emulation works. For example, an emulator that runs software made for a different system, like a video game emulator.
You cannot understand the entire tech stack, that is the curse of the computer engineer, and the source of so many problems
excellent work Prof. cheers.
Computerphile - Thanks much for the reminder of the joys of writing our own bootstrap programs for the Honeywell 2000 and having to get the entire program on a single 80 column card or hand entering it through the console keyboard, if the cardreader was down for some reason. And having to run the bootstrap every time the machine was turned on. No such thing as a Load N Go Program at that time.
I must be old school since I relate bootstrapping as part of making a computer usable as a computing device. IE the series of programs needed to allow the machine to operate from when it is turned on. Compiling, which this video talks about, is something different. Now purely in the abstract sense, these are related since the logical question is how are the bootstrap programs written?
Bootstrapping can refer to one of many things[1]:
*1*: The process of running code in increasing complexity from turning the computer on. That process is, to over-simplify,
Power button sends a '1' to the motherboard->motherboard activates CPU->CPU loads ROM-BIOS->Boot Loader->Kernel->Operating System
That is an oversimplification, of course[2].
*2 (what this video is discussing)*: the process of porting a language to itself. In the case of C, for example, its compiler, and probably its libraries, had to be written in a different langauge. After the first compiler is made, then you can write C code to generate programs. Awesome! And with that, now you can write C code that generates a program that compiles C code. A C compiler written in C. Doing this multiple times, the compiler can become increasingly sophisticated, and thus you are making the language "pull itself up by its own bootstraps"--you are bootstrapping the language.
Technically, the second definition is more 'old-school', as C was created by the eponymous K&R (Dennis Ritchie and Brian Kernighan) in the late 1960's during UNIX development (development started in 1969, and a working C implementation was 'released' by 1972)[3]. Porting languages to themselves, by that time, was already something that had been done before[4].
The concept of "booting up" a computer had only existed since the BIOS firmware interface came into the picture, when IBM started marketing their PC, which was in the 1980's[5].
*Sources*
[1] Applications of the term 'Bootstrapping' -- en.wikipedia.org/wiki/Bootstrapping#Applications
[2] The BIOS boot process -- en.wikipedia.org/wiki/BIOS#The_BIOS_boot_process
[3] The C programming language -- en.wikipedia.org/wiki/C_%28programming_language%29
[4] Bootstrapping in Software development -- en.wikipedia.org/wiki/Bootstrapping#Software_development -- "Bootstrapping in program development began during the 1950s"
[5] IBM PC Origins -- en.wikipedia.org/wiki/IBM_PC_compatible#Origins
I love that accent
Enjoyed this, good description about high/low level languages. However I must admit I thought bootstrapping was loading and passing of control from the boot loader firmware to the OS?
I wondered what my flatmate was on about when I was talking about Bootstapping in the statistical sense, as he was talking about this
Interesting - never heard this use of bootstrapping before. 32 years ago when we were taught computing at high school in the UK (in the days of the Acorn BBC B microcomputer), bootstrapping was used to describe the powering-up process of the computer, whereby it checked itself out (what we'd call POST now) and launched the BASIC interpreter from ROM. Do people still say 'booting up'? That comes from the 'old' use of the term bootstrapping.
well explained, if you think he was chatting crap you either hate our eglish accent or your too young or your programming and hardware knowledge is from youtube... This video was all facts.. the new form of bootstrapping is people who use complex code they know nothing about but use it to do the things they know it can from a base binary level, tweak it abit and maybe it works, thats the bootstrapping some of you are referring to right, so called xbox hacking etc, that aint boot strap at all, i think many used the bootstrap in the wrong way and got many beginners hooked onto something way over their heads, bootsrapping should be seen as a boot that has a particular configuration made to do whatever its meant to at its best and tries its best not to have any external dependancies to boot..
I was recently looking into a BASIC compiler (because I'm working on a LLVM front-end as a challenge). The compiler was written in BASIC and I had to download the bootstrap version.
This is really interesting!
This is GOLD.
This guy's voice is so great.
Mmmmmmm low level stuff. Keep it coming. :)
@Brandon Best. Oh I am aware of how compilers work. I remember compiling GCC itself on unique hardware to get GCC runnable on that unique hardware. I was commenting on the fact that my old school brain relates bootstrapping to turning on a computer.
Isn't the answer to the chicken and egg question obvious? If the chicken came first, it came from an egg, so thus the egg came first!
There is no dilemma over the chicken and the egg. The egg came first.
Indeed, but it wasn't a chicken's egg.
Back in the the 1970s I first learned how to write binary diagnostics for an Interdata Model 70 (an IBM clone) which needed to be entered via front panel switches. Alternatively, you could input the 50-sequence (a bootstrap-loader) which would bootstrap a small librarian from tape with which you could run a collection of pre-written diags. A year later we bought a firmware module which contained a copy of the 50-sequence so we could boot faster. It seems to me that this gentleman is using the phrase "bootstrap" in a different context (i.e. using software tools to make better software tools)
"Reverse Polish and Stacks: Coming Soon" - that's a great ideea!
Ah, another opportunity to train understanding english accents ;-)
You mean Scottish accent?
sounds more Scottish to me
Matthew Mitchell No, it's an accent of the English language, there is no such thing as a Scottish language (if you don't choose to call Scottish Gaelic Scottish, and then this would obviously not be an accent of that). The fact that Scotland isn't England is irrelevant, you still talk about an accent of English when talking about american English, right?
Matthew Mitchell Aye
Matthew Mitchell I thought he was referring to English (language) accents.
I initially thought this was about the statistical analysis method bearing the same name :D
Java probably isn't the best example since it gets converted into bytecode and is executed via virtual machine instead of being actually compiled...
I ran into this concept when writing about phylogenetic comparisons...I still have no idea...
Since all this computer architecture is built upon itself, does this mean there are inefficiencies that get multiplied throughout the entire code from low level to high level? If so, is it possible to rewrite the very low level code so that it is of maximum efficiency? Or are we stuck with ancient old code because it would be impossible to go back and change it without changing the entire computer industry standards?
To my knowledge - bootstrapping is the phase where the machine is going to start the first piece of code - and needs to know where to find it - and since the machine doesn't know for sure - its told where to find it - either from floppy or some harddisk or tape.
hardcoded instructions make the assumption where to find this piece of code
the first piece of code loaded from the media - like the bootsector - master boot record - if such exists - since those are late implementations ( iow - early machines didn't read from a media like floppy.. but a mechanical key selector - or relays - or papertape -
the BIOS is the 'static' code where the machine can find assumed settings - like where to find the first media to boot from - if you find the bios code for the 8088 (ibm) - and you debug this - you will find very primitive instructions that test the mainboard if all items are working or available.
That accent!
The title of this video is misleading. Most of it is really about compilers not about bootstrapping. Bootstrapping is the process of initiating the machine code - the operating system within the operating system. It is often responsible for the switch from physical addressing to virtual addressing. The bootstrap process in DEC's VMS operating system is one of the most elegant pieces of code I ever saw.
Also bootstrapping is the process of compiling a compiler within itself. Maybe they mean this?
That is one kind of bootstrapping. There's also stuff like the C compilers which are written in C. Somehow there had to be a first C compiler.
IchBinKeinBaum The first compiler is written in machine language, not in C (or any other higher level language). You can then write the C compiler, compile it using the machine language compiler, and THEN use it to compile subsequent copies of itself.
Now do a statistical bootstrapping video on numberphile :D
bootstrapping may have this specific meaning among compiler-writers, but in a much more common sense it refers to what happens when you turn on your computer
a chip on the motherboard, called the BIOS, runs a self-checking and hardware identification program, then if all goes well, the operating system is loaded and takes over
it is called "booting" for short, and the word is a misnomer anyway because nothing is causing its own self to move or execute
its just a logical sequence of events like everything else that happens in a computer
when you think about it nothing can "pull itself up by its own bootstraps"
anybody know the original context of this phrase? it must have been ironic
Exactly... I like Tom, but I didn't like this explanation.
The term means doing something that is impossible, because, for example, if I have to load code into memory that allows me to load code into memory then how is this possible? The answer, as you said, has nothing to do with the chicken-and-egg deal... it simply loads the primitives from the bios (which is firmware so can load without loading anything before it), and the primitives can then load the O/S, which takes over controlling the system.
Dave, yes this is the meaning I've always understood by bootstrapping too. This definition was a new one to me... learning something new every time on these vids! Great channel.
inception via compilers and code.
The first chiken egg comes from the Red junglefowl "Gallus gallus" It is thought to be ancestral to the domestic chicken.
The egg came first!!! An animal that was not a chicken laid an egg, the cells in that egg had a genetic mutation that made it a chicken and it's parent not a chicken. Thought this was well known by now
How about a video about flash memory? (SSDs, USB sticks and the like)
Very cool.
Mind Blow!
How was the first ever compiler compiled if there wasn't already a compiler to compile it?
I think that makes sense. LOL
Just like with the chicken and the egg, the egg is the idea. The blueprint of the chicken. The egg came first. (Reasoning, without a cell dividing there is no chicken. The egg starts out as a cell)
So now then, the idea that spawned binary logic (around the year 1705) was the egg and from that, the first logic gate was realized.
That has given rise to ever more complex machinery which eventually led to electric powered logic gates.
At one point in time, someone made a "simple" computer capable of being used to write more complex programs running on more complex machines that in turn were used to write even more complex (or higher level) software.
We are not quite there yet, we still need human intervention but some time in the future we will have machines developing more advanced machines on their own using whatever set of "rules" to guide them towards progress.
At that point, we humans won't even be capable of understanding the process. We will just accept that it works, no matter how badly optimized it is.
We will just say "hey, i would like XYZ" and a machine will build it for us.
actual information about bootstrapping is from 5:00 to 7:00.
Totally unrelated but just as fun to think about: Bootstrap Paradox Time-traveling related.
Is this related to "booting up" a PC?
For anyone who wants to get that feeling of "This is madness" go do Open security training x86 and Life of binary course. You can rage on me when your brain melts :)
bootstrap bill
isn't the program written for the architecture such as x86 hence why the code works on all x86 as all manufactures conform to the design.
Okay, i am very confused, okay. Thank you, okay.
nice
Really interesting video, but found it very confusing and hard to visualise without some visuals to accompany it.
The first language is the hardware architecture, it is just logic gates and a set of binary flags to trigger instructions sets.
I have to say that after a year of IT stud I still have trouble understanding the term "Abstraction". Much Like I had problems, and still do to some extent, understanding "Entropy" when studying Mechanical Engineering
75IFFY there are different kinds of abstraction. One common kind is black box abstraction where there are hidden details "inside" and a simple outer presentation or "control panel". The term "meal" is a category abstraction. It doesn't refer to today's breakfast at my house or next week's dinner at yours, those are "concrete" examples of meals. Many kinds of abstraction introduce an invented "thing" - often a kind of metaphor - whose properties are defined in terms of other abstractions or in terms of concrete things (like 1's and 0's). Ultimately there must be a concrete existence to the abstractions or you're just adrift in pure theory. The purpose of abstractions is to remove detail so that you can concentrate on a subset of the problem space. Good abstractions allow you to forget or remain ignorant of the internal details, but an old piece of software wisdom is that "all abstractions leak". Every now and then you will need to understand how compilers actually work and what exactly is going on inside the black box. Even at the machine level, the "addition" arithmetic operation is an abstraction, typically built from "logic gates" which are an abstraction on top of electrical components. You don't need to think of electricity very much when switching 1's and 0's though you will need to think of addition.
I hope that time never comes
Wrong! Bootstrap code has nothing to do with compilers or other programs. It IS specific to the machine it runs on. It refers to the first few instructions on the 'rebooted' machine which load the core filing system which is then used to load whatever program is desired. Nowadays this is held in firmware but it was initially keyed in by hand using physical switches and so was as small as possible. It 'loads the loader'. Everything else (even the OS) is applications software.
I also think it was a bit disingenuous to use Java as an example language. But Java can be compiled in the traditional sense as there are plenty of Java compilers available. It is true that the larger use case of Java is through the JVM.
when you make machine learning code and you get 6 or so vectors. It gets hard to wrap your head around
Brady is that you?
So java has f-statements...
hmm, yeah, this problem I've had...
I heard once from a ASIC manufacturer that there are not 2 100% identical chips because impurity ( en.wikipedia.org/wiki/Wafer_(electronics) but 99.99999% is ok I guess ;)
You can't understand it all? My brain doesn't like that, but it is very true.
Java gets compiled into bytecode and run on a virtual machine. Hmm
Well it still is machine instructions, which are compiled from higher level language.
...And how do you think the compiler works?
Say you write a compiler in Java, to compile Java programs. How do you compile your compiler when it itself is a Java program? You certainly can't use your compiler to compile itself (pull itself up by the bootstraps).
Solution: Bootstrapping!
Of course you can use javac to compile a compiler. Why wouldn't you be able to do it?
Vytautas Galdikas I'm not sure your comment was a reply to mine. My comment was a reply to rjday753. But here goes:
Oh you can. But javac itself is written in java. So you'd need bootstrapping in order to compile javac.
I was thinking of the same thing when he said that
Interesting. With what accent does he speak ? :)
Nowadays nobody does this kind of bootstrapping for new platforms because it would be silly. People use cross-compiling for this. For instance I don't think anybody writes mobile software using smartphones. Folks just use some PC based SDKs and IDEs which output packages that mobile OSes can install.
cheeky bit of hackertyper.net at 2:39 :P
Machine language should be the first thing students learn in the first place... Make it low level translated but java basic or C is really not the hardware level programming.
The overhead is really killing the CPU.
What was there first, the chicken or the egg? Thats and easy question. It was of course the egg. Chicken are birds and birds come from reptils (i.e. dinosaurs). Dinosaurs layed eggs, because they were reptiles. Conclusion: Stupid Question
yeah, but which came first, the chicken or the _chicken_ egg?
(still the egg, because the first chicken had to come from an egg, whereas that egg could've come from a not-quite-yet-considered-a-chicken)
***** It depends on how you define chicken egg, is it an egg laid by a chicken, or an egg containing a chicken?
While I agree, you can simplify this answer by just saying "dinosaurs laid eggs", which people tend to understand immediately.
Except, the offspring of every parent was of the same species as its parent. In biology, I find it is not so simple as the "chicken or egg" problem. :-)
Instead, it is more useful to think of all life originating from the first self-replicating molecule. :-)
In programming, I would imagine it is the same principle. There exist a set of instructions from which all programs originate. Compilers arise from these instructions, allowing us to build better compilers and from those compilers come better programs and better compilers, all that point back to simple instructions (strings of 1's and 0's). Binary is like the DNA sequence of all programs!
***** I used to think that way as well, but given how evolution works the difference between the very first modern chicken and the 'not-a-chicken' that laid its egg would likely be indistinguishable from each other in appearance, and at the genetic level would probably not show much more variation than you would see between another child and parent of the same species. Whenever I think about this question, I find myself asking, "What exactly IS a chicken in the first place?"
Chicken or egg....neither came first as chickens evolved from dinosaurs and dinosaurs evolved from fish and bacteria so there you go
Anti first !
Kyerrnall
im honestly ashamed of myself that i don't understand this.
Am I the only one who is incredibly bothered by those blinds?
Where does his accent origin?
What is an f-statement?
..
Just kidding.
I must be getting old because that is not how understood bootstrapping at all. I thought the bootstrap was the firmware installed of the motherboard that exposed the hardware of the machine and a device on which could run, so the incoming operating system which one was trying to install could do its stuff. As I say I'm old School and things probably move on with out consulting me.