Make your own free website on Tripod.com
 

Discussion #9 - Branch Control Structure


A branch is a control structure that tells the Interpreter to execute one of two possible instruction lists, depending upon the result of a test. The command ifelse implements a branch structure. ifelse requires three input expressions: a test reporter that outputs either the word 'true or the word 'false' and two quoted instruction lists. If the test reporter outputs 'true' the first instruction list is run. If the test reporter outputs 'false' the second instruction list is run. Here is an example:

ifelse :size > 100 [pr [The size is greater than 100.] ] [pr [The size is 100 or less.] ]
This instruction will print one of the two messages, depending upon whether ifelse receives 'true' or 'false' from the test reporter > .

As you can see, a branch structure is very similar is to a conditional structure. It differs only in requiring two instruction lists instead of one. Unlike a conditional, a branch will always execute an instruction list. The branch structure is used to provide alternative actions in response to situations that occur while the program is running as, for example, when the user's response to a question is right or wrong or when the turtle reaches a particular position while drawing on the screen.

The guess procedure illustrates how a branch structure works. The user tries to identify a mystery number by making guesses. The program provides clues - "Too big" or "Too small", depending on the relationship between the guess and the mystery number.

TO GUESS
  ht
  ct
  pr [I will pick a mystery number within the range you tell me.]
  pr [Your job is to find this number in as few guesses as possible.]
  pr [I will provide hints to help you out.]
  wait 200
  pr [ ]
  pr [What is the smallest possible mystery number?]
  name rw "lower.limit
  pr [What is the largest possible mystery number?]
  name rw "upper.limit
  name :lower.limit + random (:upper.limit - :lower.limit) "mystery
  pr [How many tries do you need to guess the mystery number?]
  name rw "tries
  wait 50
  pr [ ]
  pr [OK .... I'm thinking of a mystery number. What do you suppose it is?]
  wait 100
  ct
  do.guess :tries [ ]
END
TO DO.GUESS :TRIES :GUESS
  if :tries = 0 [pr se [Sorry, you have used up all your tries. The mystery number is]   :mystery stop]
  insert se :tries [tries remain. What is your guess?| | ]
  make "guess rw
  if :guess = :mystery [pr [Congratulations! You guessed the number!] stop]
  ifelse :guess > :mystery [pr [Too Big] ] [pr [Too Small] ]
  do.guess :tries-1 :guess
END
You see that the program is organized in the same way as design in Exploration #4. There is a top-level procedure, guess, whose function is to gather inputs for its subprocedure, do.guess. I have added a few "cosmetic" instructions to guess, such as inserting wait instructions and printing blank lines with the pr [ ] instruction. These have nothing to do with running the program itself; they are added only to improve readability.

The fourth name instruction is interesting. After the user has provided the needed information, the computer assigns a random mystery number to the variable :MYSTERY. random is a primitive reporter that requires one number as input. It outputs a "pseudo random" number from 0 to one less than its input. For example, if random were given the input 10, it would output a mystery number from 0 through 9. Although the output is unpredictable to the user, and therefore appears to be random, it is actually determined by a complicated formula in the computer's workspace rather than by pure chance. For this reason, it is called a pseudo random number.

In this program, the Interpreter calculates the input to random by subtracting the lowest from the highest number in the range chosen by the user (this gives the actual number of choices that random has available.) After random produces its number, the Interpreter adds the lower limit of the range. Suppose, for instance, you wanted a mystery number between 25 and 40. Subtracting 25 from 40 gives random a range of numbers from 0 to 14 from which to choose. Supposes it chooses 9. Adding 25 to 9 means that the mystery number would be 34.

The parentheses in this instruction tell the interpreter to subtract the two values before calculating the random number. When guess calls do.guess, it passes the starting values of the two local variables that do.guess requires, :TRIES and :GUESS. The value of :TRIES is obtained from the global variable created by the third name instruction. The value of :GUESS is the the empty list, since no guesses have yet been made. Both :TRIES and :GUESS are local variables in do.guess, since their values are changed with each pass through the iterative subprocedure. The variable :MYSTERY, on the other hand, is not changed by do.guess and so may remain a global variable.

Looking now at do.guess, you see that the first instruction is its stop rule, telling the Interpreter what to do in case the user runs out of tries before guessing the mystery number. The quoted list includes two separate instructions: to print a message and then to stop the run of the program. The printed message has two parts - a quoted list of words and the value of the mystery number. The primitive reporter se is needed in order to combine these two parts into a single output list for pr to use as its input. se requires two inputs that may be numbers, words, or lists; the Interpreter evaluates se by combining the elements from both of its inputs into a single output list. The next instruction uses se again, this time to combine the variable :TRIES and the quoted list of words into a single list for insert to display. insert is just like pr, except that it does not move the cursor to the next line after displaying its input, so the question and your response will appear on the same line.

The | | symbols enclose a space character that is to be included within the quoted list passed to insert for printing on the page. Without these symbols, the Interpreter would ignore any spaces after the "?" symbol. The special symbol | | tells the Interpreter to consider the space between the vertical bars as a word rather than as an end-of-element signal.

The primitive make in the next line of do.guess is similar to name. make requires the same two inputs as name but in reverse order: the variable's name is the first input to make and the variable's value is the second input. As far as the Interpreter is concerned, make and name may be used interchangeably. However, I use the two primitives to distinguish between different different activities in a program. I use name to create new variables, and I use make to change the values of variables that have already been created.  On the first pass through the iteration, make changes the empty-list value assigned to :GUESS in the top-level procedure to the first actual guess that the user enters. On succeeding passes, make changes :GUESS's value to the latest guess made by the user.

The second if instruction is also a stop rule, this time stopping the run if a successful guess is made. The branch structure ifelse is used to test whether an unsuccessful guess was larger than the mystery number, and then to print an appropriate hint: 'Too big' if the test reporter outputs 'true' and 'Too small' if it outputs 'false'. As you see, do.guess is a tail recursive procedure, since the final instruction calls the original procedure again, passing it a smaller value for :TRIES and an updated value for :GUESS.
 

Exploration #9

New Special Symbol


| | Used to delineate one or more spaces that are to included in a display. The Interpreter evaluates the space character between the vertical lines as if it were a word rather than an end-of-element signal.
 

New Commands

insert number, word, or list Similar to print, but without an automatic <RETURN> character following the display.

make variable.name number, word, or list Similar to name, but with the inputs in reverse order. make may be used instead of name anywhere in a program, but I find it helpful to use name to define a variable for the first time and make to change the value of a variable that has previously been defined.

ifelse true.or.false expression first instruction list second instruction list Used to introduce a branch control structure. If the test reporter outputs the word 'true', the Interpreter executes the instructions in the first list. If the test reporter outputs the word 'false', the Interpreter executes the instructions in the second list.

New Reporters

random number Outputs a pseudo random number from 0 to one less than its input.

sentence (se) first number, word, or list second number, word, or list Combines the elements of its two inputs into a single list and outputs the new list.
 

1. Copy the guess and do.guess procedures onto the flip side of a page and play the game enough times to really get the feel of it. Use your own wording for the questions and comments.

2. What is the most efficient strategy to use in order to minimize the number of guesses you need? What is the least number of guesses you would need to be sure of guessing it, if the mystery number could be any one of 10 numbers? any one of 100 numbers? any one of 1000 numbers?

3. Does the program work if you choose negative numbers as your range? How about with one negative and one positive number?

4. Design a new version of guess with a different kind of hint. Instead of telling you "Too Big" or "Too Small," change the hints to "Cold" or "Hot", signifying that your guess is further than 10 away from the mystery number or that it is no more than 10 away, above or below. Since the difference between your guess and mystery number could be a positive or negative number, you would need to use the or reporter as part of the branch structure. How does this change affect your playing strategy?

5. Create a few original procedures that use branch structures

6. Can you think of a way in which two branch structures might work together to direct the flow of a program along one of three possible paths? Try this with a program in which the computer prints different responses if the user answered "yes", "no" or "maybe" to a question. Try this again by modifying problem #4 to provide hints of "Cold," "Warm," and "Hot."