Question 1. (7 points) Suppose we enter the following top-level definitions into a Scheme interpreter.

(define x '(1 2 3))

(define y '(10 20))

(define z '((a b) ((c d) e) (f g h)))

What is the value of each of the following expressions, given that the above definitions are in effect? If evaluating the expression produces an error, explain what is wrong.

1. (append x y)     '(1 2 3 10 20)
2. (cons x y)       '((1 2 3) 10 20)
3. (list x y)       '((1 2 3) (10 20))
4. (car (cdr y))    20
5. (car (car y))    Error
6. (cadr z)         '((c d) e)
7. (map length z)   '(2 2 3)

Question 2. (3 points) Suppose we have a damaged Scheme interpreter that does not implement the if conditional expression. One of your colleagues, A. Hacker, proposes that if can be replaced by a regular function as follows:

(define (new-if x y z)

(cond (x y)

(else z)))

Hacker claims that this works, and demonstrates it as follows:

(new-if (= 1 0) 4 5) => 5

(new-if (= 1 1) 4 5) => 4

The question is, does function new-if work exactly the same as the regular built-in Scheme if? If so, explain why it is the same. If not, give an example showing how if and new-if can produce different results.

SOLUTION:

The answer is NO. This is because "if" in general does not evaluate all its arguments.

new-if as written above will evaluate all its arguments when it is called.

An example of a place this would not work is :

(new-if (= 1 0) (/ 1 0) (+ 2 3))

This would crash because new-if tries to evaluate (/1 0). "if" would not evaluate this argument because the boolean condition is false.

A more meaningful example which we use during checking null pointers and zeros is :

( new-if !(= x 0) (/ 1 x) 0)

Question 3. (5 points) Give the definition of a recursive Scheme function sum-pos that returns the sum of all of the positive numbers in its argument. The argument is a list containing integers, but it may contain sub-lists. Your function should recursively add up the positive integers in any sublists and include these sums in the total. Examples:

(sum-pos ?(4 -3 2 0)) => 6

(sum-pos ?(((-1 2) 3 0 -4) (-5 6)) => 11

You should assume that all of the elements in the list are integers; in other words, you do not need to check the types of list elements (other than sublists, of course).

SOLUTION:
(define (sum-pos lst)
            (if (null? lst) 0
                                (if (pair? (car lst) (+ (sum-pos (car lst)) (sum-pos (cdr lst))
                                                              (+ (car lst) (sum-pos (cdr lst)))
                                )
              )
)

Question 4. (6 points) Here is a non-tail-recursive definition of a function that reverses its list argument.

(define (revr x)

(if (null? x)

()

(append (revr (cdr x)) (list (car x)))))

Here are some examples of expressions using revr:

(revr ?(1 2 3 4)) => (4 3 2 1)

(revr ?((a b) (c d) (e f)) => ((e f) (c d) (a b))

While it works, it?s expensive. Because append runs in time proportional to the length of its first argument, revr requires O(n²) time to reverse a list of length n.

(a) Give the definition of a tail-recursive reverse function revt that produces the same results as revr. You will probably need to use an additional auxiliary function or functions. If you use additional functions, you may define them at top level, or inside of revr using an appropriate version of let (let, let*, etc.).

SOLUTION:
(define (revt lst) (revt-help lst ?())

(define (revt-help lst accum)
         (if (null? lst) accum
                        (revt-help (cdr lst) (cons (car lst) accum))
        )
)

(b) How much time does your tail-recursive function take to reverse a list of length n?

O(n). It is easy to see that unit time is taken at each recursive call. Further, at each recursive call of revt-help, the size of the lst argument reduces by 1, therefore revt-help is called n times. Thus O(n) time is taken in reversing the list.

Question 5. (8 points) This question concerns static (lexical) vs dynamic scope rules.

Suppose we have the following Scheme definitions

(define a 1)

(define b 2)

(define (f a)

(if (< a b)

(g a)

(g b)))

(define (g b) (+ a b))

1. What are the values of the following expressions, using the normal lexical scoping rules of Scheme?


(f 1) 2   (resulting from condition (< 1 2) in f
           being true, (g 1) is called, where a is
           bound to 1 due to lexical scoping)

(f 2) 3   ((g b) is called from f this time)

2. What are the values of the same expressions if they were evaluated in a Scheme dialect that used dynamic scoping?

Start from references available in the

1. Activation records of functions (basically the stack)
2. References available in "static" object references. (say if a reference to an object was found in a static variable of a class, no instance of the needs to exist for referring to that static variable.
3. Now, recursively find all references reachable from these in the heap and mark them active.

1. What is the difference between the types char and Character?


char is a primitive datatype. Character is a class which can be instantiated to form objects.
 
 
 

2. Here are two Java program fragments that use exception handling


try {

DoSomething( );

} catch (Exception e) {

cleanup();

} catch (IOException e) {

fixup();

}

try {

DoSomething( );

} catch (IOException e) {

fixup();

} catch (Exception e) {

cleanup();

}

Do these two code fragments do the same thing? Explain why or why not.

SOLUTION:

NO. The explanation is that IOException is a subclass of Exception, so the code in fixup() will never be called in the first fragment of code. So in the first fragment only cleanup() will be called for all exceptions, whereas in the second fragment, fixup() is called for IOExceptions and cleanup() for all other exceptions.
 

3. Why would it not make sense for a class in Java to be declared both abstract and final?


SOLUTION:
An abstract class cannot be instantiated. It must be extended by a concrete class which implements all its methods. Extension is exactly what a final class does not allow.
 
 
 

4. The == operator and the equals method of a class often produce different results when comparing objects. What is the intended difference between if(a==b)? and if(a.equals(b)) ? ? (i.e., what is the normal usage of == compared to equals?)

Question 8. (8 points) Consider the following Java program.

class A {

void f(int x, int y) { System.out.println("A.f: " + x+y); }

void g(int a) { System.out.println("A.g: " + a); }

}

class B extends A {

void f(int x, int y) { System.out.println("B.f: " + x-y); }

void g(int a, int b) { System.out.println("B.g: " + a*b); }

}

class C extends A {

void f(int x) { System.out.println("C.f: " + x); }

}

class Main {

static void p(A a) {

a.f(1,2);

}

public static void main (String [] args) {

A a = new A();

A b = new B();

A c = new C();

b.f(3,4); // 1

b.g(1,2); // 2

c.f(10); // 3

p(b); // 4

}

}

Describe the output produced by each of the numbered method calls in main. If the method call produces a compile- or runtime error, explain what?s wrong.

SOLUTION:

1) B.f: -1

2) Compile Error : A does not have any function g which takes in two parameters

3) Compile Error : A does not have any function matching f(one parameter).

4) B.f: -1