Chapter 1

Question 1

3 types of lamda calculus terms

Answer 1

a variable
a function applied to an argument
a lambda term - function with input parameter and function body

Question 2

Meaning of lambda term

t0 t1

Answer 2

function t0 applied to argument t1

Question 3

Function application is what associative

Answer 3

left associative

t1 t2 t3 = (t1 t2) t3

Question 4

Higher order function

Answer 4

A function that can accept other functions

Question 5

A variable name is free in an expression if 1 of the following three cases hold:

Answer 5

is free in
is free in E1 E2 if is free in E1 or it is free in E2
is free in lambda. if != AND is free in

Question 6

A variable is bound in two cases:

Answer 6

is bound in lamdba . if the identifer = or if is bound in
is bound in E1 E2 if is bound in E1 or bound in E2

Question 7

Can the same identifier occur free and bound in the same expression?

Answer 7

Yes

Question 8

FV(x) = ?

Answer 8

FV(x) = {x}

Question 9

FV(t0 t1) = ?

Answer 9

FV(t0) U FV(t1)

Question 10

FV(lambda x, t) = ?

Answer 10

FV(lambda x, t) = FV(t) - {x}

Question 11

BD(t) = ?

Answer 11

var(t) - FV(t)

Question 12

bound variable

Answer 12

defined by the closest lambda operator

Question 13

lexical (static) scoping

Answer 13

the variable’s scope is defined by the text of the program

Question 14

What does lexical in lexical scoping mean?

Answer 14

It is possible to determine the scope before the program runs by inspecting the program text

Question 15

a term is closed if

Answer 15

all variables are bound

Question 16

a term is open if

Answer 16

not all variables are bound

Question 17

alpha reduction

Answer 17

renaming a bound variable

Question 18

alpha equivalent

Answer 18

if a term alpha reduces to another term

Question 19

what is alpha reduction also called alpha renaming?

Answer 19

Defines an equivalence relation on the set of terms, but doesn’t make computational progress

Question 20

What does t{y/x} notation mean?

Answer 20

substituting all occurences of x in t with y ….y substitutes for x

Question 21

B-reduction

Answer 21

main computational rule in lambda calculus; done by capture avoiding substitution

Question 22

steps of B-reduction for (lambd x. t) t’

Answer 22

1. If no free variables in t’ is bound in the function body t (FV(t’) intersects BD(t) = empty set, replace all occurences of x in t with t’
2. Otherwise, apply alpha-reductions until the first rule applies