G22 2210 001 Programming Languages 1 Final Exam Programming Languages Final Exam General Directions 1 This is an open book test you may bring any kind of books or notes to the room computers no communication No 2 Each question is preceded by a numeric score in square brackets that score indicates both the weight of the question and a high estimate of how many minutes you should be spending on it The total is 100 The official exam period is 110 minutes 3 Write your answers on the examination paper We don t expect you will need additional sheets but there will be a supply of extra paper Be sure to write your name on any sheet that you will be submitting Name G22 2210 001 Programming Languages 2 Final Exam Questions 1 Context free BNF grammar 3 Here is a piece of a BNF grammar for a language with IF statements statement simple statement if statement if statement IF expression THEN statement ELSE statement The square brackets indicate that the ELSE statement is optional It was recognized early on that this grammar was ambiguous because of the so called dangling ELSE problem Assume that x 0 reduces to expression that print x reduces to statement Show that the statement IF x 0 THEN IF x 0 THEN print x ELSE print x has two different parse trees thereby demonstrating that the grammar is ambiguous The outer if statement could reduce to IF expression THEN statement where statement reduces to IF expression THEN statement ELSE statement Alternatively the outer if statement could reduce to IF expression THEN statement ELSE statement where the first statement reduces to IF expression THEN statement Name G22 2210 001 Programming Languages 3 Final Exam 2 Argument passing 2 2 2 6 In a hypothetical imperative language I am giving it Java syntax here is a calling program caller int a 2 5 8 10 that is a 0 2 a 1 5 a 2 8 a 3 10 int i 0 int j sub a i Note expression i first increments i then returns the incremented value Here is a called program callee int sub int p int x p p p x return x What values in the calling program change1 if arguments are a passed by value as in Java or C Underlined parts are part of the answer students must give the rest is an explanation First i becomes 1 then a 1 is evaluated to 5 and 5 is passed by value to sub where it is bound to p Then x 5 Then p is set to 5 5 or 10 The value 5 is returned to j b passed by reference as in Fortran First i becomes 1 then a 1 is passed by reference to sub where it is bound to p Then x is set to a 1 or 5 Then a 1 is added to 5 producing 10 The value 10 is then stored into p which means a 1 gets the value 10 The value 5 is returned to j c passed by name as in Algol In call by name the expression is not initially evaluated but is passed to the parameter p The first statement evaluates p which will evaluate a i incrementing i to 1 and assigning a 1 or 5 to x The next statement evaluates p x This time a i is evaluated again setting i to 2 and returning a 2 or 8 The expression evaluates to 8 5 13 which is then stored in p which will cause i to be incremented to 3 and 13 is stored in a 3 The value x or 5 is returned to j Some students did not realize that in p p x the right side is evaluated before the left side Therefore the p on the right side becomes a 2 and the p on the left side becomes a 3 1 In class this was clarified to Which variables from a i and j in the calling program change after the statement that calls sub and what do they change to Name G22 2210 001 Programming Languages 4 Final Exam 3 Mimicking call by name with closures 12 For the program of Question 2 assume the language is really Java which has call by value but we want to get the effect of call by name Rewrite the program to obtain this effect by a creating a closure including a get and set method b passing it to sub at the call site and c modifying sub to use the closure That is class Closure fill in closure here private int a holds a reference to a private int i holds a copy of i public Closure int a int i this a a this i i public int getI return i retrieves i public int get return a i evaluates a i public void set int arg a i arg stores into a i caller int a 2 5 8 10 int i 0 create a closure instance that will simulate calling sub and passing it a i by name Closure c new Closure a i make a closure passing a and i int j sub c call sub passing it the closure i c getI retrieve the updated value of i callee modify to invoke the closure to read write the parameter int sub Closure p same as original sub with reads of p replaced by p get and assignment to p replaced by p set int x p get p set p get x return x Discussion Call by name is equivalent to passing a closure containing an expression without evaluating the expression Many students missed the basic point that the evaluation of i must happen inside the closure that is invoked by the callee not inside the caller In Java you need a Closure object with two methods one to read the parameter and one to write it When the closure is constructed it is passed access to a and i The subroutine sub calls get or set each time p appears on the right or left respectively The get method evaluates the expression a i returning the result the set method stores a number into a i One wrinkle in Java is that unlike the array the integer i can t be passed into the closure s constructor by reference it must be copied to the closure at construction time and after the call is Name G22 2210 001 Programming Languages 5 Final Exam complete the changed value of i must be copied back from the closure and stored into i Many students who got the rest right missed this Name G22 2210 001 Programming Languages 6 Final Exam 4 Variant records 1 1 3 5 Here is a definition of a variant type Student in Ada TYPE Statuses IS Undergraduate Graduate TYPE Classes IS Freshman Sophomore Junior Senior TYPE Degrees IS Masters Doctorate TYPE Student Status Statuses Undergraduate IS RECORD Name String 1 30 Student Number Integer CASE Status IS WHEN Undergraduate Class Classes WHEN Graduate Degree Degrees END CASE END RECORD …