Exam 3: Sophisticated Scheming

Write 6 Ps documentation for a procedure (vector-ref-mutate! vec index proc) that applies proc to the item in vec at index, storing the result in the same location. Here are some sample runs of such a procedure.

> (define numbers (make-vector 4 0))
> (vector-ref-mutate! numbers 2 increment)
> numbers
#(0 0 1 0)
> (vector-ref-mutate! numbers 3 (l-s + 5))
> numbers
#(0 0 1 5)
> (vector-ref-mutate! numbers 4 decrement)
vector-ref-mutate!: index 4 out of bounds for vector #(0 0 1 5)
> (vector-ref-mutate! numbers 0 5)
vector-ref-mutate!: expected procedure for 3rd parameter; given 5

Implement the vector-ref-mutate! procedure. Your procedure should verify its preconditions to the extent possible. You need not verify any properties of proc other than its type.

The lab on randomized drawing used the following two procedures to simulate rolling a pair of dice.

;;; Procedure:
;;;   roll-a-die
;;; Parameters:
;;;   None
;;; Purpose:
;;;   To simulate the rolling of one six-sided die.
;;; Produces:
;;;   An integer between 1 and 6, inclusive.
;;; Preconditions:
;;;   [None]
;;; Postconditions:
;;;   Returns an integer between 1 and 6, inclusive.
;;;   It should be difficult (or impossible) to predict which
;;;     number is produced.
(define roll-a-die
  (lambda ()
    (+
      (random 6)    ; a value in the range [0 .. 5]
      1)))          ; now in the range [1 .. 6]

;;; Procedure:
;;;   pair-a-dice
;;; Parameters:
;;;   [None]
;;; Purpose:
;;;   Roll two six-sided dice and find their sum.
;;; Produces:
;;;   roll, an integer
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   2 <= roll <= 12
;;;   Across multiple calls, the various rolls have the same probabilities 
;;;     as we would get from rolling two dice.
(define pair-a-dice
  (lambda ()
    (+ (roll-a-die) (roll-a-die))))

Computational scientists often find it difficult to analyze quantities mathematically and resort to simulation to get an approximate answer.

Write, but do not document, a procedure (count-rolls n) that rolls a pair of six-sided dice n times. It should produce a vector of length 13, where the value at each index is the number of times that total (the index) came up.

Hints: Indices 0 and 1 will always contain zero, because it is not possible to roll two dice and produce a zero or a one. You should use the procedures pair-a-dice and vector-ref-mutate! in your solution.

> (count-rolls 1)
#(0 0 0 0 0 0 0 0 0 0 1 0 0)
> (count-rolls 100)
#(0 0 2 6 15 12 10 15 12 12 11 4 1)

As you may recall, (substring str start finish) extracts a substring from str that runs from position start to position finish - 1. The string-length procedure lets you find the length of a string.

Write, but do not document, a procedure, (substrings str len), that generates a list of all the substrings of str of length len. For example,

> (substrings "television" 3)
("tel" "ele" "lev" "evi" "vis" "isi" "sio" "ion")

Write, but do not document, a procedure (all-substrings str) that finds all substrings of a given string. For example,

> (all-substrings "computer")
("c" "o" "m" "p" "u" "t" "e" "r" "co" "om" "mp" "pu" "ut" "te" "er" "com" "omp" 
"mpu" "put" "ute" "ter" "comp" "ompu" "mput" "pute" "uter" "compu" "omput" 
"mpute" "puter" "comput" "ompute" "mputer" "compute" "omputer" "computer")

Hint: Your procedure should call the substrings procedure from the previous problem.

Write, but do not document, a procedure (char-shifter amount), which produces a procedure that takes a character and shifts it by amount, accounting for any wrap-around. Your procedure only needs to work for upper-case letters.

You should strive to make your procedure as concise as possible.

> (define char-encode-1 (char-shifter 5))
> (char-encode-1 #\H)
#\M
> (char-encode-1 #\Z)
#\E

Of course, Caesar ciphers are much more interesting when applied to strings, rather than to individual characters. It is also natural to think of a cipher as a function from strings to strings, rather than from numbers to strings. Hence, we'd like a procedure that builds ciphers.

Write, but do not document, a procedure (shift-encoder amount) that returns a procedure that takes a string as input and produces a string where each character is replaced by another whose collating sequence number differs from the original by amount, accounting for wrap-around. Again, your solution only needs to work for strings consisting of upper-case letters.

You should strive to make your procedure as concise as possible.

> (define encode-1 (shift-encoder 5))
> (encode-1 "HELLO")
"MJQQT"
> (define encode-2 (shift-encoder 2))
> (encode-2 "MJQQT")
"OLSSV"
> (define decode-12 (shift-encoder -7))
> (decode-12 "OLSSV")
"HELLO"
> ((o decode-12 encode-2 encode-1) "WORLD")
"WORLD"

Topics: Deep recursion, pair structures, predicates.

You have written a predicate color-tree? in the lab on trees that determines whether every leaf in a tree is a color. Generalize this idea by writing the predicate (tree-all? pred? tree), which indicates whether the predicate pred? is satisfied for all leaves in tree. You need not document tree-all?.

For example,

> (tree-all? number? (cons (cons (cons 1 2) (cons 3 4)) (cons 5 (cons 6 7))))
#t
> (tree-all? even? (cons (cons (cons 1 2) (cons 3 4)) (cons 5 (cons 6 7))))
#f
> (tree-all? char? (cons (cons #\a #\b) #\c))
#t
> (tree-all? char? (cons (cons #\a #\b) "c"))
#f
> (tree-all? odd? 1)
#t
> (tree-all? char? 1)
#f

Topics: Sorting, vectors, numeric recursion, higher-order procedures.

In the reading on sorting and the lab on insertion sort, you encountered a procedure list-keyed-insertion-sort, which could sort records stored in a list by any element of the record, not just the first element. It would be helpful to have such a procedure for records stored in a vector, as well.

Write a procedure, (vector-keyed-insertion-sort! vec get-key may-precede?) that sorts a vector of compound objects by key. You do not need to document vector-keyed-insertion-sort!.

For example,

> (define elements-mythology 
          ; Source: http://www.enotes.com/topic/List_of_chemical_elements_named_after_people
          (vector (list "iridium" "Ir" 77 "Iris" "greek")
                  (list "niobium" "Nb" 41 "Niobe" "Greek")
                  (list "promethium" "Pm" 61 "Prometheus" "Greek")
                  (list "tantalum" "Ta" 73 "Tantalus" "Greek")
                  (list "thorium" "Th" 90 "Thor" "Norse")
                  (list "titanium" "Ti" 22 "Titans" "Greek")
                  (list "vanadium" "V" 23 "Vanadis (Freyja)" "Scandanavian")))
> (vector-keyed-insertion-sort! elements-mythology caddr <=)
> elements-mythology
#(("titanium" "Ti" 22 "Titans" "Greek")
  ("vanadium" "V" 23 "Vanadis (Freyja)" "Scandanavian")
  ("niobium" "Nb" 41 "Niobe" "Greek")
  ("promethium" "Pm" 61 "Prometheus" "Greek")
  ("tantalum" "Ta" 73 "Tantalus" "Greek")
  ("iridium" "Ir" 77 "Iris" "Greek")
  ("thorium" "Th" 90 "Thor" "Norse"))

While it is possible to write this procedure by converting the vector to a list, using list-keyed-insertion-sort!, and then converting the result back to a vector, you should not use this strategy. Rather, write this procedure directly using numeric recursion over the positions in the vector. You may want to use vector-insertion-sort! as a template.

Topics: Higher-order procedures, code reading, documentation.

Many implementations of Scheme contain the following procedures.

(define negate
  (lambda (pred?)
    (lambda (val)
      (not (pred? val)))))

(define select
  (lambda (lst pred?)
    (cond
      ((null? lst)
       null)
      ((pred? (car lst))
       (cons (car lst) (select (cdr lst) pred?)))
      (else
       (select (cdr lst) pred?)))))

(define member?
  (lambda (val lst)
    (and (not (null? lst))
         (or (equal? val (car lst))
             (member? val (cdr lst))))))

Suppose we've defined the following procedure using those standard procedures.

(define list-subtract
  (lambda (lst1 lst2)
    (select lst2 (negate (r-s member? lst1)))))

Read and experiment with list-subtract to understand its purpose and use. Then write 8 Ps documentation for list-subtract. In addition to the standard 6 Ps, include two additional sections: