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 1­8, 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 built­in 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

  1. 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)
    
  2. numparens takes a list and returns the number of pairs of parentheses
        > (numparens '(1 2 3))
        1
        > (numparens '(1 () (()) (2 3 (4)))
        6
    
  3. 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)
    
  4. 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))
    
  5. 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)
    
  6. 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))
    
  7. 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 non­list 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 tail­recursive 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 tail­recursive 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 tail­recursive 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 tail­recursive 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 tail­recursive 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 tail­recursive 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 tail­recursive 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 tail­recursive 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