scheme代写: EECS 345: Programming Language Concepts Programming Exercise 2

2018/2/24 Programming Exercise 2

Programming Exercise 2

Submit Assignment

Due Wednesday by 11:59pm Points 50 Submitting a file upload

EECS 345: Programming Language Concepts Programming Exercise 2

Due Wednesday, February 28

For questions 18, write Scheme definitions for the following functions using continuation passing style (CPS) with tail recursion and provde a wrapper function to call the CPS function with the proper return continuation. The continuation argument should be the last argument. For example, if you were asked to write factorial and its CPS counterpart, the answer would be:

 (define factorial-cps
   (lambda (n return)

     (if (zero? n)
         (return 1)

         (factorial-cps (- n 1) (lambda (v) (return (* n v)))))))

 (define factorial
    (lambda (n)

       (factorial-cps n (lambda (v) v))))

For full marks, all recursive calls of your function should use only the first stack frame.

For questions 9 and 10, write the function using call/cc and a helper function. The helper function should be the only recursive function, and it should use “normal” recursion instead of tail recursion.

You do not have to convert simple scheme builtin functions that do not traverse a list (like null?, eq?, list?, number?, car, cons, cdr) to CPS, but all other helper functions you create should be in CPS.

1. insert takes a number and a list of numbers in order and inserts the number in the proper place. > (insert 7 ‘(1 4 5 6 9 10))

(1 4 5 6 7 9 10)

2. merge takes two lists of numbers that are in order and returns a list that contains the combination of both lists in order.

     > (merge '(3 5 6 7 9) '(0 1 2 4 6 8 9 10))
     (0 1 2 3 4 5 6 6 7 8 9 9 10)

https://canvas.case.edu/courses/6937/assignments/119558

1/7

2018/2/24 Programming Exercise 2

removedups takes a list of atoms and removes any atom that is a repeat of the atom that immediately precedes it.
```
    > (removedups '(a a b b b c c a b b))
    (a b c a b)
```

numparens takes a list and returns the number of pairs of parentheses

    > (numparens '(1 2 3))
    1
    > (numparens '(1 () (()) (2 3 (4)))
    6

dup* takes a list and duplicates all contents, including any sublists

    > (dup* '(1 2 (3 4) 5))
    (1 1 2 2 (3 3 4 4) (3 3 4 4) 5 5)

removedups* takes a list, that can contain sublists, and removes any atom that is the repeat of the atom that immediately precedes it in the same sublist.
```
    > (removedups* '(a a (b b b (d d) b ((d) d)) f (f f g)))
    (a (b (d) b ((d) d)) f (f g))
```
mergesort takes a list of numbers and returns a sorted version. If you recall the merge sort algorithm, you use the CPS version of split from lecture to divide the input list into two lists, you recursively call mergesort on each sublist, and then you call merge on the two lists returned by the recursive calls to mergesort.
```
         (mergesort '()) ==> '()
         (mergesort '(8 1 3 9 6 5 7 2 4 10)) ==> '(1 2 3 4 5 6 7 8 9 10)
```

replaceatoms takes two lists. The first list can contain sublists, but the second list is a single list of atoms. The output should be the first list, but each atom of the first list, from left to right, is replaced by the corresponding atom of the second list, until the second list runs out of atoms.

    > (replaceatoms '((a ((b) c d) ((((e) f g) (h i)) j (k l))) m n (o p)) '(z y x w v u t s r q p o n m
    l k j))
    ((z ((y) x w) ((((v) u t) (s r)) q (p o))) n m (l k))
    > (replaceatoms '((a ((b) c d) ((((e) f g) (h i)) j (k l))) m n (o p)) '(z y x w v u))

    ((z ((y) x w) ((((v) u g) (h i)) j (k l))) m n (o p))

Write the following function using call/cc and a single helper function that uses “normal” recursion instead of tail recursion.
suffix takes an atom and a list and returns a list containing all elements that occur after the last occurrence of the atom.
```
    (suffix 'x '(a b c))  ==> (a b c)
    (suffix 'x '(a b x c d x e f)) ==> (e f)
```

https://canvas.case.edu/courses/6937/assignments/119558

2/7

2018/2/24 Programming Exercise 2

10. Write the following function using call/cc and a single helper function that uses “normal” recursion instead of tail recursion.
emptysublists takes an atom and a list containing sublists. The output list should be the same as the input list except that any sublist (including the main list) that contains the given atom should be emptied of all nonlist atoms.

     > (emptysublists 'x '((a b c) (d e x g) (((h i) x) j k ((l m x o)))))
     ((a b c) () (() j k (())))
     > (emptysublists 'x '((a b c) (d e x g) (((h i) x) j k ((l m x o) x))))
     ((a b c) () (() j k ()))
     > (emptysublists 'x '((a b c) (d e x g) x (((h i) x) j k ((l m x o)))))
     ()

Exercise 2

https://canvas.case.edu/courses/6937/assignments/119558

3/7

2018/2/24 Programming Exercise 2

Criteria	Ratings						Pts
insert	5.0 pts Excellent Correct with proper use of CPS, tail recursion and a nice functional style. No unnecessary helper function is used.	4.0 pts Good A good tail recursive, CPS solution with minor errors or unnecessary helper functions.	3.0 pts Reasonable Uses CPS, but the solution is not tailrecursive or the solution not written in a functional manner (uses let, etc.)	2.0 pts Poor A scheme solution that does not show an understanding of continuation passing style.	1.0 pts Minimal Has something in scheme that works for part of the problem.	0.0 pts No Marks The solution does not show an understanding of scheme.	5.0 pts
merge	5.0 pts Excellent Correct with proper use of CPS, tail recursion and a nice functional style. No unnecessary helper function is used.	4.0 pts Good A good tail recursive, CPS solution with minor errors or unnecessary helper functions.	3.0 pts Reasonable Uses CPS, but the solution is not tailrecursive or the solution not written in a functional manner (uses let, etc.)	2.0 pts Poor A scheme solution that does not show an understanding of continuation passing style.	1.0 pts Minimal Has something in scheme that works for part of the problem.	0.0 pts No Marks The solution does not show an understanding of scheme.	5.0 pts
removedups	5.0 pts Excellent Correct with proper use of CPS, tail recursion and a nice functional style. No unnecessary helper function is used.	4.0 pts Good A good tail recursive, CPS solution with minor errors or unnecessary helper functions.	3.0 pts Reasonable Uses CPS, but the solution is not tailrecursive or the solution not written in a functional manner (uses let, etc.)	2.0 pts Poor A scheme solution that does not show an understanding of continuation passing style.	1.0 pts Minimal Has something in scheme that works for part of the problem.	0.0 pts No Marks The solution does not show an understanding of scheme.	5.0 pts

https://canvas.case.edu/courses/6937/assignments/119558

4/7

2018/2/24 Programming Exercise 2

Criteria	Ratings						Pts
numparens	5.0 pts Excellent Correct with proper use of CPS, tail recursion and a nice functional style. No unnecessary helper function is used.	4.0 pts Good A good tail recursive, CPS solution with minor errors or unnecessary helper functions.	3.0 pts Reasonable Uses CPS, but the solution is not tailrecursive or the solution not written in a functional manner (uses let, etc.)	2.0 pts Poor A scheme solution that does not show an understanding of continuation passing style.	1.0 pts Minimal Has something in scheme that works for part of the problem.	0.0 pts No Marks The solution does not show an understanding of scheme.	5.0 pts
dup*	5.0 pts Excellent Correct with proper use of CPS, tail recursion and a nice functional style. No unnecessary helper function is used.	4.0 pts Good A good tail recursive, CPS solution with minor errors or unnecessary helper functions.	3.0 pts Reasonable Uses CPS, but the solution is not tailrecursive or the solution not written in a functional manner (uses let, etc.)	2.0 pts Poor A scheme solution that does not show an understanding of continuation passing style.	1.0 pts Minimal Has something in scheme that works for part of the problem.	0.0 pts No Marks The solution does not show an understanding of scheme.	5.0 pts
removedup*	5.0 pts Excellent Correct with proper use of CPS, tail recursion and a nice functional style. No unnecessary helper function is used.	4.0 pts Good A good tail recursive, CPS solution with minor errors or unnecessary helper functions.	3.0 pts Reasonable Uses CPS, but the solution is not tailrecursive or the solution not written in a functional manner (uses let, etc.)	2.0 pts Poor A scheme solution that does not show an understanding of continuation passing style.	1.0 pts Minimal Has something in scheme that works for part of the problem.	0.0 pts No Marks The solution does not show an understanding of scheme.	5.0 pts

https://canvas.case.edu/courses/6937/assignments/119558

5/7

2018/2/24 Programming Exercise 2

Criteria	Ratings							Pts
mergesort	5.0 pts Excellent Correct with proper use of CPS, tail recursion and a nice functional style. No unnecessary helper function is used.		4.0 pts Good A good tail recursive, CPS solution with minor errors or unnecessary helper functions.	3.0 pts Reasonable Uses CPS, but the solution is not tailrecursive or the solution not written in a functional manner (uses let, etc.)	2.0 pts Poor A scheme solution that does not show an understanding of continuation passing style.	1.0 pts Minimal Has something in scheme that works for part of the problem.	0.0 pts No Marks The solution does not show an understanding of scheme.	5.0 pts
replaceatoms	5.0 pts Excellent Correct with proper use of CPS, tail recursion and a nice functional style. No unnecessary helper function is used.		4.0 pts Good A good tail recursive, CPS solution with minor errors or unnecessary helper functions.	3.0 pts Reasonable Uses CPS, but the solution is not tailrecursive or the solution not written in a functional manner (uses let, etc.)	2.0 pts Poor A scheme solution that does not show an understanding of continuation passing style.	1.0 pts Minimal Has something in scheme that works for part of the problem.	0.0 pts No Marks The solution does not show an understanding of scheme.	5.0 pts
suffix	5.0 pts Excellent Correct, proper use of call/cc with good functional style. No unnecessary helper functions.	4.0 pts Good Correct with good functional style but either uses call/cc in an inefficient manner. No unnecessary helper functions.		3.0 pts Reasonable Attempts to use call/cc in a recursive solution, but does not use call/cc correctly or has unnecessary helper functions.	2.0 pts Poor A scheme solution that does not show an understanding of call/cc.	1.0 pts Minimal Has something in scheme that works for part of the problem.	0.0 pts No Marks The solution does not show an understanding of scheme.	5.0 pts

https://canvas.case.edu/courses/6937/assignments/119558

6/7

2018/2/24 Programming Exercise 2

Criteria	Ratings						Pts
emptysublists	5.0 pts Excellent Correct, proper use of call/cc with good functional style. No unnecessary helper functions.	4.0 pts Good Correct with good functional style but either uses call/cc in an inefficient manner. No unnecessary helper functions.	3.0 pts Reasonable Attempts to use call/cc in a recursive solution, but does not use call/cc correctly or has unnecessary helper functions.	2.0 pts Poor A scheme solution that does not show an understanding of call/cc.	1.0 pts Minimal Has something in scheme that works for part of the problem.	0.0 pts No Marks The solution does not show an understanding of scheme.	5.0 pts
Total Points: 50.0

https://canvas.case.edu/courses/6937/assignments/119558

7/7

Related Posts