|
|
||
| C211 | Introduction to Computer Science | Spring 2000 |
-it for programs that are written in accumulator-passing style. Since APS procedures are not necessarily iterative, we will often use the suffix -aps instead.
a5.ss. Your file MUST be named a5.ss or it will be rejected by the current web-based handin system.Include the following information as a comment at the top of the file you submit:
Recall that a comment in Scheme begins with the character `;' (a semicolon) and continues to the end of the line. For example, my file a5.ss would begin:
;;; Oscar Waddell (owaddell@cs.indiana.edu)
;;; Lab Section 1398
;;; C211 Assignment 5
Label the parts of your solutions by including problem numbers as comments just before the corresponding Scheme expressions. For each procedure, include a comment that describes what the procedure does (not how it is done).
Test your code on a wide range of inputs. Many of the exercises show sample inputs and the expected results. Use these examples as a starting point. Keep in mind that we will use a wider variety of inputs when grading your assignments.
Save your work often by selecting ``Save Definitions as Text'' from the ``File'' menu. Do not simply click on the Save button. You should save your work on your student locker and on a floppy disk.
When you are ready to hand in your assignment, review the Assignment 1 handin instructions or go directly to the submissions page.
(let ([x 5])
(let ([x 9])
(let ([x 7])
x)))
This exercise asks you to rename each bound variable in an expression to make these scoping relationships explicit. That is, you are to add a numeric suffix to the name of each bound variable to indicate where it is bound. Working in from the outside of the expression, add a 1 to the name of each variable bound by the first let expression, add a 2 to the name of each variable bound by the let expression nested within, and so on. Be sure to consistently rename references to the bound variables.
| (Sample problem)
Rename bound variables in the following expression as described above. Bind your answer for this part to the variable
(let ([x 1] [y 2] [z 3])
(let ([y z] [x 9])
(list x y z)))
becomes
(define example1
(let ([x1 1] [y1 2] [z1 3])
(let ([y2 z1] [x2 9])
(list x2 y2 z1))))
Note that both expressions evaluate to (9 3 3). Renaming the bound variables has not changed the meaning of the program. |
Rename the bound variables in each of the following expressions as described above. Do this renaming for all variables bound by let, letrec, and lambda. Use a different number for each binding construct you encounter.
let expression with renamed variables) for this part to the variable exercise-1a.
(let ([x 9] [y 10])
(let ([f (lambda (x) (+ x y))])
(let ([x 5] [y 3])
(f (* x y)))))
exercise-1b.
(let ([f (lambda (x) (+ x 1))] [z 8])
(let ([f (lambda (z) (if (= z 10) 1 (* 3 (f (+ z 3)))))])
(f 7)))
exercise-1c.
(let ([f (lambda (x) (+ x 1))] [x 5])
(letrec ([f (lambda (z) (if (= z 10) 1 (* 3 (f (+ z 3)))))])
(f 7)))
exercise-1d.
(letrec ([f (lambda (n) (or (zero? n) (g (- n 1))))]
[g (lambda (x) (not (f x)))])
(list (f 3) (g 4)))
list-swap that takes two items item1 and item2 and a list ls, and replaces each top-level occurrence of item1 in ls with item2 in the output and replaces each top-level occurrence of item2 in ls with item1 in the output.
To avoid passing item1 and item2 along at each recursive step, use letrec to define a local help procedure that takes just a single argument ls.
For example, here are two equivalent ways to scale the numbers in a list. The first version passes n (unchanged) at each recursive call. Since the second version uses a local help procedure that is in the scope of the binding for n, it does not have to pass n along in the recursive call.
(define scale
(lambda (n ls)
(if (null? ls) '() (cons (* n (car ls)) (scale n (cdr ls))))))
(define scale
(lambda (n ls)
(letrec ([help
(lambda (ls)
(if (null? ls) '() (cons (* n (car ls)) (help (cdr ls)))))])
(help ls))))
We say that n is a free variable in the local help procedure: the scoping rules allow the help procedure to refer to variables that are bound in an enclosing environment (in this case, the arguments of the lambda expression). Although this technique offers only a small advantage in the example above, it proves invaluable when writing complicated procedures that manipulate dozens of variables.
Here are some sample inputs to show how list-swap should behave.
> (list-swap 2 4 '()) () > (list-swap 'a 'b '(1 2 3)) (1 2 3) > (list-swap 'dog 'man '(dog bites man)) (man bites dog) > (list-swap 'water 'chocolate '(like water for chocolate)) (like chocolate for water) > (list-swap 'to 'be '(to be or not to be)) (be to or not be to)
diff-lists that takes two lists and returns a list of the corresponding elements that differ. Signal an error if the two lists are not of the same length, but do not use the length procedure in your solution. Use letrec to define a local help procedure in the scope of bindings for the original inputs so that you can identify the original inputs when signalling an error.
> (diff-lists '() '())
()
> (diff-lists '(a b c d) '(a b c d))
()
> (diff-lists '(a b l e) '(a b c d))
((l c) (e d))
> (diff-lists '(x y z) '(1 2 3))
((x 1) (y 2) (z 3))
> (diff-lists
'(hot food hit the spot)
'(dog food hit little spot))
((hot dog) (the little))
> (diff-lists '(m e t e r) '(f o o t))
Error in diff-lists: lists (m e t e r) and (f o o t) differ in length.
> (diff-lists '(s w o r d) '(d a g g e r))
Error in diff-lists: lists (s w o r d) and (d a g g e r) differ in length.
multi-subst that takes two lists, an association list and a flat list, and returns a new copy of the second (flat) list where any item matching an entry in the association list has been replaced with the corresponding entry.
An association list is simply a list containing sublists of two elements each. The car of each sublist is a key to be matched. The cadr of each sublist is the item to use as the replacement for that key. For example, the following list associates roses with thorns, chocolate with cavities, and cards with paper-cuts:
((roses thorns) (chocolate cavities) (cards paper-cuts))
Use letrec to define any help procedures you deem necessary.
Here are some examples to show what is intended.
> (multi-subst '() '(a b c d))
(a b c d)
> (multi-subst '((i aye)) '(p i e))
(p aye e)
> (multi-subst '((a b) (c d) (e f)) '(a b c d e f))
(b b d d f f)
> (define pessimism
'((promises threatens)
(roses thorns)
(chocolate cavities)
(cards paper-cuts)))
> (multi-subst
pessimism
'(valentines day promises cards chocolate and roses))
(valentines day threatens paper-cuts cavities and thorns)
An iterative process is generated by a procedure that is tail-recursive. In order to be tail-recursive, a procedure must first be recursive. Furthermore, the recursive calls within it must be in tail position, i.e. in a position where their value is returned directly from the procedure. So the following procedure is tail-recursive:
(define trp
(lambda (x)
(if (zero? x)
1
(trp (- x 1)))))
because there is nothing to do after the recursive call to trp. The following procedure is not tail-recursive:
(define ntrp
(lambda (x)
(if (zero? x)
1
(/ (ntrp (- x 1)) x))))
because the division must still be done on return from ntrp.
index that takes a list, ls, and an element, item, and returns the zero-based index of the left-most top-level occurrence of item in ls. If item is not in ls, index should return the value #f. Your solution should call a locally defined help procedure that is written in accumulator passing style. Moreover, your solution must be iterative.
Contrast your solution with the procedure mystery given in Problem 1 of Assignment 4, which is, in fact, a recursive definition of index.
Here are some sample inputs:
> (index '(a b c a d) 'a) 0 > (index '(do re me fa so la ti do) 'fa) 3 > (index '(run jump hop skip) 'walk) #f > (index '() 'anything) #f
partition2 that takes a list, ls, and a predicate of one argument, test?, and returns a list containing two sublists. The first sublist in the result should contain those elements of ls for which test? returns true, while the other sublist contains the items for which test? returns false.The order of the elements within the two sublists is unimportant, so we will allow them to be reversed from their original order.
Your solution should call a locally defined APS procedure that maintains two accumulators, one to store the elements that pass the test and the other to store those elements that fail the test.
Here are some examples:
> (partition2 '(1 2 3 4 5 6 7 8 9 10) odd?) ((9 7 5 3 1) (10 8 6 4 2)) > (partition2 '(1 a 2 b 3 c 4 d) symbol?) ((d c b a) (4 3 2 1)) > (partition2 '(1 2 3 4 5 6 7 8 9) (lambda (x) (< x 5))) ((4 3 2 1) (9 8 7 6 5)) > (partition2 '(3 four "five" -5 #f) number?) ((-5 3) (#f "five" four)) > (partition2 '() number?) (() ())
Define the two procedures below which convert between two alternative representations of non-negative integers: Scheme numbers and lists of binary digits. Do not use append or reverse in your solutions, use APS instead.
number->binary takes a non-negative Scheme integer and returns a list of the digits in the binary (base two) expansion of that number. For example:> (number->binary 0) (0) > (number->binary 6) (1 1 0) > (number->binary 13) (1 1 0 1) > (number->binary 42) (1 0 1 0 1 0) > (number->binary 711) (1 0 1 1 0 0 0 1 1 1) > (number->binary 1492) (1 0 1 1 1 0 1 0 1 0 0) > (number->binary 123456790) (1 1 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 0)
binary->number takes a list of the digits in the binary expansion of a number and returns the corresponding non-negative Scheme integer. For example:> (binary->number '(0)) 0 > (binary->number '(1 0)) 2 > (binary->number '(0 0 1)) 1 > (binary->number '(1 0 0)) 4 > (binary->number '(1 1 0 1)) 13 > (binary->number '(1 0 1 0 1 0)) 42 > (binary->number '(1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 0)) 57630
Your file should contain definitions for: exercise-1a, exercise-1b, exercise-1c, exercise-1d, list-swap, diff-lists, multi-subst, index, partition2, binary->number, and number->binary.
When you're all done, review the submission instructions.