1 00:00:04,024 --> 00:00:09,010 Hello, in this and the next few videos I'm going to be giving a overview of COOL the 2 00:00:09,010 --> 00:00:17,061 programming language in which you'll be writing a compiler. Cool is the Classroom 3 00:00:17,061 --> 00:00:23,087 Object Oriented Language and the acronym of course, is COOL. And the unique design 4 00:00:23,087 --> 00:00:29,073 requirement for COOL is that the compiler has to be able to be written in a 5 00:00:29,073 --> 00:00:35,060 relatively short period of time. We only have one quarter, or in some cases, a 6 00:00:35,060 --> 00:00:40,078 semester for students to write the compilers. And so COOL has to be 7 00:00:40,078 --> 00:00:47,007 implementable quickly. And actually since it's used primarily for teaching 8 00:00:47,007 --> 00:00:52,027 compilers, the number of COOL compilers in the world vastly exceeds, the number of 9 00:00:52,027 --> 00:00:56,099 COOL programs. So, there many, many more compilers have been written, thousands of 10 00:00:56,099 --> 00:01:01,065 compilers, maybe tens of thousands of compilers have been written for COOL, but 11 00:01:01,065 --> 00:01:06,026 probably only some dozens, or hundreds COOL programs. And so, it's probably the 12 00:01:06,026 --> 00:01:10,086 only language, in existence for which this is true, That, that, the number of 13 00:01:10,086 --> 00:01:15,067 compilers actually exceeds the number of programs, but it does Tell you about the 14 00:01:15,067 --> 00:01:20,019 main design requirement. It's much more important in COOL that the compiler be 15 00:01:20,019 --> 00:01:25,006 easy to write then that it be easy to write programs in. And so there are some 16 00:01:25,006 --> 00:01:29,092 quirks in the language, Things that have been done specifically to make it easier 17 00:01:29,092 --> 00:01:34,097 to implement where that wouldn't take away from the, the teaching value of the, of 18 00:01:34,097 --> 00:01:39,043 the language. But that would make it inconvenient to use the language on a 19 00:01:39,043 --> 00:01:43,099 day-to-day basis as a working programmer. So, what is in the language? Well it's, 20 00:01:43,099 --> 00:01:48,031 we've tried to design it so that it will give you a taste of modern notions of 21 00:01:48,031 --> 00:01:52,095 extraction static typing reuse through inheritance, automatic memory management. 22 00:01:52,095 --> 00:01:57,032 And there's actually a few more things that we'll talk about when we come to 23 00:01:57,032 --> 00:02:02,018 them. But many things are left out. We're not gonna be able to put everything in the 24 00:02:02,018 --> 00:02:06,038 language and have it be implementable quickly. We'll be able to cover some 25 00:02:06,038 --> 00:02:10,075 things in lectures, but unfortunately, there'll even be some interesting language 26 00:02:10,075 --> 00:02:17,039 ideas that we won't be able to get to in this class. So the course project is to 27 00:02:17,039 --> 00:02:21,065 build a complete compiler. And specifically you're going to compile COOL 28 00:02:21,065 --> 00:02:26,074 into MIPS assembly language. So MIPS is a real instruction set, It was for a machine 29 00:02:26,074 --> 00:02:31,070 that was designed in the 1980's. And there is a simulator for MIPS that runs on just 30 00:02:31,070 --> 00:02:35,096 about any kind of hardware. And so this makes the, the whole project very 31 00:02:35,096 --> 00:02:41,011 portable, We can run your compiler, or you can generate MIPS assembly language and 32 00:02:41,011 --> 00:02:45,090 then that MIPS assembly language can be simulated on just about whatever kind of 33 00:02:45,090 --> 00:02:50,074 machine you have access to. The project is broken up into five assignments. First 34 00:02:50,074 --> 00:02:55,025 you're gonna write a COOL program. And that program itself will be an interpreter 35 00:02:55,025 --> 00:02:59,057 to give you a little bit of experience with writing a simple interpreter. And 36 00:02:59,057 --> 00:03:03,063 then the compiler itself will consist of the four the phases that we discussed 37 00:03:03,079 --> 00:03:07,068 lexical analysis, parsing, semantic analysis and code generation. And all of 38 00:03:07,068 --> 00:03:11,089 these phases, I should emphasize are [inaudible] compatible. Meaning that we 39 00:03:11,089 --> 00:03:16,073 have separate implementations, separate reference implementations of each of 40 00:03:16,073 --> 00:03:21,075 these. And so for example, when you are working on semantic analysis, you will be 41 00:03:21,075 --> 00:03:26,040 able to take the lexical analysis, parsing, and code generation components 42 00:03:26,040 --> 00:03:31,054 from the reference compiler and plug your semantic analysis into that. Framework 43 00:03:31,054 --> 00:03:35,078 and, and test it against the reference components. And so this way if you have 44 00:03:35,078 --> 00:03:40,039 trouble with one component or aren't sure that your components is working very well 45 00:03:40,039 --> 00:03:45,000 you won't have a problem in working on a different component because you'll be able 46 00:03:45,000 --> 00:03:49,087 to test that independently. And finally there's no required optimization 47 00:03:49,087 --> 00:03:55,005 assignment, But we do have some suggestions for optimizations that you can 48 00:03:55,005 --> 00:04:00,037 do. And many people have written optimizations for COOL. And so this is an 49 00:04:00,037 --> 00:04:05,096 optional assignment if you're interested in learning something about program 50 00:04:05,096 --> 00:04:17,069 optimization. So, let's write the simplest possible COOL program. And the first thing 51 00:04:17,069 --> 00:04:23,075 to know is that COOL source files, and in the extension dot CL for COOL, and you can 52 00:04:23,075 --> 00:04:29,067 use whatever editor you like to write your programs. I happen to use Emacs, you can 53 00:04:29,067 --> 00:04:35,051 use some other editor if you like. And every COOL program has to have a class 54 00:04:35,051 --> 00:04:40,038 called main. And let's talk about that business in a second. So a class 55 00:04:40,038 --> 00:04:45,057 declaration in COOL begins with the key word, class, Followed by the name of the 56 00:04:45,057 --> 00:04:50,081 class, So in this case, main, Followed by a pair of curly braces And inside the 57 00:04:50,081 --> 00:04:56,026 curly braces is where all the stuff that belongs to the class goes, And every class 58 00:04:56,026 --> 00:05:01,011 declaration must be terminated by a semi-colon. So a program consists of a 59 00:05:01,011 --> 00:05:06,036 list of class declarations. Each class declaration terminated by a semi-colon. So 60 00:05:06,036 --> 00:05:11,028 that's the structure of a class. And now we need this class to actually do 61 00:05:11,028 --> 00:05:16,099 something so we're going to have a method in this class, and let's call the method 62 00:05:16,099 --> 00:05:22,037 main. In fact the main method of the main class must always exist. This is the 63 00:05:22,037 --> 00:05:27,075 method that's run to start the program and furthermore this method must take no 64 00:05:27,075 --> 00:05:33,033 arguments. So the empty argument list for the main method is always empty. And let's 65 00:05:33,033 --> 00:05:39,020 say the main method its body always goes in a pair of curly braces. So the main 66 00:05:39,020 --> 00:05:44,063 method always goes inside curly braces. And a class consists of a list of such 67 00:05:44,063 --> 00:05:49,030 declarations. And again, those declarations must all be separated by 68 00:05:49,030 --> 00:05:54,046 semicolons. So in, or terminated, excuse me, by semicolons. So in this case, we 69 00:05:54,046 --> 00:05:59,026 only have one method in the class. But still has to have its semi-colon and now 70 00:05:59,026 --> 00:06:03,013 we can say what we want the method actually do so this is the place for the 71 00:06:03,013 --> 00:06:07,030 code for the method goes and let's just have the simplest possible method the one 72 00:06:07,030 --> 00:06:11,064 that just event evaluates to the number one. Okay, so [inaudible] an expression 73 00:06:11,064 --> 00:06:16,036 language, which means that wherever a piece of code can go, you can put an 74 00:06:16,036 --> 00:06:21,025 arbitrary expression, any expression can go there there's no explicit return 75 00:06:21,025 --> 00:06:26,040 statement for a method. It's just a value of the method body is the value of the 76 00:06:26,040 --> 00:06:31,042 methods. So in this case we just put the number one in there, and that will be the 77 00:06:31,042 --> 00:06:36,066 value of this method when we run it. So let's save that. And now we can try 78 00:06:36,091 --> 00:06:43,091 compiling this simple program, so how do we compile the compiler is called a COOL c 79 00:06:43,091 --> 00:06:50,067 for the COOL compiler and you just give the COOL compiler a list of COOL source 80 00:06:50,067 --> 00:06:56,086 files. So in this case there's just one file 1.CL hit enter and ooh we got a 81 00:06:56,086 --> 00:07:03,069 syntax error so we have to come back and fix that and the error said at or near the 82 00:07:03,069 --> 00:07:09,048 open curly brace on line three there's a mistake. And I know what the mistake is, 83 00:07:09,048 --> 00:07:13,071 because I'm a competent COOL programmer, at least somewhat competent COOL 84 00:07:13,071 --> 00:07:18,023 programmer. Cool methods must declare their return type. So we need to put a 85 00:07:18,023 --> 00:07:22,046 type here. And the syntax for the declaration is to put a colon after the 86 00:07:22,046 --> 00:07:27,004 name of the method and the argument list, and then the name of a type. And since 87 00:07:27,004 --> 00:07:32,002 we're returning the number one for this program for sorry, for this method we 88 00:07:32,002 --> 00:07:36,077 might as well say that the main method is going to return an integer, So save that, 89 00:07:37,069 --> 00:07:43,099 Go back to our compilation window and let's compile the program again. And this 90 00:07:43,099 --> 00:07:50,069 time it compiles successfully. And now if we look in our directory we see that there 91 00:07:50,069 --> 00:07:57,015 is a new file called 1.s. That's the assembly code for the program one. And now 92 00:07:57,015 --> 00:08:03,062 we could try to run this code. And the, The, the Mitch simulator is called spin, 93 00:08:03,062 --> 00:08:09,063 and it just takes a, assembly file to, to simulate, And so we just give it one 94 00:08:09,063 --> 00:08:15,081 [inaudible] hit enter and it will run. A whole bunch of stuff is printed out. But 95 00:08:15,081 --> 00:08:20,056 as you can see, it says part way down that the COOL program successfully executed, so 96 00:08:20,056 --> 00:08:25,016 that's good, and then afterwards there are some statistics and things like number of 97 00:08:25,016 --> 00:08:29,042 instructions executed, a number of loads and stores, a number of branches, those 98 00:08:29,042 --> 00:08:33,063 things would be interesting if we're worried about performance if we were to 99 00:08:33,063 --> 00:08:38,006 say working on the optimization of the compiled code, but we're not doing that 100 00:08:38,006 --> 00:08:43,006 right now. We're just running programs. And we can see if this program works. So 101 00:08:43,006 --> 00:08:47,019 the program ran. It terminated successfully. But it didn't actually 102 00:08:47,019 --> 00:08:52,096 produce any output. And that's because we didn't ask it to produce any output, If we 103 00:08:52,096 --> 00:08:57,084 want to have output. We have to go back and modify the program again. So, so what 104 00:08:57,084 --> 00:09:02,007 this program does currently, is that it just returns its value but that, but 105 00:09:02,007 --> 00:09:06,097 nothing is done with that value. It's not printed out or anything like that. If you 106 00:09:06,097 --> 00:09:11,032 wanted to have something printed out in a COOL program, you have to do that 107 00:09:11,032 --> 00:09:16,005 explicitly. So there's a special class built in, a primitive class called IO. And 108 00:09:16,005 --> 00:09:24,013 we can declare, what's called a attribute of this class, it will be a IO attribute 109 00:09:24,013 --> 00:09:31,082 and it will be called I, okay and I will be a object that we use to do IO. So now 110 00:09:31,082 --> 00:09:38,076 in our, main method, Here we could add a call to out-string, I dot out-string is 111 00:09:38,076 --> 00:09:45,072 how we invoke a method. Okay so out-string is a method of the IO class so we use I to 112 00:09:45,072 --> 00:09:52,059 invoke that method and then we can pass it a string that we want printed out on the 113 00:09:52,059 --> 00:10:04,031 screen. So for example we could say hello world. Okay, And now, we have to decide 114 00:10:04,031 --> 00:10:10,046 what to do, with our, with our number one there. And let me show you one more 115 00:10:10,046 --> 00:10:14,058 feature of COOL. Let's leave the one there, and let's make it part of a 116 00:10:14,058 --> 00:10:18,082 statement block. So a statement block consists of a sequence of expressions 117 00:10:18,082 --> 00:10:23,005 separated by semicolons. And you can have any number of expressions, and the 118 00:10:23,005 --> 00:10:27,045 semantics of a statement block or an expression block is to just evaluate the 119 00:10:27,045 --> 00:10:32,020 expressions in order. And the value of the block is the value of the last expression. 120 00:10:32,020 --> 00:10:36,071 But now, a statement or an expression block has to be included in its own set of 121 00:10:36,071 --> 00:10:43,008 curly braces. Okay, so that now is a valid COOL program so let me just read this for 122 00:10:43,008 --> 00:10:49,096 you so the body of the program is a block of expressions. The first one, executes. A 123 00:10:49,096 --> 00:10:55,014 out string call to the object I, which is going to print hello world for us. And 124 00:10:55,014 --> 00:11:00,045 then the second one evaluates to one, which is the value of the entire of the 125 00:11:00,045 --> 00:11:05,044 entire method. Okay, actually I should say it's the value of the block, okay, and 126 00:11:05,044 --> 00:11:11,020 then because the block is the body of the method the value of the block becomes the 127 00:11:11,020 --> 00:11:16,063 value of the entire method, So one will be returned from this method call. So let's 128 00:11:16,063 --> 00:11:26,001 save this. Go back over here and let's compile this again. So, Looks like I 129 00:11:26,001 --> 00:11:38,022 failed to save it. Let's compile this and we see we have a syntax error. And so it 130 00:11:38,022 --> 00:11:45,004 says on line four, we have a syntax error at or near our closing curly brace. And 131 00:11:45,004 --> 00:11:51,063 the problem here is that a statement block, or expression block consists of a 132 00:11:51,087 --> 00:11:58,012 series or a sequence of expressions terminated by semi-colons, and we forgot 133 00:11:58,012 --> 00:12:05,003 to terminate the last expression in the sequence by its semi-colon, So we have to 134 00:12:05,003 --> 00:12:11,048 add that. And now we should be able to compile this, and lo and behold it 135 00:12:11,048 --> 00:12:18,068 compiles correctly, and then we can run it. And now we see, oh we got another 136 00:12:18,068 --> 00:12:24,087 mistake. So we have an, when the program ran it complained that we have a 137 00:12:24,087 --> 00:12:30,038 dispatched void. So that on line four, our dispatch was to an object that didn't 138 00:12:30,038 --> 00:12:35,055 exist. And, you can see the dispatch call right here to I, and it doesn't exist, 139 00:12:35,055 --> 00:12:41,019 because, in fact, we forgot to allocate an object for I. So here we declare I to be 140 00:12:41,019 --> 00:12:46,070 of type IO, but that doesn't actually create any objects. That just says that it 141 00:12:46,070 --> 00:12:52,041 creates a variable name I but I doesn't actually have a value. So if you want I to 142 00:12:52,041 --> 00:12:57,031 actually have a value, we have to initialize it to something. So we can 143 00:12:57,031 --> 00:13:02,079 initialize it to a new IO object. And new here, is the way you allocate new objects 144 00:13:02,079 --> 00:13:07,087 in COOL and new always take a type argument so in this case were creating a 145 00:13:07,087 --> 00:13:13,045 new object in type IO and were assigning it To this object i. And notice here that 146 00:13:13,045 --> 00:13:18,087 I is a, is a, is what would be called a field name in Java. It's what we call an 147 00:13:18,087 --> 00:13:24,050 attribute in COOL. So, so these are the data el, the data elements of the, of the 148 00:13:24,050 --> 00:13:30,041 class. And so the class can have both of names of things that are so, attributes or 149 00:13:30,041 --> 00:13:37,012 fields that hold values as well as methods that can perform computation. [sound] 150 00:13:37,044 --> 00:13:48,010 Let's save this and switch back. And now we'll compile this again. So and it still 151 00:13:48,010 --> 00:13:54,010 compiles. And now we can run it. And now it runs, and low and behold, as you can 152 00:13:54,010 --> 00:13:59,065 see down there third line from the, the top, it prints out hello world. And that 153 00:13:59,065 --> 00:14:05,092 looks a little bit ugly because the, the successful execution message is on the 154 00:14:05,092 --> 00:14:11,068 same line as our hello world message. So let's fix that. Let's come back over here. 155 00:14:11,068 --> 00:14:17,024 And in our string here we can add a new line. Okay at the end of the string, so 156 00:14:17,024 --> 00:14:22,094 backslash N is how you write a new line character in the string. Save that, come 157 00:14:22,094 --> 00:14:28,027 back over here let's compile. So if you don't know Unix bang will repeat the 158 00:14:28,027 --> 00:14:33,060 previous expression the previous command that began with the same prefix that you 159 00:14:33,060 --> 00:14:38,086 type after the bang. So I want to run the last command that began with C which is to 160 00:14:38,086 --> 00:14:44,000 compile and then I want to run the last command that began with S which is to run 161 00:14:44,000 --> 00:14:49,020 spin. And now we can see there it is all nice hello world is on a line by itself. 162 00:14:50,063 --> 00:14:57,014 Let's continue now, let's [sound] clear all this out [sound]. So let me just show 163 00:14:57,014 --> 00:15:02,055 you a few variations on the same program. What I'm going to do here is just rewrite 164 00:15:02,055 --> 00:15:07,045 it in a couple of different ways. So I just illustrate a couple of features of 165 00:15:07,045 --> 00:15:12,010 COOL and get you more familiar with the syntax, and also just show some 166 00:15:12,010 --> 00:15:17,082 alternative ways to do the same thing. So you know this, this. A block here of, of 167 00:15:17,082 --> 00:15:24,002 expressions is kind of a clumsy way to, to implement the Hello World program. So 168 00:15:24,002 --> 00:15:30,015 let's get rid of that. Let's get rid of the, the block. Let's get rid of the one 169 00:15:30,015 --> 00:15:36,002 here at the end. Okay, let's just make the statement body a single expression again, 170 00:15:36,002 --> 00:15:41,027 and, and now the problem we're going to have is that the types won't match. But 171 00:15:41,027 --> 00:15:46,093 just to illustrate that, let me show it to you so let's do COOL C of one dot CL, and 172 00:15:46,093 --> 00:15:52,046 you'll see here that in complains that the inferred return type of the IO of the 173 00:15:52,046 --> 00:15:57,058 method main does not conform to the declared return type INT. So coming back 174 00:15:57,058 --> 00:16:03,010 over here, the, to the program, The, the compiler figured out that this expression, 175 00:16:03,010 --> 00:16:07,069 I dot out string, yields an object of type IO. So it returns the i object as the 176 00:16:07,069 --> 00:16:12,034 results evaluating this expression. And that does not match the type it. And so 177 00:16:12,034 --> 00:16:16,070 naturally, the compiler says, hey, something's wrong with the types. Well, 178 00:16:16,070 --> 00:16:21,071 that's easily repaired. We can just change the return type or the main method to say 179 00:16:21,071 --> 00:16:28,085 it returns something of type IO. So let's go back over here and see if that now 180 00:16:28,085 --> 00:16:36,060 works. So, we compile the program. And then we run spin on the output, and yes, 181 00:16:36,060 --> 00:16:42,040 everything still works as expected. Now, We don't have to be so specific about the 182 00:16:42,040 --> 00:16:47,032 type over here, since we're not actually using the result of the method body for 183 00:16:47,032 --> 00:16:52,036 anything. I mean, the program just exits once it prints the string. We could have 184 00:16:52,036 --> 00:16:57,040 allowed ourselves more flexibility here. We could've just declared the result type 185 00:16:57,040 --> 00:17:02,026 of main to be of type Object. So Object is the root of the class hierarchy in COOL. 186 00:17:02,044 --> 00:17:07,042 Every other class is a subclass of Object. So let's come back over h, let's save this 187 00:17:07,042 --> 00:17:13,059 first. And then we can come back over to our compilation window. We can compile it. 188 00:17:13,059 --> 00:17:22,047 And we can run it and it still works. So now another thing we can do if we want, is 189 00:17:22,047 --> 00:17:29,024 we could observe. Here that this attribute that we declare, this field I isn't really 190 00:17:29,024 --> 00:17:34,099 necessary. Here we, we allocate, you know we have a special name I when the main 191 00:17:34,099 --> 00:17:41,018 object is constructed to run the program, a new [inaudible] object is allocated to I 192 00:17:41,018 --> 00:17:46,063 and then that gets used in the main method. We can actually just do all of 193 00:17:46,063 --> 00:17:52,090 that inside the main method itself by just allocating a new [inaudible] object right 194 00:17:52,090 --> 00:17:59,011 here and then calling out string on that object. Alright, So this should also work. 195 00:18:00,057 --> 00:18:11,025 And let's check it out. So it compiles. And lo and behold, it rots. Alright, So 196 00:18:11,025 --> 00:18:17,040 coming back over here let's illustrate one more, or a couple more things that we 197 00:18:17,040 --> 00:18:22,067 could do. So, we could also say that [inaudible] inherits From IO. So we have 198 00:18:22,067 --> 00:18:27,083 to have the IO functionality somewhere in order to call the out string method. So we 199 00:18:27,083 --> 00:18:32,039 have been doing that by creating a separate object of type IO. But now we can 200 00:18:32,039 --> 00:18:36,060 say well just the main object is itself. And something that has all the 201 00:18:36,060 --> 00:18:41,046 capabilities of IO by inheriting from IO. And if you've seen any [inaudible] 202 00:18:41,046 --> 00:18:45,085 language before this will be a familiar concept. So main here gets all the 203 00:18:46,003 --> 00:18:51,013 attributes and methods of IO, in addition to whatever attributes and methods of its 204 00:18:51,013 --> 00:18:56,099 own that it will have. And now Instead of, of having to allocate a new IO object in 205 00:18:56,099 --> 00:19:02,063 order to call out string, we can just invoke it on self, Which is the name of 206 00:19:02,063 --> 00:19:08,072 the current object when the main method runs In other languages self is called 207 00:19:08,072 --> 00:19:14,081 this. Okay, and so let's we saved it, so let's go over and compile this. So it 208 00:19:14,081 --> 00:19:21,039 compiles, it compiles and, and it runs, right? So last example here, we don't have 209 00:19:21,039 --> 00:19:28,029 to name self actually in this dispatch. There's a feature that allows us to call a 210 00:19:28,029 --> 00:19:34,024 method without explicitly naming the object on which it's dispatched and 211 00:19:34,024 --> 00:19:40,082 defaults to self, so if no object is named in a dispatch then it's just a dispatched 212 00:19:40,082 --> 00:19:49,096 self. So this should also work. [sound], And indeed it does. So that concludes our 213 00:19:49,096 --> 00:19:54,054 first example. In the next couple of videos we'll look at some more complex 214 00:19:54,054 --> 00:19:56,031 examples of COOL programming.