CMSC 15100 - Summer 2005 - Lab 3

In this lab, we'll be making a guessing game web application.

To complete this lab, you'll need to download and use the webpages.scm teachpack from here. Also, on the lab computers, you'll need to set your default browser to Internet Explorer rather than Safari or Firefox. This can be done by starting Safari, going to "Preferences..." under the Safari menu, clicking General, and then choosing Internet Explorer from the Default Web Browser menu.

Part 1Let's try to write a program that plays a guessing game with you over the web. The way it will work is that it will ask you yes-or-no questions until it thinks it knows what you're thinking of. Then it will present its guess, and you will tell it whether it's right or wrong.

A natural way to represent a guessing strategy for the computer is to represent questions and the guesses they lead to as a tree:

A guessing-tree can be defined like this:

;;A guessing-tree is either:
;;   - a string [representing a guess]
;;   - (make-branch string guessing-tree guessing-tree)
;; where the string is a yes/no question, the first guessing tree is 
;; the tree to use if the answer to the question is "yes", and the
;;   second is the tree to use if the answer is "no"
(define-struct branch (question yes-tree no-tree))

The webpages.scm teachpack does the hardest bit of work for you: if provides two functions: ask-yes/no-question : string -> boolean that presents the given yes-or-no question as a web page and returns the answer the person at the web browser typed in (true means yes, false means no); and ask-free-response-question : string > string that presents the given free-response question and returns the answer as a string.

Using ask-yes/no-question, write two functions:

;; guess : string -> boolean
;; guesses that you're thinking of the given string and lets you
;; responds with whether it's right or wrong. If it's right, returns
;; true; if it's wrong, returns false.
(define (guess answer) ...)

;; play-guessing-game : guessing-tree -> boolean
;; asks you questions until it's able to make a guess, then makes that
;; guess and returns whether it was right or wrong
(define (play-guessing-game t) ...)

Part 2 Once you have these functions, it's easy to set up an infinite guessing game that always uses the same guessing strategy and never learns from its mistakes:

(define (game t) 
  (local ((define ans (play-one-game t))) 
    (game t)))

But it would be much cooler if as you played the game it got better and better, learning from its mistakes as it went on. The function

(define (play-guessing-game/learn t) 
  (play-guessing-game/learn (learn t)))

will do that with a suitable definition of learn (which will need to use ask-free-response-question in addition to ask-yes/no-question.

Write some new functions to support this:

;; get-mystery-item : string -> guessing-tree
;; given the incorrect guess the computer made, asks the user for what
;; they were actually thinking of and for a question. It returns a
;; tree whose question is the given question, whose "yes" branch is
;; the new item, and whose "no" branch is the original guess.
(define (get-mystery-item wrong-guess) ...)

;; learn : tree -> tree
;; plays the guessing game with the given tree and returns a new
;; tree that is:
;;   - the same as the old one if the program guessed right
;;   - the same as the old one except with the appropriate guess
;;     replaced by a branch
(define (learn t) ...)

(Thanks to Adam Shaw for the guessing game idea and for the Simpsons-tree image)

Part 3 The learn and play-one-game functions are similar to each other. Abstract them.

Part 4 (brain-teaser) It's pretty clear that you can cause an infinite loop — that is, have your program iterate forever and never terminate — by writing

(define (f x) (f x))
(f 1)

It's less clear, but also true, that you can write a not-much-bigger program that also causes an infinite loop without using define (or local) at all, using just the things you've learned in class up to this point. How? (This isn't a trick question.)