Bootstrapping with T-Diagrams - Computerphile

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/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

[@profdaveb6384]

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.

[@Flankymanga]

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.

[@hugoporras14]

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)

[@donovanvanderlinde3478]

You are a beautiful person sir!

[@Aziqfajar]

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.

[@GeodesicBruh]

ProfDaveB condolences

[@user-ov5nd1fb7s]

Professor Brailsford is a pleasure to listen to. My condolences.

[@LittleRainGames]

He died?

[@user-ov5nd1fb7s]

@@LittleRainGames no, one of his relatives died. I am not sure which.

[@raffitz]

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.

[@rohithkattamuri4019]

What happened??

[@jackik1410]

@@rohithkattamuri4019 Julia Bailsford died, see the end of the video. Condolences from me aswell.

[@givemecoffeeee42]

My condolences, professor. Thanks for the lesson and I wish you the best.

[@Milosz_Ostrow]

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.

[@mrlithium69]

very true analogy

[@BertGrink]

Yes it is essentially the same process.

[@TheLivirus]

I was thinking of precisely this! :)

[@flymypg]

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.

[@paulsteenbergen4223]

My deepest sympathy for your loss Prof. Brailsford. -When someone you love becomes a memory, that memory becomes a treasure.

[@bemk]

I'm sorry for your loss Prof. Brailsford.

[@rohithkattamuri4019]

What happened??

[@x3ICEx]

@@rohithkattamuri4019 ​ @michael wittmann Julia Brailsford passed away.

[@x3ICEx]

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.

[@AshleyWrigglesworth]

Prrof is like the David Attenborough of software, even sounds alike. 🤔

[@flymypg]

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!

[@nomaxx1176]

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.

[@SKyrim190]

My condolences to Professor Brailsford

[@spikeevans1488]

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.

[@Richardincancale]

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.

[@jayjeckel]

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. :)

[@ahmedelakrab]

Sorry to hear of your loss, professor. My condolences from Morocco.

[@nick2me1]

Sorry to hear of your loss. My condolences, professor.

[@rchandraonline]

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.

[@AndersJackson]

Oh, those where the times. :-)

[@Kirillissimus]

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.

[@AndersJackson]

@@Kirillissimus oh, those where the days. Memories. :-)

[@PaulTheFox1988]

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.

[@mrcturbor]

My condolences to professor Brailsford. Losing a loved one is one of the hardest things in live. I wish you all the best.

[@GeezRvonFart]

Give this man an award for awesome. Half the fun in watching these vids are the info and the other half is astonishment of the man's knowledge.

[@KenHilton]

My condolences, professor. Thank you very much for explaining this in such great detail, I wish you the very best.

[@Jojoxxr]

You’re an absolute legend, Professor. Love your lectures, very sad & sorry to learn about your loss.

[@borisdorofeev5602]

Thank you for another great video. I am sorry to here about the Professors loss.

[@BrendanGrainger]

You are an absolute treasure for all you do Professor. I'm so sorry to hear of your wife's passing.

[@insoft_uk]

He was one of the best ones in these videos, easy to understand and follow.

[@bernardo013]

Thinking of you today, Professor

[@walterjorgemazzoni]

Professor Brailsford, its a privilege to learn from your videos. Thankyou and kind regards from Argentina.

[@JxH]

Oh dear. Deepest condolences Professor.

[@egenethebest9107]

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!

[@rty1955]

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

[@Aziqfajar]

I certainly liked the explanation in this video regardless of me being very confused about bootstrapping. My deep condolences to your loss, prof.

[@merseyviking]

My deepest condolences Prof. Brailsford.

[@drskelebone]

I can offer nothing more than my deepest sympathy and love, Pr. Brailsford.

[@brabhamfreaman166]

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.

[@Manava2012]

Its mind boggling.. my head is spinning. Hope to see a follow up on compilers and assembler

[@TheBodgybrothers]

"Perfect output, first time, of cause" - what a beast of a man

[@maycodes]

My condolences, professor. Thanks for passing your knowledge

[@SomeGuyInBrisVegas]

Condolences for your loss Professor.

[@andljoy]

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.

[@steefant]

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... ;)

[@rt1517]

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).

[@Fractal80Y]

Ah finally the best explanation and video i have found on this

[@RockBottom45]

I love, how this room seems like out of the 70s xD And terrific content btw :)

[@rojasbdm]

I’m sorry about your loss.

[@morkovija]

Great video, sorry for your loss

[@alpaslaneldemir6904]

My condolences Prof. Brailsford.

[@jamildrareni4304]

Sorry for your loss Professor.

[@youretheai7586]

I was trying to wrap my mind around what you were saying as I was mixing up compost for my garden. :-)

[@xakkep9000]

TY for very clear explanation!

[@BertGrink]

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.

[@pdelong42]

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).

[@CurtisDyer]

Thank you, Professor.

[@guitarman13021]

My condolences Dr Brailsford.

[@AndersJackson]

Sorry for your loss, Professor Brailsford.

[@JulianOnions]

So sorry to hear about Julia.

[@nab-rk4ob]

What a blessing he was. He knew so much.

[@Rob_III]

I'm not quite sure you understood...

[@ralfoide]

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.

[@scbtripwire]

My condolences Professor Brailsford. :(

[@raglanheuser1162]

but who wrote the bin compiler? and what does quality mean?

[@Pablo-Herrero]

What books, papers or other literature are available, where you can read more about this?

[@unlokia]

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?

[@silkwesir1444]

it is very quiet, you have to listen more closely.

[@morrolinux]

I always wonder which program are you using for these cool VFX?

[@roar779]

My condolences to the professor.

[@ximalas]

My condolences, Prof. Brailsford.

[@RockClimberAlex]

Oh jeez, I'm sorry for your loss professor.

[@jan_wh1tey]

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.

[@michalkononenko9833]

My condolences, Professor Brailsford.

[@davidpruett9307]

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.

[@PlayTheMind]

They oddly look like *Tetris*-diagrams

[@rentzepopoulos]

My condolences to Prof. Brailsford...

[@revooshnoj4078]

R.I.P.

[@tomcho8221]

My condolences, Professor.

[@MrSlowestD16]

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.

[@dukereg]

I hope there are videos coming on the Forth style of bootstrapping.

[@PvblivsAelivs]

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.

[@Antiorganizer]

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.

[@comediehero]

Thank you

[@UpcycleElectronics]

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?

[@casperes0912]

My CS professor for programming languages used t-diagrams too.

[@RaminHonary]

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.

[@Kapin05]

This sounds much more interesting than it must've been to do.

[@RaminHonary]

@@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.

[@rawriclark]

i am shaking just by reading this

[@Kapin05]

@@RaminHonary Huh. coolio. I don't have the patience for that myself, so that's kinda surprising to hear.

[@toddblackmon]

2:03 The marker has a on the end!

[@fliptoynk]

Well... In text-based applications, I couldn't see the difference in performance between TC and TASM... except that it's harder to code in tasm, and tc's product(the .exe) is quite bigger in bytes(probably because the headers were included in the compilation). But in terms of graphics, I was shocked in awe back then when I was given a demo of a 3d paper plane written in asm. Compact, no ems, just base memory, and the graphics animation are clean, no flicker nor auras or residues. The bootstrap process may not be perfect, but hey, it made the programming tasks much easier for the rest of us so kudos to you prof nonetheless.

[@taylornate2]

Roller Coaster Tycoon was coded in ASM

[@JoshuaHillerup]

How do you represent programs that aren't just a pure function with a t-diagram?

[@Gooberpatrol66]

Professor Brailsford showing off his music collection

[@AKorigami]

What is the cd with the duck?

[@whiteeyedshadow8423]

my condlences proffesor brailsford...just learned about your loss

[@flymypg]

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.

[@andrewjknott]

"Three attempts" (holds up four fingers).... "Three attempts!" (hold up 2 fingers).

[@silkwesir1444]

at least the errors cancel each other out (the sum is 6, as expected)

[@ximalas]

The two hardest problems in CS is cache invalidation, the naming of things, and off-by-one errors.

[@HighestRank]

ximalas CS is, as most know, the abbreviation for a game called ‘Counterstrike’.

[@ximalas]

@@HighestRank 😛

[@silkwesir1444]

@@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".

[@jamesExiledLegends]

R.I.P. Mrs. Brailsford

[@chrisbebek3192]

Still has a stack of tractor feed paper. Badass.

[@stevefrandsen7897]

My belated condolences

[@cheaterman49]

Wow, classy new glasses!

[@AutoFirePad]

My condolences.

[@maciej-36]

Soo how do you write the first assembler?

[@sidazhou]

totally not confused

[@diegonayalazo]

Thanks

[@adulion]

i love how he uses dot matrix printer paper

[@haydo8373]

So does the assembler fulfill a mapping functionality? Eg, replace x assembly instruction with y binary instruction.

[@BertGrink]

Yes i think that is correct; one of the features of assembly language is that there is an exact one-to-one relationship between assembler mnemonics and the resultant binary code, something no other languages can claim.

[@haydo8373]

@@BertGrink Awesome, thank you for the reply!

[@vincei4252]

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?

[@00Skyfox]

What is that CD on his desk that has a cartoon duck on it?

[@phoenix2464]

9:50 does some have a link to this video ?

[@SevenDeMagnus]

Cool

[@micr0xchip0xverflow6]

Great explanation, but I'm still confused.

[@Boopadee]

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.

[@micr0xchip0xverflow6]

@@Boopadee Thanks, I'll have to watch it again knowing this. Then I will try and write my own bootstrapper for practice

[@trucid2]

It's compilers all the way down.

[@jacobscrackers98]

My condolences. Are there any more detailed resources for this stuff?

[@ximalas]

Any decent book on compilers should fit the bill. This was the chosen textbook while I was at uni: "Programming Language Processors in Java: Compilers and Interpreters" by David Watt and Deryck Brown, ISBN-13 978-0130257864. You'll find T-diagrams there, although they call them tombstones.