Laboratory: Debugging your programs

Summary: In this laboratory, we start to explore the DrRacket debugger.

Preparation

a. Make sure that the csc151 package is up to date.

b. Require the rackunit and rackunit/text-ui packages.

c. Add the following undocumented code to your definitions pane.

(define function
  (lambda (a b c)
    (* (+ a b c)
       (if (> a b)
           (* (+ b 1) (- 1 (+ c 1)))
           (* (+ a b) (* c c))))))

(define further-from-zero
  (lambda (a b)
    (if (>= (abs a) (abs b))
        a
        b)))

(define furthest-from-zero
  (lambda (lst)
    (let ([first (car lst)]
          [rest (cdr lst)])
      (if (null? rest)
          first
          (further-from-zero first (furthest-from-zero rest))))))

Exercises

Exercise 1: Predicting evaluation order

a. Suppose we were to call (function 2 1 -1). What expressions do you expect to be evaluated, and in what order? What values will they have?

b. Click the Debug button.

c. Right-click (or control-click) on the open parenthesis that begins the body of function. Select “Pause at this point.”

d. Click the Go button.

e. In the interactions pane, type (function 2 1 -1) and then hit Enter. If all goes well, the program will stop at the point you added a pause.

f. Using the Step button, see what order DrRacket follows in the evaluation.

g. Try one or two other sample inputs.

h. Summarize what information is and is not available while you step through the evaluation of the expression.

Exercise 2: Exploring recursive calls

You will note that we have a recursively defined furthest-from-zero procedure that follows one of the patterns we have for reducing a binary procedure over a list. We’ll use that procedure to better understand the use of the call stack in DrRacket.

a. Predict what calls will be made to further-from-zero in evaluating (furthest-from-zero '(5 1 4 2 3)). For example, you might predict that it will first compare 5 to 1 or 2 to 3. Make a list of the expected a/b values.

b. Right-click (or control-click) on the open parenthesis that begins the body of furthest-from-zero (that is, the let expression) .
Select “Pause at this point.”

c. Click the Go button.

d. In the interactions pane, type (furthest-from-zero '(5 1 4 2 3)) and then hit Enter.

e. Repeatedly click on the Step button until you reach the point that there’s only one element in the list. In the “Stack” pane, You should see four lines labeled (furthest-from- ...) with one more line on top.

f. Try clicking on each of the (furthest-from-...) lines and see what happens. Explain in your own words, what the debugger is showing you.

g. Continue clicking the Step button. Pay attention to when control enters further-from-zero. Make a list of the values of a and b that you get in each call.

h. Did your list of values match or not?

Exercise 3: Identifying potential problems

The longest-string procedure is intended to take a nonempty list of strings as input and return a longest string in the list.

;;; Procedure:
;;;   longest-string
;;; Parameters:
;;;   strings, a nonempty list of strings
;;; Purpose:
;;;   Find a longest string in the list
;;; Produces:
;;;   longest, a string
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * longest is an element of strings
;;;   * For all str in strings, (string-length longest) >= (string-length str)
;;; Potential Pitfalls:
;;;   If a list has multiple strings that could naturally count as "longest",
;;;   this procedure returns one of them, but it could be any one (first,
;;;   last, middle, alphabetically first, etc.)

Here is an incorrect definition of longest-string.

(define longest-string-0
  (lambda (lst)
    (car lst)))
(define longest-string longest-string-0)

Write a test suite for longest-string. Your test suite should be sufficiently robust that it is likely to identify an error in most incorrect implementations of longest-string.

(define longest-string-tests
  (test-suite
   "tests of longest-string"
   (test-case "singleton lists"
              (check-equal? (longest-string (list "")) "")
              (check-equal? (longest-string (list "a")) "a"))
   ...))

Exercise 4: An incorrect implementation

Consider the following definition of longest-string.

(define longest-string-1
  (lambda (lst)
    (cond
      [(null? (cdr lst))
       (car lst)]
      [(> (string-length (car lst)) (string-length (cadr lst)))
       (car lst)]
      [else
       (longest-string-1 (cdr lst))])))

a. Replace the line in your code that reads (define longest-string longest-string-0) with one that reads (define longest-string longest-string-1) and then run your test suite.

> (run-tests longest-string-tests)

b. If your test suite did not find any errors in longest-string-1, add the following case.

(check-equal? (longest-string (list "ab" "cde" "f" "ghij")) "ghij")

c. Using the debugger, figure out what is wrong with the definition of longest-string-1 by using one of the failed inputs, stepping through the code and repeatedly predicting what should happen next, until one of your predictions fails to match.

d. Correct the implementation of longest-string-1.

Hint: When you recurse in the “larger car” case, you essentially need to discard the cadr. For example, suppose the input list is '("alpha" "beta" "a" ...). The length of the car is larger than the length of the cadr, so we want to “throw away” the cadr. That means we should recurse on '("alpha" "a" ...).

Exercise 5: Another incorrect implementation

Consider the following definition of longest-string.

(define longest-string-2
  (lambda (lst)
    (let kernel ([so-far (car lst)]
                 [remaining (cdr lst)])
      (cond
        [(null? (cdr remaining))
         so-far]
        [(> (string-length so-far) (string-length (cadr remaining)))
         (kernel so-far (cdr remaining))]
        [else
         (kernel (cadr remaining) (cdr remaining))]))))

a. Replace the line in your code that reads (define longest-string longest-string-1) with one that reads (define longest-string longest-string-2) and then run your revised test suite.

b. If your test suite did not find any errors in longest-string-2, add the following case.

(check-equal? (longest-string (list "a" "bcde" "fg" "hij")) "bcde")

c. Using the debugger, figure out what is wrong with the definition of longest-string-2 by using one of the failed inputs, stepping through the code and repeatedly predicting what should happen next, until one of your predictions fails to match.

d. Correct the implementation of longest-string-2.

Exercise 6: Yet another incorrect implementation

Consider the following definition of longest-string.

(define longest-string-3
  (lambda (lst)
    (let kernel ([so-far (car lst)]
                 [remaining (cdr lst)])
      (cond
        [(null? (cdr remaining))
         so-far]
        [(> (string-length so-far) (string-length (car lst)))
         (kernel so-far (cdr remaining))]
        [else
         (kernel (car remaining) (cdr remaining))]))))

a. Replace the line in your code that reads (define longest-string longest-string-2) with one that reads (define longest-string longest-string-3) and then run your revised test suite.

b. If your revised test suite did not find an error, something is wrong. Get help.

c. Using the debugger, figure out what is wrong with the definition of longest-string-3 by using one of the failed inputs, stepping through the code and repeatedly predicting what should happen next, until one of your predictions fails to match.

d. Correct the implementation of longest-string-3.

Exercise 7: Debugger-free debugging strategies

Discuss with your partner each of the following strategies for finding problems in code. Which do you use? In what situations do you find it most helpful?

a. When dealing with a recursive procedure over lists, first try it on the empty list, then on a few singleton lists, then on a few two-element lists, then on a few three-element lists, and so on and so forth.

b. Add (display (list 'procname param)) (newline) immediately after the lambda used to define a procedure.

c. Work out what the code should do on paper.

d. Rewrite the procedure again and compare your old answer to your new answer.

e. Make a list of inputs on which it fails and see if you can identify a common problem, then look to see what in the code relates to that problem.

f. Compare inputs for which it succeeds to inputs for which it fails and see how they differ. Then see where that difference might appear in the code.

Exercise 8: Other strategies

Make a list with your partner of other strategies you use when looking for problems in your code.