Placeholder Image

字幕表 動画を再生する

  • We've talked about

  • various aspects of bootstrapping a lot on computer file

  • Going way back, I think to a ton robin video three or four years ago now which is doing very well

  • Dilemma of the chicken and the egg. He talks very well about the

  • essential nature of bootstrapping and so on but he very carefully

  • avoids going into detail because it does get complicated the way I've always found best to teach it is to use a

  • Tool called T diagrams, which you just draw for yourself

  • I'm going to explain via diagrams what it means to bootstrap

  • Bootstrap a system like an assembler or a compiler or whatever, but first of all

  • What is a t diagram draw me a t diagram let us assume that you have written a program?

  • In Bell lab C language, you are very very proud of this program

  • You think is absolutely wonderful and will win an award and all that. This is the input

  • To your program. This is the output

  • From your program and at this level I can say what does that mean?

  • It means that the program was written in

  • I've chosen C deliberately because it's low level it's fairly close to the hardware something like this

  • I hope you'll all recognize you're writing a simple program in a simple language and you're delighted when you're high level statements produce

  • Ultimately this thing I will try not to fall back into a cheese usage and say it produces a core image

  • They even call it that's about as no. It's an executable. Okay?

  • well

  • We all know that it's all very well saying our right?

  • Agency is gonna have this input it will produce that output. The next question is but how do you convert the C?

  • into a runnable executable binary

  • Which will be your program. You have to get that C

  • Translated and here you begin to see the power of T diagrams draw this one again

  • Input/output it's written in C

  • Now here's the clever that positioning another T block like that up against this one

  • Shows you how this has to be processed

  • What you need is something that will turn you'll see

  • Program statements into a working binary on the machine you're working on you may say mmm, but where did this come from?

  • somebody provided me with a thing that is capable of taking in C statements is is itself an

  • Executable binary it's running on my arm chip on my Intel on my Apple or whatever

  • This is my C compiler. Of course, there's got to have come from somewhere, but we'll get into that later

  • So there's the C compiler and if you feed the C language for your master program through that compiler, you know what happens?

  • It produces an a dot out on UNIX or an executable binary the net effect of slotting that T diagram

  • Against here slightly downwards is to show you that

  • The C you've written gets converted into binary and the net output

  • from this

  • process

  • It produces out a program that you probably store in a file somewhere

  • Which is like this left-hand side only a little bit different because it's now

  • Input/output but look

  • What has happened during the compilation process? Is that by compiling your C statements for your program?

  • It drinks the minutes data. The compiler itself is a binary running on your architecture that you're perfectly happy with. It is squirting out

  • executable binary

  • So I can write in here

  • Let's say that's my output binary code, but that output binary code

  • I'll stick with a pink our right bin in here to show you that that is what the compiler has done for you

  • You think of it as input?

  • Producing output and I wrote it in C and you close your eyes as to what happens

  • It just works but your binary your a dot out

  • your ultimate executable will tell your input will produce perfect out put first time of course, but it is

  • Essentially written in binary and has to be to execute directly the hardware that has been produced by AC

  • Compiler and the T diagram for C compiler is this I accept as input C. I am a runnable binary

  • Otherwise, I won't work at all, but I have code

  • generation capabilities I

  • Generate binary that will run and that is your user executable

  • And here's the first point

  • I want to make the quality of the binary that actually is your compiler running may be very different from the

  • Quality of the binary that it spits out as a translation of your program

  • they may be very similar or it could be that the C compiler is actually very very slow at

  • Producing your output binary, but if he gets there in the end you don't care it could be ultra fast

  • It could be that you've written a see compilers are so bad that the output that it

  • Produces for you is worse than it itself is using. I hope you all get the hang here

  • There's not necessarily any direct link between the quality of the binary

  • You are running to make the C compiler work as opposed to the binary. It is spitting out for your program has its translation

  • they may be related and may be close and all this what I think now I will try and do for you is to take

  • the story one stage backwards

  • And

  • start

  • Speculating about how the heck did I get the C compiler?

  • Is it something that 10 Thompson handed over or Dennis Ritchie hand it over to me already made it could have been oh

  • you might say

  • Dennis how did you implement that to C?

  • Compiler and he was so well the first version I wrote off the back of an assembler

  • And of course this it goes on recursively forever, but Dennis who wrote the assembler

  • You know and back and back and back right down to squirting ones and zeros in on hand kids

  • No, let's presume for the next stage of the story that from somewhere your little machine

  • did also come with an

  • assembler

  • for low-level programming for filling in the bits that may be

  • The C compiler for one reason or another isn't suitable for well. How is that done in T diagram terms and

  • By looking at how the assembler is done. We can then see how it's possible to

  • Bootstrap off an assembler version of something to a higher-level version an assembler is like a

  • Compiler except for those of you who've done it, you know in every sense an assembler is at a lower level

  • Assembler some particular macro assemblers, they'll give you a vestigial capability to do an array

  • but they may not have structures almost certainly won't they're a high level constructs you see

  • So you you're down with simple add subtract?

  • Statements you can move about memory. You've got to understand pointers

  • We've done lots of those you do them at the assembler level. You're in charge

  • You must keep track of what your pointers are in so on and so on and so on

  • It's just a simpler view of the world and a more detailed and complicated one in several ways

  • I'll call it AC and that stands for

  • assembler input now

  • You expect that assembler to produce you a runnable executable binary. Well, I'm going to write this in here as

  • saying that the code generation from the

  • Assembler is going to produce me what I'll call a binary of type a is produced from an assembler

  • It's an assembler quality binary

  • It depends on the Koho wrote the code generator for the assembler as to how good that being a is now

  • Here's the thing again. You'll have to get your head round and get used to this is au

  • Been you I don't know how this was developed this assembler

  • All I know is I met Ken in the corridor David wheeler

  • It came to the corridor and said hey, here's the assembler

  • I use they handed over an executable and I did not ask questions about how that in itself may have been

  • Bootstrapped out of nothing. They just said here's an assembler it works use it. So okay. I say, thank you

  • I mean at the midpoint of a endless sequence of bootstrapping but I can build on top of an sm

  • To build the C compiler shall we say so you put assembler codes in of course?

  • The unknown provenance binary is worrying away. And that is executing the assembler code

  • and out it comes as binary of type a

  • Which you can put in a file

  • BN a dot out file under you mix it could be whatever you can store it in a file you can invoke it you can

  • Execute it and the only difference from what's gone before is that the assembler code is it's a lower

  • Sophistication level than you'll see you would be a lot of you know again

  • I keep harking back to Bell Labs history largely because it's very good for

  • Illustrating this thing you can say look this really happened. This really is what Dennis inten did

  • This is what you have to be aware of

  • Dennis said you can and cancers to Dennis for the next version of the UNIX operating system

  • We've gotta write it in something higher level

  • It drives you mad writing it in assembler because there's no easy way of keeping track of pointers. There's no structures

  • In fact in a recent video now out there in the wild somewhere ken Thompson admits

  • He said our first three attempts to write UNIX in a higher-level language and Dennis was developing

  • Say the first three attempts. I tried I'm Ken Thompson

  • Failed. Why did they fail I found later the fourth attempt Dennis had put structures in C

  • And that's what I needed because they automatically keep track of offsets and pointers. Wonderful. Okay

  • So here we are then back in that kind of era. We are wanting to create a

  • C language

  • Compiler, but we are writing it as a simpler code level it is going to produce a binary

  • But going back to what we said last time because it came out of an assembler era

  • We're going to presume that the binary that this thing produces is what we'll call binary a it came via an assembler

  • Did this execute them fine, but then you look at that say hey, come on. This is brushing over certain details

  • You can't directly execute assembler and unless somebody's written an assembler interpreter for you, but they're again

  • No, they haven't that's emblem coding. It's got to be converted into a binary

  • How do you turn the assembler coding into a binary and so sort up another T diagram and visualize what goes on?

  • There just happens to be hanging around because Ken gave it to us in the corridor a thing

  • Called an assembler and the assembler accepts any old assembler code you like?

  • produces what we'll call been a an

  • executable binary but it came out of an assembler and that

  • the assembler itself

  • The binary is of unknown provenance

  • candidate in absolute binary off the top of his head probably not but somebody

  • labored long and hard to

  • write a thing that really works as an assembler on this particular machine that you are working on what you need to do is to

  • feed the

  • assembler code that implements your C compiler

  • Into the assembler itself to assemble it. You've got to assemble the assembly code

  • That is the compiler and it goes in as assembler coding. It's running on its own binary. You're thinking a while' crash

  • No, it won't Ken wrote it, you know this sort of thing that was around and it converts the assembler code

  • into binary of quality a

  • That binary of quality a when it's produced you can store in a file. It's an executable

  • It's an a dot out file and then you have created a thing which takes in C

  • produces binary a

  • Assembler coding so your net output here then is the following

  • It's C. It spits out an executable binary for you the C compiler

  • So we now have a C compiler that is not just as it were implemented at the assembly code level

  • But that assembly code has been

  • Translated into a binary

  • So that the C compiler can actually run on hardware

  • and once again

  • There's trace through the assembler code that implements

  • The C compiler is fed into the assembler

  • This thing was round and round like mad but the assembler code

  • statements that are the compiler get translated into bin of quality a and that's the

  • Implementation vehicle for your new C compiler you have produced a C

  • compiler by building it out of an assembler by using the assembler as the next stage long, which you have to do the

  • assembler

  • converts the assembler code that is the C compiler into being a workable runnable binary of quality a

  • so that's the first start of your compiler is to say we

  • We doing bootstrapping we've come up off an assembler solution

  • We wrote in our high-level language and here we are a very very first C compiler

  • Is there a problem with it? Not really?

  • Except that what we want to do here is to say well

  • We want an AC compiler that will produce runnable binary of some sort and then we say hey

  • But the only tool we've got to making a binary for this C compiler is that there is the assembler itself

  • Right the assembler

  • Produces Benet, so you're stuck with that

  • so

  • Can you see that by running the assembler there and making it squirt out binary a quality?

  • equivalent to the assembler code

  • that is the compiler you end up with AC compiler Marquand that

  • Spits out Benet but is running on Binet

  • We're at the mercy of bin of quality a the assembler quality binary. Is it good? Is it bad?

  • Could we do better?

  • Yeah

  • We stop there

  • but just as a marker for what's coming if your head isn't aching yet that thing is building a

  • Compiler off an assembler when that is working

  • what do you do to make it better you rewrite it and

  • You make a new version of a C compiler that produces beam B which is so binary

  • But how do you compile a new version of the C compiler answer with the old one? So

  • You end up with a seat have been better, but it's still running on Binet

  • next time

  • I'd lost my

  • Compilers notes and assembling those did you see diagrams?

  • But thanks to one of my grad students rom nots bless you Ron who was a complete pack rat?

  • He had rewritten all my notes in much better shape and had come on to them from

  • 30-something years ago so I couldn't made this video without your own. Thank you very much

We've talked about

字幕と単語

動画の操作 ここで「動画」の調整と「字幕」の表示を設定することができます

B1 中級

T-ダイアグラムを使ったブートストラップ - Computerphile (Bootstrapping with T-Diagrams - Computerphile)

  • 0 0
    林宜悉 に公開 2021 年 01 月 14 日
動画の中の単語