Questions & Results
Q1 of 10Multiple ChoiceAccuracy45s · 1 pt
Which grammar defines the syntax of the (pure) lambda calculus?
A e ::= x | λx.e | e e✓ Correct B e ::= n | x | e + e | if e then e else e C e ::= x | λx.e | let x = e in e D e ::= true | false | x | e e 11 / 179 answered · 91% correct
Q2 of 10Multiple ChoiceAccuracy60s · 1 pt
Using the conventions that λ extends as far right as possible and application is left-associative, λx.x a b is equivalent to which of the following?
D (λx.((x a) b))✓ Correct 171 / 179 answered · 60% correct
Q3 of 10Multiple ChoiceAccuracy45s · 1 pt
What does beta-reduction do to (λx.e1) e2?
A It evaluates e1 and e2 and compares their values for equality B It replaces every free occurrence of x in e1 with e2✓ Correct C It replaces every occurrence of e2 in e1 with x D It discards e2 and returns e1 unchanged 175 / 179 answered · 83% correct
Q4 of 10Multiple ChoiceAccuracy45s · 1 pt
Beta-reducing (λx.y) z gives:
176 / 179 answered · 90% correct
Q5 of 10Multiple ChoiceAccuracy60s · 1 pt
Which of the following reduces to λz.z?
a) (λy.λz.x) z
b) (λz.λx.z) y
c) (λy.y) (λx.λz.z) w
d) (λy.λx.z) z (λz.z)
178 / 179 answered · 93% correct
Q6 of 10Multiple ChoiceAccuracy60s · 1 pt
In the eager (call-by-value) evaluation rule
e1 ⇓ λx.e3 e2 ⇓ e4 e3[x := e4] ⇓ e5
------------------------------------------
e1 e2 ⇓ e5
what must happen to e2 before the beta-reduction step?
A Nothing — e2 is substituted into e3 as is B e2 must first be evaluated to a value e4✓ Correct C e2 is discarded and never used D e2 must be alpha-renamed before substitution 175 / 179 answered · 97% correct
Q7 of 10Multiple ChoiceAccuracy60s · 1 pt
In the lazy (call-by-name) evaluation rule
e1 ⇓ λx.e3 e3[x := e2] ⇓ e4
--------------------------------
e1 e2 ⇓ e4
what is substituted in place of x?
A The value that e2 evaluates to B e2 itself, unevaluated✓ Correct D Nothing; x is left as a free variable 175 / 179 answered · 94% correct
Q8 of 10Multiple ChoiceAccuracy60s · 1 pt
Which reduction sequence matches call-by-value evaluation of (λz.z) ((λy.y) x)?
A (λz.z) ((λy.y) x) → (λz.z) x → x✓ Correct B (λz.z) ((λy.y) x) → (λy.y) x → x C (λz.z) ((λy.y) x) → (λy.y) z → z D It does not reduce further 174 / 179 answered · 72% correct
Q9 of 10Multiple ChoiceAccuracy60s · 1 pt
Which reduction sequence matches call-by-name evaluation of (λz.z) ((λy.y) x)?
A (λz.z) ((λy.y) x) → (λz.z) x → x B (λz.z) ((λy.y) x) → (λy.y) x → x✓ Correct C (λz.z) ((λy.y) x) → (λy.y) z → z D It does not reduce further 175 / 179 answered · 88% correct
Q10 of 10Multiple ChoiceAccuracy60s · 1 pt
Under call-by-name, what does (λx.x (λy.y)) (u r) reduce to?
C It is stuck, since `u r` is not a value 178 / 179 answered · 49% correct
Score Distribution
Score (points) →