midterm代考：

UNIVERSITY OF SAN FRANCISCO

CS486 — SICP — SUMMER ‘21

MIDTERM

INSTRUCTIONS

1. Make a copy of this document and place your answers in that copy.
2. Where programs are required, write them in the Source §2 language. A description of the list processing functions of Source §2 can also be found in the appendix at the end of this document.
3. Feel free to write and test your functions in the SICP playground (or the public Source Academy playground) and then cut-and-paste your code into your copy of this doc.
4. As a reminder, almost all the source code definitions of Source Academy functions can be seen by evaluating the function’s name within the SICP / Source Academy playground.
5. For multiple choice questions, please underline your selected answer.
6. Partial credit may be given for correct parts of answers. You can maximize the chance for partial credit by putting comments in your code explaining your intent!
7. Submit your answers via email to mark.friedman@usfca.edu.  Your submission should be a link to, or attachment of, your copy of this edited file. Please make sure that you have given me permission to view your file.
8. Your submission is due by 11:59 pm PDT, July 1^st 2021.

Section A:  List Notation  [9 points]

Note: Please do not use Source Academy or any other interpreter for the 3 problems in this section! You may look at the descriptions of the list functions in the appendix.

(Problem 1)  [3 points]

What is the result of evaluating the following Source program in list notation?

const xs = list(6, 7, 8);

pair(xs, tail(xs));

(Problem 2)  [3 points]

What is the result of evaluating the following Source program in list notation?

const xs = list(3, 4, 5);

accumulate((x, ys) => append(list(x), list(ys)), null, xs);

(Problem 3)  [3 points]

What is the result of evaluating the following Source program in list notation?

function fun(xs) {

    return is_null(xs)

        ? null

        : pair(map(x => head(xs), enum_list(1, head(xs))),

               fun(tail(xs)) );

}

fun(list(2, 4, 3));

Section B:  Box-and-Pointer Diagrams  [8 points]

For each of the following box-and-pointer diagrams, write a Source program such that at the end of the evaluation of your program, the name result will have the value as shown in the diagram. You must not use any ellipsis (…) in your program.

For example, the following program:

       const result = list(2, 5);   

results in the following diagram:

(Problem 4)  [4 points]

// Code here

const result = build_list(1000, (i)=>pair(i+1,null));

(Problem 5)  [4 points]

// Code here

const result = accumulate(list, null, build_list(1000, i=>i+1));

Section C:  Active Lists  [13 points]

An active list is a function that takes an integer number and returns an empty list or a list of length 1. It can be used as an alternative representation of a list, where it takes as argument an element’s position in the list, and returns that element in a list of length 1. Note that the first element in a list is at position 0.

Assume the function make_active_list takes a list as its argument and returns an active list that represents the input list.

Example:

const act_list = make_active_list(list(8, 3, 5));

act_list(-1); // returns null

act_list(0);  // returns list(8)

act_list(1);  // returns list(3)

act_list(2);  // returns list(5)

act_list(3);  // returns null

Note that when the argument passed to act_list is negative, or is greater than or equal to the length of the input list to make_active_list, the function act_list should return an empty list.

One possible definition for make_active_list is:

function make_active_list(L) {

    const len = length(L);

    return pos => (pos < 0 || pos >= len)

        ? null

        : list(list_ref(L, pos));

}

(Problem 6)  [3 points]

Write the function act_length that takes as argument an active list as, and returns the length of the active list.

Example:

const as = make_active_list(list());

const bs = make_active_list(list(8, 3, 5));

act_length(as);  // returns 0

act_length(bs);  // returns 3

function act_length(as) {

    return helper(as, 0);

}

function helper(as, i){

    if(is_null(as(i))) {

        return i;

    } else {

        return helper(as, i+1);

    }

}

(Problem 7)  [5 points]

Write the function act_append that takes as arguments two active lists, as and bs, and returns an active list that results from appending bs to as.

Example:

const as = make_active_list(list(11, 22));

const bs = make_active_list(list(33, 44, 55));

const cs = act_append(as, bs);

act_length(cs);  // returns 5

list(cs(0), cs(1), cs(2), cs(3), cs(4)); 

    // returns list(list(11), list(22), list(33), list(44), list(55))

Your implementation may make use of the act_length function from the preceding task.

function act_append(as, bs) {

    const lst1 = build_list(act_length(as), i => as(i));

    const lst2 = build_list(act_length(bs), i => bs(i));

    return make_active_list(append(lst1, lst2));

}

(Problem 8)  [5 points]

Write the function sum that takes as arguments an active list as and a function f, and returns the sum of f(x) for every element x of the input active list. We assume that all elements of the input active list are numbers.

Example:

const as = make_active_list(list(1, 2, 3));

sum(as, x => x * x);  // returns 14  (1*1 + 2*2 + 3*3)

Your implementation may use the act_length function, and must make use of at least one of the three functions: accumulate, map, filter, in a meaningful way, to produce the result.

function sum(as, f) {

    const lst = build_list(act_length(as), i => as(i));

    const new_lst = map(x => f(head(x)), lst);

    return accumulate((x,y) => x + y, 0, new_lst);

}

Section D:  Pair-Trees  [30 points]

We introduce the following notion:

A pair-tree is a number or a pair whose head is a pair-tree and whose tail is a pair-tree. So, for example, each of the following statements would create a pair-tree:

2;

pair(1, 2);

pair(5, pair(4, 3));

pair(pair(8, 6), 4);

pair(pair(1, 2), pair(3, pair(4, 5)));

(Problem 9)  [2 points]

A tree of numbers is a list whose elements are numbers or trees of numbers.

Which of the following statements is correct?

(Problem 10)  [2 points]

As before, a tree of numbers is a list whose elements are numbers or trees of numbers.

Which of the following statements is correct?

(Problem 11)  [5 points]

Write the function has(t, x) that returns true if pair-tree t contains the number x, otherwise it returns false.

Examples:

const t1 = 8;

has(t1, 4);  // returns false

has(t1, 8);  // returns true

const t2 = pair(pair(1, 2), pair(3, pair(4, 5)));

has(t2, 4);  // returns true

has(t2, 8);  // returns false

function has(t, x) {

    if (is_number(t)) {

        return t === x;

    } else {

        return has(head(t), x) || has(tail(t), x);

    }

}

(Problem 12)  [6 points]

A path is a list of functions that are successively applied to a pair-tree to reach a subtree. For example, the path list(head, tail, tail) applied to pair(pair(1, pair(2, 5)), 3) gives you 5. Write the function apply(p, t) that takes a path p and a pair-tree t as arguments and returns the subtree of t that p refers to. You can assume that the given path p is a valid path within pair-tree t.

Examples:

const t1 = 8;

apply(null, t1);  // returns 8

const t2 = pair(pair(1, 2), pair(3, pair(4, 5)));

apply( list(tail, tail, head), t2 );  // returns 4

apply( list(head), t2 );  // returns pair(1, 2)

function apply(p, t) {

    if(is_null(p)) {

        return t;

    } else {

        const new_t = head(p)(t);

        const new_p = build_list(length(p)-1, i => list_ref(p, i+1));

        return apply(new_p, new_t);

    }

}

(Problem 13)  [7 points]

Assume that the number 8 (lucky number) appears exactly once in a given pair-tree. Write the function find_8(t) that takes the pair-tree as an argument and returns the unique path to 8, i.e. apply(find_8(t), t) should return 8 if t contains exactly one 8.

Examples:

const t1 = 8;

find_8(t1);  // returns null

const t2 = pair(pair(1, 2), pair(3, pair(8, 5)));

find_8(t2);  // returns list(tail, tail, head)

function find_8(t) {

    return head(filter(p => apply(p, t) === 8, helper(t, list())));

}

function helper(t, p) {

    if (is_number(t)) {

        return list(p);

    } else {

        return append(helper(head(t), append(p, list(head))), helper(tail(t), append(p, list(tail))));

    }

}

(Problem 14)  [8 points]

Write the function find_all_8(t) that takes a pair-tree t as an argument and returns the list of all paths that lead to the number 8. The order of the paths in the result list does not matter. Note that the number 8 might appear any number of times in the pair-tree, including not at all.

Examples:

const t1 = 8;

find_all_8(t1);  // returns list(null)

const t2 = pair(pair(1, 2), pair(3, pair(4, 5)));

find_all_8(t2);  // returns null

const t3 = pair(8, pair(8, pair(8, 2)));

find_all_8(t3);

// returns list( list(head), list(tail, head), list(tail, tail, head) )

function helper(t, p) {

    if (is_number(t)) {

        return list(p);

    } else {

        return append(helper(head(t), append(p, list(head))), helper(tail(t), append(p, list(tail))));

    }

}

function find_all_8(t) {

    return filter(p => apply(p, t) === 8, helper(t, list()));

}

——   END OF QUESTIONS   ———

Appendix

List Support

The following list processing functions are supported:

• pair(x, y): Makes a pair from x and y.
• is_pair(x): Returns true if x is a pair and false otherwise.
• head(x): Returns the head (first component) of the pair x.
• tail(x): Returns the tail (second component) of the pair x.
• is_null(xs): Returns true if xs is the empty list, and false otherwise.
• is_list(x): Returns true if x is a list as defined in the lectures, and false otherwise. Iterative process; time: O(n), space: O(1), where n is the length of the chain of tail operations that can be applied to x.
• list(x1, x2,…, xn): Returns a list with n elements. The first element is x1, the second x2, etc. Iterative process; time: O(n), space: O(n), since the constructed list data structure consists of n pairs, each of which takes up a constant amount of space.
• length(xs): Returns the length of the list xs. Iterative process; time: O(n), space: O(1), where n is the length of xs.
• map(f, xs): Returns a list that results from list xs by element-wise application of f. Recursive process; time: O(n), space: O(n), where n is the length of xs.
• build_list(n, f): Makes a list with n elements by applying the unary function f to the numbers 0 to n – 1. Recursive process; time: O(n), space: O(n).
• for_each(f, xs): Applies f to every element of the list xs, and then returns true. Iterative process; time: O(n), space: O(1), where n is the length of xs.
• list_to_string(xs): Returns a string that represents list xs using the text-based box-and-pointer notation […].
• reverse(xs): Returns list xs in reverse order. Iterative process; time: O(n), space: O(n), where n is the length of xs. The process is iterative, but consumes space O(n) because of the result list.
• append(xs, ys): Returns a list that results from appending the list ys to the list xs. Recursive process; time: O(n), space: O(n), where n is the length of xs.
• member(x, xs): Returns first postfix sublist whose head is identical to x (===); returns null if the element does not occur in the list. Iterative process; time: O(n), space: O(1), where n is the length of xs.
• remove(x, xs): Returns a list that results from xs by removing the first item from xs that is identical (===) to x. Recursive process; time: O(n), space: O(n), where n is the length of xs.
• remove_all(x, xs): Returns a list that results from xs by removing all items from xs that are identical (===) to x. Recursive process; time: O(n), space: O(n), where n is the length of xs.
• filter(pred, xs): Returns a list that contains only those elements for which the one argument function pred returns true. Recursive process; time: O(n), space: O(n), where n is the length of xs.
• enum_list(start, end): Returns a list that enumerates numbers starting from start using a step size of 1, until the number exceeds (>) end. Recursive process; time: O(n), space: O(n), where n is the length of xs. For example, enum_list(2, 5) returns the list list(2, 3, 4, 5).
• list_ref(xs, n): Returns the element of list xs at position n, where the first element has index 0. Iterative process; time: O(n), space: O(1), where n is the length of xs.
• accumulate(op, initial, xs): Applies binary function op to the elements of xs from right-to-left order, first applying op to the last element and the value initial, resulting in r₁, then to the second-last element and r₁, resulting in r₂, etc, and finally to the first element and r_n−1, where n is the length of the list. Thus, accumulate(op, zero, list(1,2,3)) results in op(1, op(2, op(3, zero))). Recursive process; time: O(n), space: O(n), where n is the length of xs, assuming op takes constant time.

(Scratch Paper)

(Scratch Paper)

http://cs486.cs.usfca.edu/