• Due: 6pm Friday 29 September
  • Notes:
    • This pset has lots Racket programming. Start soon.
    • This pset contains two solo problems (Problems 1 and 2).
    • You should be able to do all of the problems as of now (you have already seen all the material you need to do them.)
    • The problems needn’t be done in order. Feel free to jump around.
    • Although the official deadline is 6pm Friday 29 September, PS2 is unlikely to be graded until the end of this day, so there will be some slack.
  • Submission:
    • In your yourFullName CS251 Spring 2017 Folder, create a Google Doc named yourFullName CS251 PS3.
    • At the top of your yourFullName CS251 PS3 doc, include your name, problem set number, date of submission, and an approximation of how long each problem part took.
    • For all parts of all problems, include all answers (derivations, code, etc.) in your PS3 google doc. Please format all code and all evaluation derivations so that they’re easy to read. Format small-step derivations and Racket code using a fixed-width font, like Courier New or Consolas. You can use a small font size if that helps.
    • For Problem 1 (Solo Problem: Alternative If Semantics), include your explanation and your small-step derivation in your PS3 doc.
    • For Problem 2 (Solo Problem: Recursive Numeric Functions)
      • Be sure that all function definitions in yourAccountName-ps3-solo-functions.rkt also appear in your PS3 Doc (so that I can comment on them)
      • Drop a copy of your yourAccountName-ps3-solo-functions.rkt in your ~/cs251/drop/ps03 drop folder on cs.wellesley.edu.
    • For Problem 3 (Box-and-pointer diagrams), include all expressions in your PS3 doc.
    • For Problems 4 and 5 (Recursive Racket List Functions):
      • Be sure that all function definitions in yourAccountName-ps3-list-functions.rkt also appear in your PS3 Doc (so that I can comment on them)
      • Drop a copy of your yourAccountName-ps3-list-functions.rkt in your ~/cs251/drop/ps03 drop folder on cs.wellesley.edu.

1. Solo Problem: Alternative If Semantics (5 points)

This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.

The small-step reduction rules for if expressions in Racket are

  • (if V_test E_then E_else) ⇒ E_then, if V_test is a value that is not #f [if nonfalse]
  • (if #f E_then E_else) ⇒ E_else [if false]

Lois Reasoner thinks that the reduction of if expressions should be changed to:

  • (if V_test V_then V_else) ⇒ V_then, if V_test is a value that is not #f [if nonfalse Lois]
  • (if #f V_then V_else) ⇒ V_else [if false Lois]

These differ from the actual rules by requiring that all three subexpressions e_test, e_then, and e_false of (if e_test e_then e_false) are first evaluated to values before the if expression can be simplified.

Explain that Lois’s alternative semantics for if are a bad idea. In particular, consider the sum-between function from PS2:

(define sum-between
  (lambda (lo hi)
    (if (> lo hi)
        0
        (+ lo (sum-between (+ lo 1) hi)))))

Use Lois’s semantics for if in a small-step semantics derivation for the evaluation of (sum-between 2 3) to explain what happens. You needn’t show every step, but at the very least should show lines in which the redex is λ_sb applied to two values.

2. Solo Problem: Recursive Numeric Functions (20 points)

This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.

This problem involves the following recursive Racket function g:

(define g
  (lambda (n)
    (if (<= n 2)
        n
        (+ n
           (g (thirdish n))
           (g (half n))))))

where thirdish and half are defined as

(define thirdish
  (λ (int) (* (remainder int 3) (quotient int 3))))

(define half
  (λ (int) (quotient int 2)))

half returns the integer quotient of a number by 2 (e.g. (half 10) and (half 11) are both 5) and thirdish returns the product of the integer quotient of the number by 3 and its remainder by three. For example:

> (map (λ (n) (cons n (thirdish n))) (range 12))
'((0 . 0) (1 . 0) (2 . 0) (3 . 0) (4 . 1) (5 . 2) (6 . 0) (7 . 2) (8 . 4) (9 . 0) (10 . 3) (11 . 6))

  1. (8 points) Use small-step semantics to derive the evaluation of (g 11). To keep the size of your derivation manageable, use the same conventions used in small-step derivations in PS2 Problem 4 Sum Fun. In particular:

    • Use the notation λ_g as an abbreviation for the lambda expression

      (lambda (n)
  (if (<= n 2)
      n
      (+ n
         (g (thirdish n))
         (g (half n)))))

    • Use ⇒* to show only the steps of the derivation in which the redex is a call to λ_g.

    • Treat half and thirdish as black boxes: do not show any redexes involving calls to these functions, only the results of such calls.

  2. (1 point) How many times is g called in the evaluation of (g 11)? (Be sure to include all base case calls, such as (g 0), (g 1), and (g 2).)

  3. (1 point) What is the maximum stack depth (measured in terms of maximum number of nested + operations) in the evaluation of (g 11)?

  4. (5 points) Define a recursive Racket function named num-g-calls that takes a single integer argument n and returns the number of times that the function g is called in the evaluation of (g n). Notes:

    • Define the num-g-calls function in a new file named yourAccountName-ps3-solo-functions.rkt that you create in Dr. Racket. This file should also include the definitions of half and thirdish from above.

    • (num-g-calls 11) should return your answer from part b.

    • You should only use Racket language features you used in PS2 or learned in the lectures on Racket expressions and declarations and Racket functions

    • Do not attempt to modify the definition of g so that it counts the number of times g is called by changing the contents of a global variable.

    • Instead, write a new recursive function num-g-calls that is very much like g, but rather than returning the number calculated by g instead returns the number of calls to g made in that calculation. Your definition should use the helper functions half and thirdish.

    • Test your function using this expression, and include its result in your writeup:

      (map (λ (n) (cons n (num-g-calls n))) (range 100))

  5. (5 points) Define a recursive Racket function named max-depth-g that takes a single integer argument n and returns the maximum stack depth (measured in terms of maximum number of nested + operations) in the evaluation of (g n). Notes:

    • Add the max-depth-g function to your yourAccountName-ps3-solo-functions.rkt file.

    • (max-depth-g 11) should return your answer from part c.

    • You should only use Racket language features you used in PS2 or learned in the lectures on Racket expressions and declarations and Racket functions

    • The max function is especially useful here.

    • Do not attempt to modify the definition of g so that it determines the stack depth by changing the contents of a global variable.

    • Instead, write a new recursive function max-depth-g that is very much like g, but rather than returning the number calculated by g instead returns the maximum stack depth in that calculation. Your definition should use the helper functions half and thirdish.

    • Test your function using this expression, and include its result in your writeup:

      (map (λ (n) (cons n (max-depth-g n))) (range 100))

3. Box-and-pointer diagrams (18 points)

Consider the following box-and-pointer diagram for the list structure named a:

box-and-pointer diagram

  1. (9 points) For each of the numbers 1 through 6, write a Racket expression that uses car and cdr to extract that number from a.

  2. (4 points) Write down the printed representation for a (i.e., what would be returned by the Racket interpreter for evaluating a?).

  3. (5 points) Write a Racket definition of the form (define aexpr), where expr is an expression using cons, list,
    and the numbers 1 through 6 (but no quote or quotation) to create the structure depicted in the diagram. (Once you have defined a in this way, you may test your expressions from part (a).)

4. Recursive Racket List Functions, Part 1 (20 points)

In PS2, you wrote some recursive Racket functions that manipulate numbers. Here, you will continue to practice defining recursive Racket functions, but now you focus on functions that manipulate Racket lists. Unlike list and array data structures in many other languages, which are most naturally processed with loops, the linked-list recursively-defined nature of Racket lists make them natural candidates for recursive processing.

For each of the following Racket function specifications, write and test a recursive function that satisfies that specification. In all of your definitions, you should use the following recursive problem solving strategy:

  • For which argument(s) is the function so simple that the answer can be returned immediately? This is the base case.

  • For the other case(s) (known as the general case(s) or recursive case(s)), use divide/conquer/glue:

    • divide: make one or more subproblems that are smaller instances of the given problem;

    • conquer: assume that the recursive function you’re defining simply works and returns the correct answer on all of the smaller problems.

    • glue: combine the result(s) of the recursive function call(s) with information in the original problem to create the correct result for the whole problem.

Notes:

  • For this problem, you should use Dr. Racket to create a single file named yourAccountName-ps3-list-functions.rkt that contains all the functions (including helper functions) that you define for this problem.

  • In your definitions, unless otherwise instructed, you should not introduce any recursive helper functions. (But you can define nonrecursive helper functions).

  • If the following error message pops up during the testing of one of your functions, it mostly likely means that you have an infinite recursion that doesn’t reach its base case and runs out of memory due to a stack depth that cannot fit into available memory.

box-and-pointer-diagram

  1. (4 points) Define a function map-remainder that takes two arguments (an integer divisor and a list ints of integers) and returns an integer list the same length as ints in which every element is remainder of dividing the corresponding element of ints by divisor.

     > (map-remainder 2 (list 16 23 42 57 64 100))
 '(0 1 0 1 0 0)
 > (map-remainder 3 (list 16 23 42 57 64 100))
 '(1 2 0 0 1 1)
 > (map-remainder 5 (list 16 23 42 57 64 100))
 '(1 3 2 2 4 0)
 > (map-remainder 17 (list 16 23 42 57 64 100))
 '(16 6 8 6 13 15)

  2. (4 points) Define a function filter-divisible-by that takes two arguments (an integer divisor and a list ints of integers) and returns a new integer list containing all the elements of ints that are divisible by divisor. Use divisible-by? from above to determine divisibility.

     > (filter-divisible-by 2 (list 16 23 42 57 64 100))
 '(16 42 64 100)
 > (filter-divisible-by 3 (list 16 23 42 57 64 100))
 '(42 57)
 > (filter-divisible-by 4 (list 16 23 42 57 64 100))
 '(16 64 100)
 > (filter-divisible-by 5 (list 16 23 42 57 64 100))
 '(100)
 > (filter-divisible-by 17 (list 16 23 42 57 64 100))
 '()

    Use the following helper function, which is helpful in this problem and some of the following ones.

    (define divisible-by?
  (lambda (num divisor)
    (= (remainder num divisor) 0)))

  3. (4 points) Define a function contains-multiple? that takes an integer m and a list of integers ns that returns #t if m evenly divides at least one element of the integer list ns; otherwise it returns #f. Use divisible-by? from above to determine divisibility.

     > (contains-multiple? 5 (list 8 10 14))
 #t
 > (contains-multiple? 3 (list 8 10 14))
 #f
 > (contains-multiple? 5 null)
 #f

  4. (4 points) Write a function all-contain-multiple? that takes an integer n and a list of lists of integers nss (pronounced “enziz”) and returns #t if each list of integers in nss contains at least one integer that is a multiple of n; otherwise it returns #f. Use contains-multiple? in your definition of all-contain-multiple?.

     > (all-contain-multiple? 5 (list (list 17 10 2) (list 25) (list 3 8 5)))
 #t
 > (all-contain-multiple? 2 (list (list 17 10 2) (list 25) (list 3 8 5)))
 #f
 > (all-contain-multiple? 3 null)
 #t ; said to be "vacuously true"; there is no counterexample!

  5. (4 points) Define a function map-cons that takes any value x and an n-element list ys and returns an n-element list of all pairs '(x . y) where y ranges over the elements of ys. The pair '(x . y) should have the same relative position in the resulting list as y has in ys.

     > (map-cons 17 (list 8 5 42 23))
 '((17 . 8) (17 . 5) (17 . 42) (17 . 23))
 > (map-cons 3 (list (list 1 6 2) (list 4 5) (list) (list 9 6 8 7)))
 '((3 1 6 2) (3 4 5) (3) (3 9 6 8 7))
 > (map-cons 42 null)
 '()

5. Recursive Racket List Functions, Part 2 (37 points)

These are more challenging definitions of recursive functions than in Part 1. For this reason, for each of these functions you are required to explicilty show the following steps of the divide/conquer/glue problem solving strategy:

  1. For the example input list L specified in each problem:

    i. Show the result of calling the function on L;

    ii. Show the result of calling the function on (rest L);

    iii. Write an expression that combines the value of (first L) with the result in (ii) to yield the result in (i).

    iv. Generalize the expression in (iii) into an expression for the general case of the recursive function definition.

  2. Explain what the recursive function should return when called on the empty list. If you’re not sure, consider the case of calling the function on a singleton list, and reason from the combiner in the general case what the result for the empty list should be. Give a general expression for the base case.

  3. Combine the results of parts 1 and 2 to form your final recursive function definition.

Example:

Define a function snoc that takes an element x and a length- n list of elements ys and returns a length n+1 list in which x occurs after all the elements in ys.

    > (snoc 17 (list 7 2 5))
    '(7 2 5 17)

  1. Suppose L is '(1 2 3) in the function call (snoc 4 '(1 2 3))

    i. (snoc 4 '(1 2 3)) should return '(1 2 3 4).

    ii. (rest L) is '(2 3), and (snoc 4 '(2 3)) should return '(2 3 4).

    iii. (first L) is 1. The way to combine 1 and '(2 3 4) to yield '(1 2 3 4) is (cons 1 '(2 3 4)).

    iv. For (snoc x ys), the generalization of (iii) is the general case (cons (first ys) (snoc x (rest ys))).

  2. (snoc 17 '()) should return '(17). In general (snoc x '()) should return (list x) (which is syntactic sugar for (cons x '()).

  3. The definition of snoc is:

    (define (snoc x ys)
  (if (null? ys)
      (list x)
      (cons (first ys) (snoc x (rest ys)))))

Your Problems

  1. (7 points) Define a function my-cartesian-product that takes two lists xs and ys and returns a list of all pairs '(x . y) where x ranges over the elements of xs and y ranges over the elements of ys. The pairs should be sorted first by the x entry (relative to the order in xs) and then by the y entry (relative to the order in ys).

     > (my-cartesian-product (list 1 2) (list "a" "b" "c")) ; yes, Racket has string values
 '((1 . "a") (1 . "b") (1 . "c") (2 . "a") (2 . "b") (2 . "c"))
 > (my-cartesian-product (list 2 1) (list "a" "b" "c"))
 '((2 . "a") (2 . "b") (2 . "c") (1 . "a") (1 . "b") (1 . "c"))
 > (my-cartesian-product (list "c" "b" "a") (list 2 1))
 '(("c" . 2) ("c" . 1) ("b" . 2) ("b" . 1) ("a" . 2) ("a" . 1))
 > (my-cartesian-product (list "a" "b") (list 2 1))
 '(("a" . 2) ("a" . 1) ("b" . 2) ("b" . 1))
 > (my-cartesian-product (list 1) (list "a"))
 '((1 . "a"))
 > (my-cartesian-product null (list "a" "b" "c"))
 '()

    Notes:

    • We ask you to name your function my-cartesian-product because Racket already provides a similar (but slightly different) cartesian-product function (which you cannot use, of course).
    • Use the map-cons function from above as a helper function in your cartesian-product definition.
    • Racket’s append function is helpful here.
    • For your example list L, use ("a" "b" "c") in the call (my-cartesian-product '("a" "b" "c") '(3 4)).

  2. (8 points) Assume that the elements of a list are indexed starting with 0. Define a function alts that takes a list xs and returns a two-element list of lists, the first of which has all the even-indexed elements (in the same relative order as in xs) and the second of which has all the odd-indexed elements (in the same relative order as in xs).

     > (alts (list 7 5 4 6 9 2 8 3))
 '((7 4 9 8) (5 6 2 3))
 > (alts (list 5 4 6 9 2 8 3))
 '((5 6 2 3) (4 9 8))
 > (alts (list 4 6 9 2 8 3))
 '((4 9 8) (6 2 3))
 > (alts (list 3))
 '((3) ())
 > (alts null)
 '(() ())

    Notes:

    • As in all other problems, You should use the divide/conquer/glue strategy here. In particular, the solution for (alts elts) should be expressed in terms of combining (first elts) with (alts (rest elts)).

    • You should not treat even-length and odd-length cases differently, nor should you handle the singleton list specially.

    • You should use Racket’s let construct for declaring local names is helpful to avoiding unnecessarily recalculating the recursive call.
    • For your example list L, use (1 2 3 4 5 6) in the call (alts '(1 2 3 4 5 6))

  3. (10 points) Define a function inserts that takes a value x and an n-element list ys and returns an n+1-element list of lists showing all ways to insert a single copy of x into ys.

     > (inserts 3 (list 5 7 1))
 '((3 5 7 1) (5 3 7 1) (5 7 3 1) (5 7 1 3))
 > (inserts 3 (list 7 1))
 '((3 7 1) (7 3 1) ( 7 1 3))
 > (inserts 3 (list 1))
 '((3 1) (1 3))
 > (inserts 3 null)
 '((3))
 > (inserts 3 (list 5 3 1))
 '((3 5 3 1) (5 3 3 1) (5 3 3 1) (5 3 1 3))

    Notes:

    • The map-cons function from above is useful here.
    • Think very carefully about the base case and the combination function for the recursive case.
    • For your example list L, use (2 3 4) in the call (inserts 1 '(2 3 4))

  4. (12 points) Define a function my-permutations that takes as its single argument a list xs of distinct elements (i.e., no duplicates) and returns a list of all the permutations of the elements of xs. The order of the permutations does not matter.

     > (my-permutations null)
 '(())
 > (my-permutations (list 4))
 '((4))
 > (my-permutations (list 3 4))
 '((3 4) (4 3)) ; order doesn't matter 
 > (my-permutations (list 2 3 4))
 '((2 3 4) (3 2 4) (3 4 2) (2 4 3) (4 2 3) (4 3 2))
 > (my-permutations (list 1 2 3 4))
 '((1 2 3 4) (2 1 3 4) (2 3 1 4) (2 3 4 1) 
   (1 3 2 4) (3 1 2 4) (3 2 1 4) (3 2 4 1) 
   (1 3 4 2) (3 1 4 2) (3 4 1 2) (3 4 2 1)
   (1 2 4 3) (2 1 4 3) (2 4 1 3) (2 4 3 1) 
   (1 4 2 3) (4 1 2 3) (4 2 1 3) (4 2 3 1) 
   (1 4 3 2) (4 1 3 2) (4 3 1 2) (4 3 2 1))

    Notes:

    • We ask you to name your function my-permutations because Racket already provides the same function named permutations (which you cannot use, of course).
    • In this problem, you are allowed to use one or more recursive helper functions.
    • Although the specification allows the permuted elements to be listed in any order, the above examples show an order that works particularly well with the divide/conquer/glue strategy. In particular, study the above examples carefully to understand (1) the recursive nature of my-permutations and (2) why the inserts function from above is helpful to use when defining my-permutations.
    • In the example (my-permutations (list 1 2 3 4)), the 24 results would normally be printed by Racket in 24 separate lines, but here they have been formatted to strongly sugggest a particular solution strategy.
    • For your example list L, use (1 2 3) in the call (my-permutations '(1 2 3)).

Extra Credit: Permutations in the Presence of Duplicates (15 points)

This problem is optional. You should only attempt it after completing all the other problems.

Define a version of the my-permutations function named my-permutations-dup that correctly handles lists with duplicate elements. That is, each permutation of such a list should only be listed once in the result. You should not generate duplicate permutations and then remove them; rather, you should just not generate any duplicates to begin with. As before, the order of the permutations does not matter.

    > (my-permutations-dup (list 2 1 2))
    '((1 2 2) (2 1 2) (2 2 1)) ; order doesn't matter 
    > (my-permutations-dup (list 1 2 1 2 2))
    '((1 1 2 2 2) (1 2 1 2 2) (1 2 2 1 2) (1 2 2 2 1)
      (2 1 1 2 2) (2 1 2 1 2) (2 1 2 2 1) 
      (2 2 1 1 2) (2 2 1 2 1) (2 2 2 1 1)) ; order doesn't matter