Lambda Calculus

Question 1

What are Lambda Calculus benefits?

Answer 1

• Define computable functions
• Mathematical foundation for functional programming

Question 2

What is a function?

Answer 2

Question 3

(T/F) Lambda calculus is a method of representing functions.

Answer 3

True

Question 4

Lambda calculus provides a set of conversion rules for syntactically transforming functions. Give an example.

Answer 4

Question 5

Give an example:

Answer 5

Question 6

Give an example of the following in ML & Scheme:

Answer 6

Question 7

(T/F)

λ y. * (+ x y) 2
x is bound in this expression
y is free

Answer 7

False

Question 8

(T/F)

λ x. λ y. * (+ x y) 2
both x and y are bound in this expression.

Answer 8

True

Question 9

(T/F)

In the pure form of lambda calculus, everything is a fuction.

Answer 9

True

Question 10

Simple syntax for lambda calculus:

Answer 10

Question 11

Is this in the abstraction or application form?

(λx. ((* 2) x))

Answer 11

Abstraction

Question 12

Is this in the abstraction or application form?

((λx. ((* 2) x)) 3)

Answer 12

Application

This is a function defined by a lambda abstraction and given an argument.

Question 13

What is this special case?

(λx. x)

Answer 13

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

Question 14

(T/F)

In applications, association groupings associate to the right.

Answer 14

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).

Question 15

Which has higher precedence, abstraction or application?

Answer 15

Application has higher precedence than abstraction

λx.A B = λx.(A B)

not (λx.A) B <– This makes B an argument

Question 16

Express the following nested list expression with parenthesis.

λ x y z . E

Answer 16

(λ x. (λ y . (λ z . E )))

Question 17

Give names to λ expressions

Example: define f = (λ x . ((+ x) 1))

What is this in ML and Scheme?

Answer 17

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)

Question 18

Reduction rules in lambda expressions:

Answer 18

Apply a set of reduction rules to simplify the expression

4 kinds of reduction rules:
δ (delta)
β (beta)
α (alpha)
η (eta)

Question 19

Delta Reduction:

Use for the built-in constants

Answer 19

+ 2 3
->δ
5

Read “+ 2 3” reduced to 5 with the delta indicating that reduction used a delta rule

Question 20

Delta Reduction:

* (+ 1 2)(- 5 1)

Answer 20

Question 21

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)

Answer 21

Question 22

Beta Reduction:

( (λ x. λ y. + x y) 7 ) 8

Answer 22

Question 23

Issues with Beta reduction:

( λ x. ( (λ x.x) (+ 1 x) ) ) 3

Answer 23

Question 24

Name clash resolution:

The example again

(λ x. (λ x.x) (+ 1 x)) 3

Answer 24

Question 25

Alternative reduction:

(λ x. (λ x.x) (+ 1 x)) 3

Answer 25

Previous Reduction:

Question 26

Eta Conversion

Answer 26

Question 27

What is Normal form in Lambda Calculus?

Answer 27

A lambda expression is in normal form if it cannot be further reduced using beta reduction, a delta rule, or eta reduction.

Question 28

Can every lambda expression be reduced to normal form?

Answer 28

No, not all expressions can be reduced to normal form.

Question 29

Not all expressions can be reduced to normal form.

Are there any consequences of the failure to find normal form for all expressions?

Answer 29

Question 30

Is there more than one way to reduce a lambda expression?

Answer 30

Yes

Question 31

If there is more than one reduction strategy, does each lead to the same normal form expression?

Answer 31

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.

Question 32

Is there a reduction strategy that guarantees that a normal form expression will be produced (if there is one)?

Answer 32

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.

Question 33

Outermost and Innermost example:

Answer 33

Question 34

Definitions:

Answer 34

• 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

Question 35

(T/F)

Lambda calculus has computational power equivalent to Turing machines

Answer 35

True

Question 36

What are the two reduction strategies?

Answer 36

Question 37

Connection between reduction strategies and parameter passing.

Answer 37

Question 38

Example of normal vs applicative order reduction:

Answer 38

Question 39

What is an alternative to Normal order and Applicative order reduction?

Answer 39

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.

Question 40

Lazy Evaluation Example:

Answer 40

Question 41

Benefits of Lazy Evaluation

Answer 41

Question 42

Example: booleans and conditionals

show if true a b = a

Answer 42

Question 43

Do functional programming use iteration?

Answer 43

No. Recursion is used instead.

Question 44

Info on recursive functions:

Answer 44