Lambda Calculus Flashcards
What are Lambda Calculus benefits?
- Define computable functions
- Mathematical foundation for functional programming
What is a function?
(T/F) Lambda calculus is a method of representing functions.
True
Lambda calculus provides a set of conversion rules for syntactically transforming functions. Give an example.
Give an example:
Give an example of the following in ML & Scheme:
(T/F)
λ y. * (+ x y) 2
x is bound in this expression
y is free
False
(T/F)
λ x. λ y. * (+ x y) 2
both x and y are bound in this expression.
True
(T/F)
In the pure form of lambda calculus, everything is a fuction.
True
Simple syntax for lambda calculus:
Is this in the abstraction or application form?
(λx. ((* 2) x))
Abstraction
Is this in the abstraction or application form?
((λx. ((* 2) x)) 3)
Application
This is a function defined by a lambda abstraction and given an argument.
What is this special case?
(λx. x)
function of x that returns x, is the identity function since it is the function or
((λx. x) E) = E
for any lambda expression E
(T/F)
In applications, association groupings associate to the right.
False
(f g h) = (f g) h
not f (g h)
In ML:
fun f x :: xs gives error because this is interpreted as (f x) :: xs and it should be f (x::xs).
Which has higher precedence, abstraction or application?
Application has higher precedence than abstraction
λx.A B = λx.(A B)
not (λx.A) B <– This makes B an argument
Express the following nested list expression with parenthesis.
λ x y z . E
(λ x. (λ y . (λ z . E )))
Give names to λ expressions
Example: define f = (λ x . ((+ x) 1))
What is this in ML and Scheme?
Use val keyword in ML
val f = fn x => x+1
f 3
Use define keyword in Scheme
(define f (lambda (x) (+ x 1)))
(f 3)
Reduction rules in lambda expressions:
Apply a set of reduction rules to simplify the expression
4 kinds of reduction rules:
δ (delta)
β (beta)
α (alpha)
η (eta)
Delta Reduction:
Use for the built-in constants
+ 2 3
->δ
5
Read “+ 2 3” reduced to 5 with the delta indicating that reduction used a delta rule
Delta Reduction:
* (+ 1 2)(- 5 1)
Beta Reduction:
Given
((λ x. E1) E2)
Replace all occurrences of bound variable x in the body, E1, with E2.
What is the Beta reduction for the following?
((λ x . * 2 x) 5)
Beta Reduction:
( (λ x. λ y. + x y) 7 ) 8
Issues with Beta reduction:
( λ x. ( (λ x.x) (+ 1 x) ) ) 3
Name clash resolution:
The example again
(λ x. (λ x.x) (+ 1 x)) 3
Alternative reduction:
(λ x. (λ x.x) (+ 1 x)) 3
Previous Reduction:
Eta Conversion
What is Normal form in Lambda Calculus?
A lambda expression is in normal form if it cannot be further reduced using beta reduction, a delta rule, or eta reduction.
Can every lambda expression be reduced to normal form?
No, not all expressions can be reduced to normal form.
Not all expressions can be reduced to normal form.
Are there any consequences of the failure to find normal form for all expressions?
Is there more than one way to reduce a lambda expression?
Yes
If there is more than one reduction strategy, does each lead to the same normal form expression?
Yes
Church-Rosser theorem implies that if an expression E can be reduced in two different ways to two normal forms, then these normal forms are the same up to alphabetic equivalence (i.e. you can get one from the other using alpha conversion).
This is also called the diamond property.
Is there a reduction strategy that guarantees that a normal form expression will be produced (if there is one)?
Yes:
**Standardization theorem: **
If an expression E has a normal form, then a strategy that reduces the leftmost outermost redex at each state in the reduction is guaranteed to reach that normal form.
Outermost and Innermost example:
Definitions:
- Redex - an expression that can be reduced
- Leftmost -** **a redex whose lambda (or primitive function identifier) is textually to the left of all other redexes.
- **Outermost - **a redex not contained within any other redex
- **Innermost - **a redex that contains no other redex
(T/F)
Lambda calculus has computational power equivalent to Turing machines
True
What are the two reduction strategies?
Connection between reduction strategies and parameter passing.
Example of normal vs applicative order reduction:
What is an alternative to Normal order and Applicative order reduction?
Lazy Evaluation
Like normal order, but introduce pointer to expression (rather than copying it) and evaluate it only once, when its value is needed.
Also called graph reduction.
Lazy Evaluation Example:
Benefits of Lazy Evaluation
Example: booleans and conditionals
show if true a b = a
Do functional programming use iteration?
No. Recursion is used instead.
Info on recursive functions:
