Module 4: Lambda Calculus

Question 1

True or False:

Lambda Calculus is its own programming language.

Answer 1

True

Question 2

What is everything in lambda calculus expressed as?

Answer 2

Everything in lambda calculus uses the expressions (E)

Question 3

What are valid ways to write lambda expressions?

a. E -> ID
b. E -> λ ID . E
c. E -> E
d. E -> E E
e. E -> (E)

Answer 3

a. E -> ID
b. E -> λ ID . E
d. E -> E E
e. E -> (E)

Question 4

Is lambda left-associative or right-associative?

Answer 4

lambda is left-associative meaning it is parsed from left to right.

Question 5

Is (λ x . y) x equivalent to λ x . y x?

Answer 5

No they are not the same!

This is because when extending to the right in (λ x . y) x stops at the )

Question 6

When are variables considered free in lambda calculus?

a. If the variable does not appear in the meta data.
b. If the variable does not appear within the body of an abstraction with a metavariable of the same name
c. If the variable is not in the abstraction
d. If the variable is in the ID

Answer 6

b. If the variable does not appear within the body of an abstraction with a metavariable of the same name

Question 7

Is x free in the following?

λx . x y z

Answer 7

No x is not free

Question 8

True or False:

In lambda calculus, the term metavariable and formal parameter are the same?

Answer 8

True

Question 9

Is y free in λx . x y z?

Answer 9

Yes y is free in the lambda function

Question 10

Is x free in the following?

(λx . (+ x 1))x

Answer 10

The x on the outside of the function is free, however, the x that inside of the (λx . (+ x 1)) is not free (more specifically the x in (+ x 1)

Question 11

Is z free in the following:

λx . λy . λz . zyx

Answer 11

No Z is not free because it is both the metavariable and in the body

Question 12

Is x free in (λx . z foo)(λ y . y x)?

Answer 12

In (λx . z foo) x is free

In (λy. y x) x is free as well because it is not a formal parameter of this statement.

Question 13

Which of the following are rules for finding free variables?

a. E = x
b. E != x
c. E = λ y . E1, where y = x and x is free in E1
d. E = λ y . E1, where y != x and x is free in E1
e. E = E1 E2, where x is free in E1
f. E = E1 E2, where x is free in E2 and every occurrence of

Answer 13

a. E = x
c. E = λ y . E1, where y = x and x is free in E1
d. E = λ y . E1, where y != x and x is free in E1
e. E = E1 E2, where x is free in E1
f. E = E1 E2, where x is free in E2 and every occurrence of

Question 14

Is x free in the following?

x λ x . x

Answer 14

in E1 (x before λ) x is free
in E2 (λx.x) x is not free

Question 15

When is an expression considered to be a combinator?

a. When it has free variables
b. When there are only two free variables
c. When there is not a metadata
d. When there are not any free variables

Answer 15

d. When there is not any free variables

Question 16

Is the following considered to be a combinator?

λx . λy . x y z

Answer 16

Yes, this is a combinator because x is in the body of λy . xyz
and y is in the body of xyz

Question 17

Why is the following now a combinator?

λz . λx . xyz

Answer 17

λz . λx . xyz is not a combinator because y does not have a meta variable making it free.

Question 18

True or False:

If a variable is free it is bound?

Answer 18

False

A variable is bound if it is not free

Question 19

What are the rules for bound variables?

Answer 19

• If an occurrence of x is free in E, then it is bound by λx . in λx . E
• If an occurrence of x is bound by a particular λx . in E, then x is bound by the same λx . in λz . E
• If an occurrence of x is bound by a particular λx . in E1, then that occurrence in E1 is tied by the same abstraction λx . in E1 E2 and E2 E1

Question 20

What are the free variables in the following?

(λx . x (λy . xyzy) x) x y

Answer 20

(λx . x (λy . x y Z y) x) X Y

Question 21

What is every ID in lambda calculus called?

a. Body
b. Variable
c. Abstraction
d. All of the above

Answer 21

b. Variable

Question 22

What is E -> λ ID . E called?

Answer 22

An abstraction

Question 23

What is currying?

Answer 23

Currying is a technique to translate the evaluation of a function that takes multiple arguments into a sequence o functions that each take a single argument