Assignment 2

Principles of Programming Languages (201-1289101)

Hierarchical Data Structures -- Abstract Data Types

Due 31 Mar 1997


In scm, type the expression '() instead of nil which is predefined to be equal to #f in certain implementations.

There are 6 questions plus one bonus optional question.


  1. Reverse
  2. Iterative map
  3. Substitute
  4. Remove
  5. Introduction to questions 5 to 7
  6. Twenty-one simulator and test-strategy
  7. stop-at and watch-strategy
  8. both operator

Question 1: Reverse

Write a function reverse that takes a list as argument and returns a list with the same elements in reverse order:
(reverse (list 1 2 3 4)) --> (4 3 2 1)
(reverse (list (list 1 2) (list 3 4))) --> ((3 4) (1 2))
Write both a recursive (reverse1) and an iterative version (reverse2).

Question 2: Iterative map

Write an iterative version of map. Map takes two arguments: a procedure proc and a list l and returns the list of the results of applying proc to each element of l. Name your function mapi.

Question 3: substitute

Write a function that takes as argument a tree and two numbers and returns a tree with every occurrence of the first number replaced by the second.
(substitute tree old new)

(substitute (list (list 1 2) (list (list 3 1))) 1 5) --> ((5 2) ((3 5)))
(substitute 1 1 5) --> 5

Question 4: remove

Write a function that takes as argument a tree and a number and returns a tree similar to the input one but with all occurrences of the number removed.
(remove (list 1 (list 2 1)) 1) --> ((2))
(remove 1 1) --> ()
(remove (list 1) 1) --> ()
(remove (list 1 (list 2 (list 1))) 1) --> ((2))

21 Simulator

For questions 5, 6 and 7 (optional bonus question), the following explanations apply. The game of 21 is a card game. The (simplified) rules are as follows:
  1. There are 2 players.
  2. Each card has a numeric value between 1 and 10.
  3. The goal is to accumulate a set of cards that totals as close to 21 as possible without going over 21.
  4. Each player receives one card that is visible to both players. The next cards are not visible to the other player.
  5. The first player asks for a card or decides to stop. If he gets a card and the total goes over 21 he loses. The first player keeps playing until either he loses or he decides to stop. If the first player does not lose, the second player takes his turn and plays similarly.
  6. When the second player decides not to take more card, both players show their cards and the player with the larger total wins.
The goal of the problem is to build a simulator of the game of 21 to evaluate the value of different strategies. The following data types need to be defined for implementing the simulation: The hand Abstract Data Type is implemented as follows:

;; Constructor (define (make-hand visible-card total) (cons visible-card total)) ;; Selectors (define (hand-visible-card hand) (car hand)) (define (hand-total hand) (cdr hand)) ;; Operations (define (make-new-hand first-card) ;; Create an initial hand with a single visible card (make-hand first-card first-card)) (define (hand-add-card hand new-card) ;; Hand-add-card takes a hand and a new card and returns a hand with ;; the same visible-card as the original, but with the total augmented by the ;; value of the new card: (make-hand (hand-visible-card hand) (+ new-card (hand-total hand))))

Question 5: twenty-one and test-strategy

Write a function twenty-one to run a simulation of a game between two strategies:
(define (twenty-one player1-strategy player2-strategy)
  ;; Return 1 if player1 wins
  ;; Return 2 if player2 wins
To test your function, use the following strategy:

(define (interactive-strategy your-hand opponent-visible-card) (newline) (princ "Opponent visible card: ") (princ opponent-visible-card) (newline) (princ "Your Total: ") (princ (hand-total your-hand)) (newline) (princ "Get another card (Y/N)? ") (user-says-y?)) (define (user-says-y?) (eq? (read) 'y)) ;; Test the simulator as follows: (twenty-one interactive-strategy interactive-strategy)
Define a procedure test-strategy that tests two strategies by playing a specified number of simulated Twenty-One games using the two strategies. test-strategy should return the number of games that were won by player1. For example,
(test-strategy interactive-strategy interactive-strategy 10)
should play ten games of Twenty-One. It should return a non-negative integer indicating how many games were won by player1.

Question 6: Strategies stop-at, watch-strategy

Define a procedure stop-at that takes a number as argument and returns a strategy procedure. The strategy stop-at should ask for a new card if and only if the total of a hand less than the argument to stop-at. For example (stop-at 16) should return a strategy that asks for another card if the hand total is less than 16, but stops as soon as the total reaches 16. To test your implementation of stop-at, play a few games by evaluating:
(twenty-one interactive-strategy (stop-at 16))
Thus, you will be playing against a house whose strategy is to stop at 16. When the simulated games runs, it is impossible for us to tell what is going on. We want to watch a strategy play by observing its inputs and the decisions it makes. Define a procedure called watch-player that takes a strategy and the name of a player as arguments and returns a strategy as its result. The strategy returned by watch-player should implement the same result as the strategy that was passed to it as an argument, but, in addition, it should print the information supplied to the strategy and the decision that the strategy returns. For example:
(test-strategy (watch-player (stop-at 16) 'yael)
               (watch-player (stop-at 15) 'ido)

Game 1: 
  Yael visible 6 -- hand 6 -- opponent visible 8
       get card 4 -- ask   -- total 10
  Yael visible 6 -- hand 10 -- opponent visible 8
       get card 7 -- stop -- total 17
  Ido visible 8 -- hand 8 -- opponent visible 6
      get card 10 -- stop -- total 18
Win: Player 2.

Game 2:
  Yael visible 3 -- hand 3 -- opponent visible 9
       get card 10 -- ask   -- total 13
  Yael visible 3 -- hand 13 -- opponent visible 9
       get card 7 -- stop -- total 20
  Ido visible 9 -- hand 9 -- opponent visible 3
      get card 9 -- stop -- total 18
Win: Player 1.

--> 1 ;; Number of games won by player 1.

Question 7 (OPTIONAL): both

Implement a procedure both that takes two strategies as arguments and returns a new strategy. This new strategy will ask for a new card if and only if both strategies would ask for a new card. For example, using the strategy:
(both (stop-at 19) hit?)
will ask for a new card only if the hand total is less than 19 and the user requests a new card.
The end.