CS 61A Structure and Interpretation of Computer ProgramsFall 2011 Final Exam SolutionsINSTRUCTIONS• You have 3 hours to complete the exam.• The exam is closed book, closed notes, closed computer, closed calculator, except a one-page crib sheet of yourown creation and the three official 61A exam study guides, which are 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 rightFor which assignmentsdo you have unresolvedregrade requests?All the work on this examis my own. (please sign)For staff use onlyQ. 1 Q. 2 Q. 3 Q. 4 Q. 5 Q. 6 Total/12 /16 /12 /18 /10 /12 /8021. (12 points) What Would Python Print?Assume that you have started Python 3 and executed the following statements:def oracle(a, b, c):if a == 42:return b(a)return cclass Big(object):def medium(self, d):def small(e):nonlocal dif e > 0:d = d + self.medium(e)(-e)return dreturn smallclass Huge(Big):def medium(self, d):return Big.medium(self, d+1)For each of the following expressions, write the repr string (i.e., the string printed by Python interactively) ofthe value to which it evaluates in the current environment. If evaluating the expression causes an error, write“Error.” Any changes made to the environment by the expressions below will affect the subsequent expressions.(a) (2 pt) oracle(41, lambda x: 1/0, ’blue pill’)’blue pill’(b) (2 pt) oracle(42, lambda x: ’red pill’, 1/0)Error(c) (2 pt) Big.medium(self, -2)(-1)Error(d) (2 pt) Big().medium(1)(Big().medium(2)(3))6(e) (2 pt) Huge().medium(4)(5)11(f) (2 pt) Big() == Huge()FalseLogin: 32. (16 points) Environment Diagrams.(a) (6 pt) Complete the environment diagram for the program in the box below. You do not need to drawan expression tree. A complete answer will:• Complete all missing arrows. Arrows to the global frame can be abbreviated by small globes.• Add all local frames created by applying user-defined functions.• Add all missing names in frames.• Add all final values referenced by frames.Sixty-One A Solution3sixty(x): def o(ne): return x * ne def A(): nonlocal o o = lambda x: x * x return 2 return add(o(3), add(A(), o(4)))from operator import adddef sixty(x): def o(ne): return x * ne def A(): nonlocal o o = lambda x: x * x return 2 return add(o(3), add(A(), o(4)))sixty(1)A(): nonlocal o o = lambda x: x * x return 2o(ne): return x * nesixty:x: 1o:A:sixtyne: 3oAlambda(x): return x * xx: 4lambdaadd:add(a, b): return a + bNo points were awarded or subtracted for including or excluding add in the diagram.(b) (2 pt) What value is returned by evaluating sixty(1)? If evaluation causes an error, write “Error.”214(c) (6 pt) Complete the environment diagram for the program in the box below. Assume Python’s normallexical scoping rules. You do not need to draw an expression tree. A complete answer will:• Complete all missing arrows. Arrows to the global frame can be abbreviated by small globes.• Add all local frames created by applying user-defined functions.• Add all missing names in frames.• Add all final values referenced by frames. Represent tuple values using box-and-pointer notation.Snowman Solution5snow(a, b): return (b, a(b+2))def snow(a, b): return (b, a(b+2))def man(b): def ice(d): return (b, d) return snow(ice, b+1)e = man(2)ice(d): return (b, d)sixty:man(b): def ice(d): return (b, d) return snow(ice, b+1)man:ice:b: 2e:manb: 3a:snowd: 5ice3 2 5(d) (2 pt) If Python were instead a dynamically scoped language, what would be the value bound to e inthe global frame after this program was executed? Write the repr string of this value.(3, (3, 5))Login: 53. (12 points) Pyth-On Vacation.Finish implementing this account object in Logo. Unlike a Python Account from lecture, the balance of thisLogo account is stored as a global variable called bal.The desired behavior of the account is to accept deposit and withdraw messages. Deposit increases thebalance by an amount, while withdraw reduces the amount if funds are available.? make "john_account make_account 100? print invoke "withdraw :john_account 4060? print invoke "withdraw :john_account 70insufficient_funds? print invoke "deposit :john_account 2080? print invoke "withdraw :john_account 7010Invoking a method calls the corresponding named procedure. The deposit and withdraw procedures areimplemented below.to deposit :amtmake "bal :bal + :amt output :balendto withdraw :amtifelse :amt > :bal [output "insufficient_funds] [make "bal :bal - :amt output :bal]end(a) (6 pt) Add punctuation and the word run to make account and invoke so that the account objectbehaves as specified. You may add quotation marks, square brackets, colons, parentheses, and the wordrun, but no other words. Do not remove any words. Multiple calls to run may be needed.to make_account :balancemake "bal :balanceoutput [run sentence :message :amount]endto invoke :message :account :amountoutput run :accountendORto make_account :balancemake "bal :balanceoutput [sentence :message :amount]endto invoke :message :account :amountoutput run run :accountend6ORto make_account :balancemake "bal :balanceoutput sentence ":message ":amountendto invoke :message :account :amountoutput run :accountendLogin: 7(b) (6 pt) The D33P language includes three types of tokens: open parentheses, close parentheses, andintegers. An expression is well-formed if it contains balanced parentheses, and each integer correctlyindicates its depth: the number of nested sets of parentheses that surround that integer.Implement correct depth, which takes a list of tokens as input and returns True if and only if a prefixof the input is a well-formed D33P expression. Assume that the input contains a balanced set of nestedparentheses with single-digit positive integers surrounded by parentheses. You only need to check thatthe integers indicate the correct depths.Do not change any of the code that is provided. You may not use any def statements or lambda expressions.def correct_depth(s, depth=0):"""Return whether a prefix of list s is a well-formed D33P expression.>>> list(’(1)’)[’(’, ’1’, ’)’]>>> correct_depth(list(’(1)’))True>>> correct_depth(list(’(2)’))False>>> correct_depth(list(’((2)((3)))’))True>>>
View Full Document