CS 37

Clab 3: Recursion, Iteration, some lists

Put DrScheme in beginner mode.
Now in one drscheme window, define fibrec as the text does on page 37 (define (fibrec n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fibrec (- n 1)) (fibrec (- n 2)))))) and in a second drscheme window, define fib and fib-iter as text on page 39. (define (fib n) (fib-iter 1 0 n)) (define (fib-iter a b count) (if (= count 0) b (fib-iter (+ a b) a (- count 1)))) Invoke step on (fibrec 6) then on (fib 6). Put the stepper windows side by side and compare and contrast. You should understand what is happening and how they differ. If you do not, discuss with your neighbor and/or call me over. After you have stepped enough to see what is going on in each version, click the home button and then do 20 steps in each window. Consider what a time-sharing operating system would have to remember in order to restart each computation assuming it had to stop each and swap them out of main memory. Consider the relative space and time efficiency of these two alternative methods to compute fibonacci numbers.

Another way to appreciate the difference is to start (fibrec 30) in the interaction window with fibrec then go over to the window with fib and start (fib 30). Do that now and note how much faster the iterative process finishes compared to the recursive process.

In order to focus on procedural abstraction, your authors work only with numbers in chapter 1. I want to be able to talk about some other applications and therefore want to introduce the built-in data structure, list, now. So... Please skim over the following material from online help: the first 3 screens worth of section 6.3.2 of the R5RS manual (get by clicking help, then select Manuals, then select Revised^5 Report on the Algorithmic Language Scheme, then select contents, then scroll to 6.3.2), then read about quote, cons, car, cdr, list, null?. Also look at equal? under section 6.1 in R5RS. Don't worry if you do not understand everything. If you happen to see set-car! or set-cdr!, turn away fast! These are examples of GROSS-LISP and we are trying to work in almost-Pure-Lisp for the time being . Define some lists and try applying these functions. I'll say a few words in class about lists.

Change your language level to Full Scheme R5RS. Now try evaluating each of the following. Make sure you understand the result you get. Ask questions if you have them.

a 'a (define a '(cat dog amt)) a 'a (car a) (cdr a) (cons 'horse a) a (define b '(horse dog)) a b (cons a b) (car (cdr a)) (define c '(dog horse)) (define d '(horse dog)) a b c d (equal? a b) (equal? b d) (equal? c d) ;;; note that order counts in ;;; list equality. (eq? b d) ;;; note eq? is different than equal? For now use equal? (cdr (cdr d)) (cddr d) ;;; short hand for (cdr (cdr d)) (cons 'fun '()) (null? (cdr d)) (null? (cddr d)) Note that when we cons'd two lists, the first list became one of the elements of the result instead of the elements of the first list becoming elements of the result. Frequently, we want the latter result. In fact, there is a built-in function to achieve that called append. Compare: > a (cat dog amt) > b (horse dog) > (cons a b) ((cat dog amt) horse dog) > (append a b) (cat dog amt horse dog) But in order to understand this better, we will write our own version of append calling it app so we don't redefine the built-in append. Put the list definitions of a and b and the following definition of app in you definitions window. ;;; app assumes that both arguments x and y are lists. The result is a new ;;; list consisting of the elements of x followed by the elements of y. (define (app x y) (cond ((null? x) y) ;;; if x is empty, return y (else (cons (car x) (app (cdr x) y))) ;;;otherwise, ;;; return the first element of x ;;; cons'd to the result of app applied to ;;; the rest of x and y ) ) Hit run and then evaluate in the interactions window: a b (cons a b) (app a b) Choose language Pretty Big under PLT and press run. Put (require (lib "trace.ss")) in the definitions window and press run.

Now put trace on for car, cdr, cons, and app and evaluate (app a b) making sure you understand the output of the trace. Ask questions if you have them.

Now it is time for you to work.

Define a procedure memb? that has the following specification: (define (memb? el lst) ;; returns #t if el is an element of list lst .... ;;; returns #f otherwise. Assume lst is a list.
You can define a recursive procedure to do this using only cond, null?, equal?, car, and cdr. The idea is to have
  1. a stopping case-say when lst is empty;
  2. check if el is the first item in lst;
  3. if not, check recursively el is in the rest of the list.
Remember to determine if cat is an element of the predefined list a, you should evaluate
(memb? 'cat a).

Call me over to check when you have debugged your procedure.
Reintroduce yourself to me and show me a demo of what you have. If I am too busy, just go on and try to catch me sometime to show off your memb?.

If you have time, define and debug the following function. Ask questions if you have them. Make sure your language level is Full Scheme.

;; remove-first returns a list with the first occurrence of sym ;; removed from list l: (define remove-first (lambda (sym l) ....

That's it for today. If you got this far, that's wonderful. If you didn't, don't worry. We are not in a race. Finish up at home and ask me questions next time if you have them. This is great stuff and will hopefully help you understand your reading.

Have a nice weekend.