Bootstrapping with T-Diagrams - Computerphile
ฝัง
- เผยแพร่เมื่อ 30 ก.ย. 2024
- How do you compile a compiler? Professor Brailsford starts to unpick the idea of bootstrapping.
Bootstrapping: • What is Bootstrapping?...
Factory of Ideas - Bell Labs: • The Factory of Ideas: ...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottsco...
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
I'd like to thank all those of you who have included condolences in your comments. Yes, I lost my dear wife of 52 years 0n 27th May 2019 (her 76th birthday) Despite the sadness we tried hard to make it an up-beat occasion. Certainly Julia gave me huge encouragement in everything I did for Computerphile and it was just wonderful for me to know, during the funeral, that the A/V systems and the HD recording were being handled by those Computerphile stalwarts Sean Riley and Steve Bagley. Many thanks guys.
My Condolences to you professor. It is a joy to listen to you explaining difficult topics like compilers. I hope you will find strength to continue in your follower base from computerphile, which as one can see, is huge.
I'm so sorry to hear that, hope you the best, you are one of my favorite hosters of computerphile.
(If something is misspelled or grammatically wrong I'm sorry, not an English speaker, again, I'm sorry)
You are a beautiful person sir!
I'm so sorry to hear that... I wanted to thank you for contributing into such a beautiful video which I could actually and potentially understand the best. Pleased to watch your hard work. Be strong, professor.
ProfDaveB condolences
My condolences to professor Brailsford. Losing a loved one is one of the hardest things in live. I wish you all the best.
It seems that the quality of the executable produced by an assembler depends only on its assembly-code input. An assembler takes each instruction as-is and makes it part of the image. You can consult an op-code table and determine how each instruction has to be represented in the image. It's not like a compiler that could implement a statement in different ways, or even decide the statement unreachable and not implement it at all.
Never trust someone else's code. Always start with 1s and 0s.
Professor Brailsford is a pleasure to listen to.
My condolences.
He died?
@@LittleRainGames no, one of his relatives died. I am not sure which.
My condolences, professor. Thanks for the lesson and I wish you the best.
This software bootstrapping process is akin to the way high precision machine tools were developed over the last couple of centuries, using early, crude lathes and milling machines to create parts for ever more precise lathes and milling machines. Mankind has come a long, long way from using sticks and rocks, and the journey has been difficult.
very true analogy
Yes it is essentially the same process.
I was thinking of precisely this! :)
Prrof is like the David Attenborough of software, even sounds alike. 🤔
He's both a fundamental contributor to the field, and an awesome explainer and presenter. What a joy to visit with someone with a life passion spanning so many decades. May we all be so fortunate!
My condolences to Prof. Brailsford in what is certainly not the best of times. I hope he takes some comfort in the fact that his videos and his pedagogic skill are unparalleled in getting me excited about whatever the subject matter may be, even when it's something I already know.
What happened??
@@rohithkattamuri4019 Julia Bailsford died, see the end of the video. Condolences from me aswell.
My deepest sympathy for your loss Prof. Brailsford. -When someone you love becomes a memory, that memory becomes a treasure.
I'm sorry for your loss Prof. Brailsford.
What happened??
@@rohithkattamuri4019 @michael wittmann Julia Brailsford passed away.
Hopefully nowhere. Re: Anders Jackson "3ICE oh. Where can I see that?"
43 minutes ago
p.s.: End of the video has the dedication notice if that's what you meant.
Thanks for mentioning Julia Brailsford, and giving us the chance to share our love for The Professor during this time.
My own family has gone through a wave of "departures" this year, and it is truly a fact that "grief shared is grief diminished". The grief of departure is balanced by the joy of their having been here in the first place, especially as stories are shared. "Laughing through tears" is a real, and very special, place to be.
There is also the concept of cross compiling where machine A already has a c compiler and you use that to build an assembler for machine B.
My condolences to Professor Brailsford
The beauty of work by folk like Peter Brown in the early 1970s was the idea that you might design your own language that was specific to your problem area. Then use bootstrapping to port this problem specific language to other platforms as required. Nothing more complex than a text macro processor was needed, and if your macro processor was too simple you could apply the same technique to that tool.
I dunno , when i was studying this i just kind of got it , now the T diagram just makes it sound more complicated than it is.
Agreed. No idea how one can talk 15mins about that subject with so few details and still make it that complicated. And I don't believe it's the editing because the drawings themselves are not very clear to begin with. Probably he just not prepared it at all because it's so trivial to explain... ;)
Same here. T diagrams are making things a lot more complicated and confusing than they are. Very bad choice. He should have used shapes and arrows. One shape for source codes (including assembly code) and one shape for binaries. An arrow would go from one shape to another (often from a source to a binary) and would require an associated binary (a compiler or an assembler).
I'm about 1/3 into the video, and if they don't put the "T"s together like tetriminos, I will be very salty.
Reminds me of the GNU C compiler build process. It assumes you have a K&R C compiler available, and in the first build phase, you get a functioning GNU C compiler binary. But then that new GNU C compiler is used to compile the source for itself, thus producing a theoretically better C compiler.
Oh, those where the times. :-)
The last time I compiled GCC it has an option in the makefile to only rely on having linux-tools package installed that contains the local assembler and the linker. It didn't strictly require you to have any other C compilers available. The source code of GCC had a TCC (”tiny c compiler”) written in gnu assembler included that was used to build a compact version of GCC. Then that mini-GCC was used to build a full version of GCC, then the GCC was used to rebuild full GCC again and again from the same source code until the process started to provide the same executable as in the previous step.
@@Kirillissimus oh, those where the days. Memories. :-)
Pssst... hey kid wanna score a compiler with linker and loader huh?
SHHHH! not so loud, but yes, i want one, how much is it?
@@BertGrink Just a few thousand lines of assembler
They oddly look like *Tetris*-diagrams
Thank you for another great video. I am sorry to here about the Professors loss.
10:42. It is not quite accurate from historical perspective. First C compiler was written in newB (NB). newB compiler was written in B. At that time B compiler was written in B. Before that B compiler was written in TMG. TMG compiler was written in BCPL most likely, and earlier than that in assembler. The assembler is sufficiently easy so it can be implemented in assembler and then hand translated to machine code, or on other machine (i.e. in Fortran or whatever) with already working toolchain. Only about year later C compiler become self hosting, and was written in C and compiled by previous version of itself. Simple two-pass assembler can be few hundreds instructions. In late 60s and early 70s, nobody would translate that manually tho (it would take maybe a week or two, but was error prone), instead use some other machine (and possibly other language or assembler) to generate assembler executable and transfer it to the target machine (assuming you had an operating system, which you probably did not).
i dont understand this at all
I have never been as excited for a video as I am for the next one in this series. Compiler bootstrapping is such a fascinating topic and Professor Brailsford is a great presenter. :)
"Three attempts" (holds up four fingers).... "Three attempts!" (hold up 2 fingers).
at least the errors cancel each other out (the sum is 6, as expected)
The two hardest problems in CS is cache invalidation, the naming of things, and off-by-one errors.
ximalas CS is, as most know, the abbreviation for a game called ‘Counterstrike’.
@@HighestRank 😛
@@HighestRank "Counter-Strike", with a hyphen. That's how the game spells itself.
However, it seems to be a common mistake, so common that even some 'official' material calls it "Counterstrike".
but who wrote the bin compiler?
and what does quality mean?
The video he is referring to around the 10 minute mark is an hour long interview of Ken Thompson by non other than Brian Kernighan. Here it is th-cam.com/video/EY6q5dv_B-o/w-d-xo.html. Highly recommended!
The term "bootstrapping" came about from punched paper tape from a KSR-33 teletype. This paper tape was in binary and was usually hung up on a peg on the side of the computer. The shape of it looked like a teardrop loop similar to a "bootstrap" that were on saddles for horses. Thus you got up onto the horse with those bootstraps. Same as bringing up the computer from a "bootstrap". I wrote MANY a bootstrap loaders for various machines. Most tapes were not paper they wwre made from Mylar which was much more durable for many, many uses.
In addition an Assembler was 1:1. Meaning for every line of source code, it produced one binary opcode plus operands. Usually it made two passes of the source code. Assembler did have provisions for structures. I personally wrote over 250,000 lines of assembler code, and used to write complete applications such as a/p, a/r, g/l, payroll all in assembler and on a 48k mainframe. I wrote a banner printing program in 160bytes and used no o/s. Just raw mainframe power
Great explanation, but I'm still confused.
At the bottom level, someone manually had to write the instructions that are found in the bottom level assembler binary. Past that, everything is written at a higher level and compiled.
@@Boopadee Thanks, I'll have to watch it again knowing this. Then I will try and write my own bootstrapper for practice
It's compilers all the way down.
Thinking of you today, Professor
My condolences on your loss. Please take heart in the fact that for many of us, myself included, your videos taught us so much about computer science, and encouraged us to keep learning more. We wish you the best in life.
Professor, I feel my copy of "gcc" may have a bug, since it doesn't make that rattling sound when I compile; where do I submit a bug report?
it is very quiet, you have to listen more closely.
Sorry to hear of your loss, professor. My condolences from Morocco.
Much like Turtles, it's T-Diagrams all the way down.
It is not an infinite process; in the end - or actually in the beginning, when the very first electronic computer was started for the first time, there were NO languages at all except binary, which you entered by setting a memory address (by flipping switches), then enter the data/instruction you wanted to enter, also by flipping switches, incrementing the address, entering another data/inistruction word, and so on until you had a working program. Needless to say, this was a rather tedious process, which naturally led to writing a small program that could receive input from a keypad, typically in hexadecimal, and then using that to build an even better program that could tyake input from a "proper" keyboard. Once there, it was only a matter of time before the hfirst assembler was implemented, and as they say, the rest is history.
Sorry for being pedantic.
My condolences for your loss Professor Brailsford, I know it can't take the pain away, but I hope that the many messages of support from the commentators on this video give some small comfort through these trying times.
Its mind boggling.. my head is spinning. Hope to see a follow up on compilers and assembler
You’re an absolute legend, Professor. Love your lectures, very sad & sorry to learn about your loss.
my condlences proffesor brailsford...just learned about your loss
So sorry to hear about Julia.
I certainly liked the explanation in this video regardless of me being very confused about bootstrapping. My deep condolences to your loss, prof.
Sorry to hear of your loss. My condolences, professor.
You are an absolute treasure for all you do Professor. I'm so sorry to hear of your wife's passing.
Thanks, now I finally understand why the build process for GCC was so seemingly complicated.
Maybe I'll give it another try. I haven't attempted it since the late '90s. And it was abysmally slow on the x86 hardware I had access to at the time (running Solaris 2.5.1).
13:48 GTA Vice City Vibes.
So the point is to do it in stages. From ground up, which is starting with assembler, you create a simple language that gives you that much more expressive power that makes creating the next gen language that much better. It would take a few steps before resembling like a more complete C compiler.
The question then is, what initial "enriching" language features would you create at each step?
I suppose the act of having variables, local scopes, and subroutine calling would be a nice start.
Then, next gen, structs, proper argument handling in functions.
Or... instead of that, create a BNF parser/language at which point you can define languages.
Anyway, I'd love to drop by for tea to have this out. I'm a tad far away though.
My condolences, professor. Thank you very much for explaining this in such great detail, I wish you the very best.
My deepest condolences Prof. Brailsford.
You really can go quite far down.
I've written code, mostly due to a possibly somewhat ironic mix of stubborness and laziness, using raw hexadecimal values entered into a hex editor and saved as a file.
This is essentially doing the job of an assembler by hand.
But, rather obviously, it's still not the lowest level possible, because I used an editor capable of editing files as hex values...
And you pretty much run into that problem no matter what, hence the bootstrapping issue.
I mean, I suppose in theory you could've wired up some switches and circuitry directly to a memory chip, which you then attach to your computer (I've watched someone do that. - you set a bunch of switches, push a button, write a single value to a single memory location, and repeat.)
Of course, you can then argue about the design of the computer architecture itself, etc, etc...
But sticking with the idea that you've got a computer that provides the absolute bare minimum, that would be a monitor program, (essentially my hex editor, but simpler and working directly with the contents of the computer's memory), or, if it makes sense, for older computers, maybe some controls that allow you to manually put values into memory locations with switches. (a bit like the example I saw with an electronics project, but slightly more standardised and permanent in nature...)
Either way, you end up needing something built into the computer - either at the hardware level, or as an included software program...
Many decades ago I was too lazy to learn assembler, so I learned to program in DOS Debug, which converted Hex into op-codes. Somebody was kind enough to write this tool and include it on the distribution disk. Without it no progress would have been possible for amateur programmers, and commercial compilers were outrageously expensive.
My condolences Professor Brailsford. :(
R.I.P.
Just tell people about opcode already. Go deeper Brailsford! Go deeper!
7! 7!
Object code first! Then opcodes!
I love, how this room seems like out of the 70s xD And terrific content btw :)
I'm going to start calling my output "core images" next commit.
I had to explain this to my students so many times, this video would be a great aid on making it more understandable for them!
What books, papers or other literature are available, where you can read more about this?
But BIN subscript u is still unknown there is still a unknown entity as he said in the video that suppose dennis gave me the BINu to run the assembler code.
My condolences Prof. Brailsford.
I was trying to wrap my mind around what you were saying as I was mixing up compost for my garden. :-)
05:20 I think I'll pass on that Pessimizing Compiler, thanks all the same ;-)
Watched this for 15 minutes still have no idea how this works 😢
Oops, Professor Brailsford, it doesn't quite suffice to compile the code, you'd need a linkage editor as well to resolve storage addressing issues. Only after linkage editing you'll have an executable. A compiler translates a high-level level programming language to the machine code of the architecture you intend to run your program on.
I must have misunderstood the idea of bootstrapping: in the world I used to work in, bootstrapping was the sequence to start the the computer, like after flipping the power on switch, the hard drive starts, the operating system, device drivers, and whatever else is needed (thinking of transaction management systems) are loaded.
What a loss. Sympathies.
@sbcontt YT yes, like Professor Brailsford's talks very much myself. When I learned to use computers the terminals were hi-tech. I've used punch cards, terminals, PCs, laptops, tablets. I spent most of my professional life in the field support, debugging the runtime environments of wide-spread programming languages, on /370 or /390 architecture. I learned to program the big machines (then water-cooled), set up transaction monitors, program the PCs, worked on process automation, and then some.
When listening to Professor Brailsford it reminds me of my dad, when he talked about how computers work, in the 1970s. My dad was a field support specialist and knew the insides out of the software he was supporting, as well as the interfaces of the hardware to the software. Then in my early teens I decided that I wanted to be able to command these machines. And I did.
@sbcontt YT You got me... I have no idea what ArchLinux is. Oh, I do know that there are variants of UNIX, like Linux, AIX, and a few more, I guess. It's an operating system, for sure. To my knowledge, UNIX and the variants became popular on reduced instruction set computers (RISC). In order to speed up execution, the machine code (instruction set) was whittled down. In some architectures had become big, that is, the machine code instruction used too many cycles.
No need to be jealous, I've worked with computers for 40 years. You'll probably see architectural chances for yourself.
And remember: No RISC, no fun!😀😀
wait, so its just compilers all the way down ?
always has been..
My condolences to Prof. Brailsford...
totally not confused
I do not really agree with this explanation.
Assembler is a 1:1 conversion to binary code, there is not really any quality in this. To make the first assembler your had to manually convert to binary code.
But when the first computer (with enough capacity) was running, your was past that stage, everything could be done by cross compiling, i.e. change the code generating stage to match the target CPU.
I am sure Professor Brailsford could explain a lot of interesting stuff about that and I am going to miss his explanations.
he's doing more videos...
I have to be a bit picky.
Something like a machine code monitor would be 1:1, but an assembler isn't quite 1:1: it keeps track of things like labels, does parsing, and can provide pseudo-instructions and macros that give you different code depending on the context they're used in.
I have done a lot of assembler over the time, in my opinion it is 1:1. Luckily assemblers are smart enough to resolve address and expressions and have shorthand notation for some instructions (Like NOP for mov r0,r0 or what ever) and a macro assembler can replace single lines with a stored list of instruction even with some conditions in it. I do not see all that as invalidating my 1:1 opinion.
If I run a disassembler on anything from a assembler, I do not expect any surprises, from a high level language it is very different.
Oh jeez, I'm sorry for your loss professor.
"Perfect output, first time, of cause" - what a beast of a man
I always wonder which program are you using for these cool VFX?
Oh dear. Deepest condolences Professor.
Thanks for the upload. I would appreciate it if you would expand this topic into the ISA and various implementations. For instance, Intel's 8051 architecture is prolific since it became public domain. I have long wondered what real differences exist between the original tool chain and all of the current manufacturers that build on the 8051. It is not something people often talk about or demonstrate within the hobbyist community. There are 8051's currently manufactured by Silicon Labs, Microchip, Cypress, Analog Devices, and many many others. Where is the gap between the original intel tool chain and these other derivatives? How is it that companies like Kiel and Analog Devices sell proprietary software toolchains for their devices based on a public architecture?
I’m sorry about your loss.
Sorry for your loss, Professor Brailsford.
My condolences Dr Brailsford.
TY for very clear explanation!
One of Professor Brailsford's great fortes is his ability to make even the driest technical stuff come alive by not merely explaining the technical side, but by including the people involved. He is just a great story teller.
What is that CD on his desk that has a cartoon duck on it?
Condolences for your loss Professor.
My condolences.
My condolences to the professor.
It's deeply saddening news - my condolences Professor - but what greater tribute to your dear wife than to make so great a contribution to the CompSci-lay community's understanding of your life’s work.
This, in essence, even now in 2020 is David Brailsford's, and by extension Julia's, legacy. We, the benefittors, shall never forget nor take for granted your deep sacrifice. With great respect and earnest regards, JH.
Building the tools to make the tools to make the tools to make the program run.
When you dig all the way down, here's the sequence:
Computer schematic -> working circuits -> binary machine instructions-> assembler -> compiler -> program -> executable.
I knew I had seen these "T diagrams" before. Then I remembered. In the 1970 book "A Compiler Generator" by McKeenan, Horning, and Wortman they use the diagrams to describe the XCOM system. It describes a language called XML used to generate compilers. Interesting bit of history - XPL was used by NASA to generate the compiler for their HAL language used on the Shuttle. XPL was derived from PL/I.
God I'll never get this. Even If I understand how it must be possible that you have to build bits of your language on top of assembly in order to compile even more bits of your language into assembly, it still seems like witchcraft. And I have no idea how that could ever actually be coded. How the hell do you start.
Yeah I think that last bit is the most important. Once you're in a higher level language like C you can go back and re-write or write assemblers and compilers that may not be efficient, but can produce efficient binary, and then you're golden because you can rebuild the compiler or assembler with that.
Also, this was *way* more of a problem back in the Bell labs days, and when new archs come out, now everything can be cross-compiled to start off with, so no need to do this from scratch unless you really want to.
The opcodes were listed by the chip manufacturer, which documents were then delivered with their reference board, to a company who used them to write an OS, which like UNIX are licensed and therefore kept secret.
The.End.
Does that mean that any program written or ever will be written can be traced back, in an unbroken path, to someone flipping switches on a computer input panel somewhere in the dark past? Like evolution? A tree with many dead ends and what we currently use that is not currently a dead end?
Condolences .
i love how he uses dot matrix printer paper
My condolences.
Professor Brailsford showing off his music collection
What is the cd with the duck?
Professor Brailsford, its a privilege to learn from your videos. Thankyou and kind regards from Argentina.
Tho, in all those years, why didnt we make higher level machines able to understand a higher level version of assembler or even C natively ?
Nice guy, very smart, much respect, but man... he's gotta stop saying programs squirt stuff out.
it looks like a tower defense game:)
This is the perfect curmudgeon I sincerely hope to become some day. What clarity! Wow!
I used to write assembler programs on paper, then I would hand-translate them to binary (actually hexadecimal), which is basically manually doing the work of the assembler program with a pencil and paper. This involved looking up the operation codes and register codes from a table in the manual of the computer chip written by the manufacturer, and then writing the hex codes on note pad next to the assembler codes. After double and tripple-checking everything, I would enter the binary bit patterns into the computer with physical switches on a 16-button hexadecimal keypad. The keypad itself was hard-wired directly to the computer's memory, anything I entered on the keypad would be copied into the memory circuit directly.
This sounds much more interesting than it must've been to do.
@@Kapin05 Actually, I found it to be a ton of fun. It really lets you see down to the circuit level exactly how a Von Neumann architecture computer works. And you can get it to do fun things like make noises, or control actuators. Nowadays, USB controllers circuits do all the work for me, but I know that these controller circuits are doing the exact same thing that I used to do by hand when I was writing bits into memory directly.
The experience taught me why computer hardware manufacturers need to work so closely with the people who write compilers and operating systems. It also gave me an appreciation of how complicated modern computers are, and how much work it takes to make a compiler and operating system. This is also why I am so thankful for the Linux community.
i am shaking just by reading this
@@RaminHonary Huh. coolio. I don't have the patience for that myself, so that's kinda surprising to hear.
My condolences, professor. Thanks for passing your knowledge
2:03 The marker has a on the end!
My belated condolences
Monsieur Brailsford, je vous prie de recevoir mes très sincères condoléances et l’expression de ma profonde sympathie.
Nous sommes nombreux à apprécier l'effort que vous mettez dans votre enseignement. Le malheur qui vous frappe nous permet de vous dire combien nous sommes proches de vous, et j'espère que cela puisse vous apporter un peu de réconfort.
How do you represent programs that aren't just a pure function with a t-diagram?