CMPSC 461: Programming Language Concepts Midterm 1 Practice Questions
Problem 1 λ-calculus.
a) What are the free variables in the λ-term (λx .(λy . y z) y) x.
b) Fully evaluate (λx .(λy .((λy . y) x))) z.
c) Define a function doubleChurch, which takes a Church Numeral and doubles it. Try to build it from scratch, without using the encoding of + or ∗ as defined in lecture.
Problem 2 Higher-order functions and currying.
a) Whatisthecurriedformofλxy.(+xy).
b) Explain in one sentence, what’s the result of (λx y . (+ x y)) 1.
Problem 3 Scheme.
a) Define a recursive Scheme function that takes a list of numbers and returns the product of all the list
elements. Given the empty list, the product should be 1.
b) Define the same functions using “foldl”.
Problem 4 Scheme.
What do the following functions do?
(define (blue p l) (= (length l) (length (filter p l)))) (define (renmap f x ys) (map (lambda (y) (f x y)) ys))
(define (binmap f xs ys) (map (lambda (x) (renmap f x ys)) xs))
Problem 5 Regular Expressions.
a) Define a regular expression for all strings of odd length, over the alphabet of {0}.
b) Define a regular expression for identifiers over the alphabet of {A,B,C,a,b,c,0,1,2,3,4,5,6,7,8,9}, such that an identifier must begin with an alphabetic character and must contain at least one numeric character.
Problem 6 Context free grammar.
Consider the following context free grammar:
P ::=id|P ∨P |P ∧P |¬P |(P) id ::= p | q | r | s
where the set of terminals symbols is {p, q, r, s, ∨, ∧, ¬, (, )} and the start symbol is P . a) Give the leftmost derivations for the following expression:
• ¬(p∧q)
b) Show that this language is ambiguous.
1/2
Problem 7 Context Free Grammar.
For each of the following grammars state whether it is ambiguous or unambiguous. If it is ambiguous give an equivalent unambiguous grammar. If it is unambiguous, state all the precedences and associativities enforced by the grammar. Assume Id generates identifiers.
a) E ::= E + F | E − F | F F ::= −F |Id | (E)
b) E ::= E ∨ F | F
F ::=G∩F |G∪F |G G ::= G ∧ H | H
H ::= Id | (E)
Midterm 1 Practice Questions, Cmpsc 461
2020 Fall