Exam 3: Advanced Scheming

Topics: List recursion, higher-order procedures, encapsulating control.

As you may recall, we began our investigation of recursion by considering how we might step through a list of numbers, adding them (or multiplying them or ...). Here are variants of the two versions we wrote:

One uses simple recursion.

(define sum-right
  (lambda (numbers)
     (if (null? numbers)
         0
   (+ (car numbers) (sum-right (cdr numbers))))))

The other uses a helper to accumulate the results.

(define sum-left
  (lambda (numbers)
    (let kernel ((so-far 0)
                 (remaining numbers))
      (if (null? remaining)
          so-far
          (kernel (+ so-far (car remaining)) 
                  (cdr remaining))))))

If you think carefully about it, the two processes compute results slightly differently. Given the list (n0 n1 n2 n3 n4), the first computes

(+ n0 (+ n1 (+ n2 (+ n3 n4))))

while the second computes

(+ (+ (+ (+ n0 n1) n2) n3) n4)

For addition, this doesn't make a difference. If the operation were subtraction, it would certainly make a difference.

The process of combining a list of values using a binary procedure is quite common. We've seen it for addition, subtraction, and multiplication. We might also use it for appending strings and many other operations. Computer scientists have various names for such a process. We'll call it fold, but others use inject (as in “inject this operation into this list”) or reduce (as in, “reduce this list to a single value”).

(proc v0 (proc v1 (proc v2 (... (proc vn-1  vn) ... ))))

> (fold-right + (list 1 2 3 4))
10
> (fold-right * (list 1 2 3 4))
24
> (fold-right - (list 1 2 3 4))
-2
> (fold-right (lambda (s1 s2) (string-append s1 ", " s2)) (list "sentient" "malicious" "powerful" "stupid"))
"sentient, malicious, powerful, stupid"
> (fold-right list (list 'a 'b 'c 'd 'e))
(a (b (c (d e))))

(proc (proc ... (proc (proc v0 v1) v2) ... vn-1) vn)

> (fold-left + (list 1 2 3 4))
10
> (fold-left * (list 1 2 3 4))
24
> (fold-left - (list 1 2 3 4))
-8
> (fold-left (lambda (s1 s2) (string-append s1 ", " s2)) (list "sentient" "malicious" "powerful" "stupid"))
"sentient, malicious, powerful, stupid"
> (fold-left list (list 'a 'b 'c 'd 'e))
((((a b) c) d) e)

Topics: Vectors, numeric recursion, high-order procedures.

We've seen how to implement map using recursion over lists. But we might also want to apply a procedure to each item in a vector.

Write a procedure, (vector-transform! vec proc), that replaces each value in vec with the result of applying proc to that value. For example,

> (define vec-nums (vector 1 2 3 4 5))
vec-nums
> (vector-transform! vec-nums (l-s + 1))
#(2 3 4 5 6)
> (vector-transform! vec-nums (l-s expt 2))
#(4 8 16 32 64)
> vec-nums
#(4 8 16 32 64)

Topics: Deep recursion, pair structures, predicates.

You have seen the predicate number-tree? that determines whether every leaf in a tree is a number. Generalize this idea by writing the predicate (tree-all? pred? tree), which indicates whether the predicate pred? is satisfied for all leaves in tree.

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: Higher-order procedures, searching, files.

Write, but do not document, a procedure, (file-search filename pred?), that searches the specified file for the first value that matches pred?. For example, if the file contains the values

12
1
23
152
6

then we might see the following results.

> (file-search "sample-file" odd?)
1
> (file-search "sample-file" (lambda (x) (> x 100)))
152
> (file-search "sample-file" (lambda (x) (< x 0)))
#f
> (file-search "sample-file" string?)
#f

Topics: Pair structures, deep recursion, reading code.

The following procedure does something with trees.

(define puzzle
  (lambda (tt)
    (if (pair? tt)
        (+ 1 (puzzle (car tt)) (puzzle (cdr tt)))
        0)))

Explain the purpose of this procedure. That is, explain what the procedure computes, not how it does that computation.

Topics: Higher-order programming, map, sectioning, conciseness.

Fill in the blanks as concisely as possible so that the given expressions produce the results shown. (Recall that the procedure char-upcase can be used to convert lower-case characters to upper-case.)

> (define strings (list "sentient" "malicious" "stupid"))
strings
> (map _______________________ strings)
("Computers are sentient" "Computers are malicious" "Computers are stupid")
> (map _______________________ strings)
("sentiently" "maliciously" "stupidly")
> (list->string (map _______________________ strings))
"SMS"

Topics: Higher-order programming, map, apply, conciseness.

A very useful mathematical identity is the fact that the log of the product of numbers is equal to the sum of the log of the numbers. You may have seen the special case for two numbers, log(a*b) = log(a) + log(b), but this generalizes to any number of values. In the following, you will use the built-in Scheme procedure log.

Topics: Unit testing, numeric recursion, strings.

When a procedure passes a series of tests, can you be certain the procedure is implemented correctly? Unfortunately not. Consider the following procedure and test suite.

;;; Procedure:
;;;   string-contains?
;;; Parameters:
;;;   str, a string
;;;   substr, a string
;;; Purpose:
;;;   Determine whether substr is contained in str.
;;; Produces:
;;;   result, an integer or #f
;;; Preconditions:
;;;   No additional.
;;; Postconditions:
;;;   If result is #f, then substr is not contained in str.
;;;   If result is an integer, then
;;;     0 <= result < (string-length str)
;;;     substr appears as a substring of str beginning at position result.
(define string-contains?
  (lambda (str substr)
    (let ((substr-len (string-length substr)))
      (let kernel ((start 0)
                   (finish (- (string-length str) substr-len)))
        (cond ((= start finish)
               #f)
              ((equal? substr (substring str 
                                         start 
                                         (+ start substr-len)))
               start)
              (else
               (kernel (+ 1 start) finish)))))))

(begin-tests!)
(test! (string-contains? "banana" "ban") 0)
(test! (string-contains? "banana" "nan") 2)
(test! (string-contains? "banana" "NAN") #f)
(test! (string-contains? "banana" "orange") #f)
(end-tests!)

Although the procedure passes the given tests, it is not correctly implemented. In fact, there are at least two different situations in which this procedure gives an incorrect result.

Write two distinct test cases (using test!) for which the given implementation of string-contains? fails.

What do we mean by distinct? The relationship between substr and str should be different in each case. As a counterexample, these two tests are not distinct. They are testing essentially the same thing.

(test! (string-contains? "banana" "ban") 0)
(test! (string-contains? "pineapple" "pine") 0)

Do you see why?

Topics: Numeric recursion, image iteration, image transformations.

All of the image transformations we have considered so far change each pixel independently of the others by applying a color transformation to each pixel. However, we can certainly imagine image transformation where the new color of each pixel also depends on the color of other pixels nearby.

We can create a motion blur effect on an image using the following algorithm. We visit each pixel in the image, row-by-row and column-by-column, from left to right and top to bottom. If the column is 0 (zero), then the color remains unchanged. Otherwise, we change the color of the pixel at (row, col) to the average of two colors: the current color of that pixel and the color of the pixel immediately to the left.

Write a new procedure, (image-motion-blur! image) that takes an image and applies this motion-blur effect.

Here's an example using image-motion-blur!.

	Actual size	5x zoom
>(define lambda-pic (image-load "lambda.jpg")) 1 >(image-show lambda-pic) 1
>(image-motion-blur! lambda-pic) 1

Hint: You will need a kernel procedure that recurses over the column and row and manipulates the color data using image-get-pixel, image-set-pixel!, and rgb-average. Your recursive kernel might also keep track of the previous color, but it is not absolutely necessary.

Warning: Test your procedure on small images.

Topics: Vectors, color palettes, image-scan-region.

As you may know, a histogram measures the frequency of occurrence of different types of items in a set. For example, we might survey the class and produce a histogram that gives the number of first-years, second-years, juniors, and seniors, or the number of science, social studies, humanities, and other majors. Machine vision researchers (and others) are sometimes concerned with the frequency at which each color occurs in an image. Since the number of possible colors is so huge, they use a smaller palette to categorize each color in the image. In this problem, we'll use a palette to encode each pixel in an image, and count the number of times each palette index occurs.

Recall the procedure (palette-encode-color palette color), which encodes a color by returning the index of the closest color from the palette. Recall also that image-scan-region allows us to iterate over all the pixels in a region of an image.

Use image-scan-region and palette-encode-color to implement the procedure documented as follows.

;;; Procedure:
;;;   image-palette-histogram
;;; Parameters:
;;;   image, an image identifier
;;;   palette, a list of RGB colors
;;; Purpose:
;;;   To count the number of times each palette-encoded color is used in an image
;;; Produces:
;;;   hist, a vector
;;; Preconditions:
;;;   palette is non-null
;;; Postconditions:
;;;   The length of hist is the same as the length of palette. 
;;;   Each index in hist contains the number of times the corresponding palette 
;;;     color is used in the image.

You can copy the palette-encode-color and related procedures from here. You do not need to include them in your solution.

Hint: You will need to create a vector and use it in the body of an anonymous procedure passed to image-scan-region. Each time you encode a color from the image, increment the value in the vector that corresponds to the resulting index.

Some example runs are below:

> (define colors-rainbow (list color-red color-orange color-yellow color-green color-blue color-indigo color-violet))
colors-rainbow
> (image-palette-histogram (image-load "/usr/share/pixmaps/fsview.xpm") colors-rainbow)
#(0 179 284 42 165 108 246)
> (image-palette-histogram (image-load "/usr/share/pixmaps/gnome-error.png") colors-rainbow)
#(205 189 23 0 0 0 1887)
> (image-palette-histogram (image-load "/usr/share/pixmaps/python.xpm") colors-rainbow)
#(0 14 531 0 0 18 958)