Sections 2.1 and 2.2 Flashcards
Fill in the blank
Executing a functional program consists of ____ an expression.
Executing a functional program consists of evaluating an expression.
p. 4
Fill in the blank
A functional program has a natural representation as a ____.
A functional program has a natural representation as a graph.
p. 4
Fill in the blank
Evaluation proceeds by means of a sequence of simple steps, called ____.
Evaluation proceeds by means of a sequence of simple steps, called reductions.
Hence the term graph reduction.
p. 4
What does the term redex stand for?
“reducible expression”
p. 10
How does one read the right-pointing arrow?
→
→
“reduces to”
p. 10
Given all functions take a single argument, how should one understand the following?
(+ 3 4)
“the function +, applied to 3, the result of which is a function applied to 4.”
Fill in the blank
(+ 3 2) ←→ ((+ 3) 2)
Or in words, “Function application is ____ associative.”
Function application is left associative.
p. 11
Fill in the blank
Lambda abstraction is ____ associative.
λx . λy . E
Lambda abstraction is right associative.
λx . λy . E → (λx . (λy . E))
Adhiraj
CONS is short for what?
“construct”
p. 12
Fill in the blank
The lambda calculus provides a construct, called a lambda ____, to denote new, non-built-in functions.
(λx . + x 1)
The lambda calculus provides a construct, called a lambda abstractions, to denote new, non-built-in functions.
p. 12
What is a good way to read the following?
(λx . + x 1)
“That function of x which adds x to 1.”
Always those four parts. λ, parameter, dot, body.
p. 12
What are the four expression types?
constants, variables names, applications, lambda abstractions
<exp> :: = <constant>
| <variable>
| <exp> <exp>
| λ<variable> . <exp>
Figure 2.1, Syntax of a lambda expression (in BNF)
p. 13
What do we know about the expressions e and E ?
-
e(lower-case) is a variable. -
E(upper-case) is any lambda expression
Which variable is free? Which is bound?
(λx . + x y) 4
x is bound.y is free.
p. 14
Which variables are free? Which are bound?
\+ x ((λx . + x 1) 4)
first x is free.
second x is bound.
p. 15
What term describes this conversion?
(λx . + x 1) 4 → + 4 1
β-reduction
Instances of the parameter are replaced with the argument.
p. 15
What term describes this conversion?
\+ 4 1 ← (λx . + x 1) 4
β-abstraction
Introduces a new lambda abstraction
p. 18
What term covers both of these cases?
(λx . + x 1) 4 ←β→ + 4 1
β-conversion
Both β-reduction and β-abstraction
p. 18
What term describes this equivalence?
(λx . + x 1) ←→ (λy . + y 1)
α-conversion
“alpha”
p. 18
What term describes this equivalence?
(λx . + 1 x) ←→ (+ 1)
η-conversion
