Assignment 4a

Due Date Monday at 9:00pm (Week 4)

Caution! Submit your answers to the first two problems separately from your examples for the last problem. There are two assignments available on the handin-server that you can submit to: be careful to submit the correct answers to the correct assignment.

Purpose To practice designing functions and programs with structured data.

Graded Exercises

Exercise 5 (Related to HtDP Exercise 109)

A Finite State Machine is an abstract (and general) encoding of a fairly common scenario: it represents the idea of a finite collection of states, and a set of allowable transitions between them. For example, the traffic-light animation used three states (green, yellow, or red), and three transitions (green -> yellow, yellow -> red, red -> green) that occurred once per tick. As another example, a telephone might be in one of three states (idle, ringing, or in-use), and might have several transitions: idle -> ringing when a call comes in, ringing -> idle if you choose to ignore the call, ringing -> in-use if you answer the phone, and in-use -> idle when you hang up. In general, there could be an arbitrary number of states, and arbitrary transitions between the states.

In this problem, you’ll design a world program that implements a Finite State Machine, that recognizes when a user types "good", "goood", "goooood", or similar variants with even more "o"s in them. These letters must appear consecutively: if any other characters appear in the middle (like in "goCS2500od"), your program should not accept the input. However, it doesn’t matter how many letters appear before or after: "CS2500 is gooooooood!" would be accepted.

Concretely:

• Your program will have five states:

  • START: haven’t seen any part of "good" yet

  • G: have seen the intial "g"

  • O1: have seen at least one "o"

  • O2: have seen at least two "o"s

  • D: have seen the final "d"

• From state START, if the user types a "g", move to state G. If the user types anything else, stay in START.

• From state G, if the user types an "o", move to state O1. If the user types a "g", stay in state G. If the user types anything else, go back to state START.

• From state O1, if the user types a second "o", go to state O2. If the user types a "g", go back to state G. If the user types anything else, go back to state START.

• From state O2, if the user types another "o", stay in state O2. If the user types a "g", go back to state G. If the user types a "d", go to state D. If the user types anything else, go back to state START.

• From state D, no matter what the user types, stay in state D.

• To render your program: if the user is in state START, draw a "white" rectangle. Draw the next four states as rectangles with colors "pale green", "spring green", "lime green", and "dark green", respectively.

Suggestion: Draw these rules as a diagram in the style of Exercise 109, to help you as you develop your code. You don’t need to hand this in, but having a picture available to you might help organize your thinking.

Reminder: This problem asks you to design the world program. That implies you must first determine what information should be in the world state, and design a data definition for it. Only then can you begin to design the helper functions that the world program needs in order to run.

Exercise 6 Consider the following purpose statement:

; Consumes a String and produces a (make-posn ...)

; whose x-component is the first character of the given string, and

; whose y-component is the remainder of the given string.

; An empty input string should error with "decode: bad input string"

Complete the design process for this function.

Reminder/Hint: A Posn was defined to be a structure whose components were numbers.

Exercise 7

Hence the -net- addition to the name of the program!

Design examples for the world program simple-net-forum, that you will implement for this Thursday’s homework. This program builds on last week’s assignment, and this time adds the ability to send posts to the central server, which then sends various messages back to your program. You should not repeat examples of functions from last week, unless those functions have changed behavior in some way; you should focus on examples for the new functionality.

Again, supply a terse but representative and informative set of examples: not so many as to overwhelm a peer-reviewer of your code, but not so few that they can’t figure out what your code is doing.

If you cannot figure out how to write down your examples in valid BSL code, then write it down in clear, short paragraphs of English text (as comments in your file) instead. You should be able to write down most of the examples, now, though.

Suggestion: As with last week, you will be implementing this functionality for Thursday’s homework. You may want to start early on it, to incorporate the feedback you got from your peers and from your graders.

Note: Again, be careful not to submit your implementation of your homework! Only submit the examples and any supporting information, not function definitions...and especially do not include code from this week’s assignment.