- Commanding a Turtle
- Adding New Commands
- Iteration & Animation
- Hierarchical Structure
- Procedure Inputs
- Operators & Expressions
- Defining Operators
- Words & Sentences
- User Interface Events
- What If? (Predicates)
- Local Variables
- Global Variables
- Word/Sentence Iteration
- Mastermind Project
- Turtles As Actors
- File Input/Output
- A Java Program
- What's a Class?
- Extending Existing Classes
- Turtle Graphics
- Control Flow
- User Interface Events
- What Is TG?
- TG Directives
- jLogo Primitives
- TG Editor
- Java Tables
- Example Programs
- *** New ***:
- December 13, 2008
- January 6, 2012
- March 15, 2013
- January 20, 2014
- February 13, 2014
- July 29, 2014
- January 18, 2016
- January 29, 2016
- August 19, 2016
Word & Sentence Iteration
In this lesson, we will return to the topic of manipulating words and sentences. A while back, the Words and Sentences lesson kicked off this topic, but only covered it minimally. At that point, I needed you to understand words as symbols and sentences as compound data so that we could
- start working with keyboard input,
- start using println to expose what was happening in your programs,
- and start working with a procedure input/output that is consists of two members (specifically, the setpos command's input and pos operator's output).
This limited introduction to words and sentences has served us well up until now. But starting with this lesson, our programs will be doing more complex things and we will need to work with hierarchical data. This is the first time I've used these two words together! I've talked about structuring our programs in a hierarchical manner, but not the data in the programs.
Words and sentences can be used, thought of, as hierarchical data. Words are made up of a lower-level thing - characters. And sentences are made up of words. So, in this lesson we will learn a lot more about the manipulation of words and sentences - how to play with the pieces that they are made up of.
I will be reviewing
- how to access the first character of a word or the first word of a sentence,
- how to access the last character of a word or the last word of a sentence,
and then will introduce
- how to access all but the first character of a word or all but the first word of a sentence,
- how to access all but the last character of a word or all but the last word of a sentence,
- how to determine if a word or sentence is empty, i.e., has no characters or words in them,
- how to find out the number of characters in a word and the number of words in a sentence,
- how to determine if a character is in a word or a word is in a sentence,
- and more...
In the process of introducing all of this new functionality, we will see how it can be used along with recursion to manipulate all the characters in words and all the words in sentences.
Oh, just a heads-up, it will be very important for you to experiment as much as you can with all of the new operators you will learn in this lesson.
Accessing Parts of Words and Sentences
Let's start out with the basic operators for accessing letters in words and words in sentences. Here are often used operators that select pieces of words and sentences.
|wordOrSentence||If the input is a word, all characters except its first are output. If the input is a sentence, all words except the first are output.|
|wordOrSentence||If the input is a word, all characters except its last are output. If the input is a sentence, all words except the last one are output.|
|FIRST||wordOrSentence||If the input is a word, its first character is output. If the input is a sentence, its first word is output.|
|LAST||wordOrSentence||If the input is a word, its last character is output. If the input is a sentence, its last word is output.|
Use the following TG applet to try these operators out. See if they output what you expected? println the outputs. Try out your own experiments or use the following set of example usages of them.
TG Programming Environment Applet
Just like the math operators, they can be combined. Try to figure out what will happen when you type in the following instructions, then use the TG applet to see if you got your answers right.
Example Usage: rotateSentence
To get started, let's write a procedure, an operator, we'll name rotateSentence. It takes the first piece of a sentence, removes it and appends it onto the end of the rest of the sentence. Figure 16.1 shows a demonstration of what we want it to do.
Go back up to the TG applet and try to write rotateSentence. Do NOT read any further until you've played around a bit. If you are having trouble, go back and read the introduction to sentences and the sentence operator.
*Hint* Since you are writing an operator that will produce a new sentence, two primitive procedures you will certainly need are output and sentence.
*Hint* Remember that drawing a plumbing diagram usually helps you understand how to put things together. Figure 16.2 show the plumbing diagram for my solution.
Print Pieces of Words and Sentences
Let's see how to do something with all of the pieces of words and sentences. Let's combine what we've learned so far with recursion.
Our challenge is to write a procedure that prints all of the pieces of a word or sentence. Each piece should be printed on a line of its own. Figure 16.3 shows what I want the procedure to do.
Here is the rough outline of what we need (see the summary from the recursion lesson for a description of the pieces our procedure must consist of).
You have operators you can use to isolate a piece of a word or sentence. You have operators you can use to remove a piece of a word or sentence. But... what about the stop rule? How can a word or sentence have no pieces? A sentence consisting of NO words, a word consisting of NO characters... isn't this impossible?
?Words with NO characters, Sentences with NO words?
Well, in Logo, we use word and sentence as metaphors for things in programming languages that are more commonly called strings and lists. Till now, what you have been doing with words and sentences fits well with their counterparts in ordinary human language. But now it is time to learn a couple of things about Logo words and sentences that make them different.
Figure 16.4 shows you what happens when you attempt to get the first word of an empty sentence - just an open-square-bracket followed by a close-square-bracket. Also take note that in the error message it refers to an empty list. In Logo, a sentence is a special kind of list.
Figure 16.5 shows you what happens when you attempt to get the first character of an empty word - a quote followed by nothing.
So, in your programs it is possible to have empty words and sentences even though this makes no sense in natural language. If you think this is confusing, bear with me, you are NOT alone. A graduate student at UC Berkeley (Clint Eric Ryan) has researched why this is so. The results of his research, his Masters Thesis, is available here. I don't expect you to read it, just be aware that empty words and sentences are not a simple concept, lot's of students have trouble working with them. If you are having trouble, hang in there... make sure to work though all of the example programs.
We got to this subject of empty words/sentences because we were trying to figure out what our stop rule should be for a recursive procedure that does something to every character in a word or every word in a sentence. We need to know when we are done, when every character or every word has been dealt with. Here's what we need...
The EMPTY? Operator
How can a program check for an empty word or sentence? Here's how...
|wordOrSentence||Outputs true if its input is a word that has no characters in it, otherwise false. Outputs true if its input is a sentence that has no words in it, otherwise false.|
Go back up to the TG applet and play with this operator. Use println to display the output produced by empty? on a variety of words and sentences. Make sure to try it on the examples I gave which caused the error messages in Figures 16.4 and Figure 16.5.
Back to printPieces
You now have everything you need for printPieces, try to write it. At the very least, try something, anything. Treat it as a puzzle. Look back at the pseudocode I gave you.
*Tip* Don't forget about the valuable debugging tool trace. It can help you see what your procedure is doing when you invoke it. Figure 16.6 shows what was printed when I traced my program.
Exercise: Reverse the Printed Order
Write a procedure, printReversedPieces, which prints the pieces of its input in reverse order. Figure 16.7 shows its results.
If you would like to see a detailed walk-through about writing recursive procedures that manipulate words, here is Brian Harvey's chapter "Introduction to Recursion," from his book Computer Science Logo Style.
Practice: Program Generated Stories
Let's write a program that can generate stories. Figure 16.8 shows three similar but different little stories my version of the program came up with when I executed it three times consecutively.
The program we are going to write is actually very simple. It consists of a skeleton of the desired story with a bunch of random words placed in slots in the skeleton. You learned how to obtain a random number a long time ago. We need to write a procedure, an operator, that outputs a random word from a supplied sentence. But, first let's just print a random word from a supplied sentence.
Printing a Random Word
By now you should know that I always like to get something working and then extend it until I have what I really want. In this case, I'm going to start with the procedure we just wrote, printPieces, that prints all of the pieces of a word or sentence. Here is my new pseudocode, a modified version of the pseudocode for printPieces.
What I do that's different is to move the procedure's action part into the stop rule's instruction list. In printPieces, an empty word or sentence signaled the end of what we were doing. In printRandomWord we can be done as soon as we get started - the first word satifies the criteria of being a random word in the sentence. But the random word can also be the last word of the sentence, or any word between the first and last...
Well if we think about what we know how to do...
- We know how to get a random number, 0...N.
- We know how to discard words from a sentence, one at a time.
What about discarding a random number of words off the front of the sentence?
But we don't know how many words are in the input sentence! Can we find out? Does Logo have a primitive operator that will tell us this?
Logo Primitive: COUNT
Yes, we can get the number of words in a sentence. Meet count.
|If the input is a number or a word, the number of characters in it is output. If the input is a sentence, the number of words in it is output.|
Using count as the input to the random operator will get me a number of words to discard. So, now I'm almost ready. Just one problem - I need to introduce a new input that I can use in the stop rule. I need a variable to hold the number of words yet to be dicarded.
This happens a lot when using recursion as the mechanism for iteration. The way to solve our problem is to write a new procedure that helps us do what we need to do.
Helper Procedure: prtRandWdHelper
Here is what we end up with. The pseudocode gets moved into our new helper procedure, prtRandWdHelper, where we add the additional input which I've named num. The original procedure's body now consists of an invocation of the helper procedure with initialization of the new input - the number of words to discard - a random number.
Given this, I can now replace one line of pseudocode at a time. The translation of the pseudocode into Logo instructions is not too tricky.
Determining whether to stop or not will simply depend on the value in the input :num - when it is zero (no more words to discard) we're done. And when this is true, the first word of :sent is printed and the procedure stops.
The recursive invocation is just as straight-forward. The number of words yet to be discarded is decremented by 1 and the first word of the input sentence is discarded.
Now... Back to Our Story
So now that we have a way of injecting a random word into a story that we are creating, a story can be the production of a computer program.
I'll now give you a bit more of my program which generated the stories.
Actually this snipet of my program is missing one more thing that I have yet to talk about. Earlier in this lesson I pointed out that Logo words and sentences are not quite like words and sentences that you are familiar with. Logo words are actually things that are most commonly called strings in other programming languages.
In case you have not copy/pasted the above code in and tried it out, Figure 16.9 shows what happens if you do.
As you can see, the sentence is missing white space between the words. The reason is that each word of the sentence is being printed individually. The program does not combine all the words into a sentence before it prints them. What we need to do is to add white space between words we are printing. This is possible because there is a space character in the set of ASCII characters. And, in Logo, any ASCII character can be part of a word.
But how? A space usually marks the enc of a word!
In Logo, the backslash character ("\") and the vertical bar character ("|") are special. When you need a word that contains a character like the space we need, you have two options.
- prefix the character with a backslash, or
- use a pair of vertical bars to surround characters that you want to be included exactly as they are entered.
Here, I'll show you a nice place where a word that consists only of a space comes in handy. Suppose you want to print out a bunch of stuff. If we println each piece on a line by itself, there is only so many lines that are displayed before the contents get scrolled off. If we print each piece we need to keep them from getting all joined together. The solution is to print them along with a word (consisting only of a space) between them. Figure 16.10 shows how to do this.
printRandomNums takes an input that is the number of random numbers to print on a line. For all but the last, a random number is printed and then a word consisting only of a space is printed. The last random number is printlned so that the line is ended properly.
Now back to our story program where I can give you an example of where it's nice to use the vertical bars. Here's the part of main that I gave you before, after I *fixed* it.
I like to use the vertical bar when the space would be the last thing on the line. This way, you can see the trailing space - it comes before the second vertical bar.
OK, there you have it, all you need to write your own program that writes a story with some randomness to it. ENJOY!
Building a Collection and Then Examining It
Writing Logo programs can be a great way to check whether or not something you think is true, really is true. I'm going to use an example where I build a sentence through recursive iteration and then examine what I've created, again with recursion. Here is the question I want to answer.
If we have a sentence composed of X random integers in the range 0...X-1, will it always contain zero?
Sentence Generation With Recursion
First, let's write a procedure which creates a sentence of X random numbers. We'll write a more general procedure than we need. This is usually a good idea since it adds another tool to your toolbox, in case you have a need for something like it in the future. Notice that it uses the randomInRange procedure we wrote back in lesson 9 (Defining Operators). Just a tool in the toolbox that we know works.
What is especially interesting about this recursive procedure is that it is an operator, it outputs a sentence. This is the first operator you've seen that uses recursion. This makes a procedure harder to understand at first. That is why I'm giving you the source code right up front. I want to make sure you understand what is going on.
First notice that the stop rule's instruction list consists of an output command, which is what you would expect in an operator. In this case an empty sentence is output because that's what the procedure is doing; it's building a sentence. But why is the sentence empty? This procedure supposedly creates a sentence of :num numbers. Read on...
The next thing to notice is that the action part is now in the recursive invocation. In this procedure, I am building a sentence so the action will be the results of a sentence operator. Checkout the sentence operator following the output command. The output from sentence is the input to output. Finally, output's input is the output from randNums. This is where the sentence gets built!
Watch this procedure produce a sentence. Copy & Paste it into TG's Editor. Then use trace to see what randNums does. Figure 16.11 shows what was printed when I traced it.
Examining a Collection
Now that we have a sentence of random numbers, I'll write a procedure, another operator, which iterates through all words in a sentence looking for a specified word. It will output true if it finds it, otherwise false.
And with contains? I can now answer my question. Figure 16.12 shows what the answer is.
Practice: Acronym Operator
Here's another interesting procedure to write: acronym. It outputs the first characters of all the words in its input - a sentence.
Figure 16.13 shows a couple of examples of what acronym should do.
Remember that the first step in writing any program, any procedure, is Understanding the Problem. This has been the case since we wrote our first non-trivial program. Just because we've written a lot of code since then, doesn't mean we can skip the understanding step.
So, one thing that's different with this program is that acronym is an operator. Instead of printing its result, it must output it. This is the same scenario as when I first introduced defining operators, back in the Creating Your Own Operators lesson. Go back and checkout how we converted the command printCircleCircum into the operator circleCircumference.
Now, think about acronym's input and output. The input is a sentence which we will iterate through - we will do something to all of the words in it. There is NO difference between this and what printPieces had to do. For the output, we need to construct a word consisting of the first character of each word in the input. How do you construct a word? You use the word operator. So, here's some pseudocode that takes all of this into account.
Now to convert this to Logo.
In this case the stop rule is easy. We can check for an empty sentence just like we did in printPieces and it's pretty obvious what we want to do. Is seems logical that the acronym for an empty sentence is an empty word so we'll output one.
If our input is not an empty sentence, the acronym we want to output is a word consisting of the first character of the first word of the sentence AND... (here's the neat part) the acronym of the rest of the sentence!
Ok, so you now have the code for acronym. Play with it. trace it. Make sure you understand it. It will be a model, an example of a pattern for operators you will write in the future.
Sometimes, diagrams, graphical depictions, help with understanding complex patterns. Drawing a recursive process is not easy. The following Figures (16.14 through 16.16) show how acronym expands out into a set of *sort-of* plumbing diagrams by expanding out recursive invocations of acronym. Maybe they will help you see what's going on.
Once you get this working, improve it... Acronyms do not contain noise words, e.g., "of," "the," "for," etc... You could use the contains? operator we wrote earlier in this lesson to remove the noise words, but guess what? Logo has a primitive procedure that does exactly what contains? does.
member? will help you to find and ignore the noise words in the input sentences. I just wrote contains? to show you another recursive operator.
| char or word
|Outputs true if its first input is in its second input, otherwise it outputs false.|
Use this operator to extend your version of acronym to ignore noise words.
The Hangman Game
Now for the big project in this lesson. Let's write a simple version of the game: Hangman. The words my version of it challenges you to guess are Logo primitive procedure names. Try it out.
Click the mouse on [Start] to begin play. Use the keyboard to enter guess characters.
Hangman: Program Design
First of all, if you think you understand what needs to be done, go do it... You do not need to read any further unless
- you don't have a lot of time and want to use the code I give you for the easy (by this point in the lessons) parts of the program, or
- you are having trouble getting started.
What follows is just one way of writing the game Hangman. If you design your own version that works, congratulations, very good. But you probably should at least compare what you write with what follows - just to make sure you've picked up what this lesson is all about.
Hangman: Little People Design
Once again, I'm taking the little people approach to designing the Hangman program. Before continuing to read, think about what tasks you would assign to imaginary characters if you were designing the program. Write out job descriptions for what you would have each of your characters do.
I came up with four little people that provided all of the functionality that I needed in my program.
- The first person that I thought I needed was a person to display the characters that are guessed correctly. I immediately thought of Vanna White because she was responsible for doing this sort of thing for the "Wheel of Fortune" game show. If a guessed character is in the secret word, she will draw it in the position or positions it belongs. Vanna will also be responsible for announcing "You Win" if the word is completed.
- Harry Hangman has a job that is similar to what Vanna does, but for the opposite situation - a guessed character is NOT in the secret word. Harry draws the appropriate next body part on the graphics canvas. Harry gets to announce "You Lost" when the last body part has been painted.
- Although the player can look at the graphics canvas and see when she has won (when all character slots are occupied), our computer program can't do this. It needs a little person to figure this out. Given the secret word and the characters that have been guessed (inputs to her), Isabel Intersection will tell us if all of the letters in the secret word have been guessed. She gets her name from her ability to perform the mathematical intersection operation on sets. When the intersection of her inputs is equal to the secret word, the user has won.
- And to run things, I need Dion Director. He will look at the guessed characters, determine if they are in the secret word or not. He will get either Harry or Vanna to update the graphics canvas.
Implementing Little People as Procedures
To reduce the time it will take you to write your hangman program, I'm going to provide you with part of my version of the program. I'm doing this because I want this lesson to concentrate on the interesting parts of the program - not drawing the scaffold, or the unfortunate stick figure that pays for the game player's poor performance. We've done lots of this in the earlier lessons.
This is a slightly simplified (subset) of the applet I included above. It does not have "Start" and "Restart" buttons. These can be added once you get the game itself working.
When I wrote this program, the first thing I had to do was to write the procedures that did the things that our little people (Dion, Harry, Isabel, and Vanna) do. So, let's look at a diagram of the highest-level procedures in my program. Figure 16.17 shows the call graph for my program. I've provided the diagram so that you can visualize which procedures in my program represent which little people - as I talk about them.
In Figure 16.17, Vanna White consists of the procedures drawEmptyGuessWord and goodGuess and all of the procedures that these two invoke - which includes drawYouWin and drawCharMatches (and the bunch of procedures that they invoke, i.e., are at lower levels in the hierarchy).
Isabel Intersection consists of the procedure makeGuessWord and the procedure it invokes, namely makeGuessWordHelper.
Harry Hangman consists of the procedures drawGallows and badGuess and all of the procedures that badGuess invokes.
This leaves Dion Director who consists of the root procedures main and keyPressed, and the procedure pickSecretWord which main invokes.
You can click on Figure 16.17 to get a bigger version of it.
Hangman: Read the Code You've Been Given
Just like you did in the previous lesson, you first should read through the code that I have given you.
Copy/paste the code into TG. Use the menu item Interpret -> Editor Contents to see what happens.
The gallows is drawn, but that's about it.
So, now what? Go to the Global Variables section of the program and see what's there, read the comments. Read the main procedure. Figure out what it's doing. Note what procedures it invokes. Use the Editor's reverse search command to find the procedures it invokes and read them and their comments. Do the same with keyPressed.
Go to the CommandCenter and play with some of the procedures that are complete to see what they do. Try some of the "draw" procedures, drawHead, drawBody, ...
Doing this should give you a feel for what parts of the program are complete and what is left to do. You will have seen that all the procedures that need work have a comment ("... to be supplied ..."). The procedures you need to complete are (alphabetically)
- badGuess (part of Harry Hangman),
- drawCharMatchesHelper (part of Vanna White),
- makeGuessWordHelper (part of Isabel Intersection), and
- pickSecretWord (part of Dion Director).
Figure 16.18 has these procedures highlighted in orange in part of the program's call graph diagram.
The order in which you choose to finish these procedures is pretty much up to you. If you choose not to work on pickSecretWord first, then just use a make command to put some word, any word, into the secretWord global variable. Putting a random word into it is the job of pickSecretWord. But, if you want to delay doing the random thing, that's fine. In fact, if you just have pickSecretWord output a constant word, e.g. secret, that will make debugging the other procedures easier.
To help you with your with your final version of pickSecretWord, I'm going to introduce one more word/sentence operator: item.
ITEM: One More Procedure to Make Your Job Easier
|Outputs the number-th member of its second input. If its second input is a word, it outputs a word consisting on the number-th character. If its second input is a sentence, it outputs the number-th word of it.|
This lesson has been about the use of recursion to iterate through the members (characters) of words and members (words) of sentences. In most of the code we've worked on in this lesson, we've done something with each member. But one time, when we generated a random story, we picked random words from sentences. This was an example of where we simply extracted a member from a collection. In this case, we still used recursion to do this.
Like in this case, occasionally you will have an opportunity to compute which member of a collection that you want to do something with. In these cases you know the index number of the member, its numerical position, e.g., it's the third member, the sixth member, etc... This is where item comes in.
item has two inputs, an index number and a collection (a word or a sentence for now). It outputs the number-th member from the word or sentence. Figure 16.19 shows two examples of it in action.
Wrap up the Hangman Program
Ok, there you have it, all you need to complete Hangman. Have fun with the program. Even if it starts getting a bit frustrating, hang in their - you can do it...
Back in lesson 13 (Advanced Iteration), I introduced recursion with a bunch of graphical applications. In this lesson we used recursion to manipulate data, to iterate through the members of a collection.
As you will see in the next lesson, words and/or sentences are often used as data, to keep track of the state of things in our programs. Now that that you know how to iterate through all the members of a collection, how to take collections apart, and how to select a member from a collection, you are ready to write much more complicated Logo programs.
This has been (in my opinion) the hardest lesson in this series. Give yourself a pat on the back for completing it! Congratulations! Even if still seems a bit fuzzy how you will use what you've learned, hang in their; you'll get to use your new techniques in the next lesson.
Go to the Table of Contents
On to Mastermind Project