CS245: Principles of Programming Languages, Assignment #1

Douglas Blank
Fall 2008

Assignment #1: due Tuesday Sept 16, 2008 in class

1. Rewrite the following as Scheme expressions:
   1. 1.2 × (2 - 1/3) + -8.7
   2. (2/3 + 4/9) / (5/11 - 4/3)
   3. 1 + 1 / (2 + 1 / (1 + 1/2))
   4. 1 × -2 × 3 × -4 × 5 × -6 × 7

2. Rewrite the following expressions, using let to remove common subexpressions and to improve the structure of the code. Do not perform any algebraic simplifications.
   1. (+ (- (* 3 a) b) (+ (* 3 a) b))
   2. (cons (car (list a b c)) (cdr (list a b c)))
   
   
3. Define the function member? which takes a symbol and a list and returns #t if the symbol is in the list and #f otherwise.

   > (member? 'a '())
   #f
   > (member? 'a '(1 2 3 a))
   #t
   > (member? 'a '((a) (b) (c)))
   #f
   

4. Define the function reverse which takes a list and returns the reverse of it.

   > (reverse '())
   ()
   > (reverse '(1 2 3 a))
   (a 3 2 1)
   > (reverse '((a) (b) (c)))
   ((c) (b) (a))
   

5. Define the function rac that takes a list and returns the last item in the list.

   > (rac '(1 2 3))
   3
   > (rac '(1 2 3 a))
   a
   > (rac '())
   Error in rac: () is not a pair.
   

6. Define the function snoc that takes a symbol and a list and returns a list with the symbol on the tail end.

   > (snoc 'a '(1 2 3))
   (1 2 3 a)
   > (snoc 'b '(1 2 3 a))
   (1 2 3 a b)
   > (snoc '4 '(1 2 3))
   (1 2 3 4)
   

7. A more elegant (though possibly less efficient) way to define cadr and cddr than given in Chapter 2 is to define a procedure that composes two procedures to create a third. Write the procedure compose, such that (compose p1 p2) is the composition of p1 and p2 (assuming both take one argument). That is, (compose p1 p2) should return a new procedure of one argument that applies p1 to the result of applying p2 to the argument. Use compose to define cadr and cddr.

8. One could define the Fibonocci sequence as:

   (define fib
      (lambda (n)
         (cond 
           ((= n 1) 1)
           ((= n 2) 1)
           (else (+ (fib (- n 1)) 
                    (fib (- n 2)))))))
   

   How many times is fib called to compute (fib 30)? How does this scale up? List the number of times that fib is called for the first 35 Fibonocci numbers. If you had 24 hours, what's the n of the fib that you could compute?

   Hints: There is a (time exp) form that will tell you the amount of time it takes to evaluate exp. To get a global count of calls to fib, you'll need a global variable.