15-312 Foundations of Programming LanguagesFinal ExaminationDecember 13, 2004Name:Andrew User ID:• This is an open book, open notes, closed computer exam.• Write your answer legibly in the space provided.• There are 18 pages in this exam, including 4 worksheets.• It consists of 5 problems worth a total of 250 points and one extra credit questionworth 25 points.• The extra credit is recorded separately, so only attempt this after you have com-pleted all other questions.• You have 3 hours for this exam.• Read the questions carefully before you answer!Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Total EC50 50 55 50 45 250 2511. Continuations (50 pts)A popular way to compile functional programs (employed in implementations of Schemeand Standard ML of New Jersey) is to translate them to continuation-passing style. Thebasic intuition is that every function is transformed to take one additional argument, itscontinuation. Instead of returning a value, the function explicitly passes the return valueto its continuation argument. In this setting, continuations are implemented as ordinaryfunctions that represent the remainder of the computation, and throwing a value to acontinuation is implemented as a function call.As a simple example, consider the successor function fn(x.plus(x, num(1))). This mightbe compiled to λx. λk. k (x + 1) which passes its result (x + 1) to its continuation argumentk instead of returning it. Here, and in the rest of the problem we will use abstract syntaxfor the source of the translation and mathematical syntax for the target of the translation.Formally, we define an inductive translation [[e]] k which translates an expression e un-der a continuation k. The translation of e should pass its value to k, as exemplified in thefirst three cases below. For every variable x in the source we have a corresponding vari-able ˆx in the target. For functions and integers, the translation is defined by the followingcases:[[num(n)]] k = k n[[x]] k = k ˆx[[fn(x.e)]] k = k (λˆx. λk1. [[e]] k1)[[apply(e1, e2)]] k = [[e1]] (λx1. [[e2]] (λx2. x1x2k))At the top-level, the C-machine starts with the empty stack “•”, also called the initialcontinuation. In the functional representation, the initial continuation is the identity func-tion λz. z which returns it argument as the final answer of the computation. We thereforetranslate a given expression at the top-level under the initial continuation λz. z. For ex-ample:[[apply(fn(x.x ), num(3))]] (λz. z)= [[fn(x.x)]] (λx1. [[num(3)]] (λx2. x1x2(λz. z)))= [[fn(x.x)]] (λx1. (λx2. x1x2(λz. z)) 3)= (λx1. (λx2. x1x2(λz. z)) 3) (λˆx. λk. [[x]] k)= (λx1. (λx2. x1x2(λz. z)) 3) (λˆx. λk. k ˆx)21.1 (10 pts) Verify, step-by-step using the small-step operational semantics and the re-sult of the translation above, that[[apply(fn(x.x ), num(3))]] (λz. z) 7→∗3(λx1. (λx2. x1x2(λz. z)) 3) (λˆx. λk. k ˆx)7→The translation to continuation-passing style changes the types of expressions. Wewrite [τ ]σfor the translation of the type τ , given a final answer type σ, andˆΓ for thecontext that arises from replacing every declaration x:τ in Γ by ˆx:[τ ]σ. Then the definingproperty of the type translation isIf Γ ` e : τ and Γ0` k : [τ]σ→ σ thenˆΓ, Γ0` [[e]] k : σ.In other words, when translating [[e]] k then k must accept the value of e (after translation)and return the final answer of type σ.1.2 (10 pts) Give the definition of [τ1→ τ2]σin terms of [τ1]σand [τ2]σso that the trans-lation of functions results in well-typed terms.[τ1→ τ2]σ=31.3 (15 pts) Extend the translation to pairs by completing the following table. You mayuse pairs in the target.[τ1× τ2]σ= [τ1]σ× [τ2]σ[[pair(e1, e2)]] k =[[fst(e)]] k =[[snd(e)]] k =1.4 (15 pts) Translation to continuation-passing style makes it very easy to implementcallcc and throw in the source without using callcc or throw in the target, since con-tinuations are represented as ordinary functions. For reference, here are the typingrules for callcc and throw.Γ, x:τ cont ` e : τΓ ` callcc(x.e) : τΓ ` e1: τ Γ ` e2: τ contΓ ` throw(e1, e2) : τ0Complete the following definitions. [Hint: use the types as your guide.][τ cont]σ= [τ]σ→ σ[[callcc(x.e)]] k =[[throw(e1, e2)]] k =42. Object-Oriented Programming (50 pts)In this question we will examine the correct use of object-oriented constructs. Supposewe are writing software to handle the routing and shipping of packages. We have variousplaces that produce packages, and various parties that want consume them. Part of thedeclarations in the library shown below:class Producer of { ... }class Consumer of { ... }class Package of { ... }class RemoteProducer extends Producer of { ... }class FragilePackage extends Package of { ... }class RemoteConsumer extends Consumer of { ... }method deliver(Producer, Package, Consumer) : unitIn this library, we have classes to account for all of the producers, packages, and con-sumers, and a method which takes one of each to take care of all behavior for one delivery.Far-away production and consumption sites, and fragile packages may require specialtreatment, and so we subclass each of the three base classes.Suppose a few of our coworkers in this fictional shipping company come to us and tellus they have finished implementing the method deliver. The code they have writtenlooks like the following.extend deliver(p : RemoteProducer, k : Package, c : RemoteConsumer) = ...extend deliver(p : RemoteProducer, k : Package, c : Consumer) = ...extend deliver(p : Producer, k : FragilePackage, c : Consumer) = ...2.1 (10 pts) Given (only) these declarations, will the typechecker (using only the globalchecking algorithm described in lecture—don’t worry about the more efficient localchecking techniques) report that the program is vulnerable to a run-time ‘messagenot found’ error? (Remember that this is analogous to ML’s ‘nonexhaustive match ex-ception’) If so, give an example of a method call that will result in this error. You canwrite simply {Package: ...}, for example, to indicate an object of class Package,and similarly with the other five classes.52.2 (15 pts) Given (only) these declarations, will the typechecker report that the programis vulnerable to a run-time ‘message ambiguous’ error? If so, give an example of amethod call that will result in this error.2.3 (10 pts) If we add a caseextend deliver(p : Producer, k :