Read a Scheme reference and Chapter 8 in the EOPL book.

Write Scheme definitions for the following functions and convert them to CPS. 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 fact (lambda (n) (if (zero? n) 1 (* n (fact (- n 1)))))) (define factcps (lambda (n k) (if (zero? n) (k 1) (factcps (- n 1) (lambda (v) (k (* n v)))))))

- A function dupla that takes two argument, an element and a size,
and creates a list of the requested size:
(dupla 3 0) ==> '() (dupla 3 1) ==> '(3) (dupla 3 2) ==> '(3 3) (dupla 3 5) ==> '(3 3 3 3 3)

- A function index that returns the nth element of a list
(index 3 '(a b c d e f)) ==> 'd

- A function remove that removes the nth element of a list:
(remove 1 '(a b c d e f)) ==> '(a c d e f)

- A function insert that inserts an element at the nth position of a list:
(insert 'a 2 '(1 2 3 4 5 6)) ==> '(1 2 a 3 4 5 6)

- The Fibonacci function.
(fib 0) ==> 0 (fib 1) ==> 1 (fib 2) ==> 1 (fib 8) ==> 21

- The function filter that takes two arguments: a function that
represents a predicate, and a list of numbers. It returns a new list
that consists of all the elements in the argument list that satisfy
the predicate:
(filter even? '(1 2 3 4 5 6)) ==> '(2 4 6) (filter (lambda (x) (> x 8)) '(1 9 2 10 3 11 4 12)) ==> '(9 10 11 12) (filter (lambda (x) (and (> x 8) (< x 10))) '(1 9 2 10 3 11 4 12)) ==> '(9)

When converting to CPS, assume the predicate function has also been converted to CPS. - Write the function map that takes a function and a list of
numbers, and returns a new list that is similar to the argument list
except that the input function has been applied to each element:
(map add1 '(1 2 3)) ==> '(2 3 4) (map (lambda (x) (* x 3)) '(1 2 3)) ==> '(3 6 9)

When converting to CPS, assume the function has also been converted to CPS. - The function powerset that takes a list of numbers that
represents a set and returns the powerset. Use map and mapcps in the solution.
(powerset '()) ==> '(()) (powerset '(1 2 3)) ==> '((), (3), (2), (2,3), (1), (1,3), (1,2), (1,2,3))

- The function merge that merges two sorted lists of numbers into a
larger sorted list.
(merge '() '(1 2 3)) ==> '(1 2 3) (merge '(1 2 3) '()) ==> '(1 2 3) (merge '(1 3 5 7 8 9 10) '(2 4 6)) ==> '(1 2 3 4 5 6 7 8 9 10)

- The function split that takes a list and splits it in two
sublists. The first sublist should contain the elements at odd
indices, and the second sublist should contain the elements at even
indices.
(split '()) ==> '(() ()) (split '(1)) ==> '((1) ()) (split '(1 2 3 4 5 6 7 8 9)) ==> '((1 3 5 7 9) (2 4 6 8)) (split '(1 2 3 4 5 6 7 8 9 10)) ==> '((1 3 5 7 9) (2 4 6 8 10))

- The function mergesort that takes a list of numbers and returns a
sorted version. Use split, splitcps, merge, and mergecps in your solution:
(mergesort '()) ==> '() (mergesort '(8 1 3 9 6 5 7 2 4 10)) ==> '(1 2 3 4 5 6 7 8 9 10)

Page visited times since November 18, 1996.

sabry@cs.uoregon.edu