The Science of Everything Podcast - Episode 96: How Computers Work Part VI - High Level Programming and Software

Episode Date: March 2, 2018

In the final episode of our series on computers, I give an introduction to high-level programming languages, how they relate to assembly language and machine code, and how the compiler converts high level programs into a form that can be executed by the processor. I then outline some of the key components to high-level programming, such as data structures, control structures, and algorithms, before sketching an example implementation of a simple game. I conclude with an integrative summary of computer structure from silicon up to the operating system.

You're listening to The Science of Everything Podcast, episode 96. How Computers Work, Part 6, High Level Programming and Software. I'm your host, James Fodor. So in this episode, we finally come to the conclusion of our long series on how computers work. In this episode, I'm going to discuss high-level programming languages and how those differ from assembly languages and also a little bit about how compilers work. I'll then introduce briefly some of the key programming concepts, including control structures, data structures, algorithms,

and I'll give an example of an algorithm to just illustrate the basic idea. And then I'll go through a brief example of a program of how you might code a simple game in a high-level language just to give you the sense of how programming works in high-level languages. And to conclude the episode, then I'll go through a summary and integrative account of how computers work drawing upon all of the material that we've discussed in these previous three episodes. So, to begin, let's talk about high-level programming languages.

In the previous episode I talked about assembly language, which is essentially a symbolic form of machine code, which is much easier to program in allowing you to use short symbolic forms for op-codes, instead of having to remember the binary sequence and being able to use symbolic addresses, instead of having to specify each address in binary, etc. Assembler is much easier to program in than machine code, but even assembly is still quite tedious to programming, because, you still have to keep track of loading individual variables into particular registers and moving data from here to there and performing very low-level operations. So it's still very difficult and tedious to programming, even though it's easier than machine code. Instead, most programmers these days program in one of various high-level programming languages.

So rather than having to deal with registers, memory addresses, call and call sacks and other things like that, High-level languages tend to deal with more abstract concepts like variables, arrays, objects, more complex arithmetic and bullion expressions, subroutines, functions, loops, and other abstract concepts. So the focus here is on typically usability and functionality and reliability rather than optimal program efficiency. The very best assembly programmers can generally, at least in many cases, produce programs that are more efficient than high-level programs once they've been compiled. However, it takes much longer to write those programs, and so generally these days it's just both quicker and easier to write a program in a high-level language and have it automatically converted into machine language via the compiler, rather than try to have to optimize everything by writing it in assembly yourself. Another big difference between high-level languages and low-level assembly languages is that in assembler, every line of the program is either a pseudo-instruction to the assembler, which doesn't actually get translated into it.

to machine code, or if it's an actual line of code, one line of assembly code will correspond to one line of machine code. So there's a direct correspondence there, and thus assembly, the job of the assembler is relatively straightforward. It's just translating from the symbols to binary. In contrast, high-level languages have few, if any, elements that translate directly in this way. So you don't deal with machine op-codes or registers directly in a high-level language.

In many high-level languages, you can't do that. in others you can, but mostly you don't bother. Instead, high-level languages have instructions that are written at a high-level of abstraction, which then the compiler essentially rephrases and re-writes in a way that actually uses the machine's op-codes directly. And how this is done, I'll talk about it in a moment, but so there's not a direct correspondence between a statement in a high-level language and an operation of machine code in the way there is an assembler. So those very basic operations that are part of the machine's instruction set architecture, you don't actually use those when you're writing a high-level programming language,

when you're writing in a high-level programming language. Instead, you use higher-level abstractions, which are later converted into those instructions by the compiler. Examples of high-level programming languages in wide you use today include Python, Visual Basic, Java, Pearl, Ph.P, Ruby, and many others. There's a popular programming language called C, which some would debate, to whether it's truly a high-level language because it's an older language than many of those others that I mentioned. And so it's sort of in some ways in between Assembler and the more modern programming, high-level programming languages. So as I mentioned, the advantage of high-level programming languages is that they're easier to write and maintain than low-level languages.

The big downside of high-level programming languages is that they suffer from what's called an abstraction penalty. So generally, programs written in high-level programming languages when they're compiled, into machine code will be less efficient and will run a bit more slowly than it's possible using optimized custom written assembly code. Although you do have to be pretty good at writing assembly code to be able to outdo today's best compilers. So that's probably less of an issue than you used to be. A high-level program can be written in any text editor, even note something as simple as notepad or you could use Microsoft Word if you really wanted to, although usually more customized software is used. So the actual act of writing editing,

program does not require any special software. The special software only comes in when you try, when you want to convert that program from the sequence of statements in the high level language into a binary executable file that you can actually run on a processor. That requires a special piece of software called a compiler. A compiler is a program that converts this high level program, essentially just this text document that you've produced as you've been coding. The compiler converts this into an assembly program by following a sequence of steps. That assembly program is then converted via an assembler into machine code using the process that I discussed in the previous episode. In fact, modern compilers usually do the whole process in one go. They just convert your

high-level program directly to machine code. But conceptually, it's perhaps easier to think of the high-level language as being first converted into assembly language, which then in turn is assembled into machine code. So how is this done? How does the compiler convert the text in a high-level programming language into an equivalent assembly program that does the same thing, but uses the operations that are actually in the instructions at architect. and thus that the machine can understand. Well, the first step is lexical analysis. This means that individual tokens, like variable names or operators and keywords in the language,

must be identified and demarcated from each other. So the program has to know that, you know, this text is part of one word and this text is part of a different word or a different variable. That's fairly straightforward usually to do, usually white space. Spaces are used to distinguish them or sometimes other symbols are used to distinguish one token from another. The next stage is called a syntax analyzer. Here the tokens are placed in a logical relationship with each other using a special abstraction called a context-free grammar.

A context-free grammar is basically a system of rules that specifies how you can build complex expressions out of simple ones by adding new elements in. It basically works more or less analogously to how English sentences can be built up by adding new clauses. So you can add in nouns, verbs, and adjectives and so on at specified locations in the sentence. And often in a given location in the sentence, you can add in a new clause. So, for example, you could say, I went to the shops, the shops being, the object of that sentence, but instead of the shops, I could say I went to the place where we went for my last birthday outing. Now, that second clause, the place where I went in my last birthday outing, is the object of that sentence, but it's also a clause in itself. And if I wanted to, I could

build up more and more complex sentences by including more and more sub clauses and more complex elements in accordance with the rules of English grammar. The rules of English grammar, though, are kind of vague in some cases and subject to dispute and many exceptions, whereas in a context-freeogrammer they have to be rigorously defined and clear in terms of what can go where. And exactly how the elements, the tokens in a given language are able to be combined depends on the specification for that particular language. So there's a complicated set of rules that are built into the compiler that allows it to determine the appropriate logical relationship

of the different elements of syntax that have been identified using lexical analysis. After the syntax analyzer has built up this structure of how the different tokens relate to each other, you know, a bunch of tokens might be a subset of a procedure that's called by another token and so on and so on. Once that's done, the program is passed to what's called a semantic analyzer. This involves checking the types of different variables, ensuring all the variables have been properly initialized, and other things like that that we need in order to get the program to work. Initializing a variable means assigning it a value. So if I declare a variable like declare I to be an integer, just a number, and then I try to use I later,

the program actually can't do anything unless it knows what value I starts with. So that's what initializing means. Often if you declare a variable in a language like this, you'll just initialize it to zero. Some more advanced languages will just initialize them automatically if you don't explicitly tell it what to do. But again, that's something that will be done by the compiler. The next step is called intermediate code generation. So what the program does is it uses the pass tree and various sophisticated algorithms. The pass tree is the mapping of the relationship of the different tokens in the program that's computed by the syntax analyzer.

So that outputs what's called a pass tree that represents the logical flow of the program. The intermediate code generator then uses that pass tree and various sophisticated algorithms, which are not going to discuss, to translate the program into an intermediate form. This isn't the final assembler form, but it's an intermediate form in between the two. One advantage of converting it to an intermediate form is that it's easy to optimize this intermediate form, basically to remove redundancies and repetitions or pieces of code that don't actually do anything. It's easy to remove those in the intermediate form than in the final assembler form. So the intermediate code generator generates an intermediate form of the program,

which is then optimized to try and shorten and simplify the code as much as possible by various fancy algorithms. Then, after the optimization, the final code generation takes place, that translates the intermediate code into assembly code using a table of correspondences. And the way this will happen will depend upon the exact programming language and the compiler in question. So there are many different compilers that you can use for a given programming language. You will need a different compiler for each instruction set architecture that you want to compile a program too. So this is important to understand. A high-level programming language can be written on any system. Anything that has a text editor you can write programs in that high-level language on.

language on. However, you won't actually be able to run those programs until you compile them, and compilation involves converting the high-level language, the program in the high-level language, to a sequence of assembly statements. And remember that each instruction set architecture has its own set of assembly language statements that you can call. So that means that if I want to compile my high-level program on my desktop, that requires a different compiler, a different piece of software to if I want to compile it to use, say, on my mobile phone, which uses a different instruction set architecture. So that's one of another advantage of using high-level programming is that you can write a program which can be used on any device as long as

you have a compiler that can convert it into the particular sequence of instruction calls that that device will understand. If I was writing directly an assembler I'd have to rewrite the whole program in order to run it on a different type of device that has a different instruction set architecture. So many of the correspondences after all of the optimization and the semantic analysis so on has occurred. Many of the correspondences to convert instructions in the high-level language to instructions in assembly language will be relatively straightforward. For example, if I'm performing basic addition operations or multiplication, those have direct correspondences in the machine language.

If I'm declaring variables and changing their values, that can be represented in the form of moving data around between registers, which will have its corresponding operations in the instruction set architecture. If I've incorporated a control structure, like an if-then statement, statement into my programming code, that can often be fairly straightforwardly written in terms of some comparison statement, some comparison operation, and then a jump statement. So, you know, if the value comes out this way, jump to this part of the code, if it comes out the other way, jump to the other part of the code. So there are usually fairly straightforward correspondences between high-level language code and machine code after you've done all the optimization, the syntax

analysis and all that stuff. Sometimes, obviously, it's going to be trickier than that if the code is more complicated, but there are sophisticated algorithms that have been developed over the decades, really, of compiler development that are able to do this. Compilers these days are usually quite reliable and quite efficient, so they're able to do a pretty good job of converting a high-level program into reasonably good and efficient machine code. Now, I've been talking about compilers this whole time. A compiler is a program that takes a set of text statements in a high-level language and converts it to, or either assembly, which is then converted by an assembler to machine or just directly to machine code, which the processor can then run.

So at the output of the compiler is a binary executable file. Some programming languages, however, are what's called interpreted rather than compiled, and this means that each individual instruction is converted to a machine language format executed individually during runtime, that is, only as it's needed, instead of converting the entire program into a binary executable and then running that. And really, there's no theoretical reason why most languages need to be interpreted or compiled. It just depends on the language. So typically, for example, C programs are usually compiled, whereas Python programs are usually interpreted,

although there are exceptions to that. But that's not so important from a conceptual point of view. I just wanted to highlight that. But it's easier to talk about – I think it's easier to think about a compiler as converting the entire program into a machine language program, which is then just executed. It's conceptually easier, I think, to think about that. So if I mention this in the rest of this episode, I'll just talk about the compiler. But bear in mind that sometimes that that actually means an interpreter is doing it line by line,

and then immediately executing that line that it's just translated into machine language, instead of converting the whole program and only then running it. So now that I've discussed conceptually what high-level programming languages are and how they work and how they're compiled into machine code, I now want to just talk about some of the underlying concepts of actually writing a program in a high-level programming language. This is mainly for the benefit of people who've never programmed before, and I actually have no idea what proportion of my listeners that will be.

I imagine some of you will have at least at some point written some programs before, and others of you will not. So I do programming myself, but I'm not particularly good. I'm by no means an expert programmer. However, I just wanted to include some basic concepts of programming and then an example of a very simple program, just to give you the taste of how this actually works, how you can use the sequence of simple instructions to carry out fairly complex tasks. Because even very complex software like Microsoft Windows or high-end games and things like that, Even those are written in languages like C, which have at their base only a fairly simple,

a fairly limited set of basic instructions that can be run, and yet it's still possible to produce very complex programs as a result of these. And this ultimately is because the underlying hardware and the software built on them are too incomplete, so they can perform any computation that can be done in a finite amount of time. So that's the underlying principle as to why this is possible. But let me just give you some more practical examples and principles as to how this actually takes place. Again, I emphasize that I'm not trying to teach practical programming skills here. There are plenty of courses for that. I'm just giving you a taste of some of the key ideas

and aspects of programming. So these include basic instructions, data structures, control structures, and algorithms. So whenever you learn a new programming language or try to do something in a programming language, these are sort of four of the key areas that you'll need to familiarize yourself with, the basic instructions that you can do, different data structures that exist, control structures and algorithms that you can implement. So I'm going to discuss each of those in turn. By basic instructions, I just mean the fundamental, the most fundamental things that you can do in the programming language.

So most programming languages have a similar set of basic instructions, although more specialized ones may have additional ones for particular purposes. So they include things like defining a function, performing logical and arithmetic operations, basic input and output, so getting characters from the keyboard, displaying things on the monitor, basic string manipulation, generating random numbers, error handling, making system calls, defining variables, stuff like that. It's just very basic, straightforward things to get

things done in the program. And most of these can be implemented, most of these types of instructions can be implemented in assembly language fairly straightforwardly as either operations on the ALU or as memory management moving data from one register or memory to another. The next element of a program are data structures. Now, data structures store information that the program needs, either for input or output or for holding intermediate. results that it uses in the process of computation. There are many different data structures that can be used and different programming languages will support different ones and be easy to use some in one language compared to another. The programming language MATLAB, for example, is particularly

well suited to store data in arrays. So it's often used when that's a convenient way of storing your data. So an array is basically just like a table of results. So arrays can be one dimensional, but they're often two-dimensional, so you'll specify a row and a column, and then there's a data point that corresponds to that. So arrays are always rectangular, and they're very useful when you want to loop over all of the indexes in your array and perform an operation on all of the elements there. Another type of data structure is called a stack. A stack is, well, literally that, it's a stack of items, and the operations that you have in a stack, instead of, say, reading an index in an array, which is what you do for an array, In a stack, you either push or pop. Push means that you put a new item onto the stack, like it could be a new variable or a new number or something, and pop means you take an item off the stack,

and the item you take is always the top item of the stack. So it's literally like having a pile of papers on your desk, and you can either put one on the top or take the one on the top off and do something with it. That's very useful for things like memory management or like task management, when you only want to access the thing that's been most recently put there, and you don't need to have access to all the things below it.

Another type of data structure is called a linked list. This again is pretty descriptive of what it is. It's a list where each item in the list has a link to the next item on. And so there's usually a function that allows you to get the next item from the list. So this is useful when you want to do things in a set sequence. So you perform some operation on one item in the list and then you just get the next item and do it thereon. And it's very easy to add and remove elements from the list. In particular, it's easy to chop out an element from the middle of a list and just put a new one in,

because you can just change the linkages. Instead of element three linking to four, you can take out element three, link element two to, say, element seven, and element seven to element four, and now what was my element seven has become my element three. It's much harder to do that in an array, where the structure doesn't lend itself to taking one element out in the middle. It's easier to do that in a list. A tree is another type of data structure which is essentially like a list except that each element can have more than one successor or child. So, you know, a family tree is a classic example of essentially a data structure that it is a tree, that you can have elements and they can have any number of children. And you can add or remove elements and read them as necessary.

And this is useful when you have like nested hierarchies of things and you can take elements either very high up on the list or further down and bring with them any children that they have. So these different data structures are useful for your data. different purposes and many programming languages will have support for some or all of these types of data structures. And one of the key decisions that a programmer has to make is how they're going to store the data that they use in their program and how that's going to affect the way they access it. The next key element of high-level programming that I want to discuss are called control structures. Control structures are methods for controlling the flow of execution in a program. If you recall way back to the first episode in this series, I discussed the structured programming theorem, which essentially said that you only need three types of control structures in order for a language to be Turing complete.

And these control structures essentially corresponded to sequencing, so just doing one statement after another. That's very simple. While loops, which does something until the condition fails to hold, and if then else statements, which test a condition and take an action in accordance with the result. So a while loop will usually have some sort of what's called a guard. So that's a comparison or a test, which is done every time the loop is entered. So it could be, a classic example would be to initialize a variable, say, I equals 1, and then say, while I is less than 100, and then do something.

So do some operation a bunch of times. And each time the while loop goes around, so each time you go through the loop, you'll have to increment your control variable I. Otherwise, the loop will go around forever. So while I is less than 100, do a bunch of stuff, I equals I plus 1. So the control variable I is incremented by 1. So that loop will go through about 100 times until I is equal to 100, then that controlled condition fails, and the program will exit the loop and then just continue executing the next instruction. So that's a very useful type of control structure.

Another type of control structure that I just mentioned is an if-then statement or an if-then-else. Effectively, this tests a condition and then takes an action in accordance with the result. If it's true, it'll execute one result, if it's false, it will execute a different result. And you can incorporate more than one possible outcome by having an else statement. You can say, if such and such, then such and such, else such and such, or else if a different condition holds, then do this, else if yet another condition holds, then such and such. And that's an easy way of controlling the flow of the program. So control structures are an essential component of programming because you need to be able to control the order in which the steps are executed so as to achieve the outcome that you want. The final element of programming that I wanted to talk about is an algorithm.

An algorithm is a set of steps that you can follow that will always deliver a certain outcome in a finite number of steps. Algorithms are directly connected to the notion of touring computability that I talked about in the very first episode. You have to have an algorithm to be able to perform something and ensure that the answer will be reached in a finite number of steps. Humans often don't use algorithms. We sort of use guesses and heuristics where it may or may not achieve the desired solution. But at least in the rigorous definition, an algorithm will always achieve the, desired outcome or always achieve the right answer in a final number of steps. Algorithms are useful because they can be used to achieve specific tasks in programming and if you know that you've implemented the algorithm correctly you can ensure that the desired solution

will be achieved and this avoids you're having to implement a wide range of ad hoc methods to get the desired result. Of course often in programming that's all you have you don't have an algorithm or everything but when you do have an algorithm it's handy to be able to use it. So important algorithms include sorting algorithms so whenever you have a data structure is often useful to sort it in accordance with some order like alphabet order or numerical order or something, so there are many algorithms that can do that automatically. Searching algorithms, so being able to find a desired piece of information in a very big list or other data structure. Finding the shortest path between two nodes in a graph,

that's a surprisingly useful task that has algorithms to be able to do that, and compression algorithms for reducing the size of a given file. An example of a widely used algorithm is quicksort. This is a sorting algorithm that's able to sort the elements in a list. I'm just going to explain how it works, not because it's intrinsically important, important for our purposes, but just to give you a sense of what I mean when I talk about an algorithm as a series of steps. So here's an explanation of how quick sort works. You start with a list of elements which are not in order. Obviously you wouldn't bother sorting them if they were already in order. And then the algorithm proceeds as follows. You pick an element called the pivot from the array.

The element can be picked at random. It really doesn't matter what you start with. So once you've selected the pivot, then the next step is called partitioning. I reorder the array so that that all of the elements with values less than the pivot come before it and all of the elements with values greater than the pivot come after it. So all this requires is comparing two elements individually. So just for each element in the list, compare it with the pivot if it's less, then ensure that it's placed before the pivot. If it's more, ensure that it's placed after the pivot. So that's just very simple comparing of numbers and shifting numbers around. After the partitioning is completed, the pivot will be in its correct position. All of the other elements

will either be before or after the pivot as they should be. Those individual elements may not be in their correct order, but the pivot will be in the right order. After I've finished partitioning, all I have to do is repeat the above steps recursively to each of the subarrays that I've generated. So after I've selected the pivot, and I've partitioned appropriately

so that all of the values less than the pivot come before and all of those greater come afterwards, I'll have two subarrays. I'll have those that come before the pivot and those that come after the pivot. All I have to do to finish off quicksort is to recursively call the Quicksawad algorithm on each of those subarrays in turn. So that means I pick a new pivot in the first subarray of elements that are less than the original pivot,

and then I pick another pivot again in the second subarray of elements that are greater than the original pivot, and then I perform partitioning on those, and I keep going, sort of breaking it up and down further and further, until everything's in the correct order. A recursive algorithm is one that calls itself, and they're potentially hard to understand, you haven't encountered the concept before, but they're very useful. So you may have to go and look up an animation of QuickSort to see exactly how this recursive thing works, but it's actually quite elegant the way it works, the way it's able to sort the entire list just by arranging elements in terms of whether it's greater or less than the pivot. And anyway, the point is that QuickSort

is guaranteed, assuming you start with an appropriately formatted list, guaranteed to yield a correctly sorted list in a finite number of steps. And so in this way, it constitutes an algorithm for sorting a list. Very crudely put, programming involves a judicious combination of these key elements of selecting data structures, selecting control structures, implementing algorithms and other tricks and hacks that are used to ensure that you can design a program capable of performing the specified behaviors that you want it to. Now, to put all this together and give you a sense of how high-level programming actually works in practice, I'm going to go through a simple example of how you might code up a very basic game in a high-level programming language. Again,

this is not supposed to be an actual code. This is just an abstract description of how you might go about coding such a game. And the game that I'm going to think about is a space invaders game. So we've got to play a spaceship that sits at the bottom of the screen that you can move using the arrow keys. You can fire by pressing a space bar. The enemy ships come from the top of the screen and move down towards the player, and if they collide with the player, you'll lose a life. And you're aiming to try and shoot the ships. So that's the game that we want to try and code. So the first thing that you might want to do is define some image to represent the player spaceship. So this could just be an image file stored somewhere on the system, which we

would need to specify the address to, and we could set the program to display it in a certain size at some default position on the screen. We could then define a variable controlling the vertical and horizontal positions of the player ship and set up a key binding event so that whenever one of the arrow keys is pressed, the values defining the vertical and horizontal positions of player ship are increased or decreased appropriately so that the ship moves around as you would expect to with the pressing of the arrow keys. So that's probably going to involve some sort of system call which will require the program accessing input from the keyboard via the operating system, but we probably don't need all

of the details of that in order to program that in the high-level programming language. That will be fixed up at compilation. Now we'll also need a way of showing the bullets that I'm firing at the enemy ships. I'll have to either create those objects when the space bar is pressed, so another key binding event, or possibly I'll create them initially and just make them invisible by default and only visible when I press the space bar. So I'll want them to appear at a default position above the player ship whenever the space bar is pressed, and also I'll need them to move upwards in a regular rate at the screen, because obviously the bullets have to move forward.

So one way I could do that is to loop over all of the visible bullets, so I could have a loop saying like if the bullet dot visible equals true, then for all of the bullets take their vertical position and add one to it so that they all move up a certain amount in a given, say, frame of the game. We could also have a test condition so that once a certain vertical location of the bullets was reached corresponding to the top of the screen, then the bullet was either deleted or rendered invisible. The enemy ships, again the appearance of these ships would need to be defined by an externally loaded image. I could I could set up code so that their location on the screen was generated randomly, somewhere,

the horizontal location was generated randomly at a set vertical location so that they appear on the screen. I could also time their appearance randomly, or they could appear at set intervals, depending on how I wanted to run the game. I could do that using random number generators, which all high-level languages will have access to. Like the bullets, I could loop over all of these, so all of the ones that are visible. I could reduce their vertical positions at each clock tick of the game, not the processor clock. not the processor clock, but the game, so that they gradually move down the screen

and come closer to the player. In order to enable me to actually destroy the enemy ships with my bullets, I'll need to have some sort of additional loop over each bullet so that I loop over all of the visible bullets and then have a conditional saying essentially if the position of this particular bullet is between the leftmost position of an enemy ship and the rightmost position of that enemy ship

and also between the bottom and top of the image of that enemy ship. So essentially if the location, of the bullet and the ship overlap, then the bullet and ship will be deleted and an additional image showing an explosion will briefly appear and then disappear, and also the score count will need to be incremented because I've destroyed one of the enemy ships. If those overlaps don't happen, then nothing will happen and the bullet will just keep going. I'll also need to implement another similar collision detection mechanism that will be employed to check if the locations of any of the enemy ships overlap with the location of the player ship, player ship, in which case both of the ship should be destroyed and a game over message would printed on the screen because I've been blown up.

So that's just a very crude illustration of how I might implement a simple Space Invaders game, giving you the sense of how I could use control structures and simple algorithms to implement this. Obviously actual games are much more complicated than this and use much more complicated mechanisms, but hopefully you get the basic sense of how you might do this. Okay, so that brings us to the conclusion of all of the material I wanted to cover in this series of six episodes on how computers work. To finish out now, I just want to go over and sort of integrate and put together what we've talked about, and I think to do so I'll use the example

of this little Space Invaders game that I just discussed, and essentially just talk through all of the key concepts, or at least some of the major concepts that we've addressed, to integrate our understanding of how a computer works. So we'll start with our Space Invaders game, which has been presumably coded in a high-level programming language, using all of the these if and four loops and appropriate data structures and algorithms and so on in order to be able to tell the ships what to do when the bullets traveling in the right directions and blowing up of ships when the bullets overlap with the ships and so on. So that's all been implemented in a high-level language. In order to run that program, we need to compile it into machine code, which the actual

processer can understand and execute. And that's done by a special program, a software called a compiler, which identifies all of the tokens and puts them in a logical ordering and then translates them into machine language. This machine language program is just a series of zeros and ones, each of which corresponds to a single machine instruction. Each of these machine instructions will be one of the relatively small number that are contained in the instruction set architecture of the particular type of processor that the software is going to be running on. Each of these machine instructions will need to specify an op code, which is just a series of bits that tells the processor which operation it's going to perform. And the instruction will also need to contain some information about where to get the data, that it performs the operation on and where to put the results. So this could include specifying a memory address or the actual number itself or the string or whatever it is, or one of the registers, one or more of the registers, etc., depending on the addressing mode that's being used by that instruction. In order to actually carry out the particular instruction in the processor,

what happens is that the instruction is loaded from memory into the instruction register, which is just a sequence of flip-flops, each of which holds a single bit. The values of the bits in the instruction register are then sent to the control unit, which generates a series of control signals, which are sent to all of the different components in the processor in order to ensure that the operations that are needed are carried out. This can include activating tristate buffer devices or selecting the correct input of a multiplexar, selecting the right input of the ALU and other such operations to ensure that the correct data is moved from one register to the other,

or that the right operation and the ALU is performed, or that the correct memory location is loaded into the program counter, which is the register that points to the next instruction to be carried out, etc., etc. So this is all carried out by the signals coming from the control unit, which in turn are dependent upon the instruction currently loaded in the instruction register. The ALU is the combinatorial circuit that carries out the actual computations of the processor, and that's implemented as a combinatorial logic circuit, which can carry out operations like add and subtract, logical operations, comparisons, etc.

If the program that I'm running wants to access input or output, for example, if it wants to determine whether I've pressed one of the arrow keys or spacebars in order to control my ship, it needs to execute a set. system call, which essentially jumps the program counter to an address in a particular set-aside region of the main memory where the operating system is saved. So it jumps to a particular location there and begins to run the code that is necessary in order to carry out the necessary system call. The operating system takes over from the process that was currently running from My Game. It reads the values of certain registers that were set beforehand that tells it what

system call that wants to carry out, and then it goes ahead and carries out that system call, which can include reading data from the special registers that save the input, for example, from the keyboard. That mode of input addressing is called address mapping, so effectively in order to read the value of the keyboard that's been ready, and all of the program needs to do, is read the data on the registers that the keyboard input is specifically saved to, and then that sends it over to the CPU. The operating system saves it in a location, in a register or perhaps in main memory where my program I gain can access it, then it hands back, once it's done with the system call it, hands back control to my

program, which then is able to read the data and carry on with carrying out its instructions as it needs to. All of these operations are implemented using logic gates connected by wires. A logic gate is in turn made up of transistors. A transistor is just a switch that can neither be switched to off or on, depending upon the voltage of the gate unit, which is a section of the transistor, the voltage that I apply to that gate region determines whether the switch goes on or off. And by applying the right voltages to the right gates at the right times, I am able to activate them in a way that computes functions that I need,

for example, and gates or inverters or decoders which take in an address and produce and activate the output of one particular address line, which I can use, for example, to access an address memory. Remember that the type of logic that's used to implement logic gates in computers these days is called CMOS, which stands for complementary metal oxide semiconductors, and that means that it uses both a P-MOS and an N-MOS in combination in order to implement the gate. The basic idea is that the input of a logic gate is connected up directly to the gate regions of the transistors, and so depending on whether the voltage applied to that gate region of the transistors, and so depending on whether the voltage applied to that gate region of the transistors,

this is high or low, the switch will either turn on or off. And as the switch either turns on or off, it connects up, it will either connect or disconnect a circuit, which connects the output wire either to a high voltage source or a low voltage source. So the input wires and the output wires in transistors never directly electrically connect with each other. The input wire controls the voltages on the gates, which in turn turns the switches on and off, and those switches then determine whether the output is ultimately connected up to a high voltage or low voltage. And and thus connecting these transistors up in the appropriate ways, I can ensure that the correct functions, whether it's inversion or an or gate or whatever, that the correct functions are implemented in the logic gate. The transistors, in turn, which I used to make modern computer devices, are called mosfets, metal oxide, semiconductor, field effect transistors. Essentially, these work by having semiconductors,

one connected to a source wire, one connected to a drain wire. When the switch is on, a channel forms between the source and the drain. regions, which connects them up electrically and allows current to flow or allows voltages to be equalized across the source and the drain, when the switch is off, that channel disappears and the current no longer flows, or the voltage is no longer equalize. I can control the existence of the channel, and thus whether the switch is on or off, by controlling the voltage on the gate of the transistor. This is a so-called field effect. By applying a voltage, I can ensure that the channel is brought into existence or ensure that it does not exist, and thereby a affect whether the switch is on or off. And this all comes down to the fact that when I have two different types of semiconductors

next to each other, the P type and the N type, the different types of charges flow towards each other. The N-type charges, which are electrons and the P-type charges, which are holes, or the absence of an electron, flow towards each other, and create a depletion region in which there are no charge-carrying particles, and thus charge won't flow. The channel is an inversion layer, the channel that links up the

source to the drain is an inversion layer, meaning that it's got the opposite type of charge, that would normally be in abundance there. That's only possible if I apply the right voltage to the gate. Either a high voltage, in the case of an NMOS, the high voltage potential applied to the gate, attracts electrons, which then bunch up near the gate, and form at the inversion layer where there are more electrons than normal,

thus linking up in the channel the source and the drain and allowing a current to flow. In the case of a P-MOS device, it's the opposite. Instead of a high voltage attracting electrons forming a channel, turning the switch on, a low voltage attracts holes or positive charges which forms the channel between the source and the drain turning the switch on. So in either case, the field effect is used to adjust the voltage that's present just under, just in the well region underneath the gate, and thus whether there is an electrical connection between source and drain or not. That's fundamentally how a transistor works.

And all of this is based on the properties of semiconductors, semiconductors being materials like silicon, which have a conductivity in between that of conductors like metals or insulators like glass. Semiconductors have the properties they do because they're Fermi level, which is effectively the outer edge of the field electron levels, because remember electrons will fill up lower levels first, and then increasingly they'll fill up higher and higher levels. The Fermi level is sort of the outer limit of the field levels. Of course, it's not a precise demarcation because thermal effects

mean that some electrons are excited up to higher energy levels than they would normally be, but the Fermi level roughly indicates where the edge of the filled electrons is. In order for a material to carry a current, there need to be accessible free electron energy levels that the electrons can go into and then move about to carry the charge. Metals have plenty of these free electron energy levels because their Fermi level sits right in the middle of a nice wide band of available electron levels that the electrons can be excited into, so they're easy to, they are easily able to carry a current. Insulators have a big wide band gap just in the area of corresponding to their Fermi level, which essentially means that all the electrons are

stuck down in lower energy levels, and there's too much of an energy gap for them to jump over up into the higher energy levels that they would need to in order to be able to conduct. Semiconductors are in between those two extremes, so they still have an energy band gap that's cited around the Fermi level, but it's much smaller, so only a smaller amount of additional energy needs to be added in order to get them to conduct a current. So semiconductors are able to conduct electricity, but not quite as well as a metal, and thus they are ideally suited for making transistors because their conductivity can be significantly affected by using the field effect. So this ultimately is how the behavior of a computer is reduced via a series of levels

down to the behavior of the underlying electrons that make up the silicon and other materials used in its construction. So in this series of six podcasts, we have discussed the organization and design of computers right from the level of the properties of silicon and semiconductors at the atomic level to explain how those are used to construct transistors at the level of electronic components. I've discussed how transistors are combined together in Seymost Logic to produce logic and how logic gates are in turn combined together in various ways to produce logical components like multiplexers, adders, and registers. We then in the processor architecture podcast discussed how these logical components are combined together

to produce the central processing unit and main memory, and how those interact with each other to carry out machine instructions, which is understood by the processor as a series of zeros and ones in binary form. We discussed how a program is a set of machine instructions which are executed sequentially, and how writing those is made much easier by the use of assembly language, which is a symbolic shorthand, an abstraction, that is converted into actual machine code by a program called an assembler. We also talked about high-level programming languages like Java and Python, and how those are able to streamline the process of writing programs and make it easier by writing them at a more abstract level,

and then compiling them into machine code using a special program called a compiler, which in turn can be run directly on the processor. So, hopefully you enjoy. this series of podcast. I certainly enjoyed preparing all the material. It was quite ambitious, but I think we largely achieved the goals that I wanted to. If you're interested in some more information about computer architecture and design, I have prepared a series of notes that I used in recording these episodes, which I'll post a link up to on the Facebook page, probably a PDF or something. These are just sort of fairly informal notes that I've prepared that largely replicate the material

in the podcast, but might be useful for your review and include lots of diagrams as well. I might include links to some other sources as well that you can consult. There's quite a bit of good material online about this sort of stuff that goes into much more detail, obviously, than I was able to hear. So, hopefully you enjoyed these podcasts. If so, I'd encourage you to jump onto iTunes or a similar podcast aggregator of your choice and leave a favourable review of the podcast. Another thing you can do is send me an email. My email address is FOD12 at gmail.com. F-O-D-S-1-2 at gmail.com. I welcome any suggestions, feedback, questions, or just saying hi, I always like to hear from my listeners.

Thank you very much for listening, and I'll talk to you next time.