We've come to the end of our eight-week course in a course.
So what have you learned? A lot, I think.
For those of you who never programmed before, I hope you have a better
understanding of how some of the computational systems in the world around
you might work. And how the people who design those
systems go about their work. So I hope from that the world you feels
less mysterious than it did at the beginning of the course.
I hope you also have the confidence now that you can design small programs that
you know how to proceed systematically. Where to start, what to do first, what to
do next, how to know you're making progress.
Remember that's all systematic design means.
It doesn't mean you don't make mistakes. It doesn't mean it isn't hard.
It doesn't mean you never have to back up.
What it means is knowing what to do at each point in time, knowing how to make
progress, knowing how to break off small pieces of the problem and working on
them. With that in mind, let me try to step
back a bit from the details of the recipes we've been learning.
And see sort of what they are a little bit more generally let's look first at
information and data. What the recipe is telling us is that
when you start designing your program you should start by looking at the
information in the problem domain. You should figure out the natural
structure of that information, you should design a data representation for that,
you should work out the templates for operating on that data.
If those templates are awkward, if for example the reference relationships don't
look quite right, that's a good time to revise the representation.
Notice none of that has quite exactly the details of the exact rules that we've
done it in this particular language. But that's the general recipe we've
learned for dealing with information and data.
Let's look at function design. Well, to design each function what do we
do? Well the first thing we do is we write
down in different forms what the function should do.
I've never said it quite that way before, but that's what we've been doing all
along. The signature, the purpose and the
example are three complimentary ways to describe what the function should do.
By complimentary, I mean they should be consistent but they focus on different
aspects of the functions behavior. As you're doing this, you look for
contradictions along the forms. If your signature says it produces one
thing and you've got an example that says it produces something else.
You've got a problem, work on it right then.
You should use each form to help you develop the other forms.
You should test as often as possible. You should use stubs to help you test as
often as possible. The sooner you find a mistake in an
example or anything, the easier it is to fix.
That especially becomes true as the examples get large.
Stubs let you at least run the program even if tests are failing to make sure
that things are well formed. Sometimes stubs can do even a little
better than that. When you get to the actual function
definition it can usually be developed in two stages.
First a template which can either be a data driven template or another kind of
template as we've seen with the Sudoku functions.
Then, you fill in the details. Let's look at another aspect of the
recipes having to do with decomposition. We know that breaking the design into
parts helps manage complexity. And the key thing we've seen in this
course is that there's lots of ways to break the design process in addition to
that actual artifacts into pieces. We don't want to just have the structure
of the final program be in pieces. We want to have the work process be in
pieces. So there's analysis in program
development phases, There's data and functions.
There's steps of the process for each element type.
For a world, we do this and then we do this and then we do this.
For data, we do this and this and this. For functions and so on.
Focusing now more on the actual code, the actual decomposition of the actual code
structure. We should separate types along natural
units of information. We should separate functions where that's
indicated by the template. Or acknowledge domain shifts or where
operating on arbitrary-sized data, or for function composition.
Or for other kinds of rules that you'll learn as you go.
Again, I've just stepped back a tiny bit from the details of our recipe.
But this is the more general thing you've been learning all course.
Now's a good time to look at the question: Can this design method work in
other languages? So here's a simple function, or design
for a simple function that takes a string and a list of strings, counts how many
times that string occurs in the list of strings.
And we'll go through the details. But here it is in Python on the right.
And you know, the answer to the question can this method work in other languages?
Is of course it can, look, if I look at a Python design for this function, there's
the signature, there's the purpose, here's some check expects, there's the
body of the function. There's even the template for operating
on a list. Of course, you can develop functions in
Python or any other language following this recipe.
Also, of course, there are other and even better ways to write this Python code.
This particular code was written to look very much like the code form our course
in, in BSL and ISL. If you wrote this in more idiomatic
Python, it would look a little bit different.
There'd be other conventions for saying things like the signature and the
purpose. There are other better unit test
frameworks. This unit test framework I'm showing you
works in Python but there are other ones. There's other ways for writing the
templates. But those are all just details.
Those are details of the exact form the recipes took.
>> In the language we've been using. Let's go look at another example program.
It's Peter Norvig's sudoku solver, this is actually a fairly well-known On
program. It's got a webpage that describes it and
at the bottom of the webpage, you can find a link to look at the actual
program. If you look at that program, I think
you're going to find that the structure of the design is very familiar to you,
even though you may not know the details of the Python language.
It follows the same general structure that our programs do.
It starts with data definitions. Then there's contents.
In this program the unit tests are all grouped together though, they're not
spread with each function. Each function has a signature and a
purpose. They're written slightly differently.
The purpose is written as a string, and The signature is encoded in the primary
names, but there's a signature and a purpose.
And if you look at some of the functions in detail, there's a function called
search, for example, and has the backtracking and arbitrary area templates
in it. It has an additional thing going on in it
called constraint propagation. But this program, the design of this
program, reflects the way that we've been talking about designing programs in this
course. There's a lot of other great programs on
Peter Norman's site that you can learn a lot from.
So what I would say is you can use this in any language.
In the course we spent a lot of time on details because in any given language the
details matter, the right way to write signatures, the right way to write unit
tests. Those matter in order to produce a
program that other people can read. But the underlying approach is what
really matters. The underlying approach about designing
programs systematically is what really matters.
So I'd encourage you to take a bit more time look back over the slides I've just
done. To see what I am describing the more
general version of the recipe is. That's what you going to take forward and
I would encourage you to do what I do, which is whatever I have to design a
program that is kind of too hard to just do.
I get out this method. You know, for example, little while ago I
designed a program to solve the problem of scheduling TA's to labs and you will
see we have. 4 DTAs and 24 labs and the scheduling
problem has to be automated. Well, a scheduler is a bit of a
complicated thing. So, what did I do?
I started thinking about the information in the problem domain.
And I started thinking of a data representation for that.
I wrote down the data representation. I started thinking about the main
function. I templated it.
I maintained a wishlist. I did the whole design process that we've
been using and I ended up with a nicely structured TA solver.
It turned out there are lots of ways that have to be extended and because it was
nicely structured, those extensions were easy to do.
So, taking forward, use this method you've learned here whenever the problem
is too hard to just do. You don't have to use it if you have to
write a totally simple function that you immediately know what to write.
There's one other thing that we've talked about that I want to point out.
This is a thing that we'll get to more in Part 2 of the course when that comes.
But another thing you've learned how to do is you've learned how to see higher
level structures in code. And this is really important.
It really started to come into its own at the end of the course.
But your ability to look at a piece of code and see the template underlying it,
whether that be a data-driven template, or a generative recursion template, or a
backtracking template, or some other form of template, is very important.
Being able to see structure in code is a vital skill.
It's one of the things that separates people who are really good at this.
When they look at the code they don't see a bunch of characters, they don't see a
bunch of details, they see a piece of structure.
That's one of the reasons experts cam recode it in any languages because there
are actually be in the structure more than the details of the curve.
We've started laying a real foundation for that in this course that's one of the
things that templates do for us. And we'll come back to it again in Part
2. Let me say now a thing about Part 2.
First, we need to rest a bit. This course has been great for us.
It's been fun. But it's been a lot of work.
You do want to have a little bit of summer this summer.
But we do have most of the material already.
We've been teaching it at UBC. So you could search for the UBC CPSC 110
syllabus for a preview, just look at the last four weeks.
The material will be about accumulators and tail recursion, and graphs and sate
variables and mutable loop variables. We'll be working on harder and harder
problems, learning some more language constructs.
One really fun example we do here at UBC is to design a program that can crawl
through a graph with cycles in it. Graph with cycles in it is the fancy way
of talking about structures like webpages with all of their lengths back and forth.
And it'll be in a choice of two or more languages.
One version of it will be an ASL, which is the language that comes after
intermediate student language. One will be Python.
And we'll try to do one more. The first time out, we probably won't do
all three. We may run another version of part one
first to support our UBC students and then follow that at the end with Part 2.
The last thing I would say, and this is from me and the TA's, is thank you very
much for taking our course. Thank you, I think mostly for trusting us
with your time. Your time is very precious, and giving
eight weeks of it to this is incredible. Thank you for working so hard.
Thank you for helping each other so much. And thank you for just, you know, being
there every week and pushing us to do our best.
We've really enjoyed it, and all I can say is we hope you enjoyed it.
Thank you very much. As I said we hope to offer the course
again, so please tell your friends. Spread the word.
We'd like to get more students for it. And just keep programming, keep having
fun programming. And when the problems are hard, remember
to work systematically.