Module 4: Lambda Calculus Flashcards
True or False:
Lambda Calculus is its own programming language.
True
What is everything in lambda calculus expressed as?
Everything in lambda calculus uses the expressions (E)
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)
a. E -> ID
b. E -> λ ID . E
d. E -> E E
e. E -> (E)
Is lambda left-associative or right-associative?
lambda is left-associative meaning it is parsed from left to right.
Is (λ x . y) x equivalent to λ x . y x?
No they are not the same!
This is because when extending to the right in (λ x . y) x stops at the )
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
b. If the variable does not appear within the body of an abstraction with a metavariable of the same name
Is x free in the following?
λx . x y z
No x is not free
True or False:
In lambda calculus, the term metavariable and formal parameter are the same?
True
Is y free in λx . x y z?
Yes y is free in the lambda function
Is x free in the following?
(λx . (+ x 1))x
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)
Is z free in the following:
λx . λy . λz . zyx
No Z is not free because it is both the metavariable and in the body
Is x free in (λx . z foo)(λ y . y x)?
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.
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
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
Is x free in the following?
x λ x . x
in E1 (x before λ) x is free in E2 (λx.x) x is not free
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
d. When there is not any free variables
Is the following considered to be a combinator?
λx . λy . x y z
Yes, this is a combinator because x is in the body of λy . xyz
and y is in the body of xyz
Why is the following now a combinator?
λz . λx . xyz
λz . λx . xyz is not a combinator because y does not have a meta variable making it free.
True or False:
If a variable is free it is bound?
False
A variable is bound if it is not free
What are the rules for bound variables?
- 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
What are the free variables in the following?
(λx . x (λy . xyzy) x) x y
(λx . x (λy . x y Z y) x) X Y
What is every ID in lambda calculus called?
a. Body
b. Variable
c. Abstraction
d. All of the above
b. Variable
What is E -> λ ID . E called?
An abstraction
What is currying?
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
