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