Exam 2: Control

a. Write, but do not document, a predicate, (simple-drawing? value), that checks whether value meets the form of a simple drawing. That is, your predicate should check whether value has the form described above.

Note: You may not use the procedure drawing? in solving this problem.

> (simple-drawing? drawing-unit-circle)
#t
> (simple-drawing? 4)
#f
> (simple-drawing? (drawing-hshift drawing-unit-square 5))
#t
> (simple-drawing? (drawing-group drawing-unit-circle drawing-unit-square))
#f
> (simple-drawing? (iota 8))
#f
> (simple-drawing? (list 'drawing 'ellipse RGB-BLACK "" 2 3 4 5))
#t
> (simple-drawing? (list 'drawing 'ellipse "black" "" 2 3 4 5))
#f
> (simple-drawing? (list 'drawing 'ellipse RGB-BLACK))
#f

b. Write, but do not document, a predicate, (drawing-rectangle? val), that determines whether val is a drawing and is a rectangle. You can use the simple-drawing? predicate to first check whether a value is a drawing.

> (drawing-rectangle? drawing-unit-square)
#t
> (drawing-rectangle? (drawing-scale drawing-unit-square 23))
#t
> (drawing-rectangle? (drawing-hshift drawing-unit-square -5))
#t
> (drawing-rectangle? drawing-unit-circle)
#f
> (drawing-rectangle? "This is a drawing of a rectangle")
#f

Write a procedure, (drawing-perimeter val), that finds the perimeter of a drawing that is a rectangle. (You need not find the perimeter of any other drawing such as an ellipse.)

Be sure to check preconditions and print appropriate error messages if those preconditions are not met.

> (drawing-perimeter drawing-unit-square)
4
> (drawing-perimeter (drawing-scale drawing-unit-square 20))
80
> (drawing-perimeter drawing-unit-circle)
drawing-perimeter: Don't know how to find the perimeter of that drawing.
> (drawing-perimeter (drawing-hscale drawing-unit-square 20))
42
> (drawing-perimeter (drawing-vscale (drawing-hscale drawing-unit-square 20) 15))
70
> (drawing-perimeter (drawing-group drawing-unit-circle drawing-unit-square))
drawing-perimeter: Don't know how to find the perimeter of that drawing.
> (drawing-perimeter 5)
drawing-perimeter: Expected a drawing, given 5

Write a procedure, (drawings-largest drawings), that takes a list of rectangle drawings and returns the drawing in the list having the largest perimeter.

Topics: Image transformations, Numeric values, Anonymous procedures, RGB colors

In this problem, we consider an approach to keeping messages secret. Steganography is the process of hiding a message in an image such that no one, other than the sender and receiver, even knows there is any hidden information. One approach to hiding an image inside a full-color image is to use the "least significant bits" to store the secret image. In the same way you're not likely to notice if two numbers far after the decimal point have changed, no one is likely to notice if the colors in a photo have been changed by only 1/8 from the original brightness values. How do we do that?

Just like the decimal numbers you're probably used to have "places" for the ones digit, tens digit, thousands digit, etc., the numbers storing the colors have eight "places" for binary bits that are either zero or one. We can shift and manipulate these binary bits by dividing and multiplying the number by powers of two (rather than powers of ten as for decimal numbers), as we do in the following.

Here is the algorithm we used to create a steganographic image.

Decoding the image is much simpler. At each pixel, for each color channel you can get the last three bits (which contain our hidden image) by taking its modulus with respect to 8 and rescaling the result to the range 0-255.

(a) Write, but do not document, a procedure, (image-steg-decode steg-image), that takes a steganographic image produced using this algorithm and produces the secret image.

Note: Use image-variant in your procedure. You should write your procedure with as little repeated code as possible. However, the fewer lambdas you use to write your solution the more points you will receive. Bonus points will be given for a completely lambda-free solution.

(b) Download this image of the kitten and test your procedure on it. Describe the secret image hidden inside it.

Suppose we want to draw a background and three circles on canvas.

We might write

(define canvas (image-new 100 100))
(image-show canvas)
(region-compute-pixels!
 canvas 0 0 (- (image-width canvas) 1) (- (image-height canvas) 1)
 (lambda (col row)
   (if (and (zero? (mod col 7)) (zero? (mod row 5)))
       RGB-WHITE
       RGB-BLACK)))
(region-compute-pixels!
 canvas 0 0 (- (image-width canvas) 1) (- (image-height canvas) 1)
 (lambda (col row)
   (if (>= 1600 (+ (square (- col 30)) (square (- row 40))))
       (rgb-new (+ 128 (* 255 (sin (* (/ pi 60) row)))) 
                0 
                (+ 128 (* -255 (cos (* (/ pi 60) row)))))
       rgb-transparent)))
(region-compute-pixels!
 canvas 0 0 (- (image-width canvas) 1) (- (image-height canvas) 1)
 (lambda (col row)
   (if (>= 900 (+ (square (- col 50)) (square (- row 50))))
       (let ((c (* 4 (sqrt (+ (square (- col 60))
                              (square (- row 60)))))))
         (rgb-new c 0 c))
       rgb-transparent)))
(region-compute-pixels!
 canvas 0 0 (- (image-width canvas) 1) (- (image-height canvas) 1)
 (lambda (col row)
   (if (>= 25 (+ (square (- col 20)) (square (- row 50))))
       RGB-BLACK
       rgb-transparent)))

Rewrite this code so that there is only one call to image-compute. That is, you should use a single expression of the following form.

(define canvas (image-compute ...))

Hint: Use a cond to decide which, if any, of the circles each position belongs in.

Hint: Which circle appears in front, and which appears behind? Your code should produce the same image as the code above.

Write, but do not document, a procedure (turtle-square-spiral! turtle initial-side segments scale-factor) that draws a spiral of the given number of segments, with each segment's length scale-factor times the the previous segment's length.

For example:

(define world (image-new 200 200)) (define tommy (turtle-new world)) (turtle-teleport! tommy 100 100) (image-show world) (turtle-square-spiral! tommy 75 20 0.9)

Most of the turtle procedures you have been writing so far use the same turtle to iterate a process. For instance, the procedure turtle-spiral! from the reading on iteration iterates the process of moving one turtle forward and turning by an increasing angle.

  (define turtle-action-02!
  (lambda (turtle angle)
    (turtle-forward! turtle 5)
    (turtle-turn! turtle angle)))

  (define turtle-spiral!
  (lambda (turtle steps)
    (for-each (l-s turtle-action-02! turtle)
              (list-drop (iota (+ 1 steps)) 1))))

While repeatedly drawing polygons is interesting and useful because the turtle always returns to its original position, there are situations in which we may not want to rely on this postcondition. Those situations will often call for using multiple turtles.

Using turtle-spiral! as a helper, write, but do not document, a procedure, (turtles-spin-longer-spirals! turtles initial-steps scale-factor angle), that uses turtle-spiral! with each turtle in the list turtles. Before drawing its spiral, each turtle should be turned by angle degrees more than its previous turtle.

For example, if angle were 30, the first turtle would turn by zero, the second by 30, the third by 60, and so on.

In addition, each turtle's spiral should have a number of steps that is approximately scale-factor times the previous turtle's number of steps. (Because the number of steps needs to be an integer, you may need to round.)

Here is an example of turtle-spin-longer-spirals! in action:

(define forest (image-new 200 200)) (define tiffany (turtle-new forest)) (turtle-teleport! tiffany 100 100) (define clones (map turtle-clone (make-list 8 tiffany))) (turtles-spin-longer-spirals! clones 4 1.5 45)

An important Scheme primitive function is car that returns the first item in a list. What if you want the last item instead? Scheme does not provide last-item as a primitive, you have to make your own, perhaps like this:

;;; Procedure: 
;;;   last-element
;;; Parameters: 
;;;   lst, a list
;;; Purpose: 
;;;   Find and return the last element of a list
;;; Process
;;;   Repeatedly take cdr until we reach the list's end
;;; Produces:
;;;   last, a value
;;; Preconditions: 
;;;   lst must be non-empty
;;; Postconditions: 
;;;   last is the last element of lst
(define last-element
  (lambda (lst)
    (cond
      ((not (list? lst)) 
       (error "last-element expects a list, given: " lst))
      ((null? lst) 
        (error "last-element expects a non-empty list, given: " lst))
      (else
       (let kernel ((remaining lst))
         (if (null? (cdr remaining)) 
             (car remaining)
             (kernel (cdr remaining))))))))

There is a shorter way to write last-element that does not require you to (explicitly) write a recursive procedure. Write a shorter version of last-element. Explain in your 6-P documentation how your shorter version achieves its goal with a seventh P (process).

As you've probably noted, we like to write long procedure names that make it perfectly clear what procedures are supposed to do. These procedures have names like image-compute-pixels! or rgb-complement. We also try to choose good names for the variables and parameters in our code.

However, some programmers prefer to give their procedures and variables short names, such as f and x. Some pay little attention to formatting.

Unfortunately, such short names can obfuscate code, particularly when combined with a lack of care in formatting. For example, consider the following useful procedure.

(define m (lambda (v) (let k ((r v)) (if (null? (cdr r)) null (cons (car r) (k (cdr r)))))))

(a) Make this procedure definition easier to read as follows.

When you format your exam, please put the introductory comments before the revised procedure definition.

(b) Perhaps you'll notice that there is a shorter way (in terms of code) to implementing the same procedure. Write a second version that is shorter, much like Problem 8.

(c) Which version of last-element do you like better? What about m (or rather whatever you renamed it)? Do you like the original recursive version, or do you prefer the shorter version? Why? Write a sentence or two explaining your choice.

(I am Sam I am) is not a list palindrome; but (I am Sam am I) is a list palindrome. (a man a plan a canal panama) is not a list palindrome; but (a m a n a p l a n a c a n a l p a n a m a) is a list palindrome. Here is a definition of what it means to be a list palindrome:

(a) If lst is (i am sam am i), what is (m (cdr lst)) where m is as defined in Problem 9?

(b) Complete the definition and documentation of the procedure palindrome? that returns #t for a list palindrome and #f for anything else.

Hint: You should use the procedures from Problems 8 and 9.

;;; Procedure: 
;;;   palindrome?
;;; Parameters: 
;;;   lst, a list
;;; Purpose: 
;;;   Determine whether a list is a palindrome
;;; Process:
;;;   If lst is short enough we can return #t.
;;;   If the first and the last items of lst match, 
;;;     we check the inner portion of lst for "palindromicity"
;;; Produces: 
;;;   is-palindrome, a boolean
;;; Preconditions:
;;;   lst is a list [Unverified]
;;; Postconditions:
;;;   ___
;;;   ...
(define palindrome?
  (lambda (lst)
    (cond
      ((null? lst) ______)
      ((null? (cdr lst)) ______)
      ((equal? (car lst) (last-element lst)) 
       (palindrome? ______))
      (else #f))))

> (palindrome? '(I am Sam I am))
#f
> (palindrome? '(I am Sam am I))
#t
> (palindrome? '(able was I ere I saw elba))
#f
> (palindrome? '(able was I ere I was able))
#t
> (palindrome? (append (iota 20) (reverse (iota 20))))
#t

(c) Did you notice that the reverse of a palindrome is the same as the original list? Write a shorter version of palindrome? that makes use of this observation.

(d) Do you prefer the version of palindrome? from (b) or from (c)? Write a few sentences about why, commenting on how elegant or intuitive you find them and possibly their relative efficiency.