Studied by 20 people
Looks like no one added any tags here yet for you.
What is a Turning Machine?
An abstract machine model to reason about computation
ƛ- terms are built using only
variables, applications, and ƛ-expressions
Apply one B-reduction step to the ƛ-expression (ƛy, (x y)x)z
(x z)x
When was the turning machine invented
1936
What are the two things that the turning machine has
Moveable read/write head and finite stakes
The turning machine has infinite tapes with cells containing what?
symbols
In the program order for the turning machine what is step 1
State In
What is an exampleIn the program order for the turning machine what is step 2
Symbol In/Out
In the program order for the turning machine what is step 3
L/R
In the program order for the turning machine what is step 4
State Out
What is an example of a “State In“
inc
What is an example of a “Symbol In/Out“
0 or 1
What is an example of “L/R“
R or L
What is an example of “State Out“
stop or inc
What does a lambda expression look like in haskell?
\x → x * x
Beta Reduction is ?
the process of calculating a result from the application of a function to an expression
What is this (\x → x * x) ?
Lambda Expression
(\x → x x) => 3 × 3 is called what ?
Beta Reduction
What is pebble stones ?
A wooden board and put pebbles on it to perform calculus
What is the pebble stones based off of
roman numerals
In the pebble stones calculator what is the pebble called
calculi
What is the first thing a ƛ-term can be
variable (x,yz)
What is the second thing a ƛ-term can be
application (P Q)
What is the third thing a ƛ-term can be
ƛ-abstraction (ƛx. P)
Who came up with ƛ-Calculus
Alonzo Church
What year did Alonzo Church come up with ƛ-calculus
1930’s
What does syntax mean
how you write it
What does semantics mean
what it does, mean , and do
when you do a lambada expression + beta reduction what do you get
Turning Machine
What is a redex
Reduction Expression
Haskell is lambda but with what
sugar syntax for easy on the eyes
Built in stuff (speed)
Static types (safety)
What is a lambda term really
a sequence of strings
What is 0 as a ƛ- expression
ƛf. ƛx. * x
What is 1 as a ƛ- expression
ƛf. ƛx. * fx
What is 2 as a ƛ-expression
ƛf. ƛx. f(fx)
What is the increment function in ƛ-expression
ƛn. ƛf. ƛx. (nf)(fx)
Does ƛ-calculus have sequence of operations
no
What is alpha congruence
changing variable to be unique to not be confused
What is this called when we change the variable from this (ƛf. ƛx x) → (ƛg. ƛy. y)
alpha congruence
What number is this in ƛ- calculus
ƛf. ƛx. x
0
What number is this in ƛ-calculus
ƛf. ƛx. fx
1
What number is this in ƛ - calculus
ƛf. ƛx. f(fx)
2
What is this in ƛ- calculus
ƛn. ƛf. ƛx. (nf) (fx)
inc
what does alphabetically represent
letters
What does lexicographically
dictionary order
When looking at evaluation strategies what is this an example of
(\x → x x)(1 + 2) => (\x - > x x)3 =B> 3*3 => 9
rightmost / innermost
When looking at evaluation strategies what is this an example of
(\x → x x)(1+2) => (1+2) (1+2) => 3 + (1+2) =>
3 * 3 => 9
leftmost / outermost
What evaluation strategy does hakell use?
leftmost / outermost (lazy evaluation)
lambda calculus do recursion True or False
False
What is addition in ƛ-calculus in haskell
\m n f x → m f (n f x)
what is mutiplication in ƛ-calculus in haskell
\m n f x → m (n f) x
In haskell what does this evaluate to
(\x => x * x)(1+2)
9
In haskell what does this evaluate to
head [1,2,3]
(\x → x * x) (head [])
exception
In haskell what does this evaluate to
head [1,2,3]
(\x → 7) (head [])
7
In haskell what does this evaluate to
map (2*) [1,2,3]
[2,4,6]
In haskell what does this evaluate to
head(map (2*) [1,2,3])
2
in haskell what does this evaluate to
head(map (2*) [1, head [], 3])
2
What does this evaluate to in haskell
take 10 (map (2*) [1 . .]])
[2,4,6,8,10,12,14,16,18,20]
What does this evaluate to in haskell
head (2*1 : map (2*) [2,3])
2
What is a redex
left hand side of a reduction rule (a lambda applied to something)
What does it mean to be in normal form
A ƛ-expression with no redex
What does it mean to be in weak head normal form (WHNF)
if it has a ƛ-abstraction (or constructor or partially applied built in function in haskell) also no redex on the outside
What is computation
reduction of a ƛ-expression to normal form (or WHNF)
What is the Church-Rosser Theorem
The ƛ-calculus is confluent (flowing or merging some strategies faster than others)
What is the evaluation strategy of Applicative Order
right-most/inner most redex first
What is the evaluation strategy of call-by-value
like applicative order, but no reductions inside ƛ-abstractions
What is the evaluation strategy of normal order
left-most/outer-most redex first
What is the evaluation strategy of call-by-name
normal order, but stop at WHNF (no reductions inside ƛ-abstractions)
What is the evaluation strategy of call-by-need
call-by-name + memoization (optimization technique used primarily to speed up)
What is the evaluation strategy of lazy evaluation
an implementation of call-by-need with thunks (A thunk is an object in heap memory storing the state of the delayed evaluation of a function) used by haskell
Consider the following C code snippet:
int n = 0;
void count(int k) {
printf(“count: %d\n”, n += k);
}
Where will memory for the C-string “count: %d\n“ be allocated
static memory because there is no change in size
Consider the following C code snippet:
int n = 0;
void count(int k) {
printf(“count: %d\n”, n += k);
}
Where will the memory for the variable n be allocated?
static memory because global variables go there
Consider the following C code snippet:
int n = 0;
void count(int k) {
printf(“count: %d\n”, n += k);
}
Where will the memory for the variable k be allocated
on the stack
What form is this in
ƛy. (ƛx. x)y
WHNF
What form is this in
(ƛy. y)x
not normal
What does functional programming mean
functions that are evaluated are the main way of gaining and transforming data, functional programming is stateless. Rather than assigning values which can then be mutated like what happens in imperative languages, the value returned by a function is only dependent on its input.
What does imperative programming mean
a list of steps that need to be executed, there needs to be some way of keeping track of everything computed to that point. That’s (obviously) where variables come in. They are keeping the “state” of where the program is at which then can control where the program should go to next which continues to modify the state.
What is Haskell’s default evaluation strategy
lazy evaluation aka normal form
What is the next redex in normal order (left most/ outer most) of the lambda-expression
(ƛy. (ƛx. x) y) ((ƛz. z) 3)
(ƛy. (ƛx. x) y) ((ƛz. z) 3)
Do beta reduction on this lambda-expression
(ƛy. (ƛx. x) y) ((ƛz. z) 3)
(ƛx. x)(ƛz. z)3
Evaluate the ƛ-expression ƛy. (ƛx. x) y to WHNF
ƛy. (ƛx. x)y
What is the next redex in applicative order (right most/ inner most) of the lambda-expression (ƛy. (ƛx. x)y) ((ƛz. z) 3)
(ƛz. z)3
What is the first memory allocation type
static
what is the second memory allocation type
automatic allocation (stack)
what is the third memory allocation
dynamic (heap)
Where do global variables go
static
automatic allocation
dynamic
1
Which memory does not change in size
static
automatic allocation
dynamic
1
Which memory is allocated at loadtime and it is fixed in size during runtime
static
automatic allocation
dynamic
1
What is another word for stack
automatic allocation
to pop on the stack what do we do
decrement
to push on the stack what do we do
increment
what is an analogy or a reference that relates to the stack
pop/push or buffet style
In memory where is local variables stored
static
automatic allocation
dynamic
2
In memory where are return addresses stored
static
automatic allocation
dynamic
2
What is stackoverflow
It is uncontrolled recursion (should be linear or logarithmic) and when big stuff goes in there that is not supposed too
How long does it take to allocate and deallocate in automatic allocation
A few nanoseconds
True or False does each processor have its own stack
True
How long does the heap take
it takes a few microseconds
Which one is bigger in terms of memory heap or ram
heap and could possibly have more
what are two things the heap is known for
holding large items and being persistent
Note
Flashcard