You should read through the end of Section 1.2.2 in SICP in order to be fully prepared for this lab.

Part @: Time Synopsis

1. As you answer the problems below, make a note on how long you spent on each of the sections.

2. If any of the individual problems took you notably more time than the rating stated, please identify them and write down your actual time spent. This will help us calibrate future problem sets.

Part A: Exercises

Please complete the following exercises before your recitation on Friday. Should you have any difficulties working these basic exercises, bring your questions to recitation.

1. [20] Walk through the evaluation of the following code step by step using the substitution model. To save time, we will allow these shortcuts:

   • writing e.g.   + ==> +   instead of   + ==> [primitive procedure +]
   • writing e.g.   (lambda (x) ...) ==> itself   instead of copying the entire lambda expression
   • reducing single combinations which involve only numbers and primitive procedures in one step
     e.g.   (= 2 0) ==> #f   and (- 2 1) ==> 1.
     Note that if there are variables in the combination e.g.   (+ 2 x)   then you have to evaluate it explicitly.

   However, aside from these shortcuts, do not skip any steps. In particular, we want you to explicitly evaluate all numbers, all defines, and explicitly desugar function definitions which don't use lambdas.

   NOTE: These guidelines apply for the other substitution model problems in this lab as well.

   (define incval 2)
   (define (r arg c)
     (if (= arg 0) 
         c 
         (r (- arg 1) (+ c incval))))
   (r 2 0)
       

   Identify the kind of process that this represents.

2. [45] Using only the Scheme mathematical functions {+, -, <, >, =} and the if special form (but not *):

   1. Write a function that performs multiplication on two positive integers recursively.

   2. Walk through the evaluation of your recursive multiplication using the substitution model on the arguments 2 3 [i.e. evaluation of (multiply 2 3)].

   3. Write a function that performs multiplication on positive integers iteratively. Use a helper function.

   4. Walk through the evaluation of your iterative multiplication using the substitution model on the arguments 2 3.

Part B: Book Exercises

Please work the following exercises from the textbook:

1. [10] Exercise 1.4 (compound expressions as operators). You don't have to write out a full substitution model evaluation, but explain in words why the procedure works i.e. explain enough to convince us that you could do the full evaluation if you wanted to.

2. [30] Exercise 1.6 (if as special form)

3. [45] Exercise 1.12 (binary coefficients using recursion)

   For exercise 1.12, the procedure should be callable like this: (pascal-coefficient level n) where level is the level of the triangle (starting from 0 for the first level), and n is the index of the coefficient in the level (also starting from 0).

Part C:

1. [15] Write a function called sign that returns -1 if its argument is negative, 0 if its argument is zero, and 1 if its argument is positive.

2. [70] Write a Scheme function which uses recursion to compute the quotient resulting from dividing one positive integer by another positive integer (i.e. the answer, throwing away all fractional parts). You may use any of the arithmetic operators {+, -, <, >, =} and any other non-arithmetic Scheme operations which you have learned. [This is not necessarily an efficient division algorithm.]

   1. What is the base case?

   2. What is the reduction step? In other words, how can you express the problem in terms of the solution to a smaller problem of the same kind?

   3. Prove the correctness of the reduction step. In other words, show that the reduction step you have just described really will compute the same value.

   4. Provide Scheme code for the recursive computation that corresponds to the reduction step you described above.

   5. Identify the kind of process that this represents.

   6. Prove that your recursive procedure will always terminate on any positive input. You do not need to give a mathematical proof; just describe in words why the procedure will always terminate.

   7. Show the behavior of your solution on the following inputs:

      • (divide 5 7)

      • (divide 7 7)

      • (divide 9 7)

      • (divide 100 7)

      • (divide 365 29)

      Note that (divide 100 7) means to divide 100 by 7 (which gives the result 14).

3. [30] Consider the following iterative procedure:

       
        (define (mystery a b)
          (define (mystery-aux a b c)
            (if (< a b) 
                c
                (mystery-aux (/ a b) b (+ c 1))))
          (mystery-aux a b 0))
       

   1. What does this mystery procedure compute?

   2. Write a recursive function that performs the same operation.

Part D: Good code, Bad code

For each of the following procedures, please answer:

1. What does the procedure do?
2. How hard was it to figure this out?
3. What characteristics of the code made it easy or difficult to decipher the intended operation?

1. [10]

   (define (factor? candidate number)
      (define (factor-aux candidate number multiple)
         (if (<= multiple number) 
             (if (= (* candidate multiple) number) ;; definition of factor
                 #t
                 (factor-aux candidate number (+ multiple 1))) ;; try next larger number
             #f)  ;; (number + 1) * (anything >= 1) is definitely > number
          )
      (factor-aux candidate number 1))
     

2. [10]

   (define (smallest-factor number)
     (define (smallest-factor-aux number current)
       (if (< current number)
           (if (factor? current number) 
               current ;; found one, return it
               (smallest-factor-aux  number (+ current 1))) ;; try next larger number
           number ;; trivial factor
           ))
     (smallest-factor-aux number 2) ;; start search at 2
     )
       

3. [10]

   (define (count-prime-factors number)
      (if (= (smallest-factor number) number)
          1 ;; only prime factor is self
          (+ 1 (count-prime-factors (/ number (smallest-factor number))))))
          ;; found one prime factor, count it, remove it, 
          ;; and recursively count remaining factors
       

4. [20]

   (define (icr a b)
      (if (< a (* b b b))
          (- b 1)
          (icr a (+ b 1))))
       

5. [30]

   (define (sd x)
     (if (= x 0) 
         0 
         (+ (remainder x 10) (sd (quotient x 10)))))
   
   (define (d3 x)
      (if (or (= 3 (sd x)) (= 6 (sd x)) (= 9 (sd x)))
          #t
          (if (< x 10)
              #f
              (d3 (sd x)))))