CSE 341 - Programming LanguagesFinal exam - Autumn 2008 – Answer KeyOpen book and notes. No laptop computers, PDAs, or similar devices. (Calculators are OK, althoughyou won’t need one.) Please answer the problems on the exam paper — if you need extra space use the backof a page.90 points total1. (10 points) Suppose we have the following definition of the map function in Haskell.map f [] = []map f (x:xs) = f x : map f xsCircle each type declaration that is a correct type for map. (Not necessarily the most general type,just a correct one.)1The following are correct types:map :: ([Integer] -> [Integer]) -> [[Integer]] -> [[Integer]]map :: (a -> a) -> [a] -> [a]map :: (a -> b) -> [a] -> [b]This one is incorrect:map :: (a -> b) -> [b] -> [a]Which of the above types, if any, is the most general type for map?map :: (a -> b) -> [a] -> [b]2. (6 points) Consider the following Scheme expression:(let*((x a)(y (+ x 10)))(+ x y))Write an equivalent Scheme expression that binds x and y to the same values as above and returns thevalue of (+ x y) but that only uses let and not let*.(let ((x a))(let (y (+ x 10))(+ x y)))1Oh no, I hear you cry! Not this question again . . .13. (10 points) Write a Ruby class Delay that implements delays (as we saw in Scheme). The followingcode shows how it should work:n = 0d = Delay.new {n=n+1; 3+4}d.forced.forcev = d.forcee = Delay.new {1/0}After we evaluate these statements v should be 7, but n should only be 1 (since we only evaluate theblock once). Further, since we never force e, we shouldn’t get a divide-by-zero error.class Delaydef initialize(&p)@p = p@value = nil@unevaluated = trueenddef forceif @unevaluated@value = @p.call@unevaluated = falseendreturn @valueendend4. (10 points)(a) Write a repeat rule in CLP(R) with three arguments: N, X, and Xs. It succeeds if Xs is a listconsisting of N copies of X. Here are some sample goals and results:?- repeat(3,a,Xs).Xs = [a,a,a]?- repeat(0,a,Xs).Xs = []?- repeat(-2,a,Xs).no.repeat(0,X,[]).repeat(N,X,[X|Xs]) :- N>0, repeat(N-1,X,Xs).2(b) What answers are returned for the following goals using the rule you just defined for Question4a? (Part of answering Question 4b is deciding what a reasonable behavior is in these situations.)Continue on the back of this page as needed. If there are a finite number of answers give themall; if an infinite number give at least the first three.?- repeat(N,Q,[a,a,a,a]).Q = aN = 4?- repeat(N,Q,[a,b,c]).no?- repeat(N,a,As).As = []N = 0As = [a]N = 1As = [a, a]N = 2As = [a, a, a]N = 3As = [a, a, a, a]N = 45. (12 points) Consider the following CLP(R) rule:sum([],0).sum([X|Xs],X+S) :- sum(Xs,S).(a) Draw the simplified derivation tree for the goal sum([100], N).(b) Draw the simplified derivation tree for the goal sum(As, 10). (This is an infinite tree; in-clude at least 3 answers in the tree that you draw.)(answers on a separate scanned page)36. (10 points) This question use the following hierarchy of Java classes for simple geometric shapes.(This is the same hierarchy you used for the last homework assignment.)public interface GeometricShape {public void describe();}public interface TwoDShape extends GeometricShape {public double area();}public interface ThreeDShape extends GeometricShape {public double volume();}public class Circle implements TwoDShape {....}public class Cone implements ThreeDShape {....}public class Rectangle implements TwoDShape {....}public class Sphere implements ThreeDShape {....}Suppose we have three different implementations of a total_area method to find the total area ofsome shapes.public static double total_area1(ArrayList<TwoDShape> shapes){double sum = 0;for(TwoDShape shape : shapes) {sum = sum + shape.area();}return sum;}public static double total_area2(ArrayList<? extends GeometricShape> shapes){double sum = 0;for(GeometricShape shape : shapes) {sum = sum + ((TwoDShape) shape).area();4}return sum;}public static double total_area3(ArrayList<? extends TwoDShape> shapes){double sum = 0;for(TwoDShape shape : shapes) {sum = sum + shape.area();}return sum;}Now suppose that we have four variables declared as follows:ArrayList<Rectangle> rects;ArrayList<TwoDShape> two_d_shapes;ArrayList<GeometricShape> geo_shapes;double area;We then assign various shapes to the different arraylists. (So rects will only contain instancesof Rectangle, while geo shapes might contain instances of Circle, Cone, Rectangle, orSphere.)Consider the following code that uses these methods and variables. Write “compiles” next to thefollowing statements that compile correctly, and write “doesn’t compile” next to the ones that don’tcompile. Finally, if there is a possibility that the statement will cause a cast exception to be raised,write “possible exception” next to it.area = total_area1(rects); DOESN’T COMPILEarea = total_area1(two_d_shapes); COMPILESarea = total_area1(geo_shapes); DOESN’T COMPILEarea = total_area2(rects); COMPILESarea = total_area2(two_d_shapes); COMPILESarea = total_area2(geo_shapes); COMPILES; POSSIBLE EXCEPTIONarea = total_area3(rects); COMPILESarea = total_area3(two_d_shapes); COMPILESarea = total_area3(geo_shapes); DOESN’T COMPILE7. (6 points) What is something that Ruby mixins can do that Java interfaces can’t?Ruby mixins have implementations of the methods they include; Java interfaces just have the methodheader but no body.8. (6 points) Consider the following Java code fragments. In each case, does the code compile correctly?If so, does it execute without error, or is there an exception?5(a) Object[] a = new String[10];a[0] = "hi there";executes without error(b) ArrayList<Object> a = new ArrayList<String>();a.add("hi there");compile error(c) Object[] a = new String[10];a[0] = new Point(10,20);runtime exception9. (10 points) What is duck typing? What is an advantage of duck typing over a more standard approach,and what is a potential problem? Finally, could you program in Java in a way that follows the ducktyping philosophy? Why or why not?Duck typing is a philosophy and programming technique used in Ruby. (It could also be used in otherdynamically typed object-oriented languages such as Smalltalk, although I’m not requiring this factas part of your answer.) The term comes from the aphorism “if it walks like a duck and quacks like aduck, it’s a duck.”The idea is that rather than including any runtime checks of what the class is of an object, you justsend it the message and let it respond in whatever way it wants. If you aren’t
View Full Document
Unlocking...