Lambda Calculus Substitutions

Question 1

What is the requirement for a substitution to be case 1?

Answer 1

b must be a variable

Question 2

What is the requirement for a substitution to be case 2?

Answer 2

b must be a lambda abstraction

Question 3

What is the requirement for a substitution to be case 3?

Answer 3

b must be an application expression

Question 4

What property does subst(a, p, b) contain if the case is 1a?

Answer 4

p == b

Question 5

What property does subst(a, p, b) contain if the case is 1b?

Answer 5

p != b

Question 6

What property does subst(a, p, b) contain if the case is 2a?

Answer 6

p == x

Question 7

What properties does subst(a, p, b) contain if the case is 2b?

Answer 7

p != x and x does not occur freely in a

Question 8

What properties does subst(a, p, b) contain if the case is 2c?

Answer 8

p != x and x does occur freely in a

Question 9

What property does subst(a, p, b) contain if the case is 3?

Answer 9

e1 and e2 are arbitrary lambda expressions

Question 10

What is the evaluation of case 1a?

Answer 10

a

Question 11

What is the evaluation of case 1b?

Answer 11

b

Question 12

What is the evaluation of case 2a?

Answer 12

b

Question 13

What is the evaluation of case 2b?

Answer 13

[lambda]x.subst(a, p, E)

Question 14

What is the evaluation of case 2c?

Answer 14

The Lambda Calculus with case 2b applied, after an alpha-conversion

Question 15

What is the evaluation of case 3?

Answer 15

(subst(a, p, e1) subst(a, p, e2))