Com S 342 --- Principles of Programming Languages HOMEWORK 2: INDUCTION and RECURSION (File $Date: 2005/02/09 21:06:34 $) Due: problems 1-2 on Thursday, January 27, problems 3-6 on Tuesday February 1, 2005. In this homework, you will learn about higher-order procedures, syntax abstraction, and a bit more about recursion. All code is to be written in Scheme, using the exact procedure names specified in the problem descriptions. For code hand in *both* your printout of the code and a transcript of testing. See the directory $PUB/homework/hw2 for test data for each coding problem, as described in problem 7 below. (Recall that $PUB means /home/course/cs342/public/.) This applies even if you aren't using the Com S machines. (If you're not, see the course web page for hints.) *No* credit will be given for Scheme programming problems unless you also hand in a transcript that includes our tests. The section headings below give the readings related to the problems. (Please read them!) STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS, SECTION 1.3 (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3) 1. (5 points) [average3-c] Define a curried version of the following procedure, call it average3-c, and write the deftype for it as well. (deftype average3 (-> (number number number) number)) (define average3 (lambda (a b c) (/ (+ a b c) 3))) Test your code by executing the following. (test-hw2 "average3-c") Remember, for this and all of the following coding problems, you must hand in both a printout of your code file and a transcript showing testing using our test data. Be sure to include statements at the top of your code file identifying yourself, as described in previous homeworks. 2. (5 points) [average-9-42] Using your solution from problem 1, define a procedure, (deftype average-9-42 (-> (number) number)) that takes a number, c, and returns the average of 9, 42, and c. For example, (average-9-42 0) ==> 17 (average-9-42 3) ==> 18 Test your code by executing the following. (test-hw2 "average-9-42") Important: your solution must use average3-c from the previous problem. You will get zero points if your solution's code does not depend on average3-c. STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS, SECTIONS 1.1.6 (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html#%_sec_1.1.6) REVISED^5 REPORT ON THE ALGORITHMIC LANGUAGE SCHEME, section 4.2 CODE EXAMPLES PAGE (http://www.cs.iastate.edu/~cs342/docs/code-examples.shtml#SyntacticAbstraction) 3. (10 points) [occurs-twice using "and" and "or"] Write the procedure occurs-twice? from homework 1, problem 5 without using #t and #f, but using "and" and "or". Hand in a printout of your code and a transcript of testing that includes our test cases, which you can execute using: (test-hw2 "occurs-twice") 4. (5 points) [example of syntactic sugar] Give an example of a statement or expression in Java or C++ that is a syntactic sugar. State what langauge you are giving an example from. Explain by a simple example how to desugar this statement or expression. THE LITTLE SCHEMER, Chapters 2-5 $PUB/docs/follow-grammar-flat.txt 5. (20 points) [Following the grammar for flat lists] Which, if any, of the following proceduers has a correct outline that follows the grammar for flat lists? List all that have a correct outline for recursion over flat lists. (Note: we are mainly asking whether these have the right outline, but having the wrong outline will cause them not to work as they should.) ;; (a) (define extract-names (lambda (listings) (cond ((null? listings) '()) (else (extract-names (get-name (car listings)) (cdr listings)))))) ;; (b) (define extract-names (lambda (listings) (cond ((null? listings) '()) (else (cons (get-name (car listings)) (extract-names (cdr listings))))))) ;; (c) (define extract-names (lambda (listings) (cond ((null? listings) '()) (else (get-name (car listings)) (extract-names (cdr listings)))))) ;; (d) (define extract-names (lambda (listings) (if (null? listings) '() (cons (get-name (car listings)) (extract-names (cdr listings)))))) ;; (e) (define extract-names (lambda (listings) (if (null? listings) '() (begin (cdr listings) (cons (get-name (car listings)) (extract-names listings)))))) ;; (f) (define extract-names (lambda (listings) (cons (get-name (car listings)) (extract-names (cdr listings))))) ;; (g) (define extract-names (lambda (listings) (if (null? listings) listings (cons (get-name (car listings)) (extract-names (cdr listings)))))) 6. (20 points) [Following the grammar for flat lists 2] Which, if any, of the following proceduers has a correct outline that follows the grammar for flat lists? List all that have a correct outline for recursion over flat lists. (Note: we are mainly asking whether these have the right outline, but having the wrong outline will cause them not to work as they should.) ;; (a) (define delete-listing (lambda (name listings) (cond ((null? listings) '()) (else (cond ((equal? name (get-name (car listings))) (delete-listing name (cdr listings))) (else (cons (car listings) (delete-listing name (cdr listings))))))))) ;; (b) (define delete-listing (lambda (name listings) (cond ((null? listings) '()) ((equal? name (get-name (car listings))) (delete-listing name (cdr listings))) (else (cons (car listings) (delete-listing name (cdr listings))))))) ;; (c) (define delete-listing (lambda (name listings) (if (null? listings) '() (if (equal? name (get-name (car listings))) (delete-listing name (cdr listings)) (cons (car listings) (delete-listing name (cdr listings))))))) ;; (d) (define delete-listing (lambda (name listings) (if (null? listings) '() (append (if (equal? name (get-name (car listings))) '() (list (car listings))) (delete-listing name (cdr listings)))))) ;; (e) (define delete-listing (lambda (name listings) (cond ((equal? name (get-name (car listings))) (delete-listing name (cdr listings))) (else (cons (car listings) (delete-listing name (cdr listings))))))) ;; (f) (define delete-listing (lambda (name listings) (cond ((null? listings) listings) (else (cond ((equal? name (get-name (car listings))) (delete-listing name (cdr listings))) (else (cons (car listings) (delete-listing name (cdr listings))))))))) ;; (g) (define delete-listing (lambda (name listings) (cond ((null? listings) '()) (else (cond ((equal? name (get-name (car listings))) (delete-listing name (cdr listings))) (else (cons (car listings) (delete-listing name listings))))))))