1 00:00:06,710 --> 00:00:10,120 We've come to the end of our eight-week course in a course. 2 00:00:10,120 --> 00:00:13,600 So what have you learned? A lot, I think. 3 00:00:14,860 --> 00:00:18,700 For those of you who never programmed before, I hope you have a better 4 00:00:18,700 --> 00:00:22,120 understanding of how some of the computational systems in the world around 5 00:00:22,120 --> 00:00:25,430 you might work. And how the people who design those 6 00:00:25,430 --> 00:00:31,470 systems go about their work. So I hope from that the world you feels 7 00:00:31,470 --> 00:00:33,930 less mysterious than it did at the beginning of the course. 8 00:00:35,290 --> 00:00:40,400 I hope you also have the confidence now that you can design small programs that 9 00:00:40,400 --> 00:00:46,270 you know how to proceed systematically. Where to start, what to do first, what to 10 00:00:46,270 --> 00:00:48,950 do next, how to know you're making progress. 11 00:00:50,110 --> 00:00:52,470 Remember that's all systematic design means. 12 00:00:52,470 --> 00:00:53,220 It doesn't mean you don't make mistakes. It doesn't mean it isn't hard. 13 00:00:53,220 --> 00:01:00,530 It doesn't mean you never have to back up. 14 00:01:00,530 --> 00:01:05,030 What it means is knowing what to do at each point in time, knowing how to make 15 00:01:05,030 --> 00:01:09,150 progress, knowing how to break off small pieces of the problem and working on 16 00:01:09,150 --> 00:01:14,250 them. With that in mind, let me try to step 17 00:01:14,250 --> 00:01:17,660 back a bit from the details of the recipes we've been learning. 18 00:01:17,660 --> 00:01:22,020 And see sort of what they are a little bit more generally let's look first at 19 00:01:22,020 --> 00:01:25,540 information and data. What the recipe is telling us is that 20 00:01:25,540 --> 00:01:28,570 when you start designing your program you should start by looking at the 21 00:01:28,570 --> 00:01:32,330 information in the problem domain. You should figure out the natural 22 00:01:32,330 --> 00:01:36,500 structure of that information, you should design a data representation for that, 23 00:01:36,500 --> 00:01:40,416 you should work out the templates for operating on that data. 24 00:01:40,416 --> 00:01:46,550 If those templates are awkward, if for example the reference relationships don't 25 00:01:46,550 --> 00:01:49,880 look quite right, that's a good time to revise the representation. 26 00:01:51,560 --> 00:01:57,440 Notice none of that has quite exactly the details of the exact rules that we've 27 00:01:57,440 --> 00:02:01,330 done it in this particular language. But that's the general recipe we've 28 00:02:01,330 --> 00:02:03,710 learned for dealing with information and data. 29 00:02:03,710 --> 00:02:10,303 Let's look at function design. Well, to design each function what do we 30 00:02:10,303 --> 00:02:12,020 do? Well the first thing we do is we write 31 00:02:12,020 --> 00:02:16,750 down in different forms what the function should do. 32 00:02:16,750 --> 00:02:19,820 I've never said it quite that way before, but that's what we've been doing all 33 00:02:19,820 --> 00:02:23,050 along. The signature, the purpose and the 34 00:02:23,050 --> 00:02:28,420 example are three complimentary ways to describe what the function should do. 35 00:02:28,420 --> 00:02:33,390 By complimentary, I mean they should be consistent but they focus on different 36 00:02:33,390 --> 00:02:36,663 aspects of the functions behavior. As you're doing this, you look for 37 00:02:36,663 --> 00:02:41,206 contradictions along the forms. If your signature says it produces one 38 00:02:41,206 --> 00:02:45,900 thing and you've got an example that says it produces something else. 39 00:02:45,900 --> 00:02:48,150 You've got a problem, work on it right then. 40 00:02:48,150 --> 00:02:54,740 You should use each form to help you develop the other forms. 41 00:02:54,740 --> 00:02:59,720 You should test as often as possible. You should use stubs to help you test as 42 00:02:59,720 --> 00:03:02,900 often as possible. The sooner you find a mistake in an 43 00:03:02,900 --> 00:03:07,090 example or anything, the easier it is to fix. 44 00:03:07,090 --> 00:03:10,100 That especially becomes true as the examples get large. 45 00:03:10,100 --> 00:03:15,730 Stubs let you at least run the program even if tests are failing to make sure 46 00:03:15,730 --> 00:03:19,670 that things are well formed. Sometimes stubs can do even a little 47 00:03:19,670 --> 00:03:22,720 better than that. When you get to the actual function 48 00:03:22,720 --> 00:03:25,230 definition it can usually be developed in two stages. 49 00:03:25,230 --> 00:03:30,190 First a template which can either be a data driven template or another kind of 50 00:03:30,190 --> 00:03:33,200 template as we've seen with the Sudoku functions. 51 00:03:34,740 --> 00:03:39,420 Then, you fill in the details. Let's look at another aspect of the 52 00:03:39,420 --> 00:03:45,200 recipes having to do with decomposition. We know that breaking the design into 53 00:03:45,200 --> 00:03:49,820 parts helps manage complexity. And the key thing we've seen in this 54 00:03:49,820 --> 00:03:54,750 course is that there's lots of ways to break the design process in addition to 55 00:03:54,750 --> 00:04:00,599 that actual artifacts into pieces. We don't want to just have the structure 56 00:04:00,599 --> 00:04:05,305 of the final program be in pieces. We want to have the work process be in 57 00:04:05,305 --> 00:04:08,050 pieces. So there's analysis in program 58 00:04:08,050 --> 00:04:11,460 development phases, There's data and functions. 59 00:04:11,460 --> 00:04:14,450 There's steps of the process for each element type. 60 00:04:14,450 --> 00:04:17,370 For a world, we do this and then we do this and then we do this. 61 00:04:17,370 --> 00:04:20,970 For data, we do this and this and this. For functions and so on. 62 00:04:23,560 --> 00:04:28,660 Focusing now more on the actual code, the actual decomposition of the actual code 63 00:04:28,660 --> 00:04:31,570 structure. We should separate types along natural 64 00:04:31,570 --> 00:04:35,494 units of information. We should separate functions where that's 65 00:04:35,494 --> 00:04:39,436 indicated by the template. Or acknowledge domain shifts or where 66 00:04:39,436 --> 00:04:43,510 operating on arbitrary-sized data, or for function composition. 67 00:04:43,510 --> 00:04:45,670 Or for other kinds of rules that you'll learn as you go. 68 00:04:46,720 --> 00:04:50,490 Again, I've just stepped back a tiny bit from the details of our recipe. 69 00:04:51,820 --> 00:04:54,470 But this is the more general thing you've been learning all course. 70 00:04:54,470 --> 00:05:00,544 Now's a good time to look at the question: Can this design method work in 71 00:05:00,544 --> 00:05:04,640 other languages? So here's a simple function, or design 72 00:05:04,640 --> 00:05:08,380 for a simple function that takes a string and a list of strings, counts how many 73 00:05:08,380 --> 00:05:11,071 times that string occurs in the list of strings. 74 00:05:11,071 --> 00:05:15,775 And we'll go through the details. But here it is in Python on the right. 75 00:05:15,775 --> 00:05:19,950 And you know, the answer to the question can this method work in other languages? 76 00:05:19,950 --> 00:05:27,981 Is of course it can, look, if I look at a Python design for this function, there's 77 00:05:27,981 --> 00:05:38,204 the signature, there's the purpose, here's some check expects, there's the 78 00:05:38,204 --> 00:05:40,584 body of the function. There's even the template for operating 79 00:05:40,584 --> 00:05:44,270 on a list. Of course, you can develop functions in 80 00:05:44,270 --> 00:05:47,880 Python or any other language following this recipe. 81 00:05:47,880 --> 00:05:53,730 Also, of course, there are other and even better ways to write this Python code. 82 00:05:53,730 --> 00:05:59,460 This particular code was written to look very much like the code form our course 83 00:05:59,460 --> 00:06:03,230 in, in BSL and ISL. If you wrote this in more idiomatic 84 00:06:03,230 --> 00:06:05,580 Python, it would look a little bit different. 85 00:06:05,580 --> 00:06:08,675 There'd be other conventions for saying things like the signature and the 86 00:06:08,675 --> 00:06:11,715 purpose. There are other better unit test 87 00:06:11,715 --> 00:06:13,900 frameworks. This unit test framework I'm showing you 88 00:06:13,900 --> 00:06:17,495 works in Python but there are other ones. There's other ways for writing the 89 00:06:17,495 --> 00:06:21,865 templates. But those are all just details. 90 00:06:21,865 --> 00:06:26,305 Those are details of the exact form the recipes took. 91 00:06:26,305 --> 00:06:31,969 >> In the language we've been using. Let's go look at another example program. 92 00:06:31,969 --> 00:06:37,850 It's Peter Norvig's sudoku solver, this is actually a fairly well-known On 93 00:06:37,850 --> 00:06:41,080 program. It's got a webpage that describes it and 94 00:06:41,080 --> 00:06:45,230 at the bottom of the webpage, you can find a link to look at the actual 95 00:06:45,230 --> 00:06:48,004 program. If you look at that program, I think 96 00:06:48,004 --> 00:06:51,972 you're going to find that the structure of the design is very familiar to you, 97 00:06:51,972 --> 00:06:55,369 even though you may not know the details of the Python language. 98 00:06:56,470 --> 00:06:59,110 It follows the same general structure that our programs do. 99 00:06:59,110 --> 00:07:02,480 It starts with data definitions. Then there's contents. 100 00:07:02,480 --> 00:07:05,480 In this program the unit tests are all grouped together though, they're not 101 00:07:05,480 --> 00:07:08,601 spread with each function. Each function has a signature and a 102 00:07:08,601 --> 00:07:11,312 purpose. They're written slightly differently. 103 00:07:11,312 --> 00:07:15,680 The purpose is written as a string, and The signature is encoded in the primary 104 00:07:15,680 --> 00:07:18,450 names, but there's a signature and a purpose. 105 00:07:18,450 --> 00:07:21,290 And if you look at some of the functions in detail, there's a function called 106 00:07:21,290 --> 00:07:24,720 search, for example, and has the backtracking and arbitrary area templates 107 00:07:24,720 --> 00:07:28,170 in it. It has an additional thing going on in it 108 00:07:28,170 --> 00:07:33,200 called constraint propagation. But this program, the design of this 109 00:07:33,200 --> 00:07:37,075 program, reflects the way that we've been talking about designing programs in this 110 00:07:37,075 --> 00:07:39,590 course. There's a lot of other great programs on 111 00:07:39,590 --> 00:07:41,450 Peter Norman's site that you can learn a lot from. 112 00:07:43,020 --> 00:07:45,428 So what I would say is you can use this in any language. 113 00:07:45,428 --> 00:07:51,490 In the course we spent a lot of time on details because in any given language the 114 00:07:51,490 --> 00:07:56,222 details matter, the right way to write signatures, the right way to write unit 115 00:07:56,222 --> 00:07:58,620 tests. Those matter in order to produce a 116 00:07:58,620 --> 00:08:03,680 program that other people can read. But the underlying approach is what 117 00:08:03,680 --> 00:08:06,150 really matters. The underlying approach about designing 118 00:08:06,150 --> 00:08:08,010 programs systematically is what really matters. 119 00:08:10,030 --> 00:08:14,200 So I'd encourage you to take a bit more time look back over the slides I've just 120 00:08:14,200 --> 00:08:17,560 done. To see what I am describing the more 121 00:08:17,560 --> 00:08:22,330 general version of the recipe is. That's what you going to take forward and 122 00:08:22,330 --> 00:08:25,830 I would encourage you to do what I do, which is whatever I have to design a 123 00:08:25,830 --> 00:08:30,660 program that is kind of too hard to just do. 124 00:08:30,660 --> 00:08:34,160 I get out this method. You know, for example, little while ago I 125 00:08:34,160 --> 00:08:38,660 designed a program to solve the problem of scheduling TA's to labs and you will 126 00:08:38,660 --> 00:08:42,740 see we have. 4 DTAs and 24 labs and the scheduling 127 00:08:42,740 --> 00:08:46,060 problem has to be automated. Well, a scheduler is a bit of a 128 00:08:46,060 --> 00:08:48,440 complicated thing. So, what did I do? 129 00:08:48,440 --> 00:08:52,945 I started thinking about the information in the problem domain. 130 00:08:52,945 --> 00:08:55,720 And I started thinking of a data representation for that. 131 00:08:55,720 --> 00:08:59,732 I wrote down the data representation. I started thinking about the main 132 00:08:59,732 --> 00:09:01,432 function. I templated it. 133 00:09:01,432 --> 00:09:06,107 I maintained a wishlist. I did the whole design process that we've 134 00:09:06,107 --> 00:09:10,272 been using and I ended up with a nicely structured TA solver. 135 00:09:10,272 --> 00:09:15,712 It turned out there are lots of ways that have to be extended and because it was 136 00:09:15,712 --> 00:09:19,367 nicely structured, those extensions were easy to do. 137 00:09:19,367 --> 00:09:24,807 So, taking forward, use this method you've learned here whenever the problem 138 00:09:24,807 --> 00:09:27,710 is too hard to just do. You don't have to use it if you have to 139 00:09:27,710 --> 00:09:33,100 write a totally simple function that you immediately know what to write. 140 00:09:33,100 --> 00:09:37,380 There's one other thing that we've talked about that I want to point out. 141 00:09:37,380 --> 00:09:40,645 This is a thing that we'll get to more in Part 2 of the course when that comes. 142 00:09:40,645 --> 00:09:44,870 But another thing you've learned how to do is you've learned how to see higher 143 00:09:44,870 --> 00:09:48,480 level structures in code. And this is really important. 144 00:09:48,480 --> 00:09:51,120 It really started to come into its own at the end of the course. 145 00:09:51,120 --> 00:09:56,025 But your ability to look at a piece of code and see the template underlying it, 146 00:09:56,025 --> 00:09:59,850 whether that be a data-driven template, or a generative recursion template, or a 147 00:09:59,850 --> 00:10:04,880 backtracking template, or some other form of template, is very important. 148 00:10:04,880 --> 00:10:07,660 Being able to see structure in code is a vital skill. 149 00:10:07,660 --> 00:10:10,539 It's one of the things that separates people who are really good at this. 150 00:10:12,250 --> 00:10:15,060 When they look at the code they don't see a bunch of characters, they don't see a 151 00:10:15,060 --> 00:10:17,375 bunch of details, they see a piece of structure. 152 00:10:17,375 --> 00:10:21,610 That's one of the reasons experts cam recode it in any languages because there 153 00:10:21,610 --> 00:10:26,335 are actually be in the structure more than the details of the curve. 154 00:10:26,335 --> 00:10:31,370 We've started laying a real foundation for that in this course that's one of the 155 00:10:31,370 --> 00:10:35,555 things that templates do for us. And we'll come back to it again in Part 156 00:10:35,555 --> 00:10:39,590 2. Let me say now a thing about Part 2. 157 00:10:39,590 --> 00:10:43,590 First, we need to rest a bit. This course has been great for us. 158 00:10:43,590 --> 00:10:45,860 It's been fun. But it's been a lot of work. 159 00:10:45,860 --> 00:10:47,740 You do want to have a little bit of summer this summer. 160 00:10:48,960 --> 00:10:50,770 But we do have most of the material already. 161 00:10:50,770 --> 00:10:56,270 We've been teaching it at UBC. So you could search for the UBC CPSC 110 162 00:10:56,270 --> 00:11:00,390 syllabus for a preview, just look at the last four weeks. 163 00:11:00,390 --> 00:11:03,880 The material will be about accumulators and tail recursion, and graphs and sate 164 00:11:03,880 --> 00:11:07,200 variables and mutable loop variables. We'll be working on harder and harder 165 00:11:07,200 --> 00:11:10,710 problems, learning some more language constructs. 166 00:11:10,710 --> 00:11:15,530 One really fun example we do here at UBC is to design a program that can crawl 167 00:11:15,530 --> 00:11:21,080 through a graph with cycles in it. Graph with cycles in it is the fancy way 168 00:11:21,080 --> 00:11:25,180 of talking about structures like webpages with all of their lengths back and forth. 169 00:11:26,320 --> 00:11:29,040 And it'll be in a choice of two or more languages. 170 00:11:29,040 --> 00:11:32,790 One version of it will be an ASL, which is the language that comes after 171 00:11:32,790 --> 00:11:35,898 intermediate student language. One will be Python. 172 00:11:35,898 --> 00:11:40,270 And we'll try to do one more. The first time out, we probably won't do 173 00:11:40,270 --> 00:11:43,913 all three. We may run another version of part one 174 00:11:43,913 --> 00:11:50,492 first to support our UBC students and then follow that at the end with Part 2. 175 00:11:51,850 --> 00:11:56,680 The last thing I would say, and this is from me and the TA's, is thank you very 176 00:11:56,680 --> 00:12:01,010 much for taking our course. Thank you, I think mostly for trusting us 177 00:12:01,010 --> 00:12:04,430 with your time. Your time is very precious, and giving 178 00:12:04,430 --> 00:12:08,920 eight weeks of it to this is incredible. Thank you for working so hard. 179 00:12:08,920 --> 00:12:13,560 Thank you for helping each other so much. And thank you for just, you know, being 180 00:12:13,560 --> 00:12:17,180 there every week and pushing us to do our best. 181 00:12:17,180 --> 00:12:22,180 We've really enjoyed it, and all I can say is we hope you enjoyed it. 182 00:12:22,180 --> 00:12:25,672 Thank you very much. As I said we hope to offer the course 183 00:12:25,672 --> 00:12:28,460 again, so please tell your friends. Spread the word. 184 00:12:28,460 --> 00:12:34,660 We'd like to get more students for it. And just keep programming, keep having 185 00:12:34,660 --> 00:12:37,830 fun programming. And when the problems are hard, remember 186 00:12:37,830 --> 00:12:42,605 to work systematically.