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