CS 61A Structure and Interpretation of Computer ProgramsFall 2011 Final ExamINSTRU CTIO NS• You have 3 hours to complete the exam.• The exam is closed book, closed notes, closed computer, cl ose d calc ul at or , except a one-page crib sheet of yourown creation and the three official 61A exam study guides, which are attached t o th e b ack of t hi s exam.• Mark your answers ON THE EXAM ITSELF. If you are not sur e 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 stateme nts: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 f oll owing expressions, write the repr string (i.e., t h e string pr i nted by Python interactively) ofthe value to which it evaluates in the current environment. If evaluating the expression causes an error, writ e“Error.” Any changes made to the environment by the expressions below will affect the subsequent express ion s.(a) (2 p t) oracle(41, lambda x: 1/0, ’blue pill’)(b) (2 p t) oracle(42, lambda x: ’red pill’, 1/0)(c) (2 pt) Big.medium(self, -2)(-1)(d) (2 p t) Big().medium(1)(Big().medium(2)(3))(e) (2 pt) Huge().medium(4)(5)(f) (2 pt) Big() == Huge()Login: 32. (16 points ) Environment Diagrams.(a) (6 pt) Complete the environment diagram for the program in t he box below. You do not need to drawan expression tree. A c omp le t e ans wer 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 A2sixty(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:lambda(x): return x * x(b) (2 p t) Wh at value is returned by evaluating sixty(1)? If evaluation causes an error, write “E rr or . ”4(c) (6 pt) Complete the environment diagram for the program in the box below. Assume Python’s normallexical scoping rules. You do not need t o d raw an e xpr ession 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 tupl e valu es using box-and-pointer notation.Snowman4snow(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)man(b): def ice(d): return (b, d) return snow(ice, b+1)(d) (2 pt) If Pyt hon were instead a dynamically scoped language, what would be the value bound to e inthe global frame after this program was executed? Write the rep r string of this value.Login: 53. (12 points ) Pyth-On Vacation.Finish implementing this account object in Logo. Unlike a Pyt hon Account from lecture, the balance of thisLogo account is stored as a global variable called bal.The desire d 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 th e account objectbehaves as specified. You may add quotation marks, square brackets, colons, parentheses, and the wordrun,butno ot h er words. Do not remove any words. Multiple calls to run may be needed.to make_account :balancemake bal balanceoutput sentence message amountendto invoke :message :account :amountoutput accountend6(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 parenthe s es , 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 t h e i n pu t is a well-formed D33P expression. Assume that the input contains a balanced set of nestedparentheses with single-digit positive integers surrounded by parent he se s . 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 express io ns .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>>> correct_depth(list(’((2)(3))’))False>>> correct_depth(list(’((3)(2))’))False>>> correct_depth(list(’(((3)((4))(3))(2)((3)))’))True"""first = s.pop(0)if first != ’(’:return depth==int(first)Login: 74. (18 points) Int erp r eter s. It is possible to complete each part of this question without completing the others.The Decider language app l i es decisions, which are tree-structured rules that allow complex classificationschemes to be decomposed into hierarchies of lookups.