CS 61A Structure and Interpretation of Computer ProgramsSummer 2013 FinalINSTRUCTIONS• You have 3 hours to complete the exam.• The exam is closed book, closed notes, closed computer, closed calculator, except one hand-written 8.5” × 11”crib sheet of your own creation and the official 61A study guides attached to the back of this exam.• Mark your answers ON THE EXAM ITSELF. If you are not sure of your answer you may wish to provide abrief explanation.Last nameFirst nameSIDLoginTA & section timeName of the person toyour leftName of the person toyour rightAl l the work on this examis my own. (please sign)21. (5 points) Orange you glad it’s not “What Will Python Print”?(a) (3 pt) Assume the following definitions have been made:def foo(num):return x + numdef bar(x):return foo(x + 3)def banana(x):def orange(num):return num + x * 3return orangedef apple(x):return banana(x - 2)(4)Write what each of the function calls below would return in lexical and dynamic scope. If a function callwould result in an error, write Error instead.>>> bar(3)• Lexical scope:• Dynamic scope:>>> apple(7)• Lexical scope:• Dynamic scope:(b) (2 pt) Alan Kay drew parallels to common user interface design principles from which of the followingsports? Write an X on the line next to your answer.BasketballBowlingFootballGolfSoccerTennisVolleyballLogin: 32. (4 points) Abstract away your worriesAssume we are provided the following implementation of the rlist abstract data type:empty_rlist = Nonedef rlist(first, rest):return (first, rest)def first(s):return s[0]def rest(s):return s[1]In the following functions, clearly circle any data abstraction violations. Draw one circle for each data abstrac-tion violation.def interleave(s1, s2):if not s1:return s2elif not s2:return s1recursive = interleave(s1[1], s2[1])return rlist(first(s1), (first(s2), recursive))def filter(pred, s):if not s:return Noneelif pred(first(s)):return (first(s), filter(pred, s[1]))return filter(pred, s[1])43. (12 points) Lambdas and llamas(a) (6 pt) Fill in the environment diagram that results from executing the code below until the entire programis finished, an error occurs, or all frames are filled. You need only show the final state of each frame. Youmay not need to use all of the spaces or frames.A complete answer will:• Add all missing names, labels, and parent annotations to all local frames.• Add all missing values created during execution.• Show the return value for each local frame.Global&frame&func&in_the(sun)&def&in_the(sun):&&&&&def&sun(fun):&&&&&&&&&def&beach(water):&&&&&&&&&&&&&nonlocal&sun&&&&&&&&&&&&&if&water&==&0:&&&&&&&&&&&&&&&&&return&fun&&&&&&&&&&&&&sun&=&beach&&&&&&&&&&&&&return&sun(water&:&1)&&&&&&&&&return&beach&&&&&return&sun&&boat&=&[in_the]&boat.append(boat)&summer&=&boat[0](boat)&summer(2)(1)&Return&Value&Return&Value&Return&Value&Return&Value&in_the&Login: 5(b) (6 pt) Fill in the environment diagram that results from executing the code below until the entire programis finished, an error occurs, or all frames are filled. You need only show the final state of each frame. Youmay not need to use all of the spaces or frames.A complete answer will:• Add all missing names, labels, and parent annotations to all local frames.• Add all missing values created during execution.• Show the return value for each local frame.Global&frame&func&uni(llama)&def&uni(llama):&&&&&x&=&10&&&&&def&volde(uni,&x):&&&&&&&&&return&uni&>&llama(11,&7)&&&&&return&volde&&x&=&5&def&volde(uni,&x):&&&&&if&uni(6,&x):&&&&&&&&&return&"pi"&&&&&return&"i"&&llama&=&uni(lambda&llama,&uni:&llama&+&uni&+&x)&volde(llama,&20)&&&Return&Value&Return&Value&Return&Value&Return&Value&uni&x&5&func&volde(uni,&x)&volde&&&64. (4 points) Cupcakes cupcakes cupcakes cupcakes cupcakesRecall the type_tag function discussed in lecture:def type_tag(generic_object):return type_tag.tags[type(generic_object)]We will use this function to create a generic function. Because everyone likes pastries, you have created fivedifferent classes to represent five different kinds of pastries:• SugarCookie• SnickerdoodleCookie• RedVelvetCookie• VanillaCake• CheeseCakeYou have two functions, eat_cookie and eat_cake, which you call on the appropriate pastry to consume it.However, each function only works on pastries of a particular type – eat_cookie only works on cookies, andeat_cake only works on cake. Tired of having to manually select the correct function, you attempt to definea generic eat function:def eat(baked_good):return eat.implementations[type_tag(baked_good)](baked_good)This function takes a baked good and calls the appropriate eat function on it, regardless of its type. However,in your haste to consume delicious baked goods, you forgot to fill in the appropriate dictionaries to make thiswork! Complete the following two dictionaries so that the eat function works as expected. Use as few tagsas possible.type_tag.tags = {}eat.implementations = {}Login: 75. (10 points) Interpretive dance(a) (4 pt) Assume the following definition has been loaded into the Scheme interpreter from Project 4:(define (sum-of-squares x y z)(+ (* x x) (* y y) (* z z)))Given the following Scheme expressions, circle the correct number of calls to scheme_eval and scheme_apply:(+ 5 (* 3 7 3))scheme_eval 3 4 5 6 7 8 9scheme_apply 1 2 3 4 5 6(sum-of-squares 3 4 5)scheme_eval 4 5 8 10 14 19 24 25scheme_apply 1 2 3 4 5 6(b) (6 pt) For each of the following Scheme expressions, place an X on the line next to the correct Pairrepresentation that scheme_read from Project 4 would create.(func (4 5) 3)Pair('func', Pair(4, Pair(5, Pair(3))))Pair('func', Pair(4, Pair(5, Pair(3, nil))))Pair('func', Pair(Pair(4, 5), Pair(3, nil)))Pair('func', Pair(Pair(4, Pair(5, nil)), Pair(3, nil)))Attempting to scheme_read the above expression would result in a syntax error.'(1 2 (3))Pair(1, Pair(2, Pair(3, nil)))Pair(1, Pair(2, Pair(Pair(3, nil), nil)))Pair('quote', Pair(1, Pair(2, Pair(Pair(3, nil), nil))))Pair('quote', Pair(Pair(1, Pair(2, Pair(Pair(3, nil), nil))), nil))Attempting to scheme_read the above expression would result in a syntax error.(cdr () 'cdr)Pair('cdr', Pair(nil, Pair('cdr', nil)))Pair('cdr', Pair(Pair(nil, Pair('cdr', nil))))Pair('cdr', Pair(nil, Pair(Pair('quote', Pair('cdr', nil)), nil)))Pair('cdr', Pair(Pair(nil, Pair(Pair('quote', Pair('cdr', nil))))))Attempting to scheme_read the above expression would result in a syntax error.86. (9 points) You Oughta Like Objects(a) (6