Lab 9 Finding Your Way

Purpose: The purpose of this lab is to practice working with mutually recursive data and designing universe programs (which you will need to do in upcoming assignments).

Textbook references: Chapter 19.1: Trees, Chapter 19.4 Designing with Intertwined Data, Chapter 20: Incremental Refinement

S-Expressions

Exercise 1 Design the function substitute. It consumes an SExpr s and two Strings, old and new. The result is like s with all occurrences of old replaced by new.

Dig a Tunnel

Consider the following representation of these caverns and tunnels:

; A TunnelMaze is one of:

; - "you win!"

; - "you lose"

; - Cavern

(define-struct cave [north south east west])

; A Cavern is a (make-cave MaybeDoor MaybeDoor MaybeDoor MaybeDoor)

; representing a room with four possible trap doors (in the north, south, east, and west of the cavern)

; A MaybeDoor is one of:

; - false (representing the fact that there is no trapdoor here)

; - TunnelMaze (representing a trapdoor leading you down to more of the maze)

Note that once you go down through a trapdoor you cannot get back up again. We’ll figure out how to get out of these tunnels later. After we acquire some treasure.

Let’s design our game! The player will start in some cavern and can make their way through trap doors by pressing the arrow key in the direction of that door (so for example, pressing the "left" arrow key would allow you to jump through a trap door on the west side of the cavern). The game ends when the player reaches either a room full of treasure ("you win!") or a room with a deadly monster in it ("you lose").

We will follow the steps for designing universe programs which we learned in Lab 2 Designing Functions, Data, and Programs. If you need more help designing universe programs, look for the pinned Piazza post titled "Universe Programs (big-bang)" which contains quite a few more resources on this material.

Step 1: What stays the same?

Exercise 2 Define constants to represent the things that are not changing in the game.

Step 2: What changes?

Luckily, we already have a data definition to work with! What a crazy random happenstance.

Exercise 3 Create templates for the given data definitions. When designing with intertwined data, following the template is essential so that you don’t get lost.

Exercise 4 Create a few example TunnelMazes to work with.

Step 3: Which handlers do we need?

Exercise 5 Write down the signatures and purpose statements for the handler functions you need. This is your "wishlist" of functions that you will need to create.

Step 4: Main Function

Now that we’ve decided on our handler functions, we can put together our main function which will call big-bang. Recall that we write this function first because in this course we follow a top down programming approach. That means larger functions go at the top of our program and smaller functions go underneath.

Exercise 6 Design the main function maze-game which, given an initial TunnelMaze starts the maze game using big-bang.

Step 5: Design your handlers

Exercise 7 Design the handlers you decided on in the last step. Remember to follow all the steps of the function design recipe. These steps will help you ensure that your functions all work together the way you expect.

Lab Quiz

If we were to have a lab quiz it would be this. But we don’t have those anymore.

Exercise 8 Design the function depth. The function consumes an SExpr and determines its depth. An Atom has a depth of 1. The depth of a list of SExprs is the maximum depth of its items plus 1. Be sure to use list abstractions where appropriate.