Exam 2: COMS/SE 342 April 09, 2020
Time: Release 10am-Due in 24hrs
——————————————— Last Name First Name
Learning Outcomes
• Application of knowledge of computing and mathematics
• Ability to understand the implications of mathematical formalisms in computer science • Ability to understand syntax and semantics of grammar
• Ability to comprehend and encode functional definitions
You can consult lecture materials to answer any questions in this test. You are not allowed to collaborate in any form with anyone. You should first read all the questions before starting to work on the solutions. If you need clarification, please post in private on Piazza. Questions posted between 10am and 5pm on April 9 will be answered promptly.
Question
Points
Score
1 (True/False)
10
2 (Grammar)
10
3 (λ-Calculus)
20
4 (Racket)
10
5 (Operational Semantics: Expression Language)
10
6 (Operational Semantics: Sequential Language)
20
Total
80
1
Questions
1. Justify your answer. (unknown implies that neither true nor false assertions are valid).
(a) True/False/Unknown. Ambiguity in grammar always leads to ambiguity in the semantics of the language generated by the grammar.
(b) True/False/Unknown. There can be two grammars G1 and G2 with different number of produc- tion rules and L(G1) = L(G2).
(c) True/False/Unknown. In any programming language, if a function does not have any formal parameters and only uses local variables in its definition, then its behavior remains identical irrespective of its calling context.
(d) True/False/Unknown. A programming language, which does not allow declaration of variables that is not local to some function, cannot use static scoping.
(e) True/False/Unknown. For the interpretation of function calls, we assign the formal parameters to the valuations of the actual arguments. The interpretation can be used to realize call-by-value. call-by-pointer and call-by-reference (as is done in C++) by appropriately altering the type of the formal parameters and the actual arguments.
2. Consider the following grammar G for expressions in first-order logic (F OL is the start symbol) FOL→true|false|V |¬FOL|FOL⊕FOL|∃V FOL|(FOL)
V →x|y|z
(a) Prove that G is ambiguous.
(b) Use the following precedence and associativity to generate a grammar G′ from G such that L(G) = L(G′). (Explicitly identify the start symbol for the grammar G′.)
• ¬ operator has the highest precedence
• ⊕ has higher precedence than ∃
• ⊕ is associative, i.e., the semantics of φ1 ⊕ φ2 same as that for φ2 ⊕ φ1.
3. Given the following lambda expressions and corresponding interpretations:
• The interpretation of λf.λx.x is natural number 0 (zero). The interpretation of
λf λx.(f (f (… x))), with n applications of f on x, is the natural number n > 0.
• The interpretation of λn.λf.λx.(f ((n f) x)) is a successor function succ for natural numbers,
where n is the formal parameter corresponding to the number whose successor is computed.
• The interpretation of λm.λn.((m succ) n) is the addition function add for two natural numbers,
where m and n are the formal parameters corresponding to the numbers whose sum is computed.
• The interpretation of λm.λn.((m (add n)) zero) is the multiplication function mul for two natural numbers, where m and n are the formal parameters corresponding to the numbers whose product is computed.
• The interpretation of λa.λb.λh.((h a) b) is a pair of entities a and b on which some function h can be applied. We will refer to this function as P air. The first or second element of the pair ((Pair z1) z2) can be obtained by applying on it the functions λg.(g λa.λb.a) (referred to as fst) and λg.(g λa.λb.b) (referred to as sec), respectively.
2
• The interpretation of a pair ((P air m) n) where m, n are natural numbers, and n is non-zero, is
a positive rational number whose valuation is m/n. For instance,
((P air λf.λx.(f x)) λf.λx.(f (f x))) represents a positive rational number 1 = 0.5. 2
(a) What is the interpretation of the following function which takes as input a positive rational number.
λr.((Pair (sec r)) (fst r))
(b) What is the interpretation of the following function which takes as inputs two positive rational
numbers.
λr1.λr2.((Pair ((mul (fst r1)) (sec r2))) ((mul (sec r1)) (fst r2)))
(c) Write the lambda expression describing the following function
The function takes as input two positive rational numbers and outputs the sum of the two inputs.
(d) Describeastrategytorepresentsignedrationalnumbers(positive/negativerationalnumbers)and operations (addition, subtraction, multiplication and division) on signed rational numbers using the above knowledge. You are allowed to add new/additional interpretation of existing lambda expressions or derive new lambda expressions from the knowledge presented in this problem. It is not necessary to write the lambda expressions for the operations.
4. Consider the following Racket functions.
;; f is some lambda abstraction that can be applied
;; on one argument
;; In the following function, the output is a list
;; obtained by the application of f on each element of
;; the input list lst.
(define (myf1 f lst)
(if (null? lst)
lst
(cons (f (car lst)) (myf1 f (cdr lst)))))
;; g is some lambda expression that can be applied
;; on three arguments ( ( (g a1) a2 ) a3 )
(define (myf2 g z lst)
(if (null? lst)
0
( ( (g
(car lst)
;; first argument for g
;; second argument for g
;; third argument for g
) )
)
) z
)
(myf2 g z (cdr lst))
3
Example usage of functions is as follows:
> (myf1 (lambda (x) (+ x 1)) ’(1 2 3 4))
’(2 3 4 5)
;; applies the increment-by-1 anonymous function on each
;; element of the list
> (myf2 (lambda (a1)
(lambda (a2)
(lambda (a3)
(if (even? (/ a1 a2))
(+ a1 a3)
(- a1 a3)))))
7
’(91 14 70)
;; applies the anonymous function on each element of the list ’(91 14 70)
;; if the element a1 is such that (even? (/ a1 a2)), where a2 is 7
;; is true, then
;; add the element to the result of a3: (a3 is third argument of
;; the anonymous function)
Assume that students is a student database in the form of a list, where each element in the list is a student record also in the form of a list containing three elements–first element is the id of the student (some number), second element is the name of the student (some symbol) and third element is his/her grade (one of the symbols, A, B, C, D, F). An example student database:
’(
(1 Solo A)
(4 JarJar F)
(3 Chewie B)
(2 Luke A)
)
Apply the above functions (and lambda expressions for parameters f and g, if needed) to output the number of students in the student-database with grades equal to some “A”. You are not allowed to write any helper function. You are allowed to use tests such as equal? and arithmetic operations such as +.
5. Consider the grammar for the expression language with function (similar to the one covered in class). The ApplyF construct includes a second parameter for the apply, which is an expression.
Program -> Expr
Expr -> Number | Var | ArithExpr | VarExpr | … | FExpr | ApplyF
ArithExpr -> (+ Expr Expr) | (- Expr Expr) | …
VarExpr -> (var VarAssign Expr)
VarAssign -> (Variable Expr)
…
FExpr -> (fun FAssign Expr)
FAssign -> ((FName FormalParams) Expr)
4
) 7
FormalParams -> () | (FormalParamList)
FormalParamList -> Var | Var FormalParamList
ApplyF
Args
ArgList
-> (apply (FName Args) Expr)
-> () | (ArgsList)
-> Expr | Expr ArgList
If the semantics of the expression is 0, then the dynamic scoping rule will be followed for evaluating the semantics of the function being applied; otherwise, static scoping rule will be used to evaluate the semantics of the function being applied.
Evaluate the semantics of the following programs (Justify your answer):
(a) (var (x 10) (var (y 20)
(fun ((f ()) (+ x y))
(var (x 20)
(+ (apply (f ()) 0) (apply (f ()) 1))
)
) )
)
(b) (var (x 20) (var (y 10)
(fun ((f ()) (+ x y))
(fun ((g ()) (var (x 30)
) )
)
(+ y (apply (f ()) (- 1 t))))
)
(var (y 50)
(+ (apply (g ()) 1) (apply (g ()) 0))
) )
6. Consider the sequential programming language similar to the ones you have developed in homework assignment.
Program
SSeq
Statement
Decl
Assign
If
FunDecl
FunCall
ParamList
Params
ArgList
Args
FName
-> (SSeq)
-> Statement | Statement SSeq
-> Decl | Assign | If | FunDecl | FunCall
-> (decl Var)
-> (assign Var ArithExpr)
-> (if CondExpr (SSeq))
-> (fundecl (FName ParamList) (SSeq))
-> (call (FName ParamList))
-> () | (Params)
-> Var | Var Params
-> () | (Args)
-> ArithExpr | ArithExpr Args
-> symbol
5
ArithExpr
Op
CondExpr
-> Number | Var | (Op ArithExpr ArithExpr) -> +|- |*|/
-> BCond | (or CondExpr CondExpr) |
(and CondExpr CondExpr) | (not CondExpr)
-> (gt ArithExpr ArithExpr) | (lt ArithExpr ArithExpr) |
(eq ArithExpr ArithExpr)
-> symbol
BCond
Var
We add the following new expressions:
• Expression (pointto Var). The semantics of this expression is the address of the vari- able Var. For instance, (pointto y) returns the address of variable y; and (assign x (pointto y))resultsinmappingxtotheaddressofy.
• Expression (pointeeval Var). The semantics of this expression is the value of some vari- able x, such that the variable Var holds the address of x.
For instance,
(
…
(assign y 10)
(assign x (pointto y))
(assign z (pointeeval x))
…
)
results in mapping the variable z to the value of variable y, which is 10. (y’s value is 10; x holds
the address of y; z gets the value stored at the address of y.)
We also add a new type of declaration statement
(declref Var Var)
which creates an alias for an existing variable. Any update to the alias also results in the update of the original variable. The alias and the variable have the same address. For instance,
(
…
(decl x)
(assign x 1)
(declref y x)
(assign y 22)
(assign x (+ x y))
…
)
results in the following. First statement is a declaration of a variable x, which is initialized to 0. In the next statement, value of x is updated to 1. Due to the declref, the variable y acts as an alias to x. Due the assignment statement to y, the value of x is also updated to 22. Finally, the assignment statement(assign x (+ x y)),updatesthevaluationofxto44.
Finally, we add a new type of assignment statement 6
(assignref v expr)
which maps the pointee of the variable v to the valuation of the expression. In other words, v in this case points to some variable (let us call it x) and the assignref updates the valuation of x. For instance,
(
…
(decl x)
(decl y)
(assign x (pointto y))
(assignref x 23)
…
)
In the above, we have two variables x and y. In the third statement, x is set to point to y and then the
assignref statement is used to update the value of y pointed to by x; the updated value being 23.
Assume the block context rules (i.e., variables declared inside a block is not accessible outside the block; in other words, variables declared in the inner block do not exist in the outer block) and the assumptions that (a) any variable used in any expression will be either declared before being used or will be present in the environment context in which the expression is being evaluated, (b) same name variables are not declared in the same block, and (c) the environment has no bound on the size,
(a) What is the final value of c when the following program is executed? Justify. (
(decl a)
(decl b)
(decl c)
(assign a 0)
(assign b (pointto a))
(if (lt a 1)
(
(assign a 20)
) )
(assign c (pointeeval b))
)
(b) What are the final values for variables a, b and c when the following program is executed? Justify.
(
(fundecl (test (x y z))
(
(assign z (pointeeval x))
(assignref x (pointeeval y))
(assignref y (pointeeval x))
7
) )
(decl a)
(decl b)
(decl c)
(assign a 11)
(assign b 22)
(assign c 33)
(declref d a)
(call (test ((pointto d) (pointto b) c)))
)
(c) Prove/disprove that the inclusion of expressions pointto and pointeeval and evaluating the semantics as described in this question do not result in any exception; i.e., the semantic computation will be always successful under the given assumptions.
(d) Discuss a strategy for developing a succinct memory model that can be used to realize the se- mantics of the new expressions and statements in the language.
8