CS 421—Summer 2006 1 CS421 Summer 2006 Final Study GuideCS421 Summer 2006 Final Study GuideCS 421 — Programming Languages and CompilersSummer Term 20061. Type Derivations:(a) Provide a full type derivation for the following term. Feel free to write on the papersideways – the trees tend to be wider than they are tall. You can also write out typeenvironments separately and just reference them in the rules (so you could say Γ1= {x :int} and then just reference Γ1in the derivation) – this is especially useful if you usethe same environment in multiple places. Typing rules are on page 11.let f = fun a −> (a + 9) in (f 4)University of Illinois at Urbana-ChampaignCS 421—Summer 2006 2 CS421 Summer 2006 Final Study Guide(b) Provide a full type derivation for the following term. Feel free to write on the papersideways – the trees tend to be wider than they are tall. You can also write out typeenvironments separately and just reference them in the rules (so you could say Γ1= {x :int} and then just reference Γ1in the derivation) – this is especially useful if you usethe same environment in multiple places. Typing rules are on page 11.let rec f = fun a −> (a < 9) in (if (f 4) then 3 else 5)University of Illinois at Urbana-ChampaignCS 421—Summer 2006 3 CS421 Summer 2006 Final Study Guide2. Lambda Calculus(a) Reduce the following term using lazy evaluation.(λa b.a b)(λx y.x)((λt.t)(λu.u))(λc.c c c)(b) Reduce the same term using eager evaluation.University of Illinois at Urbana-ChampaignCS 421—Summer 2006 4 CS421 Summer 2006 Final Study Guide(c) Recall our definition of pairs in the λ calculus – a pair can be represented as a termλx.x a b where x is the constructor tag (here we only have one constructor, so we onlyneed one tag) and a and b are the two elements in the pair. Provide a λ abstractionswappair that takes a pair and returns a new pair with the ele ment swapped: applyingthis to pair (a, b) will return pair (b, a).University of Illinois at Urbana-ChampaignCS 421—Summer 2006 5 CS421 Summer 2006 Final Study Guide3. Context-Free Grammars, Derivations, and Parse Trees: The following exercises makeuse of this grammar for arithmetic expressions. Here, the start symbol is E, id refers to iden-tifiers made up of one lowercase character (a, b, · · · , y, z), and num refers to any integer:E → E + T T → T ∗ F F → idE → E − T T → T/F F → numE → T T → F F → (E)(a) Show a leftmost derivation for the following term:y/3(b) Show a rightmost derivation for the same term:(c) Provide a parse tree for the same term:University of Illinois at Urbana-ChampaignCS 421—Summer 2006 6 CS421 Summer 2006 Final Study GuideE → E + T T → T ∗ F F → idE → E − T T → T/F F → numE → T T → F F → (E)(d) Show a leftmost derivation for the following term:y/(4 + 3)(e) Show a rightmost derivation for the same term:(f) Provide a parse tree for the same term:University of Illinois at Urbana-ChampaignCS 421—Summer 2006 7 CS421 Summer 2006 Final Study Guide4. Semantics:(a) Derivations: Using natural semantics (rules are on pages 14–15), provide a derivationfor the following term:if (i ≤ n) then (n := n + 1) else (i := i + 1)Assume the starting σ = {i 7→ 1, n 7→ 3}. Feel free to turn the page sideways, orto number parts of the derivation and provide them separately (so you can say #1somewhere in the derivation and then elsewhere provide the definition for the #1 partof the derivation tree).University of Illinois at Urbana-ChampaignCS 421—Summer 2006 8 CS421 Summer 2006 Final Study Guide(b) Derivations: Using transition semantics (rules are on pages 12–13), provide a derivationfor the following term:if (i ≤ n) then (n := n + 1) else (i := i + 1)Assume the starting σ = {i 7→ 1, n 7→ 3}. Feel free to turn the page sideways, orto number parts of the derivation and provide them separately (so you can say #1somewhere in the derivation and then elsewhere provide the definition for the #1 partof the derivation tree).University of Illinois at Urbana-ChampaignCS 421—Summer 2006 9 CS421 Summer 2006 Final Study Guide(c) Semantics Rules: Say you are given a new l anguage construct for a for statement. Thisadds the following to the grammar (remember, Com is a command, something that canchange the state):Com c ::= for X := a0to a1do c0doneThis is similar to a while statement, but the iteration space is constrained by the initialvalues specified in the loop and a new name (X) is introduced into scope which can bereferenced in the loop b ody (c0). The semantics should work as follows:i. Expression a0is evaluated until it yields a number n0ii. Expression a1is evaluated until it yields a number n1iii. Name X is added to the environment and assigned the value n0iv. While the numeric value assigned to X is less than or equal to n1, execute commandc0and then add one to XThe name X should not be available once the loop ends. Define the necessary transitionsemantics rules for this construct. You can reference the transition semantics rules forthe IMP language, on pages 12–13, for guidance on how the rules should look.University of Illinois at Urbana-ChampaignCS 421—Summer 2006 10 CS421 Summer 2006 Final Study Guide(d) Semantics Rules: Define the necessary natural semantics rules for the for constructdefined above. You can reference the natural semantics rules for the IMP language, onpages 14–15, for guidance on how the rules should look.University of Illinois at Urbana-ChampaignCS 421—Summer 2006 11 CS421 Summer 2006 Final Study GuideRules for type derivations:Constants⊢ n : int(assuming n is an int)⊢ true : bool⊢ false : boolVariablesΓ ⊢ x : τif(x : τ) ∈ ΓArithmetic OperatorsΓ ⊢ e1: int Γ ⊢ e2: intΓ ⊢ e1⊕ e2: int(⊕ ∈ {+, −, ∗, /, · · · })Relational OperatorsΓ ⊢ e1: int Γ ⊢ e2: intΓ ⊢ e1∼ e2: bool(∼ ∈ {<, >, ≤, ≥, =, 6=, · · · })BooleansΓ ⊢ e1: bool Γ ⊢ e2: boolΓ ⊢ e1&& e2: boolΓ ⊢ e1: bool Γ ⊢ e2: boolΓ ⊢ e1|| e2: boolΓ ⊢ e1: boolΓ ⊢ ! e1: boolIfΓ ⊢ e1: bool Γ ⊢ e2: τ Γ ⊢ e3: τΓ ⊢ if e1then e2else e3: τFunction AbstractionΓ ∪ [x : τ1] ⊢ e : τ2Γ ⊢ fun x−>e : τ1→ τ2Function ApplicationΓ ⊢ e1: τ1→ τ2Γ ⊢ e2: τ1Γ ⊢ e1e2: τ2LetΓ ⊢ e1: τ Γ ∪ [x : τ] ⊢ e2: τ′Γ ⊢ let x = e1in e2: τ′LetrecΓ ∪ [x : τ] ⊢ e1: τ Γ ∪ [x : τ] ⊢ e2: τ′Γ ⊢ let rec x = e1in e2: τ′University of Illinois at
View Full Document
Unlocking...