ECS 140A | Programming Languages Final
Final
Please read all instructions (including these) carefully.
There are eight questions on the exam, some with multiple parts. You have 2 hours to work on the exam.
The exam is open book, open notes. If you use a tablet, make sure that wi is o . During the exam, you may only refer to the course textbooks, lecture notes, sample exams, and other printed materials. Any violations will be considered plagiarism.
Please write your answers in the space provided on the exam, and clearly mark your solutions.
Solutions will be graded on correctness and clarity. Each problem has a relatively simple and straightforward solution. You may get as few as 0 points for a question if your solution is far more complicated than necessary. Partial solutions will be graded for partial credit.
NAME:
First Name Last Name SID
|
Problem |
Max points |
Points |
|
1 |
15 |
|
|
2 |
12 |
|
|
3 |
20 |
|
|
4 |
10 |
|
|
5 |
24 |
|
|
6 |
10 |
|
|
7 |
9 |
|
|
8 (EC) |
10 |
|
|
TOTAL |
100 + 10 |
|
Fall 2015 1 of 13
ECS 140A | Programming Languages Final
1. Inheritance and subtyping in object-oriented languages (15 points)
(a) (5 points) Virtual method tables
We have four classes: A, B, C, and D. The following are contents of their virtual method tables (VMTs):
|
A's VMT |
B's VMT |
|
——– |
——– |
|
D::m1 |
B::m1 |
|
A::m2 |
D::m2 |
|
A::m3 |
B::m3 |
|
C's VMT |
D's VMT |
|
——– |
——– |
|
C::m1 |
D::m1 |
|
D::m2 |
D::m2 |
|
B::m3 |
|
|
C::m4 |
Draw the inheritance graph to relate classes A, B, C, and D (put the base class at the top).
Fall 2015 2 of 13
|
Final |
||
|
(b) (10 points) Does the following Java code compile? Circle YES or NO. |
||
|
i. class A { |
||
|
public A foo() { return this; } |
||
|
} |
||
|
class B extends A { |
||
|
@Override |
||
|
public B foo() { return this; } |
||
|
} |
||
|
YES |
NO |
|
ii. class A {
public A foo(A a) { return this; }
}
class B extends A { @Override
public B foo(A a) { return this; }
}
YES NO
iii. class A {
public A foo(A a) { return this; }
}
class B extends A { @Override
public B foo(B b) { return this; }
}
YES NO
iv. class A {
public A foo(B b) { return this; }
}
class B extends A { @Override
public B foo(B b) { return this; }
}
YES NO
v. class A {
public A foo(B b) { return this; }
}
class B extends A {
public B foo(A a) { return this; }
}
YES NO
Fall 2015 3 of 13
ECS 140A | Programming Languages Final
2. Semantics of LISP programs (12 points)
Evaluate the following s-expressions and show the output of the last s-expression.
Circle your answers.
(a) (1 point)
(* (- (+ 3 4) 5) 6)
(b) (1 point)
(car (cdr (cdr '(1 (2 4) 8))))
(c) (3 points)
(do ((l1 '(5 4 3 2 1 0) (cdr l1)) (l2 '(0 1 2 3 4 5) (cdr l2)) (cnt 0 (+ 1 cnt)))
((< (car l1) (car l2)) cnt))
(d) (3 points)
(setf fn1 (let ((a 1)) #'(lambda () (setf a (+ a 2))))) (setf fn2 #'(lambda () (let ((a 1)) (setf a (+ a 2)))))
(list (funcall fn1) (funcall fn1) (funcall fn2) (funcall fn2))
(e) (4 points)
(defun foo (f l) (if (null l) ()
(let ((lnew (mapcar f l)))
(cons (car lnew) (foo f (cdr lnew)))))) (foo #'(lambda (x) (+ x 2)) '(1 3 5 7))
Fall 2015 4 of 13
ECS 140A | Programming Languages Final
3. LISP function de nitions (20 points)
In this problem, you are asked to write a few LISP functions to perform certain tasks.
(a) (6 points) Write a function, mymaplist, to implement the built-in maplist function.
(b) (7 points) Write a function, quicksort, to implement the QuickSort algorithm. It should take a list l as argument and return the sorted list of l in increasing order of its elements.
> (quicksort '(3 1 7 5 2 6 4)) (1 2 3 4 5 6 7)
