Principles of Programming Languages — Homework 10

Due by class time Tuesday, October 22

Reading

Study today's code examples from class.

Instructions

Download the three files below, and put them all in the same folder. Use assign10.scm as your starting point for this assignment, which is the version of our interpreter from class today. To use the auto-tester, make sure the line (require "hw10-tester.scm") at the top of assign10.scm is uncommented. To test a function individually, type (test: function_name) at the DrRacket prompt. To see the details of a particular test case, type (test: function_name case_number). Or just type (test:) to test all of your functions at once.

Exercises

  1. Finish adding support for generalized with expressions to the interpreter. To do this, fill in the code in the function m marked ...you...fill...this...in.... The code will be similar to the code for with2 expressions, except that any number (one or more) of variable bindings of the form [var = exp] are allowed. You can use the auto-tester to test your code by typing (test: run).

  2. In class, we wrote the function all?, which takes a one-argument predicate function pred? and a list ls, and returns true if all of the elements of ls satisfy the predicate. (A predicate function is just a function that always returns either true or false.) Write a similar function (any? pred? ls) that returns true if at least one of the elements of ls satisfies the predicate, or false otherwise. For example: 

    (any? (lambda (x) (even? x)) '(1 3 5 6 7))  → #t
(any? (lambda (x) (even? x)) '(1 3 5))  → #f
(any? (lambda (x) (symbol? x)) '(2 b or not 2 b))  → #t
(any? (lambda (x) (number? x)) '(a b c d e))  → #f

  3. Write a function (keep pred? ls) that takes a one-argument predicate function and a list and returns a new list containing just those elements that satisfy the predicate. For example: 

    (keep (lambda (x) (even? x)) '(1 2 3 4 5 6 7 8))  → (2 4 6 8)
(keep (lambda (x) (odd? x)) '(1 2 3 4 5 6 7 8))  → (1 3 5 7)
(keep (lambda (x) (symbol? x)) '(a 1 and a 2 and a 3))  → (a and a and a)
(keep (lambda (x) (not (symbol? x))) '(a 1 and a 2 and a 3))  → (1 2 3)

  4. Complete the definition of times-all in terms of map, by filling in the blank below. This function takes a number n and a list of numbers nums and multiplies each number in the list by n, returning a new list of the results. You do not need to write map itself, since it already exists in Scheme. 
    (define times-all
  (lambda (n nums)
    (map (lambda (x) ______ ) nums)))

(times-all 10 '(1 2 3 4 5))  → (10 20 30 40 50)
(times-all 0 '(9 9 9))  → (0 0 0)
(times-all 2 '(25))  → (50)

  5. Complete the definition of pair-up in terms of map, by filling in the blank below. This function pairs element with each item in ls and returns a list of the pairs, as shown below. 
    (define pair-up
  (lambda (element ls)
    (map (lambda (x) ______ ) ls)))

(pair-up 'apple '(1 2 3 4))  → ((apple 1) (apple 2) (apple 3) (apple 4))
(pair-up 0 '(zero))  → ((0 zero))
(pair-up 'hi '(ho ho ho))  → ((hi ho) (hi ho) (hi ho))

  6. Complete the definition of add-prefix in terms of map, by filling in the blank below. This function takes an element and a list of lists, and returns a new list with the element added to the front of each inner list, as shown below. 
    (define add-prefix
  (lambda (element ls)
    (map (lambda (x) ______ ) ls)))

(add-prefix 0 '((0 0) (0 1) (1 0) (1 1)))  → ((0 0 0) (0 0 1) (0 1 0) (0 1 1))
(add-prefix 1 '((0 0) (0 1) (1 0) (1 1)))  → ((1 0 0) (1 0 1) (1 1 0) (1 1 1))
(add-prefix 'a '((one) (two) (three)))  → ((a one) (a two) (a three))

  7. Complete the definition of swap in terms of map, by filling in the blank below. This function swaps all occurrences of sym1 and sym2 within a list of symbols ls. Hint: use a cond inside the lambda expression. 

    (define swap
  (lambda (sym1 sym2 ls)
    (map (lambda (s) ______ ) ls)))

(swap 'red 'blue '(red fish blue fish red fish))  → (blue fish red fish blue fish)
(swap 'o 'i '(l o l l i p o p))  → (l i l l o p i p)
(swap 'spam 'ham '(green eggs and ham))  → (green eggs and spam)

  8. Write the function (binary n), which generates a list of all binary patterns of length n, in proper counting order. To generate all patterns of length n, first recursively generate all shorter patterns of length n-1, and then add a 0 to the front of each shorter pattern (hint: see add-prefix). In the same way, add a 1 to the front of each shorter pattern, and then combine the results. There is exactly one binary pattern of length 0, namely (), so binary should return this pattern in a list by itself when n is 0.

    (binary 2) → ((0 0) (0 1) (1 0) (1 1))
(binary 3) → ((0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1))
(binary 0) → (())

  9. A rectangular matrix of elements can be represented as a list of lists, where each inner list is one row of the matrix. For example: ((1 2) (3 4)) would be a 2 × 2 matrix, and ((1 2 3) (4 5 6) (7 8 9)) would be a 3 × 3 matrix. Complete the definition of matrix-map in terms of map, by filling in the blank below. This function takes a one-argument function f and a matrix as input, and returns a new matrix consisting of f applied to the elements of matrix. 

    (define matrix-map
  (lambda (f matrix)
    (map (lambda (x) _____ ) matrix)))

(matrix-map (lambda (n) (* n n)) '((1 2) (3 4)))  → ((1 4) (9 16))
(matrix-map (lambda (n) (+ n 1)) '((1 2 3) (4 5 6) (7 8 9)))  → ((2 3 4) (5 6 7) (8 9 10))
(matrix-map (lambda (n) (- n)) '((10 20) (30 40) (50 60) (70 80)))  → ((-10 -20) (-30 -40) (-50 -60) (-70 -80))

Turning in Your Homework