In the previous lesson, I showed you about what functions are and what they do. I also showed you about variables and a bit about how to use them, but for this lesson I'm going to put them aside and spend some more time on functions. I told you what functions are, but not much about why you would use them.
Before we get to the actual programming part, I want to talk about algorithmic thinking, or thinking in a way that can be translated into a program. As I mentioned before, computers are kind of stupid. They're good at doing what you tell them, but you have to be really clear and know exactly what to instruct them to do. Writing programs is a lot about learning this clarity and learning how to express yourself.
Algorithms, what's up with them?
I'm using the term "algorithm," so I should define it. An algorithm is just a list of steps that solve a problem or accomplish some goal. These "steps" are a pretty abstract concept. They can be as vague or as specific as you'd like when you think up the algorithm, but by the time they are translated into a program, they must be specific.
Let's look at a sample algorithm. The problem we want to solve is tidying up a house. What does that entail?
- Go into the living room.
- Pick up trash lying around.
- Put trash in the garbage.
- Pick up things off of the floor.
- Put things back where they belong.
- Plug in the vacuum cleaner.
- Vacuum the floor.
- Unplug the vacuum cleaner.
- Dust the furniture.
- Move into the dining room.
- Pick up trash lying around.
- Put trash in the garbage.
- Pick up things off of the floor.
- Put things back where they belong.
- Plug in the vacuum cleaner.
- Vacuum the floor.
- Unplug the vacuum cleaner.
- Dust the furniture.
- Wipe down the dining table.
- Move into the kitchen.
- ...
This program has several steps. I've described the house cleaning process in pretty good detail (ignore for now whatever house cleaning tasks I forgot to do). But there are problems with this algorithm. First of all, if you have a house with 10 rooms in it, think of how many individual tiny steps are needed in total. The program overall would be very long. Most programs that do anything useful are very long, and one way to manage the problem of length is to break up the problem into pieces and tackle them individually.
If I were to break this program up into a few pieces, here is what I might come up with:
-
Cleaning the living room
- Go into the living room.
- Pick up trash lying around.
- Put trash in the garbage.
- Pick up things off of the floor.
- Put things back where they belong.
- Plug in the vacuum cleaner.
- Vacuum the floor.
- Unplug the vacuum cleaner.
- Dust the furniture.
-
Cleaning the dining room
- Move into the dining room.
- Pick up trash lying around.
- Put trash in the garbage.
- Pick up things off of the floor.
- Put things back where they belong.
- Plug in the vacuum cleaner.
- Vacuum the floor.
- Unplug the vacuum cleaner.
- Dust the furniture.
- Wipe down the dining table.
-
Cleaning the dining room
- Move into the kitchen.
- ...
The algorithm is still a large number of small steps, but organized this way, it becomes easier to see what the overall tasks are. The next thing you might notice is that a lot of the steps are really the same. I mean, in reality they are slightly different depending on what room you're in, but the steps themselves are common to every room you clean. We could express this better and eliminate this redundancy.
-
Cleaning the living room
- Go into the living room.
- Clean the room:
- Pick up trash lying around.
- Put trash in the garbage.
- Pick up things off of the floor.
- Put things back where they belong.
- Plug in the vacuum cleaner.
- Vacuum the floor.
- Unplug the vacuum cleaner.
- Dust the furniture.
-
Cleaning the dining room
- Move into the dining room.
- Clean the room. (same as above)
- Wipe down the dining table.
-
Cleaning the dining room
- Move into the kitchen.
- Clean the room. (same as above)
With this kind of "factoring", the redundant part of the algorithm doesn't need to be repeated in many different places. It makes things easier to read and understand. These are important goals in writing good programs.
From algorithm to program
Let's see what this same algorithm would look like in the form of a program. This will rely heavily on concepts from lesson 1. To start with, let's look at the first version before we made any improvements.
WScript.Echo("Go into the living room.");
WScript.Echo("Pick up trash lying around.");
WScript.Echo("Put trash in the garbage.");
WScript.Echo("Pick up things off of the floor.");
WScript.Echo("Put things back where they belong.");
WScript.Echo("Plug in the vacuum cleaner.");
WScript.Echo("Vacuum the floor.");
WScript.Echo("Unplug the vacuum cleaner.");
WScript.Echo("Dust the furniture.");
WScript.Echo("Move into the dining room.");
WScript.Echo("Pick up trash lying around.");
WScript.Echo("Put trash in the garbage.");
WScript.Echo("Pick up things off of the floor.");
WScript.Echo("Put things back where they belong.");
WScript.Echo("Plug in the vacuum cleaner.");
WScript.Echo("Vacuum the floor.");
WScript.Echo("Unplug the vacuum cleaner.");
WScript.Echo("Dust the furniture.");
WScript.Echo("Wipe down the dining table.");
WScript.Echo("Move into the kitchen.");
WScript.Echo("...");Remember from the first lesson that Echo just displays some text. You can save this program in a file (like c:\cleaning1.js) and run it using cscript to see the output, which, after the problem set in lesson 1, hopefully you can already guess. If you can't guess it, I would recommend taking another look at lesson 1 and trying the problems again.
Improvement: adding structure and names
Our first step in improving our algorithm was giving it some logical structure by grouping tasks together and naming them in a way that makes sense. Recall from lesson 1 that a function is a series of statements that are executed together and which are given a name to call them by. We can use functions here to express the structuring I showed earlier.
function CleanLivingRoom()
{
WScript.Echo("Go into the living room.");
WScript.Echo("Pick up trash lying around.");
WScript.Echo("Put trash in the garbage.");
WScript.Echo("Pick up things off of the floor.");
WScript.Echo("Put things back where they belong.");
WScript.Echo("Plug in the vacuum cleaner.");
WScript.Echo("Vacuum the floor.");
WScript.Echo("Unplug the vacuum cleaner.");
WScript.Echo("Dust the furniture.");
}
function CleanDiningRoom()
{
WScript.Echo("Move into the dining room.");
WScript.Echo("Pick up trash lying around.");
WScript.Echo("Put trash in the garbage.");
WScript.Echo("Pick up things off of the floor.");
WScript.Echo("Put things back where they belong.");
WScript.Echo("Plug in the vacuum cleaner.");
WScript.Echo("Vacuum the floor.");
WScript.Echo("Unplug the vacuum cleaner.");
WScript.Echo("Dust the furniture.");
WScript.Echo("Wipe down the dining table.");
}
function CleanKitchen()
{
WScript.Echo("Move into the kitchen.");
WScript.Echo("...");
}
CleanLivingRoom();
CleanDiningRoom();
CleanKitchen();You could save this in a file (I'd call it c:\cleaning2.js) and run it with cscript, and you will see the same output as cleaning1.js. I will briefly reiterate some of the important things I talked about in the first lesson.
The first part of this program defines functions, that is, gives the function name, parameters (in this case, there are no parameters; that is permitted), and body.
The second part of the program (just the last three lines) calls the functions that were just defined, which causes the computer to jump into the function body of each function, run the lines of code within it, and jump back to the next line.
In terms of readability, you may be able to tell that doing something as simple as giving names to tasks and grouping tasks together makes things in general much easier to see. Imagine for a moment that CleanLivingRoom, CleanDiningRoom, and CleanKitchen were actually defined in some other file, so their function bodies were invisible to you. Even with this diminished knowledge of their specifics, just by reading their names you can get an overall sense for what the functions would do if you called them. Learning how to structure programs this way is a very important technique in programming.
Improvement: reducing redundancy
The second improvement we made in the algorithm above was not listing out all of the steps for cleaning a room each time -- reducing redundancy. We can do the same thing with our sample program too.
function CleanThisRoom()
{
WScript.Echo("Pick up trash lying around.");
WScript.Echo("Put trash in the garbage.");
WScript.Echo("Pick up things off of the floor.");
WScript.Echo("Put things back where they belong.");
WScript.Echo("Plug in the vacuum cleaner.");
WScript.Echo("Vacuum the floor.");
WScript.Echo("Unplug the vacuum cleaner.");
WScript.Echo("Dust the furniture.");
}
function CleanLivingRoom()
{
WScript.Echo("Go into the living room.");
CleanThisRoom();
}
function CleanDiningRoom()
{
WScript.Echo("Move into the dining room.");
CleanThisRoom();
WScript.Echo("Wipe down the dining table.");
}
function CleanKitchen()
{
WScript.Echo("Move into the kitchen.");
CleanThisRoom();
}
CleanLivingRoom();
CleanDiningRoom();
CleanKitchen();You can save this program in a new file (say, c:\cleaning3.js) and run it with cscript. You should see the same output as the previous two iterations of the program.
Much the same way as I described it in the algorithm, we have now written down in just one place the steps needed to clean a single room (the function we just defined, called CleanThisRoom), and anywhere we need to do those steps, we can call that function. Now if we needed to continue adding rooms to be cleaned, it's a matter of adding just a few more lines. With a house of 20 rooms, the program would still be quite readable. Compare this mentally to what the original unstructured program would look like; that one would be over a hundred lines!
The thought process for writing and refining algorithms
Now that we've looked at an algorithm and its corresponding program in practice, I want to go back to algorithmic thinking. It is really about following all of the steps we did before:
- Think of the problem you need to solve
- Express very explicitly all of the steps you feel you need to do to solve the problem. Err on the side of being more verbose. It's easier to work with too many steps than too few.
- Step back and try to identify patterns or structure in the set of steps you came up with. Look for groups of things that are often or always done together, and put them into groups.
- Look across the groups and see whether any of them are similar or identical. In these cases, you can write something like, "now see steps for X".
I want to stress one thing, that we're doing these steps when examining the algorithm, not the program. That is, these are steps we can follow before writing the program code that will improve the way we go on to write it. At this time we're not applying them to the program code itself, though we may do that in a subsequent lesson.
One more program - drawing weird shapes
With those steps in mind, let's do one more example program. I like this particular example so much that I'm going to translate it almost verbatim from the CSE142 lecture where it was presented.
The problem: draw these weird ASCII art shapes
We want to write a program that can display these ASCII art shapes: a wand with a star on the end, a plain sword, and a serrated sword.
*
|
|
|
|
|
|
|)
|>
|>
|>
|>
|
|)A simplistic algorithm to draw the shapes
Let's go through the steps above when considering how to solve this problem. First, let's consider the problem. We have to draw a few different shapes. this will again consist of using Echo to display lines of text that make up the drawings.
Next, let's write down explicitly the steps needed to solve the problem. At this stage, I'm not going to consider too much structure or examine patterns; that will come later.
- Draw a
* - Draw a
| - Draw a
| - Draw a
| - Draw a blank line
- Draw a
| - Draw a
| - Draw a
| - Draw a
|) - Draw a blank line
- Draw a
|> - Draw a
|> - Draw a
|> - Draw a
|> - Draw a
| - Draw a
|)
So basically, every step is just drawing the corresponding lines from the figures. That might seem like a pretty simple solution, but it is one that works.
Identifying structure in the simplistic algorithm
Now let's go through and look for structure. Well, since I told you what these figures are earlier (a wand with a star on the end, a plain sword, and a serrated sword), maybe it's worth breaking them apart into their constituent parts.
The wand is made up of two parts, primarily: the star on the end and the shaft. Likewise, the sword is made up of the blade and the handle. The serrated sword is also made up of a blade and a handle, though the blade looks a little different. So maybe we can propose the following set of more general steps.
-
Draw the wand:
- Draw the star
- Draw the shaft
- Draw a blank line
-
Draw the plain sword:
- Draw 3 pieces of plain blade
- Draw the handle
- Draw a blank line
-
Draw the serrated sword:
- Draw the serrated blade
- Draw a piece of plain blade
- Draw the handle
Compared to the set of steps above, this is much easier to grasp intuitively, which again comes back to the benefit of identifying structure in your algorithms.
Removing redundancy from the structured algorithm
I'm going to go through the algorithm again and color some of the things I feel are common.
-
Draw the wand:
- Draw the star
- Draw the shaft
- Draw a blank line
-
Draw the plain sword:
- Draw 3 pieces of plain blade
- Draw the handle
- Draw a blank line
-
Draw the serrated sword:
- Draw the serrated blade
- Draw a piece of plain blade
- Draw the handle (see above for steps)
You may be a little surprised here that I didn't consider drawing the wand's shaft to be similar to drawing the blade of the sword. It's true that in ASCII art they look the same, but in an abstract sense, they're not similar. A wand's shaft looks nothing like a sword blade, so intuitively, why would I use the same program code to draw them? Imagine for a moment that we were making a program to draw these things not in ASCII art, but with more realistic 3D rendering. There's no way our algorithms to draw those two would be similar; we'd never consider them common. Likewise, it's not suitable to do that with this algorithm.
You might come up with a counterargument for sword handles, that different swords could have very different types of handles. But you have to admit that there are situations in which drawing them could be the same. We're going to assume here that these handles do look alike, for the purpose of this problem.
So all in all there isn't too much redundancy in this program. That's fine; all programs are different, and have different amounts and types of redundancy.
Finally, just to sum up the point of this whole lesson, I want to reiterate that functions are a tool that can be used to help break down larger tasks with many steps into smaller groups of tasks. You can name functions to help make your program code easier to read. You can call functions multiple times to reduce redundancy in your programs. When trying to write a program to solve a problem, it's best to think about the overall problem, then break it up into smaller tasks, then try to identify patterns to reduce the redundancy. It's best to follow through with this thought process before writing the program code.
Problems and solutions
Problem 1: write the program code to draw the wand and swords above. We've already thought about the algorithm, so it's more about translating it into some function definitions and function calls. It's worth noting that you might get a somewhat different solution than I did, based on how you decided to name the functions, etc.. That's okay.
Problem 1 solution - click to show or hide
// the star at the top of the wand
function DrawWandStar()
{
WScript.Echo(" *");
}
// part of the handle of the wand
function DrawWandShaftPiece()
{
WScript.Echo(" |");
}
// draw the entire shaft, piece by piece
function DrawWandShaft()
{
DrawWandShaftPiece();
DrawWandShaftPiece();
DrawWandShaftPiece();
}
function DrawWand()
{
DrawWandStar();
DrawWandShaft();
}
// draw a piece of plain blade
function DrawPlainBladePiece()
{
WScript.Echo(" |");
}
// draw the whole plain blade
function DrawPlainBlade()
{
DrawPlainBladePiece();
DrawPlainBladePiece();
DrawPlainBladePiece();
}
function DrawSwordHandle()
{
WScript.Echo(" |)");
}
function DrawPlainSword()
{
DrawPlainBlade();
DrawSwordHandle();
}
// a piece of the serrated blade
function DrawSerratedBladePiece()
{
WScript.Echo(" |>");
}
// draw the whole serrated blade in pieces
function DrawSerratedBlade()
{
DrawSerratedBladePiece();
DrawSerratedBladePiece();
DrawSerratedBladePiece();
}
function DrawSerratedSword()
{
DrawSerratedBlade();
// remember from the reference drawings that there is one piece of
// plain blade here
DrawPlainBladePiece();
DrawSwordHandle();
}
// the part of the program where we actually call those functions
DrawWand();
WScript.Echo("");
DrawPlainSword();
WScript.Echo("");
DrawSerratedSword();Problem 2: add to your program above, to draw the Keyblade:
|=
|
|
|
[|]Your additions may result in modifications to functions you wrote earlier, or change function names. You may introduce new functions. You may call functions that you had already created for problem 1.
Problem 2 solution - click to show or hide. I have highlighted the new parts that were added to answer problem 2.
// the star at the top of the wand
function DrawWandStar()
{
WScript.Echo(" *");
}
// part of the handle of the wand
function DrawWandShaftPiece()
{
WScript.Echo(" |");
}
// draw the entire shaft, piece by piece
function DrawWandShaft()
{
DrawWandShaftPiece();
DrawWandShaftPiece();
DrawWandShaftPiece();
}
function DrawWand()
{
DrawWandStar();
DrawWandShaft();
}
// draw a piece of plain blade
function DrawPlainBladePiece()
{
WScript.Echo(" |");
}
// draw the whole plain blade
function DrawPlainBlade()
{
DrawPlainBladePiece();
DrawPlainBladePiece();
DrawPlainBladePiece();
}
function DrawSwordHandle()
{
WScript.Echo(" |)");
}
function DrawPlainSword()
{
DrawPlainBlade();
DrawSwordHandle();
}
// a piece of the serrated blade
function DrawSerratedBladePiece()
{
WScript.Echo(" |>");
}
// draw the whole serrated blade in pieces
function DrawSerratedBlade()
{
DrawSerratedBladePiece();
DrawSerratedBladePiece();
DrawSerratedBladePiece();
}
function DrawSerratedSword()
{
DrawSerratedBlade();
// remember from the reference drawings that there is one piece of
// plain blade here
DrawPlainBladePiece();
DrawSwordHandle();
}
// top of the keyblade
function DrawKeybladeEnd()
{
WScript.Echo(" |=");
}
function DrawKeybladeHandle()
{
WScript.Echo("[|]");
}
// draw the top, then the plain blade portion in the center, then the handle
function DrawKeyblade()
{
DrawKeybladeEnd();
DrawPlainBladePiece();
DrawPlainBladePiece();
DrawPlainBladePiece();
DrawKeybladeHandle();
}
// the part of the program where we actually call those functions
DrawWand();
WScript.Echo("");
DrawPlainSword();
WScript.Echo("");
DrawSerratedSword();
WScript.Echo("");
DrawKeyblade();
0 comments:
Post a Comment